Know When to Fold

I am teaching an undergraduate course in programming languages. We build interpreters and compilers for toy languages, in the hope that students gain a basic understanding of syntax, semantics, and language translation.

I use Scala to implement the interpreters and compilers because of its nifty “combinator parser” library. (This and this blog have nice introductions into Scala combinator parsers.) Why not just lex and yacc, the Model T of parser generators? My colleague is doing just that, and it is a good thing because it gives students much-needed experience with C programming. But I don't have the heart to see students suffer with pointer errors. With Scala, we can implement an interpreter for a simple language that supports arithmetic, if/else, and closures, in < 150 lines of code.

I am learning Scala on the job, and I don't know all of the language features yet. In particular, surely there must be some kind of while or for loop, but I haven't run into it yet.

The reason is that I try to follow the advice of the Scala gurus and use val instead of var whenever I can. If you can't update any variables, and generally try to avoid side effects, there isn't much you can do in a loop body. (Experienced functional programmers will surely say “Duh”, but it came as a surprise to me)

Instead, I find that I use the “fold” operator an awful lot. Let me explain the operator with the shopworn example of computing the product 1 * 2 * ... * n. Here is the iterative solution, which uses an unsightly var:

def fac(n : Int) = { var r = 1; for (i <- 2 to n) r *= i ; r }

As L. Peter Deutsch said, to iterate is human; to recurse, divine:

def fac(n : Int) : Int = if (n <= 1) 1 else n * fac(n - 1)

Recursing may be divine, but it even better to fold: 

def fac(n : Int) = (1 /: (2 to n)) {_ * _}

To visualize what is going on, draw a tree:

      op
     /  \
    op   4
   /  \
  op   3
 /  \
1    2

The /: operator has three arguments:

There is also a :\ if the tree happens to go the other way.

At first, I thought that these operators are mere curiosities, but they turned out to come in handy many times. Consider evaluating a block in a toy language:

{
   val a = 3;
   val b = 2 * a;
   val fun = { x => x * x };
   ...
}

Each definition has to be added to an environment (a mapping of names to values). Here is the tree:

             op
           /    \
          op     third def.
        /    \
       op      second def.
     /    \
original   first def.
environ.

What is the operation? To add the definition to the previous environment. There is a function evalDef that takes an environment and a definition, returning the environment that is augmented by the definition. (That's what you do when working with immutable data structures.) To add all definitions, you simply use

(env /: block.defs) { evalDef(_, _) }

Ok, what's the point? I am interested in blue collar languages because they get lots of users, and when there are lots of users, someone builds great tools. Many years ago, I switched from Pascal—the original quiche eater language—to C so I could get decent tools and libraries.

With functional languages, there are all these nifty idioms that lead to very concise code that looks like random line noise to the uninitiated. (It isn't just Scala—in Ruby, /: is called inject, and Ruby programmers are just as delighted when they discover it. Read this blog about using inject for printing a Mandelbrot set, surely an activity that only a quiche eater can love.) I can just hear the blue collar programmers looking at (1 /: (2 to n)) {_ * _} and wailing “oh my, what is this, my head hurts”.

The conventional wisdom (for example, expressed in this blog) is that functional programming will never be mainstream. I used to think that too, but now I am having second thoughts. After all, if you now look at Pascal, it is hard to imagine why people were so opposed to it. It is just C with a saner syntax, or Java with only static methods and no objects. And Microsoft, surely the bastion of the blue-collar programmer, is adding all sorts of functional programming features to its flagship language. Check out this blog on folding with LINQ. It is pretty disconcerting—kind of like Sarah Palin's correctly pronouncing nu-cle-ar.

Maybe we are at that point in history when closures are becoming mainstream?