Sample Midterm 2

• You can ignore white spaces (as usual)
• You can use ‘...’ as usual, but it won’t make it shorter
• You cannot assume that something like <int> is known — you must specify the grammar completely
• Integers are actually plain natural numbers (decimal, no sign)
• You do, however, need to make sure that numbers do not begin with redundant leading zeros, for example 120 and 0 are valid, but 0120 and 00 are not.

1. (blank (random 1000)) ; random does the usual
2. (blank + 60)
3. (blank blank) ; easy, but write a type too
4. (or ’blank (blank))
5. (let ([blank 330]) blank)

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

We wish to extend the Flang language with two-argument (binary) functions. We begin by extending the BNF with two new rules for binary functions and binary function applications:

Begin by extending the formal evaluation rules with cases for the two new kinds of expressions fun2 and call2. You need to write only these two rules, since the rest of the rules are not modified. Complete the question with the extended eval function — again, you need only the two new cases branches for Fun2 and Call2 because the rest of the code is the same.

Important: this question is hard, don’t get stuck on it before you finish the rest of the exam. Note that all answers should be quite short.

1. Consider the above two implementations of fun2 and call2. The two implementations result in a different semantics for these expressions. Find an expression that can reveal the difference, by evaluating differently based on which implementation is used.
2. The difference between the two binary function extensions is pointing at a trade-off: each implementation can claim a feature that the other lacks. Find such a feature for each side.
3. In the first implementation of the binary functions it was important to assume that the two argument names are different. Explain why this assumption is important in that implementation, and what you can gain by removing the assumption from the second one.
4. In a language implementation like the attached Flang code, do we really need a garbage collector? Explain.
5. What if we were to change this implementation to use dynamic scope? — Would we need a garbage collector then? (Note: this is a hard question!)

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

Please 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:
  eval(N,env)                = N
  eval({+ E1 E2},env)        = eval(E1,env) + eval(E2,env)
  eval({- E1 E2},env)        = eval(E1,env) - eval(E2,env)
  eval({* E1 E2},env)        = eval(E1,env) * eval(E2,env)
  eval({/ E1 E2},env)        = eval(E1,env) / eval(E2,env)
  eval(x,env)                = lookup(x,env)
  eval({with {x E1} E2},env) = eval(E2,extend(x,eval(E1,env),env))
  eval({fun {x} E},env)      = <{fun {x} E},env>
  eval({call E1 E2},env1)
           = eval(Ef,extend(x,eval(E2,env1),env2))
                             if eval(E1,env1)=<{fun {x} Ef},env2>
           = 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)
  (match sexpr
    [(number: n)    (Num n)]
    [(symbol: name) (Id name)]
    [(cons ’with more)
     (match sexpr
       [(list ’with (list (symbol: name) named) body)
        (With name (parse-sexpr named) (parse-sexpr body))]
       [else (error ’parse-sexpr "bad ‘with’ syntax in ~s" sexpr)])]
    [(cons ’fun more)
     (match sexpr
       [(list ’fun (list (symbol: name)) body)
        (Fun name (parse-sexpr body))]
       [else (error ’parse-sexpr "bad ‘fun’ syntax in ~s" sexpr)])]
    [(list ’+ lhs rhs) (Add (parse-sexpr lhs) (parse-sexpr rhs))]
    [(list ’- lhs rhs) (Sub (parse-sexpr lhs) (parse-sexpr rhs))]
    [(list ’* lhs rhs) (Mul (parse-sexpr lhs) (parse-sexpr rhs))]
    [(list ’/ lhs rhs) (Div (parse-sexpr lhs) (parse-sexpr rhs))]
    [(list ’call fun arg) (Call (parse-sexpr fun) (parse-sexpr arg))]
    [else (error ’parse-sexpr "bad syntax in ~s" sexpr)]))

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

;; Types for environments, values, and a lookup function

(define-type ENV
  [EmptyEnv]
  [Extend (id Symbol) (v VAL) (rest-env ENV)])

(define-type VAL
  [NumV (n Number)]
  [FunV (name Symbol) (body FLANG) (env ENV)])

(: lookup : Symbol ENV -> VAL)
(define (lookup name env)
  (cases env
    [(EmptyEnv) (error ’lookup "no binding for ~s" name)]
    [(Extend id val rest-env)
     (if (eq? id name) val (lookup name rest-env))]))

(: arith-op : (Number Number -> Number) VAL VAL -> VAL)
;; gets a Scheme numeric binary operator, and uses it within a NumV
;; wrapper
(define (arith-op op val1 val2)
  (: NumV->number : VAL -> Number)
  (define (NumV->number v)
    (cases v
      [(NumV n) n]
      [else (error ’arith-op "expects a number, got: ~s" v)]))
  (NumV (op (NumV->number val1) (NumV->number val2))))

(: eval : FLANG ENV -> VAL)
;; evaluates FLANG expressions by reducing them to values
(define (eval expr env)
  (cases expr
    [(Num n) (NumV n)]
    [(Add l r) (arith-op + (eval l env) (eval r env))]
    [(Sub l r) (arith-op - (eval l env) (eval r env))]
    [(Mul l r) (arith-op * (eval l env) (eval r env))]
    [(Div l r) (arith-op / (eval l env) (eval r env))]
    [(With bound-id named-expr bound-body)
     (eval bound-body
           (Extend bound-id (eval named-expr env) env))]
    [(Id name) (lookup name env)]
    [(Fun bound-id bound-body)
     (FunV bound-id bound-body env)]
    [(Call fun-expr arg-expr)
     (let ([fval (eval fun-expr env)])
       (cases fval
         [(FunV bound-id bound-body f-env)
          (eval bound-body
                (Extend bound-id (eval arg-expr env) f-env))]
         [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) (EmptyEnv))])
    (cases result
      [(NumV n) n]
      [else (error ’run
                   "evaluation returned a non-number: ~s" result)])))