Lambda the Ultimate

I'm back... I had a great vacation (aside from being on my way to Toronto when this happened...) Now back to work ;-)

For interesting background on XQuery's development here's the full text of Udell's interview with Jonathan Robie.

As opposed to procedural abstraction, higher-order functions, etc. Nice answer from Patrick Logan (who was once a member of the LtU team but seems to have forgotten about us...)

By comparing three versions of the memo (unsigned, but believed written by Irv Ziller) “Proposed Specifications for FORTRAN II for the 704″, dated August 28, September 25, and November 18, 1957, you can watch the design of the subroutine feature of FORTRAN II unfold.

Also: separate compilation.

In Haskell, data structure elements are memoized. That is, the function that creates say, an element of a list is called at most once. After the first evaluation, the resulting value is saved away in case it is ever needed again. This is great for things like the infinite list of Fibonacci numbers...

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

...but it can lead to excessive memory in situations like...

main = print (length list, sum list)
list = [1..10000000]

...where at some point the entire list will need to be in memory. You could have avoided the large memory usage by traversing the list in a linear way, building up the length and sum at the same time, rather than in sequence.

Now imagine an evaluation régime, where instead of memoizing each data element (for later use), we call all of the functions which have a pointer to this element. Afterwards, no more pointers to this element will exist, so we can reclaim its memory. It changes the rule "evlaute a data item at most once" into "evaluate a data item as most once, and be sure to call anything that depends on it immediately, because it is short lived". Is there a name for this evaluation strategy, and any programming languages which implement it?