Refal: Recursive Functions Algorithmic Language

Last month, while reading a post by Cyril Slobin, dated “Fri, 12 Dec 2008 09:20:35 +0300,” in the thread “Beginnings – History of Declarative Languages” on the Qilang mailing list on the Qi programming language, I came across a reference to an unusual functional programming language called “Refal.”  “Refal” is short for “Recursive functions algorithmic language,” and is a language designed by Valentin Turchin for symbol manipulation.

Refal is based on pattern matching, and unlike Prolog, pattern matching in Refal works forwards, not backwards.

To illustrate a Refal program in action, let us consider the problem of determining whether a given string is a palindrome.  Here is a formal definition of a palindrome (quoted from “Section 1.1: A Simple Function Definition” of the online manual “REFAL-5: programming guide & reference manual“):

1. An empty string is a palindrome.
2. A string of one symbol is a palindrome.
3. If a string starts and ends with the same symbol, then it is a palindrome if and only if the string which remains after the removal of the first and the last letters is a palindrome.
4. If none of the above are applicable, the string is not a palindrome.

Based on the above definition, here is an example of a typical Refal program for determining whether a given string is a palindrome:

Pal { = True;
     s.1 = True;
     s.1 e.2 s.1 = <Pal e.2>;
     e.1 = False;  }

Here, “Pal” is the function name, followed by a definition.  In the definition, the first line matches a blank string with “True.”  Thus, an empty string is a palindrome.

In the next line, “s.1” is a free variable of type symbol, which matches any single symbol, but only a single symbol, with “True.”  (The ‘1’ here is a subscript.)  I.e., such symbols as ‘a,’ ‘1,’ ‘%,’ etc. match with “True,” and hence are palindromes as well.

In the following line, “e.2” is a free variable of type expression, where an expression is the most general data type in Refal, possibly being a string of symbols.  This line matches any single symbol, followed by any expression, followed by the same single symbol.  Angular brackets denote a function call, so “<Pal e.2>” denotes a recursive call of Pal on “e.2.”  Here, “e.2” is just the inner expression, sans the outer pair of identical symbols.  Thus, “aba” will match and then recursively call Pal on the inner ‘b,’ “abca” will call on the inner “bc,” “ab1a” will call on the inner “b1,” and so forth.

In the last line, any other expression which does not match the other two lines above it is not a palindrome.  E.g., “ab” is not, nor is “a%,” nor is “a1,” nor are any other similar expressions that do not match the above two lines.

In practice, Pal is called with a line such as the following at the top of a .ref Refal source file:

$ENTRY Go { = <Prout <Pal ‘tattarrattat‘>> }

Here, “tattarrattat” can be replaced by any other palindrome.  (I haven’t yet proceeded far enough to explain this line in the manual, so I shall leave explanation of this line for a possible alternative time.)

The above-referenced Refal manual also includes a reference to an online Refal compiler for viewing, editing, compiling, and executing Refal snippets in a Web browser.  This compiler even saves source code in a temporary file between Web sessions!

There is also Refal-SciTE, a compact combined GUI-based editor, REPL, and compiler, based on Refal-5 and the SciTE editor.

What I find especially notable about Refal is its emphasis on symbol manipulation, instead of numeric computation.  Many other functional languages tend to focus more on numeric computation; however, one of my original interests in programming back in the 1980’s, when I was still reading such ancient computer magazines as Byte, was in simulating human verbal communication.  I fondly remember one article back at the time (unfortunately, I do not remember in which magazine the article had been published) about somebody who had written a simple program (I think that it had actually been in a dialect of BASIC) to create sentences using grammatical units stored in a dictionary which was part of the program.

This person reportedly spent just one afternoon writing the program, and then sat back for several hours as he watched, fascinated, as the program output sentence after sentence of original prose, in which some sentences were quite unusual and unlike anything that a human being would naturally come up with.  For example (I am coming up with these examples on my own, based upon what I remember of the kinds of examples given in the article), some possible sentences created by the program could be the following:

Fish swim in cheese under umbrellas.

Nelson coughed dynamite eating raw fish.

Jack sweated programs sleeping monkeys.

These are all grammatically correct English sentences, but unlike anything that most English speakers would come up with on their own, because the ideas behind them tend to be considered absurd or preposterous by most human English speakers.  However, a computer program that simply pulled grammatical units out of a dictionary and matched them at random in following grammatical rules could easily come up with such examples.  It is precisely the absurdity of such examples that caused their type to stick in my mind and to stay there for more than twenty years.

Other examples of functional programming languages focusing on symbol processing often cited are LISP and Scheme, but while Scheme remains one of my favorite functional programming languages, it lacks pattern matching.  Prolog has pattern matching, but employs backtracking instead of forward reasoning; in addition, Prolog programs tend to be very verbose compared to equivalent programs in such functional programming languages as Haskell.

Furthermore, recently my interests have been veering towards such statically typed programming languages as Haskell, Typed Scheme, and Qi, which have the advantage of increasing the probability that a program which successfully compiles does not need to be debugged (while decreasing the probability that a program hastily written will compile in the first place).

Moreover, I tend to enjoy the mental gymnastics of writing in a purely functional programming language, which does not allow side effects, such as Haskell; it is rather like trying to navigate through town while being limited to jumping over the tops of buildings and flying down their staircases like Spider-Man.  To stretch the analogy, the higher-order functions are the buildings, the spider webs are the maps, and the staircases are the recursive calls, which typically bottom out at the zeroth floor level.  There are fewer steps required, because each step jumps over an entire building, or maps over an entire series of buildings, but if you actually want to get in or out of a building, you need to do something special in binding yourself in returning through the door.

Yet while the purely functional style of Haskell often leads to interesting mental exercises in concocting elegant programs that do not rely on side effects, most Haskell examples tend to be focus on some form of numeric computation, rather than symbol manipulation; in addition, most discussion on Haskell seems to touch on some form of mathematics, often category theory; there is relatively little discussion focusing on symbol manipulation.  Refal, on the other hand, specializes in symbol manipulation, uses forward reasoning, and is concise.  I have barely started reading about Refal, but it seems a possibly interesting alternative for writing programs to deal with words and phrases.