Assignment 7, CSC430, Winter 2017

1 Goal

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

2 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 type declaration, specifying the input and output types.

• 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 typed/racket language. If you still haven’t seen them, you might be interested in these Hints on Using Typed Racket in CPE 430.

Your test cases must use the check-equal?, check-=, or check-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.1 Handling Errors

All of your error messages must start with the string "PHYM: ". Essentially, this allows my test cases to distinguish errors correctly signaled by your implementation from errors in your implementation. To be more specific: any error message that doesn’t contain the string "PHYM" will be considered to be an error in your implementation.

2.2 Progress Toward Goal comment

Graders are happier when they know what to expect. Your final submission should start with a short one- or two-line comment indicating how far you got through the project. Ideally, this would just be: “Full project implemented.” But if you only implemented, say, squazz and blotz, and didn’t get to frob or dringo, please indicate this in the comment, so that we don’t spend all our time searching for bits that aren’t there.

3 Macro Definition

For this assignment, we’re starting with the PHYM3 language, optionally enriched with the top-level environment setup of early PHYM4. In either case: 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.

For this assignment, hygiene is entirely optional. If you add hygiene to your system, you may be able to pass the Program7Elite tests. However, you can receive full credit for the assignment without adding any hygiene whatsoever.

Note: for all of the examples below, adding hygiene will mean that your resulting s-expressions may contain different but equivalent names. For instance, you may rename the variable temp to temp_0 everywhere in the first example. As long as the resulting expression evaluates correctly, any renaming is fine.

3.1 First Example

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

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

{or false {+ 12 1}}}

This should expand into {{lam {temp} {if temp temp {+ 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. 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.

When does a pattern match a use? The rules are these: if the pattern is a symbol, it matches any use. If a pattern is a list and the use is also a list of the same length, then the pattern matches if and only if the elements of the pattern match the elements of the use. If the pattern is a number or a string, it’s an illegal pattern and you must signal an error.

So, for instance, if a macro with has only one clause, with the pattern {with {n r} b} and the template {{lam {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 {{lam {{+ 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.

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 var

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

5.1 Syntax of PHYM7

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

... where an id is not let-stx, =, =>, if, lam, 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-interp [s : Sexp]) : string

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

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