Here’s an interesting short paper by Wadler: Lazy vs. strict. Philip Wadler. ACM Computing Surveys, June 1996. To paraphrase, the simplest model of lazy evaluation is given by Church’s original $\lambda$ calculus, and the simplest model of strict evaluation is given by Plotkin’s $\lambda_v$ calculus. $\lambda$ is problematic because it gives a poor notion of the cost of programs, and $\lambda_v$ is problematic because it is not complete. These flaws can be removed at the cost of slightly more complicated models, and the resulting models turn out to be extremely similar.

Something just occurred to me about the gcc implementation of std::vector in C++. Internally, an instance of vector needs to store (1) a pointer to the start of the memory, (2) the current vector size, and (3) the current buffer size. However, (2) and (3) can be represented either as integers relative to the start pointer or as absolute pointers past the end of the active and buffer spaces. Specifically, the two representations are

Gah. I’m trying to write some straightforward combinatorial code in Haskell, and I finally got to the point where I had to start using nontrivial algorithms to make it acceptably fast. When I run those algorithms the first time, I get the following gem: *Main> drops 100 2 *** Exception: divide by zero The “drops” function is now 15 lines of mutually recursive Haskell, and the interactive interpreter conveniently informs me that there was a division by zero.

Here’s an interesting lazy variant of the sieve of Eratosthenes by Nick Chapman, from a discussion on LTU: primes = 2 : diff [3..] (composites primes) composites (p:ps) = cs where cs = (pp) : merge (map (p) (merge ps cs)) (composites ps) merge (x:xs) (y:ys) | xy = diff (x:xs) ys In words, the algorithm computes the list of primes as all numbers which are not composites, and the computes the list of composites by extremely constructing and merging all prime factorizations.

I use closures quite a lot in python, but the variable lifetime semantics of closures are undocumented as far as I can tell. For example, consider the following code: def f(): a=1 b=1 def g(): return b return g If we call ‘f’ and store the value, ‘b’ will be kept alive. Is ‘a’ kept alive? A naive implementation of closures might store a reference to the entire stack frame of ‘f’ inside the ‘g’ closure, causing ‘a’ to live even though it will never be used.