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.
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.
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-let
s. 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.
calc-locals
functionYou 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
Other than input that raises this exception, you may assume all input to calc-locals
is otherwise well-formed.
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.)
To get started on Part I, here is:
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/
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.
Here are the stencils for Part II:
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 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