The history of one task: The shortest JavaScript reader

It was in the evening, on the eve of the annual conference of HolyJS in St. Petersburg. Our company is not the first year sponsor: accordingly, it has its own stand with interesting things for the inquisitive mind of caring developers. When the main course was ready and all the tasks were updated and finished, I decided to throw some intellectual food at night with my colleagues:

Write a memoser - a decorating function that stores the results of the wrapped function to prevent recalculations. You have only 50 characters.

Language - of course, JavaScript . The task itself is a classic, but the limit of 50 characters has turned into a real challenge.

In the breaks of the first day of the conference, we discussed options for achieving the goal, gradually reducing the answer. The whole excitement was crowned with the idea of ​​sharing the task with all the conference participants, and on the second day we visualized the task (see the Appendix) and began distributing forms to those who wanted it. As a result, we received about 40 solutions and once again became convinced of the uncommonness of the js-developers community, but Dmitry Kataev's record (53 SEMrush) remained in 53 characters. Let's figure it out!

Habitual implementation

function memoize(f) { let cache = {}; return function ret() { let key = JSON.stringify(arguments); if (!cache.hasOwnProperty(key)) { cache[key] = f.apply(this, arguments); } return cache[key]; } } 

Result: ~ 190 characters

• memoize - our memoiser
• f - decorated, wrapped function
• ret - the resulting function

To get the answer - the size of the function - use:

 memoize.toString().replace(/\s+/g, ' ').length 

When assessing the size of a function, we pay attention to its body and the list of parameters. If the function is anonymous, the ad is not counted.

Simple tests to test performance after abuse:

 const log = memoize(console.log); const inc = memoize(o => ox + 1); 

Further, the result of each implementation will be marked by the result of the tests.

Net implementation

First of all, I want to get rid of the Function Declaration in favor of the arrow function, since the context of this is not interesting to us, we don’t refer to arguments, and we don’t intend to call a new constructor. At the same time reduce the names of local variables used:

 const memoize = f => { let c = {}; return function() { let k = JSON.stringify(arguments); if (!c.hasOwnProperty(k)) { c[k] = f.apply(this, arguments); } return c[k]; } } 

Result: 154 , tests passed

Then you can perform a similar operation with the resulting function, but there we need arguments . This is where the spread operator comes to the rescue, allowing us to replace the transferred object of arguments with an array variable a . In addition, we will no longer pass this : context to the function being decorated; if necessary, then Function.prototype.bind or its own polyfil will help.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); if (!c.hasOwnProperty(k)) { c[k] = f(...a); } return c[k]; } } 

Result: 127 , tests passed

Now we turn to the body of the resulting function. Obviously, finding the key in the cache and returning the value is cumbersome. Let's try to reduce how:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c[k] || (c[k] = f(...a)); } } 

Result: 101 , dropped tests 3 and 4

Here we discard the hasOwnProperty method. We can afford it, since the result of serializing an array of arguments via JSON.stringify will always be "[...]" and it is unlikely that such a property will be in the prototype cache ( Object ).

Next, we use the "logical" operator OR feature to return the first expression if it can be converted to true , or otherwise the second one with the previous function evaluation.

And here tests 3 and 4 fell down. This happened because the decorated console.log function does not return a value: the result will be undefined . We put this in the cache, and when we try to check with the disjunctor feature when we call it again, we get implicitly deduced false in the first operand and, accordingly, we get into the second one, which leads to the function call. This effect will take place for all of the false results: 0, "", null, NaN , etc.

Instead of OR and if statement we can use the conditional ternary operator:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c.hasOwnProperty(k) ?c[k] :c[k] = f(...a); } } 

Result: 118 , tests passed

Cut very slightly. And what if instead of a simple object, Map is used as a storage? There is also a short hash method:

 const memoize = f => { let c = new Map; return (...a) => { let k = JSON.stringify(a); return (c.has(k) ?c :c.set(k, f(...a))).get(k); } } 

Result: 121 , tests passed

Cut down completely failed. But discarding the Map immediately is not worth it. This implementation of the key-value store allows you to use objects as a key. And this means, should we not abandon JSON.stringify at all?

 const memoize = f => { let c = new Map; return (...a) => (c.has(a) ?c :c.set(a, f(...a))).get(a); } 

Result: 83 , dropped tests 3 and 4

Looks very promising! However, tests 3 and 4 started falling again. This is because the comparison of keys in the Map object is implemented using the SameValueZero algorithm. If you omit the details with NaN, -0, and 0 , then it works just like strict comparison operator ( === ). And we have a new array of arguments (which means an object) for each call to the wrapped function, even with the same values. The comparison takes place according to the reference of the object and therefore the Map.prototype.has method will never find anything.

Thus, using the Map did not reduce us hasOwnProperty or JSON.stringify .

In operator comes to the rescue, which checks the presence of a property in an object or in a chain of its prototypes. Why we can not fear the search in the prototypes was explained above.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return k in c ?c[k] :c[k] = f(...a); } } 

Result: 105 , tests passed

The body of both the memoizer and the resulting function consists of two expressions, with the need to declare and initialize a local variable before the logic in the return statement . Is it possible here to reduce the body of the arrow function to one expression? Of course, using the IIFE pattern ( Immediately Invoked Function Expression ):

 const memoize = f => (c => (...a) => (k => k in c ?c[k] : c[k] = f(...a))(JSON.stringify(a)) )({}); 

Result: 82 , tests passed

It's time to get rid of extra spaces:

 f=>(c=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)))({}); 

Result: 68 , tests passed

Obviously, now the bottleneck is the long JSON.stringify method, which recursively serializes an object into a JSON string, which we use as a key. In fact, we need not a serialization function, but a hash function, with which we could check the equality of objects, as it works in other languages. But unfortunately there is no native solution in JavaScript, and the samopisny polyfil hashCode in the prototype of Object clearly goes beyond.

Hmm, why should we even serialize ourselves? When adding an element to an object by key, it will implicitly invoke toString. Since we refused to use the iterated arguments object in favor of the array via the spread operator , the toString call will not be from an Object.prototype , but from Array.prototype , in which it is redefined and its elements are comma-separated. Thus, for a different set of arguments, we get a different key.

 f=>(c=>(...a)=>a in c?c[a]:c[a]=f(...a))({}); 

Result: 44 , fell test 6

The test 6 is just beginning to fall. It seems that the return value is the result of the previous function call in test 5. Why is this happening? Yes, we bypassed the toString call for the arguments object, but we did not take into account that any argument can also be a complex object, calling toString from which we will get everyone's favorite [object Object] . This means that the arguments {x: 1} and {x: 2} will use the same key in the hash.

A good contender for the serialization feature seemed to be btoa , used to convert to base64. But he leads first to the string, so no chance. We thought in the direction of generating a URI, and forming an ArrayBuffer , of any functions for obtaining any hash or serialized value. But it remained in place.

By the way, JSON.stringify has its own features: Infinity, NaN, undefined, Symbol will be cast to null . The same goes for functions. If possible, an implicit call toJSON from the object occurs, and Map and Set will be represented simply by enumerated elements. This is understandable, given the final format: JSON.

What next?

Toxic refinement

We all certainly love pure functions, but under the conditions of the task such a requirement is not necessary. And that means it's time to add a pinch of side effects.

First, why not initiate the cache as follows:

 (f,c={})=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)); 

Result: 66 , tests passed

Here we use the default parameter in the arrow function. Of course, we give the customer the opportunity to set their cache, so what? But we have reduced 2 characters.

How else can you initiate a cache for the function being decorated? The correct answer is: why should we initiate it? Why not use something ready in the context of the wrapped function. And what if the function itself? We all know that functions in JavaScript are also objects:

 f=>(...a)=>(k=>k in f?f[k]:f[k]=f(...a))(JSON.stringify(a)); 

Result: 59 , tests passed

Here JSON.stringify will protect us from intersection with other properties and methods of an object (function) by wrapping the arguments in "[...]".

At this very moment, the previously applied IIFE pattern ceases to justify itself. But saving the only expression for the arrow function is urgently needed to avoid the return statement :

 f=>(...a)=>(k=JSON.stringify(a),k in f?f[k]:f[k]=f(...a)); 

Result: 57 , tests passed

Since we do not use the block statement in the switch function, we cannot declare a variable ( var or let ), but we can use the global context - side-effect! Here the conflict already has some chances to be.

With the help of the comma operator, we concatenate two expressions into one: the operands are calculated left-to-right, and the result is the value of the latter.

 f=>(...a)=>(k=JSON.stringify(a))in f?f[k]:f[k]=f(...a); 

Result: 54 , tests passed

So, using the permutation of only one bracket, we got rid of three characters at once. Grouping operator over the calculation of the key allowed us to combine both operands of the expression into a single expression, and the closing bracket removed the space before the in operator .

And finally:

 f=>(...a)=>f[k=JSON.stringify(a)]=k in f?f[k]:f(...a); 

Result: 53 , tests passed

Why not calculate the key at the time of access to the value. And then - all the same ternary operator and assignment. Total: 53 characters!

Is it possible to remove the remaining 3 characters?

Comprehension

Why all this? This simple task and the subsequent chain of conversions familiar to indecent demonstrates a considerable number of features of the JavaScript language. In our arguments we touched upon such things as:

• Arrow function expression
• Lexical scoping & IIFE
• Array-like arguments object
• Spread, comma, or operators
• Strict comparison operator
• JSON.stringify & toString
• In operator & hasOwnProperty
• Grouping operator & block statement
• Map object
• and something else

Similar to this story are a good reason to immerse yourself in learning the specifics of the language, help to better understand it (or vice versa). And of course just for fun!

application

In his adventures, Rick often has to calibrate his portal cannon. The procedure takes time, but the input data is often repeated. The scientist is trying to memorize the already obtained results in order not to make calculations again, but alcoholism and senility have a strong effect on his memory. He asked Morty to improve the cannon's tuning module by adding a memo-function. This function should save the results of the function being decorated to prevent re-evaluations. Only Morty is terribly afraid of long functions. Help him solve the problem as compactly as possible . As arguments, the function being decorated can take integers, strings, booleans, and objects.