Sample Midterm 3

We can use a mapping function to specify an arbitrary graph — the function will consume a node name and return a list of node names that are reachable from it: A -> (Listof A). Note that this is using A, to keep the actual type of node names abstract (for example, one graph might use numbers as labels, and another can use symbols). Using this representation, you need to write a find-path function that looks for a path between two given nodes:

Write the function, implementing a simple recursive depth-first search (that is, no need for fancy improvements like breadth-first search) that looks for a path. If such a path exists, the result will be a list whose first element is from and whose last element is last. If no such path exists, then the result should be #f.

To test this function, it is best if we have a function that consumes a list of node specifications, each a list of a node name and the nodes you can reach from it, and returns a mapping function:

To avoid getting stuck in a loop, you need to make sure that you don’t go to a node that you’ve already visited. Luckily, you need to collect the nodes that you visit anyway (to return as a result), so it is natural to write a solution that will use an extra argument to collect the path, and use it to avoid loops (hint: use member). Using this, the find-path function itself would be a one-liner (it will also need to use reverse). Make your helper function look like:

Reminder: make sure that you write a correct type for both functions, and a clear purpose statement for find-path.

1. (+ blank (length blank))
2. ((blank "660"))
3. ((blank blank) (blank blank))
4. (or (not blank) blank)
5. (let ([blink blank]) (blank blink))

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

Write an unparse function for the FLANG abstract syntax tree. You basically need to write a simple recursive function that will convert a given input expression into a string form that would parse to an equal expression AST. A convenient tool to create the strings is the format function. Here are some examples of using it to render a symbol and a number to a string, and an example that glues together several pieces:

When you write your unparser, you will see that the cases for the arithmetic operators and for call are all very similar. This means that you should define a small internal helper function that will help constructing the resulting string.

Here is a utility function for testing, and a few tests:

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

For some obscure reason, it turns out that performing multiplications is horrendously slow, and clients who use your FLANG implementations are complaining. In an attempt to make things run faster, we can modify the way that the interpreter evaluates Mul expressions: we can do the following:

• if the first value is equal to (NumV 0), return it
• if its equal to (NumV 1), return the second value as is
• and finally the same goes for the second value.

Your job is to implement this smart-mul function so it will do the above. Important: make sure you use cases to inspect the two values.

It turns out that your clients are so much happier with the optimized FLANG interpreter that you implemented in the previous question, that your friend decides to write such a function in for himself, to use in his Scheme code. He writes this:

When you see this code in the weekly code reviews, you notice that this function is not the same as the multiplication function. Explain why. Your explanation should be simple: an expression that demonstrates a case where (fast-mul m n) is not going to return the same result as (* m n).

Also, explain how using Typed Scheme avoided an even more dangerous change in semantics of this multiplication function. For this, you need to show a worse kind of a mistake that could result if we hadn’t used typed scheme.
Note: this part of the question can be very difficult, don’t get stuck on it if you don’t know the answer.

In class, we have seen how the Lambda Calculus (or Schlac, in our case) can be used to encode values of various types as functions. One thing that we’ve seen is that certain functions can be viewed as an encoding of values of different types. For example,

1. 1 (a number) is also the identity function (an A -> A function),
2. #f (a boolean) is also 0 (a number),
3. 2 (a number) is also a square operation (a Number -> Number function), and in fact, any encoded number n is a xⁿ operation when used as a Number -> Number function.

There are many more functions that can be viewed as doing different things for different types. For example, consider or, defined as:

Show what or does when viewed as a binary numeric function, Number Number -> Number. Your explanation should be formal, similar to the above.

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.

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