Computation
7 – A universal program (Self-interpreter)
• … we have learned the WHILE-language…
• …that we have chosen to represent our notion of computation (to write “effective procedures”).
Copyright By PowCoder代写 加微信 powcoder
• We learned how to represent programs-as- data…
…so now we can write interpreters.
Eating your own tail?
We look at a special form of interpreter:
self-interpreter
WHILE-interpreter in WHILE
and first an WH1LE-interpreter in WHILE
a very important concept for computability theory (used later)
http://www.strangedangers.com/content/item/158424.html
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
let’s use WHILE instead!
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!
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?
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.
Tree Traversal of ASTs
(with intermediate
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 t’s opcode has n arguments
then push t’s 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
read PD {
P := hd PD ;
D := hd tl PD;
B := hd tl P;
DSt := nil;
(* input is a list [P,D] *)
(* P = [X,B,X] *)
(* D input data *)
(* B is program block *)
(* CSt is code stack *)
(* initially commands of B *)
(* DSt is computation stack for *)
(* intermediate results *)
(* D is initial value of variable *)
state := [ CSt, DSt, val ];
(* wrap up state for STEP macro *)
while CSt { (* main loop for interpretation *)
state :=
CSt := hd state
val := hd tl tl state
(* get command stack *)
(* get final value of variable *)
(* return value of the one variable *)
CSt is the code stack (code in list format), DSt is the stack of intermediate values, val contains value D of the one variable
WH1LELF-IN ofreadetofre
describ value st stack,fjust
geaccocharul . . . .
7.1. WH1LE CHAPTER 7. SELF-INTERPRETER CHAPTER 7. SE
1 Step Macro
sakeofreadability, letuspresentthebehaviourofSTEPasasetofrewriterulesof
the form 1
ability, letuspresentthebehaviourofSTEPasas
[CSt,DSt,val] ) [CSt ,DSt ,val ] new new new
performs tree traversal based on CSt, DSt, and val. 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, change according to their current values. Diagrammatically, such a rule is depicted
[CSt,DSt,val] ) [CSt ehowthedatastructuresofthetraversalS,the
,DSt anthe”forenonsistso
,val ] new new
=) rdihentvalueracally,su
. ng t.o t
. ircu.rre
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
. D that c
value to val
more clearly how the stacks (and the value of the variable) change according to
their top elements.
. Below we will give those rules in diagrammatic form, showing
WH1LE-interpreter
A set of those rules then describes, in a way, a big case-statement that te what happens depending on what values can be found on top of the code stac valu
N the code totheoneva 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 ];
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
he STEP macro needs to behave as prescribed by the following r
diagrammatic form:
o following the pedagogical route taken by [1] 76
AST Leaves (expressions without arguments)
We consider the leaves for ASTs, i.e.13atoms of the form [quote,a] and variables of the form [var, X ] where the number encoding the variable name does not mat-
Fig. 7.3: STEP macro for evaluating quote an1d var
ter as it is always the same variable that will be used in a WH LE-program. The
diagrammatic form of the rules for AST leaves is depicted in in Fig. 7.3.
CHAPTER 7. SELF-INTERPRETER 7.1. WH LE
7.1.2.1 Nullary Expressions
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] val
=) [var,X ] val
. 1 7.1. WH LE
CHAPTER 7. SELF-INTERPRETER =)
CSt DSt CSt DSt
7.1.2.1 Nullary Expressions
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
[quote,a] val a val has been dealt with).
Thee.valuationofav.ariable(recallwehaveon.lyoneinlang.uageWH1LEreturns . . . .
agrammatic .
rm of the rul .
the value of this one variable and this is pushed onto the result stack. The variable
expressCiSotn is poppedDfrSotm the code stack. CSt DSt
[var,X ] val val val
Next, we need to handle single argument compound expressions hd and tl. The
difoesforthoseisFi
X is irrelevant in this case
7.1.2.2 Compound Expressions
To evaluate a marker
. aluated expr
r consumed
aessionofthefwtoevaluateE. =)
n AST expr Hd is pushe
Sododontothecok,thestilltobe eveshinghappenstaueisproduced no at
sion E. Not
. this stage.
Once a marker doHd is found on top of the code stack we know that we can finish the computation of a hd expression. We also know that the evaluated argument has
Fig. 7.3: STEP macro for evaluating quote and var 77
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
depicted in .
orm [hd,E]
mmand stac
on the.data s
e first.need followed by
ck as no val
the value of this one variable and this is pushed onto the result stack. The variable
expression is popped from the code stack.
Compound Expressions (unary and binary)
hd (similarlyfortl)
additional atoms used as mnemonic markers: what needs to be done when this marker is popped off the stack
[hd,E] doHd
7.1. WH1LE 7.1. WH1LE
CHAPTER 7. SELF-INTERPRETER CHAPTER 7. SELF-INTERPRETER
. . =) . .
. . =) . . . . =). .
doHd hv1.v2 i val 12
v1 val . .
val E val val E val
doHd hv .v i val . 1 . 2
doHd nil val
doHd nil val ….
[tl,E ] 16 doTl doTl
[tl,E] doTl
. . =) . .
. . =) . . . . =). . . . . . . . . .
CSt DSt CSt DSt
Auxiliary atoms
We now add new (encoded) atoms to
denote 6 more values in ID
doHd, doTl, doCons, doAsgn, doIf, doWhile
[[p]](d) for all p I-progra
CHAPTER 7. SELF-INTERPRETER 7.1. WH1LE
Proof. The overall structu
Use: push on stack to indicate operation still to be do-ne
Proposition 4.1.1 Ther
[cons,E,F ] [cons,E,F ]
. . =⇒. . .. .. =).. .. …. ….
CSt DSt CSt DSt CSt DSt CSt DSt
…. …. .. .. .. .
. …. ….
interpreters will be used e
4.1 A universa
We first develop an interp variable, and then modify
been pushed on top of the data stack. So we pop this value v off the data stack,
compute hd v and push the result on the data stackw. SihncewrehaSveTnoEwPdealitswithhe sequen the hd expression we pop the marker off the code stack.
For an AST of the form [tl,E ] we do exactly thiessamteoaspfor hodvjuest rcepolarcinrgectness of doHd by doTl and instead of the result of hd v we push the result of tl v on the
ddoCons u vvaall Inputisapvarlovaglraminth .. ..
. h u . v⟨ iu . v ⟩
Let { :=, ;, while, va
of ID mentioned in Definit
4.1.1 Interpretatio
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
P := hd PD;
C :=hd(tlP)
Cd := cons C nil;
St := nil; Vl := tl PD;
while Cd do STEP;
through the first and only
St, Vl. The firs To evaluate an AST expression of the form [ cons, E , F ] we first need to evaluate
. .. .. . .. .
.. Fig. 7.5 STEP macro for evaluating cons
Fig. 7.5: STEP macro for evaluating cons
compute hd v and push the result on the data stack. Since we have now dealt with
expressions E and F . So a mar1k8er 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
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.
7.1. WH LE CHAPTER 7. SELF-INTERPRETER 7.1. WH LE 19 CHAPTER 7. SELF-INTERPRETER
We have now dealt with the cons expression, hence we can pop the marker of tthe code stack.
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
[:=,X,E ] .
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
Fig. 7.6: STEP macro for evaluating assignment
Fig. 7.6: STEP macro for evaluating assignment
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
to evaluate the expression E. So we push first a marker doAsgn on the code stack to evaluate the expression E. So we push first a marker doAsgn on the code stack
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-
we analogously pop marker and conditional and push the commands of the else-
B = [C1,C2,…,Cn]
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
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 .
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] [if,E,BT,BE] [if,E,BT,BE]
doIf =) doIf
CSt . CSt .
BT =[C1,C2,…,Cn] BT =[C1,C2,…,Cn]
Val val Val val
. =) . .. =) .
[if,E,BT,BE] [if,E,BT,BE]
hu, vi hu, vi
Analogously, if top element of DSt is nil, B i E
.. . =)C .
[if,E,BT,BE] .. n
[if,E,BT,BE] . Cn . DSt DSt
pushed on CSt C2 val
BE = [C1,C2,…,Cn] BE =[C ,C ,…,Cn]
DSt DSt CSt . 21 CSt .
. . Fig. 7.7: STEP macro for evaluating if-then-else
Fig. 7.7: STEP macro for evaluating if-then-else
81 7.1. WH1LE 81
CHAPTER 7. SELF-INTERPRETER
The final command, and the most complicate to execute, is the while loop [while,E,B].
[while,E,B]
[while,E,B]
[while,E,B]
val E [while,E,B]
val E val val doWhile
. =) . . [while,E,B] .
doWhile DSt
[while,E,B] CSt
[while,E,B] .
.=).. . . CSt[while,E,B] . . CSt .
. doWhile CSt . val doWhi val
[while,E,B] .
B = [C1,C2,…,Cn]
. DSt CSt .
h u.v i val
=) [while,E,B]
keep all of this for repeated looping
B = [C1,C2,…,Cn] C2
doWhile . [while,E,B] C
doWhile [while,E,B]
hu.vi val .
. Fig. 7.8: STEP macro for evaluating while
=)C S t [ w h i .
Fig. 7.8: STEP macro for evaluating while
To interpret an AST representing 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
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 lo
or ck de on
to be evaluated. Nothing happens on the value stack as no value is produced n op 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 sta e code stack, followed by a marker doWhile, followed by the expression E still
we know that we have finished the evaluation of the guard expression and can deci 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 onsumed 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
Changes to interpret
Now we need a store
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] store =
[Xn,vn] [X ,v ]
a list of key-
[X ,v ] valu1e p1airs
1 1 [X2,v2]
CHAPTER 7. SELF-INTERPRETER 7.2. A SELF-INTERPRETER FOR WHILE
CSt DSt [Xn,vn]
CSt DSt [Xn,vn]
CHAP[vTaErR,X7]. SELF-INTERPRETER7.2. A SELF-INTERPRETER FOvR WHILE
[X1,v1] [X1,v1] . . . . . .
doAsgn . . .
[var,X] [X ,v ]
[1X,v1] [X,v] 11
Assignment
1.1 =) 1.1 .
C.St .DSt . . . CSt . DSt. . X .. v .. [X2,.v2]. . . . .. . .
[X,v] [X,v] …. =).. ..
CSt DSt . [X ,v ] CSt DSt . [ X [ , Xv , ] v ]
. . .. ..nn .. . .. nn
[Xn,vn] [X1,v1]
[X ,v ] CSt DSt n n
d o A s g n
[X ,v ] DStn n
[X ,v ] 1 1
. . X is n.ow relevant .
[Xn,vn] [X1,v1]
1 [ X1 2 , v 2 ]
[X2,v2] . doAsgn [X2,v2] Fig. 7.10: Adapte.d ru=le)s for STEPn macro
[:=X,E] . X .
. [:=X,E] . .=) X . .
CSt DSt [Xn,vn] CSt CSt DSt [Xn,vn] CSt
7.2.1 Store Manipulation Macros
DSt [Xn,vn] DSt [Xn,vn]
[X,v[X],v] [X,v] [X,v] 1111 11 11
7.2.1.1 Lookup [X ,v ] . . X v 2 [ X2 2 , v 2 ] .
.. …=)….[X,v]
TheprogramlookupfromFig.7.11takesasinputalist[X,St]w.hereXisaunary CSt DSt . CSt DSt . .
.. ….=)…..
C.St . DSt .
CSt . DSt .
number encodin.g a variab.le nam[eXn
l]e bindings, i.e.
n]dStis a l.ist contain.ing var[Xi
Fig. 7.10: Adapted rules for STEPn macro
name and v 2 D is the current value of this variable. There is one exceptional case:
Fig. 7.10: Adapted rules for STEPn macro
if X does not appear as variable in the list St, i.e. if one looks up a variable that
. . . . [[Xn,vn] two-element lists of the form [X ,v ] where eachX is a number encoding a variable
.. . . [Xn,vn]
. .ii i. .
has not been initialised, then the result Res will be nil (as in this case it will not
7.2.1 Store Manipulation Macros
have been assigned anything). The consequence is that uninitialised variables are
7.2.1 Store Manipulation Macros
implicitly7.l2o.1o.1keLdooukpupwith value nil which is exactly what we need.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com