The Refal machine is an abstract device which executes Refal programs. It has two potentially infinite information storages: the program field and the view field. The program field contains a Refal program which is loaded into the machine before the run and does not change during the run. The view field contains an expression without free variables; we refer to such expressions as ground expressions. The view field (i.e., the expression in the view field) changes in time as the machine works.
The Refal machine works by steps. Each step is executed as follows. If the
expression in the view field includes no evaluation brackets
(we shall refer to such expressions as passive),
the Refal machine comes to a normal stop. Otherwise it picks up one of the
sub-expressions of the form
<
F
>
, where
F
is a function
symbol and
an expression, in order to transform it
using the definition of
F
in the program.
This sub-expression is referred to as the primary
active sub-expression. It is defined as the first (from the left)
sub-expression
<
F
>
such that
is passive, i.e., includes no
evaluation brackets.
The primary sub-expression
<
F
>
is transformed as follows.
The Refal machine compares
with the consecutive sentences of the
definition of
F
, starting with the first one, in search of an
applicable sentence. A sentence is applicable if
can be
recognized as the pattern
in its left side, i.e., the matching
:
is successful. On finding the first applicable sentence,
the Refal machine copies its right side
and applies to it the substitution
resulting from the matching
:
. Thus the free variables in
are replaced by the values they have taken in the matching.
The ground expression thus formed is then substituted for the primary
active sub-expression
<
F
>
in the view field. This completes the
current step and the machine proceeds to execute the next step.
If there is no applicable sentence in the definition of
F
,
the Refal machine comes to an abnormal stop `Recognition impossible'.
To compute the value of some function
F
with the argument
(which must be an object expression), we put
<
F
>
in the
view field of the Refal machine and switch it on. If, after a finite number
of steps, the Refal machine comes to a normal stop, then the contents
of the view field (an object expression, again) is the value of the
function. If it runs forever or comes to an abnormal stop, the value
of the function call is undefined.
The order of computation of nested function calls used in Refal is known as applicative or the inside-out order. Before starting to compute any function call we complete the evaluation of all function calls in the argument.
In addition to functions defined in Refal by sentences, there are a few functions which need not (and in many cases cannot) be defined in Refal but can still be used, because they are built in into the system. Input-output functions and the functions executing arithmetic operations, among others, belong to this category. The implementation of the Refal machine on the computer is different from the abstract Refal machine in that before looking for the definition of a function in the program field, the system checks whether the function's name is in the list of available built-in functions. If it is there, the corresponding subprogram is activated which performs the required operations and replaces the function call in the view field by its computed value.