** Make sure you are working with the latest versions of the class code compatible with Julia 1.0. **

====Objective:====

This lab is designed to help you begin to understand how to design and implement an interpreter for a simple language.  The concepts you will practice here will be foundation to further labs!

----
====Prerequisite:====

You will need to download and install [[https://julialang.org|Julia]] for this lab.
Note: if you are using Ubuntu, be careful using the ''apt'' version of Julia (it may be too old!).  **You should use Julia 1.0 or later.**

Note that the code required for this lab is available on LearningSuite, in the "Content" section, under the "Interpreters" subsection, on the page titled "Base Interpreter".  You will need the following files:
  * ''Lexer.jl'' - the lexical analyzer
  * ''Error.jl'' - defines an error exception we'll throw as appropriate
  * ''CI0.jl'' - the base interpreter built in class

You should not modify the ''Lexer.jl'' or ''Error.jl'', and these will stay the same for all of the interpreter assignments.

After playing with it to make sure it's working and you have everything set up correctly, make a copy of ''CI0.jl'' and name it ''RudInt.jl'' (short for "Rudimentary Interpreter", or this assignment). You should then edit ''RudInt.jl'' using the provided CI0 interpreter as a base.  Remember to change the name of the module defined within the file to ''RudInt'' as well.

For code development, you may wish to use any of the following:
  * The [[http://junolab.org|Juno]] IDE built on [[https://atom.io|Atom]],
  * The [[https://github.com/JuliaLang/IJulia.jl|IJulia]] plugin for [[https://jupyter-notebook.readthedocs.io/en/stable/|Jupyter]],
  * Your preferred text editor (look to see if it has Julia extensions) and command-line invocation of your programs, or
  * Another IDE of your choice.

The instructor and TAs are prepared to help you with the first two (Juno and Jupyter), but you're on your own if you choose an arbitrary editor or IDE that we aren't familiar with.

----
====Deliverable:====

For this lab, you will create a simple interpreter for a language we call OWL ("Our Widdle Language").  You need to create a Julia module that implements all requisite functionality.

Your module should export ''parse'' and ''calc'' functions.

Remember that you will use multiple dispatch to implement different "versions" of ''parse'' and ''calc'', based on the input type.

An important difference between the code that you will implement for this lab, and the code we went through in class, is that your code should properly abstract multiple binary AST nodes into a single class we'll call ''BinopNode''.

Please name your module RudInt and submit just the one file.

===Operator Table ===

Define a data structure to contain a mapping from operator symbols to the functions that actually implement that symbol.  
These functions can be either built-in ones or ones that you write, so long as you preserve the semantic meaning of the operation.

For example:

<code Julia>
Dict(:+ => +)
</code>

For operations that do not require any further semantic checking, you should map to the corresponding built-in function.

===Parser===
Write the following function(s):

<code julia>
function parse(expr)
</code>

''expr'' will always be the output of the lexer, and will consist of numbers, symbols, and lists of numbers and symbols.

''parse'' parses ''expr'' into an OWL datastructure according to this grammar:

<code BNF>
  <AE>	 	::=	 	number
 	 	|	 	(+ <AE> <AE>)
 	 	|	 	(- <AE> <AE>)
 	 	|	 	(* <AE> <AE>)
 	 	|	 	(/ <AE> <AE>)
                |               (mod <AE> <AE>)
                |               (collatz <AE>)
                |               (- <AE>)
</code>

where number is a Julia real number literal.

**You should have test cases for all legal and illegal types of expressions.**  For example, the expression ''(+ 1 2 3)'' will pass the lexer just fine, but it is not accepted by our grammar -- our grammar can only handle two arguments, not three!

If you are given invalid input, you **must** throw an error, such as ''throw( LispError("Whoa there!  Unknown operation!") )''.  This is defined in ''Error.jl''.  Do not just print an error message, as this will not by caught by the autograder's ''try...catch'' block.


You must parse ''expr'' into the following types (copy and paste this to the top of your code):

<code julia>

abstract type AE end

struct NumNode <: AE
	n::Real
end

struct BinopNode <: AE
	op::Function
	lhs::AE
	rhs::AE
end

</code>

Plus any other subtypes you deem necessary.

===Interpreter===
Write the following function:

<code julia>
function calc(e)
</code>

Consumes an OWL abstract syntax tree representing an expression and computes the corresponding numerical result.

It should throw a Lisp error if division by zero or collatz of a negative number or zero is attempted. 

----
====Implementing mod====

This interpreter has another binary operation called ''mod'', similar to other binary operations.  You should implement it in Julia using Julia's built-in ''mod'' function (note that this is **not** the same as the ''%'' in-line operator, at least for negative numbers!).

====Implementing collatz====

One of the fundamental "primitives" in our language is a function called ''collatz''.  This function is commonly used as an example of a function that is simple to write, but which cannot be analyzed -- illustrating the difficulty of the general problem of program analysis.  It comes from the
[[https://en.wikipedia.org/wiki/Collatz_conjecture|Collatz conjecture]].  Our collatz function returns the number of times the function recurses.  Note that for some numbers, such as ''n=28'', the function returns quite quickly -- only 18 iterations -- but for neighboring numbers, such as ''n=27'', the function takes 111 iterations!

The function is defined as:

<code julia>

function collatz( n::Real )
  return collatz_helper( n, 0 )
end

function collatz_helper( n::Real, num_iters::Int )
  if n == 1
    return num_iters
  end
  if mod(n,2)==0
    return collatz_helper( n/2, num_iters+1 )
  else
    return collatz_helper( 3*n+1, num_iters+1 )  
  end
end

</code>

----
====Hints:====

Note that the ''-'' operator has two distinct usages: as a binary operation (the "minus" operation) and as a unary operation ("negation").  You should create a distinct class to handle unary operations.

If you change a module, it can sometimes be tricky to convince Julia to reload it and not use the previously compiled and cached version.  I **strongly** recommend using the ''[[https://github.com/timholy/Revise.jl|Revise]]'' module and loading it before you load the rest of your code.  If it's working as designed, it should automatically reload any subsequently loaded modules if the corresponding source code file changes.  (If you have not already installed the ''Revise'' package, use [[https://docs.julialang.org/en/v1/stdlib/Pkg/#Getting-Started-1|Julia's package manager]] to install it.)

<code julia>
using Revise # make sure to load before the others
using Error
using Lexer
using RudInt
</code>

In order for your code to work with the solo-grader you will need to do following:
  -Name your module ''RudInt''.
  -Make sure the ''julia'' binary is in your executable path (like you did for ''racket'' previously)
  -Make sure the path for the Error and Lexer files are on you Julia path. To do this you can add ''push!(LOAD_PATH,pwd())'' into your ''~/.julia/config/startup.jl'' file, then just make sure to run the autograder from the same directory in which you have RudInt, Lexer, and Error.
  -Inside your module have the lines ''using Error'' and ''using Lexer''.  (These should already be in the base code we give you to start with.)

====Change Log====
Changes since first given this semester:
  * Replaced "type..." with "struct..." in the abstract syntax definitions to be compatible with Julia 1.0
  * Changed "Num" to "NumNode" and "Binop" to "BinopNode" to be consistent with the in-class interpreters and the given base code in CI0.
  * Tweaked the Hints to be compatible with Julia 1.0, especially changing .juliarc to startup.jl.
  * Changed the autograders accordingly.