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. It’s 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?
It’s 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: ei@sussex.ac.uk
2
Using your feedback
In last year’s 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
using extensions can be translated (compiled) into one writte
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 o
We use special additional atoms.
We use special additional atoms.
Definition 6.5 (Extra atoms). We add several special atoms D that so far only used Definition 6.5 (Extra atoms). We add several special atoms D
one atom: nil. These extra atoms are var, cons, :=, while, if, tl, hd, quote.
one atom: nil. These extra atoms are var, cons, :=, while, if
Programs as data in WHILE This extension can be done according to our discussion in Sec 5.3.
This extension can be done according to our discussion in Sec
There is one more issue we need to sort out yet for the representation of pro-
There is one more issue we need to sort out yet for the re
grams as data objects, namely the encoding of variables. We cannot use a fi-
grams as data objects, namely the encoding of variables. W
We are now in a position to define more
nite number of at•oms as there are an infinite number of possible variables. We
nite number of atoms as there are an infinite number of po
exactly how the list encoding of abstract
use numbers to encode variable names. This encoding is produced by the map
use numbers to encode variable names. This encoding is pr
syntax trees work.
varnum : VariableName ! N for which it holds that varnum = varnum implies
•
varnum : VariableName ! N for wXhich it holdYs that varnumX that X = Y. In other words, varnum uniquely encode variable names. The concrete
that X = Y. In other words, varnum uniquely encode variable n Lists are themselves encoded as binary trees.
numbers are actually not important, it is only important that the same variable is
•
numbers are actually not important, it is only important that 2
encoded by the sameLneutm’sbgeor.: 2
encoded by the same number.
The representation ppq of a WHILE-program p as data can now be defined by
The representation ppq of a WHILE-program p as data can the map p q: WHILE-programs ! WHILE-data as outlined in Figure 6.2. On the
the map p q: WHILE-programs ! WHILE-data as outlined in right hand side of each equational definition we define lists and not trees as those
right hand side of each equational definition we define lists an are more readable. To obtain proper elements in D one just needs to apply encoding
are more readable. To obtain proper elements in 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 com The program name is not iTnchleudperodgirnamthenaAmSeTisbencoatuisneclnuadmedesinarteheonAlySTnebeedceadufsoernames
macro calls in the extendedmlacnrgoucaaglels, binutthweeedxetefindeedthleanegnucoagdein,gbuotnwlyefodrefi“npeurteh”e encod WHILE-programs. WHILE-programs.
⇥⇤⇥
pprognamereadX{S}writepYpqr=ognamvearenuamdX,p{Sq},wvrarintuemYq = varnum ,pSq,va XYX
pwhile E Bq pwh=ile E[ wBhqile, pEq, pBq ] = [ while, pEq, pBq
pX:=Eq pX:=Eq[:=,varnumX,pEq] = [:=,varnumX,pEq
pifEB elseB q pif=EB [eilfs,epEBq,qpB q,pB q] = [if,pEq,pB q,pB TETETET
pifEBq pif=EBq[if,pEq,pBq,[]] = [if,pEq,pBq,[]]
expressions commands
p{C=;C ;[.p.C.;Cq,p}Cq q,…,pC q] = [pC q,pC q,…,p 12n121n2n12
p{C ;C ;…;C }q pnilq
pXq
pcons E Fq phd Eq
ptl Eq
pni=lq [ quote, nil ]
pXq= [var,varnumX]
pcons E Fq
= [ cons, pEq, pFq ]
phd Eq
= [hd,pEq]
ptl Eq
= [tl,pEq]
= [ quote, nil ]
= [ var, varnumX ] = [ cons, pEq, pFq ] = [hd,pEq]
= [tl,pEq]
WHILE programs in D
Fig. 6.2: Encoding of WHILE-programs as da Fig. 6.2: Encoding of WHILE-programs as data
18
2 One can use unary or binary representation of numbers actually, and in th One can use unary or binary representation of numbers actually, and in the following we may use
2
one or the other, according to the task at hand.
one or the other, according to the task at hand.
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 -La add [3,4]
@doWhile
23
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
A special interpreter
24