How it all started

I was talking to frantic about some trick JavaScript question where we needed to use bind and apply in non obvious way and that reminded him of a similar problem where you needed to implement an add function that both works with arbitrary number of elements and can either be used as a number or another function.

test(add(1, 2), 3);
test(add(3)(4)(), 7);
test(add(3)(4)(5), 12);

It sounded fun so I asked him to provide me with some tests so that I could try to implement it. He did it https://github.com/frantic/currying and posted on the internal JavaScript group.

Then, Tadeu Zagallo, another co-worker working on React Native, saw it and while we were sharing our solutions mentioned that 140byt.es just closed down. I got emotional as I loved solving those kind of problems and for fun decided to shrink my implementation to see in how many characters it could fit. And this is how my Friday and Saturday vanished :p

In order to spread the fun, I posted it on Twitter and a lot of people helped out, including RReverser and sainaen who improved the existing solution!

Getting Started

In order to get started you need a valid implementation. Here is the code I wrote in ES6:

var add = (...args) => {
  var sum = args.reduce((a, b) => a + b);
  var fn = (...args) => add(sum, ...args);
  fn.valueOf = () => sum;
  return fn;
};

and "minified" it to be

91:var add=(...a)=>{var s=a.reduce((a,b)=>a+b),f=(...a)=>add(s,...a);f.valueOf=()=>s;return f}

But, unfortunately (or fortunately), ES6 has a lot of shorthand helpers that let you express this in a very concise way without much room for crazy hacks. So we decided to go the ES5 way instead.

The first version we started from was a direct translation of the ES6 version:

189:function add(){
  var s=[].reduce.call(arguments,function(a,b){return a+b});
  var f=function(){return add.apply(0,[s].concat([].slice.call(arguments)))};
  f.valueOf=function(){return s};
  return f;
}

There are three parts in this function: the sum, the returned function and valueOf. We'll see all the experiments we've done with the three.

Sum

Sadly, arguments is not a real array object so we need to do [].reduce.call(arguments instead of the normal version with less characters arguments.reduce(.

57:var s=[].reduce.call(arguments,function(a,b){return a+b})

One of the realization of this game is that creating a function is very expensive in characters. You've got to pay for function(){return} just to play. Let's see with a normal loop how we can write it shorter.

56:for(var s=0,i=0;i<arguments.length;++i){s+=arguments[i]}

We already won one character, but we can do better. arguments is very long, we can make a variable out of it.

52:for(var s=0,i=0,a=arguments;i<a.length;++i){s+=a[i]}

Turns out that the braces are not needed if there's only one statement in the body. 2 free characters.

50:for(var s=0,i=0,a=arguments;i<a.length;++i)s+=a[i]

At this point we're a bit stuck with the normal for loop. Thankfully, JavaScript has another way of looping through an array: for(var key in obj). It is technically supposed to be for objects but also works for arrays :p

40:var i,s=0,a=arguments;for(i in a)s+=a[i]

This is the shortest we could find using a normal loop. But JavaScript has many builtin functions that can be exploited in a few characters. In this case eval and join. Yes, eval! We care about code size, not best practices πŸ™‚

39:var s=eval([].join.call(arguments,'+'))

The caveat with using this version is that join doesn't respect valueOf but instead calls toString. So we need to lose one character there.

Curried function

The objective for this one is to create a function that calls add with an initialized value of the current sum. The naive version is the following:

74:var f=function(){return add.apply(0,[s].concat([].slice.call(arguments)))}

Again, we don't want an entire function for doing that, the trick we're going to use time and time again is bind to generate a function in much less characters.

33:var s=this.s||0,f=add.bind({s:s})

Turns out that this only work in non strict mode. But if you enable strict mode it doesn't work anymore because undefined.s will throw an exception. Also, if you have a global variable s it will break. We found a way to make it a bit smaller using arrays instead of objects.

32:var s=this[0]||0,f=add.bind([s])

What you would really like to do is to just bind(s), turns out that you can do that if you are in strict mode. Because if you call add(), then this will be undefined and ||0 will work fine.

27:var s=this||0,f=add.bind(s)

What if we just did this|0, it will convert the element into a signed 32bit integer and has the nice property that window|0 === 0 and undefined|0 === 0 so it works in both strict and non strict mode! The caveat is that the function no longer works with floating point numbers as 3.6|0 === 3.

26:var s=this|0,f=add.bind(s)

But then we realized that we didn't need to pass that initial value as this, we could just pass it as an additional argument. Not only making it shorter but another few characters, but also working with strict/non-strict and floats πŸ™‚

23:var s=0,f=add.bind(0,s)

Constant function

The last piece of the puzzle is to write a function that always return a number. This is something simple yet there are many ways to write it. Let's start with the naive version:

20:function(){return s}

The first attempt was to look at array functions for one that returns the first element and pass an array with just one. Turns out that join fits the bill. The only trick is that it converts the number into a string, so we need to cast it back to a number when we do the sum s+=+a[i] losing a character.

17:[].join.bind([s])

Then we figured out that we could use Number as a function to generate a number

16:Number.bind(0,s)

But, we're going to be evil again and use eval to shorten it even more!

14:eval.bind(0,s)

Putting it all together

We start with the following

108:function add(){var f,i,s=0,a=arguments;for(i in a)s+=a[i];
f=add.bind(0,s);f.valueOf=eval.bind(0,s);return f}

We have four variables f, i, s and a that we have to declare, but we don't really need all of them at the same time. We use isa together and then fs together. So we don't need to allocate a variable for f, we can reuse a or i.

106:function add(){var i,s=0,a=arguments;for(i in a)s+=a[i];
a=add.bind(0,s);a.valueOf=eval.bind(0,s);return a}

var i,s,a is a lot of characters, would be nice to be able to move it inside of the function declaration function add(i,s,a). Unfortunately, this only work in strict mode because in non-strict, if you override the variables it's also going to override the variables in arguments in the same position.

105:function add(i,s,a){s=0,a=arguments;for(i in a)s+=a[i];
a=add.bind(0,s);a.valueOf=eval.bind(0,s);return a}

Thankfully, when we switch to the eval version of the sum, JavaScript reads from arguments before setting the variable so it works even in non-strict mode πŸ™‚

105:function add(s,a){s=eval([].join.call(arguments,'+'));
a=add.bind(0,s);a.toString=eval.bind(0,s);return a}

Now we're getting in the final phase where we're trying to inline as many expressions as possible. When you have s=...;bind(0,s), you can turn it into bind(0,s=...) which saves two characters: a ; and a repetition of s.

103:function add(s,a){a=add.bind(0,s=eval([].join.call(arguments,'+')));
a.toString=eval.bind(0,s);return a}

In the same vein, we can transform a=...;a.toString=...;return a into return(a=...).toString=...,a. It transforms 3a and 2; into 2a and () which is one less character!

102:function add(s,a){return(a=add.bind(0,s=eval([].join.call(arguments,'+'))))
.toString=eval.bind(0,s),a}

Here, we use eval (4 characters) twice: once to compute the sum s=eval(...) and once to have a function that returns a constant eval.bind(0,s). It turns out that we can build a function that returns the sum by doing s=eval.bind(0,...) and in order to get the sum we use s(). Doing this we save another two characters to reach 100!

100:function add(s,a){s=eval.bind(0,[].join.call(arguments,'+'));
return(a=add.bind(0,s())).toString=s,a}

It turns out that you don't even need to eval in the sum itself, you can pass the string '1+2+3' as first argument to the add function and when it is finally time to toString, then you can evaluate this entire expression.

96:function add(s,a){return(a=add.bind(0,s=[].join.call(arguments,'+')))
.toString=eval.bind(0,s),a}

Conclusion

  • This was super fun πŸ™‚
  • I would have never imagined that there were so many avenues of optimization for this seemingly simple problem.
  • New JavaScript standards like strict mode and ES6 make writing more concise code easier.
  • In order to spawn collaboration, having a runnable specification is the critical.
  • No one person came up with all the optimizations, it was truly a collaborative effort.
If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • November 4, 2013 Bitwise Truthiness (0)
    In this blog post, I explore another form of truthiness in Javascript. What happens if you use a bitwise operator on a value like 0|value or ~~value. Context We recently turned on the JSHint bitwise rule by default and the following code was caught. var isValid = false; for […]
  • August 29, 2011 Javascript: Improve Cache Performance: Reduce Lookups (2)
    In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances. Common pattern In order to test if the key is already in the cache, the usual pattern is to use key […]
  • July 4, 2012 CSS – Vertical Height of Smileys (1)
    There's one big issue when displaying images inline like smileys is to position them at the right height. Using vertical-align pre-sets Usually what you do is try to use vertical-align and test all the possibilities. Then you are frustrated because you can't find the one that is […]
  • January 8, 2010 Javascript – Sorting Table (15)
    For my new project on World of Raids I have to implement a table sorting. The browser not stable sorting and the faster sorting trick add difficulty to the task. String Comparison As mentionned in the Speed Up Javascript Sort() article, using a string as a key to represent each […]
  • October 26, 2011 Javascript Presentation – Slides & Video (2)
    I've done the Javascript presentation. It went alright and I hope that I taught things to people. I'm sorry for my blog reader but it's in French :) Few remarks: The code in the slide was not big enough, people in the back couldn't read it. It also appears crappy in the […]