Assignment 8, CSC430, Fall 2022

1 Goal

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

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 (possibly inline), 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 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.

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 contain the string "JYSS". 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 "JYSS" 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 JYSS5 language. 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.

3.1 First Example

Here’s a simple example:

{let-stx {or = [{or a b} => {{proc {t1 t2} {if t1 t1 t2}} a b}]}

{or false {equal? 13 13}}}

This should expand into {{proc {t1 t2} go {if t1 t1 t2}} false {equal? 13 13}}. It should evaluate to true.

Here’s how it works.

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

(Note: as we discussed in class, it might be more accurate to say that it happens between read and parse.)

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 {equal? 13 13}.

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. The [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 clause to expand the macro. If the pattern doesn’t match the use, it signals an error.

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 {{proc {n} go 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 {{proc {{+ 9 4}} go 12} x}, which will signal an error at parse time. It’s not your job to detect these at expansion time.

Macro uses can expand into macro uses; your expander should recur on the result of a successful expansion.

Macro definitions can shadow other outer definitions. When this happens, the new patterns and templates are the only legal ones; the expander should not "fall through" to the outer macro definition if none of the clauses from the inner one match; instead, your expander should signal an error.

It should be possible for a macro definition to shadow any identifier, even let-stx or proc.

To simplify the assignment, you are not required to differentiate binding and expression positions; In other words, if a programmer writes {proc {a b c} go 13} and a is bound to a macro in the macro environment, it’s fine to go ahead and perform the expansion, even though that makes no sense and is an obviously terrible idea.

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-one-macro helper function, which will probably use a try-pattern-match function, and a template-subst function.

4 Removal of var

Now that we have let-stx, there’s no need for a var rule in our parser. Get rid of it! If you want to use it in your programs, just re-introduce it as a let-stx binding.

4.1 Syntax of JYSS8

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

... where an id is not let-stx, =, =>, if, proc, go, or let-stx, but an any-id is any identifier at all.

4.2 Syntax Notes:

Note that all of the ‘...’s are to be read as *zero* or more. That is, zero is legal in these cases.

5 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.