Extended Interpreters

Like the first assignment, this is to be completed solo.

  1. Write a parser and interpreter for the CFWAE language we’ve discussed in class, extended with the language features described below. Your interpreter should have eager application semantics and use caching substitution.

  2. After completing the first part of the assignment, copy the resulting interpreter and modify it so that it has lazy application semantics. (We strongly recommend that you not attempt this part of the assignment until you’ve gotten the first interpreter done and thoroughly tested and debugged!)

Turn in the first and second parts of the assignment in the files part1.scm and part2.scm, respectively. Please factor out as much common code as possible into another file that gets included by the first two. [1]

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, as well as the function interp, which consumes both an abstract syntax expression (as returned by the parse function) and an environment and returns a CFWAE-value. Please include a contract for every function that you write and include test cases that amply exercise all of the code you’ve written.

Features to Implement

Conditionals

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 signals an error for non-numeric test values.

Multi-argument fun

Extend the fun language feature described in lecture so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate in the same environment. To simplify your program, you may assume that the number of arguments in a function invocation always matches the number in the procedure definition. For example:

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

evaluates to 6.

The syntax of the CFWAE language with these three additional features can be captured with the following EBNF:

<CFWAE> ::= <num>
    | {+ <CFWAE> <CFWAE>}
    | {- <CFWAE> <CFWAE>}
    | {* <CFWAE> <CFWAE>}
    | <id>
    | {if0 <CFWAE> <CFWAE> <CFWAE>}
    | {with {{<id> <CFWAE>} ...} <CFWAE>}
    | {fun {<id> ...} <CFWAE>}
    | {<CFWAE> <CFWAE> ...}

In this grammar, the ellipsis (...) means that the previous non-terminal is present zero or more times.

Get Points Back

This assignment builds on the previous. If you know your rudimentary interpreter had problems, and you fix those problems in your extended interpreter, and you provide test cases to prove this, and you tell us what you fixed, we’ll give you back any points that you lost for functionality.

Describe what you fixed in your README file.


1: To include the contents of one Scheme file in another, use the load function. For example:

  ;; Extended Interpreters assignment
  ;; Author phopkins
  ;; part1.ss

  (load "common.ss")

  (define (interp ...))

The above code would include the entire contents of the file “common.ss” into this file. You will need to switch to the PLAI - Pretty Big language to use load.