Thursday, 22 August 2019

Harrop's Tenth Rule

I was just reading one of the many self-soothing essays from the Lisp community and remembered my parody of Greenspun's Tenth Rule:
"Any sufficiently complicated Lisp program contains an ad hoc informally-specified bug-ridden slow implementation of half of ML."
Specifically, I was amazed by the following quote from that essay:
"Dr. Mark Tarver — twice-quoted, above — wrote a dialect of Lisp called Qi. It is less than ten thousand lines of macros running atop Clisp. It implements most of the unique features of Haskell and OCaml. In some respects, Qi surpasses them. For instance, Qi's type inferencing engine is Turing complete. In a world where teams of talented academics were needed to write Haskell, one man, Dr. Tarver wrote Qi all by his lonesome.
Read that paragraph, again, and extrapolate."
Several misconceptions are packed into this one paragraph.

  1. Qi and Shen are nowhere near implementing "most of the unique features of Haskell and OCaml".
  2. As an integral part of the compilation process, the objective is to make type inference as efficient as possible in all cases of practical interest. Making it Turing complete is precisely the opposite so far from "surpassing" conventional solutions this is far worse in practice. Furthermore, C++ templates and F# type providers already demonstrated how awful compile times are when compilation stages are made Turing complete.
  3. The "teams of talented academics" weren't just writing the compiler, they were inventing the languages.

Whereas Standard ML had a formal specification and significant parts of OCaml have been proven correct, Qi and Shen are ad-hoc and informally specified.
Whereas Haskell and OCaml are mature languages (my company had 1,000 industrial clients who were using OCaml!), Qi and Shen boast ~100 tests in the compiler suite and no users at all (their subreddit has seen 14 posts over the past 9 years!) so we can assume they will be bug ridden.
Back in the day, Mark Tarver ran a benchmark comparing his Qi code to my OCaml code and found that Qi was 1.8x slower.
So this is exactly what I was talking about when I first wrote my tenth rule.