Skip to topic | Skip to bottom


Main.POPLAssignment2r1.6 - 05 Nov 2009 - 09:05 - SanderVermolen

Start of topic | Skip to actions

POPL Assignment 2

The assignment consists of two separate parts:

  1. Write a parser and two interpreters for CFWAE (conditionals, functions, with, and arithmetic expressions), extended with the language features described below. The first interpreter should have eager application semantics and use explicit substitution. The second should have eager application semantics and use deferred substitution.
  2. After completing the first part of the assignment, copy the interpreter implementing deferred substitution and modify it so that it has lazy application semantics. (We strongly recommend that you do not attempt this part of the assignment until you’ve gotten the first interpreter done, thoroughly tested, and debugged!) Ensure you don't miss the changes you must make to the comntracts for this part.

In each part of the assignment, implement the function parse, which consumes an expression in the language’s concrete syntax and returns the abstract syntax representation of that expression. parse must accept only expressions in the grammar of the language.

In addition to parse, you must implement the function interp, which consumes an abstract syntax expression (as returned by the parse function) and returns a CFWAE-value. Please include a contract for every function that you write and include test cases that amply exercise all of the code you’ve written.

Features to Implement


To save the trouble of having to add boolean values and operators over them, create the construct if0 using the syntax described by the EBNF below. Note that if0 has three branches:

  • A test expression
  • A “then” expression, which evaluates if the test expression evaluates to zero
  • An “else” expression, which evaluates for any other number.

Evaluation should signal an error for non-numeric test values.

Multi-argument fun

Extend the fun language feature described in lecture so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate with the same deferred substitutions. An example of a multi-argument fun:

    {{fun {x y} {* x y}} 2 3}

This evaluates to 6.

As you did for multi-armed with, you must ensure that the arguments to a function have distinct names.


Implement a tracing mechanism for your interpreter. The traces should show (on screen) what expressions are being interpreted.

Syntax of CFWAE

The syntax of the CFWAE language with these additional features can be captured with the following EBNF:

<CFWAE> ::= <num>
    | {+ <CFWAE> <CFWAE>}
    | {- <CFWAE> <CFWAE>}
    | {* <CFWAE> <CFWAE>}
    | {/ <CFWAE> <CFWAE>}
    | <id>
    | {if0 <CFWAE> <CFWAE> <CFWAE>}
    | {with {{<id> <CFWAE>} ...} <CFWAE>}
    | {fun {<id> ...} <CFWAE>}
    | {<CFWAE> <CFWAE> ...}
where an id is not +, -, *, /, with, if0 or fun.

In this grammar, the ellipsis (...) means that the previous non-terminal is present zero or more times.

If a fun or a with expression has duplicate identifiers, we consider it a syntax error. Therefore, such errors must be detected in parse. For example, parsing the following expressions must signal errors:

{with {{x 10} {x 20}} 50}

{fun {x x} 10}

Testing Your Code

You must include a contract for every function that you write and include test cases that amply exercise all of the code you’ve written. We will not give full credit to untested functionality, even if it is correct!

Your parser and interpreter must detect errors and explicitly signal them by calling (error ...). We will consider an error raised internally by Scheme to be a bug in your code.

For example, Scheme signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Scheme's division function to implement division in CFWAE, you may be tempted to leave it to Scheme to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Scheme's division procedure. If you are not sure if an error raised by your program constitutes a bug, search the Help Desk for test/exn. test/exn tests for errors, but only succeeds on errors that you explicitly signal.

Support Code

Your code must adhere to the following template, without any changes:

(define-type Binding
  [binding (name symbol?) (named-expr CFWAE?)])

(define-type CFWAE
  [num (n number?)]
  [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)]
  [with (lob (listof Binding?)) (body CFWAE?)]
  [id (name symbol?)]
  [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)]
  [fun (args (listof symbol?)) (body CFWAE?)]
  [app (f CFWAE?) (args (listof CFWAE?))])

(define-type Env
  [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)])

(define-type CFWAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFWAE?)
            (env Env?)])

;; parse : expression -> CFWAE
;; This procedure parses an expression into a CFWAE
(define (parse sexp)

;; interp : CFWAE -> CFWAE-Value
;; This procedure interprets the given CFWAE and produces a result
;; in the form of a CFWAE-Value (either a closureV or a numV)
(define (interp expr)

However, for the second part of the assignment (lazy application), you will need to add an exprV variant to CFWAE-Value. That is, CFWAE-Value for should read:

(define-type CFWAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFWAE?)
            (env Env?)]
  [exprV (expr CFWAE?) (env Env?)]))


You should turn in three Scheme programs where each contains all of the code needed to run your parser and interpreter. One should be for the eager, direct evaluation, called "", one for the eager, deferred, called and one for the lazy evaluation, called "". You can also include a readme or other relevant files.

You will have two weeks to complete the assignment. The deadline is 1 December. Please hand in the assignment on or before the deadline, by sending your source files to S.D.Vermolen at This is an individual assignment, each student is expected to hand in their own solution.

-- SanderVermolen - 19 Nov 2008

Edit | Attach | Printable | Raw | More topic actions
Revisions: | r1.6 | > | r1.5 | > | r1.4 | Page history | Backlinks
You are here: Main > WebLeftBar > Courses > POPL > POPLAssignments > POPLAssignment2

to top

Copyright © 2003-2018, Software Engineering Research Group, Delft University of Technology, The Netherlands