Code and decision trees

A lot of what programs do is transforming inputs into outputs. Take, for example, a piece of JavaScript code like this:

itemsToMarkup( items, viewType, galleryType ) {

    let markup;

    switch ( viewType ) {
        case 'gallery':
            if ( 'individual' === galleryType ) ) {
                markup = getHTML( items );
            } else {
                markup = getShortcode( items );
            }
            break;

        case 'image':
        default:
            markup = getHTML( items );
    }

    return markup;
}

What’s the purpose of this code? It takes some input data structures and outputs a markup, either proper HTML or a code to be processed by later stages of the pipeline. At the core, what we are doing is taking a decision based on the input’s state so it can be modeled as a decision tree:

tree-original

By restating the problem in a more simple language, the structure is made more evident. We are free of the biases that code as a language for thinking introduces (code size, good-looking indenting, a certain preference to use switch or if statements, etc). In this case, conflating the two checks into one reduces the tree depth and the number of leaves:

cof

Which back to code could be something like:

itemsToMarkup( items, viewType, galleryType ) {

    let markup;
    const isGalleryButNotIndividual = ( view, gallery ) => view === 'gallery' && gallery !== 'individual';

    if( isGalleryButNotIndividual( viewType, galleryType ) ) {
        markup = getShortcode( items );
    } else {
        markup = getHTML( items );
    }

    return markup;

}

By having a simpler decision tree, the second piece of code makes the input/output mapping more explicit and concise.

How comparing things is faster and simpler with immutability

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

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

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.

sum-csv

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.

Designing for growth

«Code should grow by addition rather than mutation.»

The best example of that axiom I ever found is the one in Beck’s Implementation patterns. What goes next is almost an exact reproduction of the book. After reading this post, if you liked, I’d strongly recommend you to buy a copy.

Imagine a graphic editor where one of the main metaphors is the Figure. It has methods like display(). So, if you want to support several figures in the editor, you can start by writing just a simple conditional:

public void display() {
    switch (getType()) {
        case RECTANGLE :
            //...
            break;
        case OVAL :
            //...
            break;
        case TEXT :
            //...
            break;
        default :
            break;
        }
}

This naïve example, shows early its cons: if you want to add a new kind of figure, you will need to modify the GraphicEditor class adding a new case statement in every switch you have written along the class. Not only it is tedious and error-prone, but it also requires modify a working functionality, putting it at risk. Besides, you should coordinate the changes with other developers using that class. At this point, likely you have thought on better ways to manage change: make the code growth by addition rather than mutation. How is that? Well, two of the tools you have available are inheritance (using classes) and delegation (using interfaces):

If you should choose one of another is a matter of context. It depends. For example, if you would want to rewrite the display method using delegation you would write:

public void display() {
    getType().display();
}

while let the rectangle and other figures to implement the logic of displaying themselves.

This change will allow us to add new kind of figures dinamically. We will only need to implement the Figure interface and use the mechanisms of GraphicEditor to select our new figure. No needs to change the existent code neither coordination costs or try to understand the whole picture before making any change. Just need to focus on implementing our tool. That’s the power of designing for growth: managing complexity.

How gvSIG MapControl works: flow of control

Within gvSIG design, MapControl is one of the core components. Its main responsibility is to allow users to interact with a map of layers (zoom in/out, edit geometries, …). That goal is achieved through two concrete tasks:

  • Route the user actions to the proper tool which will execute it.
  • Manage the drawing of the layers.

This post covers the first of above tasks in an introductory way.

Flow of control

MapControl is a java component, which uses the idea of Chain of Responsibility to delegate work on others. Let’s see how it works in this case with a good old graphic:


  1. MapControl listen MouseEvents through the MapToolListener. In response to an event, the MapToolListener will call the active tool (let’s say this class is named Behaviour).
  2. The active Behaviour processes the info from the mouse, put together the contextual information needed (let’s call that an Event) and calls the next step in the chain (let’s call it the ToolListener).
  3. Finally, the ToolListener will execute the actions needed to carry on the task an user have asked for.
Some notes before digging into code:
  • MapControl can have only 1 tool (Behaviour) active at any time. It holds the current selection in a private variable: Behaviour currentMapTool
  • MapControl wraps MouseEvents in 4 basic canonical events (see com.iver.cit.gvsig.fmap.tools.Events within libFMap project): MeasureEvent, PointEvent, MoveEvent and RectangleEvent. Any other event will inherit from and extend one of these canonical forms.

A concrete example: how a move event is processed

1 – MapToolListener: listen the mouse event and proxy it to the current selected behaviour (currentMapTool variable).

public void mouseReleased(MouseEvent e) {
    try {
        if (currentMapTool != null)
        currentMapTool.mouseReleased(e);
    } catch (BehaviorException t) {
        throwException(t);
    }
}

2 – Behaviour (MoveBehaviour in this case): takes the event, put together the context (MoveEvent) and redirects the petition to the proper ToolListener (listener variable).

public void mouseReleased(MouseEvent e) throws BehaviorException {
    if (e.getButton() == MouseEvent.BUTTON1 && m_FirstPoint!=null) {
        MoveEvent event = new MoveEvent(m_FirstPoint, e.getPoint(), e);
        listener.move(event);
    }
    m_FirstPoint = null;
}

3 – ToolListener: carry on the task. In this case, the listener (a PanListener) make the viewport to update the extent with the new contents.

public void move(MoveEvent event) {

    ViewPort vp = mapControl.getMapContext().getViewPort();
    Point2D from = vp.toMapPoint(event.getFrom());
    Point2D to = vp.toMapPoint(event.getTo());

    //build the new extent
    Rectangle2D.Double r = new Rectangle2D.Double();
    Rectangle2D extent = vp.getExtent();
    r.x = extent.getX() - (to.getX() - from.getX());
    r.y = extent.getY() - (to.getY() - from.getY());
    r.width = extent.getWidth();
    r.height = extent.getHeight();

    //update the ViewPort
    vp.setExtent(r);
}

Coda

Some useful resources about MapControl in gvSIG wiki:

Links to code:

How gvsig manages the snappers

Last week I paired together with Francisco Puga to review the status of opencadtools. As Fran is doing a great work in preparing the integration of opencadtools as default CAD tools in gvSIG, I wanted to know first hand how it was going. iCarto and Cartolab were kind enough to sponsor this pairing session. One of the results, apart from working with Fran -which is always motivating and enjoyable, per se-, was a deeper understanding on how snappers work in gvSIG, which is something I had asked myself sometimes. And, as one of the improvements of opencadtools is a followgeometry snapper, it seems a good goal to review that part of the project. Find below the summary:

CADToolAdapter class in extCAD extension maintains a list of snappers and layers to snap to from the editing layer. When the mouse is moved, the snappers are recalculated following this algorithm (note that the code below is the core of the method, some other parts/casts and boilerplate code is missing):

ArrayList snappers = SnapConfigPage.getActivesSnappers();
ILayerEdited layerInEdition =
    CADExtension.getEditionManager().getActiveLayerEdited();
ArrayList layersToSnap = layerInEdition.getLayersToSnap();

for (FLyrVect layer : layersToSnap) {

    // Getting the set of geometries within the envelope
    // The envelope is calculated based on the tolerance the user wants
    SpatialCache cache = layer.getSpatialCache();
    List geometries = cache.query(envelope);

    // Updating the nearest point
    for (Feature geomToSnap : geometries){
        for (int i=0; i distance){
                minimunDistance = distance;
        }
    }
}

This algorithm is executed every time the user move the mouse and is very quick if you have few layers to snap to. But, as the number of layer to check increases, the editing process becomes very slow. Besides, as a comment of software design, after reviewing this part of code, I like the way the snappers fit in gvsig cad tools. If you want to add a new snapper, just need to implement ISnapperVectorial interface and make getSnapToPoint method to return the nearest point to the position of the mouse. So, designing your own snappers is very easy!

By the way, if you feel like replying how other GIS applications (QGIS, uDig, …) manage the snappers, I’d be more than happy to hear and learn that!