User Tools

Site Tools



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 parse and calc functions, and two return types, NumVal and ClosureVal.

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 with statements.

However, you will need to extend the functionality of several of these statements, as described below.

You must also do some basic error handling.

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

where number is a Julia Real and id is a Julia Symbol that is not :+, :-, :*, :/, :with, :if0, :mod, :collatz, or :lambda.

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.

Expanded functionality:

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:

  1. When you encounter a function definition, you must remember how many arguments it expects (and what symbol they are - the formal parameters)
  2. When you call a function, you must
    1. evaluate multiple argument expressions (the actual parameters)
    2. create an extended environment that binds each actual parameter to each formal parameter

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 with and lambda calls:

In class, we wrote this:

(lambda x (+ x 1))
(with (x 5) (+ x 1))

But now, we will write things like

(lambda (x y) (+ x y))
(with ((x 2) (y 6)) (+ x y))

Error handling:

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 ClosureVal.

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.. Think how you'd feel as a programmer if an error in your source code caused your compiler to crash instead of telling you what was wrong.

To include LispError put “using Error” after the module declaration of you code. Error is a module containing LispError.


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 +, -, *, /, and 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
struct BinopNode <: AE
struct If0Node <: AE
struct WithNode <: AE
struct VarRefNode <: AE
struct FunDefNode <: AE
struct FunAppNode <: AE
abstract type RetVal end
abstract type Environment end
struct NumVal <: RetVal
struct ClosureVal <: RetVal
struct EmptyEnv <: Environment
struct ExtendedEnv <: Environment

Additional details:

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.

Multi-argument fun

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.

cs330_f2016/labw.txt · Last modified: 2021/06/30 23:42 (external edit)