6.2 Metacode

Program transformation is one of the important fields where Refal is used; both the programs to be transformed (level 1, objectprograms) and the transforming programs (level 2) will be typically written in Refal -- this makes self-application of transforming programs possible.

To write Refal programs that deal with Refal programs, we have to represent object programs by some object expressions because free variables and activation brackets which are used in object programs cannot be objects of transformation in Refal. Indeed, suppose that we have some program and want to transform every call of a function F1 in it into the call of F1 . A sentence like:


  Subst21 { e1 <F1 eX> e2  =
             e1 <F2 eX> <Subst21 e2>; }
will not work. According to the syntax of Refal, active sub-expressions cannot be used in the left side. But even if we extended Refal to allow such a use, the active sub-expression <F2 e1> in the right side would be understood as a process, not an object; the evaluation of this call would start before the further evaluation of Subst21 , even though we did not want it. Likewise, we cannot use a free variable as an object of transformation, because it will be understood by the Refal machine as a signal for substitution.

A mapping of all Refal objects on a subset of object expressions will be referred to as a metacode. Such a mapping must, of course, be injective; i.e., the images (``the metacodes'') of distinct Refal objects must be distinct, so that there is a unique inverse transformation. Metacode transformation is the lowering of the metasystem level of the object -- from a controlling device to an object of work. Therefore, when we apply a metacode transformation to an expression E , we say that we downgradeit to the metacode; applying the inverse transformation we say that we upgradeE  from the metacode. When we actually write Refal programs dealing with Refal programs, we must choose a certain concrete metacode transformation. But when we speak about downgrading and upgrading expressions, we often want a notation allowing us to leave these transformations unspecified. Thus downgrading to the metacode will be represented by a down arrow down_arrow  ; for upgrading we reserve the up arrow up_arrow  . When the range of these operations extends to the end of the current sub-expression, we simply put down_arrow  or up_arrow  in front of it. If it is necessary to delimit the range, we use braces. For example, the concatenation of the downgraded E1 with the unchanged E2 is { down_arrow E1}E2, while ( down_arrow E1)E2is the same as ({ down_arrow E1}) E2. Obviously, up_arrow down_arrow E = E; and if up_arrow E exists, then down_arrow up_arrow E = E.

The purpose of metacoding is to map activation brackets and free variables on object expressions. It would be nice to leave object expressions unchanged in the metacode transformation. Unfortunately this is impossible because of the requirement of a unique inverse transformation. Indeed, suppose that we have such a metacode. Then down_arrow down_arrow e1 must be equal to down_arrow e1 , because down_arrow e1 is an object expression. It follows that two different objects, e1 and down_arrow e1 , have identical metacodes.

We can, however, minimize the difference between an object expression and its metacode. The metacode we are using in the Refal system singles out one symbol, namely the asterisk '*' , which is changed in the metacode transformation. All other symbols and object brackets (parentheses) are represented by themselves. The following table defines our metacode:

Expression E

its metacode down_arrowE

sI

'*S'I

tI

'*T'I

eI

'*E'I

< F E>

'*'(( F) down_arrowE)

(E)

(down_arrowE)

E1E2

{down_arrowE1} down_arrowE2

'*'

'*V'

S (but not '*')

S

Thus down_arrow eX is '*E'X , down_arrow s1 is '*S'1 , down_arrow 'a*b' is 'a*Vb' , down_arrow <F e.Arg>is '*'((F)'*E'Arg) etc.

When the metacode transformation is applied to an object expression, its result can be computed by calling the Refal function Dnwhich replaces every '*' by '*V' :


Dn {
   '*'e1  =  '*V' <Dn e1>;
   s2 e1 = s2 <Dn e1>;
   (e2)e1 = (<Dn e2>) <Dn e1>;
    = ; }
 The function Dn is also implemented in the Refal system as a built-in function which downgrades its argument in one step.

For any object expression E0,


  <Dn E0>  ==  down_arrowE0

The time required for downgrading or upgrading an object expression is proportional to its length. It is often desirable to delay the actual metacoding of an expression until the moment when its downgraded form is actually used because it well may happen that the whole expression, or its part, will be later upgraded back to its original self. Therefore, we may avoid an unnecessary two-way transformation of an expression if we somehow indicate that the expression must be put in the metacode but do not actually transform it. We use the expression


  '*!'(E0)   to represent the delayed metacode of E0. This does not violate the uniqueness of the inverse transformation because the combination '*!' could not have arisen in any other way. Thus the inverse transformation will simply transform '*!'(E0 ) back into E0 . The following rule helps to handle delayed metacoding: for any (not only object) expression .,


  '*!'(E)          is equivalent to        <Dn E>

Indeed, even if E includes free variables and active sub-expressions, the implied sequence of actions on both sides of this equivalence is the same: first free variables must be replaced by object expressions, then the computation process must start and end, and then the result must be downgraded.

 The inverse function of Dn is Up . If its argument is the result of a metacode transformation of an object expression E0 , then Up returns E0:


  <Up <Dn E0>>  ==  E0 But we can extend the domain of Up to include metacodes of any ground expression Egr (i.e., one that may contain active subexpressions but no free variables). Take a ground expression, e.g., <F 'abc'> , and downgrade it into the object expression '*'((F)'abc') . Now if we apply Up to it, it will be upgraded back to the original active expression:


  <Up '*'((F)'abc')>  ==  <F 'abc'>
which will immediately start a computation process. Generally, for any ground expression Egr,


 <Up down_arrowEgr>  ==  Egr

The function Up can be defined in Refal as follows:


  Up {
     '*V'e1 = '*'<Up e1>;
     '*'((sF) e1)e2 = <Mu sF <Up e1>> <Up e2>;
     '*!'(e2)e1 = e2 <Up e1>;
     s2 e1 = s2 <Up e1>;
     (e2)e1 = (<Up e2>)<Up e1>;
      =  ; }
 

The evaluation of <Up down_arrowEgr> is a simulation of the evaluation of Egr -- as one can see from the definition of Up . This function converts the ``frozen'' function calls in Egr into their active form, and does this in exactly the same inside-out order as the Refal machine would do.

Exercise 6.2 If the the function Up meets the first metacode of a free variable, e.g., '*E'X , it will leave it unchanged, and that would be an error. When its argument is not a metacode of a ground expression, this function must be undefined. Indeed, the upgrading of '*E'Xshould result in the free variable eX which will be put in the view field; however, this is not allowed by the definition of the Refal machine. Modify the above definition of Up so that when the argument is out of the domain, an error message is printed and an abnormal stop occurs.

Actually, the above definition of the function Up is of a purely academic interest because the Refal system includes the built-in function Up which is equivalent to our Refal definition for an argument down_arrowEgr , but works faster. In one step it puts Egr in the view field of the Refal machine. In addition, its domain is extended to include the metacode of  any Refal expression, not necessarily a ground one. This will be discussed in Sec. 6.4.

Using the function Up , we have the same alternatives, in terms of modular structure, as with Mu . Our built-in function Up is static. The user must see to it that the functions intended for activation by Upare visible from the module in which the call of Upoccurs. If your function using Up is defined in an auxiliary module, replace it by UpD and define UpDin the main module:


  $ENTRY UpD { eX = <Up eX> }
in a full analogy with the treatment of Mu .

NOTE: One must keep in mind the difference between down_arrow and up_arrow, on one hand, and Dn and Up , on the other hand. The former are just metasymbols used to denote certain Refal objects; they are not Refal objects themselves and no part of the Refal system. The latter are legitimate function names.

Exercise 6.3 Expand into Refal expressions (if possible):


(a) down_arrow<Add (35)16>(b) down_arrow<Up (down_arrow<F (e1)e2>)'*!'(e3)>(c) up_arrow'*'((Comp) 'A*VB')(d) up_arrow'*!'('A*B')Exercise 6.4 Compute:



(a)  <Dn <Add (35)16>>
(b)  <Up '*!'('A*B')>