We know that some of you are not yet comfortable with Racket; for that reason, we will weight this assignment very, very low in the overall score. Doing poorly on it will not at all damage your course grade. But, you should exploit this opportunity to become familiar with the style of programming you will do in the rest of the semester. All the remaining assignments will involve extensive Racket programming, so getting comfortable with Racket now is a very good idea.
Interpreter
You will write a parser and interpreter for the CFWAE language, as described below. Your interpreter should have eager application semantics and use deferred substitution. Call the new language CFWAE (conditionals, functions, with, and arithmetic expressions).
There are two functions you must implement to complete this assignment:
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 grammar of the language.-
interp
, which consumes an abstract syntax expression (as returned by theparse
function) and returns aCFWAE-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
- Arithmetic
-
CFWAE includes binary addition, multiplication, subtraction, and division. There is no desugaring in this assignment: All of these features are in the core language CFWAE. The binary operations are defined in terms of their Racket counterparts.
Evaluation should signal an error for non-numeric values passed to binary arithmetic operations.
In place of having separate rules (and syntactic forms) for
+
,-
,*
, and/
, we will define a single syntactic rule for all binary arithmetic operators. Parse these into abinop
datatype variant (shown in the data definition below). Define a table that maps operator names (symbols) to actual functions (Racket procedures) that perform the corresponding operation. Having a single rule like this, accompanied by a table, makes your language easier to extend: once you have modified your parser and interpreter once to support binary operators, you won't need to touch either one to add any number of new ones. - Multi-Armed With
-
with
is a binding form, similar tolet
in other languages (andlocal
in Racket). Each identifier bound by thewith
expression is bound only in its body. There will be zero or more identifiers bound by eachwith
expression. If there are multiple bindings of the same identifier in a singlewith
expression’s bindings list, your parser should halt with an error message (sointerp
never sees multiple bindings of the same identifier). An example:{with {{x 2} {y 3}} {with {{z {+ x y}}} {+ x z}}}
will evaluate to
7
, while{with {{x 2} {x 3}} {+ x 2}}
will halt with an error message.
- 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 grammar below. Note thatif0
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.
- 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 with the same deferred substitutions. An example of a multi-argument fun:{{fun {x y} {* x y}} 2 3}
This evaluates to 6.
As you did for multi-armed
with
, you must ensure that the arguments to a function have distinct names.
Syntax of CFWAE
The syntax of the CFWAE language with these additional features can be captured with the following EBNF:
<CFWAE> ::= <num> | {+ <CFWAE> <CFWAE>} | {- <CFWAE> <CFWAE>} | {* <CFWAE> <CFWAE>} | {/ <CFWAE> <CFWAE>} | <id> | {if0 <CFWAE> <CFWAE> <CFWAE>} | {with {{<id> <CFWAE>} ...} <CFWAE>} | {fun {<id> ...} <CFWAE>} | {<CFWAE> <CFWAE> ...} where an id is not +, -, *, /, with, if0 or fun.
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}
Testing Your Code
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. We will not give full credit to untested functionality, even if it is correct! Refer to the syllabus for style requirements.
Your parser and interpreter must detect errors and explicitly signal them by
calling (error ...)
. We will consider an error raised internally
by Racket to be a bug in your code.
For example, Racket signals a "divide by zero" error if you
attempt to evaluate (/ 1 0)
. Since we use Racket's division
function to implement division in CFWAE, you may be tempted to leave it to
Racket to signal division by zero errors for you. However, you must signal the
error yourself by explicitly testing for division by zero before calling
Racket's division procedure.
test/exn
. test/exn
tests
for errors, but only succeeds on errors that you explicitly signal.
Support Code
Your code must adhere to the following template, without any changes:
#lang plai (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?))]) (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 : CFWAE -> CFWAE-Value ;; This procedure interprets the given CFWAE and produces a result ;; in the form of a CFWAE-Value (either a closuerV or a numV) (define (interp expr) ...)
The support code is here: xinterp.rkt
File Structure and Handin
You should implement everything in one file called "xinterp.rkt"
.
You can download an assignment binary from here, which you can use to generate a grade
report. Download the zip bundle that matches your architecture, and unpack it.
From the directory that "xinterp.rkt"
is in, run:
> debian-dist/bin/assignment2-debian --report > myreport.txt
OR, you can use the --report-to-file
option and provide and
explicit file argument (this is useful from the Windows shell, which has issues
with output redirection):
> win32-dist\assignment2-win32.exe --report-to-file myreport.txt
At the handin link, turn in:
- Your grade report (don't forget the .txt), and
- A single Racket file (including the definition of
parse
,interp
, and your test cases)
Update: We're working on new grading scripts for those who want to use the typed version of PLAI, located here. These are intended to be a strict upgrade of the untyped version (they will grade either untyped or typed xinterp.rkt files), but are not guaranteed to work perfectly. Currently, we only have the Debian version compiled and ready to go; do try it if you want to program in the typed version of the language, and let us know if you run into any problems.
Note regarding grading: We will look at code style and test case coverage for Brown students' submissions. You will not get credit for features that you don't test, and your code should adhere to the style and testing guidelines under Coding and Testing in the syllabus. We will provide you with feedback on how you can improve your testing and code style. Online students: We don't anticipate having the resources to provide you with this feedback; your successful completion of this assignment will be determined by the grade report only.