• CLEARLY PRINT YOUR NAME HERE:

• You have 80 minutes to complete the exam (8:30-9:50)
• There are 5 questions on the exam, worth 9 marks each, attempt all questions.
• Answer directly on the exam paper, extra paper is available if needed.
• Some of the questions are quite open-ended, so be sure not to spend excessive amounts of time on one question at the expense of the rest of the exam.
• The exam is open book, open notes, but no calculators, phones, or other electronic aids of any form may be used during the exam.
• Be sure to check your exam to make sure all five questions are included.

Question	Mark
1. Parameter passing [9 marks]
2. Tail recursion [9 marks]
3. Higher order functions [9 marks]
4. Macros [9 marks]
5. Grammars [9 marks]
Exam Total [45 marks]

Question 1: Parameter passing [9]

We studied a number of lisp features with respect to parameter passing, including &rest, &key. For each of these, discuss how it differs from your experience with either C, C++, or Java, and whether or not you feel you would use such a feature if it was supported in those languages. (Be sure to provide justification for why you would/would not use the feature.)

Question 2: Tail recursion [9]

(i) Describe the role of an accumulator in tail recursion.

(ii) Write a tail recursive version of the function below.

; (alternates L EvenOdd) takes a list, L as its first parameter
;   and a true/false value, EvenOdd, as its second
; If L is not a list the function simply returns L,
;    otherwise it returns a copy of L with alternate elements missing.
; The EvenOdd parameter specifies whether the odd-position elements or
;   the even-position elements are missing.
; e.g. (alternates '(a b c d e f g) t)   would return (a c e g)
;      (alternates '(a b c d e f g) nil) would return (b d f)
(defun alternates (L EvenOdd)
   (cond
      ((not (listp L)) L)
      ((null L) L)
      (EvenOdd (cons (car L) (alternates (cdr L) nil)))
      (t (alternates (cdr L) t))))

Question 3: Higher order functions [9]

(i) Describe the concept of closures, and the role of higher order functions in implementing them.

(ii) Implement the function specified below.

; (applyAll FuncList ArgList)
; - FuncList is meant to be a list of functions
; - ArgList is meant to be a list of arguments
; - applyAll applies each function in FuncList to the argument list,
;   and forms and returns a list of the results
; e.g. (applyAll '(+ - *) '(10 5)) returns (15 5 50)

Question 4: Macros [9]

Given the xor macro definition below, show the expansion of the following macro use: (xor A B C)

(defmacro xor (v1 v2 &rest vrest)
   `(cond
       ((null (quote ,vrest)) (if ,v1 (not ,v2) ,v2))
       (,v1 (not (xor ,v2 ,@vrest)))
       (t (xor ,v2 ,@vrest))))

Question 5: Grammars [9]

Assuming INT matches any sequence of digits and VAR matches any sequence of alphabetic characters, either show that the grammar below is ambiguous or describe why it is not ambiguous.

S --> VAR "=" E
E --> PROD "+" E
E --> E "-" PROD
PROD --> VAL "*" PROD
PROD --> PROD "/" VAL
VAL --> INT
VAL --> VAR