University of Sussex Spring 2021 Informatics
Limits of Computation
Feedback for Exercises 6 Dr Bernhard Reus
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 representation). How do you create and call this program with- out writing a new program from scratch, given that we already have produced the addition program (see add.while on Can- vas)? The answer should be expressed as an hwhile call de- scription.
(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).
Answer: Let ADD be the program as data representation of add.while, i.e. as hwhile output (using the extra @ symbols):
[0 ,
] ]
,2 ]
[ [@:=, 1, [@hd, [@var, 0]]]
, [@:=, 2, [@hd, [@tl, [@var, 0]]]]
,
[ @while, [@var, 1]
,
[ [@:=, 2, [@cons, [@quote, nil], [@var, 2]]]
, [@:=, 1, [@tl, [@var, 1]]]
]
Then the required program call is:
hwhile spec.while “[ADD,3]”
This will return the following program as data (list) that one can run with the help of the self-interpreter u:
1
[0, [
[@:=, 0, [@cons, [@quote, 3], [@cons, [@var, 0], [@quote, 0]]]],
[@:=, 1, [@hd, [@var, 0]]],
[@:=, 2, [@hd, [@tl, [@var, 0]]]],
[@while, [@var, 1], [
] ]
, 2]
[@:=, 2, [@cons, [@quote, 0], [@var, 2]]],
[@:=, 1, [@tl, [@var, 1]]]
]
2. Assume we added to WHILE an expression *myself such that E∗myselfσ = p where p is the program in which this expression is used. This would buy us immediate access to the encoding of a program within this program itself: a powerful programming principle, also called reflection.
(a) In this extended language, write a program that outputs its own encoding (AST). This is now suddenly very easy. Answer:
quine read X {
Y := *myself
}
write Y
(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 a WHILE-program (with the same semantics) that does not use this extension. Note that you do not have to actually carry out the compi- lation.
Answer:
This is a consequence of the Recursion Theorem. The above example from (a) would be translated to:
p read L {
q:= hd L;
d:= hd tl L
}
write q
so we get by definition that
WHILE
2
p
[q, d] = q
where the encoding brackets have been explicitly written (often we drop them for simplicity).
Now by the Recursion Theorem we know that because of the above there must be a WHILE-program q such that
or if dropping the encoding brackets q
General Case: Now, in general replace all occurrences of *myself in the statement list S of the program by a fresh variable q (not occurring in S) and call the resulting statement list SQ. Then the program
prog read X { S
}
write Y
that contains *myself in S is used to write p as before to which will then apply the Recursion Theorem:
p read L {
q:= hd L;
X:= hd tl L;
SQ
}
write Y
Then, by the same reasoning as for the example above, we get from the Recursion Theorem the existence of program q such that
prog read X {
Y:= cons X X
}
write Y
Compute timeWHILE(d) for any input d ∈ D. p
Answer:
timeWHILE(d)=2+twhereY:=consXX⊢time {X:d}⇒t. p
3
WHILE WHILE
q
and putting it all together we obtain
(d) = p [q, d] WHILE
q (d) = q
WHILE
(d) = q.
WHILE WHILE WHILE
q (d) = p [q, d] = prog (d) 3. Consider the following program:
Let us compute t, for which need the rule: X:=E⊢time σ⇒t+1ifTE=t
Instantiating Y for X, {X : d} for σ, cons X X for E we obtain: Y:=consXX⊢time {X:d}⇒TconsXX + 1
By the rules for T that tell us how much time it takes to eval- uate WHILE-expressions we get:
T cons X X = 1 + T X + T X = 1 + 1 + 1 = 3 Therefore, timeWHILE(d) = 2 + (3 + 1) = 6 for any d ∈ D. This
p
is of course a special case, as most of the time the runtime depends on the input.
4. Write a WHILE-program q with the following time measure: timeWHILE(d) = 5 × length(l ) + 4
qd
whereld isthelistencodedbyd,i.e.d=lforanyd∈D.
Answer: A program that satisfies the requirement is e.g.
prog read X {
while X {
X:= tl X }
}
write X
Note that the body of the while loop takes 3 units – 1+(1+1) – to execute, but the guard and the check for nil add 2 = 1+1 units. So the loop execution takes 3+2=5 times the length of the input as list. Wait, we have to consider the termination case of the loop, for which 2 more units are needed for the guard evaluation and nil-check, and finally 2 more units for input and output. So we get the required 5 × length(ld) + 2 + 2.
4