The National Student Survey (NSS) 2021
Have your say
1
Have your say
What is the NSS?
A national survey of all final-year undergraduate students. Its designed to find out about your experience of studying at Sussex
When does the survey run?
The NSS opened on 6 January and closes on 30 April 2021
Why should I take part?
Its one important way to share feedback about your course. Your answers can help prospective students decide what and where to study
Complete the NSS:
thestudentsurvey.com
750 prize draw
Enter by 28 February
Cut off to claim voucher 31st May 2021
Find out more:
sussex.ac.uk/nss
Eligible UG Engineering and Informatics students can also claim a 10 Amazon UK voucher by forwarding their Thank you for completing the survey e-mail to: [email protected]
2
Using your feedback
In last years NSS students in the School of Engineering and Informatics told us
You said
You said you were struggling to access the lab machines you need to run specialist software
You wanted a clearer focus on careers
You wanted more advice on finding and making the most of placements
We listened
We introduced Citrix Workspace so you can access lab computers from home
We increased careers & employment advice within modules, and introduced new study skills training from library
We employed four Student Placement Connectors to provide advice and support on placements
3
Limits of
Computation
6 Programs as Data Objects Bernhard Reus
4
So far
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
5
WHILE-programs as lists We show how WHILE-programs can be data
Y;
HILE-program in concrete and abstract syntax as data
GRAMS AS DATA OBJECTS 6.3. ENCODE ASTS
objects usable in another WHILE-program
[0,
[[:=,1,[quote,nil]],
[while,[var,0],
[ [:=,1,[cons,[hd,[var,0]],[var,1]]],
[:=,0,[tl,[var,0]]]
]
]], 1]
A WHILE- program abstract syntax tree encoded as list
APTER 6. PRO
rse read X {
nil;
le X {
:= cons hd X
:= tl X
eY
Fig. 6.3: A W hat next?
6
THIS TIME
H
e = i Y X }
t
Programs as Input or Output
Compiler
program transformer which takes a program and translates it into an equivalent program, most likely in another language;
Interpreter
takes a program and its input data, and returns the result of applying the program to that input.
6.2. ASTS CHAPTER 6. PROGRAMS AS DATA OBJECTS
we explain how one can encode ASTs of WHILE-programs in the WHILE-datatype
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).
of binary trees (Sect. 6.3).
6.1 Interpreters Formally
7
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 1
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.
From Sect. 3.3.2 we recall that WHILE has pairing.
We can now define exactly what an interpreter int for a language S written in L is:
8
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 :
JintKL(p,d) = JpKS(d) (6.1)
language is in general. We already said what the semantics of WHILE (programs) is. This can be generalised now:
Definition 6.1. A programming language L consists of
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
their semantic behaviour, namely a partial function mapping inputs to outputs, which are both in L-data.
6.1. INTERPRETERS FORMACLLHYAPTER 6. PROGRAMS AS DATA OBJECTS
Definition 6.2. A programming language L defined as above has pairing if its data we explain how one can encode ASTs of WHILE-programs in the WHILE-datatype type, L-data, permits the encoding of pairs. For a general (unknown) language that of binary trees (Sect. 6.3).
has pairing we denote pairs (a, b), i.e. using parenthesis and a comma. From Sect. 3.3.2 we recall that WHILE has pairing.
6.1 Interpreters Formally
Definition 6.3. A programming language L defined as above has programs as data
Does WHILE have pairing?
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 To be able to be more precise (and formal) about programs that take other programs
p pq.
(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) The rest of the chapter will be devoted to proving that WHILE has programs-
is. This can be generalised now:
as-data. With this concept one can define exactly what an interpreter int for a
language S written in L is:
Definition 6.1. A programming language L consists of
Definition 6.4. Assume S has programs as data, S-data L-data and L has pairing.
9
An interpreter int for a language S written in L must fulfil the following equation 1. two sets: L-programs (the set of L-programs) and L-data (the set of data values
for any given S-program p and d 2 S-data: 1 described by the datatype used by this language) .
2.AfunctionJKL:L-programs!(L-data!L-data )whichmapsL-programsinto LS?
JintK (ppq,d) = JpK (d) (6.1) 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
PL with Programs As Data
h1aspairingwedenotepairs(a,b),i.e.usingparenthesisandacomma.
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. From Sect. 3.3.2 we recall that WHILE has pairing.
Definition 6.3. A programming languag6e6L 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:
JintKL(ppq,d) = JpKS(d) (6.1) 10
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.
6.1. INTERPRETERS FORMACLLHYAPTER 6. PROGRAMS AS DATA OBJECTS
we explain how one can encode ASTs of WHILE-programs in the WHILE-datatype of binary trees (Sect. 6.3).
6.1 Interpreters Formally
programs as binary tree
Programs as Data
If language L has programs as data we
To be able to be more precise (and formal) about programs that take other programs
can write compilers, interpreters, and
(in various languages) as input, we need to say what the semantics of a programming language is sinpgeecniearlails. eWresailnreaLdy. said what the semantics of WHILE (programs) is. This can be generalised now:
We want WHILE to have programs as data. Definition6T.1h.AusprwogeranmemeindglanrgeuapgreeLseconntsaistsionf ofWHILE
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.
It isLnatural to use abstract syntax trees 2.AfunctionJK :L-programs!(L-data!L-data )whichmapsL-programsinto
?
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 11
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.
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.
66
our notion, formally
12
Abstract Syntax Trees as lists
op arg1 arg2
translates to [op,arg1,arg2,,argn]
argn
op
arg1
arg2
argn
spine
13
AST as list Y:= hd Y (Y is 1st variable)
var 1
hd var 1
:=
translates to
var 1
needs to be unfolded as list too, see next slide
var nil nil 1
14
[:=,var1,[hd,var1]]
:=
var 1
hd
nil
AST as list Y:= hd Y (Yisvar 1)
:=
var 1
hd
translates to
[:=,1,[hd,[var,1]]]
Simplification: we do only need to store the variable name (i.e. number), as we can only assign to variables
nil
15
What to do with var etc?
[:=,1,[hd,[var,1]]]
var 1 nil
hd
var nil
These are not yet trees/lists:
hd
var
:=
Answer: either introduce them as additional atoms or encode them (uniquely) as numbers.
16
:=
nil
nil
nil nil nil
nil
one or the other, according to the task at hand.
using extensions can be translated (compiled) into one writte o
f
e W
r
X
n
n n n
m s
d
a
q
B
p
a h
this does not pose any restrictions on us.
this does not pose any restrictions on us.
First we need to encode labels in order to represent the type of operation in ASTs. First we need to encode labels in order to represent the type
We use special additional atoms.
We use special additional atoms.
6.5 (Extra atoms). We add several special atoms D that so far o Definition 6.5 (Extra atoms). We add several sp
nil. These extra atoms are var, cons, :=, while, if, tl, hd, quo one atom: nil. These extra atoms are var, cons,
Programs as data in WHILE sion can be done according to our discussion in Sec 5.3.
This extension can be done according to our disc
is one more issue we need to sort out yet for the representation There is one more issue we need to sort out
data objects, namely the encoding of variables. We cannot u grams as data objects, namely the encoding
We are now in a position to define more
er of atoms as there are an infinite number of possible variab
nite number of atoms as there are an infinite
exactly how the list encoding of abstract
ers to encode variable names. This encoding is produced by t use numbers to encode variable names. This e
syntax trees work.
VariableName ! N for which it holds that varnum = varnum
varnum : VariableName ! N for wXhich it holdYs . In other words, varnum uniquely encode variable names. The c
that X = Y. In other words, varnum uniquely en Lists are themselves encoded as binary trees.
are actually not important, it is only important that the same var
numbers are actually not important, it is only i 2
y the sameLneutmsbgeor.: 2
encoded by the same number.
presentation ppq of a WHILE-program p as data can now be de
The representation ppq of a WHILE-program q: WHILE-programs ! WHILE-data as outlined in Figure 6.2.
the map p q: WHILE-programs ! WHILE-data side of each equational definition we define lists and not trees
right hand side of each equational definition we
readable. To obtain proper elements in D one just needs to apply e are more readable. To obtain proper elements in
Definitionnlyused
ecial atoms D
oneatom:te.
:=, while, i
This exten
ussion in Sec
There of pro-
yet for the r
gramsasseafi-
of variables.
nitenumbles.We number of po
usenumbhemap ncoding is p
varnum : implies
that varnum
thatX=Yoncrete code variable
numbersiableis
mportant that Therefinedby
encoded b
p as data ca the map p On the
right hand as those define lists a
aremorencoding
D one just nee
operator p q. It has been discussed already
operator p q. It has been discussed already in Sect. 3.4 how th
in Sect. 3.4 how this is defined (as well as encodings of natural numbers i due to Def. 3.5). Some comments are in order.
17
as encodings of natural numbers i due to Def. 3.5). Some co The program name is not iTnchleudperodgirnamthenaAmSeTisbencoatuisneclnuadmedesinarteheonAlySTnebeedceadufsoername
macro calls in the extendedmlacnrgoucaaglels, binutthweeedxetefindeedthleanegnucoagdein,gbuotnwlyefodrefinpeurtehe enco WHILE-p
as outlined i
rograms. WHILE-programs. pprognamereadX{S}writepYpqr=ognamvearenuamdX,p{Sq},wvrarintuemYq =
XY pwhile E Bq pwh=ile E[ wBhqile, pEq, pBq ]
= [ = [ = [ = [
= [
pX:=Eq pX := Eq [ :=, varnumX, pEq ] pifEB elseB q pif=EB [eilfs,epEBq,qpB q,pB q]
TE TETE pifEBq pif=EBq[if,pEq,pBq,[]]
p{C ;C ;;C }q
12n 121n2n
pnilq
pXq
pcons E Fq phd Eq
pXq= [var,varnumX] pcons E Fq
= [ = [ = [ = [ = [
ptl Eq
Fig. 6.2: Encoding of WHILE-programs as data
p{C=;C ;[.p.C.;Cq,p}Cq q,,pC q] pni=lq [ quote, nil ]
= [ cons, pEq, pFq ] phd Eq
= [hd,pEq] ptl Eq
= [tl,pEq]
Fig. 6.2: Encoding of WHILE-
2
2 One can use unary or binary representation of numbers actually, and in t One can use unary or binary representation of numbers actually, and in the following we may use
18
one or the other, according to the task at hand.
varnumX, pSq, v
while, pEq, pBq :=, varnumX, pE if, pEq, pBTq, p if,pEq,pBq,[]]
pC1q,pC2q,,
quote, nil ] var, varnumX ] cons, pEq, pFq ] hd, pEq ]
tl, pEq ] programs as d
expressions commands
WHILE programs in D
Example 6.1. In Figure 6.3 the WHILE-program p on the left and ppq as list repr sentation of the corresponding AST on the right. Indentation is used to highlight t structure of the AST in list representation on the right hand side.
HAPTER 6. PROGRAMS AS DATA OBJECTS 6.3. ENCODE ASTS
reverse read X { [0,
verse read X {
:= nil;
hile X {
[0,
[[:=,1,[quote,nil]],
[while,[var,0],
Fig. 6.3: A WHILE-program in concrete and abstract syntax as data
X is var 0
Y:= nil; [[:=,1,[quote,nil]],
pq
ntation of the corresponding AST on the right. Indentation is used to highlight the
xample 6.1. In Figure 6.3 the WHILE-program p on the l
Y is var1
while X { [while,[var,0],
st repre-
dp Example
eft
an
as
li
Y:= cons hd X Y; [ [:=,1,[cons,[hd,[var,0]],[var,1]]]
ucture of the AST in list representation on the right hand side.
X:= tl X [:=,0,[tl,[var,0]]]
}] } ]], write Y 1]
Y:= cons hd X Y;
X:= tl X }]
translate program into data
[ [:=,1,[cons,[hd,[var,0]],[var,1]]],
[:=,0,[tl,[var,0]]]
]],
The tags for commands and expression operators, like := and var, are the ext
Fig. 6.3: A WHILE-program in concrete and abstract syntax as data What next?
ite Y 1]
the next chapter.
xercises
produce this list representation:
atoms introduced earlier. They could also be (in a more tedious fashion) encod via natural numbers to avoid extra atoms.
19
he tags for commands and expression operators, like := and var, are the extra
We have seen how one can encode WHILE-programs as data in the form of a
oms introduced earlier. They could also be (in a more tedious fashion) encoded
stract syntax trees. Since we can also encode pairing, we are in a position to write
a natural numbers to avoid extra atoms.
WHILE-interpreter in WHILE, a so-called self-interpreter. We will do this in det
What next?
Exercises
Programs-as-data in hWhile in the next chapter.
We can now write compilers, interpreters, specializers in
Thus we do not have to care about parsing programs.
WHILE using abstract syntax trees in list notation
(programs-as-data) instead of string representation.
e have seen how one can encode WHILE-programs as data in the form of ab-
1. Assuming that we start counting variables from 0, give the program-as-data re act syntax trees. Since we can also encode pairing, we are in a position to write a
resentation of the WHILE-program given in Fig. 6.4. HILE-interpreter in WHILE, a so-called self-interpreter. We will do this in detail
In hwhile (see Canvas) we can use the -u flag to 2. Consider the tree t depicted in Fig. 6.5.
a. Why is t a correct tree in D although items like 1, 0, cons, :=, quote, va appear at its leaves rather than just nil?
b. Write tree t in list notation.
c. Does t correctly encode a WHILE-program in abstract syntax? If this is t
case, write the corresponding WHILE-program p for which ppq = t hol 20
in concrete syntax. If this is not the case, apply minimal corrections to t su Assuming that we start counting variables from 0, give the program-as-data rep-
resentation of the WHILE-program given in Fig. 6.4. Consider the tree t depicted in Fig. 6.5.
hWhile -u reverse.while
[0 ,
] ]
,1 ]
[ [@:=, 1, [@quote, nil]]
,
[ @while, [@var, 0]
,
[ [@:=, 1, [@cons, [@hd, [@var, 0]], [@var, 1]]]
, [@:=, 0, [@tl, [@var, 0]]]
]
hWhile uses @ to indicate special atoms
21
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
integer
list of trees list of integers
./hwhile add [3,4]
./hwhile -i add [3,4]
7
./hwhile -l add [3,4]
[nil,nil,nil,nil,nil,nil,nil]
./hwhile -li add [3,4]
[0, 0, 0, 0, 0, 0, 0]
22
A note on hWhile output
There are more output formats, to see them all run: Look at this one, can you explain it?
-La ?
./hwhile -h
/hwhile -Laadd [3,4]
@doWhile
23
END
2008-21. Bernhard Reus, University of Sussex
Next time:
A special interpreter
24
Reviews
There are no reviews yet.