Problem 2 (12 points).
Consider the following Scheme program:
(define A
(lambda ()
(let* ((x 0)
(C (lambda (P) (let ((x 1)) (P))))
(D (lambda () x))
(B (lambda () (let ((x 2)) (C D)))))
(B)
) )
)
a) (3 points) What does this Scheme program print? Explain your answer.
b) (3 points) What would the program print if Scheme used dynamic scoping with shallow binding?
c) (3 points) What would the program print if Scheme used dynamic scoping with deep binding?
d) (3 points) In the above program, A, B, C, and D are functions. Which of these are higher-order functions? Explain your answer.
Problem 3 (6 points, 2 points each).
Circle TRUE or FALSE.
a) (TRUE/FALSE) If functions are third-class values, then when a function is called, its static reference environment (i.e., statically enclosing environment) is always active on the stack.
b) (TRUE/FALSE) If functions are first-class values, then when a function is called, its static reference environment is always active on the stack.
c) (TRUE/FALSE) If functions are second-class values, then when a function is called, its static reference environment is always active on the stack.
CSCI4430 Exam 2, Spring 2016 3
Name: __________________________
Part 2. Scheme Programming Problem 1 (13 points). Consider the following function
(define func1
(lambda (n)
(cond ((zero? n) 1)
((eq? n 1) 1)
(else (* n (func1 (- n 1))))
) )
)
a) (3points)Whatdoesfunc1do?
b) (10 points) Write a tail-recursive version of func1.
CSCI4430 Exam 2, Spring 2016 4
Name: __________________________
Problem 2 (17 points).
Consider function subseqs.
(define subseqs
(lambda (lis1 lis2)
(cond ((null? lis1) 1)
((null? lis2) 0)
((equal? (car lis1) (car lis2))
(+ (subseqs (cdr lis1) (cdr lis2))
(subseqs lis1 (cdr lis2))))
(else (subseqs lis1 (cdr lis2)))
) )
)
a) (12 points)* What does subseqs do? Give 2 examples of usage of subseqs showing the input and output, as you did in the comments for your Scheme homework. Examples where the first or second argument is the null list do not count
(e.g., (subseqs ¡®() ¡®(a b c)) doesn¡¯t count).
b) (5points)Issubseqstail-recursive? YES NO
CSCI4430 Exam 2, Spring 2016
5
Name: __________________________
Part 3. Higher-order functions map, foldl and foldr
Below are the definitions of higher-order functions map, foldl and foldr, which we
studied in class.
(define (map f lis)
(if (null? lis) ¡®()
(cons (f (car lis)) (map f (cdr lis)))))
(define (foldl op lis id)
(if (null? lis) id
(foldl op (cdr lis) (op id (car lis)))))
(define (foldr op lis id)
(if (null? lis) id
(op (car lis) (foldr op (cdr lis) id))))
Problem 1 (6 points).
Circle the ones that are tail-recursive:
map foldl foldr
Problem 2 (12 points)*
Define a function filter, which takes a list and returns a list containing all elements that satisfy a given predicate. The elements should appear in the order they appear in the original list. For example,
(filter (lambda (x) (< x 5)) ¡®(3 9 5 2 4 7)) should return (3 2 4).
Important note: You are allowed to use only foldl, cons, if and function constructor lambda.
(define (filter p lis)
(foldl ________________________________________________________
______________________________________________________________ ______________________________________________________________
CSCI4430 Exam 2, Spring 2016 6
Name: __________________________
Problem 3 (12 points)*.
Write a function syms, which takes a list of arbitrarily nested numbers and symbols and produces a flat list containing only the symbols.
As an example, (syms ¡®(((8)) a (1 c ((7 b))))) should return (a c b). As another example, (syms ¡®(1 (2 (d (a))))) should return (d a).
Important note: The body of the function should be one call to cond. In addition to cond, use exactly foldl, map, cons, append, number?, symbol? and constant ().
(define (syms lis)
(cond ______________________________________________
________________________________________________________
________________________________________________________
CSCI4430 Exam 2, Spring 2016 7
Name: __________________________
Part 5. Evaluation order
Problem 1 (20 points).
Consider lambda expression (¦Ëz. z z) ((¦Ëxy. x y) ((¦Ëv. v) (¦Ëw. w)))
a) (10 points) Evaluate the expression using applicative order. Important note: At each step underline the redex you choose; we will deduct points otherwise.
b) (10 points)* Now, evaluate the expression using normal order. Important note: At each step underline the redex you choose.
Name: __________________________
CSCI4430 Exam 2, Spring 2016 10