Inside 206-105

Existential Pontification and Generalized Abstract Digressions

The Haskell Heap

/img/heap/title.png

The Haskell heap is a rather strange place. It’s not like the heap of a traditional, strictly evaluated language...

/img/heap/traditional-heap.png

...which contains a lot of junk! (Plain old data.)

In the Haskell heap, every item is wrapped up nicely in a box: the Haskell heap is a heap of presents (thunks).

/img/heap/present.png

When you actually want what’s inside the present, you open it up (evaluate it).

/img/heap/evaluated.png

Presents tend to have names, and sometimes when you open a present, you get a gift card (data constructor). Gift cards have two traits: they have a name (the Just gift card or the Right gift card), and they tell you where the rest of your presents are. There might be more than one (the tuple gift card), if you’re a lucky duck!

/img/heap/constructor.png

But just as gift cards can lie around unused (that’s how the gift card companies make money!), you don’t have to redeem those presents.

Presents on the Haskell heap are rather mischievous. Some presents explode when you open them, others are haunted by ghosts that open other presents when disturbed.

/img/heap/tricksters.png

Understanding what happens when you open a present is key to understanding the time and space behavior of Haskell programs.

/img/heap/evaluate.png

In this series, Edward makes a foray into the webcomic world in order to illustrate the key operational concepts of evaluation in a lazily evaluated language. I hope you enjoy it!

Next time: Evaluation on the Haskell Heap

Technical notes. Technically speaking, this series should be “The GHC Heap.” However, I’ll try to avoid as many GHC-isms as possible, and simply offer a metaphor for operationally reasoning about any kind of lazy language. Originally, the series was titled “Bomberman Teaches Lazy Evaluation,” but while I’ve preserved the bomb metaphor for thunks that error or don’t terminate, I like the present metaphor better: it in particular captures several critical aspects of laziness: it captures the evaluated/non-evaluated distinction and the fact that once a present is opened, it’s opened for everyone. The use of the term “boxed” is a little suggestive: indeed, boxed or lifted values in GHC are precisely the ones that can be nonterminating, whereas unboxed values are more akin to what you’d see in C’s heap. However, languages like Java also use the term boxed to refer to primitive values that look like objects. For clarity’s sake, we won’t be using the term boxed from now on (indeed, we won’t mention unboxed types).
http://i.creativecommons.org/l/by-sa/3.0/88x31.png

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

10 Responses to “The Haskell Heap”

  1. gasche says:

    Wait, you mean opening a present is a *mutation* of the heap؟

  2. Matthias says:

    > Wait, you mean opening a present is a *mutation* of the heap

    Yes, it is. Haskell does lots of mutation behind the scenes.

    Okasaki said something like “Lazyness can be seen as a very disciplined version of mutation.”

  3. fuzxxl says:

    And… what is an MVar or a mutable array in your concept of presents?

    Keep on! This is the best introduction to thunks I’ve ever seen.

  4. rian says:

    this is amazing. i definitely feel like there is a dearth of information about and attention to the time and space behavior of haskell programs. this is on purpose of course but i worry about using haskell for my microcontroller, i never know if that one badly programmed evaluation will start crunching and stalling.

  5. Mitch S says:

    Great metaphor! Love the bomb present. The ghost drawing cracks me up.

    Hooray for engaging the monkey-brain to understand abstract stuff!

  6. fuzxxl: Mutation won’t be treated in this series. Fortunately, there’s already a lot of good work about mutation, so I think people can use their existing intuition to figure this out.

  7. Schrödinger says:

    In reality a thunk is a box for Schrödinger’s cat. As long as you do not look into the box, the content is in a meta-state. Only if you open the box in order to observe the content, then its content turns into a final state.

  8. Ywen says:

    Unboxed types are stored on the stack, right?

  9. […] in the context of formal languages is that evaluation is postponed until absolutely necessary (Here is a cute (illustrated) blog post describing this lazy evaluation stuff). Take this code for […]

Leave a Comment