University of Sussex Informatics
Spring 2021
Limits of Computation
Feedback to Exercises 2 (covers Lectures 3–5)
Dr Bernhard Reus
WHILE-programs: Syntax & Semantics and Extended WHILE 1. Consider the binary tree t in linear notation:
⟨ ⟨ ⟨ nil.nil ⟩.nil ⟩.⟨ ⟨ nil.nil ⟩.nil ⟩ ⟩ (a) Draw t in the usual two-dimensional form.
Answer (we abbreviate nil by n):
/\ /\ /\ /\ /\ n/\ n
nn nn
(b) Does t encode a natural number, and if so, which number? Answer: NO, the tree does not have the required format (consider that a number corresponds to a list of nils).
(c) Does t encode a list of natural numbers, and if so, which list of numbers?
Answer: NO, the second element would work – ⟨ nil.nil ⟩ – but not the first element – ⟨⟨nil.nil⟩.nil⟩ – as it does not encode a number.
(d) Does t encode a list of lists of natural numbers, and if so, which list of list of numbers?
Answer: YES, [[1],[0]] .
Comment: In principle, other readings of the tree are also pos- sible (but not asked for) like: [[1],1] , [⟨⟨nil.nil⟩.nil⟩,1] or [[[0]],[0]]
In these cases the elements of the list all have different “types” (note that “types” are in the “eye of the beholder” in WHILE).
1
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? Answer: Addition of the two natural numbers encoded by M and N.
(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?
Answer: Addition of the two natural numbers encoded by M and N, the other lists are ignored.
(c) What does the program p compute for an input list [M,N] where M and N are not both lists encoding natural numbers? Answer: The result is the concatenation of the list encoding length(M) and list N. Note that every tree can be seen as list, so it is ok to apply length.
(d) What happens if we only provide one list in the input, i.e. input is of the form [M] where M is a list encoding a natural number?
Answer: Result is the number encoded by M.
(e) What is the semantics of program p? In other words, define
WHILE
length(a1) ◦ a2
p (d) = length(a1)
p
Answer: According to the above, we have that
WHILE
if d = [a1, a2, . . .] if d = [a1]
if d = []
. (Look at the answers for the above questions.)
[]
2
where ◦ denotes list concatenation. So, for instance, [1, 2, 3] ◦ [4, 5, 6] = [1, 2, 3, 4, 5, 6]
Note that above length(a1) is a number, so length(a1) is a number encoding, which we know is a list of nils (or equiv- alently 0s). And a2 is a tree which we can always read as a list, so this concatenation makes sense. The outermost for this concatenation above is to indicate the tree that rep- resents that resulting concatenated list. Note also that this is a complete definition, because every d ∈ D encodes some list as well as each ai ∈ D.
(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] if M and N are both lists, but of an unspecified type? Answer: The program will return reverse(M) concatenated with N. It will ignore any extra elements in the input list. Any missing list will be replaced by the empty list. Note that every tree can be seen as list.
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 Answer:
prog1 read L {
X:= cons hd L cons hd tl L cons (cons nil nil) cons nil nil;
}
write X
(b) prog2 read L {
X:=
if X=1{Y:=2}else{Y:=1}
}
3
write Y
Answer:
prog2 read L {
X:= cons hd tl L nil;
if hdX { //Xnotanumber
else {
Y:= cons nil nil
}
iftlX{ //Xisatleast2ornotnumber Y:= cons nil nil
}
else { // X is exactly 1
Y:= cons nil cons nil nil
}
} }
write Y
Of course, one could also replace X=1 with the code for equal [X,1] once we have written the equality function (next week). But this would lead to a much longer program.
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 exten- sions (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.
Answer: Try this at home first. The answer will be published as a .while program in the programs section of our Canvas site in a few days.
4