1.1 A Simple Function Definition

Consider this very simple problem. You want to define a function that determines whether a given string of characters is or is not a palindrome. A palindrome is a string which reads the same from left to right and from right to left. There are two obvious ways to make this definition precise. The first is to define a procedure of reversing the string and then compare the reversed string with the initial string. Clearly, an algorithm written on the basis of this definition will not be the most efficient. If the string ends with a character different from the starting character, then it is not a palindrome, and this can be established without reversing the whole string. Therefore, we shall adopt the other definition, which we can write down in the usual mathematical form:

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.

Let us call Pal the function we want to define, and let it take the value True in case the argument is a palindrome and False otherwise. The definition in Refal will closely follow the mathematical definition:

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

This program starts with the function name followed by a block enclosed in braces. A block is a list of sentences separated by semicolons. In our case there are four sentences, each corresponding to one clause in the verbal mathematical definition above. A sentence is a replacement rule. Its left side represents a pattern of the argument of the function; the right side, separated by the equal sign = , is a replacement for the function call.

In the first sentence the argument of the function Pal is empty, thus the value must be True .

In the second sentence the argument is given as a free variable of symbol s.1 . It will match any symbol, such as a character, but only one symbol. Thus the sentence is read: if the argument is a single symbol, replace the call by True .

The third sentence represents the case where the argument starts and ends with some symbol s.1 , and has any expression e.2 in between. An expression is the most general data structure in Refal; in particular, it may be a string of symbols. The right side of this sentence is a call of function Pal of the argument e.2 . We use round brackets (parentheses) for creating data structures, but angular brackets to denote function call. We write <Pal e.2> for what would be written in mathematical notation as pal(e₂) .

Finally the argument in the last sentence is an arbitrary expression (string). Each sentence in a function definition in Refal is used only if all preceding sentences were found inapplicable. Thus the last sentence is read: if none of the above, then with any argument the value of the function call is False .

A precise definition of the algorithmic meaning of Refal programs is achieved through the definition of the abstract Refal machine (see Sec. 1.5) which executes Refal programs, i.e., evaluates functions defined in Refal. The Refal machine works by steps, each step being an application of one sentence. If, e.g., we turn to the Refal machine the call of Pal with the argument 'revolver' , i.e., <Pal 'revolver'> , then the working space of the Refal machine (which we refer to as the view field) will pass through the following stages:

<Pal 'revolver'>
 <Pal 'evolve'>
  <Pal 'volv'>
   <Pal 'ol'>
     False