====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 1.0 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 ''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.

----
====Description:====

The grammar for our new language is the following:

<code BNF>
<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>*)         
</code>

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:

  - When you encounter a function definition, you must remember how many arguments it expects (and what symbol they are - the formal parameters)
  - When you call a function, you must
    - evaluate multiple argument expressions (the actual parameters)
    - 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:

<code lisp>
(lambda x (+ x 1))
or
(with (x 5) (+ x 1))
</code>

But now, we will write things like

<code lisp>
(lambda (x y) (+ x y))
or
(with ((x 2) (y 6)) (+ x y))
</code>


----
===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:

<code lisp>
(with ((x 10) (x 20)) 50)
(lambda (x x) 10)
</code>

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

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

<code julia>

# 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

</code>

----
  
===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:

<code Julia>
function parse(expr::Any)
function calc(ast::AE)
</code>

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 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:
<code lisp>
((lambda (x y) (* x y)) 2 3)
</code>
This evaluates to 6.

As you did for multi-armed with, you must ensure that the arguments to a function have distinct names.