Sample Midterm 1

• The ellipsis notation makes BNFs more expressive, for example, here is a language using ellipsis that cannot be expressed without it. (If you think that this is the right answer, you need exactly one example, no additional examples, and no verbal explanations are necessary.)
• The ellipsis notation does not make BNFs more expressive. Here is an exact description for taking a BNF that uses ellipsis, and converting it to one that does not have them. (If you think that this is the solution, then it's enough to assume a BNF that has exactly one use of ellipsis and show how to eliminate it.)

1. (/ (blank) 0)
2. (blank (/ 1 0))
3. (car (map (blank) (list (blank))))
4. (and (blank) blank 'blank)
5. (let ([blank +]) (blank (blank))) ; careful!

1. First, you need to write a find-immediate-application function that consumes a FLANG value, looks for such an application expression, and returns the first one it finds. (Reminder: the Flang implementation is attached to the end of the exam for reference.)
2. The next step is to perform the inlining of such an expression. Implement an inline-application function that performs that inlining. Note that this part works on a single application, one that was found by the previous function. To simplify this part, you can assume that you have the subst function from the substitution-based Flang implementation, the one that has this signature:

   ;; 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 ...))

3. The last step is to combine these two together, basically running a loop that finds an immediate application and inlines it, and continues while such expressions still exist in the code. As mentioned above, you do not need to implement this code.

1. The alternative implementation of the recursive rec binder in the previous question has certain advantages and disadvantages. Mention at least one of each. (Be brief, and don't write “just in case” text — wrong and/or redundant arguments will be penalized.)
   
   
   
   
   
2. In the question where you inlined immediate application forms there are two serious problems. A hint for the first problem (which can itself have two bad outcomes in such code) is in this expression:

   {call {fun {x} {* x 2}} {/ y 3}}

   Describe this problem.
   
   
   
   
   
3. The second problem in this inlining has a hint in this monster code, which is the result of manually inlining immediate applications:

   (define foo((lambda(f)((lambda(x)(x x))(lambda(x)(f(x x)))))(lambda(f )(lambda(x)(((x(lambda(x)(lambda(x y) y))(lambda(x y)x))(x(lambda(x)( ...)))))))))

   To see the hint, look for an un-inlined immediate application, and that should lead you to the problem.
   
   
   
   
   
4. Suggest a solution to the first problem (hint: with), which will solve the second one too. (Note: this one can be difficult.)
   
   
   
   
   

The following is the Flang implementation that uses environments. 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.

(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 an 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)])))