Midterm guidelines and practice questions

6.10

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 big-step CE and CES semantics or the small-step CEK semantics from the slides, but you should understand how these semantics work conceptually as well as closure creation, store-passing, and stack-passing 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 stack-passing or store-passing translation.
You should understand alpha-conversion, beta-reduction, eta-reduction/expansion, capture-avoiding substitution, and the concept of free/bound variables. You should be able to evaluate programs step-by-step in the lambda-calculus using the call-by-value context-and-redex style of semantics.
You should understand the Scheme semantics for lambdas/closures, call/cc, first-class 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)

(* n (fact (- n 1)))))

Write a tail-recursive version. (Need not be stack-passing, you can use an integer accumulator.)

2. What can the following scheme-exp? expression translate to in terms of the ir-exp? 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)

(+ (fib (- n 1)) (fib (- n 2)))))

Perform a stack-passing transformation of fib to produce a tail-recursive 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 (call-by-value) context-and-redex semantics. Show both the evaluation context and redex at each step.

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

5. The function 3n1-steps 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 (3n1-steps 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)

(loop v)))))

Write a semantically equivalent function without using mutation (set!). Do not inline the function next, but manually perform a store-passing/value-passing style of transformation.

6. Write a church-encoding 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 alpha-renaming) 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 call-by-value (eager) order of evaluation and call-by-name (lazy) order of evaluation.

9. Show three steps in the evaluation of the following term using a (call-by-value) context-and-redex 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 store-passing interpreter—with a bug in it.

(define (interp e env sto)

(match e

; ...

[`(and ,e0 ,e1)

(match-define (cons v0 sto1) (interp e0 env sto))

(if v0

(interp e1 env sto1)

(cons #f sto1))]

[`(or ,e0 ,e1)

(match-define (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 closure-creating 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)

(tfact (- n 1) (* v n))))

(tfact n 1))

and

(define (fact n)

(let loop ([n n][v 1])

(if (= n 0)

(loop (- n 1) (* n v)))))

In fact, Racket compiles these exactly the same way as both desugar to a letrec form defining a single tail-recursive function.

2. Either

(let loop () (loop))

(letrec* ([loop (lambda () (loop))])

(loop))

(let ([loop '()])

(let ([_ (set! loop (lambda () (loop)))])

(loop)))

(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 n-2 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

[`(n-2 ,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) `(n-2 ,(- 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 let-values and values instead of match-let and cons. You might also assume it’s a cons cell and use car and cdr directly.

(define (3n1-steps-pure 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])

(match-let ([(cons v c) (next n c)])

(if (= v 1)

(loop v c)))))

6. A valid encoding would be:

(((λ (t) (λ (f) (t t)))

(λ (_) (λ (g) (λ (x) x))))

(λ (_) (λ (a) (λ (b) a))))

where this breaks down into

((boolean-true

(λ (_) nat-zero))

(λ (_) curried-lambda))

boolean-true: (λ (t) (λ (f) (t t)))

nat-zero: (λ (g) (λ (x) x))

curried-lambda: (λ (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 call-by-value evaluation, argument expressions are evaluated to a value before being passed to the applied function. In call-by-name (lazy) evaluation, arguments are passed as a suspended computation (like a promise), to be evaluated when needed.
In a textual reduction (term rewriting) semantics, call-by-value requires argument expressions to be evaluated to a value (lambda) before being substituted into the applied function. In a call-by-name (lazy) semantics, an application expression in argument position may be substituted into the body of a lambda to be evaluated later.
In a call-by-value CE (control-expression and environment) semantics, substitution environments accumulate a mapping from variables to pairs of a lambda-expression and environment. In a call-by-name 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 or-form is evaluated for side-effects 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.