For

Since my last two posts about for expressions I’ve been working on an implementation. Implementing new features in Saturn is pretty easy, by design, but this feature has taken longer than usual for two reasons. First of all, I really only had the syntax when I started so I first had to come up with a decent semantics. Also, implementing it revealed a bunch of bugs in other parts of the system — for instance, it turns out that mixing tail-call optimization and non-local returns gives some interesting problems. But all that has been fixed. Here’s a method that returns the factors of a given integer

factors(k) -> for (x : 2 .. k, k % x == 0) -> x;
// factors(18) = [2, 3, 6, 9]

It’s not particularly efficient but it is definitely succinct. You can also create infinite data structures:

def primes = for (x: Naturals, x > 1, factors(x).is_empty()) -> x;
// primes = [2, 3, 5, 7, ...]
// primes[100] = 541

Of course you can also use it for plain, everyday stuff like

def all_names = for (person: employees) -> person.get_name()

Compare this with, let’s pick a random language, Java:

List all_names = new ArrayList();
for (Person person: employees)
  names.add(person.getName());

It’s just not the same…

Now, how does this actually work? The for expression uses a single method on collections: map_filter (I’m not too happy about this name so if you have a better idea feel free to tell me). This method takes two block arguments, map and filter and returns a new collection which contains the results of map applied to the elements in this collection for which filter returns true. A straightforward implementation could be:

map_filter(map, filter) {
  def result = new ArrayList();
  for (elm: this) {
    if (filter(elm))
      result.add(map(elm));
  }
  return result;
}

Note that for statements (for (...) { ... }) are not the same as for expressions (for (...) -> ...).

All a for expression is, really, is calls to the map_filter method. For instance, the body of the factor function above is expanded into

(2 .. k).map_filter(fun x -> x, fun x -> k % x == 0)

Implementing the map_filter method should be pretty straightforward and the good thing is that the implementer is free to decide how to represent the result. I definitely like this approach better than requiring collections to implement several different methods. Scala, for instance, uses three: map, filter and flatMap.

The freedom to choose the representation of the result is the key to implementing the list of primes: the implementation of map_filter in Naturals applies the map and filter lazily:

class Naturals is Collection {

  map_filter(map, filter) 
    -> new MapFilterCollection(this, map, filter);

  operator [index] -> index;

  for(block) {
    var i = 0;
    while (true) {
      block(i);
      i = i + 1;
    }
  }

}

class MapFilterCollection is Collection {

  def collection, map, filter;

  // constructor, etc.

  map_filter(map, filter) 
    -> new MapFilterCollection(this, map, filter);

  for(block) {
    for (obj: collection) {
      if (filter(obj))
        block(map(obj));
    }
  }

  operator [index] {
    var i = 0;
    for (obj : this) {
      if (index == i) return obj;
      i = i + 1;
    }
  }

}

This is not an efficient implementation of MapFilterCollection but it should give an idea of how things work underneath: the collection just postpones all the work until you iterate through it or ask for a particular element.

Apart from the name of the method, map_filter, I think that’s a pretty decent approach. There’s still one issue left: what happens when you iterate through several collections at once:

for (x: 0 .. 100, y: 0 .. x, z: 0 .. y,
     x + y + z == 50) -> new Tuple(x, y, z)

This expression uses three map_filters, one for each variable, but the result has to be turned into a single collection. I have implemented a solution but I think is still needs a bit of work. I’ll write more about that later.