CS 3520 Homework 7

Due: Friday, October 27th, 2023 11:59pm

Difficulty:  ★★★★

Start with let_cc2.rhm, which is like let_cc.rhm, but it changes the representation of function expressions, application expressions, and closure values to support a list of arguments—which is the boring work behind part 2 below. The parse function in let_cc2.rhm still matches only single-argument functions and applications, so you’ll have to change that when you’re ready to work on part 2.

Part 1 — More Arithmetic Operators

Add two new arithmetic operators: neg and avg. The neg form takes a single number and returns its negation; the avg form (which evaluates its subexpressions left-to-right) takes three numbers and returns the average of the numbers. Also, add if constrained to == 0 as usual.

  <Exp> = <Number>
        | <Symbol>
        | <Exp> + <Exp>
        | <Exp> * <Exp>
        | fun (<Symbol>): <Exp>
        | <Exp>(<Exp>)
        | let <Symbol> = <Exp>: <Exp>
        | (<Exp>)
        | neg(<Exp>)
        | avg(<Exp>, <Exp>, <Exp>)
        | if <Exp> == 0 | <Exp> | <Exp>

The if form has weakest precedence. The neg and avg forms have a precedence like function calls, but should be preferred by the parser over a function-call form, so they can be matched just before a function-call form in parse.

Implement neg and avg as core forms, instead of sugar. More generally, implement them without relying on the interpreter’s existing implementation of addition and multiplication (e.g., don’t generate an doPlusK continuation in the process of interpreting negation or averaging).

As in recent previous homeworks, provide interp_expr, which takes an expression, interprets it with an empty environment, and produces either a number syntax object or 'function'; return 'function' when the result is a closure or continuation.

  check: interp_expr(parse('neg(2)'))
         ~is '-2'
  check: interp_expr(parse('avg(0, 6, 6)'))
         ~is '4'
  check: interp_expr(parse('let_cc k: neg(k(3))'))
         ~is '3'
  check: interp_expr(parse('let_cc k: avg(0, k(3), 0)'))
         ~is '3'
  check: interp_expr(parse('let_cc k: avg(k(2), k(3), 0)'))
         ~is '2'
  check: interp_expr(parse('if 1 == 0 | 2 | 3'))
         ~is '3'
  check: interp_expr(parse('if 0 == 0 | 2 | 3'))
         ~is '2'
  check: interp_expr(parse('let_cc k: if k(9) == 0 | 2 | 3'))
         ~is '9'

The use of let_cc in the examples above just help check that you’re not breaking the rules of continuation-passing style, which is that interp and continue can call themselves and each other only via tail calls.

Part 2 — 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:

  <Exp> = <Number>
        | <Symbol>
        | <Exp> + <Exp>
        | <Exp> * <Exp>
        | fun (<Symbol>, ...): <Exp>
        | <Exp>(<Exp>, ...)
        | let <Symbol> = <Exp>: <Exp>
        | (<Exp>)
        | neg(<Exp>)
        | avg(<Exp>, <Exp>, <Exp>)
        | if <Exp> == 0 | <Exp> | <Exp>

Assume that each argument <Symbol> is distinct for a fun expression (i.e., your parser does not need to check). If the wrong number of arguments are provided, then a clear error message should be reported. Implement support for multiple arguments as part of the interpreter, not as sugar.

When a Moe program calls a continuation value (instead of a closure), the continuation value should still always take a single argument, and the interpreter should report a clear error if zero or multiple arguments are provided to a continuation.

  check: interp_expr(parse('(fun(x, y): y + neg(x))(10, 12)'))
         ~is '2'
  check: interp_expr(parse('fun (): 12'))
         ~is 'function'
  check: interp_expr(parse('fun (x): fun (): x'))
         ~is 'function'
  check: interp_expr(parse('(fun (x): fun (): x)(13)()'))
         ~is '13'

  check: interp_expr(parse('let_cc esc: (fun (x, y): x)(1, esc(3))'))
         ~is '3'
  check: interp_expr(parse('let f = (fun (x, y): fun (z): z + y):
                              (let_cc esc: f(1, let_cc k: esc(k)))(10)'))
         ~is '20'

  check: interp_expr(parse('(fun (x, y): 1)(1, 2, 3)'))
         // error because function is given too many arguments,
         // but the specific error message is not specified
         ~raises ""
  check: interp_expr(parse('let_cc esc: esc()'))
         // error because continuation is given 0 arguments
         ~raises ""
  check: interp_expr(parse('let_cc esc: esc(1, 2)'))
         // error because continuation is given 2 arguments
         ~raises ""

Part 3 — Faster Exceptions (extra credit)

This exercise as extra credit for CS 3520 and CS 6520 students.

Extend your interpreter to bring back try:

  <Exp> = ...
        | try: 
            <Exp>
            ~catch: <Exp>

When raising an exception for an erroneous expression, instead of searching the continuation for a tryK continuation, arrange for the interpreter to keep track of the current handler so that an exception is raised in constant time (no matter how long the continuation between the error and the enclosing try).