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.

1 thought on “How equality and copy operations work”

Leave a Reply