This is an old revision of the document!
This lab is designed to help you go deeper into what it takes to build an interpreter. We will expand our language by adding additional language constructs and better error handling.
For this lab, you should have Julia 1.0 installed, the same as for the rudimentary interpreter. You will need both the Lexer and Error modules.
For this lab, you will expand the interpreter that you have already built, and combine it with the interpreter that we have built in class, plus add some new functionality and error handling.
The primary deliverable for this lab is a new Julia module. Your module should export
calc functions, and two return types,
Your module should be able to do everything that your simple interpreter could do (all unary, binary operations, and built-in functions). In addition, your new interpreter must implement all of the functionality of the
CI3.jl module from class, including
if0 expressions, closures and
lambda statements, and
However, you will need to extend the functionality of several of these statements, as described below.
You must also do some basic error handling.
CI3.jl module is available in the Content section on the class's Learning Suite pages.
Please name your module ExtInt.
The grammar for our new language is the following:
<AE> ::= number | (+ <AE> <AE>) | (- <AE> <AE>) | (* <AE> <AE>) | (/ <AE> <AE>) | (mod <AE> <AE>) | (collatz <AE>) | (- <AE>) | id | (if0 <AE> <AE> <AE>) # Major change: function definitions, calls & # with statements now take a variable number of arguments! # Note the extra parens. | (with ( (id <AE>)* ) <AE>) | (lambda (id*) <AE>) | (<AE> <AE>*)
number is a Julia Real and
id is a Julia Symbol that is not
Here the “*” notation is the Kleene star (zero or more occurrences) you should have seen in CS 236 and/or CS 252.
Remember, this grammar is for the concrete syntax: the lexer will return data structures that put everything between parentheses into an array (removing the parentheses).
This grammar blends both the grammar for the simple interpreter and the in-class interpreter we have built, but also expands several of the functions.
There are two primary ways you must extend the simple interpreter: both the
with statement and function definitions (and calls!) must be able to accept multiple parameters.
This implies several changes that you will need to make:
The logic for
with statements that define multiple symbols is similar.
There are many ways to create an extended environment with multiple new symbols; the easiest is just to extend the current environment multiple times with multiple <formal,actual> argument mappings. But you could, for example, implement a small hash for each scope.
Note that there are some small (concrete) syntax changes as a result of the new grammar. Specifically, you need some extra parentheses for
In class, we wrote this:
(lambda x (+ x 1)) or (with (x 5) (+ x 1))
But now, we will write things like
(lambda (x y) (+ x y)) or (with ((x 2) (y 6)) (+ x y))
This interpreter needs to be able to handle new kinds of errors. We expect you to properly catch both type errors , syntax errors and arity errors. Remember the parser's job is to reject input that does not fit the grammar and output an abstract syntax tree when it does. The Interpreters job is to interpret an abstract syntax tree and throw an error on invalid computations.
For type errors: There are a couple of times when types are essential. For example, when we evaluate a
Plus node, we calculate the LHS and RHS, and then attempt to add them. Obviously, we need to make sure that both the LHS and RHS returned numbers! Similarly, when we calc a FunApp node, we evaluate a function expression – it must result in a
For syntax errors: There are several new opportunities for mistakes. Similar to the simple interpreter, it is a syntax error if the programmer attempts to add three numbers. If a
lambda or a
with expression has duplicate identifiers or use a key word ( '+, '-, '*, '/, 'with, 'if0, 'mod, 'collatz, or 'lambda) as and identifier, we consider it a syntax error. Therefore, such errors must be detected in parse. For example, parsing the following expressions must signal errors:
(with ((x 10) (x 20)) 50) (lambda (x x) 10)
For arity errors: Arity errors occur when a defined function is given too many or too few parameters. These should be caught when a function is applied, during the calc phase.
Remember to throw errors, not simply print error messages.
Your parser and interpreter must detect errors and explicitly signal them by calling throw(LispError(Reason). We will consider an error raised internally by julia to be a bug in your code.
To include LispError put “using Error” after the module declaration of you code. Error is a module containing LispError.
For example, Julia signals a “divide by zero” error if you attempt to evaluate (/ 1 0). Since we use Julia's division function to implement division in OWL, you may be tempted to leave it to Julia to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Julia's division procedure.
Your code must use the following types (BUT - note that you may need to change the definition of the With, FunApp and FunDef nodes to support multiple symbols/parameters!)
You should again collapse the binary operators
mod to a single Binop node in the AST as you did in the previous lab. (Feel free to graft in your code for this from that lab.) You will also need to add whatever abstract syntax your parser generated for the unary minus and collatz operators.
# Abstract syntax abstract type AE end struct NumNode <: AE n::Real end struct BinopNode <: AE op::Function lhs::AE rhs::AE end struct If0Node <: AE condition::AE zero_branch::AE nonzero_branch::AE end struct WithNode <: AE sym::Symbol binding_expr::AE body::AE end struct VarRefNode <: AE sym::Symbol end struct FunDefNode <: AE formal::Symbol fun_body::AE end struct FunAppNode <: AE fun_expr::AE arg_expr::AE end abstract type RetVal end abstract type Environment end struct NumVal <: RetVal n::Real end struct ClosureVal <: RetVal formal::Symbol body::AE env::Environment end struct EmptyEnv <: Environment end struct ExtendedEnv <: Environment sym::Symbol val::RetVal parent::Environment end
You should explicitly check to make sure that programs don't attempt to redefine reserved words.
Your module should export two core functions:
function parse(expr::Any) function calc(ast::AE)
As with the previous lab it may be easier to overload the functions for each type.
The semantics of (if0 test then else) is as follows: if the test evaluates to zero, then the entire expression evaluates to the result of then expression, otherwise, it evaluates to the result of the else expression. Evaluation should signal an error for non-numeric test values.
All arguments to the function must evaluate with the same deferred substitutions. An example of a multi-argument fun:
((lambda (x y) (* x y)) 2 3)
This evaluates to 6.
As you did for multi-armed with, you must ensure that the arguments to a function have distinct names.