Assignment 3, CSC430, Winter 2011

1 Goal

Implement an interpreter for a first-order language with a rich enough set of data types to write a meta-interpreter on top of it.

2 Guidelines

2.1 Contracts & Test Cases

For this and all remaining assignments, every function you develop must come with the following things:

• A commented header line that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two.

• A commented contract line that gives the types of the inputs and the output. The contract should have the form <in-type> ... -> <out-type>. So, for instance, a numerical square function might have the contract line:
    ; number -> number

• Test cases. A function without test cases is incomplete. Write the test cases first, please.

2.2 Handling errors

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 CF1WAE, 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.

Note that you may assume that your contracts are respected. That is, if your interp function’s contract indicates that it expects a CF1WAE, you do not need to worry about miscreants that call it with a number or a string or another surprising value.

2.3 Language Level & File Format

Your solution should take the form of a single file. Solve each problem separately, and make sure that each solution appears in a separate part of the file, with comments separating each problem’s solution.

Hand in your solution using the handin server. For help with the handin server, please see the course web page.

3 Extended Interpreter

Write a parser and interpreter for the F1WAE language we’ve discussed in class, extended with the language features described below. Your interpreter should have eager application semantics and use deferred substitution. Call the new language CF1WAE (conditionals, first-order functions, with, and arithmetic expressions).

4 Changes to the Existing Framework

First off, you will need two parsing functions: one to parse expressions, and one to parse function definitions. The function parse-exp must consume an expression in the language’s concrete syntax and return the abstract syntax representation of that expression. The function parse-fun must consume a function definition and produce a FunDef.

Next, for this assignment the binop variant is joined by the unop variant, for use in representing unary operators. The operator is represented using a symbol.

Also, since this assignment features a number of different kinds of primitive values (numbers, booleans, strings, and null), the CF1WAE definition includes variants for each of these.

Finally, since this assignment defines an interpreter that can return both simple and compound values (using pairs), the result of the interpreter is no longer a simple number; now, it returns a CF1WAE-Value, which can be a numV, a strV, a boolV, an mtV, or a pairV.

You must signal an error for a reference to an unbound variable. These do not need to be caught by the parser; you may signal the error in the interpreter.

I recommend that you make these extensions and test them thoroughly before moving on.

5 Features to Implement

5.1 Booleans

Your language should now include the boolean values, true and false, the boolean library functions, and, or, and the unary function not.

From the parser’s standpoint, these names should all be treated as keywords. That is, the parser will recognize true, false, explicitly, and they will not be recognized as variable names. The parser should produce a bool containing the corresponding Racket value, as mentioned above.

I recommend that you add booleans to your language and test this extension thoroughly before moving on.

5.2 Comparisons

You must add the primitive functions <= and equal? to your language.

• equal? : returns true if the two arguments are equal. Use Racket’s equal? to perform the comparison.

• <= : signals an error if either of the two arguments is not a number, otherwise returns true if the first number is less than or equal to the second, false otherwise

Again, I recommend that you add comparison functions to your language and test them before moving on. Do you detect a pattern here?

5.3 Conditionals

Next, we want a conditional. We’ll use a switch that’s not unlike Java’s. Specifically, a switch contains an expression to dispatch on, and a sequence of clauses, where each clause contains a value to match against and a result expression to use if the value matches. Finally, every switch must contain an else clause to catch values that don’t match any of the clauses.

Your evaluator should evaluate a switch by first evaluating the dispatch expression, then sequentially evaluating the match expressions one by one until reaching one that is equal? to the result of the dispatch expression, or falling through to the else case. The result is then the result of evaluating the corresponding result expression.

A simple example:

'{switch {get-fruit}

["apple" => "good choice!"]

["banana" => "excellent choice!"]

["durian" => "Hmm, I'm not sure your taxi driver is going to like that."]

[else "I don't recognize your so-called 'fruit'."]}

I recommend that you add switch to your language and test this extension thoroughly before moving on.

5.4 Pair and Null

Next, we want to be able to represent larger pieces of data in our target language. We’ll do this by introducing the built-in pair operator, that accepts two values and returns a pairV containing the two (this would be a good time to uncomment the pairV variant of the F1WAE-Value definition). In other words, pair is exactly like Racket’s cons.

We also need a way to end our lists, so we’ll add a null value. A null in the program should parse into an (mt).

Please implement and test these extensions before moving on.

5.5 Strings

The last kind of data we want to add to our language is strings. So, for instance, the parser should accept the string "abc", and produce (str "abc").

5.6 Multi-argument fun

As you did for multi-armed with, you must ensure that the arguments to a function have distinct names.

You must signal an error if a function is applied to the wrong number of arguments. You must also signal an error if a call is made to a nonexistent function.

5.7 A Tiny Meta-Interpreter

At this point, our target language is now powerful enough... to write an interpreter!

You must define the constant target-interp. This must be a function definition for the name meta-interp that, when parsed with parse-fun, produces a function that consumes an s-expression of pairs and nulls in the target language and produces the numeric answer. This is called a "meta-interpreter". To keep it simple, this meta-interpreter only needs to handle expressions containing numbers, plus, and minus. Here’s an example of a test case that your target-interp needs to handle, corresponding to the evaluation of (+ (- 6 3) 13) :

(interp (parse-exp '{meta-interp

{pair "+"

{pair

{pair "-"

{pair 6

{pair 3 null}}}

{pair 13 null}}}})

empty

(list (parse-fun target-interp)))

5.8 Syntax of CF1WAE

The concrete syntax of the CF1WAE language with these additional features can be captured with the following EBNF:

CF1WAE		=		num
		|		string
		|		true
		|		false
		|		null
		|		{operator CF1WAE *}
		|		id
		|		{switch CF1WAE [CF1WAE => CF1WAE] * [else CF1WAE]}
		|		{with {{id = CF1WAE} *} CF1WAE}
		|		{id CF1WAE *}

operator		=		+
		|		-
		|		*
		|		/
		|		and
		|		or
		|		equal?
		|		<=
		|		pair
		|		not
		|		number?
		|		pair?
		|		string?
		|		null?
		|		first
		|		rest

... where an id is not true, false, with, switch, else, or one of the operator names.

The concrete syntax of a function definition is provided by this EBNF:

CF1WAE-Fundef

=

{fun id {id *} CF1WAE}

5.9 Syntax Notes:

If a with expression or a function definition has duplicate identifiers, we consider it a syntax error. Therefore, such errors must be detected in parse. For example, parsing the following expression and fundef must signal errors:

{with {{x 10} {x 20}} 50}

{fun f {x x x} {+ x 3}}

6 Support Code

Your code must adhere to the following template; each of the given functions and definitions must appear in your program. Naturally, you’ll have to add functions of your own, as well.

; represents an expression

(define-type CF1WAE

[num (n number?)]

[str (s string?)]

[bool (b boolean?)]

[mt]

[unop (op any/c) (arg CF1WAE?)]

[binop (op any/c) (lhs CF1WAE?) (rhs CF1WAE?)]

[with (lob (listof Binding?)) (body CF1WAE?)]

[varref (name symbol?)]

[switch (val CF1WAE?) (clauses (listof SClause?)) (elseval CF1WAE?)]

[app (f symbol?) (args (listof CF1WAE?))])

; represents a function definition

(define-type FunDef

(fundef (name symbol?) (params (listof symbol?)) (body CF1WAE?)))

; represents a binding in a with expression

(define-type Binding

[binding (name symbol?) (named-expr CF1WAE?)])

; represents a 'switch' clause

(define-type SClause

[clause (patval CF1WAE?) (result CF1WAE?)])

; An environment should be represented as an immutable hash table

; represents a possible result of evaluation

(define-type CF1WAE-Value

[numV (n number?)]

[strV (s string?)]

[boolV (b boolean?)]

[mtV]

[pairV (first CF1WAE-Value?) (rest CF1WAE-Value?)])

; parse-exp : s-exp? -> CF1WAE?

; This procedure parses an s-expression into a CF1WAE

(define (parse-exp exp)

...)

; parse-fun : s-exp? -> FunDef?

; This procedure parses an s-expression into a FunDef

(define (parse-fun exp)

...)

; interp : CF1WAE? immutable-hash-table? (listof FunDef?) -> CF1WAE-Value?

; This procedure interprets the given CF1WAE in the given

;  environment with the given function definitions and

;  produces a result in the form of a CF1WAE-Value

(define (interp exp env defs)

...)

7 Using Immutable Hash Tables

Here’s an example of a short program that uses immutable hash tables. These should be all the primitives you need.

; import the immutable hash table creation function:

(require (only-in mzscheme make-immutable-hash-table))

; create a new empty immutable hash table:

(define a (make-immutable-hash-table '()))

; define b as a extended with a map from 'k to 'v

(define b (hash-set a 'k 'v))

; does b have a mapping for key 'k? Yes, it does.

(hash-ref b 'k)

; does a have a mapping for key 'k? No, it does not.

(hash-ref a 'k)

For posterity, note that the require here won’t be needed in version 5.1 and later of DrRacket, and the creation primitive will be named differently.

8 Getting Started

In order to make sure that you’re able to hand in early and often, let me suggest the following work pattern.

1. Use the given define-types to replace the ones in your working Program 2.

2. Use block comments (#| ... |#) to comment out the rest of your program.

3. Submit.

4. Uncomment the parser and its test cases.

5. Put in stubs for the new forms.

6. Submit.

7. Et Cetera....