cs330_f2016:lab16
Differences
This shows you the differences between two versions of the page.
|
cs330_f2016:lab16 [2016/11/26 18:58] morse |
cs330_f2016:lab16 [2021/06/30 23:42] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ** This is a draft version of the assignment. Do not start on it until this line is removed. ** | ||
| - | ====Objective:==== | ||
| - | |||
| - | Learn how to implement type checking in an interpreter. | ||
| - | |||
| - | ---- | ||
| - | ====Deliverable:==== | ||
| - | |||
| - | Implement the CITypes interpreter using the provided shell. | ||
| - | |||
| - | === Language Overview === | ||
| - | |||
| - | The CITypes language is based on the CI5 language, just like your Extended Interpreter. | ||
| - | ** You do not need to add any functionality from your previous assignments. ** | ||
| - | |||
| - | To make the type system more interesting, the CITypes language adds booleans and numeric lists. | ||
| - | The "if0" function is replaced by "ifb", which requires that the conditional return a boolean value (like in Java). | ||
| - | A new operator "iszero" is added, which tests to see if a number is zero and returns a boolean result. | ||
| - | |||
| - | The language includes two new boolean literals: | ||
| - | * true | ||
| - | * false | ||
| - | |||
| - | The language also requires that the types of formal parameters be specified with the function is declared: | ||
| - | <code> | ||
| - | (lambda <id> : <type> <expr>) | ||
| - | </code> | ||
| - | To support this, the language's grammar also includes a new nonterminal "<type>", which can be "number", "boolean", "nlist", or a function type signature of the form "(<type> : <type>)". | ||
| - | |||
| - | For example, a simple numeric increment function would be written as | ||
| - | <code> | ||
| - | (lambda x : number (+ x 1) | ||
| - | </code> | ||
| - | and a function that takes as input a function from numbers to numbers would look like this: | ||
| - | <code> | ||
| - | (lambda f : (number : number) (f 3)) | ||
| - | </code> | ||
| - | |||
| - | There are five new types of expressions for handling numeric lists: | ||
| - | * nempty, which returns an empty numeric list | ||
| - | * nisempty, which returns whether a numeric list is empty | ||
| - | * ncons, which prepends a number to a numeric list | ||
| - | * nfirst, which returns the first number in a numeric list | ||
| - | * nrest, which returns the rest of a numeric list after the first item | ||
| - | |||
| - | === Grammar / Parser === | ||
| - | |||
| - | Here is the grammar for the CITypes language: | ||
| - | <code> | ||
| - | <expr> ::= <number> | ||
| - | | true | ||
| - | | false | ||
| - | | (+ <expr> <expr>) | ||
| - | | (- <expr> <expr>) | ||
| - | | (iszero <expr>) | ||
| - | | (ifb <expr> <expr> <expr>) | ||
| - | | (with <id> <expr> <expr>) | ||
| - | | <id> | ||
| - | | (lambda <id> : <type> <expr>) | ||
| - | | (<expr> <expr>) | ||
| - | | nempty | ||
| - | | (ncons <expr> <expr>) | ||
| - | | (nempty <expr>) | ||
| - | | (nfirst <expr>) | ||
| - | | (nrest <expr>) | ||
| - | |||
| - | <type> ::= number | ||
| - | | boolean | ||
| - | | nlist | ||
| - | | (<type> : <type>) | ||
| - | |||
| - | </code> | ||
| - | |||
| - | A working parser for this grammar is already provided as part of the shell. | ||
| - | Note: since the focus here is on type checking, this parser works for syntactically valid input but does not adequately reject invalid input. | ||
| - | **You do not need to bulletproof or otherwise modify the parser.** | ||
| - | |||
| - | Notice that there is a new non-terminal for type declarations, which is also handled by the parser. | ||
| - | |||
| - | === Type Checker === | ||
| - | |||
| - | You should implement a function "type-of-expression" that returns the type of an expression. | ||
| - | As with "calc" in the earlier interpreters, there is a top-level version of the function that takes only an expression and then calls (using multiple dispatch) the corresponding function for that kind of abstract syntax node, passing to it an empty type environment. | ||
| - | |||
| - | The shell includes implementations of this function for numeric literals and the plus/minus operators, which you can use as examples. | ||
| - | |||
| - | The form of these functions is always the same: | ||
| - | - Recursively use type-of-expression to type check and determine the types of any subexpressions | ||
| - | - Verify that types are being used correctly in this expression | ||
| - | - Return the type of the result of this expression | ||
| - | |||
| - | ** The type checker should perform no evaluation of the code, only type checking. ** | ||
| - | |||
| - | Some of the tests will involve comparing two types, and a "same_types" function is provided to do a (recursive if necessary) comparison. | ||
| - | |||
| - | When your type checker catches an error, it should throw an exception with a descriptive error message. | ||
| - | |||
| - | ====Hints:==== | ||
cs330_f2016/lab16.txt ยท Last modified: 2021/06/30 23:42 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
