Midterm guidelines and practice questions
The midterm will be Monday, October 16 in class. You’ll get 75 minutes and no access to computer or notes.
Some general guidelines for material focused on by the midterm:
You may be shown and/or asked to write short snippets of Racket.
Anything from the assignments such as church encodings or desugarings may be covered.
You will not be asked about the exact semantics for the bigstep CE and CES semantics or the smallstep CEK semantics from the slides, but you should understand how these semantics work conceptually as well as closure creation, storepassing, and stackpassing as techniques.
You should understand all the interpreters we’ve looked at and code written in class. You may be asked to fix or finish code for an interpreter or to transform code manually using a stackpassing or storepassing translation.
You should understand alphaconversion, betareduction, etareduction/expansion, captureavoiding substitution, and the concept of free/bound variables. You should be able to evaluate programs stepbystep in the lambdacalculus using the callbyvalue contextandredex style of semantics.
You should understand the Scheme semantics for lambdas/closures, call/cc, firstclass continuations, promises, exceptions, letrec and letrec*, begin, set!, and other features we’ve looked at specifically.
Following are some example questions and answers to prepare with.
1 Review questions
1. The factorial function can be defined in Racket:
(define (fact n) 
(if (= n 0) 
1 
(* n (fact ( n 1))))) 
Write a tailrecursive version. (Need not be stackpassing, you can use an integer accumulator.)
2. What can the following schemeexp? expression translate to in terms of the irexp? language. This should be something reasonable your assignment 2 desugarer might produce (without any unnecessary helper functions added).
(let loop () (loop)) 
You can show it as multiple desugaring steps or just the end result.
3. This fib function computes the nth number in the Fibonacci sequence.
(define (fib n) 
(if (<= n 1) 
n 
(+ (fib ( n 1)) (fib ( n 2))))) 
Perform a stackpassing transformation of fib to produce a tailrecursive version that accumulates a stack explicitly, modifying it at each point where fib is called and/or returns. You might start with code that looks like:
(define (fib n) 
(define (ret n st) 
(match st 
..; handle each possible stack frame 
[else n])) 
(define (tfib n st) 
..) 
(tfib n '())) 
4. Show each step in the evaluation of the following term using a (callbyvalue) contextandredex semantics. Show both the evaluation context and redex at each step.
((λ (x) x) ((λ (u) (u u)) (λ (y) y))) 
5. The function 3n1steps iterates the collatz sequence (even numbers are halved, odd numbers are multiplied by 3 and incremented) until reaching the number 1 and returns the number of increasing steps.
(define (3n1steps n) 
(define c 0) 
(define (next n) 
(if (= 0 (modulo n 2)) 
(/ n 2) 
(begin (set! c (+ c 1)) 
(+ 1 (* 3 n))))) 
(let loop ([n n]) 
(let ([v (next n)]) 
(if (= v 1) 
c 
(loop v))))) 
Write a semantically equivalent function without using mutation (set!). Do not inline the function next, but manually perform a storepassing/valuepassing style of transformation.
6. Write a churchencoding of the following
(if #t 0 (λ (a b) a)) 
into the grammar:
e ::= (λ (x) e) 
 (e e) 
 x 
using the encodings from assignment 1.
7. Show an αequivalent term (an alpharenaming) such that each variable is bound by only a single lambda.
(λ (a) (((λ (a) a) a) (λ (a) (a a)))) 
8. Referencing any of the semantics we’ve discussed so far, explain the difference between callbyvalue (eager) order of evaluation and callbyname (lazy) order of evaluation.
9. Show three steps in the evaluation of the following term using a (callbyvalue) contextandredex semantics. Show both the evaluation context and redex at each step.
((λ (x) (x x)) (λ (y) ((y y) y))) 
10. What does the following Racket code return? Explain.
(((((call/cc call/cc) (lambda (x) (lambda (y) x))) 1) 2) 3) 
11. The following is part of a storepassing interpreter—
(define (interp e env sto) 
(match e 
; ... 
[`(and ,e0 ,e1) 
(matchdefine (cons v0 sto1) (interp e0 env sto)) 
(if v0 
(interp e1 env sto1) 
(cons #f sto1))] 
[`(or ,e0 ,e1) 
(matchdefine (cons v0 sto1) (interp e0 env sto)) 
(if v0 
(interp e0 env sto1) 
(interp e1 env sto1))] 
; ... 
)) 
Give an example of a Scheme expression that would not be evaluated correctly using this interpreter (assuming all other language forms such as let, lambda, if, etc, are implemented correctly).
12. If evaluating the program ((λ (a) (λ (b) a)) (λ (c) c)) in a closurecreating interpreter (i.e., either a CE or CEK semantics). What value is returned (i.e., a closure consisting of what lambda and environment)?
1.1 Solutions
1. There are many reasonable answers. Two are:
(define (fact n) 
(define (tfact n v) 
(if (= n 0) 
v 
(tfact ( n 1) (* v n)))) 
(tfact n 1)) 
and
(define (fact n) 
(let loop ([n n][v 1]) 
(if (= n 0) 
v 
(loop ( n 1) (* n v))))) 
In fact, Racket compiles these exactly the same way as both desugar to a letrec form defining a single tailrecursive function.
2. Either
(let loop () (loop)) 
=> 
(letrec* ([loop (lambda () (loop))]) 
(loop)) 
=> 
(let ([loop '()]) 
(let ([_ (set! loop (lambda () (loop)))]) 
(loop))) 
or
(let loop () (loop)) 
=> 
(letrec ([loop (lambda () (loop))]) 
(loop)) 
=> 
(let ([loop '()]) 
(let ([tmp (lambda () (loop))]) 
(let ([_ (set! loop tmp)]) 
(loop)))) 
would be good.
3. Add two stack frames. The frame n2 remembers to compute (fib ( n 2)) and places an add frame with the value of (fib ( n 1)) on the stack when invoked. the frame add takes both values and adds them, returning the sum to the rest of the stack. When a null stack is reached, the final value is returned.
(define (fib n) 
(define (ret n st) 
(match st 
[`(n2 ,n1 ,st1) 
(tfib n1 `(add ,n ,st1))] 
[`(add ,n1 ,st1) 
(ret (+ n n1) st1)] 
[else n])) 
(define (tfib n st) 
(if (<= n 1) 
(ret n st) 
(tfib ( n 1) `(n2 ,( n 2) ,st)))) 
(tfib n '())) 
4. In three steps:
((λ (x) x) ((λ (u) (u u)) (λ (y) y))) 

context: ((λ (x) x) □) 
redex: ((λ (u) (u u)) (λ (y) y)) 
beta> ((λ (y) y) (λ (y) y)) 

((λ (x) x) ((λ (y) y) (λ (y) y))) 

context: ((λ (x) x) □) 
redex: ((λ (y) y) (λ (y) y)) 
beta> (λ (y) y) 

((λ (x) x) (λ (y) y)) 

context: □ 
redex: ((λ (x) x) (λ (y) y)) 
beta> (λ (y) y) 

(λ (y) y) 
5. The count becomes another parameter to loop, passed forward at each call. It also becomes both another parameter and returned value for next. It would also be just fine to use letvalues and values instead of matchlet and cons. You might also assume it’s a cons cell and use car and cdr directly.
(define (3n1stepspure n) 
(define (next n c) 
(if (= 0 (modulo n 2)) 
(cons (/ n 2) c) 
(cons (+ 1 (* 3 n)) (+ c 1)))) 
(let loop ([n n] [c 0]) 
(matchlet ([(cons v c) (next n c)]) 
(if (= v 1) 
c 
(loop v c))))) 
6. A valid encoding would be:
(((λ (t) (λ (f) (t t))) 
(λ (_) (λ (g) (λ (x) x)))) 
(λ (_) (λ (a) (λ (b) a)))) 
where this breaks down into
((booleantrue 
(λ (_) natzero)) 
(λ (_) curriedlambda)) 

booleantrue: (λ (t) (λ (f) (t t))) 
natzero: (λ (g) (λ (x) x)) 
curriedlambda: (λ (a) (λ (b) a)) 
7. Using the names x,y,z, this would be:
(λ (x) (((λ (y) y) x) (λ (z) (z z)))) 
8. Some reasonable answers:
In callbyvalue evaluation, argument expressions are evaluated to a value before being passed to the applied function. In callbyname (lazy) evaluation, arguments are passed as a suspended computation (like a promise), to be evaluated when needed.
In a textual reduction (term rewriting) semantics, callbyvalue requires argument expressions to be evaluated to a value (lambda) before being substituted into the applied function. In a callbyname (lazy) semantics, an application expression in argument position may be substituted into the body of a lambda to be evaluated later.
In a callbyvalue CE (controlexpression and environment) semantics, substitution environments accumulate a mapping from variables to pairs of a lambdaexpression and environment. In a callbyname semantics, substitution environments would need to map variables to arbitrary expressions (not just lambdas) paired with environments.
9. Three steps:
((λ (x) (x x)) (λ (y) ((y y) y))) 

context: □ 
redex: ((λ (x) (x x)) (λ (y) ((y y) y))) 
beta> ((λ (y) ((y y) y)) (λ (y) ((y y) y))) 

((λ (y) ((y y) y)) (λ (y) ((y y) y))) 

context: □ 
redex: ((λ (y) ((y y) y)) (λ (y) ((y y) y))) 
beta> (((λ (y) ((y y) y)) (λ (y) ((y y) y))) (λ (y) ((y y) y))) 

(((λ (y) ((y y) y)) (λ (y) ((y y) y))) (λ (y) ((y y) y))) 

context: (□ (λ (y) ((y y) y))) 
redex: ((λ (y) ((y y) y)) (λ (y) ((y y) y))) 
beta> (((λ (y) ((y y) y)) (λ (y) ((y y) y))) (λ (y) ((y y) y))) 

((((λ (y) ((y y) y)) (λ (y) ((y y) y))) (λ (y) ((y y) y))) (λ (y) ((y y) y))) 
10. The number 2 is returned. The expression
(call/cc call/cc) 
is equivalent to
(call/cc (lambda (k) k)) 
and returns the current continuation. This is because the current continuation is passed to call/cc, which passes the current continuation to itself.
In this case, the current continuation of (call/cc call/cc) is
((((□ (lambda (x) (lambda (y) x))) 1) 2) 3) 
This continuation is then applied on (lambda (x) (lambda (y) x)) which results in a function (lambda (y) x) with an environment [x > (lambda (x) (lambda (y) x))] being applied on the numbers 1, 2 and 3 in that order.
11. An expression (let ([x 0]) (begin (or (set! x (+ x 1)) #f) x)) would evaluate to 2 instead of 1 because the first subexpression of an orform is evaluated for sideeffects twice. The second call to interp on e0 should be (interp e0 env sto) or (cons v0 sto1) and not (interp e0 env sto1).
12. The value is ((λ (b) a), [a > ((λ (c) c), ∅)]). That is, the lambda (λ (b) a) closed by an environment mapping free variable a to the lambda (λ (c) c) with no free variables and an empty environment.