Haskell nearly never existed. They originally planned to build on David Turner’s Miranda language rather than invent a new one.

Released in the 1980s, Miranda compiles a Haskell-like language to a certain set of combinators which a C program interprets. This is precisely what we do!

In January 2020, Miranda’s source was released. Its approach to compilation has remained unchanged through the years, yielding an excellent opportunity for an exhibition match.

▶ Download the files from this contest: cmpmira.tar.gz.

These go to eleven

We bump up a Miranda example that solves the eight queens puzzle to 11 queens:

queens 0 = [[]]
queens (n+1) = [q:b|b<-queens n;q<-[1..11];safe q b]
safe q b = and[~checks q b i|i<-index b]
checks q b i = q=b!i \/ abs(q-b!i)=i+1
main = queens 11

On my laptop, to build mira, I had to first edit the Makefile and change quotehostinfo to ./quotehostinfo. Afterwards:

$ mira -make q11.m
$ time mira -exec q11.m > /dev/null

real    0m8.132s
user    0m8.111s
sys     0m0.020s

We translate it for our assembly compiler. We need much more code as we lack a standard library:

▶ Toggle q11.hs

On my laptop:

$ (cat rts.c;./assembly < q11.hs) > q11.c
$ cc -O2 q11.c -o q11
$ time ./q11 > /dev/null

real    0m6.783s
user    0m6.734s
sys     0m0.048s

I can’t help feeling proud. Miranda uses Turner’s bracket abstraction algorithm, which pushes Schönfinkel’s classic approach about as far as it can go. It has a large set of combinators, including dedicated combinators for map and fold. And surely its runtime system must be expertly tuned.

Our program, on the other hand, compiles to a handful of basic combinators, uses the Scott encoding for all data types except unsigned ints, and the source to its hastily designed virtual machine prizes brevity over efficiency: it began life as an IOCCC entry after all. Indeed, simple changes boost its speed by 10%, which we shall examine in depth another day.

But really its performance has little to do with my prowess. The credit goes to Oleg Kiselyov’s bracket abstraction algorithm (with minor tweaks from a few syntactic rewrites).

▶ Toggle combinators

A second opinion

The difference is even more pronounced for another example that computes e to 4096 decimal places:

$ time ./e4096 > /dev/null

real    0m6.532s
user    0m6.471s
sys     0m0.060s
$ time mira -exec e4096.m > /dev/null

real    0m14.350s
user    0m14.321s
sys     0m0.013s

The Miranda original:

edigits = "2." ++ convert (repeat 1)
convert x = mkdigit (hd x'):convert (tl x')
            where x' = norm 2 (0:map (10*) x)
mkdigit n = decode(n + code '0'), if n<10
norm c (d:e:x) = d + e div c: e' mod c : x', if e mod c + 9 < c
               = d + e' div c : e' mod c : x', otherwise
                 (e':x') = norm (c+1) (e:x)
main = take 4096 edigits

Our version:

▶ Toggle e4096.hs

A rematch?

See David Turner’s talk, Open Sourcing Miranda, especially for tips on updating C code written 30 years ago! I was pleased to hear that:

  • Miranda’s VM has an ATOMLIMIT that is like our scheme of addressses starting at 128, with lower values representing combinators. (Though unlike Miranda, we box our characters.)

  • Turner talks about rewriting Miranda’s fragile conservative garbage collector. We began with a robust copying garbage collector.

  • Turner also talks about rewriting much of the C in Miranda. Been there, done that: we wrote everything but the VM in Haskell from the start.

But most of all, I’m pleased Miranda is alive again, and look forward to rematches with future releases.

Ben Lynn blynn@cs.stanford.edu 💡