ezyang’s blog

the arc of software bends towards understanding

April, 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

Mailbox: Advice for a sup first-timer

What is the Mailbox? It's a selection of interesting email conversations from my mailbox, which I can use in place of writing original content when I’m feeling lazy. I got the idea from Matt Might, who has a set of wonderful suggestions for low-cost academic blogging. From: Brent Yorgey I see you are a contributor […]

  • April 16, 2011

Tracing the compilation of Hello Factorial!

It is often said that the factorial function is the “Hello World!” of the functional programming language world. Indeed, factorial is a singularly useful way of testing the pattern matching and recursive facilities of FP languages: we don’t bother with such “petty” concerns as input-output. In this blog post, we’re going to trace the compilation […]

  • April 13, 2011

Bugs from using the wrong variable

I was supposed to have another post about Hoopl today, but it got scuttled when an example program I had written triggered what I think is a bug in Hoopl (if it’s not a bug, then my mental model of how Hoopl works internally is seriously wrong, and I ought not write about it anyway.) […]

  • April 11, 2011

Hoopl: Dataflow analysis

Once you’ve determined what dataflow facts you will be collecting, the next step is to write the transfer function that actually performs this analysis for you! Remember what your dataflow facts mean, and this step should be relatively easy: writing a transfer function usually involves going through every possible statement in your language and thinking […]

  • April 8, 2011