4 Functions Interpreter

This assignment has you implement an extension to Paret to support lists and higher-order functions.

4.1 Data Definitions

You’ll be implementing an extended Paret with higher-order functions and lists. Its concrete syntax is:

Some examples of Paret programs are:

The abstract syntax of Paret is described by a few Pyret data definitions:

data Op:
  | op-plus
  | op-minus
  | op-times
  | op-divide
  | op-less
  | op-greater
  | op-equal
end

data UnOp:
  | op-first
  | op-rest
  | op-is-empty
end

data Expr:
  | e-num(n :: Number)
  | e-bool(b :: Boolean)
  | e-empty
  | e-link(first :: Expr, rest :: Expr)
  | e-unop(op :: UnOp, arg :: Expr)
  | e-op(op :: Op, left :: Expr, right :: Expr)
  | e-if(cond :: Expr, consq :: Expr, els :: Expr)
  | e-let(binds :: List<Bind>, body :: Expr)
  | e-lam(args :: List<String>, body :: Expr)
  | e-app(fun-expr :: Expr, arg-exprs :: List<Expr>)
  | e-id(x :: String)
end

data Bind:
  | bind(id :: String, expr :: Expr)
end

This is mostly maps one-to-one with the pieces of concrete syntax.

Paret programs can result in values or raise errors, which are described by two Pyret data structures:

data Error:
  | unbound-id
  | div-0
  | not-a-num
  | not-a-bool
  | not-a-fun
  | not-a-list
  | not-a-link
  | arity-mismatch
end


data Value:
  | v-num(n :: Number)
  | v-bool(b :: Boolean)
  | v-empty
  | v-link(first :: Value, rest :: Value%(is-v-list))
  | v-clos(env :: Env, args :: List<String>, body :: Expr)
end

Finally, your interpreter will be based on an environment, rather than substitution, so there is a definition for environments:

type Env = StringDict<Value>

4.2 Paret Semantics

You will define an evaluator for Paret with a single function:

fun interp(env :: Env, expr :: Expr) -> Value

The semantics of the expressions from original Paret are unchanged, though they should be implemented with an environment rather than substitution (as noted below). Your implementation should not have a subst function. The new forms are described here:

• e-empty evaluates to v-empty.

• e-link evaluates its arguments and produces a v-link of the values. It raises not-a-list if the rest value isn’t a v-link or v-empty.

• e-unop expressions evaluate their argument and raise not-a-list if it isn’t a v-link or v-empty. Then:

  • op-first raises not-a-link if the argument is v-empty, and returns the first field of a v-link.

  • op-rest raises not-a-link if the argument is v-empty, and returns the rest field of a v-link.

  • op-is-empty returns v-bool(true) if the argument is a v-empty, and v-bool(false) otherwise.

• e-lam expressions should evaluate to an appropriate v-clos.

• e-app expressions evaluate the function position to a value, and raise not-a-fun if it isn’t a v-clos. If the number of argument expressions doesn’t match the number of function arguments, raise arity-mismatch. Then, evaluate the arguments in left-to-right order, and evaluate the closure’s body in an appropriately-extended environment.

• e-let has the same observable eval behavior as in original Paret. It should use the environment, rather than substitution, however.

• e-id expressions evaluate to their binding in the current environment.

4.3 Logistics

You have been provided two files:

• fun-interp-impl.arr, which contains your implementation of Paret.

• fun-interp-tests.arr, which will hold your external tests for the evaluator.

The files are at:

Code: https://code.pyret.org/editor#share=0B32bNEogmncOZUFCTGh5eFpZWk0&v=v0.5r790

Tests: https://code.pyret.org/editor#share=0B32bNEogmncOVFRJMGduZ1ZqOVU&v=v0.5r790

Both files import the module fun-interp-defs.arr, which defines the data definitions and the helper function used by eval to parse strings to ASTs:

https://code.pyret.org/editor#share=0B32bNEogmncOMERfaE1VRTQ1M3M&v=v0.5r790

4.3.1 Using Modules

Here is the appropriate binding boilerplate for this assignment, if you prefer to use it:

type Error = I.Error
unbound-id = I.unbound-id
div-0 = I.div-0
not-a-num = I.not-a-num
not-a-bool = I.not-a-bool
not-a-fun = I.not-a-fun
not-a-link = I.not-a-link
not-a-list = I.not-a-list

type Op = I.Op
op-plus = I.op-plus
op-minus = I.op-minus
op-times = I.op-times
op-divide = I.op-divide
op-less = I.op-less
op-greater = I.op-greater
op-equal = I.op-equal

type UnOp = I.UnOp
op-is-empty = I.op-is-empty
op-first = I.op-first
op-rest = I.op-rest

type Expr = I.Expr
e-num = I.e-num
e-bool = I.e-bool
e-op = I.e-op
e-if = I.e-if
e-let = I.e-let
e-id = I.e-id
e-lam = I.e-lam
e-link = I.e-link
e-unop = I.e-unop

type Bind = I.Bind
bind = I.bind

type Value = I.Value
v-num = I.v-num
is-v-num = I.is-v-num
v-bool = I.v-bool
is-v-bool = I.is-v-bool
v-clos = I.v-clos
is-v-clos = I.is-v-clos
v-empty = I.v-empty
is-v-empty = I.is-v-empty
v-link = I.v-link
is-v-link = I.is-v-link

4.4 Testing and Submission Steps

By midnight Sunday (Feb 15), you should submit 5-10 of what you think are the most interesting tests to Captain Teach at the cs91-basic-interp link from:

https://www.captain-teach.org/swarthmore-cs091/assignments/

Submit a single Pyret file with your test cases filled into the check block in the template file. If you’re budgeting your time over the weekend, you shouldn’t need to spend more than about an hour playing with the interpreter to come up with some interesting cases.

By midnight Monday (Feb 16), you should submit any reviews you were assigned. You should feel free to complete the reviews at any time before then, and they will be assigned as submissions come in (so if multiple people submit on Saturday, reviewing can start then).

On Tuesday, a set of different implementations will be released, with instructions for adding an import line to access and test the different implementations.

Update: You can now include the interpreters for testing with:

import shared-gdrive("fun-interp-different-solutions.arr", "0B32bNEogmncOVktjbzBoRE9xb1E") as B

All of the interpreters can be found on B.bad-interps. Their names are:

dynamic-scope
reverse-arg-eval-order
no-arity-check
keep-old-bindings
mutable-env
reverse-arg-bind-order
rest-empty
rest-link-empty
is-empty-err
list-append

By midnight Thursday (Feb 19), you should submit a completed implementation of the interpreter, and a final test suite. Use the same submission link as above, but submit to the code step, which will unlock after you complete your reviews.

4.5 Asking for Help

You will get more efficient feedback from me if you ask your question in one of the following ways (setting up the question may even address your problem):

• "I don’t understand how to write a test for <some part of the concrete syntax>."

• "I don’t understand why this program has the output/raises the error it does: <some Paret program>."

• "I’m confused because my interpreter produces <some value or error> on <this program>, but the reference implementation produces <some other value or error>. I think it has to do with the case where <some description of case>."

You can ask anything you want, of course, but those kinds of questions tend to be the most effective.

4.6 Grading

Your grade will be in a few parts:

• 10% for submitting an interesting initial set of tests.

• 35% for the quality of your tests, based on the number of bad implementations they catch. As before, I reserve the right to grade based on additional bad implementations that I don’t release, so catching the ones that are out there does not guarantee a perfect testing score.

• 55% for the quality of your implementation, based on its correctness, clarity, and style.

Peer reviews will not factor into your grade, though you are free to copy tests from others that you see during review. Please don’t share tests with one another outside of what’s provided during test review.