View the Project on GitHub TiarkRompf/cs590

Metaprogramming and Program Generation

One person's program is another program's data.

Tiark Rompf, Fall 2014, 3 credits

Week 1


Read the following two papers and write a short summary (0.5 pages for each):

Your summary should identify the main insights and scientific contribution of the paper: what is the key idea? what is possible after the paper came out that wasn't possible before? (It is a good idea to skim some of the related work to answer these questions).

Here is some additional advice, by Kathryn S McKinley (thanks to Keith Chapman for the link).

Summaries are due before midnight on Sunday, August 31 (submit per email to the instructor).


The programming assignments will be done in Scala. To get started with the assignments, clone the course repo from GitHub.

Solutions are due before midnight on Sunday, August 31 Wednesday, September 3 (submit per email to the instructor).

If you are new to Scala, the official doc site is a good starting point. You may also want to consider getting one of the books. There are also mailing lists, and Stack Overflow is pretty helpful, too.

1. Higher-Order Functions in Scala

The first assignment will review functional and object oriented programming in Scala (file Sets.scala).

A. Sets as Higher-Order Functions

To get acquainted with higher order functions, we implement a Set datatype, representing sets by their characteristic functions. In other words, a set of integers is a function that, for a given integer, returns a boolean that indicates if the integer is in the set or not:
type Set = Int => Boolean
Given this representation, we define a function that tests if a certain value is contained in a set in the following way:
def contains(s: Set, elem: Int): Boolean = s(elem)

Your first task is to complete the implementation by defining the following functions that build sets:
def set(elem: Int): Set // create a single-element set
def union(s: Set, t: Set): Set
def intersect(s: Set, t: Set): Set
def diff(s: Set, t: Set): Set // all elements from s that are not in t

Now define a function filter that selects only those elements of a set that match a given predicate p. The filtered elements are returned as a new set. You solution must be independent of the type of Set and of union,intersect,diff defined above.
def filter(s: Set, p: Int => Boolean): Set

Define a function forall that tests if a given predicate p holds for all elements in a set:
def forall(s: Set, p: Int => Boolean): Boolean
We note that it is not possible to access the elements of a set directly, so we restrict ourselves to a range of possible integers from -1000 to 1000.

With the help of forall, implement a function exists that tests if a set contains at least one element for which the predicate holds.
def exists(s: Set, p: Int => Boolean): Boolean

Finally, implement a function map that transforms a given set by applying a function f to each of its elements:
def map(s: Set, f: Int => Int): Set

Implement suitable test cases for your functions. Ideally, write the tests first.

A. Sets as Immutable Objects (Bonus)

An alternative representation for sets is based on objects and classes.

Implement function intersect. Hint: start by adding a function intersect0 that takes an accumulator as the second argument:
def intersect(that: IntSet): IntSet
def intersect0(that: IntSet, accu: IntSet): IntSet
This accumulator will keep a partial result while computing the intersection.

Implement function filter. Hint: use the same accumulator technique as above.

Now implement a new version of intersect in terms of filter.

2. Interpreters in Scala

The second assignment will implement some simple interpreters in Scala (file Interpreters.scala)

A. Reynolds Interpreter I

The code template contains an interpreter similar to the first one presented in Reynolds' paper (Section 5). But some functionality is missing. Find out what and implement the missing pieces.

Implement the factorial function as a test case for your interpreter:
def fact(n:Int) = if (n == 0) 1 else n * fact(n-1)
(you will need to extend the interpreter slightly to support the times and minus operations).

B. Reynolds Interpreter II

Implement the defunctionalized Interpreter II from the paper (Section 6).