University of Sussex Informatics
Spring 2021
Limits of Computation
Exercises 2 (covers Lectures 3–5)
WHILE-programs: Syntax & Semantics and Extended WHILE 1. Consider the binary tree t, given in linear notation:
⟨ ⟨ ⟨ nil.nil ⟩.nil ⟩.⟨ ⟨ nil.nil ⟩.nil ⟩ ⟩
(a) Draw t in the usual two-dimensional form.
(b) Does t encode a natural number, and if so, which number?
(c) Does t encode a list of natural numbers, and if so, which list of numbers?
(d) Does t encode a list of lists of natural numbers, and if so, which list of list of numbers?
2. Let a WHILE-program p be given as follows:
p read L {
X:= hd L;
Y:= hd tl L;
while X {
Y:= cons nil Y;
X:= tl X
} }
write Y
(a) What does the program p compute for an input list [M,N]
where M and N are both lists encoding natural numbers?
(b) What happens if we provide more lists than two in the input, i.e. input is of the form [M,N,O,P] where M , N, O , P are all lists encoding natural numbers?
1
(c) What does the program p compute for an input list [M,N] where M and N are not both lists encoding natural numbers?
(d) What happens if we only provide one single list, i.e. input is of the form [M] where M is a list encoding a natural number?
(e) What is the semantics of program p? In other words, define
WHILE
p
. (Look at the answers for the above questions.)
(f) Let p2 be the program we get from p by changing the line Y:= cons nil Y; into Y:= cons (hd X) Y; What does the program p2 compute for an input list [M,N] where M and N are both lists, but of an unspecified type?
For the above you are not supposed to write down any formal computation.
3. Rewrite each of the following programs written in extended WHILE into an equivalent one (i.e. one with the same semantics) in core WHILE:
(a) prog1 read L {
X:= [hd L, hd tl L, 1, false];
}
write X
(b) prog2 read L {
X:=
if X=1{Y:=2}else{Y:=1}
}
write Y
4. (To be completed at home) Write a core WHILE-program isnumber that returns true if the input tree encodes a natural number and false otherwise. Core means that you must not use any extensions (from Lecture 5). Test your program with hwhile.
The interpreter hwhile is available from the labs’ Software Hub and binaries can be downloaded also from our Canvas page enti- tled “WHILE (Programs)”. Read the short manual I put on canvas and familiarise yourself with hwhile.
2