Idris to JavaScript: New and improved!

Posted on January 28, 2014 by raichoo

It’s been a long time since I’ve blogged about progress on the JavaScript side of Idris, too long actually. A lot of people picked up my blog examples only to find out that they didn’t work anymore. Tons of things have changed and I was way to busy to talk about them at length, sorry ’bout that.

Today I want to talk a little bit about what happens to your Idris code when you compile it to JavaScript. When this new code generator was introduced into Idris a lot of folks were very excited about the possiblity to run Idris programs in the browser or on Node. Once they looked at the generated code a lot of them turned away in horror (which is perfectly understandable and I’ll demonstrate why in a minute). But a lot has changed since then and I’d like to show you how.

The example code I’ll using is inspired from the purescript example which shows off purescript’s TCO. It’s not very spectacular but it’ll do.

module Main

recTest : Integer -> Integer
recTest = recTestHelper 1
  where
    recTestHelper : Integer -> Integer -> Integer
    recTestHelper n 0 = n
    recTestHelper n m = recTestHelper (n * m) (m - 1)


main : IO ()
main = print $ recTest 10000

Let’s look at what the generated code for the recTestHelper function looked like in the past (Brace yourself!).

var __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0 = function(me0,me1){
  var __var_0 = me0;
  var __var_1 = me1;
  return (function(__var_2){
    return (function(cse){
      if (cse.equals(__IDRRT__ZERO)) {
        return __var_0;
      } else {
        return (function(__var_3){
          return (function(__var_4){
            return new __IDRRT__Cont(function(){
              return __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0(__var_3,__var_4)
            })
          })((function(__var_4){
            return (function(__var_5){
              return __var_4.subtract(__var_5)
            })((function(__var_5){
              return __IDRRT__tailcall(function(){
                return __IDR__mEVAL0(__var_5)
              })
            })(__IDRRT__ONE))
          })(__IDRRT__tailcall(function(){
            return __IDR__mEVAL0(__var_1)
          })))
        })((function(__var_3){
          return (function(__var_4){
            return __var_3.multiply(__var_4)
          })(__IDRRT__tailcall(function(){
            return __IDR__mEVAL0(__var_1)
          }))
        })(__IDRRT__tailcall(function(){
          return __IDR__mEVAL0(__var_0)
        })));
      }
    })(__var_2)
  })(__IDRRT__tailcall(function(){
    return __IDR__mEVAL0(__var_1)
  }))
}

Ok that does not look like our recTestHelper function at all. One is not even sure what this monster is trying to do and how. Granted, with generated code comes some unreadabilty but this is atrocious. Anyway. This was the first attempt to translate Idris into JavaScript, it was more like a proof-of-concept rather than a production grade compiler.

However, things have changed, now we have an optimizer in place that is doing a whole lot of work. Lets take a look at what current JavaScript that is generated by Idris looks like.

var __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0 = function(me0,me1){
  var __var_2 = __IDRRT__tailcall(function(){
    return __IDR__mEVAL0(me1)
  });
  if (__var_2.equals(__IDRRT__ZERO)) {
    return me0;
  } else {
    return new __IDRRT__Cont(function(){
      return __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0(__IDRRT__tailcall(function(){
        return __IDR__mEVAL0(me0)
      }).multiply(__IDRRT__tailcall(function(){
        return __IDR__mEVAL0(me1)
      })),__IDRRT__tailcall(function(){
        return __IDR__mEVAL0(me1)
      }).subtract(__IDRRT__ONE))
    });
  }
}

Now this is a whole different ball game. Let’s break down what happens here.

There are two interesting elements in this code snippet I want to focus on first, __IDRRT__tailcall and __IDRRT__Cont. Let’s look at the code of these two functions.

var __IDRRT__tailcall = function(k) {
  var ret = k();
  while (ret instanceof __IDRRT__Cont)
    ret = ret.k();

  return ret;
};

var __IDRRT__Cont = function(k) {
  this.k = k;
};

So basically these two functions provide us with a trampoline for tailcalls. Now we can get a better understanding of what’s happening here.

This is pretty much what we wrote in the first place.

There is still room for even more optimizations here since we are evaluating some values more than once, but this is very close to what we wrote in the first place. I’m constantly working on the optimizer for faster and smaller code.

Some people also wondered why the generated code got so much bigger at some point. A lot of this additional code is the new BigInteger library I’m using now which is jsbn (presummably the fastest lib for BigIntegers in JavaScript that is out there at the moment) and it’s about 50% faster than the one I’ve been using before.

Another point of complaint was that the FFI examples posted on this blog don’t work anymore. This is true, the FFI also has changed and I encourage you to look at the tutorial since it now features a chapter about JavaScript code generation.

Hopefully this sheds some light on the changes that have happend to the JavaScript side of Idris. We are now approaching a level that seems more suitable for real development. I hope you find this post helpful :)

UPDATE 01.31.2014

After some more optimizer tweaking the code now looks like this (__IDRRT__EVALTC is an optimized version of evaluation in combination with a trampoline):

var __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0 = function(me0,me1){
  var __var_2 = __IDRRT__EVALTC(me1);
  if (__var_2.equals(__IDRRT__ZERO)) {
    return me0;
  } else {
    return new __IDRRT__Cont(function(){
      return __IDR__wnurecTesturecTestHelper0swnurecTesturecTestHelper0(
        __IDRRT__EVALTC(me0).multiply(__var_2),__var_2.subtract(__IDRRT__ONE)
      )
    });
  }
}

Looks like a great candidate for TCO :)

comments powered by Disqus