6.4 Freezer

In program transformation, metacoded function calls of level 1 (which usually include some free variables) become arguments of level 2 functions:

  <F² ... <F¹ ... e.1 ...> ... >

i.e.,

  <F² ... '*'((F¹) ... '*E'1 ...) ... >

This is a schematic representation of the situation. In the argument of F² we may have any combination of function calls as well as passive expressions; we refer to these combinations as configurations of the Refal machine loaded with the definitions of level 1 functions.

The basis of any system of program transformation in such languages as Refal is the replacement of a function call by what comes from it in one step of the algorithm. When doing program transformation in Refal, we compare the call with the left sides of the defining sentences which, like functional configurations, are used in a metacoded form. Then we simulate a step of the Refal machine. This process is known as driving. In driving we split the sets of possible values of free variables into subsets corresponding to different sentences of the function definition. This makes it possible for each subset to perform the step in a unique way. Suppose, for instance, that we have the following definition of a function Fa :

  Fa {
     'a's.X e.1 = 'b's.X <Fa e.1>;
     s.2 e.1 = s.2 <Fa e.1>;
     = ; }

and drive the call <Fa e.1> . The result of one step of driving is a graph where directed edges designate some subsets of the full set of the variables' possible values, while the nodes represent the configurations resulting from the step. In our case the graph will have three edges (branches). The first branch defines the step for the instance when the value of e.1 starts with 'a' followed by some symbol s.X . It leads to the configuration:

  'b's.X <Fa e.1>

where e.1 now stands for what remains of the original e.1 after the first two symbols are stripped from it. The second branch corresponds to the subset where the first symbol is not 'a' — or it is 'a' but the remaining part of the expression is either empty or starts with a parentheses. The third subset consists of one element: the empty expression.

It is clear that driving, like any form of interpretation, takes much more time than direct computation. Therefore, when there are no free variables in a configuration, it would be much faster to directly compute it than to use the general mechanism of driving. Moreover, whenever the step can be performed in a unique way, independent of the values of free variables, it would also be very desirable to perform it by a direct computation. Suppose, e.g.,, that with the definition above we have this configuration:

  <Fa 'a's.1'bc'e.2>

No matter what the values of s.1 and e.2 are, the resulting configuration will be:

  'b's.1 <Fa 'bc'e.2>

In a similar way, the next two steps will be unique and result in:

  'b's.1'bc' <Fa e.2>

It is only now that the next step depends on the values of the variables, and driving is inevitable. Thus, in some cases driving can be reduced to a direct partial evaluation of function calls.

The Refal system provides the means for an efficient partial evaluation as long as a direct execution of Refal steps does not depend on the values of free variables. This is achieved as follows.

An additional type of object is allowed in the view field. These objects will be referred to as unknown. The information content of an unknown is its type (S, T or E), its level (a non-negative whole number), and its index (a macrodigit). The system knows that an unknown of the s-type stands for a symbol and an unknown of the t-type for a term; this is taken into account in matching. As long as the values of unknown objects are not required for execution of a Refal step, they are passed from one expression to another and may be copied. Their existence, or rather their difference from normal object expressions, is not noticed by the system. Unknown objects can been seen by using the tracer, which prints them out in the form:

  \type.level  index

Unknown objects are created by the function Up and transformed by Up and Dn . If we denote an unknown object of type t, level n, and index i as:

  unknown(t,n,i)

then the extension of these functions' definitions can be described by the following formulas:

  <Up '*'s.T s.I>  =   unknown(s.T,0,s.I);
  <Up  unknown(t,n,i)> =  unknown(t,n+1,i);
  <Dn  unknown(s.T,0,s.I)> = '*'s.T s.I;
  <Dn  unknown(t,n+1,i)> =  unknown(t,n,i);

The built-in function Ev-met (`evaluate over metacode') is available. Its effect on the view field is as if it were defined as follows:

  Ev-met { e.X = <Freezer <Up e.X>>;}

In addition it does some system operations. Freezer is a fictitious function which we need in order to enclose the expression resulting from upgrading and executing the argument of Ev-met. It also ``freezes'' its argument, i.e., downgrades it back into metacode. Freezer cannot be called by the user and appears only when placed by Ev-met. After the argument of Ev-met is upgraded, the process of direct execution starts. It may end in the following three ways:

The execution reaches a successful end with some result which is a passive expression (but still may include unknown objects). Then the call of the freezer is replaced by:
```
  0 
```
At a certain stage of the execution the next step becomes impossible because of an unknown object. Then a freeze takes place. First an enclosing call of Freezer is found. If there are more than one, the innermost call is taken; if there are none, an error condition occurs. Then the argument of Freezer is downgraded to the metacode and the call of the freezer is replaced by:
```
  1 
```
At a certain stage an input-output function call becomes active. It should not be activated and performed because this must happen at run time, not at the time of function transformation. Therefore, a freeze takes place, as in the preceding case. The result is again:
```
  1 
```
At a certain stage of the execution an abnormal stop (recognition impossible) occurs, with some expression. enclosed by the freezer. Then the call of the freezer is replaced by:
```
  2 
```

Note that even though unknown objects essentially stand for the same things as free variables, we had to introduce a special notation for them in order to express the operations over them as Refal sentences. Indeed, something like:

  <Up '*E'X>  =  e.X

would violate the syntax of Refal (a free variable in the right side which is not found in the left side), while:

  <Dn e.X>  =  '*E'X

would define Dn as a completely different function.

Function Up should be used only when we know that its argument does not include free variables. If it does, Up will create unknown objects and since they are not enclosed by the freezer, an error will occur the first time an unknown variable hinders the evaluation. Note that the first thing most built-in functions do is to transform their arguments from the list structure into arrays. Therefore, they cause freezing even before starting their specific work.

Unknowns cannot be dealt with in the same way as all other legitimate (``known'') Refal objects. Their only purpose is to make partial evaluation faster. Whatever you want to do with them, you must first convert all expressions containing unknown objects into metacode. Then unknowns become metacoded representations of free variables.

Let us draw a sketch of the use of the freezer for program transformation. Suppose we have a (metacoded) call of the function Fa to explore:

  '*'((Fa) )

where

is some pattern expression. Before driving it we use the function Try-pe (`try partial evaluation') which is defined as follows:

  Try-pe { e.E = <Checkfr <Ev-met e.E>> }
  * Check the contents of freezer
  Checkfr {
     0 e.E = <Passive e.E>;
     1 e.E = <Drive e.E>;
     2 e.E = <Undefined e.E>;
          }

When we call:

  <Try-pe '*'((Fa) )>

the call of Fa is upgraded and put in the freezer. Suppose

is '*E'1 (an arbitrary argument). Then, without making a single step, the system will downgrade it back and pass to the function Drive for driving. But if

    =  'a*S'1 'bc*E'2

as in the example above, then three steps of the Refal machine will be performed directly, after which the driving will take over. If

is 'a*S'1'bc', the computation will go through to the passive result 'b*S'1'bc'. The function Passive will then define what to do next.

Exercise 6.5 Modify the evaluator described in Sec. 6.3 so that when an abnormal stop occurs, a message is sent, the view field is printed out in metacode, and control is passed to the function Error which is supposed to cope with the situation.