University of Sussex Informatics
Spring 2021
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;
Limits of Computation
Exercises 3
Programs-As-Data, Self-Interpreter, and hwhile 1. Consider the programs p1 in Figure 1 and add in Figure 2.
(a) What is p1 ([2, 5, 7, 8]) according to the definition of p1 WHILE
and add (from the last exercise sheet) according to ?
(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.
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.
1
while X {
Y := cons nil Y;
X := tl X
} }
write Y
Figure 2: WHILE-program add
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).
2