6.2 Metacode
Program transformation is one of the important fields
where Refal is used; both the programs to be transformed
(level 1, object programs)
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
, we say that we downgrade
it to the metacode; applying the inverse transformation
we say that we upgrade
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
; for upgrading we reserve the up arrow
.
When the range of these operations extends to the end of the current
sub-expression, we simply put
or
in front
of it. If it is necessary to delimit the range, we use braces.
For example, the concatenation of the downgraded
1 with the
unchanged
2 is {
1}2,
while (
1
)2
is the same as ({
1})
2.
Obviously,
=
; and if
exists,
then
= .
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
e1
must be equal to
e1
,
because
e1
is an object
expression. It follows that two different objects, e1
and
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 | its metacode |
| sI | '*S'I |
| tI | '*T'I |
| eI | '*E'I |
| < F > | '*'(( F) ) |
| () | () |
| 1 2 | {1} 2 |
| '*' | '*V' |
| S (but not '*') | S |
Thus
eX
is '*E'X
,
s1
is '*S'1
,
'a*b'
is 'a*Vb'
,
<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 Dn
which 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 0,
<Dn 0> == 0
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
'*!'(0)
to represent the delayed metacode of 0.
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 '*!'(0)
back into 0.
The following rule helps to handle delayed metacoding:
for any (not only object) expression .,
'*!'() is equivalent to <Dn >
Indeed, even if 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 0,
then Up
returns 0:
<Up <Dn 0>> == 0
But we can extend the domain of Up
to include
metacodes of any ground expression
gr
(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 gr,
<Up gr> == gr
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 gr>
is a simulation of the evaluation
of gr -- as one can see from the definition of Up
.
This function converts the ``frozen'' function calls in gr 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'X
should 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 gr,
but works faster. In one step it puts gr 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 Up
are visible from the module in which the call of Up
occurs. If your function using Up
is defined in an
auxiliary module, replace it by UpD
and define UpD
in 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 and ,
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) <Add (35)16>
(b) <Up (<F (e1)e2>)'*!'(e3)>
(c) '*'((Comp) 'A*VB')
(d) '*!'('A*B')
Exercise 6.4
Compute:
(a) <Dn <Add (35)16>>
(b) <Up '*!'('A*B')>