CS 5510 Homework 7

Due: Thursday, October 27th, 2011 10:45am

Part 1 – More Arithmetic Operators

Start with fae-k.rkt and add two new arithmetic operators: neg and avg. The neg form takes a single number and returns its negation; the avg form takes three numbers and returns the average of the numbers.

  <FAE> = ....
        | {neg <FAE>}
        | {avg <FAE> <FAE> <FAE>}

As in recent previous homeworks, provide interp-expr, which takes an expression, interprets it with an empty substitution and empty continuation, and produces either a number or 'function.

  (test (interp-expr (parse '{neg 2}))
        -2)
  (test (interp-expr (parse '{avg 0 6 6}))
        4)

Part 2 – Restore withcc

Add withcc back to the interpreter:

  <FAE> = ....
        | {withcc <id> <FAE>}

Make interp-expr return 'function when the result is a continuation.

  (test (interp-expr (parse '{withcc k 7}))
        7)
  (test (interp-expr (parse '{withcc k k}))
        'function)
  (test (interp-expr (parse '{withcc k {neg {k 3}}}))
        3)

Part 3 – Functions that Accept Multiple Arguments, Again

Change your interpreter to support multiple or zero arguments to a function, and multiple or zero arguments in a function call:

  <FAE> = ....
        | {fun {<id>*} <FAE>}
        | {<FAE> <FAE>*}

Assume that each argument <id> is distinct for a fun expression. All continuations still accept a single argument (so supplying multiple arguments to a continuation triggers an error).

  (test (interp-expr (parse '{{fun {x y} {- y x}} 10 12}))
        2)
  (test (interp-expr (parse '{fun {} 12}))
        'function)
  (test (interp-expr (parse '{fun {x} {fun {} x}}))
        'function)
  (test (interp-expr (parse '{{{fun {x} {fun {} x}} 13}}))
        13)

  (test (interp-expr (parse '{withcc esc {{fun {x y} x} 1 {esc 3}}}))
        3)
  (test (interp-expr (parse '{{withcc esc {{fun {x y} {fun {z} {+ z y}}} 1 {withcc k {esc k}}}} 10}))
        20)

Part 4 – Extra Credit: Exceptions

This exercise is optional, for extra credit.

Extend your interpreter to support catching and throwing exceptions:

  <FAE> = ...
        | {try <FAE> catch <FAE>}
        | {throw}

The try ... catch form evaluates its first <FAE> and returns its value—unless evaluating the first <FAE> throws an exception by evaluating{throw}, in which case the result of the try expression is the result of the second <FAE>. Of course, catching the exception (and starting to evaluate the second <FAE>) means that the throw is not seen by any enclosing try. The result is undefined if throw is used without a dynamically enclosing catch.

  (test (interp-expr (parse '{try 7 catch 8}))
        7)
  (test (interp-expr (parse '{try {throw} catch 8}))
        8)
  (test (interp-expr (parse '{try {+ 1 {throw}} catch 8}))
        8)
  (test (interp-expr (parse '{{fun {f}
                                   {try {f} catch 8}}
                              {fun {} {throw}}}))
        8)

  (test (interp-expr (parse '{try {try {throw} catch 8} catch 9}))
        8)
  (test (interp-expr (parse '{try {try {throw} catch {throw}} catch 9}))
        9)
  (test (interp-expr (parse '{try {try 7 catch {throw}} catch 9}))
        7)

  (test (interp-expr (parse '{{withcc esc {try {{withcc k {esc k}}} catch {fun {x} 8}}}
                              {fun {} {throw}}}))
        8)

  (test (interp-expr (parse '{{withcc esc {try {{withcc k {try {esc k} 
                                                               catch {fun {} {fun {y} 9}}}}}
                                               catch {fun {x} 8}}}
                              {fun {} {throw}}}))
        8)

Hint: The currently active try ... catch is much like a dynamic binding.