[SOLVED] CS interpreter data structure Limits of

Limits of
Computation
7 A universal program (Self-interpreter) Bernhard Reus
1
So far
we have learned the WHILE-language
that we have chosen to represent our notion of computation (to write effective procedures).
We learned how to represent programs-as- data

so now we can write interpreters.
2

Eating your own tail?
We look at a special form THIS TIME of interpreter:
self-interpreter
WHILE-interpreter in WHILE

a very important concept for computability theory (used later)
WHILE
and first an WH1LE-interpreter in WHILE
WHILE
http://www.strangedangers.com/content/item/158424.html
3
Compare to TMs
Turing defined a universal Turing machine U
that can take TM program description D and a word W as input on its tape
and simulate the run of TM D with given input W
so U is aTM program which is an interpreter for TM programs
a self-interpreter in TM
lets use WHILE instead!
4

Use of self-interpreter?
in practice:
cheap way to extend your programming
language with extra features (interpret them in smaller language)
in computability theory:
we will explain this soon. Stay tuned!
5
First consider WH1LE
is like WHILE
but programs can only have one variable. simpler memory management
Can we solve fewer problems in language WH1LE than in WHILE?
6

Interpret WH1LE in WHILE
Since it is simpler, we first look at an
interpreter of WH1LE written in WHILE.
Then we generalise to arbitrarily many variables and obtain a WHILE-interpreter in WHILE.
7
Tree Traversal of ASTs
(with intermediate
results)
NO RECURSION !
initialise tree and value stack to be empty push tree (to be traversed) on tree stack while tree stack not empty
pop a tree t from tree stack
if t is just an opcode o with arity n // a marker then pop n results r1,,rn from value stack
r := o(r1,,rn) // compute intermediate result
push r on value stack else // t proper tree
order of arguments important
if ts opcode has n arguments
then push ts opcode on tree stack // (as marker!)
push n subtrees of t on tree stack else // o is leaf
compute result and push on value stack
8
Recipe

read PD{
P := hd PD ;
D := hd tl PD;
B := hd tl P;
CSt := B;
DSt := nil;
(* input is a list [P,D] *)
(* P = [X,B,X] *)
(* D input data *)
(* B is program block *)
(* CSt is code stack*)
(* initiallycommands of B *)
(* DSt is computation stack for *)
(* intermediate results *)
(* D is initial value of variable *)
val := D;
state := [ CSt, DSt, val ];
(* wrap up state for STEP macro *)
while CSt { (* main loop for interpretation *)
state := state;(* loop body macro *)
CSt := hd state
}
val := hd tl tl state
}
write val
(* get command stack *)
(* get final value of variable *)
(* return value of the one variable *)
CSt is code stack (code in list format), DSt is Stack of intermediate values, val contains value D of the one variable
9
.1.WH1LELF-INTER akeofreadetofrewrit
e form
at describ value stack odestack,fjustone hangeaccocharuleis s:
. . . . value to valnew. Below we will give th1o0se rules in diagrammatic form, showing
7.1. WH1LE CHAPTER 7. SELF-INTERPRETER CHAPTER 7. SE
.
d val
1 Step Macro
sakeofreadability, letuspresentthebehaviourofSTEPasasetofrewriterulesof
the form 1
ability, letuspresenttheb
that describe how the data structures of the traversal DSt, the value stack, CSt the
code stack, and val the store for execution that consists of just one variable,
f STEP as a s performs tree traversal based on CSt, DSt, and val.
[CSt,DSt,val] ) [CSt ,DSt ,val ]
change according to their current values. Diagrammatically, such a rule is depicted
as: ehowthedatastructuresofthetraversalS,the
antheforenonsistso
=) rdihentvalueracally,su
CSt
.
Note that stacks grow upwards here, pushing and popping happens from the top.
Such a rule states that if the current code stack is CSt, the current value stack is
DSt, and the value of our one variable is val, then the STEP macro has to change ..
..
(or update) the code stack to CSt vanld the value stack to CSt and the variable new new
ne
e
w
n
hav
[CSt,DSt,val] ) [CSt ,DSt ,val ] new new new
i
ew
n
our
o
ew
. D that c
DStnew
.
. mm.ati
t valnew
. ng t.o t
.
e stor
. xecutio
DSt
.
. ircu.rre
val
CStnew
.
. s.D.iag
more clearly how the stacks (and the value of the variable) change according to
CSt DSt
CSt DSt
their top elements.
=) new new
. A set of those r.ules then describes, in a way, a big case-stat.ement that tells us . . . what happens depe.nding on what values can be found on top of.the code stack and .
WH1LE-interpreter
7P
se h
h c
c a
value stack, respectively.

their top elements.
A set of those rules then describes, in a way, a big case-statement that tells u
what happens depending on what values can be found on top of the code stack an valu
N the code stac totheonevariabl used
e stack, respectively.
ow according to the interpreter of Fig. 7.2 the initial state sets
e body of the program B, the data stack to nil and the value of th to val, which in diagrammatic form is depicted as follows:
Initial set-up
state := [ CSt, DSt, val ];
B
C2 .
C1
initial stack is the body of the program
B = [C1,C2,,Cn]
data stack (for intermediate results) initially empty
initial value of the one variable
Cn
val
he STEP macro needs to behave as prescribed by the following r
Tewriterulesi
diagrammatic form:
1 als
11
o following the pedagogical route taken by [1] 76
AST Leaves (expressions without arguments)
12
s d
k e
n

Fig. 7.3: STEP macro for evaluating quote and var
We consider the leaves for ASTs, i.e. atoms of the form [quote,a] and variables
of the form [var, X ] where the number encoding the variable name does not mat- ter as it is always the same variable that will be used in a WH1LE-program. The
The evaluation of a quoted literal returns the literal as value which is therefore
diagrammatic form of the rules for AST leaves is depicted in in Fig. 7.3.
pushed on the data stack. The quote expression is popped from the code stack (as it
1
CHAPTER 7. SELF-INTERPRETER 7.1. WH LE
7.1.2.1 Nullary Expressions
Atoms
We consider the leaves for ASTs, i.e. atoms of the form [quote,a] and variables of the form [var, X ] where the number encoding the variable name does not mat-
ter as it is always the same variable that will be used in a WH1LE-program. The diagrammatic form of the rules for AST leaves is depicted in in Fig. 7.3.
a is any atom, eg nil
=)
[quote,a]
.
CSt
.
a
.
DSt
.
[var,X ] val . .
CSt DSt =)
val val
. .
CSt DSt
. .
. . 1
CHAPTER 7. SELF-INTERPRETER
7.1. WH LE
val
.
val
.
DSt
.
.
CSt
.
7.1.2.1 Nullary Expressions
13
has been dealt with).
The evaluation of a variable (recall we have only one in language WH1LE returns
the [vqaulouteeo,af]this one variable anvdalthis is pushed onto the resulat stack. Thvealvariable expression is popped from the code stack.
Variable
. . . .
CSt DSt =) CSt DSt
7.1.2.2 C. ompound Ex. pressions . X is irrelevant in this case
.
Next, we need to handle single argument compound expressions hd and tl. The diagrammatic form of the rules for those is depicted in Fig. 7.4.
To evaluate
[var,X] a marker
.
aluated expr .
r consumed
CSt
Once.a mar e computati
e first need
val
followed by
ck as no val .
.
DSt
we know tha .
he evaluated
anASTexpressftheform[hd,E]w touateE.
SodoHdispushedohecommandstack,thltobe
ion o
val
nto t
eveshinghappenstaueisproduced
=) keundontopofktwecanfinish
no at thonression.Weattargumenthas
77
Fig. 7.3: STEP macro for evaluating quote and var
The evaluation of a quoted literal returns the literal as value which is therefore pushed on the data stack. The quote expression is popped from the code stack (as it has been dealt with).
The evaluation of a variable (recall we have only one in language WH1LE returns
eval
val
.
sion E.. Not
this stage.
DSt
rdoHdisfo .
of a hd exp
on the.data s
CSt
the code stac .
lso know tha
e stil
the value of this one variable and this is pushed onto the result stack. The variable
expression is popped from the code stack.
7.1.2.2 Compound Expressions
14
Next, we need to handle single argument compound expressions hd and tl. The

Compound Expressions (unary and binary)
15
7.1. WH1LE 7.1. WH1LE
CHAPTER 7. SELF-INTERPRETER CHAPTER 7. SELF-INTERPRETER
=) . =) . =). .
. .
=) =)
E E
doHd doHd .
.
. .
CSt
CSt
. .
. .
.
hd (similarlyfortl)
additional atoms used as mnemonic markers: what needs to be done when this marker is popped off the
stack . .
[hd,E] [hd,E] .
.
. .
CSt
. .
CSt
. .
.
. . .
. h . . .
i
.
. .
val val
val val
DSt
. .
DSt
. .
.
. .
DSt
DSt
. .
. .
.
doHd doHd
. . .
.
CSt
. .
CSt
. . .
hv1.v2 i v1 .v2
. . .
.
DSt
. .
DSt
. . .
v1 v1
. . .
.
DSt
DSt
. .
. . .
val val
. . .
. . .
val val
.
CSt
CSt
. .
. . .
doHd doHd
. .
. .
.
CSt
. .
CSt
. . .
nil nil
. .
. .
.
DSt
. .
DSt
. . .
nil nil
. .
. .
.
DSt
DSt
. .
. . .
val val
=) =)
val val
. .
E val E val
. .
val val
. .
.
CSt
CSt
. .
. . .
[tl,E ] 16 doTl [tl,E] doTl
. . =) . .
. . =) . .
. . =). . . . . .
. . . .
CSt DSt CSt
DSt
. . . .
CSt DSt CSt
DSt
. . . . . . . . .
. . . .

CHAPTER 7. SELF-INTERPRETER
7.1. WH1LE
17
called I, in which programs interpreters will be used exte
versal
an interpret n modify th
hile, var, n Definition
ues in ID, d
retation
.1 There e I-programs
Auxiliary atoms
We now add new (encoded) atoms to
denote 6 more val
doHd, doTl, doCons, doAsgn, doIf, doWhile
[[p]](d) for all p Proof. The overal
Use: push on stack to indicate operation still to be do-ne Proposition 4.1
4.1 A uni
We first develop variable, and the
Let {:=,;,w
of ID mentioned i
4.1.1 Interp
l structure where STEP is the sequence
been pushed on top of the data stack. So we pop this value v off the data stack,
is to prove correctness of the
compute hd v and push the result on the data stack. Since we have now dealt with the hd expression we pop the marker off the code stack.
For an AST of the form [tl,E] we do exactly the samre aesafordhdPjusDt r;eplacing
;
doHd by doTl and instead of the result of hd v we push the result of tl v on the
P :=hdPD
data stack.
Next, we discuss the binary operator cons. The rules are shown in diagrammatic
7f.1ormA iSnelFf-igin.te7r.p5r.eter for WHILE -Programs with One Variable cons EF
C :=hd(t
Cd := cons77
St := nil;
[cons,E,F ]
[cons,E,F ] doCons
while Cd do
CSt DSt CSt DSt
CSt DSt
.. .. .. ..
CSt DSt
val
val
E
F
Vl := tl PD
val
val
. . =. .
Vl;
.. .. =) . . . .
vvaall =)
doCons
writ
e
.
.
ddoCons u
Input is a progra through the first
ables: Cd, St, Vl. . . h u.v iu.v
. . . . . . . .
valval
..
CSt .
v .
= .
..
.. DSt .. DSt
. . CSt .
CSt
CSt
.. DSt . . DSt
. .. . . . ..
Fig. 7.5 STEP macro for evaluating cons
Fig. 7.5: STEP macro for evaluating cons
To evaluate an AST expression of the form [ cons, E , F ] we first need to evaluate compute hd v and push the result on the data stack. Since we have now dealt with
expressions E and F . So a marker doCons is pushed onto the code stack, followed the hd expression we pop the marker off the code stack.
by the still to be evaluated expression trees E and F. Note that the order in which For an AST of the form [ tl, E ] we do exactly the same as for hd just replacing
18
we push both arguments is arbitrary in principle, but it is important that it is fixed doHd by doTl and instead of the result of hd v we push the result of tl v on the
such that the rule for doCons knows in which order to take values from the data data stack.
stack to build the resulting tree correctly. Nothing happens on the value stack as no
Next, we discuss the binary operator cons. The rules are shown in diagrammatic value is produced nor consumed at this stage. Once a marker doCons is found on
form in Fig. 7.5.
top of the command stack, we know that we can finish the computation of a cons
l P) C nil;
; STEP;
m in the a and only v The first is
To evaluate an AST expression of the form [ cons, E , F ] we first need to evaluate
p
i
q
x o
b a

Commands
19
7.1. WH1LE
We have now dealt with the cons expression, hence we can pop the marker of tthe
code stack.
CHAPTER7. SELF-INTERPRETER
Assignment
7.1.2.3 Commands
Finally, we have to consider how to execute the various commands: assiignmentt,,
conditional, and while loops. First we look at the assignment operator.. The rulles fforr that are depicted diagrammatically in Fig. 7.6.
X is irrelevant in this case
E
doAsgn
. .
CSt
. . .
val
[:=,X,E ]
. .
CSt
. . .
. =) . .. . . . ..
=)
Fig. 7.6: STEP macro for evaluating assignment
.. ..
DSt
.. .. ..
val
.
.
. DSt
. . .
doAsgn
.
. .
CSt
. . .
v
.
. .
DSt
. . .
val
Fig. 7.6: STEP macro for evaluating assignment
To interpret an AST encoding an assignment of the form [ :=, X , E ] we first need To interpret an AST encoding an assignment of the form [ :=, X , E ] we first need
. .
v
CSt
. . .
.. ..
DSt
.. .. ..
to evaluate the expression E. So we push first a marker doAsgn on the code stack to evaluate the expression E. 2S0o we push first a marker doAsgn on the code stack
followed by the still to be evaluated E. Nothing happens on the value stack as no followed by the still to be evaluated E. Nothing happens on the value stack as no
value is produced nor consumed at this stage. Once a marker doAsgn is found on top value is produced nor consumed at this stage. Once a marker doAsgn is found on top
of the command stack, we know that we can finish the interpretation of an assign- of the command stack, we know that we can finish the interpretation of an assign-
ment command. We also know that the value to be assigned has been pushed onto ment command. We also know that the value to be assigned has been pushed onto
the data stack. So we pop this value v off the data stack and update the memory, the data stack. So we pop this value v off the data stack and update the memory,
in this case the value for the one variable of the program. Since we have now dealt in this case the value for the one variable of the program. Since we have now dealt

block B onto the command stack. We also pop the top element, the used value of E, block BTTonto the command stack. We also pop the top element, the used value of E,
.
from the data stack. In case the top element of the data stack is nil, representing false, from the data stack. In case the top element of the data stack is nil, representing false,
we analogously pop marker and conditional and push the commands of the else- we analogously pop marker and conditional and push the commands of the else-
block B instead. Again we pop the top element off the data stack. It is important to block B Einstead. Again we pop the top element off the data stack. It is important to
notice that one does not push the blocks B and B , respectively, in their entirety as notice that one does not push the blocks B T and B E, respectively, in their entirety as
E
a list but rather pushes all commands of the corresponding list in the correct order. a list but rather pushes all commands of the corresponding list in the correct order.
This means that we push the last command first and the first command last, such
CSt CSt
. ..
TE
E E
doIf doIf
[if,E,BT,BE] [if,E,BT,BE]
CSt CSt
if
This means that we push the last command first and the first command last, such
that the first command of the block will now be executed first. The rules for the that the first command of the block will now be executed first. The rules for the
conditional are depicted in Fig. 7.7 conditional are depicted in Fig. 7.7
=) . =)
[if,E,BT,BE] if,E,BT,BE]
CSt CSt
[
.. D.St
DSt
..
val val
..
BT =[C1,C2,,Cn]
BT BT
C1 C1
C2 C2
..
Cn Cn
CSt CSt
doIf nil doIf nil
Val Val
.
. =) .
.. =)C . [if,E,BT,BE] .. n .
[if,E,BT,BE] . Cn . DSt DSt
BT =[C1,C2,,Cn] .
. . .
DSt DSt .
doIf doIf
[if,E,BT ,BE [if,E,BT,BE]
CSt CSt
hu, vi hu, vi
.
..
DSt DSt
.. .
]
=) . .. =) .
BE BE
C1 C1
val C2 val C2
..
BE = [C1,C2,,Cn] Analogously, if top element of DSt is nil, B is pushed on CSt
. .
DSt DSt .
BE = [C1,C2,,Cn]
E
val val
. .
val val
. . .
val val
DSt DSt
CSt . CSt . .21 .
Fig. 7.7: STEP macro for evaluating if-then-else Fig. 7.7: STEP macro for evaluating if-then-else
81 81
7.1. WH1LE CHAPTER 7. SELF-INTERPRETER The final command, and the most complicate to execute, is the while loop
[while,E,B]. while
E
doWhile
[while,E,B]
CSt
. =) .
.
DSt
.
val
[while,E,B]
CSt
doWhile
[while,E,B]
.
CSt
.
nil
.
DSt
.
val val
=)
.
. DSt
CSt . .
.
DSt
.
val
22
B C1
B = [C1,C2,,Cn] C2

The final command, and the most complicate to execute, is the while loop
[while,E,B].
val E val
val E [while,E,B]
doWhile
. =) . . [while,E,B] .
To interpret an AST representing a while loop [while,E,B], we first need to
the code stack, followed by a marker doWhile, followed by the expression E still
evaluate the guard expression E. Since we might need to evaluate the body of this
to be evaluated. Nothing happens on the value stack as no value is produced nor
loop for a yet unknown number of times we first push the entire while command on
consumed at this stage. Once a marker doWhile is found on top of the code stack
the code stack, followed by a marker doWhile, followed by the expression E still
to co w w h
we know that we have finished the evaluation of the guard expression and can decide on
val
[w val
doWhile DSt
DSt
[while,E,B] CSt
.
.=).. . . CSt[while,E,B] . . CSt .
DSt
DSt
. doWhile CSt nil . val doWhi val
. hile,E,B] . .
. . le
doWhile
[while,E,B]
.
CSt
.
nil
.
DSt
.
. DSt =) CSt .
. DSt CSt .
=). . . B
. .
B = [C1,C2,,Cn]
C1
keep all of this for repeated looping
.
CSt
.
val
.
DSt
.
B
.
C1
C2
doWhile
[while,E,B] l
.
=)C S t [ w h i .
hu.vi
n
,E,B] .
DSt
.
doWhile hu.vi
[while,E,B] .
va
B = [C1,C2,,Cn] C2
.
C =)
. va .
le . . .
.
CSt
DSt
DSt

CSt
. . . .
. Fig. 7.8: STEP macro for evaluating while
val
Cn
[while,E,B] l
. .
CSt
.
.
DSt
.
val
Fig. 7.8: STEP macro for evaluating while
To interpret an AST23representing a while loop [while,E,B], we first need to
evaluate the guard expression E. Since we might need to evaluate the body of this loop for a yet unknown number of times we first push the entire while command on
be evaluated. Nothing happens on the value stack as no value is produced nor
what to do next accordingly. We also know that the value of the guard expressi
nsumed at this stage. Once a marker doWhile is found on top of the code stack
has been pushed onto the data stack. We consider two cases:
e know that we have finished the evaluation of the guard expression and can decide hat to do next accordingly. We also know that the value of the guard expression
as been pushed onto the data stack. We consider two cases: 82
82
Changes to interpret
WHILE
24

Variable lookup
CHAPTER 7. SELF-INTERPRETER 7.2. A SELF-INTERPRETER FOR WHILE X is now relevant
[var,X ] [X1,v1] v [X1,v1] . . . . . .
. . [X,v]=). . [X,v] CSt DSt . CSt DSt .
. . . . . .
[Xn,vn] [X1,v1]
[X2,v2] [:=X,E] . =)
[Xn,vn] E [X1,v1]
doAsgn [X2,v2] X .
CSt DSt [Xn,vn] 25
CHAPTER 7. SELF-INTERPRETER 7.2. A SELF-INTERPRETER FOR WHILE
doAsgn
1 [ 1 X 1 , v 1 ] [ X 1 , 1v 1 ] 1 . v . [X2,v2]. . . . .
CSt CSt
7.2.1.1 Lookup doAsggnn
DSt [Xn,vn] DSt [Xn,vn]
[X ,v[X] ,v ] 1111
CSt
CSt
DSt
DSt
[Xn,vn] [X ,v ]
CSt
.
. .
DSt [Xn,vn] CHAP[vTaErR,X7]. SELF-INTER[PXRE,TvE]R7.2. ASELF-INTERPRETERFOvRWHILE[X ,v ]
X
. . [X,v] . . [X,v]
[var,X] [X ,v ] v
[X ,v ]
. . 1.1 =). .1.1
[X,v] .
=)
C.St .DSt .. . . CSt . DSt
. . .. . .. .. . . .. .
. . .
. . [X,v] . [.X,v] DSt CSt DSt
. . =) . .
. . . . [Xn,.vn] Assignment
CSt
. CSt . DSt .[Xn,vn] CSt . DSt . .
[Xn,vn] [Xn,vn]
[Xn,vn]
. . .
[Xn,vn] [X ,v ]
E
[:=X,E] . X .
[X1,v1] [X2,v2]
X is now relevant [X1,v1]
Fig. 7.10: Adapted rules for STEPn macro
[X ,v ]
1 [ X1 2 , v 2 ]
E
1 1 [X2,v2]
[X2,v2] . =)
[:=X,E] . .=) X . .
7.2.1 Store Manipulation Macros
.
[Xn,vn] [X ,v ]
.
The program lookup from Fig. 7[X.1,1v ]takes as input a list [X,St] w.here X is a unary
. . Xv.
X v 2 [ X2 2 , v 2 ] .
number encoding a variable name and St is a list containing var[iXa,bv]le bindings, i.e.
.. =).
[X,v] two-element lists of the form [X ,v ] where eachX is a number encoding a. variable
.. .=)..
CSt DSt i i . CSt i DSt . .
C.St . DSt . CSt . DSt .
. . [Xn,vn] . . [Xn,vn]
name and v 2 D is the current value of this variable. There is one exceptional case:
i .. . . [Xn,vn]
if X does not appear as variable in the list St, i.e. if one looks up a variable that
d o A s g n doAsgn
. . . . [[Xn,vn] Fig. 7.10: Adapted rules for STEPn macro
has not been initialised, then the result Res will be nil (as in this case it will not Fig. 7.10: Adapted rules for STEPn macro
have been assigned anything). The consequence is that uninitialised variables are
implicitly looked up with value nil which is exactly what we need.
7.2.1 Store Manipulation Macros
26
7.2.1 Store Manipulation Macros
7T.2h.e1p.1rogLroamokluopokup from Fig. 7.11 takes as input a list [X,St] where X is a unary number encoding a variable name and St is a list containing variable bindings, i.e. two-element lists of the form [X ,v ] where eachX is a number encoding a variable
7.2.1.1 Lookup
11 11

7.2. A SELF-INTERPRETER FOR WHILE CHAPTER 7. SELF-INTERPRETER
read PD { P:=hd PD D:=hd tl X:=hd P; Y:=hd tl B:=hd tl CSt := B;
; PD;
tl P; P;
(* input is a list [P, D] *) (* P = [pname[,X,B,Y] *)
(* D input data *)
(* X is input var name *)
(* Y is output var name *)
(* B is program code block *)
(* CSt is code stack*)
(* initially contains only B *)
(* DSt is data stack for *)
(* intermediate results *)
this part is as before but we now keep X and Y
DSt := nil;
bind := [ X, D ];
St := [ bind ];
state := [ CSt, DSt, St ];(* wrap state for STEP macro *)
while CSt { (* main loop for interpretation *)
(* initialise store *)
state := state; (* loop body macro*)
CSt := hd state
};
St := hd tl tl state;
arg := [ Y, St ];
Out := arg
}
write Out
(* get command stack *)
(* get final store *)
(* wrap argument for lookup *)
(* lookup output variable value *)
(* return value of result variable *)
WHILE-interpreter
Cd is code stack (code in list format),
Vl contains value d of the one variable,
Fig. 7.9: A WHILE-interpreter in WHILE St is Stack of intermediate values
27
For an AST representing an assignment [:=,X,E] we again push the marker and the still to be evaluated expression E but we also need to remember which variable this assignment is for so we push the variable number X onto the command stack before we also push the marker. Once we then hit the doAsgn marker on the com- mand stack, we know the value of the assignment expression has been evaluated and resides on the top of the data stack.
We pop the marker doAsgn and the following variable number X off the com- mand stack, pop the result value v off the data stack, and update the element that corresponds to variable X in the list [[X1,v1],[X2,v2],,[Xn,vn]] to contain v in the binding for X . This will be done in code using the auxiliary macro update described in the following Section 7.2.1.
Coding the macros
The code for the lookup and update, respectively, is based on simple list manip- ulation checking for the right binding using the atom encoding the variable name. Their code is briefly discussed in the following subsection which can be skipped if one is not interested in coding the self-interpreter.
Finally, the concrete code for the STEP macro is left as Exercise 1.
The update and lookup macro are available
from Canvas as is the main interpreter loop.
The STEP macro we might do partially at least
in the exercises
84
28

END
2008-21. Bernhard Reus, University of Sussex
Next time: Our first non-computable problem
29