Lambda the Ultimate

The following query: lazy vs strict site:lambda-the-ultimate.org produced the following threads:

Practical Advantages of Lazy Evaluation is a recent, highly relevant thread.

Combining lazy and eager evaluation of terms

Applicative vs Functional (Applicative order is another word for strict order, FTMP)

Question about laziness and algorithmic runtime analysis seems to address one of your questions

Why Functional Programming Matters is an excellent introduction to the topic.

I'd do more, but I have a strict limit of five links. Any more might be flagged as spam, and besides, I'm lazy....

Strictly speaking (ha!) Scala has a call-by-name argument annotation rather than the call-by-need that people generally mean when they say "lazy." Its big advantage is syntactic; you can do call-by-name in other strictly evaluated functional languages with a slightly heavier syntactic burden using functions of type Unit->t. That said, it's some pretty sweet syntactic sugar since it lets you create control structures that look like native syntax. It's the kind of thing that isn't theoretically a huge deal but you sure miss it when you don't have it.

Scala also has an optional true blue lazy annotation on immutable variables. It brings some (but by no means all) of the advantages of Haskell style laziness for some limited use cases.

In general, I think they're quite useful but the mix of non-strict and strict evaluation in an impure language isn't all sunshine. Ordering of side effects is hard enough to figure out in a strictly evaluated environment. Every couple of weeks somebody in the mailing list is confused because they mapped an impure function over a lazy list and didn't get the effects they expected when they were expected.

From the thesis:

Besides the complexity of the runtime system, laziness is a generally challenging aspect of Haskell programming, because laziness makes it difficult for the programmer to reason about evaluation order and memory usage. In my experience of developing the concurrency library, my program occasionally run into stack overflow errors and it often takes a long time to find out that the problem is on the order of evaluation for large, purely functional data structures. When the concurrency library manages more than 100,000 threads, its internal data structures, such as task queues, need to be carefully engineered to make sure that operations on such large structures do not cause memory leaks. When the program complexity scales up, it is generally difficult to get everything right even for an experienced Haskell programmer — the strictness annotations and order of evaluation must be all correct, or there will be memory leaks.

This is the general experience of people who program a lot in lazy languages. Whether it is a fundamental problem is unknown. A contemptible observation is that sufficiently large programs seem only to work with added strictness annotations.

It might be a reason why monads are so popular at the moment since they often 'linearize' the computation, resulting in more predictable behavior.

I guess one should be able to prove that for every eager statement of an algorithm, there exists an equivalent (bisimilar) lazy algorithm, and vice-versa. It might sometimes just be hard to find the equivalent lazy algorithm, but that might also be inexperience.

From the article:

This demonstrates that lazy evaluation is strictly more efficient - in asymptotic terms - than eager evaluation, and that there is no general complexity-preserving translation of lazy programs into an eager functional language.

Yeah, well, except for an interpreter.

Variable lookup in such an interpreter wouldn't be constant-time though, would it? The premise assumes you don't have a handy array.

Wrong premise I guess. Basic idea: Haskell programs are run on a strict machine, that doesn't make them faster.

I will scan the paper, but my best guess is that if you need O(log(N)) lookup on variables in the eager evaluation, you would need the same for the lazy evaluation. Maybe they play a trick on the mathematical level on the lazy term language which superficially gives them O(1).

[Scanned the abstracts. The claim is that there are lazy counterparts of algorithms which (with memoization) have better complexity than certain impure eager algorithm (I guess without memoization) only translated with severe restrictions. Yeah, well, duh... If I bind your hands with tennis, I am also certain to win the game.]

[Without having read the whole article: I guess their basic statement is "Purity can be exploited to implement memoization easily, therefor will often result in fast and concise algorithms." I am not sure if by memoization sharing of nodes is meant, or the classical optimization of memoizing small values on small functions often found in pure languages.]

I don't think this is a problem. For a particular program, lookups of its fixed set of variable names by different methods can only contribute a constant factor to its execution time. O(log n) complexity is only a problem as n goes to infinity, which it doesn't if the set of variables is held fixed.

It's not looking up variables in an environment that's the problem, it's implementing the thunks without fast arrays or mutation.