Differences

This shows you the differences between two versions of the page.

--- cs330_f2016:labw [2017/09/27 21:21]
corey [Description:]
+++ cs330_f2016:labw [2021/06/30 23:42]
@@ Line 1: / Line 1: @@
-====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 LearningSuite, under "Content -> Julia -> Functions and Closures".
-Please name your module ExtInt.
-----
-====Description:====
-The grammar for our new language is the following:
-<code BNF>
-<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>*)
-</code>
-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:
-  - 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.
-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.
-<code julia>
-# 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
-abstract type RetVal 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
-abstract type Environment end
-type mtEnv <: Environment
-end
-type CEnvironment <: Environment
-  name::Symbol
-  value::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::Array{Symbol or Real})
-function calc(ast::OWL)
-</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: 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:
-<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.

BYU CS classes

User Tools

Site Tools

Differences

Page Tools