How comparing things is faster and simpler with immutability

The third post of the series about the differences between values and references is focused on a practical example, the same trick that is at the core of React and Redux performance.

In the previous post of the series, I wrote about the nature of value and reference data types, and the differences between shallow and deep operations. In particular, the fact that we need to rely on deep operations to compare things is a major source of complexity in our codebases. But we can do better.

Comparing mutable structures

When working with mutable data structures, things like determining whether an object has been changed or not is not so simple:

var film = {
    'title': 'Piratees of the Caribean', 
    'released': 2003
};

// At some point, we receive an object and one of its properties
// might have changed. But how do we know?
newFilm = doSomething( film );

film === newFilm; // What does a shallow equality yield?

If we are allowed to mutate objects, although film and newFilm identifiers are equal, the payload might have been updated: a shallow equality check won’t suffice, we’ll need to perform a deep equality operation with the original object to know.

Comparing immutable structures

In JavaScript, primitives (numbers, strings, …) are immutable, and reference data types (object, arrays, …) are not. But if mutable structures are the reason why comparing things is difficult, what would happen if we worked with reference data types as if they were immutable?

Let’s see how this would work:

If something changes, instead of mutating the original object, we’ll create a new one with the adequate properties. As the new and the old object will have different identifiers, a shallow equality check will set them apart.

var film = {
    'title': 'Piratees of the Caribean', 
    'released': 2003
};

var doSomeThing = function( film ) { 
    // ... 
    return Object.assign( 
        {}, 
        film, 
        {'title': 'The curse of the Black Pearl'} 
    ); 
}

var newFilm = doSomething( film ); 

film === newFilm; // false

If nothing changes, we’ll return the same object. Because the identifier is the same, the shallow equality check will yield true.

var film = {
    'title': 'Piratees of the Caribean', 
    'released': 2003
};

var doSomeThing = function( film ) { 
    // ... 
    return film; 
} 

var newFilm = doSomething( film ); 

film === newFilm; // true

It is easier to tell what have changed when reference data types are immutable because we can leverage the shallow equality operations.

As a side-effect, it takes less effort to build a whole lot of systems that depend on calculating differences: undo/redo operations, memoization and cache invalidation, state machines, frameworks to build interfaces with the immediate mode paradigm, etc.

Coda

One of the reasons I started this series of posts was to explain how using immutable reference data types was one of the tricks at the core of Redux and React. Their success is teaching us a valuable lesson: immutability and pure functions are the core ideas of the current cycle of building applications – being the separation between API and interface the dominant idea of the previous cycle.

I have already mentioned this some time ago, but, at the time, I wasn’t fully aware of how quick these ideas will spread to other areas of the industry or how that will force us to gain a deeper understanding of language fundamentals.

I’m glad they did because I believe that investing in core concepts is what really matters to stay relevant and make smart decisions in the long term.

How equality and copy operations work

This is the second post of a series about how fundamental operations work depending on the nature of data they work with. JavaScript is used as example.

In the introductory post of this series we talked about the differences between value and reference data types:

  • Value data types store their payload as the contents of the variable.
  • Reference data types store an identifier as the contents of the variable, and that identifier is a reference to the actual payload in an external structure.

Through this post will see how the equality and copy operations use the content of the variable, meaning that they’ll use the payload for data types and the identifier for reference types.

Working with value data types

Let’s say we have the following value variables:

In plain JavaScript, this would be:

var foo = 42;
var bar = 42;
foo === bar; // this yields true

If we were copying variables instead:

var foo = 42;
var bar = foo;
foo === bar; // true

foo = 23;
foo === bar; // false

As the content of the variables is the mere payload, the operations are straightforward.

Working with reference data types

Let’s say now that we are working with reference data type variables:

In JavaScript, this would translate as:

var x = {'42': 'is the answer to the ultimate question'};
var y = {'42': 'is the answer to the ultimate question'};
x === y; // This yields false.

When we create new reference data type variables, they are going to have a brand new identifier, no matter whether the payload is actually the same than other existing variable. Because the language interpreter is comparing identifiers, and they are different, the equality check yields false.

What if we were copying variables instead:

var x = {'42': 'is the answer to the ultimate question'};
var y = x; // Copies x identifier to y.
x === y; // This yields true.

It is important to realize why these are equal: because their identifiers are equal, meaning that both variables are indexing the same payload.

With that in mind, what would happen on modifying the payload?

x['42'] = 'the meaning of life'; // Changes the payload.

x === y; // Still true, the identifiers haven't changed.
console.log(y['42']); // Yields 'the meaning of life'.

But:

var x = {'42': 'is the answer to the ultimate question'};
var y = x; // Copies x identifier
x === y; // We already know this is true.

x = {'42': 'the meaning of life'}; // New identifier and payload.

x === y; // This would yield false.
console.log(x['42']); // 'the meaning of life'
console.log(y['42']); // 'is the answer to the ultimate question'

The reason is that x = {'42': 'the meaning of life'} assigns a new identifier to x, that references a different payload – so we’ll be back to the first scenario shown in this block.

(A short aside: in the introduction, I mentioned that references and pointers were different. The above case is a good example of how they’re different: if y was a pointer, it would index the contents of x, so both variables would remain equals after x contents change.)

In computer science, the operations that work with the contents of the variable (be it values or reference identifiers) are called shallow operations, meaning that they don’t go the extra step to find and work with the actual payload. On the other hand, deep operations do the extra lookup and work with the actual payload. Languages usually have shallow/deep equality checks and shallow/deep copy operations.

JavaScript, in particular, doesn’t provide built-in mechanisms for deep equality checks or deep copy operations, these are things that either we build ourselves or use an external library.

An example with nested reference data types

A JavaScript idiom to create new objects by reusing parts of existing ones is using the method Object.assign(target, …sources):

var x = {'42': 'meaning of life'};
var y = Object.assign({}, x);
x === y; // Yields false, identifiers are different.
x[42] === y[42]; // Yields true, we are comparing values.

Object.assign creates a shallow copy of every own property in the source objects into the target object. If the target has the same prop, it’ll be overwritten. In the example above, we’re assigning a new identifier to the variable y, whose own properties will be the ones present in the object x.

This works as expected for objects whose own properties are value data structures, such as string or number. If any property is a reference data structure, we need to remember that we’ll be working with the identifiers.

For example:

var book = {
    'title': 'The dispossesed',
    'genre': 'Science fiction',
    'author': {
        'name': 'Ursula K. Le Guin',
        'born': '1929-10-29'
    }
};

// We are creating a newBook object:
// * the identifier would be new
// * the payload would be created by shallow copying 
//   every book's own property
var newBook = Object.assign({}, book);

newBook === book; // false, identifiers are different

// Compare value data types properties:
newBook['title'] === book['title']; // true
newBook['genre'] === book['genre']; // true

// Compare reference data types properties:
newBook['author'] === book['author']; // true

Both newBook and book objects have the same identifier for the property author, that references the same payload. Effectively, we have two different objects with some shared parts:

If we change some properties, but not the author identifier, both book and newBook will still see the same author payload:

book['title'] = 'Decisive moments in History';
book['genre'] = 'Historical fiction';
book['author']['name'] = 'Stefan Zweig';
book['author']['born'] = '1881-11-28';

newBook === book; // Yields false, identifiers are still different.

// Value variables have diverged.
newBook['title'] === book['title']; // false
newBook['genre'] === book['genre']; // false

// The author identifier hasn't changed, its payload did.
newBook['author'] === book['author']; // true 
newBook['author']['name'] === book['author']['name']; // true 
newBook['author']['born'] === book['author']['born']; // true

For both objects to be completely separate entities, we need to dereference the author identifier in some of them. For example:

book['title'] = 'Red Star';
book['genre'] = 'Science fiction';
book['author'] = { // this assigns a new identifier and payload
    'name': 'Alexander Bogdanov',
    'born': '1873-08-22'
};

newBook === book; // Yields false, identifiers are still different.

// Reference identifier for author changed,
// book.author and newBook.author are different objects now.
newBook['author'] === book['author']; // false

Coda

Humans have superpowers when it comes to pattern matching, so we are biased towards using that superpower whenever we can. That may be the reason why the reference abstraction is sometimes confusing and why the behavior of shallow operations might seem inconvenient. At the end, we just want to manipulate some payload, why would do be interested in working with identifiers?

The thing to remember is that programming is a space-time bound activity: we want to work with potentially big data structures in a quick way, and without running out of memory. Achieving that goal require trade-offs, and one that most languages do is having fixed memory structures (for the value data types and reference identifiers) and dynamic memory structures (for the reference payload). This is an oversimplification, but I believe it helps us to understand the role of these abstractions. Having fast equality checks is a side-effect of comparing fixed memory structures, and we can write more memory efficient programs because the copy operation works with identifiers instead of the actual payload.

Working with abstractions is both a burden and a bless, and we need to understand them and learn how to use them to write code that is simple. In the next post, we shall talk about one of the tricks that we have: immutable data structures.

Value and reference data types

The introductory post of a series about how fundamental operations behave depending on the nature of the data they work with. JavaScript will be used as an example.

There are a number of ways to classify data types in computer science. Of all of them, I find that the difference between value data types and reference data types is a useful classification for the daily life of application programmers – knowing the differences results in fewer bugs, less time to understand code, and more confidence to sleep well at night.

One way to think about them is by considering what is the content of the variable for each data type:

  • Value data types store their payload as the contents of the variable.
  • Reference data types store an identifier as the contents of the variable, and that identifier is a reference to the actual payload in an external structure.

Let’s say the FOO variable is a value data type and its payload is 42, while the BAR variable is a reference data type and has 42 as payload. A visual representation of this might look like:

We usually are interested in the payload of the variable (in green), not in their metadata (in red), yet fundamental operations of the languages we use every day have a different behavior depending on whether the variable content is a value or a reference.

For example, JavaScript has value and reference data types: the primitive data types are value data types – number, boolean, or string- and all the rest are reference data types – objects or arrays.

In terms of memory management, it is common for value data types and reference identifiers to be assigned a fixed amount of memory, and to live in a part of the memory called the stack. On the other hand, the reference payload usually doesn’t have a fixed amount of memory assigned so it can grow to any length, and tends to be stored in a different part of the memory sometimes called the heap. This is a generalization and an area that depends heavily on the language and its interpreters, but the reason this distinction exists in some manner is that we want fast and easy operations for an unlimited amount of data: operating with fixed memory variables is easier and faster, but dynamic memory allocation makes a better use of the limited space in memory – it’s a space/time tradeoff.

Boxing and unboxing

Languages with both value and reference data types, tend to provide ways to convert values into references, and vice-versa. This is called boxing and unboxing.

It is common that each value has a reference counterpart. For example, in JavaScript, there is the string primitive and the String object, the number primitive and the Number object, the boolean primitive and the Boolean object.

Also, languages tend to provide automatic boxing and unboxing in some situations. For example, JavaScript primitives don’t have methods or extra properties like the reference objects have; yet, they’ll be automatically boxed to the equivalent reference object when you’re trying to use one of its methods or properties.

This is a source of confusion, and the reason why:

var foo = 'meaning of life';
// Defines foo as a primitive string.
// To define it as the reference object String we'd do
// var foo = new String('meaning of life');

foo.toUpperCase();
// This yields 'MEANING OF LIFE'.
// Although foo is a primitive we can use the object methods
// thanks to the autoboxing.
// We could think of it as a type conversion in other languages: 
// ((String) foo).toUpperCase();

foo.constructor === String;
// This yields true.
// When we call a property or method belonging the object String,
// foo will automatically boxed, so it behaves like the object.

foo instanceof String; 
// This yields false.
// In this case foo is in its natural state (unboxed),
// so we are comparing the primitive to the reference.

typeof foo;
// This yields 'string'.
// In this case, foo is in its natural state (unboxed),
// so we are asking the system what kind of variable it is.

A note about references VS pointers

Some may argue that reference is how Object Oriented languages coined the old pointer data type. They are different things, though. The way I set them apart is by picturing what are the contents of the variables. References contain an identifier of the payload in an external structure; pointers index the content of another variable.

If, for example, a language would allow us to define a variable called Z as a pointer to X, visually it might look like this:

Although the difference between pointers and reference might be subtle, it has deep connotations when it comes to how operations work with them.

Coda

We, applications programmers, are mostly interested in the payload of the variables, but our programs consist of wrangling variables around with operations such as equality checks, copying, and passing arguments to other functions. These operations depend on the nature of the data they work with, so we are bound to deeply understand their inner workings. That will be the topic for the next post of the series.

CSS Grid, from Galifornia

One of the bigger milestones in Q1 2017 was the landing of the new CSS Grid standard in all major browsers.

Personally, the cool thing about this is that support for webkit and blink (namely, safari and chrome browser) was led and developed by IGALIA with a team of people (Manuel, Javier, and Sergio) from Galicia. I love seeing how Baiona or A Coruña can be attractive places for high-tech talent. We are Galifornia!

sum-csv

Reflections on a little thing I made, to learn how to better create the bigger ones.

After the last blog categories reorganization, I realized that I talk less about what I do and more about what others do. That make sense, as this blog is part of my learning process and I’m always looking around to find ways to improve myself. Yet, I’d like to start writing more about the little things I do. Writing helps me to reflect upon the how, so eventually I’ll learn more about my thought processes. These are likely to be very small things.

sum-csv

sum-csv is a small utility I have built to help me to crunch some statistics I was working with. I had a complete dataset in a CSV file, but what I wanted was an ordered list of the number of times something happened.

Original CSV: What I wanted:

A data transformation

This is a small task – my old self whispered. Yet, instead of opening the editor and start coding right away, the first thing I did was drawing things. I am a visual person and drawing helps me to gain understanding. The algorithm I came up with was a succession of mathematical transformations: Which is to say:

  • transpose the original matrix
  • eliminate the rows I was not interested in
  • for each row, group all numerical values (from column 1 onwards) by adding them, to calculate the total
  • sort the rows by the total

Now, I was prepared to write some code. Amusingly, the gist of it is almost pure English:

d3-array.transpose( matrix ).filter( isWhitelisted ).map( format ).sort( byCount );

Reflection

Creating production-ready code took me four times the effort of devising an initial solution: finding good and tested libraries for some of the operations not built-in in the language such as reading a CSV into a matrix or transpose the matrix itself, creating the tests for being able to sleep well at night, distributing the code in a way which is findable (GitHub/npm) and usable by others/my future self, and, actually, writing the code.

I am not always able to write code as a series of mathematical transformations, but I find pleasure when I do: it is much easier to conceptually proof whether the code is correct. I also like how the code embodied some of the ideas I’m more interested in lately, such as how a better vocabulary helps you to make things simpler.

A more expressive vocabulary for programming

map and friends are more precise, sophisticated ways to talk about consistent patterns in data manipulation. Using them over for is analogous to using the word “cake” instead of “the kind of food that you make by whipping egg whites and maybe adding sugar”.

Interestingly, you can eventually add new layers of category on top of established layers: just like saying that butter cakes constitute a specific family of cakes, one could say that pluck is a specialization of map.

Of vocabulary and contracts, Miguel Fonseca.

Simple made easy

Precise words make communication more efficient. Arguably, software development is about managing conceptual complexity. Simple made easy, by Rich Hickey is a talk that tackles those two topics.

Two takeaways from this talk:

  • The differences between simple and easy.
    • Simplicity is an objective measure, and its units are the level of interleaving (of concepts). Simplicity should not be measured by the cardinality, the number of concepts/units.
    • Easiness is a subjective measure, and it is related to how familiar you are with some topic or your past experience.
  • We can make things simple with the tools we already have by favoring concepts that make things simpler to reason about, not quicker to write. He recommends:

See also:

La La Land

Now, this is a musical that I like. Entertaining, moving, and complex.

I wouldn’t say musicals are my kind of films. My personal favorite is Sweeney Todd: The Demon Barber of Fleet Street, which is typical Burton. I didn’t like Les Misérables and haven’t watched Moulin Rouge. That’s my track record. Yet, this film is energizing, jazz everywhere, a colorful photography, with brilliant performances by Stone & Gosling.

At the core, I’d say this is a wonderful love story, with a positive and naïve message – just what we need right now. That’d be enough to recommend it. At the same time, it is not what would you expect from a Hollywood film: it is sad in many and fundamental ways, which makes the film a modern story about love, life, and personal growth. And has an epic soundtrack.

To the hackers that grew older

A rant about the needs to create software more community centric, instead on focusing too much on the individual.

The hacker ethic and the spirit of the information age, by Pekka Himanen, was one of these essays that had a big influence on my early yo. It resonated with how I felt about a lot of things: discovery & learning as a fundamental part of myself or work attached to meaning are two that I remember now. It was the first time I thought about how we divide life into chunks of time, more or less isolated.

One thing I didn’t realize at the time was who this essay was written for: a generation of individuals, with friends & family, but that see themselves as the unit of life in Earth. Given that the book defined the spirit that has driven one of the major social and cultural changes of the human race, this is no minor issue. As Jack Sparrow in the Pirates of the Caribbean, this generation had a mindset of fighting for their liberty against companies and governments. As individuals.

That attitude towards life, I believe, is one of the reasons why the products we create and consume are tailored for the individual and not for the communities: we have a personal music account, a personal pictures account, a personal mail account, etc. Solutions that take the group into account are rare and mostly exist for production-driven organizations (companies or volunteer based bodies), but less for leisure or consumption communities.

As we grew older and our communities became online, they asked us for help. So we create the “pay the service for user” feature as to pay for our relatives accounts, the family plans in our music and video stores, or the network setup for our publishing platform. These changes reflect a fundamental and more humane way to interact with others through technology. We are still in the early stages, but I expect this pattern to become stronger because one of the drivers for this to happen is that we have grown older in the same way that any other generation did in the past: realizing that we are weak as individuals, our natural state is to tribe within groups. Jack Sparrow struggled with this as well; he found out that the Black Pearl can be easily lost if you are on your own, and that you need a team if you want to navigate the ocean in freedom.

I, for one, look forward to a future more community-oriented. What specific shapes it will take is something that only we can invent; so let’s do it.