On this page:
4.1 Data Definitions
4.2 Paret Semantics
4.3 Logistics
4.3.1 Using Modules
4.4 Testing and Submission Steps
4.5 Asking for Help
4.6 Grading
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:

exp := (<op> <exp> <exp>)

    |  (let ((<id> <exp>) ...) <exp>) [where <id>'s are all different]

    |  (if <exp> <exp> <exp>)

    |  true

    |  false

    |  <number>

 

    # For creating functions

    |  (lam (<id> ...) <exp>) [where <id>'s are all different]

    # For calling functions

    |  (<exp> <exp> ...)

 

    # For lists

    |  (<unop> <exp>)

    |  (link <exp> <exp>)

    |  empty

 

 

op   := + | - | * | / | < | > | ==

unop := first | rest | is-empty

id   := any symbol other than an op or unop,

        or true, false, let, if, lam, link, empty

Some examples of Paret programs are:

((lam (n) (lam (m) (< n m))) 5)

 

(link 5 empty)

 

empty

 

(first (link 5 empty))

 

(rest (link 5 (link 6 (link 7 empty))))

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:

4.3 Logistics

You have been provided two files:

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):

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:

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.