►Introduction to Programming Languages
►Labs and Assignments
▼Labs
►6 State Interpreter
On this page:
6.1 Data Definitions
6.2 Paret Semantics
6.2.1 Testing Multiple Representations
6.2.2 New and Updated Semantics
6.3 Logistics
6.3.1 Using Modules
6.4 Testing and Submission Steps
6.5 Grading
    ← prev  up  next → 
6 State Interpreter

This assignment has you implement an extension to Paret to support state. At the end of this assignment, you will have more or less implemented Lisp (http://en.wikipedia.org/wiki/Lisp_%28programming_language%29). Paret has immutable lists instead of mutable pairs, a slightly different syntax, and doesn’t implement a few desugarings, but those are mostly minor details.

6.1 Data Definitions

You’ll be implementing an extended Paret with variables.

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

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

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

    |  true

    |  false

    |  <number>

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

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

    |  (<unop> <exp>)

    |  (link <exp> <exp>)

    |  empty

 

    # for variables

    | (set-var <id> <exp>)

 

    # for convenience

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

 

 

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

unop := first | rest | is-empty

id   := any symbol

Some examples of Paret programs are:

(let ((x 0))

  (let ((x2 x))

    (block

      (set-var x2 5)

      (+ x x2))))

 

(let ((counter 0))

  (let ((next (lam ()

               (block

                (set-var counter (+ counter 1))

                counter))))

    (link (next) (link (next) 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-var(x :: String)
  | e-set-var(x :: String, new-val :: Expr)
  | e-block(exps :: List<Expr>%(is-link))
end

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

fun is-v-list(v :: Value):
  is-v-empty(v) or is-v-link(v)
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; the only change is to the Env type (noted lower down), and the addition of the equal-funs error:

data Error:
  | unbound-id
  | div-0
  | not-a-num
  | not-a-bool
  | not-a-fun
  | not-a-list
  | not-a-link
  | arity-mismatch
  | equal-funs
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 and a store, so there is a definition for environments, and for locations. Note that environments now contain locations rather than directly containing values:

type Location = Number
type Env = SD.StringDict<Location>

The store is described more in the next section.

6.2 Paret Semantics

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

fun interp(env :: Env, store :: Store, expr :: Expr) -> VandS

It is up to you what definitions to use for Store and VandS. You can rename them if you like. You should change the definition of eval to make sure that it returns a Value, to ensure uniform testing. So, for example, you might choose what we did in lecture:

data Store:
  | mt-sto
  | sto(l :: Location, v :: Value, rest :: Store)
end
data VandS:
  | vs(v :: Value, s :: Store)
end

Then you should make sure that eval only returns the v field of the VandS that is returned.

Note that the assignment doesn’t mandate that you implement alloc, update, and deref as we mentioned in class, but that might be a useful place to start.

6.2.1 Testing Multiple Representations

Since you’re free to pick any representation for the store, and any allocation strategy (start locations from 0, from 100, counting backwards, etc.), there are many possible correct behaviors for evaluations that return or v-clos values (which contain Locations in their environments). The Value type is set up so that you cannot directly test equality of closures; you’ll get an error if you do. So, intead of testing that the interpreter returns a v-clos with a particular environment, you could check that the interpreter returned some v-clos:

check:
  eval("(lam () 5)") satisfies is-v-clos
end

This is similar to testing sorts that may or may not be stable. The specification admits many possible input/output behaviors, so it’s relational, rather than functional. If you want to test in more detail, you should make the test apply the function. Of course, you can also test your representations directly in your code file and look for particular locations. Your tests in the external test file need to use the satisfies style to handle all possible correct implementations.

Note that this also helps you use tests from others that you see during review, since if you had different allocation strategies, it would be difficult to re-use or give feedback on tests that depended on the store implementation.

6.2.2 New and Updated Semantics

The semantics of some expressions from original Paret have changed, and new forms added. The new forms are described here:

6.3 Logistics

You have been provided two files:

The files are at:

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

Tests: https://code.pyret.org/editor#share=0B32bNEogmncOZjBucnNUWEpUWXM&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=0B32bNEogmncOYnE4TGs0bHd1Unc&v=v0.5r790

6.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
equal-funs = I.equal-funs

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-var = I.e-var
e-lam = I.e-lam
e-link = I.e-link
e-unop = I.e-unop
e-set-var = I.e-set-var

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

is-v-list = I.is-v-list
6.4 Testing and Submission Steps

By midnight Sunday (Feb 22), you should submit 5-10 of what you think are the most interesting tests to Captain Teach at the cs91-state 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 23), 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: Bad solutions are available via:

import shared-gdrive("state-interp-different-solutions.arr", "0B32bNEogmncOcWRZQVlZc1ltNU0") as C

The names of the interpreters are:

dynamic-scope-again
let-star-again
arg-eval-order-again
set-returns-old-val
store-has-one-location
store-has-five-locations
store-forgetful-in-args
store-forgetful-in-binops
store-forgetful-after-app
wrong-closure-env-recursion

This was the in-class test that I projected in lab. I recommend getting your state-interp to pass it:

S.eval(```
      (let ((sum-to-n
      (lam (n)
      (let ((sum-helper (lam (f acc)
      (if ( == n 0 ) acc
      (block
      (set-var n (- n 1))
      (f f (+ n acc)))))))
      (sum-helper sum-helper 0)))
      )
      )
      (sum-to-n 5))
      ```)

By midnight Thursday (Feb 26), 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.

6.5 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.

    ← prev  up  next →