ezyang’s blog

the arc of software bends towards understanding

July, 2010

Suggestion box

Taking a page from Raymond Chen’s blog, please post suggestions for future blog posts by me. What would you like to see me explain? What do you think would be amusing if I attempted to write a post about it? Topics I am inclined to cover: Almost anything about Haskell, GHC and closely related maths. […]

  • July 30, 2010

Delaying implicit parameter binding

Today, we talk in more detail at some points about dynamic binding that Dan Doel brought up in the comments of Monday’s post. Our first step is to solidify our definition of dynamic binding as seen in a lazy language (Haskell, using the Reader monad) and in a strict language (Scheme, using a buggy meta-circular […]

  • July 28, 2010

Reader monad and implicit parameters

For when the Reader monad seems hopelessly clunky The Reader monad (also known as the Environment monad) and implicit parameters are remarkably similar even though the former is the standard repertoire of a working Haskell programmer while the latter is a GHC language extension used sparingly by those who know about it. Both allow the […]

  • July 26, 2010

Managing foreign pointers effectively

Foreign.ForeignPtr is a magic wand you can wave at C libraries to make them suddenly garbage collected. It’s not quite that simple, but it is pretty darn simple. Here are a few quick tips from the trenches for using foreign pointers effectively with the Haskell FFI: Use them as early as possible. As soon as […]

  • July 23, 2010

Pipelines and continuations

Attention conservation notice. Function pipelines offer an intuitive way to think about continuations: continuation-passing style merely reifies the pipeline. If you know continuations, this post probably won’t give you much; otherwise, I hope this is an interesting new way to look at them. Why do you care about continuations? They are frequently an extremely fast […]

  • July 21, 2010


System.Posix.Redirect is a Haskell implementation of a well-known, clever and effective POSIX hack. It’s also completely fails software engineering standards. About a week ago, I excised this failed experiment from my work code and uploaded it to Hackage for strictly academic purposes. What does it do? When you run a command in a shell script, […]

  • July 19, 2010

Maximum matching deadlock solution

Last Monday, I presented a parallel algorithm for computing maximum weighted matching, and noted that on real hardware, a naive implementation would deadlock. Several readers correctly identified that sorting the nodes on their most weighted vertex only once was insufficient: when a node becomes paired as is removed from the pool of unpaired nodes, it […]

  • July 16, 2010

Flipping arrows in coBurger King

Category theory crash course for the working Haskell programmer. A frequent question that comes up when discussing the dual data structures—most frequently comonad—is “What does the co- mean?” The snippy category theory answer is: “Because you flip the arrows around.” This is confusing, because if you look at one variant of the monad and comonad […]

  • July 14, 2010

Graphs not grids: How caches are corrupting young algorithms designers and how to fix it

Subtitle: Massively multithreaded processors make your undergraduate CS education relevant again. Quicksort. Divide and conquer. Search trees. These and other algorithms form the basis for a classic undergraduate algorithms class, where the big ideas of algorithm design are laid bare for all to see, and the performance model is one instruction, one time unit. “One […]

  • July 12, 2010

Safety first: FFI and threading

Update. While this blog post presents two true facts, it gets the causal relationship between the two facts wrong. Here is the correction. Attention conservation notice. Don’t use unsafe in your FFI imports! We really mean it! Consider the following example in from an old version of Haskellwiki’s FFI introduction: {-# INCLUDE <math.h> #-} {-# […]

  • July 9, 2010