20bits

Even though I'm employed as a computer programmer and have a formal education in mathematics, natural language processing, and have studied much more than the usual first-year discrete mathematics cirriculum I have no formal education in computer science. Yes, it's true: never have a taken a class called "Algorithms," "Operating Systems," "Programming Languages," or "Databases." I say it's time to rectify this.

It all started with this paper by John Backus, who died on March 17th of this year. The paper is baroque, even for its time, but it contains a many gems. The heart of it is a critique of the von Neumann style of programming, so let's dive in.

The von Neumann style is characterized by a separation between data manipulation and data storage, i.e., between a processor and memory. Most languages, including Backus' own FORTRAN, follow this style. You read some data from memory, perform computations on said data, and then push that data back into memory. Backus claims that this is undesirable because it leads to more complicated and less extensible programs, and that such a design can suffer from what he calls the "von Neumann bottleneck" because the system spends so much time "pushing vast numbers of words back and forth."

To remedy this Backus details the specification for a purely functional programming language he calls FP. Two things struck me about this language: one, it is unlike any other programming language I've seen; two, it allows a (relatively) simple expression of complicated mathematical operations. The biggest oddity is that it contains no variables whatsoever. Instead FP provides for many combinators which construct new functions from old ones.

For example, the inner product is defined by Backus thus: Def IP ≡ (/+) o (αx) o Trans. This seems totally opaque, but it's not too bad. Let's define the building-blocks one-by-one:

1. Trans is matrix transposition, so Trans([[1,2,3], [4,5,6]]) becomes [[1,4], [2,5], [3,6]].
2. + is a function which adds two numbers.
3. x is a function which multiplies two numbers.
4. α is a combinator which applies the given function to every element in a sequence, so (αx)([[1,2], [3,4]]) = [1×2, 3×4] = [2,12].
5. / is a combinator which inserts a binary operator between each element of the sequence. This is equivalent to the omnipresent "reduce" operation in functional languages, so, e.g., (/+)([1,2,3]) = 1+2+3 = 6
6. o is a combinator which corresponds to function composition, so that (f o g)(x) = f(g(x)).

Back to the original reason for writing this post, namely, to teach myself how to implement programming languages. I have decided to write an FP interpreter (and maybe a compiler) in Javascript over the next month or so. I chose Javascript because, one, it has many functional aspects, and two, as a language it gets a lot of crap for being a "toy."

To start with I implemented all the FP primitives and functional forms in Javascript. I can now write:

This is so easy because Javascript treats functions as first-class objects, the core feature of any functional programming language. For example, the compose function is just

Extending this to an arbitrary number of arguments is simple, but FP functions only ever accept a single parameter as an input — multiple parameters are passed in as arrays of other objects. Anyhow, downloads fp.js yourself and take it for a spin. All that's left is to write a tokenizer and parser, which is what I really wanted to learn how to do. Cheers!