ezyang’s blog

the arc of software bends towards understanding

Reified laziness

Short post, longer ones in progress.

One of the really neat things about the Par monad is how it explicitly reifies laziness, using a little structure called an IVar (also known in the literature as I-structures). An IVar is a little bit like an MVar, except that once you’ve put a value in one, you can never take it out again (and you’re not allowed to put another value in.) In fact, this precisely corresponds to lazy evaluation.

/img/ivar.png

The key difference is that an IVar splits up the naming of a lazy variable (the creation of the IVar), and specification of whatever code will produce the result of the variable (the put operation on an IVar). Any get to an empty IVar will block, much the same way a second attempt to evaluate a thunk that is being evaluated will block (a process called blackholing), and will be fulfilled once the “lazy computation” completes (when the put occurs.)

It is interesting to note that this construction was adopted precisely because laziness was making it really, really hard to reason about parallelism. It also provides some guidance for languages who might want to provide laziness as a built-in construct (hint: implementing it as a memoized thunk might not be the best idea!)

3 Responses to “Reified laziness”

  1. Wu Xingbo says:

    Very interesting. When blocked, it said “…….” in mind:(“I really don’t know what it is!”). But after a while it returns and say “what you want is xxx”. regardless of how long you have been waiting for, you get a “pure” logical interface.

  2. Yeah! So the caller can’t actually tell if it started trying to calculate the value, or it’s just waiting for someone to tell you what it is.

    It should be noted that you do need to wrap IVars in another interface to produce a more traditional laziness mechanism (since, on the first get to an IVar, the lazy thread of execution should be started up.) Par is all about letting you move these executions around to be earlier or later, depending on your knowledge of the problem.

  3. Paul Liu says:

    IVar may be lazy, but not call-by-need.

Leave a Comment