Assignment 7, CSC430, Fall 2015

1 Goal

Add a pattern-matching macro mechanism to the language of assignment 3.

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. The header lines must include input and output types.

• 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 class, 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.

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 Macro Definition

For this assignment, we’re starting with the LOOI3 language; no classes, no mutation, no store-passing. We want to add a simple macro-definition language. It will be based on Racket’s let-syntax, and we’ll call it let-stx.

In this system, a name will be bound to a series of clauses, where each has a pattern and a template. Within the scope of the let-syntax, any use of the macro is matched against the macro’s defined clauses; the expander picks the first clause that matches, and applies the substitutions to the associated template.

Additionally, the expander will perform renaming of func-bound variables. Note that since our LOOI5 language doesn’t have quote, we don’t need to worry about preserving the original name, and we can just pick a new name formed by adding an underscore and a number to the original name. I do not require you to ensure that the name is fresh (that is, doesn’t appear in the rest of the program), but ... it would be a better language if you had this property.

3.1 First Example

Here’s an example like one we saw in class:

{let-stx {or = {[{or a b} => {{func temp {if temp temp b}} a}]}}

{or false {+ 12 1}}}

This should expand into {{func temp_0 {if temp_0 temp_0 {+ 12 1}}} false}. It should evaluate to 13, because it’s the first non-false answer.

Here’s how it works.

First, expansion is a separate pass; it happens before parsing.

The expander looks at the expression, and sees that it’s a let-stx. It adds the binding from or to the given transformer (pattern and template) in the expander environment, and then continues expanding.

It encounters the or use, looks in its environment, and sees that or is bound to a macro use. It then considers each pattern (in this case there’s only one), finds that it matches, and then performs substitution; every a in the template is replaced by false, and every b is replaced by {+ 12 1}.

Then, the resulting expression is expanded again. The expression is not a macro use or a function definition, so we expand each of the two pieces. Of these pieces, the left one turns out to be a function definition, with a variable temp. We pick a fresh name, possibly temp_0, and rename all uses of temp to temp_0. There are no other function definitions or macro uses in the expression, so it’s returned unchanged.

3.2 Semantics of Syntax Bindings

The expander transforms one s-expression into another. Expressions that are not macro definitions or macro uses are unchanged by the expander.

The let-stx form has this shape:

{let-stx {name = {[pat => template] ...}} body}

...where name is an identifier, pat and template are s-expressions, and body is an s-expression. The name is the newly bound macro’s name. each [pat => template] clause contains a pattern and a template.

Within the body, macro uses look like applications of the macro’s name; that is, it matches the pattern {SYMBOL ANY ...}, where the SYMBOL matches the macro’s name.

When the expander encounters a macro use, it uses the macro’s clauses to expand the macro. More specifically, it tries each pattern in turn. When the matcher finds a pattern that matches, it uses the corresponding template to rewrite the macro use.

So, for instance, if a macro with has only one clause, with the pattern {with {n r} b} and the template {{func n b} r}, and a use has the shape {with z 14}, the pattern match would fail (because the pattern would try to match the pattern {n r} against the user code z). If, on the other hand, the use was {with {f 19} {+ f 2}}, then the pattern would match, and the pieces n, r, and b would be plugged into the template to yield the expanded expression. Finally, note that the expansion may not be sensible; if the use of the macro reads {with {{+ 9 4} x} 12}, this will expand successfully into {{func {+ 9 4} 12} x}, which will signal an error at parse time. It’s not your job to detect these at expansion time.

3.3 Implementation Details

Implementing the expander will require a number of helper functions. First, the expander will need to maintain an environment, indicating which macros are in scope. Each let-stx will add a binding to this environment.

When you find a macro use, you will probably make a call to an expand-macro helper function, which will probably try each macro clause using a try-macro-clause function. This in turn will probably have a try-pattern-match function, and a template-subst function. This may call a template-subst1 function.

Expanding a func requires generating a fresh variable name, and you’ll probably need a helper function for this. The complexity of this process depends on how careful you are about generating truly fresh names.

4 Change to the semantics of If

There is one small change to the meaning of if; it should admit any value, not just a boolean, as the result of its test expression, and it should evaluate its then clause for any test value other than false.

5 Removal of with

Now that we have let-stx, there’s no need for a with rule in our parser. Get rid of it!

5.1 Syntax of LOOI5

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

... where an id is not true, false, let-stx, =, =>, if, func, let-stx, or one of the operator names, but an any-id is any identifier at all.

5.2 Syntax Notes:

Note that the last rule is the one for applications. Also, note that all of the ‘...’s are to be read as *zero* or more. That is, zero is legal in these cases.

6 Interface

Make sure that you include the following functions, and that they match this interface:

(define (top-eval [s : s-expression]) : string

(serialize (interp (parse (expand s)) empty-env)))

Your body can be different if you really want, but the types must match these.