One person's program is another program's data.
Tiark Rompf, Fall 2014, 3 credits
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.
The first assignment will review functional and object oriented programming in Scala (file Sets.scala).
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.
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.
The second assignment will implement some simple interpreters in Scala (file Interpreters.scala)
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).
Implement the defunctionalized Interpreter II from the paper (Section 6).