Calculating Local Variables: With

We don't intend for these assignments to take too long. If you have spent five hours on any part of this assignment please stop and check in with the TAs.

You will be working with sets. The documentation is on pyret.org/docs/latest.

You will implement the function calc-locals twice -- first for a language in which every with and lam is annotated with the type of its argument, and second where they have no annotations.

1. Extended Language

1.1 With

(with rec body) first evaluates rec to a record value, and then evaluates body with all of the record's fields added as bindings to the current environment.

For example,

(with (record (a 1) (b 2)) (Record (a Num) (b Num)) (+ a b)) # in the typed version

(with (record (a 1) (b 2)) (+ a b)) # in the untyped version

would both evaluate to 3.

Part I (Typed)

In Part I, with and lam expressions have type annotations. Please note that an expression can be a subtype of the given type annotation. For example, in (with <rec-expr> <rec-type> <expr>), <rec-expr> can be any subtype of <rec-type>.

The grammar and abstract syntax are at the bottom of the page. For reference, here is the definitions file for Part I.

As in the other calc-locals assignments, it must return precisely the set of identifiers that are in scope at the hole. In particular, replacing a hole with any one of the identifiers returned by calc-locals must never cause an unbound identifier exception. Contrariwise, every identifier not in the set returned by calc-locals must be unbound at that position (though it may not result in a runtime exception, because it may never be evaluated).

For example, the following program:

parse-n-calc("(with (record (a (+ 1 2)) (b 3))
                    (Record (a Num) (b Num))
                (+ a @))")

should return [set: "a", "b"].

You may assume all input to calc-locals is well-formed. By this we mean that the type annotation on a with expression will always be a record and there are no type-errors in the input.

Test Cases

Do not write test cases that include no holes or more than one hole. Do not write test cases where the argument to with is not a subtype of the type annotation.

Submission of Part I

To get started on Part I, here is:

the code stencil

the tests stencil

Submit a zip of these two files through Captain Teach. Make sure to call them "calc-with-typed-code.arr" and "calc-with-typed-tests.arr".

https://www.captain-teach.org/brown-cs173/assignments/

Part II (Untyped)

For the second part of the assignment, your task is exactly the same as before, except that now the language doesn't have types (or type annotations on with or lam).

Again, your calc-locals function must return precisely the set of identifiers that are in scope at the hole. It may not leave out any identifier that is in scope, and it may not include any identifier that is not in scope.

For example, the following program:

parse-n-calc("(with (record (a (+ 1 2)) (b 3))
                (+ a @))")

would return [set: "a", "b"].

The grammar and abstract syntax are at the bottom of the page. For reference, here is the definitions file for Part II.

Submission of Part II

Here are the stencils for Part II:

code stencil

tests stencil

Submit a zip of these two files through Captain Teach. Make sure to call them "calc-with-untyped-code.arr" and "calc-with-untyped-tests.arr".

https://www.captain-teach.org/brown-cs173/assignments/

2. The Grammar

The grammar is almost the same for both parts, so here is a combined presentation:

<expr> ::= <num>
         | <bool>
         | (+ <expr> <expr>)
         | (num= <expr> <expr>)
         | (if <expr> <expr> <expr>)

         | <id>
         | (<expr> <expr>)
         | (let (<id> <expr>) <expr>)

         | (record (<id> <expr>)  ...)
         | (lookup <expr> <id>)
         | (extend <expr> <id> <expr>)

         | @                           # a "hole"

         # In the "typed" language, for Part I
         | (with <expr> <type> <expr>)
         | (lam (<id> : <type>) <expr>)

         # In the "untyped" language, for Part II
         | (with <expr> <expr>)
         | (lam <id> <expr>)

<type> ::= Num
         | Bool
         | (<type> -> <type>)         # function type
         | (Record (<id> <type>) ...) # record type

Notice that the syntax for with and lam is different in each part, and the untyped part doesn't use the type syntax. The abstract syntax is also mostly the same, so we show them together. Again, the only difference between parts is e-with and e-lam, and the lack of types in the untyped version.

data Expr:
  | e-num(value :: Number)
  | e-bool(value :: Boolean)
  | e-op(op :: Operator, left :: Expr, right :: Expr)
  | e-if(cond :: Expr, consq :: Expr, altern :: Expr)

  | e-id(name :: String)
  | e-app(func :: Expr, arg :: Expr)
  | e-let(name :: String, expr :: Expr, body :: Expr)

  | e-rec(fields :: StringDict<Expr>)
  | e-lookup(record :: Expr, field-name :: String)
  | e-extend(record :: Expr, field-name :: String, new-value :: Expr)

  | e-hole

  # In the "typed" language, for Part I
  | e-with(record :: Expr, rec-type :: Type, body :: Expr)
  | e-lam(id :: String, arg-t :: Type, body :: Expr)

  # In the "untyped" language, for Part II
  | e-with(record :: Expr, body :: Expr)
  | e-lam(id :: String, body :: Expr)
end

data Operator:
  | op-plus
  | op-num-eq
end

data Type:
  | t-num
  | t-bool
  | t-fun(arg-type :: Type, return-type :: Type)
  | t-rec(field-types :: StringDict<Type>)
end