User Tools

Site Tools


cs330_f2016:labw

Objective:

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.


Pre-requisite:

For this lab, you should have Julia 0.6+ installed, the same as for the rudimentary interpreter. You will need both the Lexer and Error modules.


Deliverable:

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 CI4.jl module, including if0 statements, 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 CI4.jl module is available on Dropbox.

Please name your module ExtInt.


Description:

The grammar for our new language is the following:

<OWL> ::= number
          | (+ <OWL> <OWL>)
          | (- <OWL> <OWL>)
          | (* <OWL> <OWL>)
          | (/ <OWL> <OWL>)
          | (mod <OWL> <OWL>)
          | (collatz <OWL>)
          | (- <OWL>)      
          | id
          | (if0 <OWL> <OWL> <OWL>)
 
          # Major change: function definitions, calls &
          # with statements now take a variable number of arguments!
          # Note the extra parens.
 
          | (with ( (id <OWL>)* ) <OWL>)
          | (lambda (id*) <OWL>)
          | (<OWL> <OWL>*)         

where number is a Julia Real and id 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 quoted S-expressions; 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))
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))

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.

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.


Template

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 OWL end
 
type NumNode <: OWL
    n::Real
end
 
type BinopNode <: OWL
    op::Function
    lhs::OWL
    rhs::OWL
end
 
type If0Node <: OWL
  condition::OWL
  zero_branch::OWL
  nonzero_branch::OWL
end
 
type WithNode <: OWL
  name::Symbol
  binding_expr::OWL
  body::OWL
end
 
type IdNode <: OWL
  name::Symbol
end
 
type FunDefNode <: OWL
    formal_parameter::Symbol
    fun_body::OWL
end
 
type FunAppNode <: OWL
    fun_expr::OWL
    arg_expr::OWL
end
 
# Rejigger our type hierarchy to better support return values
 
# Define both abstract types before we use them
 
abstract type RetVal end
 
abstract type Environment end
 
type NumVal <: RetVal
  n::Real
end
 
type ClosureVal <: RetVal
    param::Symbol
    body::OWL
    env::Environment  # this is the environment at definition time!
end
 
# Definitions for our environment data structures
 
type mtEnv <: Environment
end
 
type CEnvironment <: Environment
  name::Symbol
  value::RetVal
  parent::Environment
end

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::Array{Symbol or Real})
function calc(ast::OWL)

As with the previous lab it may be easier to overload the functions for each type.

Conditionals:

The semantics of (if0 test then else) is: if the test evaluates to zero, then the entire expression evaluates to the result of then, otherwise, it evaluates to else. 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: 2017/10/03 11:31 by corey