COMPUTER SCIENCE TRIPOS Part IB – 2016 – Paper 3
Compiler Construction (TGG)
Programming answers should be written in some notation approximating SML or
OCaml.
(a) Describe what is meant by tail recursion. [4 marks]
(b) Eliminate tail recursion from foldl given below. Explain your answer.
(*
foldl : (‘a -> ‘b -> ‘a) -> ‘a -> ‘b list -> ‘a
*)
let rec foldl f accu l =
match l with
[] -> accu
| a::l -> foldl f (f accu a) l
[8 marks]
(c) Eliminate tail recursion from the following mutually tail-recursive functions.
Explain your answer.
let rec is_even n =
if n = 0
then true
else is_odd (n – 1)
and is_odd n =
if n = 0
then false
else is_even(n – 1)
[8 marks]