Log in

Next 10

Mar. 17th, 2009

Haskell is sandbox crack!

I've been spending my Copious Free Time lately trying to implement a simple dynamically-typed language in Haskell, both because I like this kind of programming and to make me a better Haskell programmer. Learning Haskell isn't like learning most other programming languages. With most programming languages, you work with the language for a few weeks or months and then feel pretty confident that you understand most of what's going on. Sure, there are idioms and design patterns you don't know, but you can pick those up as you go along. In contrast, with Haskell you stumble along in a fog, then find a map that gives you a clue which way to go, then stumble a bit further, then realize that although you got where you wanted to go, you could have gotten there much more easily using a different path, then you backtrack and try again, then you find another map, etc. etc. In other words, even when you know how to do something you keep finding better ways of doing the same thing.

This is extremely time-consuming and frustrating, and yet I continue to do it. Why?

One reason is obvious: Haskell is a pure functional language. And that means that Things Just Work in a Sensible Way. It also means that things compose nicely, so you can keep stacking abstractions on top of abstractions, and removing all the repeated code to build better abstractions. So you can program at a very high level. Well-written Haskell programs seem almost stratospheric in their abstraction level compared to well-written programs in other languages.

There's another reason that is less obvious: Haskell is sandbox crack. What I mean by this is that what Haskell does better than any other language I know of is to allow programmers to define isolated computational sandboxes that handle some aspect of the overall computational work. This is what Haskell monads are mainly used for. So instead of allowing functions to do arbitrary input/output (and thus break functional purity), Haskell provides you with the IO monad and tells you that all of your input/output must be done in the context of that monad. So now you have a clean separation between pure functions (that don't do any I/O, and thus that Behave Nicely), and those that do. BUT: once you get a taste for this sort of thing, you become addicted to it, and you're never satisfied. Suddenly you say "My application has to read from an input stream, but it doesn't have to write to an output stream; why should I use the IO monad when I'm not going to be writing anything?" So you use the Reader monad instead. If you just need to write and not read, you use the Writer monad. You can use IO to give you mutable variables with imperative update, but if you don't actually have to do input/output, why use IO (which is more general than you want)? You can use the ST monad instead. Or if you only have a couple of small piece of state, why use the ST monad, which handles arbitrary amounts of state (and is implemented in terms of the IO monad anyway, which I find kind of ugly). So you use the State monad, which only handles a fixed amount of state. And on and on. Each new sandbox allows you to make stronger statements about what your code is allowed to do, and more importantly, what it isn't allowed to do. Different parts of your program need different sandboxes, and if some parts need more than one you can use monad transformers to add up sandboxes to make larger sandboxes. And all is well in the world (or should I say the RealWorld?).

Then eventually you reach a situation where the sandboxes that Haskell provides you aren't quite sufficient to give you the sandbox you want, and you post angry emails to haskell mailing lists saying something like "Goddamn it! What I need are third-order existential abstract generalized monadoids, and I cannot believe that Haskell doesn't support this natively!" And you're serious, and you wonder why nobody else takes you seriously. And if you're Oleg, you write an article showing how Haskell's type classes can already support third-order existential abstract generalized monadoids, but there is an obscure corner case in which they may break some natural invariant. And if you're not Oleg, you try to understand what Oleg wrote and eventually get about 20% of it. And then you use some workaround which would be considered incredibly elegant in any other language but which breaks your heart because you can't make your sandbox quite as small as you want it to be, so you feel like a coding slob. You're embarrassed to show anyone else your code, but it does work.

And this is a good thing. Because this is part of the process by which programming languages will become what they need to become. But nobody said that it was going to be pleasant.

Aug. 14th, 2008

The Y Combinator (Slight Return)


How to Succeed at Recursion Without Really Recursing

Tiger got to hunt,
Bird got to fly;
Lisper got to sit and wonder, (Y (Y Y))?

Tiger got to sleep,
Bird got to land;
Lisper got to tell himself he understand.

    — Kurt Vonnegut, modified by Darius Bacon


I recently wrote a blog post about the Y combinator. Since then, I've received so many useful comments that I thought it was appropriate to expand the post into a more complete article. This article will go into greater depth on the subject, but I hope it'll be more comprehensible as well. You don't need to have read the previous post to understand this one (in fact, it's probably better if you haven't.) The only background knowledge I require is a tiny knowledge of the Scheme programming language including recursion and first-class functions, which I will review. Comments are (again) welcome.

Read moreCollapse )

Jul. 20th, 2008

The Y Combinator

OK, I'm going to try to explain what the Y combinator is, why it's interesting, and how it works. I'll have to include a bit of background information to try to make this post self-contained.

The Y combinator has become a bit of a cool buzzphrase since Paul Graham named his startup incubator company Y Combinator. Why did he choose that name? I think the reason is that he wanted to attract the kind of programmers who were smart enough to have heard about the Y combinator, and who actually care about this kind of thing. So if you understand the Y combinator, maybe you can get some brownie points with Paul if you're interested in working with his company. If you meet him, say hi for me.

Before I explain what the Y combinator is or why (no pun intended) it's important, I want to explain the problem that the Y combinator solves. Let's say you have a very simple programming language which does not have recursion as a built-in feature. (If you don't know what recursion is, Wikipedia is your friend.) However, let's say that your programming language does have one fairly advanced feature: it supports first-class functions. This means that functions can be treated as data: they can be passed as arguments to other functions, they can be created on the fly, and they can be returned as the result of a function. As we'll see, some very simple languages do have this property.

So what is the problem that the Y combinator solves? Basically, it's this: The Y combinator allows us to define recursive functions in computer languages that do not have built-in support for recursive functions, but that do support first-class functions.

That's it. That's what the Y combinator allows us to do. It's important to note that the Y combinator is mainly important to theoretical computer scientists, especially programming language theorists who tend to work a lot with minimal programming languages. It's unlikely that you're going to be using it much in practical programming (or at least I haven't; maybe that just means that I'm not enlightened enough yet). So why should you care, other than as a way to impress Paul Graham when you present him with your cool internet startup idea? For this reason: it's one of the most beautiful and counterintuitive ideas in all of computer science. The Y combinator is one of those things that makes me feel like computer science is an art on the level of great painting or poetry. It's the same reaction I have when I think about Godel's incompleteness theorem. Basically, learning about the Y combinator will teach you to appreciate beauty in programming.

Read moreCollapse )

Apr. 10th, 2008


Wow, it's been a long time since I wrote a blog post. Sorry about the delay in finishing my Haskell state monad series; it's coming, I promise.

The reason for this post is that I stumbled upon a very cool free (and well-documented) interpreter for the Forth language written in x86 assembly language. That implementation, by Richard Jones, can be found here, if you're impatient. In my previous post about foundational programming languages, I described Forth as a very cool but not quite foundational language. Here I'll expand on why I think Forth is cool, and why every serious computer language geek should look into Forth.

Read moreCollapse )

Jan. 22nd, 2008

Haskell state monads, part 2

In my previous post, I described in general terms how state transformations are represented in functional languages like Haskell that don't have the concept of mutable state (assignment to variables). There are different ways to do this, but the way that most closely simulates the way things work in imperative languages is by using state monads. This involves taking an imperative computation and breaking it down into very small subcomputations, each of which is a very simple state transformation. In this post, I'm going to expand on this, showing what I mean by "simple state transformation". I'm going to try to explain not only how state monads work in Haskell, but why they work the way they do.

Read moreCollapse )

Jan. 21st, 2008

Haskell state monads, part 1

I found the concept of state monads in Haskell quite hard to grasp for a long time, so I thought I'd give a (hopefully) brief description of what they are, why they're useful, and how they work. In addition to being useful and interesting by themselves, understanding state monads will make it much easier to understand the IO monad, which is how input/output is done in Haskell (and which is thus one of the most useful monads).

Read moreCollapse )

Jan. 16th, 2008

Ruby critique, part 1

A couple of friends of mine have written a book about Ruby on Rails called RailsSpace. I was a tech reviewer for the book (at least for a while, long story). I was interested in the book because I've always wanted to learn web programming (well, maybe not in the womb, but immediately after that for sure) and Rails seemed like a mature and agile web framework. Of course, I'd have to learn Ruby to understand the code. I've been using Python for many years and I like it; it's clean and (for the most part) simple. Since Python and Ruby are quite similar, I figured I could follow the code without too much work, and I could. However, I was interested enough in the peculiarities of Ruby (those areas where it was markedly different from Python) to start reading the PickAxe book in order to learn the language more thoroughly. I was also considering teaching the language as part of my CS 11 course at Caltech.

I really, really, really wanted to like Ruby. In fact, there are many features of the language that I do like. However, I kept hitting misfeatures that made me cringe and not want to use the language. Recently, I've discovered the Django web framework, which seems to be just about as capable as Rails and written in Python, so my motivation for mastering Ruby has waned considerably. What I'd like to talk about here are the features of Ruby that bug me, as well as the features I like. This is not going to be a FUD-laced diatribe against the language; I just want to point out some features that I consider to be misfeatures in the hope that the Ruby community can wake up and fix things. I think that there is a terrific smaller language inside Ruby struggling to get out, and I'd like to see it get out. But to do that, we have to be able to separate the wheat from the chaff.

Read moreCollapse )

How not to explain Haskell monads

One of the key concepts in Haskell that sets it apart from other programming languages is the concept of a "monad". People seem to find this difficult to learn (I did as well), and as a result there are loads of monad tutorials on the web, some of which are very good (I particularly like All About Monads by Jeff Newbern). It's even been said that writing a monad tutorial is a rite of passage for new Haskell programmers. However, one big problem with many monad tutorials is that they try to explain what monads are in reference to existing concepts that the reader already understands (I've even seen this in presentations by Simon Peyton-Jones, the main author of the GHC compiler and general Haskell grand poobah). This is a mistake, and I'm going to tell you why.

Read moreCollapse )

Jan. 15th, 2008

"Foundational" programming languages

I was reading this Smalltalk tutorial the other day. I found it excessively pedantic, but one turn of phrase caught my eye: the author claims that Smalltalk is a "foundational" programming language. I agree with him, but what does this term mean? I would say that to me, a foundational language is one which is such a good exemplar of a particular programming paradigm that it can be seen as the embodiment of that paradigm. Furthermore, foundational languages are worth learning even if you never program any substantial applications in them, because they will expand your mind and thus make you a better programmer.

Read moreCollapse )

Welcome to my blog!

OK, I finally decided to start a blog so I could rant about programming-related topics.  I've written a few rants that have already gotten quite a bit of visibility on reddit.com and similar sites (to my surprise), but these days I don't have the time or patience to write out long, clear, insightful essays on programming-related topics.  So instead, I thought it would be nice to have a site where I can write short, poorly-thought-out, semi-grammatical, and generally incoherent ramblings on the topic of programming and programming languages as said ramblings occur to me.  Isn't that the way of the internets nowadays?

What you (hopefully) won't find here is any information on my personal life or anything about me other than my programming-related interests.  I also apologize in advance for not posting any cute pictures of my cats.

Next 10