ezyang’s blog

the arc of software bends towards understanding

Haskell Heap

Bindings and CAFs on the Haskell Heap

New to the series? Go to the beginning. Today, we discuss how presents on the Haskell Heap are named, whether by top-level bindings, let-bindings or arguments. We introduce the Expression-Present Equivalent Exchange, which highlights the fact that expressions are also thunks on the Haskell heap. Finally, we explain how this let-bindings inside functions can result […]

  • May 9, 2011

How the Grinch stole the Haskell Heap

New to the series? Go to the beginning. Today, we introduce the Grinch. A formerly foul and unpleasant character, the Grinch has reformed his ways. He still has a penchant for stealing presents, but these days he does it ethically: he only takes a present if no one cares about it anymore. He is the […]

  • April 29, 2011

Functions produce the Haskell Heap

New to the series? Go to the beginning. We’ve talked about how we open (evaluate) presents (thunks) in the Haskell Heap: we use IO. But where do all of these presents come from? Today we introduce where all these presents come from, the Ghost-o-matic machine (a function in a Haskell program). Using a function involves […]

  • April 27, 2011

Implementing the Haskell Heap in Python, v1

New to the series? Go to the beginning. Here is a simple implementation of all of the parts of the Haskell heap we have discussed up until now, ghosts and all. heap = {} # global # ---------------------------------------------------------------------# class Present(object): # Thunk def __init__(self, ghost): self.ghost = ghost # Ghost haunting the present self.opened = […]

  • April 25, 2011

IO evaluates the Haskell Heap

New to the series? Go to the beginning. In today’s post, we focus on you, the unwitting person rooting around the Haskell heap to open a present. After all, presents in the Haskell heap do not spontaneously unwrap themselves. Someone has to open the first present. If the Haskell heap doesn’t interact with the outside […]

  • April 24, 2011

Evaluation on the Haskell Heap

New to the series? Go to the beginning. The Ghost of the Christmas Present In today’s post, we’ll do a brief survey of the various things that can happen when you open haunted presents in the Haskell heap. Asides from constants and things that have already been evaluated, mostly everything on the Haskell heap is […]

  • April 20, 2011

The Haskell Heap

The Haskell heap is a rather strange place. It’s not like the heap of a traditional, strictly evaluated language... ...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). When you actually want what’s […]

  • April 18, 2011