Assignment 2, CSC430, Winter 2011

1 Guidelines

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.

For this assignment, you must develop your solutions using the

#lang plai

language level. Your test cases must use the (test ...) or the (test/exn ...) forms.

Your solution should take the form of a single file. Solve each problem separately, ands 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.

2 Rudimentary Interpreter

Write a parser and interpreter for the WAE language ([1]) we discussed in class. The textbook can be of great assistance in this part of the assignment; it provides the beginnings of a parser, an abstract syntax datatype and an interpreter.

Once you’ve written and tested the parser and interpreter for WAE, extend the language with these features:

2.1 Binary arithmetic operators

In place of having separate rules for + and -, define a single syntactic rule for all binary arithmetic operators. Parse these into a binop datatype variant. 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. To demonstrate this, define multiplication and division (using * and / to represent them in the language’s concrete syntax).

2.2 Multi-armed with

Each identifier bound by the with expression is bound only in its body. There will be zero or more identifiers bound by each with expression. If there are multiple bindings of the same identifier in a single with expression’s bindings list, your interpreter should halt with an error message. 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.

The syntax of the WAE language with these additional features can be captured using EBNF notation ([2]):

WAE	=	num
	\|	{+ WAE WAE}
	\|	{- WAE WAE}
	\|	{* WAE WAE}
	\|	{/ WAE WAE}
	\|	{with {{id = WAE}*} WAE}
	\|	id

where an id is not +, - , *, / , or with . You should turn in a single Racket program containing all of the code needed to run your parser and interpreter. Implement the function parse, which consumes an expression in the language’s concrete syntax and returns the abstract syntax representation of that expression. Also implement the function interp , which consumes an abstract syntax expression (as returned by the parse function) and returns a racket number.

[1] Remember, the WAE language has numbers, two arithmetic operators (+, -), identifiers and with expressions. Of course, to handle identifiers and with expressions you’ll have to implement substitution. Finally, both the concrete syntax and abstract syntax are specified by the WAE language’s BNF (which can be found in the textbook).

[2] The textbook introduced you to BNF. An extension of this notation, called EBNF (Extended Backus-Naur Form), provides three additional operators:

? means that one or more symbols to its left can appear zero or one times.
* means that one or more symbols to its left can be repeated zero or more times.
+ means that one or more symbols to its left can appear one or more times.

2.3 Support Code

Your code must adhere to the following templates, without any changes:

  (define-type WAE
    [num (n number?)]
    [binop (op any/c) (lhs WAE?) (rhs WAE?)]
    [with (lob (listof Binding?)) (body WAE?)]
    [varref (name symbol?)])

  (define-type Binding
    [binding (name symbol?) (named-expr WAE?)])

  ; parse : s-exp -> WAE
  ; Accepts an s-expression and generates the corresponding WAE
  (define (parse sexp)
    ...)

  ; interp : WAE -> number
  ; Accepts a WAE representation of an expression and computes
  ; the corresponding numerical result
  (define (interp expr)
    ...)

  ; subst : symbol? number? WAE? -> WAE?
  ; Accepts a variable name, a number, and an expression, and
  ; replaces every free instance of the variable name with the
  ; given number
  (define (subst from to in)
    ...)

3 Acknowledgments

Thanks to Shriram Krishnamurthi and Greg Cooper for these assignments.