The Essence of Lambda

When I was studying Scheme on a programming course at HUT, I remember I was a bit baffled by first-class functions. My previous experiences were with C, Pascal, Basic, and other languges which didn’t have first-class functions. Data is data, code is code. You don’t go mixing those two. Why would you want to create new functions on the fly and pass them around as values? Crazy talk!

What really made me understand was the following homework exercise:

Define cons, car, and cdr without using any built-in data structures. Hint: Use first-class functions.

As you may know, cons is a function which takes two arguments and returns a single value which contains the two argument values inside. This single value is called a pair (or sometimes a cons cell). The car and cdr functions extract the left and right parts of a pair, respectively.

Without further ado, here’s the solution. I suppose most readers aren’t necessarily familiar with Scheme, so I’m including both JavaScript and Scheme code.

function cons(a, b) {
  return function(x) {
    if (x) {
      return a
    } else {
      return b
    }
  }
}
 
function car(p) {
  return p(true)
}
 
function cdr(p) {
  return p(false)
}

This really helped my understand what this lambda business is all about. It’s more than a function without a name. It’s less magical than generating code on the fly, which was what I first believed must be happening. A first-class function is a way to bind together some values (a and b) together with some code operating on those values (the if). The result is a function you can call like a regular function.

Sometimes, I’m a bottom-up kind of guy, so the final missing piece of understanding had to come from figuring out how lambda could be implemented by the compiler or interpreter. Here’s how:

function cons_f(a, b, x) {
  if (x) {
    return a
  } else {
    return b
  }
}
 
function cons(a, b) {
  return [cons_f, a, b]
}
 
function car(p) {
  return p[0](p[1], p[2], true)
}
 
function cdr(p) {
  return p[0](p[1], p[2], false)
}

So when the compiler encounters a function body which refers to variables outside the body, it kind of lifts the lambda into a top-level function. Any open variables are made into new explicit parameters for the function. The function value is basically a vector with a reference to this “normal” function, plus the values of the open variables at the time.

Technically this is not exactly how things happen, but hopefully you get the point. The point being that deep down, lambda is really not that much more special than allocating a vector.

As for the solution itself, we can actually do a bit better. We don’t really need to use a conditional:

function cons(a, b) {
  return function(f) {
    return f(a, b)
  }
}
 
function car(p) {
  return p(function(a, b) { return a })
}
 
function cdr(p) {
  return p(function(a, b) { return b })
}

We can go even more basic than this. The above code uses functions with two arguments. Let’s make it curried, and only use functions with one argument. It’ll change the API, though, so instead of cons(a, b) you call cons(a)(b).

var cons =
  function (a) {
    return function(b) {
      return function(f) {
        return f(a)(b) 
      }
    }
  }
 
function car(p) {
  return p(function(a) {
    return function(b) {
      return a }
  })
}
 
function cdr(p) {
  return p(function(a) {
    return function(b) {
      return b
    }
  })
}

This is arguably as basic as it gets. We’ve defined cons, car, and cdr using nothing but function definitions and function calls.

Hopefully this little exercise helped you as much as it helped me. They say you don’t really know a programming language until you’ve learned to hate it with a passion. I’d say you don’t really know a programming language until you’ve implemented a compiler for it.

Related posts:

1. Programming Problems in Disguise
2. Overriding System Functions for Fun and Profit
3. The Three Doors of Type Systems

If you liked this, click here to receive new posts in a reader.
You should also follow me on Twitter here.