# Desugaring, Promises, Exceptions #
This project is the start of a multi-stage ‘nano-pass’ compiler. For
the next few projects, you will be starting with an input language
defining a set of features you will implement. You will then translate
(compile) those features into an output language–sometimes a subset
of the language you started with. In each of these projects, your
input and output will both be S-expressions that satisfy some
predicate we define in the starter code.
In this assignment, you will take as input a large language that
comprises a large subset of Scheme. You will transform this into a
smaller subset of Scheme in preparation so that future passes of your
compiler will be able to deal with a smaller set of language forms.
The input language includes a number of forms: exceptions, call/cc,
first-class primitives, etc. After the pass completes, a core language
including the lambda calculus, let-binding, conditions, set!, call/cc,
and explicit primitives operations is yielded. This encompasses a wide
rane of behavior in the R6RS Scheme standard, but leaves out a few
important things–exceptions, dynamic-wind, and pattern matching are
all things we will skip for now. You may choose to add exceptions or
dynamic-wind into your compiler as a final project.
# Input And Output Grammar #
The input grammar is a large subset of the Scheme Programming
Language. For this project, you will need to understand all of these
forms. It is impossible to write a compiler without understanding the
language you are compiling–whenever you get stuck and don’t
understand a particular form, please look it up in the official R6RS
report, which you can find at the following URL:
https://small.r7rs.org/attachment/r7rs.pdf
I (Kris, the instructor) am happy to help you understand any of these
forms as well. Please make a note of each form you do not understand
and we will discuss it in class. Note that for this project, you do
not need to desugar call/cc, but you must support it in your input
language–your compiler should simply compile the argument of the
call/cc but leave the call/cc in tact to be handled in subsequent
passes.
“`
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)
| (if e e e)
| (and e …)
| (or e …)
| (when e e)
| (unless e e)
| (begin e …+)
| (cond cond-clause …)
| (case e case-clause …)
| (delay e)
| (force e)
| (call/cc e)
| (set! x 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 output is a much smaller langauge, desugared to allow us to focus
on the core aspects of compilation in subsequent passes.
“`
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)
“`
# Your code
You will be implementing parts of two main functions: `desugar` and
`desugar-aux`. It is occasionally helpful as a compiler author to
implement builtin functions so that you may use those functions in
other pieces of your compiler. For example, my implementation wraps
the expression to define a function `promise?` that I then use in my
subsequent implementation of `force` by generating a call to
`promise?`.
The bulk of your work will be defining `desugar-aux`, which pattern
matches the input expression to transform it into an output expression
that satisfies the output grammar.
You will probably also want to read utils.rkt, which details the full
implementation of the input and output grammar, along with a few
helpful routines you may use.
# Redundancy #
Many languages provide redundant operators. Because there are multiple
ways to do something, the programmer can choose the best way for their
task. However, having a large syntax only complicates a compilers (and
a compiler writer’s!) job. By “desugaring” the language, we can make
future passes much more focused so they need focus only on the core
essence of the language.
For example, the `when` expression in the input language is similar to
`if`, but defaults to returning void when the condition is false. In
other words, the translation is:
“`
(where c t) => (if c t (void))
“`
This can wholly remove the `where` expression without loss of
information to the compiler. This project requires understanding how
each part of the old grammar can be converted into the new, and then
writing code to transform it.
# Promises #
Promises are a way to store values to be computed at some point in the
future. Their API involves a few special forms:
“`scm
(define p (delay (long-computation)))
(println (force p)) ; long computation computed here
(println (force p)) ; will NOT be computed a second time, same value is returned.
“`
To desugar promises, you can implement them with the `vector`
primitive API, and a
[‘thunk’](https://en.wikipedia.org/wiki/Thunk). They should be treated
specially, not as a simple primitive. The `promise?` function must be
implemented in racket code.
When you desugar primitives, do a special check to see if the
primitive is `promise?`, if so, it should _not_ be expanded to `prim
promise?` (or `apply-prim promise?`, depending). Because promises
should be expanded to use the user defined function.
You must desugar promises correctly. We manually check each
solution–if your solution defers to Racket’s promise API, we will
consider this an honor code violation and will invalidate your test
results for any tests making use of promises.
# Exceptions / raise, guards, and dynamic-wind #
You do not have to implement exceptions, guards, or dynamic-wind for
this assignment. If you are interested in implementing it after you
finish the project, feel free to talk to me and I can help you add it.
# Advice #
* To understand semantics of specific expressions, consult the `r7rs`
spec, which is what is used to evaluate the Scheme code. It can be
found [here](https://small.r7rs.org/attachment/r7rs.pdf). This short
report contains complete semantics for all grammatical clauses
required in this project.
* 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.
* 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.
* Consult the variable `prims-list` to obtain a list of primitives you
can use. You can use `(prim void)` to return a void value.
* 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.
* You will need to desugar all primitive operations (except
`promise?`) 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)))`.
* You may desugar `call/cc` directly into `call/cc`, without making
any special changes. A correct implementation of `call/cc` will
require [cooperation with
`dynamic-wind`](https://www.scheme.com/tspl2d/control.html#g1978).
* 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)]) …))`
# Running #
Test using tester.py as usual. You may find the contents of each test
at test/
of reading the input tests and then calling `desugar` (or
`desugar-aux`) yourself to manually inspect what they do. If you try
to simply look at the error from the resulting term and guess why it’s
broken that will be extremely challenging.
## Running With Docker ##
(Kris: I do not recommend running with Docker, as this project does
not require LLVM. I strongly recommend running locally)
If you have docker installed, you dont need to install python3 or
clang. You still need to install racket so you can access DrRacket and
edit your code. To run the tests, you can run the Docker container so
that it stays up, and then execute it as needed.
To run these commands on windows you need to replace `$(pwd)` with the
current directories path, and `$(basename pwd)` with the name of the
curretn directory. See Course staff (Kris) for help.
“`bash
# changes directory to current directory
cd /project/directory/here/
# Builds the docker image (installs clang/python/racket in the docker image)
docker build -t cis400 .
# runs the docker image with the current directory as a volume
# so the project can be accessed and tested
docker run –name $(basename $(pwd)) -v $(pwd):/project -d cis400
# run tests (same as `python3 tester.py –verbose –all` locally)
docker exec -it $(basename $(pwd)) /project/run –verbose –all
“`