Monday, July 28, 2014

I like ES6...works well, even for golfing (factorial demo hack)

Disclaimer: All code in this post is licensed under the BSD license.


Update: updated much of the code, made the JS smaller and the assembly half the instruction size. Also made the comments fit a little better space-wise.

Everyone knows about JavaScript and the basic factorial function, and here's the basic recursive implementation:

// ES5 and previous
function fact(n) {
  if (x > 0) {
    return n * factorial(n - 1);
  } else {
    return 1;
  }
}

// ES6
let fact = n => n > 0 ? n * factorial(n - 1) : 1;

But, I find this hack fairly cool: it basically takes enormous advantage of precedence and how logic statements work in ECMAScript. The hack assumes integer input.


// ES5 and previous
function fact(n) {
  return +(n < 1) || n * fact(n - 1);
}

// ES6
let fact = n => +(n < 1) || n * fact(n - 1);

The hack version also takes advantage of an implicit boolean-to-integer cast, which is usually quicker than a conditional. Code golfing is a little fun for these kinds of hacks, so let's compare a golfed C/C++ version to this ECMAScript hack unminified (using the ES6 versions):


int f(int n){int r=1;while(n--)r*=n;return r;} // Golfed C/C++
let fact = n => +(n < 1) || n * fact(n - 1); // Unminified ES6
function fact(n) { return +(n < 1) || n * fact(n - 1); } // Unminified ES5

And minified:

int f(int n){int r=1;while(n--)r*=n;return r;} // C/C++
function f(n){return +(n<=0)||n*f(n-1)} // Minified ES5 and previous
let f=n=>+(n<1)||n*f(n-1); // Minified ES6

Here's an explanation of the hack, comments inline:


// This works in all ECMAScript standards, from ECMAScript 3 through
// ECMAScript 6 and beyond.
function fact(n) {
  return +(n < 1) // This implicitly casts from boolean to
                  // integer, retaining truthiness.
                  // If true, this returns 1 and does not
                  // evaluate the right side.
         ||       // If false, evaluate the next part.
         n * fact(n - 1); // Here's some pseudocode explaining
                          // this:
                          //
                          // 1. Remember n in a pseudo-variable
                          //    x.
                          // 2. Decrement n by 1.
                          // 3. Apply the factorial function to
                          //    n.
                          // 4. Multiply it by the pseudo-
                          //    variable x.
                          // 5. Return the value.
}

Here's the function without comments:

function fact(n) {
  return +(n <= 0) || n * fact(n--);
}

let fact = n => +(n <= 0) || n * fact(n--);

You'll never beat assembly in speed, though... (this is written for x86 using Intel syntax)


; And almost in size...this is surprisingly short.
_fact: pop ecx    ; assumes cdecl calling convention, returns
       mov eax, 1 ; on eax
.loop: mul ecx
       loop .loop
       ret