CSCI 1730 · Fall 2026
2 Desugar
2.1 Introduction
For this assignment, you will write a desugarer for Paret: a function that turns programs in a richer surface language into programs in the Core Paret of the Interpreter. This lets you add new syntax forms without having to change the interpreter.
2.2 Assignment
Paret adds three forms to Core Paret: and, or, and let. The parser from the Interpreter doesn’t know them, and its Expr type can’t represent them, so we have provided a second module, paret.rhm, with a parser for the richer language and a new abstract syntax type, Surface:
parse_surface :: Sexp -> Surface |
parse_surface_str :: String -> Surface |
(These are named differently from paret_core.rhm’s parse and parse_str, so that you can import both modules with open.)
Surface has a constructor for each form of Core Paret, named s_num, s_app, and so on, and three more, s_and, s_or, and s_let, for the sugar.
You will implement one function:
desugar :: Surface -> Expr |
which replaces every instance of syntactic sugar with an equivalent built from Core Paret, and returns the result. Expr is the type from paret_core.rhm, unchanged.
Observe that an expression may have multiple different correct desugarings. (A desugaring is “correct” if, when the result is evaluated, it produces the desired result.) For example, two desugarings of the same and can be different trees that nonetheless produce the same value, or the same error, on every program. Therefore, the only way to judge whether your desugar is correct is to run its output. This also affects how you test; see Testing.
When we grade your desugar, we run the programs it produces on our interpreter, which is correct, not on yours. That way, a test fails only because of your desugar, never because of a bug in your interpreter. Your tests still use your own interpreter (see Testing), but you don’t hand it in.
2.3 Grammar
<expr> ::= <num> |
| <string> |
| <var> # variable (a.k.a. identifier) |
| true |
| false |
| (+ <expr> <expr>) |
| (++ <expr> <expr>) |
| (num= <expr> <expr>) |
| (str= <expr> <expr>) |
| (if <expr> <expr> <expr>) |
| (and <expr> <expr>) |
| (or <expr> <expr>) |
| (let (<var> <expr>) <expr>) |
| (lam <var> <expr>) # anonymous function |
| (<expr> <expr>) # function application |
and, or, and let are keywords too, and cannot be used as variables.
2.4 Abstract Syntax
type Surface |
| s_num(n :: Int) |
| s_str(s :: String) |
| s_bool(b :: Boolean) |
| s_op(op :: Op, left :: Surface, right :: Surface) |
| s_if(cnd :: Surface, thn :: Surface, els :: Surface) |
| s_lam(param :: Symbol, body :: Surface) |
| s_app(fn :: Surface, arg :: Surface) |
| s_var(name :: Symbol) |
| s_and(left :: Surface, right :: Surface) |
| s_or(left :: Surface, right :: Surface) |
| s_let(name :: Symbol, rhs :: Surface, body :: Surface) |
Op, Expr, Value, and Env are as in the Interpreter. This is the point: we grow the language without those parts changing.
2.5 Features to Implement
desugar should convert s_let, s_and, and s_or into equivalent Exprs, and leave everything else as it is. There are multiple implementation strategies. Be sure to test well: it’s easy to miss some details when desugaring!
2.5.1 let
let accepts a single variable-value pair and a body. It evaluates the value, binds it to the variable, and evaluates the body with the newly bound variable in scope. For example, the following evaluates to 3:
(let (x 1) (+ x 2)) |
let is not recursive: in (let (<var> <expr>) <body>), <var> is bound in <body> but not in <expr>.
The desugaring of let may not be obvious, so here’s a hint: which Expr extends the environment?
2.5.2 and and or
and evaluates to true if both of its operands are true; otherwise, it evaluates to false.
or evaluates to true if at least one of its operands is true; otherwise, it evaluates to false.
Both short-circuit: if the first operand of and evaluates to false, the second is not evaluated and the whole expression is false; likewise, if the first operand of or evaluates to true, the second is not evaluated. Thus the second operand of a short-circuited expression can never raise an error.
Both are also Boolean-strict: an operand that is evaluated and is not a Boolean is an error, exactly as a non-Boolean condition of if is. So (and false 5) is false, while (and true 5) and (and 5 true) are errors. Since your desugaring is built from if, you get all of this from if provided you desugar carefully.
2.6 Testing
Because there is more than one correct desugaring, any test of the form
check: |
desugar(...) |
~is ... |
is invalid: run against a different, equally correct desugar, it would fail. Every test therefore goes through your interpreter, on the desugared program:
check: |
interp(desugar(parse_surface_str("(let (x 1) (+ x 2))"))) |
~is v_num(3) |
The stencil desugar_tests.rhm imports paret_core.rhm, paret.rhm, and your two implementation modules, all with open. Keep those imports as they are. Since the test file opens both of your modules, interpreter.rhm and desugar.rhm must not define helper functions with the same name.
Of course, since these tests rely on both your interp and your desugar, a failure could come from either. If you can’t find a bug, double-check your interpreter by writing more tests for it. And recall from the Testing Guidelines that errors are tested by the symbol they are raised with, which for a desugared program is still the interpreter’s "interp": desugar itself raises no errors.
2.7 Starter Code
You are provided with:
desugar.rhm, the stencil for your desugarer.
desugar_tests.rhm, the stencil for your tests.
paret.rhm, the surface language, and paret_core.rhm, sexp.rhm, and sexp.rkt from the Interpreter.
Copy your interpreter.rhm from the Interpreter into the same directory.
2.8 What To Hand In
You will submit to two Gradescope drops for this assignment:
desugar.rhm, which should be uploaded to the “Code” drop.
desugar_tests.rhm, which should be uploaded to the “Tests” drop.