Sample Midterm 1

1. (lambda (x) (+ 1 2))
2. (lambda (x) (lambda (y) x))
3. (lambda (x) (lambda () x))
4. (lambda (x) (x))
5. (lambda (x) (x x x))
6. (lambda ((x)) x)
7. (lambda (x) (x x (x x)))
8. (lambda (x) (x x (lambda x x)))
9. ((lambda (x) (x x)) (lambda (x) (x x)))
10. (define omega = ((lambda (x) (x x)) (lambda (x) (x x))))
11. (define + 3)
12. (lambda (1) (+ 1 2))

1. (* blank 7) ; no need for a calculator
2. (* blank blank)
3. ((blank (blank)))
4. (blank ((lambda (x) (x x)) (lambda (x) (x x))))
5. ((lambda (blank) (blank blank)) blank)

(Use the Flang source at the end of the exam for this question.)

A useful utility for code that manipulates programs is a free-vars function: given an expression in AST form, it returns a list of names that appear free in it. This is a useful function because it can be used to implement other useful tools like asking whether an identifier is free in an expression, determining whether an expression is closed (has no free identifiers) or not, etc; and these tools are useful in various tasks from detecting errors to program optimization.

Given the type definition for the Flang abstract syntax tree, write this free-vars function. It should consume a FLANG expression value and return a list of free identifiers that it contains. The order of names in the resulting list and possible repetitions do not matter — so tests for this function should use set equality:

(Use the Flang source here too.)

As we have seen, the semantics of call, like the semantics of with, are eager: the argument is evaluated before the substitution happens. We want to extend the language with a lazy-call expression that is similar to call except that it is lazy. To do this, we begin by extending the BNF, the FLANG type definition, and adapting the parser. The new BNF entry and variant are:

1. The formal substitution rule for lazy-call,
2. A case for LCall in subst,
3. The formal evaluation rule for lazy-call,
4. A case for LCall in eval.

1. Write a proper test case for the new lazy-call expression from the previous question. The test case should demonstrate that the new call is indeed lazy.
2. Are the lazy-call evaluation rule and code fragment in the previous question completely lazy? Explain (briefly).
3. If your evaluation of lazy-call is correct, it uses subst with an expression rather than a value. Why is it still fine to evaluate

   {with {x 1} {lazy-call {fun {y} {with {x 2} y}} x}}

   when it looks like it might lead to name capture?
4. In Assignment #3 we implemented the boolean constants True and False in the parser:

   (define (parse-sexpr sexpr) (match sexpr ... ;; the constants must precede the Id case ['True (Bool #t)] ['False (Bool #f)] ...))

   In an environment-based evaluator, we could simplify the parser: parse them as identifiers, then start the evaluation with an initial environment that has bindings for the two identifiers. This will, however, change the semantics of the language. Write an expression that demonstrates the change. (Hint: you can see the same change in Scheme, when you use #t and #f, vs using true and false.)
5. When we wrote the typed definition of the fixed-point combinator, we had a Tau type defined for x:

   (: make-recursive : (All (S T) (((S -> T) -> (S -> T)) -> (S -> T)))) (define (make-recursive f) (define-type (Tau S T) = (Rec this (this -> (S -> T)))) ((lambda: ([x : (Tau S T)]) (f (lambda: ([z : S]) ((x x) z)))) (lambda: ([x : (Tau S T)]) (f (lambda: ([z : S]) ((x x) z))))))

   Is this definition really needed? Explain why (briefly!) or show how it can be written without the definition.

The following is the Flang implementation that uses substitution. Use it as a reference for related questions.

This is for reference only, tear this part off, do not hand it in it with the rest of the exam. Do not write solutions on these pages.

#lang pl

#|
The grammar:
  <FLANG> ::= <num>
            | { + <FLANG> <FLANG> }
            | { - <FLANG> <FLANG> }
            | { * <FLANG> <FLANG> }
            | { / <FLANG> <FLANG> }
            | { with { <id> <FLANG> } <FLANG> }
            | <id>
            | { fun { <id> } <FLANG> }
            | { call <FLANG> <FLANG> }

Evaluation rules:

  subst:
    N[v/x]                = N
    {+ E1 E2}[v/x]        = {+ E1[v/x] E2[v/x]}
    {- E1 E2}[v/x]        = {- E1[v/x] E2[v/x]}
    {* E1 E2}[v/x]        = {* E1[v/x] E2[v/x]}
    {/ E1 E2}[v/x]        = {/ E1[v/x] E2[v/x]}
    y[v/x]                = y
    x[v/x]                = v
    {with {y E1} E2}[v/x] = {with {y E1[v/x]} E2[v/x]} ; if y =/= x
    {with {x E1} E2}[v/x] = {with {x E1[v/x]} E2}
    {call E1 E2}[v/x]     = {call E1[v/x] E2[v/x]}
    {fun {y} E}[v/x]      = {fun {y} E[v/x]}           ; if y =/= x
    {fun {x} E}[v/x]      = {fun {x} E}

  eval:
    eval(N)            = N
    eval({+ E1 E2})    = eval(E1) + eval(E2)  \ if both E1 and E2
    eval({- E1 E2})    = eval(E1) - eval(E2)   \ evaluate to numbers
    eval({* E1 E2})    = eval(E1) * eval(E2)   / otherwise error!
    eval({/ E1 E2})    = eval(E1) / eval(E2)  /
    eval(id)           = error!
    eval({with {x E1} E2}) = eval(E2[eval(E1)/x])
    eval(FUN)          = FUN ; assuming FUN is a function expression
    eval({call E1 E2}) = eval(Ef[eval(E2)/x]) if eval(E1)={fun {x} Ef}
                       = error!               otherwise
|#

(define-type FLANG
  [Num  (n Number)]
  [Add  (lhs FLANG) (rhs FLANG)]
  [Sub  (lhs FLANG) (rhs FLANG)]
  [Mul  (lhs FLANG) (rhs FLANG)]
  [Div  (lhs FLANG) (rhs FLANG)]
  [Id   (name Symbol)]
  [With (name Symbol) (named FLANG) (body FLANG)]
  [Fun  (name Symbol) (body FLANG)]
  [Call (fun-expr FLANG) (arg-expr FLANG)])

(: parse-sexpr : Sexpr -> FLANG)
;; to convert s-expressions into FLANGs
(define (parse-sexpr sexpr)
  [...])

(: parse : String -> FLANG)
;; parses a string containing a FLANG expression to a FLANG AST
(define (parse str)
  [...])

(: subst : FLANG Symbol FLANG -> FLANG)
;; substitutes the second argument with the third argument in the
;; first argument, as per the rules of substitution; the resulting
;; expression contains no free instances of the second argument
(define (subst expr from to)
  (cases expr
    [(Num n) expr]
    [(Add l r) (Add (subst l from to) (subst r from to))]
    [(Sub l r) (Sub (subst l from to) (subst r from to))]
    [(Mul l r) (Mul (subst l from to) (subst r from to))]
    [(Div l r) (Div (subst l from to) (subst r from to))]
    [(Id name) (if (eq? name from) to expr)]
    [(With bound-id named-expr bound-body)
     (With bound-id
           (subst named-expr from to)
           (if (eq? bound-id from)
             bound-body
             (subst bound-body from to)))]
    [(Call l r) (Call (subst l from to) (subst r from to))]
    [(Fun bound-id bound-body)
     (if (eq? bound-id from)
       expr
       (Fun bound-id (subst bound-body from to)))]))

(: arith-op : (Number Number -> Number) FLANG FLANG -> FLANG)
;; gets a Scheme numeric binary operator, and uses it within a FLANG
;; ‘Num’ wrapper
(define (arith-op op expr1 expr2)
  (: Num->number : FLANG -> Number)
  (define (Num->number e)
    (cases e
      [(Num n) n]
      [else (error ’arith-op "expects a number, got: ~s" e)]))
  (Num (op (Num->number expr1) (Num->number expr2))))

(: eval : FLANG -> FLANG)
;; evaluates FLANG expressions by reducing them to *expressions*
(define (eval expr)
  (cases expr
    [(Num n) expr]
    [(Add l r) (arith-op + (eval l) (eval r))]
    [(Sub l r) (arith-op - (eval l) (eval r))]
    [(Mul l r) (arith-op * (eval l) (eval r))]
    [(Div l r) (arith-op / (eval l) (eval r))]
    [(With bound-id named-expr bound-body)
     (eval (subst bound-body
                  bound-id
                  (eval named-expr)))]
    [(Id name) (error ’eval "free identifier: ~s" name)]
    [(Fun bound-id bound-body) expr]
    [(Call fun-expr arg-expr)
     (let ([fval (eval fun-expr)])
       (cases fval
         [(Fun bound-id bound-body)
          (eval (subst bound-body
                       bound-id
                       (eval arg-expr)))]
         [else (error ’eval "‘call’ expects a function, got: ~s"
                            fval)]))]))

(: run : String -> Number)
;; evaluate a FLANG program contained in a string
(define (run str)
  (let ([result (eval (parse str))])
    (cases result
      [(Num n) n]
      [else (error ’run
                   "evaluation returned a non-number: ~s" result)])))