Elm Converts Tail Calls to Loops!
Submitted by Bill St. Clair on Wed, 12 Oct 2016 19:19:50 GMT
I've been converting my Kakuro game at kakuro-master.com to Elm. I'm loving it. I decided I needed a hash function, and not finding any good ones, I wrote my own, connecting to a JavaScript implementation I found via a quick Google search.
I figured I might as well provide it to the community, so I packaged it up as a module, pushed it to GitHub, and did "elm package publish" to upload it to the community packages site. I was met with this bug report:
It is not possible to publish packages with native modules.
Elm compiles to JavaScript right now, but that may not always be true. For the long-term health of our package ecosystem, as many packages as possible should be written in Elm. This definitely means we will grow a bit slower, but I am willing to pay that cost if it leads to a better community and ecosystem!
Oh, well. I understand. Evan Czaplicki is working on non-JavaScript backends, and doesn't want the conversion to get any worse than it already is.
So I decided to convert the JavaScript library into Elm, just for practice. It has lots of loops, which need to be converted to recursion in Elm, so I wanted to see if I was setting myself up for stack overflow. Apparently, not. Let-bound functions can call themselves recursively, and the compiler turns tail calls, in both let-bound functions and top-level functions, into loops in the generated JavaScript. There's no need to worry about stack overflow.
Here's the Elm code:
foo : Int -> Int -> Int
foo =
let foo' = (\y z ->
if y<= 0 then
z
else
foo' (y-1) (z+1))
in
foo'
bar : Int -> Int -> Int
bar y z =
if y <=0 then
z
else
bar (y-1) (z+1)
And here's the output of the compiler:
var _billstclair$elm_sha256$Temp$foo = function () {
var foo$ = F2(
function (y, z) {
foo$:
while (true) {
if (_elm_lang$core$Native_Utils.cmp(y, 0) < 1) {
return z;
} else {
var _v0 = y - 1,
_v1 = z + 1;
y = _v0;
z = _v1;
continue foo$;
}
}
});
return foo$;
}();
var _billstclair$elm_sha256$Temp$bar = F2(
function (y, z) {
bar:
while (true) {
if (_elm_lang$core$Native_Utils.cmp(y, 0) < 1) {
return z;
} else {
var _v0 = y - 1,
_v1 = z + 1;
y = _v0;
z = _v1;
continue bar;
}
}
});
But it's not smart enough to handle tail-calls correctly for two mutually-recursive functions, each of which tail-calls the other. Can't say I'm surprised. It's certainly possible to do, but it would be much easier if JavaScript just provided tail call optimization. Then the generated code would work. As it happens, the new ECMAScript 6 DOES provide tail-call optimization.
Here's my mutually-recursive Elm example:
foo : Int -> Int -> Int
foo y z =
if y <=0 then
z
else
bar (y-1) z
bar : Int -> Int -> Int
bar y z =
foo y (z + 1)
And here's the generated JavaScript:
var _billstclair$elm_sha256$Temp$foo = F2(
function (y, z) {
return (_elm_lang$core$Native_Utils.cmp(y, 0) < 1) ?
z :
A2(_billstclair$elm_sha256$Temp$bar, y - 1, z);
});
var _billstclair$elm_sha256$Temp$bar = F2(
function (y, z) {
return A2(_billstclair$elm_sha256$Temp$foo, y, z + 1);
});
The single self-recursive program is all I need for my sha256 loops. And now I know that I have to keep the recursion inside ONE Elm function, until ECMAScript replaces JavaScript inside major browsers.
