Assignment 5: Top level, defines, quasiquote, and pattern matching
Your task on assignment 5 is to round out the top-level for your compiler project by adding implicit begin forms explicitly, quoting all datums, desugaring defines nested in such begin forms to a letrec*, desugaring quasiquote and unquote, and (optionally) implementing a simple pattern matcher.
This assignment is somewhat smaller than previous assignments, but has some tricky components. It can be effectively completed (including all extra credit) in around 100-120 lines of Racket.
Input language:
e ::= (define x e) |
| (define (x x ... defaultparam ...) e ...+) |
| (define (x x ... . x) e ...+) |
| (letrec* ([x e] ...) e ...+) |
| (letrec ([x e] ...) e ...+) |
| (let* ([x e] ...) e ...+) |
| (let ([x e] ...) e ...+) |
| (let x ([x e] ...) e ...+) |
| (lambda (x ... defaultparam ...) e ...+) |
| (lambda x e ...+) |
| (lambda (x ...+ . x) e ...+) |
| (dynamic-wind e e e) |
| (guard (x cond-clause ...) e ...+) |
| (raise e) |
| (delay e) |
| (force e) |
| (and e ...) |
| (or e ...) |
| (match e match-clause ...) |
| (cond cond-clause ...) |
| (case e case-clause ...) |
| (if e e e) |
| (when e e ...+) |
| (unless e e ...+) |
| (set! x e) |
| (begin e ...+) |
| (call/cc e) |
| (apply e e) |
| (e e ...) |
| x |
| op |
| (quasiquote qq) |
| (quote dat) |
| nat | string | #t | #f |
|
cond-clause ::= (e) | (e e e ...) | (else e e ...) |
case-clause ::= ((dat ...) e e ...) | (else e e ...) |
match-clause ::= (pat e e ...) | (else e e ...) |
; in all cases, else clauses must come last |
dat is a datum satisfying datum? from utils.rkt |
x is a variable (satisfies symbol?) |
defaultparam ::= (x e) |
op is a symbol satisfying prim? from utils.rkt (if not otherwise in scope) |
op ::= promise? | null? | cons | car | + | ... (see utils.rkt) |
qq ::= e | dat | (unquote qq) | (unquote e) | (quasiquote qq) |
| (qq ...+) | (qq ...+ . qq) |
;; (quasiquote has the same semantics as in Racket) |
pat ::= nat | string | #t | #f | (quote dat) | x | (? e pat) | (cons pat pat) | (quasiquote qqpat) |
qqpat ::= e | dat | (unquote qqpat) | (unquote pat) | (quasiquote qq) |
| (qq ...+) | (qq ...+ . qq) |
;; (same semantics as Racket match for this subset of patterns) |
Output language (i.e., the input for assignment 2, the desugar function):
e ::= (letrec* ([x e] ...) e) |
| (letrec ([x e] ...) e) |
| (let* ([x e] ...) e) |
| (let ([x e] ...) e) |
| (let x ([x e] ...) e) |
| (lambda (x ...) e) |
| (lambda x e) |
| (lambda (x ...+ . x) e) |
| (dynamic-wind e e e) |
| (guard (x cond-clause ...) e) |
| (raise e) |
| (delay e) |
| (force e) |
| (and e ...) |
| (or e ...) |
| (cond cond-clause ...) |
| (case e case-clause ...) |
| (if e e e) |
| (when e e) |
| (unless e e) |
| (set! x e) |
| (begin e ...+) |
| (call/cc e) |
| (apply e e) |
| (e e ...) |
| x |
| op |
| (quote dat) |
|
cond-clause ::= (e) | (e e) | (else e) ; in all test cases |
case-clause ::= ((dat ...) e) | (else e) ; else clauses always come last |
dat is a datum satisfying datum? from utils.rkt |
x is a variable (satisfies symbol?) |
op is a symbol satisfying prim? from utils.rkt (if not otherwise in scope) |
op ::= promise? | null? | cons | car | + | ... (see utils.rkt) |
The match form shown in the grammar above is optional and not required; see the section on extra credit below. Likewise you do not need to handle nested quasiquotes and unquotes properly, or functions with default parameters, but may for extra credit.
The assignment 5 starter contains an updated utils.rkt. The function read-begin will read from a specified port or the default port (as read does) until all expressions are read and then wraps them in a top-level begin form. A file containing just "5 6" will be read in as ’(begin 5 6) by this function. The function eval-top-level will take a top-level-scheme input and evaluate it. As before, you may assume all inputs will be valid.
Some unsorted advice for assignment 5:
Be careful to handle directly nested begin forms correctly. Check how these work using Dr. Racket.
Be careful not to bind pattern variables in match forms when the pattern does not match but only when it does.
When generating a sequence of let bindings for successfully matched patterns, untangling nested patterns into a flat sequence of let forms can be done in a manner similar to ANF conversion.
Extra credit opportunities: There are several extra credit tests that check nested quasiquotes (e.g., such as “,,x), for functions with default parameters (e.g., (define (inc a [b 1]) (+ a b))), and for the pattern-matching form defined above. Functions with default parameters must have these parameters at the end of the parameter list without an interspersed non-defaulting parameter. Match clauses that fail should raise an exception that can be caught with a guard, but none of the tests will check what this exception object is comprised of (i.e., you could simply raise a boolean if you wanted, or a useable error message if you prefer).