Actor Model

Another digression, but still heading towards the same general direction.

---

Sussman and Steele developed Scheme to explore some of the semantics of Hewitt's Actor model. They discovered that the code that implemented message passing and the code that implemented function application was identical (modulo the naming). In other words, a closure can be considered an actor that waits for a message (the arguments) and runs until it computes a value. Message passing is simply invoking a closure on a set of arguments. (This doesn't capture the entire Actor model, but it captures some interesting facets.)

A crucial part of the Actor Model is the ability to delegate computation. Any Actor can foist off part or all of a computation on to another Actor. If an Actor simply redirects a message to a different Actor (after possibly munging the payload of the message), it is important that it free any temporary resources it was using. There is no logical limit on the length of a delegation chain, so there shouldn't be a physical one if it isn't necessary.

In Scheme, this translates into the requirement for general tail recursion. If a Scheme function, call it `Foo', delegates its computation to another function `Bar', there is no need to return control to `Foo' if all it is going to do is pass the return value on up the stack. The temporary resources used by `Foo' can be released when control passes to `Bar'. If `Bar' were to delegate to `Baz', then `Bar' can release its temporary resources when it passes control. This chaining of delegation can be indefinitely long. Stack overflow is not an issue because we free the stack frames as soon as we no longer need them.

Languages that do not support general tail recursion cannot support this kind of indefinite delegation: the delegation chain must be bounded.

---

To tie this in with the post from a few days ago:

Languages with general tail recursion can run any program that can run without tail recursion. However, there is a class of programs that can run only if general tail recursion can be depended upon. Included in this class are continuation-passing-style and indefinite delegation. (CPS can be considered a subset of indefinite delegation if you wish). You cannot run these styles of programs without resorting to whole-program analysis and restructuring.