CS代写 Computation - PowCoder代写

Computation
6 – Programs as Data Objects
• “effective procedure” = WHILE-program
• introduced WHILE-language with binary tree data type …

• … that can also be viewed as a type of (arbitrary deeply) nested lists
• and extended WHILE for convenience

WHILE-programs as lists • We show how WHILE-programs can be data
HILE-program in concrete and abstract syntax “as data”
GRAMS AS DATA OBJECTS 6.3. ENCODE ASTS
objects usable in another WHILE-program
[[:=,1,[quote,nil]],
[while,[var,0],
[ [:=,1,[cons,[hd,[var,0]],[var,1]]],
[:=,0,[tl,[var,0]]]
A WHILE- program abstract syntax tree encoded as list
read X { ;
ons hd X lX
g. 6.3: A W ext?
seen how tax trees. S
nterpreter i t chapter.
ing that w ation of the
one can encode WHILE-programs as data in the form of ab-
n WHILE, a so-called self-interpreter. We will do this in detail Programs as Input or Output
ince we can also encode pairing, we are in a position to write a
• Compiler
program transformer which takes a program and translates it into an
• equivalent program, most likely in another language; Interpreter
e start counting variables from 0, give the program-as-data rep-
takes a program and its input data, and returns the result of applying WHILE-prothgerapmrogriavmentointhFaitgi.np6u.4t.
Program Specialiser
takes a program with two inputs and one data for one of the inputs and
partially evaluates the program with the one given data producing a new program with one input only (more on that later).
Fig. 6.4: Sample program for Exercise 1

6.1 Interpreters Formally
To be able to be more precise (and formal) about programs that take other programs
(in various languages) as input, we need to say what the semantics of a programming
language is in general. We already said what the semantics of WHILE (programs) Programming Languages
is. This can be generalised now:
Definition 6.1. A programming language L consists of
our notion, formally
1. two sets: L-programs (the set of L-programs) and L-data (the set of data values 6.1. INTERPRETERS FORMACLLHYAPTER 6. PROGRAMS AS DATA OBJECTS
described by the datatype used by this language)1.
2. A function J KL : L-programs ! (L-data ! L-data? ) which maps L-programs into
we explain how one can encode ASTs of WHILE-programs in the WHILE-datatype their semantic behaviour, namely a partial function mapping inputs to outputs,
of binary trees (Sect. 6.3). which are both in L-data.
Definition 6.2. A programming language L defined as above has pairing if its data
type L-data permits the encoding of pairs. For a general (unknown) language that 6.1 Interpreters Formally
has pairing we denote pairs (a, b), i.e. using parenthesis and a comma.
FTrombeSaebclet.t3o.3b.e2mwoererepcraelclitsheat(aWnHdIfLorEmhaal)sapbaoiruitnpgr.ogramsthattakeotherprograms
(inWvaercioaunsnloanwgdueafigense)eaxsaicntplyutw,whaetnaenedinttoersparyetwehraitnthtefsoermaalnatnigcsuaogfeaSprwogrirtatmenmininLg
ilsa:nguage is in general. We already said what the semantics of WHILE (programs)
is. This can be generalised now:
Definition 6.3. An interpreter int for a language S written in L must fulfil for any
given S-program p and d 2 S-data :
Definition 6.1. A programming language L consists of
JintKL(p,d) = JpKS(d) (6.1) 1. two sets: L-programs (the set of L-programs) and L-data (the set of data values
described by the datatype used by this language)1.
2.AfunctionJK :L-programs!(L-data!L-data?)whichmapsL-programsinto
L PL with Pairing 6.2 Abstract Syntax Trees
their semantic behaviour, namely a partial function mapping inputs to outputs,
which are both in L-data.
In order to be able to write compilers, interpreters, and specialisers in WHILE, we
Definition 6.2. A programming language L defined as above has pairing if its data need a representation of WHILE-programs as data objects (“programs as data”).
type, L-data, permits the encoding of pairs. For a general (unknown) language that Since the WHILE-datatype of binary trees is not ideal for representing strings, it
has pairing we denote pairs (a, b), i.e. using parenthesis and a comma.
makes sense to represent programs directly as abstract syntax trees (a concept
known from compilation). Such trees are usually obtained by the so-called lexical From Sect. 3.3.2 we recall that WHILE has pairing.
analysis phase that takes the string of ASCII symbols and represent the structure of Definition 6.3. A programming language L defined as above has programs as data
1 Again, weDmoakeesoWmeHsIimLplEifyihngaavsseumptaioinrsinhegre?in the sense that we only have one datatype. if its data type, L-data, permits the encoding of L-programs. For a general (un-
We talk about untyped languages so it makes sense to have just one type.
known) language that has programs as data the encoding of a program p is denoted
The rest of the chapter will be devoted to proving that WHILE has programs-
as-data. With this concept one can define exactly what an interpreter int for a language S written in L is:
Definition 6.4. Assume S has programs as data, S-data ✓ L-data and L has pairing. An interpreter int for a language S written in L must fulfil the following equation for any given S-program p and d 2 S-data:

described by the datatype used by this language) .
2. A function J KL : L-programs ! (L-data ! L-data? ) which maps L-programs into
their semantic behaviour, namely a partial function mapping inputs to outputs,
which are both in L-data.
Definition 6.2. A programming language L defined as above has pairing if its data
type, L-data, permits the encoding of pairs. For a general (unknown) language that
has pairing we denote pairs (a, b), i.e. using parenthesis and a comma. PL with Programs As Data
From Sect. 3.3.2 we recall that WHILE has pairing.
Definition 6.3. A programming language L defined as above has programs as data if its data type, L-data, permits the encoding of L-programs. For a general (un- known) language that has programs as data the encoding of a program p is denoted p pq.
The rest of the chapter will be devoted to proving that WHILE has programs- as-data. With this concept one can define exactly what an interpreter int for a
The purpose of this session is  
language S written in L is:
to show that WHILE has programs as data.
Definition 6.4. Assume S has programs as data, S-data ✓ L-data and L has pairing. An interpreter int for a language S written in L must fulfil the following equation for any given S-program p and d 2 S-data:
intL(ppq,d)= pS(d) (6.1)
1 Again, we make some simplifying assumptions here in the sense that we only have one datatype. We talk about untyped languages so it makes sense to have just one type.
Programs as Data
• If language L has “programs as data” we can write compilers, interpreters, and specialisers in L.
• We want WHILE to have “programs as data”.
• Thus we need a representation of WHILE
programs as binary tree
• It is natural to use abstract syntax trees

From Sect. 3.3.2 we recall that WHILE has pairing.
Definition 6.3. A programming language L defined as above has programs as data if its data type, L-data, permits the encoding of L-programs. For a general (un- known) language that has programs as data the encoding of a program p is denoted p pq.
Interpreter
The rest of the chapter will be devoted to proving that WHILE has programs- as-data. With this concept one can define exactly what an interpreter int for a language S written in L is:
Definition 6.4. Assume S has programs as data, S-data ✓ L-data and L has pairing. An interpreter int for a language S written in L must fulfil the following equation for any given S-program p and d 2 S-data:
JintKL(ppq,d) = JpKS(d) (6.1) 1 Again, we make some simplifying assumptions here in the sense that we only have one datatype.
We talk about untyped languages so it makes sense to have just one type.
our notion, formally
Abstract Syntax Trees as lists
arg1 arg2 … argn
translates to [op,arg1,arg2,…,argn] op

AST as list Y:= hd Y (Y is 1st variable)
Simplification: we do only need to store the variable name (i.e. number), as we can only assign to variables
translates to
needs to be unfolded as list too, see next slide
AST as list Y:= hd Y
translates to
(Yisvar 1) [:=,1,[hd,[var,1]]]
[:=,var1,[hd,var1]]
nil nil nil

What to do with var etc?
[:=,1,[hd,[var,1]]]
These are not yet trees/lists:
Answer: either introduce them as additional atoms or encode them (uniquely) as numbers.
Programs as data in WHILE
• We are now in a position to define more exactly how the list encoding of abstract syntax trees work.
• Lists are themselves encoded as binary trees.
• Let’s go:

as encodings of natural numbers i due to Def. 3.5). program name is not included in the AST because names are only needed for
The program name is not included in the AST because na macro calls in the extendedmlacnrgoucaaglels, binutthweeedxetefindeedthleanegnucoagdein,gbuotnwlyefodrefi“npeurteh”e e
WHILE-programs. WHILE-programs.
2 One can use unary or binary representation of numbers actually, an One can use unary or binary representation of numbers actually, and in the following we may use
pwhile E Bq pwh=ile E[ wBhqile, pEq, pBq ] =
pX:=Eq pX:=Eq[:=,varnumX,pEq] =
pif E B else B q pif=E B [eilfs,epEBq,qpB q, pB q ] = TE TETE
[ while, pEq [:=,varnum [ if, pEq, pB [if,pEq,pB
p{C ;C ;…;C }q
pcons E Fq phd Eq
pif=EBq[if,pEq,pBq,[]] =
p{C=;C ;[.p.C.;Cq,p}Cq q,…,pC q] = [pC q,pC q
TER6.PROGRAMSASDonAeToArthOeBotJhEeCr,TacScordingtothe6t.a3sk.aEtNhaCndO.DEASTS one or the other, according to the task at hand.
e read X { il;
cons hd X Y;
[[:=,1,[quote,nil]],
[while,[var,0],
Fig. 6.3: A WHILE-program in concrete and abstract syntax “as data”
[ [:=,1,[cons,[hd,[var,0]],[var,1]]],
[:=,0,[tl,[var,0]]]
reverse read X { [0, Example
X is var 0 
Y:= nil; [[:=,1,[quote,nil]],
while X { [while,[var,0], 68
on of the corresponding AST on the right. Indentation is used to highlight the
le 6.1. In Figure 6.3 the WHILE-program p on the l Y is var1
pprognamereadX{S}writepYpqr=ognamvearenuamdX,p{Sq},wvrarintuemYq = varnum ,p XYX
12n121n2n12
ptl Eq = [tl,pEq]
CHAPTER 6. PROGRAMS AS DATA OBJECTS
pni=lq [ quote, nil ]
pXq= [var,varnumX]
pcons E Fq
= [ cons, pEq, pFq ]
= [hd,pEq]
= [ quote, nil = [ var, varnu = [ cons, pEq, = [hd,pEq]
= [tl,pEq] 6.3. ENCODE
WHILE programs in D
expressions commands
Fig. 6.2: Encoding of WHILE-programs Fig. 6.2: Encoding of WHILE-programs as data
Example 6.1. In Figure 6.3 the WHILE-program p on the left and ppq as list 15
sentation of the corresponding AST on the right. Indentation is used to highli structure of the AST in list representation on the right hand side.
Y:= cons hd X Y; [ [:=,1,[cons,[hd,[var,0]],[var,1 X:= tl X [:=,0,[tl,[var,0]]]
re of the AST in list representation on the right hand side.
}] } ]], write Y 1]
translate program into data
The “tags” for commands and expression operators, like := and var, are th
atoms introduced earlier. They could also be (in a more tedious fashion) e via natural numbers to avoid extra atoms.
Fig. 6.3: A WHILE-program in concrete and abstract syntax “as data”

Programs-as-data in hwhile
• We can now write compilers, interpreters, specializers in WHILE using abstract syntax trees in list notation (“programs-as-data”) instead of string representation.
• Thus we do not have to care about parsing programs.
• In hwhile (see Canvas) we can use the -u flag to produce this list representation:
hwhile -u reverse.while
[ 1, nil]]
[ @while, 0]
[ 1, 0]], 1]]]
, 0, 0]]]
hWhile uses @ to indicate special atoms

A note on hwhile output
hWhile output by default is given as binary tree:
use flags to determine the “type” in which it is presented
list of trees list of integers
./hwhile add [3,4]
>>>>>>
./hwhile -i add [3,4]
./hwhile -l add [3,4]
[nil,nil,nil,nil,nil,nil,nil]
./hwhile -li add [3,4]
[0, 0, 0, 0, 0, 0, 0]
A note on hwhile output
There are more output formats, to see them all run: Look at this one, can you explain it?
./hwhile -h
/hwhile -La add [3,4]

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts