Problem 4 (10 points)*
Below is a program, written in the Pascal-like language we used in class. Assume that the language uses dynamic scoping.
x : integer
procedure set_x(n : integer)
x := n
procedure print_x
write_integer(x)
procedure foo(S,P : function; n : integer)
x : integer := 5
if n in {1,3}
set_x(n)
else
S(n)
if n in {1,2}
print_x else
P
/* begin main */
set_x(0); foo(set_x, print_x, 1); print_x;
set_x(0); foo(set_x, print_x, 2); print_x;
set_x(0); foo(set_x, print_x, 3); print_x;
set_x(0); foo(set_x, print_x, 4); print_x;
a) (4 points) What does the program print if the language uses dynamic scoping with shallow binding?
b) (6 points) What does the program print if the language uses dynamic scoping with deep binding?
CSCI4430 Exam 2, Fall 2018 4
Name: __________________________
Part II. Scheme Programming
For your reference, functions map, foldl and foldr are included below.
(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 (12 points)*
Consider the following Scheme function
(define (fun lis)
(foldr (lambda (x y)
(let ((f (lambda (z) (cons x z))))
(append (map f y) y)))
lis ‘(()) ))
a) (6 points) Give two distinct examples of usage of fun showing the input and output as you did in the comments for your Scheme homework.
b) (6points)Whatdoesfuncompute?
CSCI4430 Exam 2, Fall 2018 5
Name: __________________________
Problem 2 (13 points)
Here is another fun. You may assume that the argument is a positive integer.
(define fun
(lambda (n)
(if (= n 1) 0 (+ 1 (fun (quotient (+ n 1) 2))))))
a) (4 points) What does fun compute?
b) (2 points) Is fun tail-recursive (circle one)? YES NO
c) (7 points) If your answer to b) is YES, explain why. If your answer is NO, write a tail-recursive version of fun.
CSCI4430 Exam 2, Fall 2018 6
Name: __________________________
Problem 3 (12 points)*
Willy Wazoo is writing function all-pairs, which takes two lists and computes their Cartesian product. E.g., (all-pairs ¡®(1 2 3) ¡®(6 5 4)) should yield ((1 6) (1 5) (1 4) (2 6) (2 5) (2 4) (3 6) (3 5) (3 4)).
Willy needs to use foldl, and he started on the right track, then he got stuck. Fill in the blanks in Willy¡¯s code.
(define (all-pairs lis1 lis2)
(foldl (lambda (x1 y1)
(foldl (lambda (x2 y2)
________________________________ ;; body of inner lambda ____________ ;; list argument of inner fold
____________ ;; id argument of inner fold )) ;; closing inner fold and outer lambda
____________ ;; list argument of outer fold ____________ ;; id argument of outer fold
)) ;; closing outer fold and define
Problem 4 (13 points)*
Write a function deep-reverse, which takes an arbitrarily nested list and produces its ¡°mirror image¡±. For example,
(deep-reverse ¡®(((8)) a (1 c ((7 b))))) should yield ((((b 7)) c 1) a ((8))).
Important: Use foldl and map at least once each. In addition to foldl and map, the only functions/constructs you are allowed to use are cons, if, atom? and lambda.
(define (deep-reverse lis)
(if _______________________________________________
________________________________________________________
________________________________________________________
CSCI4430 Exam 2, Fall 2018 7
Name: __________________________
Name: __________________________
Part |II. Attribute Grammars over the Lambda Calculus
Problem 1 (15 points)
Recall the grammar that defines the syntax of the pure lambda calculus:
E¡úx
E ¡ú ( ¦Ëx. E ) E¡ú(EE)
a) (10 points) Write an attribute grammar that associates an attribute whnf with each expression E, such that E.whnf = true if and only if the lambda term in E is in weak head normal form (WHNF).
b) (3 points) Your grammar from a) is S-attributed YES c) (2 points) Attribute whnf is Synthesized
NO Inherited
CSCI4430 Exam 2, Fall 2018
8
Name: __________________________
Part IV. Lambda Calculus and Reduction Strategies
Problem 1 (25 points)
a) (10 points) Reduce the term below to an answer in normal form using normal order reduction. Important: At each step underline the redex you choose; we will deduct points otherwise.
(¦Ëy.¦Ëz. y) (¦Ëx.(¦Ëy.¦Ëz. y) x ((¦Ëy. x y) (¦Ëy. x y))) ¨¦Â
b) (10 points) Now, reduce the same term to an answer in normal form using applicative order reduction. Important: At each step underline the redex you choose.
(¦Ëy.¦Ëz. y) (¦Ëx.(¦Ëy.¦Ëz. y) x ((¦Ëy. x y) (¦Ëy. x y))) ¨¦Â
c) (5 points) Reduce the term below to an answer in head normal form using normal order reduction. Important: At each step underline the redex you choose.
(¦Ëy.¦Ëz. y) (¦Ëx.(¦Ëy. y) x ((¦Ëy. x y) (¦Ëy. x y))) ¨¦Â
CSCI4430 Exam 2, Fall 2018 9