Assignment 2:   Desugaring (project)
Getting started
Some advice
Extra Credit
6.10

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

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—such as ec-shadowing-0and you can try satisfying them for bonus points. I recommend you write a version which works for other tests first and only then extend it to pass these tests by passing an environment of bound ids.

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%.)

 

Web Accessibility