University of Sussex Informatics
Spring 2021
Limits of Computation
Feedback Exercises 3
Programs-As-Data, Self-Interpreter, and hwhile (covers Lectures 3–6)
Dr Bernhard Reus
1. Consider the programs p1 in Figure 1 and add in Figure 2.
p1 read L {
R := 0;
X := hd L;
Y := hd tl L;
while X {
R :=
X := tl X }
}
write R
Figure 1: WHILE-program p1 WHILE
add read L {
X := hd L;
Y := hd tl L;
(a) What is p1 ([2, 5, 7, 8]) according to the definition of p1 WHILE
and add (from the last exercise sheet) according to ? Answer: Since p2 is addition (on encodings of natural numbers),
WHILE
(b) Translatetheprogramaddfromaboveintoitsdatarepresentation (programs as data) using the definition of the encoding presented in Lecture 6. Encode the variables starting from number 0 in the order of appearance.
while X {
Y := cons nil Y;
X := tl X
} }
write Y
Figure 2: WHILE-program add
p1 is multiplication, so p1 ([2, 5]) = 10. Note that only the first two elements are used in the input list.
Answer:
1
[0,
[ [:=,1,[hd,[var,0]]],
[:=,2,[hd,[tl,[var,0]]]], [while,[var,1],
[ [:=,2,[cons,[quote,nil],[var,2]]], [:=,1,[tl,[var,1]]]
] ]
], 2]
Make sure that you have the right number of square brackets for all the blocks.
2. On our Canvas page you find the program STEP incomplete.while in the Programs section – or also from this link
canvas.sussex.ac.uk/courses/12888/files/2022795
This program is macro-called in the self-interpreter for the WHILE- language with one variable, called WH1LE. One case in the second switch construct is missing (for assignment). Fill in the missing lines.
Answer:
val:= arg ;
DSt:= tl DSt;
CSt:= tl CSt
This follows directly from Lecture 6, Slide 20.
3. Run the program p1 from Question 1 in hwhile. Which output flag is appropriate here?
Please consult the Canvas page:
canvas.sussex.ac.uk/courses/12888/pages/while-programs-and-hwhile
on our Limits site for more info about hwhile. Ask the tutor in your seminar if you have problems with installation. Note that hwhile is also available on the SoftwareHub on the Chichester Lab machines (which are accessible remotely).
Answer: The -i flag as the result is a number.
2