How to write programs in two easy steps

I’m bored, so I’m browsing the blog-o-tubes, and noticing the occasional comment wondering why functional languages like Haskell and Lisp are typically used for no more than implementing other programming languages. I won’t comment on the truth or otherwise of this claim, because I don’t think it’s a bad thing in any case. Here’s why — this is a technique I learned from Conor McBride (who learned it from his father Fred McBride), explaining how to write any computer program in two easy stages:

• Design and implement the programming language which would be best for solving the problem.
• Write the program in the language you’ve just implemented.

This may, on first hearing, seem less than helpful; sort of like telling someone that to play the guitar you just grab a guitar and move your hands around like a guitarist. But consider what is involved in implementing a non-trivial system (e.g. an AI for playing Go) — you spend some time coding up the domain knowledge (e.g. the rules of the game — this is where you design the language) and the rest of the time applying this knowledge to a specific problem (e.g. a strategy for winning the game — this is where you use the language).

I make the bold claim that most people who are faced with the task of programming a computer are not computer scientists or programmers by training, nor do they really want to know. They are perhaps physicists, engineers, mathematicians, accountants — experts in some other domain. I wouldn’t (in general, though I know several exceptions) expect them to have a deep understanding of my language of choice, Haskell, any more than they would expect me to, say, know how to design a bridge that doesn’t fall down, get an aeroplane off the ground, understand my tax return, or indeed do anything practically useful.

This is where the two stage approach to program design comes in. The programming language geek, with the help of a domain expert, designs a Domain Specific Language (DSL) for solving a certain class of problems. Then the physicists, engineers, mathematicians, accountants etc. can hack away at their own real problems blissfully unaware that they are making extensive use of laziness, monads, GADTs and so on. It’s just code reuse…

Haskell (along with other similar languages) is a particularly good language for implementing DSLs, in particular because algebraic data types allow you to express and manipulate abstract syntax easily and because Haskell makes it possible to embed DSLs as a library (Domain Specific Embedded Languages, or DSELs), thus saving you from writing a parser. Some examples which already exist are Lava (a language for describing circuit designs), Haskore (a music language) and Parsec (a language for building parsers). You could even consider Ivor a DSEL for building tactics for theorem proving. I think it’s also an area where dependently typed languages like Epigram will shine, because it will one day be possible to write verified interpreters for domain specific languages, and the users need not know anything about the details.

I don’t worry that I spend time working on languages that are primarily good for implementing other languages in. It’s these other languages that allow people to get real work done (like saving me from the wrath of the tax man), and if we write tools which make the verified implementation of these languages easier, we have done a good thing.

Greenspun’s Tenth Rule states that “Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.” I like to think this means that everyone writing in C or Fortran is following Fred McBride’s method, implementing a language then writing a program in it, whether they know it or not…