CS 6510 Homework 6

Due: Tuesday, February 28th, 2017 11:59pm

Start with abort.rkt, which is like lambda-k.rkt, but adds an {abort} form that discards the current continuation and immediately returns 0. In addition, abort.rkt 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 abort.rkt 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 if0 as usual.

  <Expr> = <Num>
         | <Sym>
         | {+ <Expr> <Expr>}
         | {* <Expr> <Expr>}
         | {lambda {<Sym>} <Expr>}
         | {<Expr> <Expr>}
         | {abort}
         | {neg <Expr>}
         | {avg <Expr> <Expr> <Expr>}
         | {if0 <Expr> <Expr> <Expr>}

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 doAddK 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 substitution, and produces either a number S-expression or `function; return `function when the result is a closure.

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

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:

  <Expr> = <Num>
         | <Sym>
         | {+ <Expr> <Expr>}
         | {* <Expr> <Expr>}
         | {lambda {<Sym>*} <Expr>}
         | {<Expr> <Expr>*}
         | {abort}
         | {neg <Expr>}
         | {avg <Expr> <Expr> <Expr>}
         | {if0 <Expr> <Expr> <Expr>}

Assume that each argument <Sym> is distinct for a lambda expression.

  (test (interp-expr (parse '{{lambda {x y} {+ y {neg x}}} 10 12}))
        '2)
  (test (interp-expr (parse '{lambda {} 12}))
        `function)
  (test (interp-expr (parse '{lambda {x} {lambda {} x}}))
        `function)
  (test (interp-expr (parse '{{{lambda {x} {lambda {} x}} 13}}))
        '13)

  (test (interp-expr (parse '{{lambda {x y} x} 1 {abort}}))
        '0)