On Thu, Mar 19, 2009 at 07:24:55AM -0700, John Baez wrote:
I think most functional programming languages either delay evaluation in this way, or give the user the option to do this.
It's generally fairly easy to roll your own lazily-evaluated data-structures in any modern language. All you do, instead of returning the value in question, is return a function of no arguments (often called a "thunk", or a "promise") which calculates said value when called. When the value is needed, the thunk is called (and then usually replaced with the value, to save future computation). In languages without first-class functions (functions which can be stored in variables, constructed on-the-fly, etc) you have to do slightly more work to construct the thunk, but this is tedious rather than hard. See http://blog.plover.com/prog/defunctionalization.html for a discussion of how Java programmers work around the lack of first-class functions. At the other end of the scale, some strictly-evaluated languages (Scheme and O'Caml, for example), provide convenient interfaces for constructing lazily-evaluated data-structures, which are implemented using thunks. It's perhaps worth mentioning that lazy evaluation, though often a Very Good Thing, is not all roses: it makes the run-time performance (speed and memory consumption) of a program more complex to predict. Miles -- An extensible program is a double-edged sword, but recent experience has shown that users prefer a double-edged sword to a blunt one. -- Paul Graham