Skip to topic | Skip to bottom


Main.POPLAssignment4r1.4 - 07 Jan 2009 - 13:57 - SanderVermolen

Start of topic | Skip to actions

POPL Assignment 4

The goal of this assignment is to hone your skills for defining interpreters, deepen your understanding of continuations, and make sure you understand the notion of variable capture in substitution.

Implement (reuse) an interpreter for the eager language CFAE (first-class functions, arithmetic, conditional).

Extend the interpreter to support lists, i.e., with the following built-in operations:

  • empty : constructs the empty list (a value)
  • {{cons x} xs) : constructs a list with head x and tail xs
  • empty? : {empty? empty} -> 0
  • head : {head {{cons x} xs}} -> x
  • tail : {tail {{cons x} xs}} -> xs

This does not require the extension of the syntax of the language, but just special cases in the interpreter. However, it does require extension of the values produced by the interpreter.

Extend the interpreter with an implementation of web-read/k, along the lines of the definition on page 153 of the book.

Verify that the implementation of transformation to CPS that we developed in class (see below) is correct by means of tests. Correct any errors that you might find.

Provide a definition for the function 'normalize' that simplifies CFAE expressions by applying Beta and Eta reduction:

   {{fun {x} e1} e2} -> e1[x := e2]

   where [x := e] is substitution of all free occurrences of x by e
   (note that this assumes the 'Barendregt agreement' of uniquely named variables)
   {fun {x} {e x}} -> e

   if x does not occur free in e

Using the composition (pp (normalize (cps e))) can you reproduce the transformations to CPS of Chapters 16 and 17? For example, what is the CPS version of:

{with {map {fun {f} 
                {fun {l} 
                     {if0 {empty? l}
                          {cons {f {first l}}
                                {{map f} {rest l}}}}}}}
      {map {web-read {{cons 1} {{cons 2} empty}}}}}

Hand in the interpreter and transformation with tests.

In order to make it easier to test the transformations you may want to rewrite the pretty-printer to produce a string instead of printing strings.


To hand in this assignment, email a zip file of all the sources to S.D.Vermolen at Because of the end-of-the-year holidays, you have more time to complete your application than usual. The deadline is 12 January (similar to assignment 5).

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

to top

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