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!