Available from January 24, 2022 until August 31, 2022

Course: CSE2120 Edition: 2021-2022

One can enroll until Thu, Jun 23, 2022 23:59:00
1.4. 4: Desugaring and Environments

1 Overview

The language you will implement this week is similar to the language in the previous week (Week 3). In this week (Week 4), you will use environments to delay substitutions. Additionally, you will implement a desugarer to convert parsed expressions to core language. Furthermore, the language has been extended with a new construct, rec-lam for recursive functions.

You have to implement a desugarer and interpreter this week. A parser is provided as part of the (hidden) library in WebLab.

The lab assignment is based on Chapter 6 in PLAI.

2 Concepts

2.1 Environments

You should use an environment to propagate substitutions down through the abstract syntax tree, as it is traversed and interpreted. An Environment is a list of Bind objects that represent a binding of a name (String) to a Value (see the classes below).

Requirements and hints:

  • [Interpretation] Your interpreter needs to do name shadowing. You can achieve this by ordering the bindings in the environment in the right way.
  • [Interpretation] An environment corresponds to a set of substitutions that remain to be applied in an expression. Be careful that the application case of your interpreter ensures that function bodies are evaluated in the context of an environment that reflects the same set of substitutions as would have been applied in your interpreter of Week 3.


It may be possible to get a high automatically-computed grade by copy-pasting the substitution-based interpreter from week 3. However, your solution will be manually checked to see that you are using environments rather than substitution. If you use substitution, you will fail the assignment.

2.2 Recursive Lambdas

The language you will be implementing has support for recursive lambdas that use the following syntax:

(rec-lam f (x) e)

Here, f is the name of the function being recursively defined; x is the name that the function binds; and e is an expression that can refer to both x and f. Note that the name f is only bound in the expression e. In order to name the function value that a rec-lam expression constructs, it must be manually bound to a name (as in the second example below).

The following example program defines a function that sums the numbers from 0 to n:

(rec-lam sum (n) 
  (if (num= n 0)
    (+ n (sum (- n 1)))))

We can name and call this function by, e.g., using a let binding:

(let ((sum (rec-lam sum (n) 
             (if (num= n 0)
               (+ n (sum (- n 1)))))))
  (sum 3))

You can also write infinite loops using rec-lam. The following program will loop forever:

((rec-lam forever (x) (forever x)) 0)

This week’s programming assignment asks you to implement recursive functions using the Z combinator. rec-lam can be defined by desugaring into an application of the Z combinator. For example, the sum function above can be desugared as follows (where <Z> is a placeholder for the Z combinator):

  (lambda (sum) 
    (lambda (n)
      (if (num= n 0)
        (+ n (sum (- n 1)))))))

Implement the desugaring illustrated above.

2.3 Syntactic Sugar for Lists

A list expression is syntactic sugar for nested cons lists. For example, (list 1 2 3) should desugar into a cons list: (cons 1 (cons 2 (cons 3 nil))).

2.4 Sugaring Cond Expressions

cond expressions make their return from week 2. However, this time they should be desugared into if expressions instead. For the case where none of the branches match and there is no else branch, you should use the UndefinedC construct, which should throw an exception if reached in the interpreter.

  • [Desugaring] Multi-armed conditionals should desugar into (possibly nested) if expressions.
  • [Desugaring] You will want to use UndefinedC case class (see Classes below) for the form that does not have an else case. (To understand why, it is instructive to look at the examples given below.)
  • [Interpretation] The UndefinedC is an expression that represents that your interpreter is in a case whose behavior is undefined. Your interpreter should raise an InterpException (or a subclass thereof) in this case.


This program should result in an InterpException (by using the UndefinedC construct in your desugarer).

  ((num> 0 1) 1)
  ((num< 1 0) 2))

3 Grammar

module functions

imports Common

context-free syntax

  Expr.NumExt       = INT      // integer literals
  Expr.TrueExt      = [true]
  Expr.FalseExt     = [false]
  Expr.IdExt        = ID

  Expr.UnOpExt      = [([UnOp] [Expr])]
  Expr.BinOpExt     = [([BinOp] [Expr] [Expr])]

  UnOp.MIN          = [-]
  UnOp.NOT          = [not]
  UnOp.HEAD         = [head]
  UnOp.TAIL         = [tail]
  UnOp.ISNIL        = [is-nil]
  UnOp.ISLIST       = [is-list]

  BinOp.PLUS        = [+]
  BinOp.MULT        = [*]
  BinOp.MINUS       = [-]
  BinOp.AND         = [and]
  BinOp.OR          = [or]
  BinOp.NUMEQ       = [num=]
  BinOp.NUMLT       = [num<]
  BinOp.NUMGT       = [num>]
  BinOp.CONS        = [cons]

  Expr.IfExt        = [(if [Expr] [Expr] [Expr])]
  Expr.NilExt       = [nil]
  Expr.ListExt      = [(list [Expr*])]

  Expr.CondExt      = [(cond [Branch+])]
  Expr.CondEExt     = [(cond [Branch+] (else [Expr]))]
  Branch.Branch     = [([Expr] [Expr])]

  Expr.FdExt        = [(lambda ([ID*]) [Expr])]
  Expr.AppExt       = [([Expr] [Expr*])]
  Expr.LetExt       = [(let ([LetBind+]) [Expr])]
  LetBind.LetBind   = [([ID] [Expr])]

  Expr.RecLamExt    = [(rec-lam [ID] ([ID]) [Expr])]

Note that [ID*] denotes a sequence of zero or more [ID]s; and [LetBind+] denotes one or more [LetBind]s.

4 Classes

These classes should be used in your solution.

4.1 Abstract Syntax

The abstract syntax is postfixed with Ext for extended syntax.

sealed abstract class ExprExt
case class TrueExt() extends ExprExt
case class FalseExt() extends ExprExt
case class NumExt(num: Int) extends ExprExt
case class BinOpExt(s: String, l: ExprExt, r: ExprExt) extends ExprExt
case class UnOpExt(s: String, e: ExprExt) extends ExprExt
case class IfExt(c: ExprExt, t: ExprExt, e: ExprExt) extends ExprExt
case class ListExt(l: List[ExprExt]) extends ExprExt
case class NilExt() extends ExprExt
case class AppExt(f: ExprExt, args: List[ExprExt]) extends ExprExt
case class IdExt(c: String) extends ExprExt
case class FdExt(params: List[String], body: ExprExt) extends ExprExt
case class LetExt(binds: List[LetBindExt], body: ExprExt) extends ExprExt
case class RecLamExt(name: String,
                     param: String,
                     body: ExprExt) extends ExprExt
case class CondExt(cs: List[(ExprExt, ExprExt)]) extends ExprExt
case class CondEExt(cs: List[(ExprExt, ExprExt)], e: ExprExt) extends ExprExt

case class LetBindExt(name: String, value: ExprExt)

object ExprExt {
  val binOps = Set("+", "*", "-", "and", "or", "num=", "num<", "num>",
  val unOps = Set("-", "not", "head", "tail", "is-nil", "is-list")
  val reservedWords = binOps ++ unOps ++ Set("list", "nil", "if", "cond", "else",
    "lambda", "let", "true", "false", "rec-lam")

4.2 Desugared Syntax

The desugared syntax is postfixed with C for core syntax.

sealed abstract class ExprC
case class TrueC() extends ExprC
case class FalseC() extends ExprC
case class NumC(num: Int) extends ExprC
case class PlusC(l: ExprC, r: ExprC) extends ExprC
case class MultC(l: ExprC, r: ExprC) extends ExprC
case class IfC(c: ExprC, t: ExprC, e: ExprC) extends ExprC
case class EqNumC(l: ExprC, r: ExprC) extends ExprC
case class LtC(l: ExprC, r: ExprC) extends ExprC
case class NilC() extends ExprC
case class ConsC(l: ExprC, r: ExprC) extends ExprC
case class HeadC(e: ExprC) extends ExprC
case class TailC(e: ExprC) extends ExprC
case class IsNilC(e: ExprC) extends ExprC
case class IsListC(e: ExprC) extends ExprC
case class UndefinedC() extends ExprC
case class AppC(f: ExprC, args: List[ExprC]) extends ExprC
case class IdC(c: String) extends ExprC
case class FdC(params: List[String], body: ExprC) extends ExprC

4.3 Values

sealed abstract class Value
case class NumV(n: Int) extends Value
case class BoolV(b: Boolean) extends Value
case class NilV() extends Value
case class ConsV(hd: Value, tl: Value) extends Value
case class ClosV(f: FdC, env: Environment) extends Value

4.4 Other

case class Bind(name: String, value: Value)
type Environment = List[Bind]

5 Exceptions

Specific exceptions should be created that inherit from the given abstract exceptions.
Creating specific exceptions for each case makes debugging a lot easier and are more informative.
Throw only exceptions derived from DesugarException in the desugarer and only exceptions
derived from InterpException in the interpreter.

abstract class DesugarException extends RuntimeException
abstract class InterpException  extends RuntimeException