Assignments are due on the due date by 23:59 AST and have to include this cover page. Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the authors named above declare that its content is their original work and that they did not use any sources for its preparation other than the class notes, the textbook, and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported to the Faculty’s Academic Integrity Offificer and possibly to the Senate Discipline Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity
Question 1 (10 marks) A property of pure—that is, side-effect-free—functions is that they are referentially transparent: They interact with other parts of the program exclusively by taking input through explicit function arguments and producing output in the form of their return values. They cannot depend on any “context” (e.g., the contents of certain memory locations not explicitly specifified as function arguments) and they cannot modify any such context through side effects. Explain how this makes it easier to (a) reason about the behaviour of the function, (b) test the function, and (c) debug the function if it misbehaves. Address each of these three points explicitly, even though they are interrelated.
Question 2 (10 marks) Inform yourself about tail recursion and tail call optimization as a method to eliminate the runtime cost of recursive functions used to express essentially iterative computations. The textbook chapter on Control Flow discusses tail recursion. The Wikipedia page (https://en. wikipedia.org/wiki/Tail_call) is also a good source. You may fifind other online material that can help you understand tail recursion, but please do cite any source of information you use in your answer other than the textbook or Wikipedia.
(a) Describe brieflfly what tail recursion is and how the compiler optimizes tail-recursive functions.
(b) Explain why tail call optimization is important in functional languages and why it is okay for imperative languages such as C, Python or Java not to perform tail call optimization. (In other words, even tail-recursive functions use a linear amount of stack space in the recursion depth in these languages.)
(c) Consider the following simple functions written in Haskell. State for each of them whether it is tail-recursive.
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort [x] = [x]
quickSort xs@(p:_) = quickSort ls ++ es ++ quickSort gs
where
(ls, es, gs) = partitionAroundPivot p xs
-- Implementation of partitionAroundPivot omitted
sum1 :: Num a => [a] -> a
sum1 [] = 0
sum1 (x:xs) = x + sum1 xs
sum2 :: Num a => [a] -> a
sum2 xs = sum’ 0 xs
where
sum’ s [] = s
sum’ s (x:xs) = sum’ (s + x) xs
Question 3 (10 marks) In class, I claimed that recursion is more powerful than iteration. In terms of expressiveness, this is certainly true: anything that can be expressed elegantly using iteration can also be expressed reasonably elegantly using recursion, but the converse is not true. This question focuses not on elegance but on an objective notion of expressive power. Are there computations that can be formulated as recursive functions but absolutely cannot be expressed using iteration? If you answer yes, give an example and explain why this computation cannot be expressed iteratively at all. If you answer no, explain how any recursive function can be turned into an equivalent iterative computation. (Hint: Think about how your processor executes any program.)