Don Stewart

Just watched the talk. The technique the author's discovered is called "supercompilation" (note: this is distinct from "superoptimisation", mentioned in sibling comments).

The idea is to use an evaluation strategy which works at compile time, reducing statically-known expressions whilst shuffling around unknown values symbolically to preserve the semantics. The result ends up folding constants, inlining, unrolling, etc. automatically, just like the examples in the talk.

Whilst supercompilation can be slow, the main criticism is that resulting code is quite large, due to the amount of inlining.

The main difference between supercompilers and the technique discussed in the talk is that supercompilation is provably correct: it doesn't rely on testing or placing exhaustiveness requirements on the user. I don't think it's necessary to sacrifice correctness; the speaker mentioned the use of guards in JITs, and how he avoids them for speed, but I think that since we're performing such extensive rewriting of the code anyway, many redundant guards can be supercompiled-away, and those remaining can be shunted to the start of the program, so that no branches appear in the hot path.

The allusions to the scientific method seem to be about properties/invariants, and potential counterexamples to them. I'm all for finding and sharing properties of programs, both conjectured and proven, although I don't like the idea of assuming the conjectures are true.

I've looked into this in Haskell,…

Pure functional programming's core delusion is pretty clear as well: all state is immutable.

There is no "state" in functional programming, there is function application. Your program is a function from some value (inputs) to some value (the result). You write that program by composing various smaller programs with operators like (.) and (>>=) (or if you like being generic, (>>>)). There is no data, there is just function application.

So then, "state" becomes an imaginary concept that sometimes makes things easier to think about; if there is a sequence of computations that logically operate on the same "thing", then you call that "thing" the state. The State monad is nothing but syntax sugar that lets you very explicitly pretend that there is a such thing as state; something you can "get" at and "put" into as needed. This abstraction, BTW, is no different than state in any other language (which is why it comes up so much in hastily-written Haskell programs; you can just cut-n-paste from C and change the spelling of some keywords), except instead of "get" and "put", you just use variable names and "=". Otherwise, exactly the same concept and semantics, and very similar syntax everywhere.

In procedural languages, state is important because the procedures abstract CPU instructions, which operate on little boxes called "registers". But in functional programming, your program is not a list of things to do to a register, it's just functions. So state is not really…

The pretentious view that Haskell's core is a mathematical structure familiar to mathematicians is wrong.

Haskell borrows concepts from category theory (a "field" so abstract from most math that most mathematicians don't need but a handful of its concepts) to label typeclasses, and those typeclasses don't always follow from their namesake.

Further, Haskell could exist and keep its property of referential transparency without the the 'mathematical' structures or their names. Here's a version of Haskell without monads: http://donsbot.wordpress.com/2009/01/31/reviving-the-gofer-standard-prelude-circa-1994/

Monads, functors, arrows, etc. are more aesthetic than fundamental to the core nature of Haskell. They're just a bookish (and sometimes bureaucratic, IMO) design choice. What I mean by that, is that the language designers took a concept (referential transparency) and built an understandable structure, but beside and aside from this, made a bunch of nested, derived typeclasses of dubious value or purpose. Sometimes I look at a Haskell library and have a more academic version of the, "Why the fuck is this a class?" moment.

I'd like to comment tangentially that Haskell is almost the OOP/Java of the 2010's - the programming community claims that it makes your code "safer", and in some sense it very much does, but its features are being perverted and overhyped while its caveats are being forgotten.

> .. you can write vastly more complicated programs that are, say, 80% as fast as hand-optimized C for only 10% of the effort of hand-optimized C.

Computer Language Benchmarks of GHC versus C don't seem to be close to matching your 80% as fast claim [1]. Also, the 10% of the effort of hand-optimized C bit - seem to recall there was a caveat - "if you happen to Don Stewart" [2].

The following is just my vague, uninformed impression, but Haskell and Go seem to be opposite ends of a spectrum, with Rust somewhere in between:

Haskell: good for expert individuals and small teams. The language is highly sophisticated and the compiler is rather slow. At heart, it's a research language, so the direction might not always suit production use. If you contract out to a Haskell development shop, who do you turn to with your Haskell code-base if things don't work out?

Go: designed by Google for their use-case - large teams of commodity programmers. It's very quick to onboard programmers - they can be productive and non-dangerous quickly. The language is very simple and the compiler is very quick - which is again good for scaling large teams.

[1] https://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=ghc&lang2=gcc

[2] https://donsbot.wordpress.com/2008/05/06/write-haskell-as-fast-as-c-exploiting-strictness-laziness-and-recursion/

Good compilers don't keep immutable things immutable at runtime, but turn uses of clean high-level functional code into tight C-like loops.

https://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs-new-llvm-codegen/

It's been seven years since: that's GHC 6.13, and GHC 8.2.1 is being released soon. Performance is even better now as long as laziness doesn't bite you (which is much less rare than people think).

> you won't be able to convince him that a standard recursive-descent parser is 10x simpler to write and read

I don't know what a "compile-time parser" is, but someone used to a good parser combinator library is going to be difficult to convince.

http://www.haskellforall.com/2017/06/translating-c-parser-to-haskell.html

It reads like the formal spec of the language. Hand-writing recursive descent parsers isn't fun (given a sufficiently complex grammar) and expecting people to accept it as the One True Practical Non-Ivory Tower Way (and expressing dismay at not being able to convince them otherwise) is suggestive of monoculture, the kind that prides itself on copying code and using wrappers over the two or three first-class data structures that exist in the language for everything.

Since the other comments are platitudes, I'll try to give some concrete information. Well implemented purely functional data structures are usually anywhere from just as fast to about 20x slower. If the imperative version is tree like, the cost for lookups in the functional version is the same, but the cost for updating is a bit higher because a path needs to be copied rather than just 1 node modified in place. For a data structure like an unordered map, you can use a hash table backed by an array for the imperative version, but you'll have to use a tree for the purely functional one. This can cause about a 10x-20x slowdown.

For example in this post http://donsbot.wordpress.com/2009/09/26/very-fast-scalable-mutable-maps-and-hashes-for-haskell/ Haskell's Data.Map is compared with Judy arrays, and found to be 11x slower. Judy arrays themselves are about 2x slower than a basic hash table http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array/

Is this slow? Perhaps, but in most cases the difference is smaller. Compare this to the speed of Ruby vs C, that can easily be a 100x difference yet people use Ruby a lot because of productivity reasons.