CSCI 330: Spring 2017 Midterm
format and topics

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