The Extended Interpreter

lego-bricks

In this laboratory, you'll be extending your interpreter to handle some new language constructs. In particular, we'll add an if statement (called if0  so we don't confuse the if in our programming language with the if in Scheme), and we'll add the ability to use functions. 

Now, functions will require you to think and learn. In particular, we have to be careful about how we do (deferred) substitution in the face of functions. 

As you have seen from the previous lab, thinking about the problems, and understanding the why of our interpreter, is where the real value in the class comes from.

Big Picture

Write a parser and interpreter for the CFWAE language, extended with the language features described below. Your interpreter should have eager application semantics and use deferred substitution.

I recommend that you check in with me at each stage, to discuss what did or didn't work for you along the way.

Requirements

In each part of the assignment, implement the function parse, which consumes an expression in the language's concrete syntax and returns the abstract syntax representation of that expression. parse must accept only expressions in the syntax of the language.

In addition to parse, you must implement the function interp, which consumes an abstract syntax expression (as returned by the parse function) and returns a CFWAE-Value.

You must include a contract for every function that you write and include test cases that amply exercise all of the code you've written. Refer to the style requirements for clarification, if necessary.

I have attempted to break the lab apart into a sequence of steps that, if followed, should make things easier. Skipping ahead, or deciding to conflate one step with another, may lead to confusion. 

Further, I have given you two paths through the laboratory: one path by which you leave with statements handling a single binding (and functions handling a single argument), or a second path where you handle multiple-binding with statements and multiple-argument functions. Start down the first path, and then, if time allows, revise your project to handle the second path.

Cleanup and Tweaking

Begin with your interpreter from the previous laboratory. It should pass all tests. I highly recommend your interpreter makes use of type-case for both interp and subst, as it keeps the code simpler than if you are working with cond. 

This may be a good opportunity to talk with some of your other classmates and refactor your interpreter. That is, if you want to clean up your code and make it ready for this lab, and you want to talk to others about what they did, that would not be a bad idea.

Defer Substitution

In lecture, I've discussed differed substitution. Or, if you prefer, I transformed the interpreter from class into an environment-passing interpreter. You should begin by transforming your interpreter into an environment-passing interpreter, thus getting rid of subst. 

You may start with the code from class, but it makes use of match, map, and foldl in a number of places. I would not use this interpreter unless you fully understand what it is doing. (That was intentional on my part. If you want to use that code, you need to demonstrate that you know how to use it.)

So, your first step: implement deferred substitution.

Conditional Statements

To save the trouble of having to add boolean values and operators over them, create the construct if0 using the syntax described by the EBNF below. Note that if0 has three branches:

  • A test expression
  • A "then" expression, which evaluates if the test expression evaluates to zero
  • An "else" expression, which evaluates for any other number.


Evaluation should signal an error for non-numeric test values.

To be clear: we are not introducing booleans into our language. An expression is true if the condition equals zero, and false otherwise.

Functions

I will talk about functions more in-class.

Start with functions of just one argument.

You'll need to extend your parser to allow the definition of functions. They'll only appear (as definitions) on the right-hand side of a with binding. You will also need to find places where functions are applied, and in those cases, build a fun-app data structure. So, in our interpreter, we will be looking for fun-def structures (which are function definitions) and fun-app structures (which are function applications).

Once you are parsing functions into fun-def structures, you'll then want to extend your interpreter to build a closure whenever a function is found. 

Lastly, you'll need to implement function application in your interpreter. This is not conceptually difficult: you have done it already for binops. Remember, a binop was a function, and you simply pulled the op out and applied it to the arguments (the lhs and rhs). That said, careful consideration needs to be given to the environment in which you will apply your function. 

A big part of writing an interpreter is managing the environment, or (if you prefer) the bindings of values to names.

Testing

Your test suite from the previous exercise should continue to work with your new interpreter. However, it needs  to be extended. 

If you are working on a single-binding, single-argument function interpreter, then you need tests that stress your with statements and functions.

If you are working on a multi-binding, multi-argument function interpreter, then you need to test multiple bindings and multiple arguments as well.

Strategy

Write test cases before you extend your interpreter. You should know what kind of code your parser will handle, and what values will come back from your interpreter. 

When you write a test case, send it to the class mailing list. Flag the test as either "SBSA: " or "MBMA: " so people know what stage of the lab you are working on. Therefore, everyone will benefit from your efforts, and visa-versa.

Multi-argument functions

The last step in this laboratory is to allow functions of multiple arguments. 

Extend the fun language feature so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate with the same deferred substitutions. An example of a multi-argument fun:

{{fun {x y} {* x y}} 2 3}


This evaluates to 6.

You will need to extend your test suite to include functions of multiple arguments.

Grammars

To make clear, you can do this laboratory to two levels. If you wish to be graded with a maximum possible grade of a B, you should implement this grammar:

<CFWAE1> ::= <num>
    | {+ <CFWAE1> <CFWAE1>}
    | {- <CFWAE1> <CFWAE1>}
    | {* <CFWAE1> <CFWAE1>}
    | {/ <CFWAE1> <CFWAE1>}
    | <id>
    | {if0 <CFWAE1> <CFWAE1> <CFWAE1>}
    | {with {<id> <CFWAE1>} <CFWAE1>}
    | {fun {<id>} <CFWAE1>}
    | {<CFWAE1> <CFWAE1>}
where an id is not +, -, *, /, with, if0 or fun.


Put simply, this is a language of single-binding with statements and single-argument functions. If your interpreter is well-written, well-tested, and adheres to style, then the submission of an interpreter for this language can earn, at maximum, a B. This is an accomplishment.



Once you reach this threshold, I would then extend my interpreter to include multiple bindings in the with, and multiple-argument functions. Implementing this language raises your maximum possible grade to an A.

<CFWAE2> ::= <num>
    | {+ <CFWAE2> <CFWAE2>}
    | {- <CFWAE2> <CFWAE2>}
    | {* <CFWAE2> <CFWAE2>}
    | {/ <CFWAE2> <CFWAE2>}
    | <id>
    | {if0 <CFWAE2> <CFWAE2> <CFWAE2>}
    | {with {{<id> <CFWAE2>} ...} <CFWAE2>}
    | {fun {<id> ...} <CFWAE2>}
    | {<CFWAE2> <CFWAE2> ...}
where an id is not +, -, *, /, with, if0 or fun.


This grammar describes a language with multiple-binding with statements and functions that can handle multiple arguments. In this grammar, the ellipsis (...) means that the previous non-terminal is present zero or more times.

If a fun or a with expression has duplicate identifiers, 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}
{fun {x x} 10}

Support Code (single-bindings)

(define-type Binding
  [binding (name symbol?) (named-expr CFWAE?)])
(define-type CFWAE
  [num (n number?)]
  [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)]
  [with (b Binding?) (body CFWAE?)]
  [id (name symbol?)]
  [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)]
  [fun (arg symbol?) (body CFWAE?)]
  [app (f CFWAE?) (arg CFWAE?)])
;; This may look new, but it is really just an
;; onion-core and an onion. Think about it.
(define-type Env
  [mtEnv]
  [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)])
(define-type CFWAE-Value
  [numV (n number?)]
  [closureV (param symbol?)
            (body CFWAE?)
            (env Env?)])
;; parse : expression -> CFWAE
;; This procedure parses an expression into a CFWAE
(define (parse sexp)
  ...)
;; interp-with-env : CFWAE Env -> CFWAE-Value
(define (interp-with-env expr env)
  ...)
;; interp : CFWAE -> CFWAE-Value
;; This procedure interprets the given CFWAE and produces a result
;; in the form of a CFWAE-Value (either a closureV or a numV)
(define (interp expr)
  (interp-with-env expr (mtEnv))

Support code (multiple bindings)

(define-type Binding
  [binding (name symbol?) (named-expr CFWAE?)])
(define-type CFWAE
  [num (n number?)]
  [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)]
  [with (lob (listof Binding?)) (body CFWAE?)]
  [id (name symbol?)]
  [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)]
  [fun (args (listof symbol?)) (body CFWAE?)]
  [app (f CFWAE?) (args (listof CFWAE?))])
;; This may look new, but it is really just an
;; onion-core and an onion. Think about it.
(define-type Env
  [mtEnv]
  [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)])
(define-type CFWAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFWAE?)
            (env Env?)])
;; parse : expression -> CFWAE
;; This procedure parses an expression into a CFWAE
(define (parse sexp)
  ...)
;; interp-with-env : CFWAE Env -> CFWAE-Value
(define (interp-with-env expr env)
  ...)
;; interp : CFWAE -> CFWAE-Value
;; This procedure interprets the given CFWAE and produces a result
;; in the form of a CFWAE-Value (either a closureV or a numV)
(define (interp expr)
  (interp-with-env expr (mtEnv))