BYU CS classes

Learn how to implement type checking in an interpreter.

Implement the CITypes interpreter using the provided shell.

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:

(lambda <id> : <type> <expr>)

. For example, a simple numeric increment function would be written as

(lambda x : number (+ x 1)

.

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

Here is the grammar for the CITypes language:

<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>)

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.

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:

1. Recursively use type-of-expression to type check and determine the types of any subexpressions
2. Verify that types are being used correctly in this expression
3. 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 comparison.