ezyang’s blog

the arc of software bends towards understanding

March, 2010

More fun with Futamura projections

Code written by Anders Kaseorg. In The Three Projections of Doctor Futamura, Dan Piponi treats non-programmers to an explanation to the Futamura projections, a series of mind-bending applications of partial evaluation. Go over and read it if you haven't already; this post is intended as a spiritual successor to that one, in which we write […]

  • March 31, 2010

The case of the Hash Array Mapped Trie

The fast, efficient association map has long been the holy grail of the functional programming community. If you wanted such an abstract data structure in an imperative language, there would be no question about it: you would use a hash table. But the fact that the hash table is founded upon the destructive update makes […]

  • March 29, 2010

Ad hoc wireless

Hello from Montreal! I'm writing this from a wireless connection up on the thirty-ninth floor of La Cité. Unfortunately, when we reading the lease, the only thing we checked was that it had "Internet"... not "Wireless." So what's a troop of MIT students with an arsenal of laptops and no wireless router to do? Set […]

  • March 24, 2010

Hunting for abstractions in mathematics

Abstraction (n.) The act or process of separating in thought, of considering a thing independently of its associations; or a substance independently of its attributes; or an attribute or quality independently of the substance to which it belongs. (Oxford English Dictionary) Abstraction is one of the most powerful beasts in the landscape of programming, but […]

  • March 22, 2010

Mutation sleuthing in Python

Python is a language that gives you a lot of rope, in particular any particular encapsulation scheme is only weakly enforced and can be worked around by a sufficiently savvy hacker. I fall into the "my compiler should stop me from doing stupid things" camp, but I'll certainly say, dynamic capabilities sure are convenient. But […]

  • March 19, 2010

Haskell, The Hard Sell

Last week I talked about how we replaced a small C program with an equivalent piece of Haskell code. As much as I'd like to say that we deployed the code and there was much rejoicing and client side caching, the real story is a little more complicated than that. There were some really good […]

  • March 17, 2010

Straitjacket programming

The importance of constraint is one well known to those who embark on creative endeavors. Tell someone, "you can do anything you want: anything at all," and they will blank, paralyzed by the infinite possibility. Artists welcome constraint. Writers like the constraint of a sonnet because it imposes form and gives a place to start; […]

  • March 15, 2010

Five tips for maintainable shell scripts

When I was seventeen, I wrote my very first shell script. It was a Windows batch file, bits and pieces very carefully cargo-culted from various code samples on the web. I had already had the exquisite pleasure of futzing with pear.bat, and the thought of scripting was not something I relished; "why not write the […]

  • March 12, 2010

Replacing small C programs with Haskell

C is the classic go-to tool for small programs that need to be really fast. When scripts.mit.edu needed a small program to be a glorified cat that also added useful HTTP headers to the beginning of its output, there was no question about it: it would be written in C, and it would be fast; […]

  • March 10, 2010

Being an expert considered harmful

It's a sunny day in your advanced symbolic programming class. Your teacher has just started going over monads—in Scheme, though—and you sit in the back of the classroom snarking about little tidbits of knowledge you know from Haskell. Suddenly, the teacher says (quite earnestly too), "Edward here seems to know a lot about monads. Why […]

  • March 8, 2010