length - recursive style

Reifing the continuation of a computation simplifies such tasks as source to source transformation and compilation.

Example - a recursive algorithm is transformed into an iterative one.

Here is a typical, recursive defintion of the function length.

(defun length1 (L)                      ; Common Lisp.
  (if (null L) 0
    (+ 1 (length1 (cdr L)))))

static int length1 (Cons L) {           // Java
  if (L == null) return 0;
  else return 1 + length1(L.cdr());}

Stack space must be allocated for each call to length1 so 1 can be added to it.

length - continuation passing style

This version uses a continuation, k to add the one.

(defun length2 (L k)
  (if (null L) (funcall k 0)
    (length2 (cdr L) (lambda (v) (funcall k (+ 1 v))))))

static int length2 (Cons L, Continuation k) {
  if (L == null) k._(0);
  else {
    Continuation j = new class implements Continuation {
                           int _ (int v) { return k._(1 + v); }
                     }
    return length2(L.cdr(), j);
  }
}

Evalutating length2

If we evaluate (length2 '(1 2 3) (lambda (v) v)) symbolically, we'd get the following steps:

(length2 '(1 2 3) (lambda (v) v))
(length2 '(2 3)   (lambda (v) (+ 1 v)))
(length2 '(3)     (lambda (v) (+ 1 (+ 1 v))))
(length2 '()      (lambda (v) (+ 1 (+ 1 (+ 1 v)))))
(funcall (lambda (v) (+ 1 (+ 1 (+ 1 v)))) 0)
3

The continuation simply grows over time waiting to be passed a 0 at which point all the additions occur.

Use math identities

Using the properties of + we can replace the more costly continuation representation by an integer.

(defun length3 (L k)
  (if (null L) k
    (length3 (cdr L) (+ k 1))))

static int length3 (Cons L, int k) {
  if (L == null) return k;
  else return length3(L.cdr(), k + 1);
}

After tail recursion elimination, this gives the standard iterative definition of length.

(length3 (1 2 3) 0)
(length3 (2 3)   1)
(length3 (3)     2)
(length3 ()      3)
3