Etikettarkiv: JavaScript

Memoization

This blog post is also available on the Fortnox developer blog.

As developers we have a large selection of design patterns and techniques at our disposal when we design and implement our solutions. This is especially true in object oriented code; patterns such as decorators, builders and factory methods are just some of the patterns you probably see during your workday if you are coding with that paradigm.

Most of these design patterns have names that reveal their purpose. If we take the three patterns mentioned in the previous paragraph, the decorator pattern decorates an object with additional behaviour. The purpose of the builder and factory patterns are also reflected in their names; the builder pattern lets you construct an instance of a class using a fluent interface, while the factory method pattern is used to separate the construction of a complex object so that it resides in its own distinct method.

But then there are other techniques whose names do not convey their purpose as clearly. One example I would like to mention here is memoization, which is a concept I have stumbled upon several times during my days and figured that it must be something very mysterious. With a name like that it must be something really hard to understand, right?

Well not really. Memoization is basically an optimization technique in which a cache is used to store previous results of expensive computations. If the computation has occurred once, the following calls to the same routine will return the cached value instead of redoing all that work again.

In my attempt to understand how the technique works I decided to implement memoization in JavaScript, and this implementation can be seen below. The code defines a function called memoization, which closes over an initial numeric value. This value will then be used as the first operand for simple addition calculations. When you call memoization with a numeric value, that value will be used as the other operand and the result is returned. Previous results are cached according to the memoization technique.

let memoization = (val) => {
  let cache = {};

  return (other) => {
    if (!cache[other]) {
      // replace assignment below with your expensive computation
      cache[other] = val + other;
      console.log('Cached new value');
    }

    return cache[other];
  }
}

let plusFive = memoization(5);

// first call caches the result and outputs "Cached new value".
plusFive(10);

// second call reuses the cached result, i.e. no console output this time.
plusFive(10);

Now you’re probably thinking that a simple addition is not a very costly computation, and that’s true. The whole idea of this example was just to show how an implementation of the technique can look like. Apparently, the technique is useful for purposes other than optimization, but that is for you to dig into if you want to know more. :)

That’s all for now. Until next time!

Learning JavaScript properly

This blog post is also available on the Fortnox developer blog.

During the early 00s my programming was more or less about creating and maintaining web sites in LAMP setups. From that period I remember fighting many battles trying to make JavaScript code work across web browsers. It was not fun. For many years now I’ve kept my distance from the language, hoping for a better replacement to arrive at some point.

The thing is that JavaScript survived and is used extensively in all kinds of web setups, which is why I’ve decided to give the language another go. So I picked up JavaScript: The Good Parts (that have collected dust in a book shelf at home for several years) and saw this really nice presentation on functions in JavaScript recommended to me by a colleague at work. I read up on higher-order functions in the language and learned about some new stuff like arrow functions and constants (which are pretty cool). And then I decided to program something based on my understanding gained from all those resources.

My idea was to avoid the prototype stuff that I haven’t grasped fully yet and instead build something using functions and closures only. In the end I chose to build a simple snake game using JavaScript and React. Using React for a snake game is maybe overkill, but I found that the Create React App project gave me a nice bootstrapped environment for me to work in without the need to setup Babel, Webpack and all those other things you need to worry about. A few days in now there is a working version of the game that you can try here if you want. Just use the arrow keys or swipe to control the snake. Although the code is most probably far from idiomatic JavaScript, I decided to publish the code on GitHub, with the plan to ask some colleagues more experienced in the language to tell me what I’m doing wrong.

From this basic snake implementation I take with me a few insights. First, my time with the language was actually more pleasant than I had imagined. I believe that programming in Clojure and other functional programming languages have made me let go of the object-oriented paradigm a bit. This time around, when I decided to stick with using just functions and closures, the code felt more natural to write than when I tried to program like I do in Java.

Secondly, I miss working with persistent data structures and having robust ways to manage state changes. The ability to stay immutable takes away a lot of complexity not really related to the problem you want to solve and lets you instead focus on what’s important. You can get all this by simply using ClojureScript instead of JavaScript (as ClojureScript compiles to JavaScript) but I’ll save that subject for another post. 😉

A final and fun takeaway from this exercise is that the snake in a snake game can be modeled as a queue (along with a variable to control its growth when it feeds). Let’s have a look at how this works, starting with the algorithm to use each time the snake moves.

1. Push the next coordinate to the queue.
2a. If the grow variable is zero, then pop the first item from the queue.
2b. Else, decrease the grow variable by one.

Consider the following queue with x and y coordinates represented as tuples. JavaScript lacks both a tuple and a queue data type, so good old arrays will have to do.

let grow = 0;
const queue = [[1,1], [2,1], [3,1]];

So above we have a queue with three coordinates representing the snake. In this example, the snake is facing right, which means that the front of the snake is at [3,1] and the end of the snake is at [1,1]. Let’s move the snake one step to the right. According to the above algorithm, we push the next coordinate to the queue, which means that the queue now looks like this:

queue.push([4,1]);
// queue is now: [[1,1], [2,1], [3,1], [4,1]]

The grow variable is zero, so we pop off the first element like so::

queue.splice();
// queue is now: [[2,1], [3,1], [4,1]]

Alright, so now we have moved one step to the right! Let’s pretend that the snake found something to eat at [4,1], which means that the snake will grow. In the current version of the game, the snake grows by three whenever it eats, so we’ll increase the grow variable by three. Now, let’s move the snake to the right again. We first add [5,1] to the queue. This time, the grow variable is greater than zero, so we will not pop an item off the queue this time but rather reduce the grow variable by one. The outcome of the first movement we  just described is shown below.

queue.push([5,1]);
grow--;

// grow is now: 2
// queue is now: [[2,1], [3,1], [4,1], [5,1]]

As the snake keeps on moving the grow variable will eventually be reduced to zero. When that happens, we will start popping items off the queue again whenever the snake moves. I hope you found the snake discussion super interesting and life changing. 😉 That’s all for today, until next time!

Jag köpte mig en bok

”The best nature of JavaScript is so effectively hidden that for many years the prevailing opinion of JavaScript was that is was an unsightly, incompetent toy. [..] My intention here is to expose the goodness in JavaScript, an outstanding, dynamic programming language.”

Ovanstående citat kommer ur det inledande kapitlet av JavaScript: The Good Parts av Douglas Crockford, en bok jag köpte för att ta tag i det oundvikliga. År efter år har jag hållit mig på säkert avstånd, övertygad om att något vettigare alternativ förr eller senare måste dyka upp. Men det dök ju aldrig upp något alternativ och språket vann av någon outgrundlig anledning mer och mer mark för varje år. Det var väl dags att ta tag i det oundvikliga. Så jag köpte mig en bok.

När jag nu nästan har läst boken till ända ställer jag mig frågande till det citat jag inledde min lilla text med. Gång på gång har författaren förklarat hur man ska göra för att göra ”rätt”  – boken fokuserar ju just på ”the good parts” – och samtidigt belyst väldigt många konstigheter i språket som inte bör användas. Och det finns väldigt många.

Bara det där med att instansiera objekt rätt är knepigt. Det finns en för många av oss bekant operator vid namn new, men det är enligt författaren en bra strategi att hålla sig borta från den och välja andra tillvägagångssätt. Men om man nu ändå designar sin kod runt att använda sig av new gäller det att inte glömma bort att använda den; att glömma bort att använda new gör att this-referensen kommer att peka på något helt annat än det man tror, det globala objektet. Trots det kompilerar koden och kan köras utan minsta varning.

Sida efter sida målar boken upp bilden av ett språk som förlåter väldigt mycket och inte erbjuder mycket till struktur att luta sig emot. Ändå väljer författaren att kalla språket för ett ”outstanding, dynamic programming language”. Om jag förstår honom rätt syftar han med det citatet egentligen på en delmängd av språket, alltså det som ingår i ”the good parts”. Men kan man ens resonera så? Kan man sätta skygglappar på och låtsas att det som är dåligt inte existerar? Alla konstigheter som inte kvalar in bland ”the good parts” är ju likväl en del av språket?

Och hur fungerar det med språkets alla oskrivna regler i större projekt? Ska man inför projektstart enas om allt mellan himmel och jord för att få till en gemensam struktur att samarbeta kring? Typ ”använd inte detta, tänk på det här, instansiera inte så”. Och eftersom kompilatorn många gånger inte säger ifrån när man gör nåt knäppt tänker jag mig att mycket tid måste gå åt till Code Review för att upprätthålla den struktur man kommit överens om. Det känns som att man verkligen måste veta vad man gör och ha tungan rätt i mun för att koden ska bli förvaltningsbar.

Men vad vet jag, jag har ju aldrig egentligen lärt mig JavaScript ”på riktigt”. Vilken tur då att jag kan avsluta mitt resonemang med ett annat härligt citat från boken:

”The amazing thing about JavaScript is that it is possible to get work done with it without knowing much about the language [..]”