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
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:
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:
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).
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 where (e':x') = norm (c+1) (e:x) main = take 4096 edigits
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.