en.SH.PP.RU
six senseless letters
Refal programs operate on expressions. Refal expression is a sequence of terms, possibly empty.
Term may be a single character, a compound symbol, or an expression enclosed in parentheses or angle brackets. It means that parentheses and chevrons in expressions must be balanced.
Single characters are written in qoutes (e.g. '$'). They stick together, thus '$300' is same as '$' '3' '0' '0'. C-quotes like '\n' are supported.
Compound symbols (as opposite to single characters) are sequences of characters which do not start with = nor contain any of this: #;{}()<>' Each compound symbol is treated as a single character.
Sample expressions:
'Hello, world!\n'
<+ ('37')('5')>
'You have ' <alpha> ' apples.'
Refal programs consist of sentences. Each sentence is of form:
<pattern> -> <substitution> ;
Both pattern and its substitution are expressions.
The second part of a program source is an initial view field (a.k.a. VF). This is an expression being evaluated.
Initial view field is written at the end of a program file after an '=' sign.
The program execution is based on replacing expressions in angle brackets (a.k.a. active terms) in the view field with right sides of sentences.
At each execution step, interpreter finds the leftmost active term which itself does not contain active terms (a.k.a. primary active term a.k.a. PAT), then finds such program sentence, that expression in chevrons matches its pattern, and replaces the PAT with its right side.
If the view field does not contain active terms, execution is stopped normally.
Example:
phi 'p' -> '0'; phi '4' -> alpha; phi '3' -> '1'; g alpha -> '5'; g beta -> '6'; f '5' -> '-1'; = <f <g <phi '4'>>>
At the start, primary active term is <phi '4'>. Interpreter
looks for a
sentence with the pattern phi '4', and finds the second sentence.
Then, it
replaces the active term with alpha. The view field is now
<f <g alpha>>.
It finds the PAT again, which is now <g alpha>. It matches the
pattern of
the fourth sentence. Interpreter replaces it with '5'. The view
field
becomes <f '5'>.
<f '5'> matches with the sixth sentence, and it is replaced with
'-1'. The
view field does not contain active terms now, and the program finish with
the result '-1'.
Mathematicians would now say: ``But it's just Markov algorithms!''. They are Turing-complete, but not very handy. This is why patterns may contain variables.
Variables are denoted by a compound symbol starting with `s.', `t.' or `e.'. Examples of variables:
s.x e.tail t.42
Variables bind with parts of a primary active term, corresponding with their type:
Each variable name in the right side of a sentence is replaced by its value.
If the PAT matches several sentences, the first one is used. In case there are several ways to bind variables with values, the leftmost E-var recieves the shortest value.
For example, given a program
remove (s.x) e.1 s.x e.2 -> e.1 e.2;
remove (s.x) e.s -> e.s;
= <remove ('5') '125345'>
The PAT matches with the first sentence. s.x is '5', e.1 is '12' and e.2 is '345'. The result is '12345'.
The PAT matches with the second sentence, too, but it is used only if the string does not contain the character.
As you could notice, in previous examples we used a compound symbol at the start of a pattern to split the program into functions.
We can write recursive functions, too. For example, we can modify `remove', so it will remove all characters from string:
remove-all (s.x) e.1 s.x e.2 -> e.1 <remove-all (s.x) e.2>; remove-all (s.x) e.s -> e.s;
Since the leftmost E-var recieves the shortest value, e.1 would never contain s.x; you can execute this program with -v flag to see, how it is evaluated.
Hash sign # is used for line comments (in Unix style), which means the shebang #! execution is supported. Braces { } are used for multi-line comments (in Pascal style). Nested comments are supported.
© Koshelkov Pjotr, 2026
