Assignment 2: Desugaring (project)
Your task on Assignment 2 is to write a desugaring pass for the class project. You are building a compiler pass for an input language with a number of forms including exceptions, dynamic-wind, call/cc, first-class primitives, etc. The pass yields terms in a small core language including only a let form, the lambda-calculus, conditionals, set!, call/cc, and explicit primitive-operation forms.
Input language:
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) |
Output language:
e ::= (let ([x e] ...) e) |
| (lambda (x ...) e) |
| (lambda x e) |
| (apply e e) |
| (e e ...) |
| (prim op e ...) |
| (apply-prim op e) |
| (if e e e) |
| (set! x e) |
| (call/cc e) |
| x |
| (quote dat) |
The assignment 2 starter contains a file utils.rkt which provides some useful functions and a specification for the input and output languages in the form of two predicates scheme-exp? and ir-exp?. You can also use the functions eval-scheme and eval-ir to evaluate programs that are in each of these languages.
Your job is to write your own set of unit tests and define a translation function desugar, provided in a file desugar.rkt, that simplifies programs satisfying scheme-exp? into programs satisfying ir-exp? that are (if they don’t error) semantically equivalent according to eval-scheme and eval-ir.
Although basic forms and primitive operations can be shadowed in Scheme/Racket, you may assume tests never redefine or shadow symbols matching either prim? or reserved? (also from utils.rkt). Handling this properly is worth extra credit (see below).
Getting started
For your assignment you may use the stubbed out code and tests linked above. A small number of tests are provided, but to do well on the assignment you will mostly need to write your own tests. You should turn in a desugar.rkt file that provides a desugar function. It may be helpful to require the utils.rkt module and make use of functions like prim? and prims->list.
#lang racket |
|
; by First Last |
|
(provide desugar) |
(require "utils.rkt") |
|
(define (desguar-aux e) |
(match e ...)) |
|
(define (desugar e) |
; wrap e in any special functions or definitions you need |
; and then pass it into a helper function that performs the |
; case-by-case translation recursively |
(desugar-aux (wrap-with-definitions e))) |
|
; I, First Last, pledge on my honor that I have not given or received any unauthorized |
; assistance on this project. |
|
I recommend you get started by writing simple cases for forms that are both in the source language and target language (such as let, lambda, and if), testing that you can pass very simple inputs that are in both languages first. Then you can build up to desugaring forms like unless and cond.
Some advice
(NEW) See the end of the CEK slides (refresh to get latest version) or the note on Piazza for the implementation of dynamic-wind and call/cc. The slides also show an outline for the implementation of raise and guard.
I recommend you get started by supporting forms that match ‘(,(? prim?) ,es ...) and ‘(quote ,(? datum?))—
this will be enough to pass test start-0 which should desguar to ’(prim + ’2 ’3). Then you can support trivially recuring over all the other forms in the target language (e.g., for a pass t, (t ‘(if ,e0 ,e1 ,e2)) yields ‘(if ,(t e0) ,(t e1) ,(t e2))) which will be enough to support test start-1. From here you can work on writing new tests and extending your desugarer to support other features of the input language. Any *.scm file added to tests/public/, tests/release/, or tests/secret/ will be treated as a test. Add a file like mytest.scm and run racket tests.rkt mytest to test it.
Remember when writing tests that all datums must be explicitly quoted (except in the case form). This means that (+ 1 2) is an invalid input, but (+ ’1 ’2) is valid.
The function gensym can be used to generate fresh variable names. This appends a number to the symbol provided to produce a fresh symbol; e.g., (gensym ’tmp) => ’tmp3276.
Use (prim->list) to obtain a list of primitives you can use. You can use (prim void) to return a void value.
You will need to desugar all primitive operations into explicit prim and apply-prim forms. So for example, you must desugar primitives passed as arguments into lambdas (eta-expanding them). E.g. ’((lambda (f) (f ’2 ’3 ’4)) +) could desugar into ’((lambda (f) (f ’2 ’3 ’4)) (lambda args (apply-prim + args))).
It doesn’t matter how you encode promises as long as your promise? function distinguishes them properly (you might use a unique tag inside a list to ensure this). Don’t emit ‘(prim promise? x), but replace it with code that checks your own encoding of promises. You also need to ensure that the value forced is saved; try vector-set! for this.
At first you may desugar call/cc directly into call/cc, but ultimately a correct desugaring of call/cc will require cooperation with dynamic-wind as we’ll discuss in class.
You will need to turn lambdas such as (lambda (a . b) ...) into lambdas that take an argument list such as (lambda t (let ([a (car t)][b (cdr t)]) ...))
Extra Credit
Extra credit opportunity: You do not need to correctly handle shadowing of primitive operations or language
forms such as let, letrec, or cons. You may assume that none of the binding forms in input programs will
redefine these identifiers. There are several extra-credit release tests which do—
There is also a test ec-letcc that will test a (let/cc x e) expression you can implement for a few extra points. If trying this last form, download the latest version of utils.rkt so scheme-exp? will accept it. (Each of the 5 extra credit tests are worth +3%.)