1.5 The Abstract Refal Machine

The Refal machine is an abstract device which executes Refal programs. It has two potentially infinite information storages: the programfieldand the viewfield. 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 Fis a function symbol and   an expression, in order to transform it using the definition of Fin the program. This sub-expression is referred to as the primaryactivesub-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, as1 the Refal machine comes to an abnormal stop `Recognitionimpossible'.

To compute the value of some function Fwith 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 builtin 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.