Tuesday, March 4, 2008

Functions do not return values

Ok, let me start pulling some of these disparate threads together.

Do functions return values?

There are basically three ways a function can finish its computation:
  1. Returning a literal constant.
  2. Returning the value of a variable.
  3. Calling another function.
As I mentioned last time, when we call another function to compute the return value, we are actually delegating the computation to the other function. The caller doesn't need to hang around to simply pass back the value, it can free its resources and just transfer control to the callee.

But obviously, a function like
(define (foo) 3)

has to return the value 3. Well, not really. The interpreter or compiler could treat literal constants and variables as calls to the identity function. We'd never be able to tell the difference. Without loss of generality, we can assume that this is exactly what happens. So every user-defined function finishes its computation by explicit delegation to another function or implicit delegation to the identity function.

But surely the identity function would have to return! Well, not really.
(define (identity x)
  (call/cc (lambda (k) (k x))))
Identity can delegate to call/cc. call/cc delegates to the thunk argument, and that delegates to the captured continuation.

My point isn't to amuse and amaze with stupid continuation tricks, however. My point is that all control transfer, be it a function call or return can be uniformly modeled as a function call. This isn't news. People have been doing this for years. Henry Baker took it to the extreme when he suggested that this could be an effective technique for implementing Scheme in C. Felix Winkelmann's Chicken compiler uses this exact technique. The underlying implementation never returns a value. When the stack is exhausted, the live data is evacuated and the stack pointer is reset.

Next time: a few odd consequences.