ezyang’s blog

the arc of software bends towards understanding

February, 2010

History as documentation

It's real easy to argue about the utility, style and implementation of source code comments, those good ole' pals of code that try to add supplementary information when the pure code isn't enough. However, to focus solely on the latest snapshot of any particular source file is to miss a wealth of information that is […]

  • February 26, 2010

The Art of Posing a Problem

Last week, I was talking with Alexey Radul to figure out some interesting research problems that I can cut my teeth on. His PhD thesis discusses "propagation networks", which he argues is a more general substrate for computation than traditional methods. It's a long work, and it leaves open many questions, both theoretical and practical. […]

  • February 24, 2010

Comonads and Convolutions

> {-# LANGUAGE GeneralizedNewtypeDeriving #-} > import Control.Comonad > import Data.List That scary Control.Comonad import from category-extras is going to be the subject of today's post. We're going to look at one possible implementation of comonads for non-empty lists that model causal time-invariant systems, systems whose outputs depend only on inputs that are in the […]

  • February 22, 2010

Type manipulation: Tricks of the trade

I present here a few pieces of folklore, well known to those practiced in Haskell, that I've found to be really useful techniques when analyzing code whose types don't seem to make any sense. We'll build practical techniques for reasoning about types, to be able to derive the type of fmap fmap fmap by ourselves. […]

  • February 19, 2010

Why we stay up late

I was having a discussion a few nights ago about attention, and someone mentioned the fact that contiguous blocks of time are precious. It's obvious once it's been pointed out to you, and with it in mind I've noticed my tendency to bucket useful activities into various categories: checking email, reading news feeds and simple […]

  • February 17, 2010

Hunting for constraints

> import Data.List > import Control.Monad The following question appeared as part of a numbers-based puzzle in the 2010 MIT Mystery Hunt: His final level on Wizard of Wor was equal to the smallest number that can be written as the sum of 4 non-zero squares in exactly 9 ways I'd like to explore constraint […]

  • February 15, 2010

Scheming environments

Environments are first-class objects in MIT/GNU Scheme. This is neat, because an integral part of the lexical structure of a Scheme is also a data-structure in its own right, able to encode data and behavior. In fact, the environment data structure is precisely what Yegge calls property lists, maps that can be linked up with […]

  • February 12, 2010

Sources of music

I love listening to music, especially new and interesting pieces that I've never heard before. Unfortunately, being a somewhat frugal spender my own personal collection of music grows very slowly; perhaps a bit too slowly for my own tastes. When I need new music, where do I turn? MixApp is a collaborative music listening application. […]

  • February 10, 2010

Nested loops and exceptions (Oleg Kiselyov)

Editorial. Today we interrupt our regularly scheduled programming to bring you a guest post by Oleg Kiselyov, reinterpreting our previous post about nested loops and continuations with exceptions. Hello! I noticed your recent article about nested loops and continuations. I should have commented on it using the provided form, but I was not sure how […]

  • February 8, 2010

Nested loops and continuations

The bread and butter of an imperative programmer is the loop. Coming from a C/assembly perspective, a loop is simply a structured goto which jumps back to a set location if some condition is not met. Frequently, this loop ranges over the elements of some list data structure. In C, you might be doing pointer […]

  • February 5, 2010