Lambda the Ultimate

Simon Peyton Jones wrote a book about implementing lazy languages.
It is available on-line in
http://research.microsoft.com/Users/simonpj/Papers/pj-lester-book/

From a naive look at that algorithm, it looks like you could get into situations where dirtying a dependency tree of nodes took up a lot of time. Did you find that to be the case in practice much, or did things tend to ground into already-dirty nodes pretty quickly? I suppose my second reaction is that you'll only tend to have large fields of clean nodes to dirty if you've got something actively using them and cleaning them, and so the cost of dirtying them will mostly get absorbed into immediate re-cleanings for calculating changed outputs.

Brooks Moses: From a naive look at that algorithm, it looks like you could get into situations where dirtying a dependency tree of nodes took up a lot of time.

In practice that would be a problem if mutating inputs happened often. But in the context of deployments that scaled (they had eyes on balancing bank books with really complex financial instruments), a pure non-mutable state functional programming was assumed for performance. The cost of dirtying a dependency tree was expected only when users played "what if" games while manually tweaking things they could see, and then user perceptible performance responsiveness was all we wanted.

Because I left to go work on Apple's OpenDoc, I never saw it deployed in contexts so large that we had to alter the naive implementation model to avoid some large scaling costs. For example, while the model pretended all nodes were always in memory, you wouldn't want to do that for very large graphs. But you could still make an external view of the system behave as if all nodes were always present.

Similarly, you could try safe approximations of the dependency dirtying model, such as dirtying entire classes of nodes by rule without actually touching memory for them. But it could get complex if you invented something fancy. But the simple minded dependency dirtying description is a simple spec to follow, so you would reason about whether fancy simulations still did the same thing.

Thinking about the "whole graph" (the entire execution tree, ie an unrolled call stack tree) sometimes helped when deciding whether a technique changed any behavior perceived by an observer. (It always made me relax, and reminded me of discrete math technique in school addressing all parts of a global system at once.) We wanted users to be unable to tell an imperative approach was not being used, so they could assume eager evaluation if that fit their mental simulation better.

The guys I worked with at first were hardware guys used to building large simulations of chip circuits, which might explain some of the approach used.

The approach that you're describing, Rys, sounds to me quite a lot like Lambda Calculus Plus Letrec. With respect to the topic at hand, we find, in Part III:

Since most implementations of non-strict functional languages rely on sharing to avoid repeating computations, we develop a variant of our cyclic lambda calculus that enforces the sharing of computations and show that the two calculi are observationally equivalent. For reasoning about strict languages we develop a call-by-value variant of the sharing calculus. We state the difference between strict and non-strict computations in terms of different garbage collection rules. We relate the call-by-value calculus to Moggi's computational lambda calculus and to Hasegawa's calculus.

Credit where credit is due: Tim Sweeney pointed me to this work some months ago.