Assignment 4: Let and fun

Objectives:

• Become comfortable with the basic scope, local binding, and programming with local functions.

Resources:

• The Plait tutorial and documentation page: https://docs.racket-lang.org/plait/

Parameters:

• Due date: Friday Feb. 9 at 11:59PM
• Upload your solution as a code.rkt file on Gradescope.
• Ask questions on Piazza or during Office Hours.
• Use the following starter code
• Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code.
• Grading read carefully: each problem is worth a certain number of points. The points given for each problem is the fraction of tests passed for that problem (i.e., if 50% of the tests are passed for a 20 point problem, 10 points are given). Update: Your grade will be determined solely by the public autograder score on this assignment.

Problem 1: Scope? Nope!

Consider the following let language from class:

(define-type Exp
  [numE (n : Number)]
  [plusE (l : Exp) (r : Exp)]
  [varE (s : Symbol)]
  [let1E (var : Symbol)
         (assignment : Exp)
         (body : Exp)])

(define (subst id assignment body)
  (type-case Exp body
    [(numE n) (numE n)]
    [(plusE l r) (plusE (subst id assignment l) (subst id assignment r))]
    [(varE s) (if (symbol=? s id) (numE assignment) (varE s))]
    [(let1E innervar innerassignment innerbody)
     (let1E innervar (subst id assignment innerassignment)
            ; check for shadowing
            ; if id is being shadowed, then return inner body
            ; else, substitute inner body
            (if (symbol=? innervar id)
                innerbody
                (subst id assignment innerbody))
            )]))

(define (eval e)
  (type-case Exp e
    [(numE n) n]
    [(plusE l r) (+ (eval l) (eval r))]
    [(varE s) (error 'runtime "uninitialized")]
    [(let1E id assignment body)
       ;Semantics of (let1E var assignment body):
       ;(1) evaluate assignment to value
       ;(2) substitute `var` with value in body
       ;(3) evaluate body
     (eval (subst id (eval assignment) body))
     ]))

Include in your submission two components:

Problem 1a. Define two functions: broken-subst and broken-eval. broken-eval is identical to eval except
broken-subst is used in place of subst. broken-subst, unlike subst, causes the following tests to pass:

(test (broken-eval (let1E 'x (numE 10)
         (let1E 'x (numE 20) (varE 'x)))) 10)

(test (broken-eval (let1E 'x (numE 20)
         (let1E 'x (plusE (varE 'x) (numE 5)) (varE 'x)))) 20)

Problem 1b. Using your eval and broken-eval, define two Exps:

• An Exp named unaffected that evaluates to the same value, when evaluated using both eval and broken-eval, and
• An Exp named affected that evaluates to different values.

Use test to make sure that unaffected and affected exhibit the correct behavior. You are not allowed to use any of the test cases defined above.

Problem 2: Uniquify

You are tired of dealing with shadowing, so you’ve decided to implement a function called uniquify that, when given an abstract syntax tree for the let language, renames all shadowed variables to unique names. This way, you can tell a variable’s scope just by looking for its unique binding in the program!

You run into a challenge almost immediately: even if we generate unique names, we need a way to replace the existing name in your abstract syntax tree with your newly generated unique one. Notice how our current subst function does not do that yet.

Problem 2a. Write function update-names such that, (update-names e id id2) replaces all instances variables with name id in e with the name id2. You can assume that id2 will never appear in e.

Example behavior:

(test (update-names 
  (let1E 'x (numE 10)(varE 'x)) 'x 'y) 
  (let1E 'y (numE 10) (varE 'y)))

(test (update-names
  (let1E 'x (varE 'x) (let1E 'x (numE 10) (varE 'x))) 'x 'y)
  (let1E 'y (varE 'y) (let1E 'y (numE 10) (varE 'y))))

Problem 2b. Implement uniquify using update-names. Your solution should additionally use the following fresh-name! function, which you can assume is guaranteed to produce a unique name whenever it is called (don’t worry about understanding how it works; we will cover mutation later):

(define counter (box "###"))
(define (fresh-name!)
  (string->symbol (begin
    (set-box! counter (string-appnd "a" (unbox counter)))
    (unbox counter))))

Try calling fresh-name! a few times and see how it behaves.

If we assume variables can’t be shadowed, we can simplify our let evaluator to remove the check for shadowing inside subst:

(define (subst-uniq id assignment body)
  (type-case Exp body
    [(numE n) (numE n)]
    [(plusE l r) (plusE (subst-uniq id assignment l) (subst-uniq id assignment r))]
    [(varE s) (if (symbol=? s id) (numE assignment) (varE s))]
    [(let1E innervar innerassignment innerbody)
     (let1E innervar (subst-uniq id assignment innerassignment)
                (subst-uniq id assignment innerbody))
            ]))

(define (eval-uniq e)
  (type-case Exp e
    [(numE n) n]
    [(plusE l r) (+ (eval-uniq l) (eval-uniq r))]
    [(varE s) (error 'runtime "uninitialized")]
    [(let1E id assignment body)
     (eval-uniq (subst-uniq id (eval-uniq assignment) body))
     ]))

Example behavior:

(test
  (eval-uniq (uniquify
    (let1E 'x (numE 10)
    (let1E 'x (numE 20)
    (varE 'x)))
  ))
  20)

Hint: Your solution will likely require a helper function that maintains an environment, like we’ve seen in lecture. You can make use of any features of Plait in your solution. You may find the list member function useful (see the Plait documentation here)

Problem 3: Lambda the ultimate boolean

Recall from lecture our untyped λ-calculus:

(define-type LExp
  [var (s : Symbol)]
  [lam (x : Symbol) (body : LExp)]
  [app (e : LExp) (arg : LExp)])

(define-type Value
  [fun (arg : Symbol) (body : LExp)])

; retrieve argument name from a function
(define (get-arg v)
  (type-case Value v
    [(fun arg body) arg]))

; retrieve function body from a function
(define (get-body v)
  (type-case Value v
    [(fun arg body) body]))

; perform e1[x |-> e2]
(lam-subst : (LExp Symbol LExp -> LExp))
(define (lam-subst e1 x e2)
  (type-case LExp e1
    [(var s) (if (symbol=? s x) e2 (var s))]
    [(lam id body) (if (symbol=? x id) (lam id body) (lam id (lam-subst body x e2)))]
    [(app e1App e2App) (app (lam-subst e1App x e2) (lam-subst e2App x e2))]))

; runs a λ-calculus expression
(define (interp e)
  (type-case LExp e
    [(var s) (error 'runtime "unbound symbol")]
    [(lam id body) (fun id body)]
    [(app e1 e2)
     ; run e1 to get (lambda (id) body)
     ; run e2 to get a value argV
     ; run body[id |-> v]
     (letrec [(e1V (interp e1))
              (body (get-body e1V))
              (id (get-arg e1V))
              (argV (interp e2))]
       (interp (lam-subst body id (lam (get-arg argV) (get-body argV)))))]))

And consider the below subset of the IteExp language we discussed as well:

(define-type BExp
  [boolE (b : Boolean)]
  [iteE (guard : BExp) (thn : BExp) (els : BExp)])

In this problem we will Church encode expressions of type BExp. Church encodings are representations of data types (like Booleans) and their manipulation (like if-then-else) into pure functions in the λ-calculus. Such encodings have been used for a long time as both mathematical objects of study and also foundations for compilers for real languages, namely Lisp.

Problem 3. Define a function church-encode of type (BExp -> LExp) that returns the Church encoding of an arbitrary BExp. To help you out, recall the Church encodings of #t and #f we reviewed in class:

(church-encode (boolE #t)) ---> (lam 'x (lam 'y (var 'x)))
(church-encode (boolE #f)) ---> (lam 'x (lam 'y (var 'y)))

One way to tackle the last case is to consider how Booleans work functionally in our language. In BExp, Booleans are used by if-then-else expressions:

(iteE (boolE #t) (boolE #t) (boolE #f)) should evaluate to (boolE #t),
(iteE (boolE #f) (boolE #t) (boolE #f)) should evaluate to (boolE #f).

In the λ-calculus, there is no notion of if-then-else, so we must resort to using our Booleans as functions.