# CS代考计算机代写 compiler ER interpreter The National Student Survey (NSS) 2021

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

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 at•oms 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 sameLneutm’sbgeor.: 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,gbuotnwlyefodrefi“npeurteh”e 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 -La add [3,4]

@doWhile

23

END

© 2008-21. Bernhard Reus, University of Sussex

Next time:

A special interpreter

24