Calculating Locals

There will be no reviews for this assignment, but it does have two parts. First submit the code and tests for Part I, and next submit the code and tests for Part II.

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

Note: The purpose of `calc-locals` is to statically check what is in scope at a given part of your program, so it should always halt.

For this assignment, you will write a function calc-locals. It takes an expression with a "hole" in it, and returns the set of identifiers which are in scope at that hole. You will actually do this twice -- first for a language in which every with and lam is annotated with the type of its "namespace" record argument, and second where they have no annotations.

Part I (Typed)

The Language

You will be working with a language similar to the language for type-checker, with records added. There is no and or or, and there are no strings. There is no desugaring in this language, so you will have to handle e-lets. The expression type has been extended to include "holes". The concrete syntax for a hole is @, and it's represented as e-hole. with and lam expressions have type annotations.

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

The calc-locals function

You will implement a function that takes an expression with a hole in it and returns the set of identifiers that are in scope at the hole:

fun calc-locals(expr :: C.Expr) -> Set<String>:
  ...
end

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"]. (parse-n-calc is a helper function we provide that parses and then calls calc-locals.)

You do not need to type-check the program, and can generally assume that the type annotation on with is correct. However, if the annotation on with is not a record type, that's obviously wrong and will get in the way of calc-locals, so raise the following exception:

data CalcLocalsError:
  | err-with-not-a-record(with-type :: Type)
end

Test Cases

Do not write test cases that include no holes or more than one hole. Do not write test cases where the type annotation on with doesn't match the type of its record.

We have let-bound is-err-with-not-a-record = C.is-err-with-not-a-record at the top of the test stencil. You can check for this error by writing:

parse-n-calc("(with 3 Num 4)") raises-satisfies is-err-with-not-a-record

(This way if you make a typo in the error name, Pyret will raise an exception when you run your tests.)

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-locals-typed-code.arr" and "calc-locals-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 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 @))")

should 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-locals-untyped-code.arr" and "calc-locals-untyped-tests.arr".

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

The Grammar

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

<expr> ::= <num>
         | <id>
         | <bool>
         | (+ <expr> <expr>)
         | (num= <expr> <expr>)
         | (if <expr> <expr> <expr>)
         | (let ((<id> <expr>)) <expr>)
         | (<expr> <expr>)
         | (record <field> ...)
         | (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

<field> ::= (<id> <expr>)   # field name, followed by field value

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-app(func :: Expr, arg :: Expr)
  | e-id(name :: String)

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

  | e-let(name :: String, expr :: Expr, body :: Expr)
  | e-hole

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

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

data FieldExpr:
  | e-field(field-name :: String, value :: Expr)
end

data Binding:
  | binding(name :: String, expr :: 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 :: List<FieldType>)
end

data FieldType:
  | t-field(field-name :: String, field-type :: Type)
end

data CalcLocalsError:
  | err-with-not-a-record(with-type :: Type)
end