University of Sussex Spring 2021 Informatics
Limits of Computation
Exercises 6
Specialisers, Self-referencing Programs & Time Measure
(Lectures 10–12)
1. Assume you need a program with just one argument that com- putes “+3”, i.e. adds 3 to the given input number (in unary rep- resentation). How do you create and call this program without writing a new program from scratch, given that we already have produced the addition program (see add.while on Canvas)? The answer should be expressed as an hwhile call description.
(Hint: use the specialiser from Lecture 10, also available in file spec.while from Canvas.)
Try out your answer and inspect the output (and test the out- putted program itself via the self-interpreter).
2. Assume we added to WHILE an expression *myself such that E ∗myself σ = p where p is the program in which this expres- sion is used! This says that the semantics of expression *myself in a store is the encoding of the program in which it occurs. This new expression would buy us immediate access to the encoding of a program within this program itself: a powerful programming principle, also called reflection, which is not explicitly expressible in the semantics of WHILE as given.
(a) In this extended language, write a program that outputs its own encoding (AST). This is now suddenly very easy.
(b) Explain why this feature (*myself) can be again deemed a “simple” WHILE-extension that can be translated away into “core” WHILE. In other words, explain why we could rewrite any program using (*myself) into an equivalent WHILE-program (with the same semantics) that does not use this extension. You are not supposed to carry out the actual compilation, just argue why it is possible.
1
3. Consider the following WHILE-program p:
p read X {
Y:= cons X X
}
write Y
Compute timeWHILE(d) for any d ∈ D. p
4. Write a WHILE-program q with the following time measure: timeWHILE(d) = 5 × length(l ) + 4
qd
for any d ∈ D. Here ld denotes the list encoded by d, i.e. d = l. Hint: Start with the simplest terminating while loop you can think of.
2