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. Specifically, the only difference between them is the following law, let x = M in N -> N which holds with laziness and fails for strictness. In other words, the different between strict and lazy languages is exactly what one would expect: in a lazy model unused terms can be ignored, and in a strict model they must be evaluated to make sure they don’t loop forever.

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. No hint as to where it might be, of course. Come to think of it, this was probably the reason I dropped back to Python after my last Haskell stint.

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 = (p*p) : 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. This would be very bad, since generating a closure inside a long function could potentially cause a large memory leak. I wouldn’t expect this since python is implemented by smart people, but it’s worth checking.