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:

Stack machines

Back in the time before at Durham, we had a snazzy whiteboard on which you could press a button and get a hard copy of your scribblings. We don’t have such a thing at St Andrews, but there are two other options. One is the smart board software, where you write onto a screen then the computer then renders it illegible for you (at least it does when I try it). My preferred way, though, is one I’ve borrowed from the Epigram gang. Just take a digital photo of the whiteboard…

At the minute, we’re trying to find a typed intermediate code for representing functional programs with explicit stack bounds. Here’s what James and I came up with on Friday: