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