Add a Clean implementation

[camilstaps]

tl;dr: this adds an implementation in Clean which can be interpreted in WebAssembly. Benchmark result corrected for machine differences is 52.79ms; significantly slower than Idris but faster than TypeScript and Asterius. Code size is average.

---

I don't know if you're interested in pull requests for other languages, so feel free to ignore this. However, when I saw this project announced on the Haskell Weekly I thought it could be a nice larger benchmark to compare the WebAssembly interpreter for Clean with backends for other languages. Of course, it should be noted that this is an interpreter backend and the others are (AFAIK) all compilers.

Clean is a functional programming language similar to Haskell. It compiles through an intermediate language for an abstract machine based on graph rewriting, the ABC machine. It is possible to run Clean in the browser through WebAssembly with an interpreter for the ABC machine. For more details, see the interpreter repository and doi:10.1145/3412932.3412941.

Some notes about the implementation:

• Clean uses uniqueness types (the * in *CPU) for mutability. Values of a unique type are guaranteed to be referred to only once, so that they can be updated in place. This allows fast updates of CPU registers and memory. This is the standard way to implement something like this in Clean, rather than using IORefs or hiding mutability in a monad.
• In fact, unique types don't play nice with monads, so I was unable to follow the Haskell implementation very strictly. This makes the comparison a bit unfair. On the other hand, if I remember correctly GHC has lots of monad optimizations which the Clean compiler does not have since monads are used much less in Clean, so using monads would also be unfair, in a way.
• There are many more optimizations possible here (e.g. 20% by inlining some functions to let the compiler improve strictness analysis results), but I did not include these for fairness.

I compared my results with the JavaScript implementation, which was the easiest to set up for me. This gives 1.61ms for JavaScript and 40.09ms for Clean. The time reported for JavaScript on your blog is 2.12ms, so corrected for that Clean has 2.12/1.61*40.09 = 52.79ms.

Some other notes:

• The JavaScript FFI of the ABC interpreter is rather slow and as a result the test spends quite some time in copying the program ArrayBuffer to the WebAssembly heap. I am primarily interested in the speed of the backend, so I would be interested in a program that runs for more than ±4000 instruction cycles. I haven't looked at the Asterius code, but something similar may be going on there. The other backends target JavaScript, so they don't need to copy the buffer.
• The generated ABC bytecode is 32,504 bytes. However, an additional 192,777 bytes are needed by the runtime system and supporting JavaScript code (for a total of 225,281 bytes). The runtime system has a fixed size. I think likewise Asterius will contain things like a garbage collector that are counted towards the total, whereas Idris generates JavaScript and probably does not include a garbage collector if it relies on the JavaScript garbage collector. So the code sizes measured for just one application may be only a rough indication of the size of the actually generated code. Essentially, if the Idris code grows with a factor 2, I don't expect the Asterius code to grow with a factor 2 as well. I don't know if you're interested in pull requests for other languages, so feel free to ignore this. However, when I saw this project announced on the Haskell Weekly I thought it could be a nice larger benchmark to compare the WebAssembly interpreter for Clean with backends for other languages.

[gergoerdi]

Any idea why I might be unable to build this on a fresh install of Clean and Nitril?

Never mind, turns out I had clm installed in my $HOME/bin from back in 2008 when I last played with it at uni :D

[gergoerdi]

Good stuff. Merged in c4bab9076ab8fef9ae4cd9256fed4b402ab7dd46. For what it's worth, I'm seeing 40ms; but then again, if you look at my blogpost, I also had to update the JS number because for some reason I see faster numbers now...

[camilstaps]

Cool, thanks!