JAVASCRIPT CHAPTER 2 2018-12-19T12:45:59+00:00

JAVASCRIPT  Chapter 2

Topics:- (Data Set, Objects, Arrays,JSON,Abstraction, Higher-order Functions, Filtering arrays, Compostability, Strings and Character code, Encapsulation, Prototype, Classes, Maps, Polymorphism, Getter, Setter, Statics, Inheritance, Project: A Robot )

Data Structures: Objects and Arrays

Numbers, Booleans, and strings are the atoms that data structures are built from. Many types of information require more than one atom, though. Objects allow us to group values—including other objects—to build more complex structures. The programs we have built so far have been limited by the fact that they were operating only on simple data types. This chapter will introduce basic data structures. By the end of it, you’ll know enough to start writing useful programs. The chapter will work through a more or less realistic programming example, introducing concepts as they apply to the problem at hand. The example code will often build on functions and bindings that were introduced earlier in the text.

The weresquirrel

Every now and then, usually between 8 p.m. and 10 p.m., Jacques finds himself transforming into a small furry rodent with a bushy tail. On one hand, Jacques is quite glad that he doesn’t have classic lycanthropy. Turning into a squirrel does cause fewer problems than turning into a wolf. Instead of having to worry about accidentally eating the neighbor (that would be awkward), he worries about being eaten by the neighbor’s cat. After two occasions where he woke up on a precariously thin branch in the crown of an oak, naked and disoriented, he has taken to locking the doors and windows of his room at night and putting a few walnuts on the floor to keep himself busy.

That takes care of the cat and tree problems. But Jacques would prefer to get rid of his condition entirely. The irregular occurrences of the transformation make him suspect that they might be triggered by something. For a while, he believed that it happened only on days when he had been near oak trees. But avoiding oak trees did not stop the problem.

Switching to a more scientific approach, Jacques has started keeping a daily log of everything he does on a given day and whether he changed form. With this data he hopes to narrow down the conditions that trigger the transformations. The first thing he needs is a data structure to store this information.

Data sets

To work with a chunk of digital data, we’ll first have to find a way to represent it in our machine’s memory. Say, for example, that we want to represent a collection of the numbers 2, 3, 5, 7, and 11.

We could get creative with strings—after all, strings can have any length, so we can put a lot of data into them—and use “2 3 5 7 11” as our representation. But this is awkward. You’d have to somehow extract the digits and convert them back to numbers to access them. Fortunately, JavaScript provides a data type specifically for storing sequences of values. It is called an array and is written as a list of values between square brackets, separated by commas.

let listOfNumbers = [2, 3, 5, 7, 11]; console.log(listOfNumbers[2]);

// → 5

console.log(listOfNumbers[0]);

// → 2

console.log(listOfNumbers[2 – 1]);

// → 3

The notation for getting at the elements inside an array also uses square brackets. A pair of square brackets immediately after an expression, with another expression inside of them, will look up the element in the left-hand expression that corresponds to the index given by the expression in the brackets. The first index of an array is zero, not one. So the first element is retrieved with listOfNumbers[0]. Zero-based counting has a long tradition in technology and in certain ways makes a lot of sense, but it takes some getting used to. Think of the index as the amount of items to skip, counting from the start of the array.

Properties

We’ve seen a few suspicious-looking expressions like myString.length (to get the length of a string) and Math.max (the maximum function) in past chapter. These are expressions that access a property of some value. In the first case, we access the length property of the value in myString. In the second, we access the property named max in the Math object (which is a collection of mathematics-related constants and functions). Almost all JavaScript values have properties. The exceptions are null and undefined. If you try to access a property on one of these nonvalues, you get an error.

null.length;

// → TypeError: null has no properties

The two main ways to access properties in JavaScript are with a dot and with square brackets. Both value.x and value[x] access a property on value—but not necessarily the same property. The difference is in how x is interpreted. When using a dot, the word after the dot is the literal name of the property. When using square brackets, the expression between the brackets is evaluated to get the property name. Whereas value.x fetches the property of value named “x”, value[x] tries to evaluate the expression x and uses the result, converted to a string, as the property name.

So if you know that the property you are interested in is called color, you say value.color. If you want to extract the property named by the value held in the binding i, you say value[i]. Property names are strings. They can be any string, but the dot notation works only with names that look like valid binding names. So if you want to access a property named 2 or John Doe, you must use square brackets: value[2] or value[“John Doe”].

The elements in an array are stored as the array’s properties, using numbers as property names. Because you can’t use the dot notation with numbers and usually want to use a binding that holds the index anyway, you have to use the bracket notation to get at them. The length property of an array tells us how many elements it has. This property name is a valid binding name, and we know its name in advance, so to find the length of an array, you typically write array.length because that’s easier to write than array[“length”].

Methods

Both string and array objects contain, in addition to the length property, a number of properties that hold function values.

let doh = “Doh”;

console.log(typeof doh.toUpperCase);

// → function

console.log(doh.toUpperCase());

// → DOH

Every string has a toUpperCase property. When called, it will return a copy of the string in which all letters have been converted to uppercase. There is also toLowerCase, going the other way. Interestingly, even though the call to toUpperCase does not pass any arguments, the function somehow has access to the string “Doh”, the value whose property we called.  Properties that contain functions are generally called methods of the value they belong to, as in “toUpperCase is a method of a string”. This example demonstrates two methods you can use to manipulate arrays:

let sequence = [1, 2, 3];

sequence.push(4);

sequence.push(5);

console.log(sequence);

// → [1, 2, 3, 4, 5]

console.log(sequence.pop());

// → 5

console.log(sequence);

// → [1, 2, 3, 4]

The push method adds values to the end of an array, and the pop method does the opposite, removing the last value in the array and returning it. These somewhat silly names are the traditional terms for operations on a stack. A stack, in programming, is a data structure that allows you to push values into it and pop them out again in the opposite order so that the thing that was added last is removed first. These are common in programming—you might remember the function call stack , which is an instance of the same idea.

Objects

Back to the weresquirrel. A set of daily log entries can be represented as an array. But the entries do not consist of just a number or a string—each entry needs to store a list of activities and a Boolean value that indicates whether Jacques turned into a squirrel or not. Ideally, we would like to group these together into a single value and then put those grouped values into an array of log entries. Values of the type object are arbitrary collections of properties. One way to create an object is by using braces as an expression.

let day1 = {

squirrel: false,

events: [“work”, “touched tree”, “pizza”, “running”]

};

console.log(day1.squirrel);

// → false

console.log(day1.wolf);

//→ undefined

day1.wolf = false;

console.log(day1.wolf);

// → false

Inside the braces, there is a list of properties separated by commas. Each property has a name followed by a colon and a value. When an object is written over multiple lines, indenting it like in the example helps with readability. Properties whose names aren’t valid binding names or valid numbers have to be quoted.

let descriptions = {

work: “Went to work”,

“touched tree”: “Touched a tree”

};

This means that braces have two meanings in JavaScript. At the start of a statement, they start a block of statements. In any other position, they describe an object. Fortunately, it is rarely useful to start a statement with an object in braces, so the ambiguity between these two is not much of a problem. Reading a property that doesn’t exist will give you the value undefinedIt is possible to assign a value to a property expression with the = operator. This will replace the property’s value if it already existed or create a new property on the object if it didn’t.

To briefly return to our tentacle model of bindings—property bindings are similar. They grasp values, but other bindings and properties might be holding onto those same values. You may think of objects as octopuses with any number of tentacles, each of which has a name tattooed on it. The delete operator cuts off a tentacle from such an octopus. It is a unary operator that, when applied to an object property, will remove the named property from the object. This is not a common thing to do, but it is possible.

let anObject = {left: 1, right: 2};

console.log(anObject.left);

// → 1

delete anObject.left;

console.log(anObject.left);

// → undefined

console.log(“left” in anObject);

// → false

console.log(“right” in anObject);

// → true

The binary in operator, when applied to a string and an object, tells you whether that object has a property with that name. The difference between setting a property to undefined and actually deleting it is that, in the first case, the object still has the property (it just doesn’t have a very interesting value), whereas in the second case the property is no longer present and in will return falseTo find out what properties an object has, you can use the Object.keys function. You give it an object, and it returns an array of strings—the object’s property names.

console.log(Object.keys({x: 0, y: 0, z: 2}));

// → [“x”, “y”, “z”]

There’s an Object.assign function that copies all properties from one object into another.

let objectA = {a: 1, b: 2};

Object.assign(objectA, {b: 3, c: 4});

console.log(objectA);

// → {a: 1, b: 3, c: 4}

Arrays, then, are just a kind of object specialized for storing sequences of things. If you evaluate typeof [], it produces “object”. You can see them as long, flat octopuses with all their tentacles in a neat row, labeled with numbers.We will represent the journal that Jacques keeps as an array of objects.

let journal = [

{events: [“work”, “touched tree”, “pizza”, “running”, “television”],

squirrel: false},

{events: [“work”, “ice cream”, “cauliflower”, “lasagna”, “touched tree”, “brushed teeth”],

squirrel: false},

{events: [“weekend”, “cycling”, “break”, “peanuts”, “beer”],

squirrel: true},

/* and so on… */

];

Mutability

We will get to actual programming real soon now. First there’s one more piece of theory to understand. We saw that object values can be modified. The types of values discussed in earlier, such as numbers, strings, and Booleans, are all immutable—it is impossible to change values of those types. You can combine them and derive new values from them, but when you take a specific string value, that value will always remain the same. The text inside it cannot be changed. If you have a string that contains “cat”, it is not possible for other code to change a character in your string to make it spell “rat”.

Objects work differently. You can change their properties, causing a single object value to have different content at different times.When we have two numbers, 120 and 120, we can consider them precisely the same number, whether or not they refer to the same physical bits. With objects, there is a difference between having two references to the same object and having two different objects that contain the same properties. Consider the following code:

let object1 = {value: 10};

let object2 = object1;

let object3 = {value: 10};

console.log(object1 == object2);

// → true

console.log(object1 == object3);

// → false

object1.value = 15;

console.log(object2.value);

// → 15

console.log(object3.value);

// → 10

The object1 and object2 bindings grasp the same object, which is why changing object1 also changes the value of object2. They are said to have the same identity. The binding object3 points to a different object, which initially contains the same properties as object1 but lives a separate life. Bindings can also be changeable or constant, but this is separate from the way their values behave. Even though number values don’t change, you can use a let binding to keep track of a changing number by changing the value the binding points at. Similarly, though a const binding to an object can itself not be changed and will continue to point at the same object, the contents of that object might change.

const score = {visitors: 0, home: 0};

// This is okay

score.visitors = 1;

// This isn’t allowed

score = {visitors: 1, home: 1};

When you compare objects with JavaScript’s == operator, it compares by identity: it will produce true only if both objects are precisely the same value. Comparing different objects will return false, even if they have identical properties. There is no “deep” comparison operation built into JavaScript, which compares objects by contents, but it is possible to write it yourself 

The lycanthrope’s log

So, Jacques starts up his JavaScript interpreter and sets up the environment he needs to keep his journal.

let journal = [];

function addEntry(events, squirrel) {

journal.push({events, squirrel});

}

Note that the object added to the journal looks a little odd. Instead of declaring properties like events: events, it just gives a property name. This is shorthand that means the same thing—if a property name in brace notation isn’t followed by a value, its value is taken from the binding with the same name. So then, every evening at 10 p.m.—or sometimes the next morning, after climbing down from the top shelf of his bookcase—Jacques records the day.

addEntry([“work”, “touched tree”, “pizza”, “running”, “television”], false);

addEntry([“work”, “ice cream”, “cauliflower”, “lasagna”, “touched tree”, “brushed teeth”], false);

addEntry([“weekend”, “cycling”, “break”, “peanuts”, “beer”], true);

Once he has enough data points, he intends to use statistics to find out which of these events may be related to the squirrelifications.

Correlation is a measure of dependence between statistical variables. A statistical variable is not quite the same as a programming variable. In statistics you typically have a set of measurements, and each variable is measured for every measurement. Correlation between variables is usually expressed as a value that ranges from -1 to 1. Zero correlation means the variables are not related. A correlation of one indicates that the two are perfectly related—if you know one, you also know the other. Negative one also means that the variables are perfectly related but that they are opposites—when one is true, the other is false.

To compute the measure of correlation between two Boolean variables, we can use the phi coefficient (φ). This is a formula whose input is a frequency table containing the number of times the different combinations of the variables were observed. The output of the formula is a number between -1 and 1 that describes the correlation. We could take the event of eating pizza and put that in a frequency table like this, where each number indicates the amount of times that combination occurred in our measurements:

If we call that table n, we can compute φ using the following formula:

 (2.1)

(We do not intend to torture you with endless pages of cryptic notation—it’s just this one formula for now. And even with this one, all we do is turn it into JavaScript.) The notation n01 indicates the number of measurements where the first variable (squirrelness) is false (0) and the second variable (pizza) is true (1). In the pizza table, n01 is 9. The value n1• refers to the sum of all measurements where the first variable is true, which is 5 in the example table. Likewise, n •0 refers to the sum of the measurements where the second variable is false.

So for the pizza table, the part above the division line (the dividend) would be 1×76−4×9 = 40, and the part below it (the divisor) would be the square root of 5×85×10×80, or  340000. This comes out to φ ≈ 0.069, which is tiny. Eating pizza does not appear to have influence on the transformations.

Computing correlation

We can represent a two-by-two table in JavaScript with a four-element array ([76, 9, 4, 1]). We could also use other representations, such as an array containing two two-element arrays ([[76, 9], [4, 1]]) or an object with property names like “11” and “01”, but the flat array is simple and makes the expressions that access the table pleasantly short. We’ll interpret the indices to the array as two-bit binary numbers, where the leftmost (most significant) digit refers to the squirrel variable and the rightmost (least significant) digit refers to the event variable. For example, the binary number 10 refers to the case where Jacques did turn into a squirrel, but the event (say, “pizza”) didn’t occur. This happened four times. And since binary 10 is 2 in decimal notation, we will store this number at index 2 of the array.

This is the function that computes the φ coefficient from such an array:

function phi(table) {

return (table[3] * table[0] – table[2] * table[1]) /
Math.sqrt((table[2] + table[3]) *
(table[0] + table[1]) *
(table[1] + table[3]) *
(table[0] + table[2]));}

console.log(phi([76, 9, 4, 1]));

// → 0.068599434

This is a direct translation of the φ formula into JavaScript. Math.sqrt is the square root function, as provided by the Math object in a standard JavaScript environment. We have to add two fields from the table to get fields like n1• because the sums of rows or columns are not stored directly in our data structure.Jacques kept his journal for three months. To extract a two-by-two table for a specific event from the journal, we must loop over all the entries and tally how many times the event occurs in relation to squirrel transformations.

function tableFor(event, journal) {

let table = [0, 0, 0, 0];

for (let i = 0; i < journal.length; i++) {

let entry = journal[i], index = 0;

if (entry.events.includes(event)) index += 1;

if (entry.squirrel) index += 2;

table[index] += 1;

}

return table;

}

console.log(tableFor(“pizza”, JOURNAL));

// → [76, 9, 4, 1]

Arrays have an includes method that checks whether a given value exists in the array. The function uses that to determine whether the event name it is interested in is part of the event list for a given day. The body of the loop in tableFor figures out which box in the table each journal entry falls into by checking whether the entry contains the specific event it’s interested in and whether the event happens alongside a squirrel incident. The loop then adds one to the correct box in the table. We now have the tools we need to compute individual correlations. The only step remaining is to find a correlation for every type of event that was recorded and see whether anything stands out.

Array loops

In the tableFor function, there’s a loop like this:

for (let i = 0; i < JOURNAL.length; i++) {

let entry = JOURNAL[i];

// Do something with entry

}

This kind of loop is common in classical JavaScript—going over arrays one element at a time is something that comes up a lot, and to do that you’d run a counter over the length of the array and pick out each element in turn.There is a simpler way to write such loops in modern JavaScript.

for (let entry of JOURNAL) {

console.log(`${entry.events.length} events.`);

}

When a for loop looks like this, with the word of after a variable definition, it will loop over the elements of the value given after of. This works not only for arrays but also for strings and some other data structures. 

The final analysis

We need to compute a correlation for every type of event that occurs in the data set. To do that, we first need to find every type of event.

function journalEvents(journal) {

let events = [];

for (let entry of journal) {

     for (let event of entry.events) {

           if (!events.includes(event)) {

                     events.push(event);

              }

       }

}

return events;

}

console.log(journalEvents(JOURNAL));

// → [“carrot”, “exercise”, “weekend”, “bread”, …]

By going over all the events and adding those that aren’t already in there to the events array, the function collects every type of event. Using that, we can see all the correlations.

for (let event of journalEvents(JOURNAL)) {

console.log(event + “:”, phi(tableFor(event, JOURNAL)));

}

// → carrot:   0.0140970969

// → exercise: 0.0685994341

// → weekend:  0.1371988681

// → bread:   -0.0757554019

// → pudding: -0.0648203724

// and so on…

Most correlations seem to lie close to zero. Eating carrots, bread, or pudding apparently does not trigger squirrel-lycanthropy. It does seem to occur some-what more often on weekends. Let’s filter the results to show only correlations greater than 0.1 or less than -0.1.

for (let event of journalEvents(JOURNAL)) {
let correlation = phi(tableFor(event, JOURNAL));
if (correlation > 0.1 || correlation < -0.1) {console.log(event + “:”, correlation); }

}
// → weekend:            0.1371988681

// → brushed teeth: -0.3805211953

// → candy:                 0.1296407447

// → work:                 -0.1371988681

// → spaghetti:           0.2425356250

// → reading:              0.1106828054

// → peanuts:             0.5902679812

Aha! There are two factors with a correlation that’s clearly stronger than the others. Eating peanuts has a strong positive effect on the chance of turning into a squirrel, whereas brushing his teeth has a significant negative effect. Interesting. Let’s try something.

for (let entry of JOURNAL) {

if (entry.events.includes(“peanuts”) &&

!entry.events.includes(“brushed teeth”)) {

entry.events.push(“peanut teeth”);

   }

}

console.log(phi(tableFor(“peanut teeth”, JOURNAL)));

// → 1

That’s a strong result. The phenomenon occurs precisely when Jacques eats peanuts and fails to brush his teeth. If only he weren’t such a slob about dental hygiene, he’d have never even noticed his affliction. Knowing this, Jacques stops eating peanuts altogether and finds that his transformations don’t come back.

For a few years, things go great for Jacques. But at some point he loses his job. Because he lives in a nasty country where having no job means having no medical services, he is forced to take employment with a circus where he performs as The Incredible Squirrelman, stuffing his mouth with peanut butter before every show. One day, fed up with this pitiful existence, Jacques fails to change back into his human form, hops through a crack in the circus tent, and vanishes into the forest. He is never seen again.

Further arrayology

Before finishing the chapter, we want to introduce you to a few more object-related concepts. We’ll start by introducing some generally useful array methods. We saw push and pop, which add and remove elements at the end of an array. The corresponding methods for adding and removing things at the start of an array are called unshift and shift.

let todoList = [];

function remember(task) {

todoList.push(task);

}

function getTask() {

return todoList.shift();

}

function rememberUrgently(task) {

todoList.unshift(task);

}

That program manages a queue of tasks. You add tasks to the end of the queue by calling remember(“groceries”), and when you’re ready to do something, you call getTask() to get (and remove) the front item from the queue. The rememberUrgently function also adds a task but adds it to the front instead of the back of the queue. To search for a specific value, arrays provide an indexOf method. The method searches through the array from the start to the end and returns the index at which the requested value was found—or -1 if it wasn’t found. To search from the end instead of the start, there’s a similar method called lastIndexOf.

console.log([1, 2, 3, 2, 1].indexOf(2));

// → 1

console.log([1, 2, 3, 2, 1].lastIndexOf(2));

// → 3

Both indexOf and lastIndexOf take an optional second argument that indicates where to start searching. Another fundamental array method is slice, which takes start and end indices and returns an array that has only the elements between them. The start index is inclusive, the end index exclusive.

console.log([0, 1, 2, 3, 4].slice(2, 4)); // → [2, 3]

console.log([0, 1, 2, 3, 4].slice(2)); // → [2, 3, 4]

When the end index is not given, slice will take all of the elements after the start index. You can also omit the start index to copy the entire array. The concat method can be used to glue arrays together to create a new array, similar to what the + operator does for strings. The following example shows both concat and slice in action. It takes an array and an index, and it returns a new array that is a copy of the original array with the element at the given index removed.

function remove(array, index) {

return array.slice(0, index)

.concat(array.slice(index + 1));

}

console.log(remove([“a”, “b”, “c”, “d”, “e”], 2));

// → [“a”, “b”, “d”, “e”]

If you pass concat an argument that is not an array, that value will be added to the new array as if it were a one-element array.

Strings and their properties

We can read properties like length and toUpperCase from string values. But if you try to add a new property, it doesn’t stick.

let kim = “Kim”;

kim.age = 88;

console.log(kim.age);

// → undefined

Values of type string, number, and Boolean are not objects, and though the language doesn’t complain if you try to set new properties on them, it doesn’t actually store those properties. As mentioned earlier, such values are immutable and cannot be changed. But these types do have built in properties. Every string value has a number of methods. Some very useful ones are slice and indexOf, which resemble the array methods of the same name.

console.log(“coconuts”.slice(4, 7));

// → nut

console.log(“coconut”.indexOf(“u”));

// → 5

One difference is that a string’s indexOf can search for a string containing more than one character, whereas the corresponding array method looks only for a single element.

console.log(“one two three”.indexOf(“ee”));

// → 11

The trim method removes whitespace (spaces, newlines, tabs, and similar characters) from the start and end of a string.

console.log(” okay \n “.trim());

// → okay

The zeroPad function  also exists as a method. It is called padStart and takes the desired length and padding character as arguments.

console.log(String(6).padStart(3, “0”));

// → 006

You can split a string on every occurrence of another string with split and join it again with join.

let sentence = “Secretarybirds specialize in stomping”;

let words = sentence.split(” “);

console.log(words);

// → [“Secretarybirds”, “specialize”, “in”, “stomping”]

console.log(words.join(“. “));

// → Secretarybirds. specialize. in. stomping

A string can be repeated with the repeat method, which creates a new string containing multiple copies of the original string, glued together.

console.log(“LA”.repeat(3));

// → LALALA

We have already seen the string type’s length property. Accessing the individual characters in a string looks like accessing array elements.

let string = “abc”;

console.log(string.length);

// → 3

console.log(string[1]);

// → b

Rest parameters

It can be useful for a function to accept any number of arguments. For example, Math.max computes the maximum of all the arguments it is given. To write such a function, you put three dots before the function’s last parameter, like this:

function max(…numbers) {

let result = -Infinity;

for (let number of numbers) {

if (number > result) result = number;

}

return result;

}

console.log(max(4, 1, 9, -2));

// → 9

When such a function is called, the rest parameter is bound to an array containing all further arguments. If there are other parameters before it, their values aren’t part of that array. When, as in max, it is the only parameter, it will hold all arguments. You can use a similar three-dot notation to call a function with an array of arguments.

let numbers = [5, 1, 7];

console.log(max(…numbers));

// → 7

This “spreads” out the array into the function call, passing its elements as separate arguments. It is possible to include an array like that along with other arguments, as in max(9, …numbers, 2)Square bracket array notation similarly allows the triple-dot operator to spread another array into the new array.

let words = [“never”, “fully”];

console.log([“will”, …words, “understand”]);

// → [“will”, “never”, “fully”, “understand”]

The Math object

As we’ve seen, Math is a grab bag of number-related utility functions, such as Math.max (maximum), Math.min (minimum), and Math.sqrt (square root). The Math object is used as a container to group a bunch of related functionality. There is only one Math object, and it is almost never useful as a value. Rather, it provides a namespace so that all these functions and values do not have to be global bindings. Having too many global bindings “pollutes” the namespace. The more names have been taken, the more likely you are to accidentally overwrite the value of some existing binding. For example, it’s not unlikely to want to name some-thing max in one of your programs. Since JavaScript’s built-in max function is tucked safely inside the Math object, we don’t have to worry about overwriting it.

Many languages will stop you, or at least warn you, when you are defining a binding with a name that is already taken. JavaScript does this for bindings you declared with let or const but—perversely—not for standard bindings nor for bindings declared with var or functionBack to the Math object. If you need to do trigonometry, Math can help. It contains cos (cosine), sin (sine), and tan (tangent), as well as their inverse functions, acos, asin, and atan, respectively. The number (pi)—or at least the closest approximation that fits in a JavaScript number—is available as Math.PI. There is an old programming tradition of writing the names of constant values in all caps.

function randomPointOnCircle(radius) {

let angle = Math.random() * 2 * Math.PI;

return {x: radius * Math.cos(angle),

y: radius * Math.sin(angle)};

}

console.log(randomPointOnCircle(2));

// → {x: 0.3667, y: 1.966}

If sines and cosines are not something you are familiar with, don’t worry. The previous example used Math.random. This is a function that returns a new pseudorandom number between zero (inclusive) and one (exclusive) every time you call it.

console.log(Math.random());

// → 0.36993729369714856

console.log(Math.random());

//→ 0.727367032552138

console.log(Math.random());

// → 0.40180766698904335

Though computers are deterministic machines—they always react the same way if given the same input—it is possible to have them produce numbers that appear random. To do that, the machine keeps some hidden value, and whenever you ask for a new random number, it performs complicated computations on this hidden value to create a new value. It stores a new value and returns some number derived from it. That way, it can produce ever new, hard-to-predict numbers in a way that seems random. If we want a whole random number instead of a fractional one, we can use Math.floor (which rounds down to the nearest whole number) on the result of Math.random.

console.log(Math.floor(Math.random() * 10));

// → 2

Multiplying the random number by 10 gives us a number greater than or equal to 0 and below 10. Since Math.floor rounds down, this expression will produce, with equal chance, any number from 0 through 9.There are also the functions Math.ceil (for “ceiling”, which rounds up to a whole number), Math.round (to the nearest whole number), and Math.abs, which takes the absolute value of a number, meaning it negates negative values but leaves positive ones as they are.

Destructuring

Let’s go back to the phi function for a moment.

function phi(table) {

return (table[3] * table[0] – table[2] * table[1]) /

Math.sqrt((table[2] + table[3]) *

   (table[0] + table[1]) *

   (table[1] + table[3]) *

    (table[0] + table[2]));

}

One of the reasons this function is awkward to read is that we have a binding pointing at our array, but we’d much prefer to have bindings for the elements of the array, that is, let n00 = table[0] and so on. Fortunately, there is a succinct way to do this in JavaScript.

function phi([n00, n01, n10, n11]) {

  return (n11 * n00 – n10 * n01) /

   Math.sqrt((n10 + n11) * (n00 + n01) *

                         (n01 + n11) * (n00 + n10));

}

This also works for bindings created with let, var, or const. If you know the value you are binding is an array, you can use square brackets to “look inside” of the value, binding its contents. A similar trick works for objects, using braces instead of square brackets.

let {name} = {name: “Faraji”, age: 23};

console.log(name);

// → Faraji

Note that if you try to destructure null or undefined, you get an error, much as you would if you directly try to access a property of those values.

JSON

Because properties only grasp their value, rather than contain it, objects and arrays are stored in the computer’s memory as sequences of bits holding the addresses—the place in memory—of their contents. So an array with another array inside of it consists of (at least) one memory region for the inner array, and another for the outer array, containing (among other things) a binary number that represents the position of the inner array.

If you want to save data in a file for later or send it to another computer over the network, you have to somehow convert these tangles of memory addresses to a description that can be stored or sent. You could send over your entire computer memory along with the address of the value you’re interested in, I suppose, but that doesn’t seem like the best approach. What we can do is serialize the data. That means it is converted into a flat description. A popular serialization format is called JSON (pronounced “Jason”), which stands for JavaScript Object Notation. It is widely used as a data storage and communication format on the Web, even in languages other than JavaScript.

JSON looks similar to JavaScript’s way of writing arrays and objects, with a few restrictions. All property names have to be surrounded by double quotes, and only simple data expressions are allowed—no function calls, bindings, or anything that involves actual computation. Comments are not allowed in JSON. A journal entry might look like this when represented as JSON data:

{

“squirrel”: false,

“events”: [“work”, “touched tree”, “pizza”, “running”]

}

JavaScript gives us the functions JSON.stringify and JSON.parse to convert data to and from this format. The first takes a JavaScript value and returns a JSON-encoded string. The second takes such a string and converts it to the value it encodes.

let string = JSON.stringify({squirrel: false,

events: [“weekend”]});

console.log(string);

// → {“squirrel”:false,”events”:[“weekend”]} console.log(JSON.parse(string).events);

// → [“weekend”]

Higher-Order Functions

A large program is a costly program, and not just because of the time it takes to build. Size almost always involves complexity, and complexity confuses programmers. Confused programmers, in turn, introduce mistakes (bugs) into programs. A large program then provides a lot of space for these bugs to hide, making them hard to find. Let’s briefly go back to the final two example programs in the introduction.The first is self-contained and six lines long.

let total = 0, count = 1;

while (count <= 10) {

total += count;

count += 1;

}

console.log(total);

The second relies on two external functions and is one line long.

console.log(sum(range(1, 10)));

Which one is more likely to contain a bug? If we count the size of the definitions of sum and range, the second program is also big—even bigger than the first. But still, we’d argue that it is more likely to be correct. It is more likely to be correct because the solution is expressed in a vocabulary that corresponds to the problem being solved. Summing a range of numbers isn’t about loops and counters. It is about ranges and sums. The definitions of this vocabulary (the functions sum and range) will still involve loops, counters, and other incidental details. But because they are expressing simpler concepts than the program as a whole, they are easier to get right.

Abstraction

In the context of programming, these kinds of vocabularies are usually called abstractions. Abstractions hide details and give us the ability to talk about problems at a higher (or more abstract) level. As an analogy, compare these two recipes for pea soup. The first one goes like this:

Put 1 cup of dried peas per person into a container. Add water until the peas are well covered. Leave the peas in water for at least 12 hours. Take the peas out of the water and put them in a cooking pan. Add 4 cups of water per person. Cover the pan and keep the peas simmering for two hours. Take half an onion per person. Cut it into pieces with a knife. Add it to the peas. Take a stalk of celery per person. Cut it into pieces with a knife. Add it to the peas. Take a carrot per person. Cut it into pieces. With a knife! Add it to the peas. Cook for 10 more minutes.

And this is the second recipe:

Per person: 1 cup dried split peas, half a chopped onion, a stalk of celery, and a carrot.

Soak peas for 12 hours. Simmer for 2 hours in 4 cups of water (per person). Chop and add vegetables. Cook for 10 more minutes.

The second is shorter and easier to interpret. But you do need to understand a few more cooking-related words such as soak, simmer, chop, and vegetableWhen programming, we can’t rely on all the words we need to be waiting for us in the dictionary. Thus, we might fall into the pattern of the first recipe— work out the precise steps the computer has to perform, one by one, blind to the higher-level concepts that they express. It is a useful skill, in programming, to notice when you are working at too low a level of abstraction.

Abstracting repetition

Plain functions, as we’ve seen them so far, are a good way to build abstractions. But sometimes they fall short. It is common for a program to do something a given number of times. You can write a for loop for that, like this:

for (let i = 0; i < 10; i++) {

console.log(i);

}

Can we abstract “doing something N times” as a function? Well, it’s easy to write a function that calls console.log N times.

function repeatLog(n) {

for (let i = 0; i < n; i++) {

console.log(i);

   }

}

But what if we want to do something other than logging the numbers? Since “doing something” can be represented as a function and functions are just values, we can pass our action as a function value.

function repeat(n, action) {

for (let i = 0; i < n; i++) {

action(i);

   }

}

repeat(3, console.log);

// → 0

// → 1

// → 2

We don’t have to pass a predefined function to repeat. Often, it is easier to create a function value on the spot instead.

let labels = [];

repeat(5, i => {

labels.push(`Unit ${i + 1}`);

});

console.log(labels);

// → [“Unit 1”, “Unit 2”, “Unit 3”, “Unit 4”, “Unit 5”]

This is structured a little like a for loop—it first describes the kind of loop and then provides a body. However, the body is now written as a function value, which is wrapped in the parentheses of the call to repeat. This is why it has to be closed with the closing brace and closing parenthesis. In cases like this example, where the body is a single small expression, you could also omit the braces and write the loop on a single line.

Higher-order functions

Functions that operate on other functions, either by taking them as arguments or by returning them, are called higher-order functions. Since we have already seen that functions are regular values, there is nothing particularly remarkable about the fact that such functions exist. The term comes from mathematics, where the distinction between functions and other values is taken more seriously. Higher-order functions allow us to abstract over actions, not just values. They come in several forms. For example, we can have functions that create new functions.

function greaterThan(n) {

return m => m > n;

}

let greaterThan10 = greaterThan(10);

console.log(greaterThan10(11));

// → true

And we can have functions that change other functions.

function noisy(f) {

return (…args) => {

console.log(“calling with”, args);

let result = f(…args);

console.log(“called with”, args, “, returned”, result);

return result;

  };

}

noisy(Math.min)(3, 2, 1);

// → calling with [3, 2, 1]

// → called with [3, 2, 1] , returned 1

We can even write functions that provide new types of control flow.

function unless(test, then) {

if (!test) then();

}

repeat(3, n => {

unless(n % 2 == 1, () => {

console.log(n, “is even”);

   });

});

// → 0 is even

// → 2 is even

There is a built-in array method, forEach, that provides something like a for/of loop as a higher-order function.

[“A”, “B”].forEach(l => console.log(l));

// → A

// → B

Script data set

One area where higher-order functions shine is data processing. To process data, we’ll need some actual data. This chapter will use a data set about scripts—writing systems such as Latin, Cyrillic, or Arabic. Remember Unicode , the system that assigns a number to each character in written language? Most of these characters are associated with a specific script. The standard contains 140 different scripts—81 are still in use today, and 59 are historic. Though some can fluently read only Latin characters,we appreciate the fact that people are writing texts in at least 80 other writing systems, many of which we wouldn’t even recognize. For example, here’s a sample of Tamil handwriting:

The example data set contains some pieces of information about the 140 scripts defined in Unicode The binding contains an array of objects, each of which describes a script.

{

name: “Coptic”,

ranges: [[994, 1008], [11392, 11508], [11513, 11520]],

direction: “ltr”,

year: -200,

living: false,

link: “https://en.wikipedia.org/wiki/Coptic_alphabet”

}

Such an object tells us the name of the script, the Unicode ranges assigned to it, the direction in which it is written, the (approximate) origin time, whether it is still in use, and a link to more information. The direction may be “ltr” for left to right, “rtl” for right to left (the way Arabic and Hebrew text are written), or “ttb” for top to bottom (as with Mongolian writing). The ranges property contains an array of Unicode character ranges, each of which is a two-element array containing a lower bound and an upper bound. Any character codes within these ranges are assigned to the script. The lower bound is inclusive (code 994 is a Coptic character), and the upper bound is non-inclusive (code 1008 isn’t).

Filtering arrays

To find the scripts in the data set that are still in use, the following function might be helpful. It filters out the elements in an array that don’t pass a test.

function filter(array, test) {

let passed = [];

for (let element of array) {

if (test(element)) {

passed.push(element);

   }

}

return passed;

}

console.log(filter(SCRIPTS, script => script.living));

// → [{name: “Adlam”, …}, …]

The function uses the argument named test, a function value, to fill a “gap” in the computation—the process of deciding which elements to collect. Note how the filter function, rather than deleting elements from the existing array, builds up a new array with only the elements that pass the test. This function is pure. It does not modify the array it is given. Like forEach, filter is a standard array method. The example defined the function only to show what it does internally. From now on, we’ll use it like this instead:

console.log(SCRIPTS.filter(s => s.direction == “ttb”));

// → [{name: “Mongolian”, …}, …]

Transforming with map

Say we have an array of objects representing scripts, produced by filtering the SCRIPTS array somehow. But we want an array of names, which is easier to inspect. The map method transforms an array by applying a function to all of its elements and building a new array from the returned values. The new array will have the same length as the input array, but its content will have been mapped to a new form by the function.

function map(array, transform) {

let mapped = [];

for (let element of array) {

mapped.push(transform(element));

}

return mapped;

}

let rtlScripts = SCRIPTS.filter(s => s.direction == “rtl”); console.log(map(rtlScripts, s => s.name));

// → [“Adlam”, “Arabic”, “Imperial Aramaic”, …]

Like forEach and filter, map is a standard array method.

Summarizing with reduce

Another common thing to do with arrays is to compute a single value from them. Our recurring example, summing a collection of numbers, is an instance of this. Another example is finding the script with the most characters. The higher-order operation that represents this pattern is called reduce (some-times also called fold). It builds a value by repeatedly taking a single element from the array and combining it with the current value. When summing numbers, you’d start with the number zero and, for each element, add that to the sum. The parameters to reduce are, apart from the array, a combining function and a start value. This function is a little less straightforward than filter and map, so take a close look at this function:

function reduce(array, combine, start) { let current = start;

for (let element of array) {

current = combine(current, element);

}

return current;

}

console.log(reduce([1, 2, 3, 4], (a, b) => a + b, 0));

// → 10

The standard array method reduce, which of course corresponds to this function, has an added convenience. If your array contains at least one element, you are allowed to leave off the start argument. The method will take the first element of the array as its start value and start reducing at the second element.

console.log([1, 2, 3, 4].reduce((a, b) => a + b));

// → 10

To use reduce (twice) to find the script with the most characters, we can write something like this:

function characterCount(script) {

return script.ranges.reduce((count, [from, to]) => {

     return count + (to – from);

   }, 0);

}

console.log(SCRIPTS.reduce((a, b) => {

return characterCount(a) < characterCount(b) ? b : a;

}));

// → {name: “Han”, …}

The characterCount function reduces the ranges assigned to a script by summing their sizes. Note the use of destructuring in the parameter list of the reducer function. The second call to reduce then uses this to find the largest script by repeatedly comparing two scripts and returning the larger one.

The Han script has more than 89,000 characters assigned to it in the Unicode standard, making it by far the biggest writing system in the data set. Han is a script (sometimes) used for Chinese, Japanese, and Korean text. Those languages share a lot of characters, though they tend to write them differently. The (U.S.-based) Unicode Consortium decided to treat them as a single writing system to save character codes. This is called Han unification and still makes some people very angry.

Composability

Consider how we would have written the previous example (finding the biggest script) without higher-order functions. The code is not that much worse.

let biggest = null;

for (let script of SCRIPTS) {

if (biggest == null ||

characterCount(biggest) < characterCount(script)) {

biggest = script;

     }

}

console.log(biggest);

// → {name: “Han”, …}

There are a few more bindings, and the program is four lines longer. But it is still very readable. Higher-order functions start to shine when you need to compose operations. As an example, let’s write code that finds the average year of origin for living and dead scripts in the data set.

function average(array) {

return array.reduce((a, b) => a + b) / array.length;

}

console.log(Math.round(average(

SCRIPTS.filter(s => s.living).map(s => s.year))));

// → 1188 console.log(Math.round(average(

SCRIPTS.filter(s => !s.living).map(s => s.year))));

/ → 188

So the dead scripts in Unicode are, on average, older than the living ones. This is not a terribly meaningful or surprising statistic. But  hope you’ll agree that the code used to compute it isn’t hard to read. You can see it as a pipeline: we start with all scripts, filter out the living (or dead) ones, take the years from those, average them, and round the result. You could definitely also write this computation as one big loop.

let total = 0, count = 0;

for (let script of SCRIPTS) {

if (script.living) {

total += script.year;

count += 1;

   }

}

console.log(Math.round(total / count));

// → 1188

But it is harder to see what was being computed and how. And because intermediate results aren’t represented as coherent values, it’d be a lot more work to extract something like average into a separate function. In terms of what the computer is actually doing, these two approaches are also quite different. The first will build up new arrays when running filter and map, whereas the second computes only some numbers, doing less work. You can usually afford the readable approach, but if you’re processing huge arrays, and doing so many times, the less abstract style might be worth the extra speed.

Strings and character codes

One use of the data set would be figuring out what script a piece of text is using. Let’s go through a program that does this. Remember that each script has an array of character code ranges associated with it. So given a character code, we could use a function like this to find the corresponding script (if any):

function characterScript(code) {

for (let script of SCRIPTS) {

if (script.ranges.some(([from, to]) => {

return code >= from && code < to;

})) {

return script;

    }

}

return null;

}

console.log(characterScript(121));

// → {name: “Latin”, …}

The some method is another higher-order function. It takes a test function and tells you whether that function returns true for any of the elements in the array.But how do we get the character codes in a string? We mentioned that JavaScript strings are encoded as a sequence of 16-bit numbers. These are called code units. A Unicode character code was initially supposed to fit within such a unit (which gives you a little over 65,000 characters). When it became clear that wasn’t going to be enough, many people balked at the need to use more memory per character. To address these concerns, UTF-16, the format used by JavaScript strings, was invented. It describes most common characters using a single 16-bit code unit but uses a pair of two such units for others.

UTF-16 is generally considered a bad idea today. It seems almost intentionally designed to invite mistakes. It’s easy to write programs that pretend code units and characters are the same thing. And if your language doesn’t use two-unit characters, that will appear to work just fine. But as soon as some-one tries to use such a program with some less common Chinese characters, it breaks. Fortunately, with the advent of emoji, everybody has started using two-unit characters, and the burden of dealing with such problems is more fairly distributed.

Unfortunately, obvious operations on JavaScript strings, such as getting their length through the length property and accessing their content using square brackets, deal only with code units.

// Two emoji characters, horse and shoe

let horseShoe = “🐴👟”;

console.log(horseShoe.length);
// → 4
console.log(horseShoe[0]);
// → (Invalid half-character)

console.log(horseShoe.charCodeAt(0));
// → 55357 (Code of the half-character)

console.log(horseShoe.codePointAt(0));
// → 128052 (Actual code for horse emoji)

JavaScript’s charCodeAt method gives you a code unit, not a full character code. The codePointAt method, added later, does give a full Unicode character. So we could use that to get characters from a string. But the argument passed to codePointAt is still an index into the sequence of code units. So to run over all characters in a string, we’d still need to deal with the question of whether a character takes up one or two code units. We mentioned that a for/of loop can also be used on strings. Like codePointAt, this type of loop was introduced at a time where people were acutely aware of the problems with UTF-16. When you use it to loop over a string, it gives you real characters, not code units.

let roseDragon = “🌹🐉”;
for (let char of roseDragon) {
console.log(char);
}

// → 🌹 // → 🐉

If you have a character (which will be a string of one or two code units), you can use codePointAt(0) to get its code.

Recognizing text

We have a characterScript function and a way to correctly loop over characters. The next step is to count the characters that belong to each script. The following counting abstraction will be useful there:

function countBy(items, groupName) {

let counts = [];

for (let item of items) {

let name = groupName(item);

let known = counts.findIndex(c => c.name == name); if (known == -1) {

counts.push({name, count: 1});

} else {

counts[known].count++;

    }

}

return counts;

}

console.log(countBy([1, 2, 3, 4, 5], n => n > 2));

// → [{name: false, count: 2}, {name: true, count: 3}]

The countBy function expects a collection (anything that we can loop over with for/of) and a function that computes a group name for a given element. It returns an array of objects, each of which names a group and tells you the number of elements that were found in that group. It uses another array method—findIndex. This method is somewhat like indexOf, but instead of looking for a specific value, it finds the first value for which the given function returns true. Like indexOf, it returns -1 when no such element is found. Using countBy, we can write the function that tells us which scripts are used in a piece of text.

function textScripts(text) {

let scripts = countBy(text, char => {

let script = characterScript(char.codePointAt(0));

return script ? script.name : “none”;

}).filter(({name}) => name != “none”);

let total = scripts.reduce((n, {count}) => n + count, 0);

if (total == 0) return “No scripts found”;

return scripts.map(({name, count}) => {

return `${Math.round(count * 100 / total)}% ${name}`;

}).join(“, “);

}

console.log(textScripts(‘英国的狗说“woof”, 俄罗斯的狗说“тяв”‘));

// → 61% Han, 22% Latin, 17% Cyrillic

The function first counts the characters by name, using characterScript to assign them a name and falling back to the string “none” for characters that aren’t part of any script. The filter call drops the entry for “none” from the resulting array since we aren’t interested in those characters. To be able to compute percentages, we first need the total number of characters that belong to a script, which we can compute with reduce. If no such characters are found, the function returns a specific string. Otherwise, it transforms the counting entries into readable strings with map and then combines them with join.

The Secret Life of Objects

In programming culture, we have a thing called object-oriented programming, a set of techniques that use objects (and related concepts) as the central principle of program organization. Though no one really agrees on its precise definition, object-oriented programming has shaped the design of many programming languages, including JavaScript. This chapter will describe the way these ideas can be applied in JavaScript.

Encapsulation

The core idea in object-oriented programming is to divide programs into smaller pieces and make each piece responsible for managing its own state. This way, some knowledge about the way a piece of the program works can be kept local to that piece. Someone working on the rest of the program does not have to remember or even be aware of that knowledge. Whenever these local details change, only the code directly around it needs to be updated. Different pieces of such a program interact with each other through interfaces, limited sets of functions or bindings that provide useful functionality at a more abstract level, hiding their precise implementation.

Such program pieces are modeled using objects. Their interface consists of a specific set of methods and properties. Properties that are part of the interface are called public. The others, which outside code should not be touching, are called privateMany languages provide a way to distinguish public and private properties and prevent outside code from accessing the private ones altogether. JavaScript, once again taking the minimalist approach, does not—not yet at least. There is work underway to add this to the language. Even though the language doesn’t have this distinction built in, JavaScript programmers are successfully using this idea. Typically, the available interface is described in documentation or comments. It is also common to put an underscore (_) character at the start of property names to indicate that those properties are private. Separating interface from implementation is a great idea. It is usually called encapsulation.

Methods

Methods are nothing more than properties that hold function values. This is a simple method:

let rabbit = {};

rabbit.speak = function(line) {

console.log(`The rabbit says ‘${line}’`);

};

rabbit.speak(“I’m alive.”);

// → The rabbit says ‘I’m alive.’

Usually a method needs to do something with the object it was called on. When a function is called as a method—looked up as a property and immediately called, as in object.method()—the binding called this in its body automatically points at the object that it was called on.

function speak(line) {

console.log(`The ${this.type} rabbit says ‘${line}’`);

}

let whiteRabbit = {type: “white”, speak};

let hungryRabbit = {type: “hungry”, speak};

whiteRabbit.speak(“Oh my ears and whiskers, ” + “how late it’s getting!”);

// → The white rabbit says ‘Oh my ears and whiskers, how

// late it’s getting!’

hungryRabbit.speak(“I could use a carrot right now.”);

// → The hungry rabbit says ‘I could use a carrot right now.’

You can think of this as an extra parameter that is passed in a different way. If you want to pass it explicitly, you can use a function’s call method, which takes the this value as its first argument and treats further arguments as normal parameters.

speak.call(hungryRabbit, “Burp!”);

// → The hungry rabbit says ‘Burp!’

Since each function has its own this binding, whose value depends on the way it is called, you cannot refer to the this of the wrapping scope in a regular function defined with the function keyword. Arrow functions are different—they do not bind their own this but can see the this binding of the scope around them. Thus, you can do something like the following code, which references this from inside a local function:

function normalize() {

console.log(this.coords.map(n => n / this.length));

}

normalize.call({coords: [0, 2, 3], length: 5});

// → [0, 0.4, 0.6]

If I had written the argument to map using the function keyword, the code wouldn’t work.

Prototypes

Watch closely.

let empty = {};

console.log(empty.toString);

// → function toString()…{}

console.log(empty.toString());

// → [object Object]

We have pulled a property out of an empty object. Magic! Well, not really. We have simply been withholding information about the way JavaScript objects work. In addition to their set of properties, most objects also have a prototype. A prototype is another object that is used as a fallback source of properties. When an object gets a request for a property that it does not have, its prototype will be searched for the property, then the prototype’s prototype, and so on. So who is the prototype of that empty object? It is the great ancestral prototype, the entity behind almost all objects, Object.prototype.

console.log(Object.getPrototypeOf({}) == Object.prototype);

// → true

console.log(Object.getPrototypeOf(Object.prototype));

// → null

As you guess, Object.getPrototypeOf returns the prototype of an object. The prototype relations of JavaScript objects form a tree-shaped structure, and at the root of this structure sits Object.prototype.  It provides a few methods that show up in all objects, such as toString, which converts an object to a string representation. Many objects don’t directly have Object.prototype as their prototype but instead have another object that provides a different set of default properties. Functions derive from Function.prototype, and arrays derive from Array .prototype.

console.log(Object.getPrototypeOf(Math.max) == Function.prototype);

// → true

console.log(Object.getPrototypeOf([]) ==

                       Array.prototype);

// → true

Such a prototype object will itself have a prototype, often Object.prototype, so that it still indirectly provides methods like toStringYou can use Object.create to create an object with a specific prototype.

let protoRabbit = {

speak(line) {

console.log(`The ${this.type} rabbit says ‘${line}’`);

}

};

let killerRabbit = Object.create(protoRabbit);

killerRabbit.type = “killer”;

killerRabbit.speak(“SKREEEE!”);

// → The killer rabbit says ‘SKREEEE!’

A property like speak(line) in an object expression is a shorthand way of defining a method. It creates a property called speak and gives it a function as its value. The “proto” rabbit acts as a container for the properties that are shared by all rabbits. An individual rabbit object, like the killer rabbit, contains properties that apply only to itself—in this case its type—and derives shared properties from its prototype.

Classes

JavaScript’s prototype system can be interpreted as a somewhat informal take on an object-oriented concept called classes. A class defines the shape of a type of object—what methods and properties it has. Such an object is called an instance of the class. Prototypes are useful for defining properties for which all instances of a class share the same value, such as methods. Properties that differ per instance, such as our rabbits’ type property, need to be stored directly in the objects themselves.

So to create an instance of a given class, you have to make an object that derives from the proper prototype, but you also have to make sure it, itself, has the properties that instances of this class are supposed to have. This is what a constructor function does.

function makeRabbit(type) {

let rabbit = Object.create(protoRabbit);

rabbit.type = type;

return rabbit;

}

JavaScript provides a way to make defining this type of function easier. If you put the keyword new in front of a function call, the function is treated as a constructor. This means that an object with the right prototype is automatically created, bound to this in the function, and returned at the end of the function. The prototype object used when constructing objects is found by taking the prototype property of the constructor function.

function Rabbit(type) {

this.type = type;

}

Rabbit.prototype.speak = function(line) {

console.log(`The ${this.type} rabbit says ‘${line}’`);

};

let weirdRabbit = new Rabbit(“weird”);

Constructors (all functions, in fact) automatically get a property named prototype, which by default holds a plain, empty object that derives from Object.prototype. You can overwrite it with a new object if you want. Or you can add properties to the existing object, as the example does. By convention, the names of constructors are capitalized so that they can easily be distinguished from other functions. It is important to understand the distinction between the way a prototype is associated with a constructor (through its prototype property) and the way objects have a prototype (which can be found with Object.getPrototypeOf). The actual prototype of a constructor is Function.prototype since constructors are functions. Its prototype property holds the prototype used for instances created through it.

console.log(Object.getPrototypeOf(Rabbit) ==

Function.prototype);

// → true console.log(Object.getPrototypeOf(weirdRabbit) ==

                                          Rabbit.prototype);

// → true

Class notation

So JavaScript classes are constructor functions with a prototype property. That is how they work, and until 2015, that was how you had to write them. These days, we have a less awkward notation.

class Rabbit {

constructor(type) {

this.type = type;

}

speak(line) {

console.log(`The ${this.type} rabbit says ‘${line}’`);

}

}

let killerRabbit = new Rabbit(“killer”);

let blackRabbit = new Rabbit(“black”);

The class keyword starts a class declaration, which allows us to define a constructor and a set of methods all in a single place. Any number of methods may be written inside the declaration’s braces. The one named constructor is treated specially. It provides the actual constructor function, which will be bound to the name Rabbit. The others are packaged into that constructor’s prototype. Thus, the earlier class declaration is equivalent to the constructor definition from the previous section. It just looks nicer.

Class declarations currently allow only methods—properties that hold functions— to be added to the prototype. This can be somewhat inconvenient when you want to save a non-function value in there. The next version of the language will probably improve this. For now, you can create such properties by directly manipulating the prototype after you’ve defined the class. Like function, class can be used both in statements and in expressions. When used as an expression, it doesn’t define a binding but just produces the constructor as a value. You are allowed to omit the class name in a class expression.

let object = new class { getWord() { return “hello”; } };

console.log(object.getWord());

// → hello

Overriding derived properties

When you add a property to an object, whether it is present in the prototype or not, the property is added to the object itself. If there was already a property with the same name in the prototype, this property will no longer affect the object, as it is now hidden behind the object’s own property.

Rabbit.prototype.teeth = “small”;

console.log(killerRabbit.teeth);

// → small

killerRabbit.teeth = “long, sharp, and bloody”;

console.log(killerRabbit.teeth);

// → long, sharp, and bloody

console.log(blackRabbit.teeth);

// → small

console.log(Rabbit.prototype.teeth);

// → small

The following diagram sketches the situation after this code has run. The Rabbit and Object prototypes lie behind killerRabbit as a kind of backdrop, where properties that are not found in the object itself can be looked up.

Overriding properties that exist in a prototype can be a useful thing to do. As the rabbit teeth example shows, overriding can be used to express exceptional properties in instances of a more generic class of objects, while letting the nonexceptional objects take a standard value from their prototype. Overriding is also used to give the standard function and array prototypes a different toString method than the basic object prototype.

console.log(Array.prototype.toString == Object.prototype.toString);

// → false

console.log([1, 2].toString());

// → 1,2

Calling toString on an array gives a result similar to calling .join(“,”) on it—it puts commas between the values in the array. Directly calling Object. prototype.toString with an array produces a different string. That function doesn’t know about arrays, so it simply puts the word object and the name of the type between square brackets.

console.log(Object.prototype.toString.call([1, 2]));

// → [object Array]

Maps

We saw the word map used in the previous  for an operation that transforms a data structure by applying a function to its elements. Confusing as it is, in programming the same word is also used for a related but rather different thing. A map (noun) is a data structure that associates values (the keys) with other values. For example, you might want to map names to ages. It is possible to use objects for this.

let ages = {

Boris: 39,

Liang: 22,

Júlia: 62

};

console.log(`Júlia is ${ages[“Júlia”]}`);

// → Júlia is 62

console.log(“Is Jack’s age known?”, “Jack” in ages);

// → Is Jack’s age known? false

console.log(“Is toString’s age known?”, “toString” in ages);

// → Is toString’s age known? true

Here, the object’s property names are the people’s names, and the property values are their ages. But we certainly didn’t list anybody named toString in our map. Yet, because plain objects derive from Object.prototype, it looks like the property is there. As such, using plain objects as maps is dangerous. There are several possible ways to avoid this problem. First, it is possible to create objects with no prototype. If you pass null to Object.create, the resulting object will not derive from Object.prototype and can safely be used as a map.

console.log(“toString” in Object.create(null));

// → false

Object property names must be strings. If you need a map whose keys can’t easily be converted to strings—such as objects—you cannot use an object as your map. Fortunately, JavaScript comes with a class called Map that is written for this exact purpose. It stores a mapping and allows any type of keys.

let ages = new Map();

ages.set(“Boris”, 39);

ages.set(“Liang”, 22);

ages.set(“Júlia”, 62);

console.log(`Júlia is ${ages.get(“Júlia”)}`);

// → Júlia is 62

console.log(“Is Jack’s age known?”, ages.has(“Jack”));

// → Is Jack’s age known? false

console.log(ages.has(“toString”));

// → false

The methods set, get, and has are part of the interface of the Map object. Writing a data structure that can quickly update and search a large set of values isn’t easy, but we don’t have to worry about that. Someone else did it for us, and we can go through this simple interface to use their work. If you do have a plain object that you need to treat as a map for some reason, it is useful to know that Object.keys returns only an object’s own keys, not those in the prototype. As an alternative to the in operator, you can use the hasOwnProperty method, which ignores the object’s prototype.

console.log({x: 1}.hasOwnProperty(“x”));

// → true

console.log({x: 1}.hasOwnProperty(“toString”));

// → false

Polymorphism

When you call the String function (which converts a value to a string) on an object, it will call the toString method on that object to try to create a meaningful string from it. We mentioned that some of the standard prototypes define their own version of toString so they can create a string that contains more useful information than “[object Object]”. You can also do that yourself.

Rabbit.prototype.toString = function() {

      return `a ${this.type} rabbit`;

};

console.log(String(blackRabbit));

// → a black rabbit

This is a simple instance of a powerful idea. When a piece of code is written to work with objects that have a certain interface—in this case, a toString method—any kind of object that happens to support this interface can be plugged into the code, and it will just work. This technique is called polymorphism. Polymorphic code can work with values of different shapes, as long as they support the interface it expects. We have mentioned  that a for/of loop can loop over several kinds of data structures. This is another case of polymorphism—such loops expect the data structure to expose a specific interface, which arrays and strings do. And we can also add this interface to your own objects! But before we can do that, we need to know what symbols are.

Symbols

It is possible for multiple interfaces to use the same property name for different things. For example, we could define an interface in which the toString method is supposed to convert the object into a piece of yarn. It would not be possible for an object to conform to both that interface and the standard use of toStringThat would be a bad idea, and this problem isn’t that common. Most JavaScript programmers simply don’t think about it. But the language designers, whose job it is to think about this stuff, have provided us with a solution anyway.

When we claimed that property names are strings, that wasn’t entirely accurate. They usually are, but they can also be symbols. Symbols are values created with the Symbol function. Unlike strings, newly created symbols are unique—you cannot create the same symbol twice.

let sym = Symbol(“name”);

console.log(sym == Symbol(“name”));

// → false Rabbit.prototype[sym] = 55;

console.log(blackRabbit[sym]);

// → 55

The string you pass to Symbol is included when you convert it to a string and can make it easier to recognize a symbol when, for example, showing it in the console. But it has no meaning beyond that—multiple symbols may have the same name. Being both unique and usable as property names makes symbols suitable for defining interfaces that can peacefully live alongside other properties, no matter what their names are.

const toStringSymbol = Symbol(“toString”);

Array.prototype[toStringSymbol] = function() {

return `${this.length} cm of blue yarn`;

};

console.log([1, 2].toString());

// → 1,2

console.log([1, 2][toStringSymbol]());

// → 2 cm of blue yarn

It is possible to include symbol properties in object expressions and classes by using square brackets around the property name. That causes the property name to be evaluated, much like the square bracket property access notation, which allows us to refer to a binding that holds the symbol.

let stringObject = {

[toStringSymbol]() { return “a jute rope”; }

};

console.log(stringObject[toStringSymbol]());

// → a jute rope

The iterator interface

The object given to a for/of loop is expected to be iterable. This means it has a method named with the Symbol.iterator symbol (a symbol value defined by the language, stored as a property of the Symbol function). When called, that method should return an object that provides a second interface, iterator. This is the actual thing that iterates. It has a next method that returns the next result. That result should be an object with a value property that provides the next value, if there is one, and a done property, which should be true when there are no more results and false otherwise.

Note that the next, value, and done property names are plain strings, not symbols. Only Symbol.iterator, which is likely to be added to a lot of different objects, is an actual symbol. We can directly use this interface ourselves.

let okIterator = “OK”[Symbol.iterator]();

console.log(okIterator.next());

// → {value: “O”, done: false}

console.log(okIterator.next());

// → {value: “K”, done: false}

console.log(okIterator.next());

// → {value: undefined, done: true}

Let’s implement an iterable data structure. We’ll build a matrix class, acting as a two-dimensional array.

class Matrix {

constructor(width, height, element = (x, y) => undefined) {

this.width = width;

this.height = height;

this.content = [];

for (let y = 0; y < height; y++) {

for (let x = 0; x < width; x++) {

this.content[y * width + x] = element(x, y);

          }

     }

}

get(x, y) {

return this.content[y * this.width + x];

}

set(x, y, value) {

this.content[y * this.width + x] = value;

       }

}

The class stores its content in a single array of width × height elements. The elements are stored row by row, so, for example, the third element in the fifth row is (using zero-based indexing) stored at position 4 × width + 2. The constructor function takes a width, a height, and an optional content function that will be used to fill in the initial values. There are get and set methods to retrieve and update elements in the matrix. When looping over a matrix, you are usually interested in the position of the elements as well as the elements themselves, so we’ll have our iterator produce objects with x, y, and value properties.

class MatrixIterator {

     constructor(matrix) {

            this.x = 0;

            this.y = 0;

            this.matrix = matrix;

   }

next() {

      if (this.y == this.matrix.height) return {done: true};

      let value = {x: this.x,

                           y: this.y,

                          value: this.matrix.get(this.x, this.y)};

     this.x++;

     if (this.x == this.matrix.width) {

            this.x = 0;

           this.y++;

}

return {value, done: false};

       }

}

The class tracks the progress of iterating over a matrix in its x and y properties. The next method starts by checking whether the bottom of the matrix has been reached. If it hasn’t, it first creates the object holding the current value and then updates its position, moving to the next row if necessary. Let’s set up the Matrix class to be iterable. We’ll occasionally use after-the-fact prototype manipulation to add methods to classes so that the individual pieces of code remain small and self-contained. In a regular program, where there is no need to split the code into small pieces, you’d declare these methods directly in the class instead.

Matrix.prototype[Symbol.iterator] = function() {

return new MatrixIterator(this);

};

We can now loop over a matrix with for/of.

let matrix = new Matrix(2, 2, (x, y) => `value ${x},${y}`);

for (let {x, y, value} of matrix) {

console.log(x, y, value);

}

// → 0 0 value 0,0

// → 1 0 value 1,0

// → 0 1 value 0,1

// → 1 1 value 1,1

Getters, setters, and statics

Interfaces often consist mostly of methods, but it is also okay to include properties that hold non-function values. For example, Map objects have a size property that tells you how many keys are stored in them. It is not even necessary for such an object to compute and store such a property directly in the instance. Even properties that are accessed directly may hide a method call. Such methods are called getters, and they are defined by writing get in front of the method name in an object expression or class declaration.

let varyingSize = {

get size() {

return Math.floor(Math.random() * 100);

   }

};

console.log(varyingSize.size);

// → 73

console.log(varyingSize.size);

// → 49

Whenever someone reads from this object’s size property, the associated method is called. You can do a similar thing when a property is written to, using a setter.

class Temperature {

constructor(celsius) {

this.celsius = celsius;

}

get fahrenheit() {

return this.celsius * 1.8 + 32;

}

set fahrenheit(value) {

this.celsius = (value – 32) / 1.8;

}

static fromFahrenheit(value) {

return new Temperature((value – 32) / 1.8);

    }

}

let temp = new Temperature(22);

console.log(temp.fahrenheit);

// → 71.6

temp.fahrenheit = 86;

console.log(temp.celsius);

// → 30

The Temperature class allows you to read and write the temperature in either degrees Celsius or degrees Fahrenheit, but internally it stores only Celsius and automatically converts to and from Celsius in the fahrenheit getter and setter. Sometimes you want to attach some properties directly to your constructor function, rather than to the prototype. Such methods won’t have access to a class instance but can, for example, be used to provide additional ways to create instances. Inside a class declaration, methods that have static written before their name are stored on the constructor. So the Temperature class allows you to write Temperature.fromFahrenheit(100) to create a temperature using degrees Fahrenheit.

Inheritance

Some matrices are known to be symmetric. If you mirror a symmetric matrix around its top-left-to-bottom-right diagonal, it stays the same. In other words, the value stored at x,y is always the same as that at y,xImagine we need a data structure like Matrix but one that enforces the fact that the matrix is and remains symmetrical. We could write it from scratch, but that would involve repeating some code very similar to what we already wrote.

JavaScript’s prototype system makes it possible to create a new class, much like the old class, but with new definitions for some of its properties. The prototype for the new class derives from the old prototype but adds a new definition for, say, the set method. In object-oriented programming terms, this is called inheritance. The new class inherits properties and behavior from the old class.

class SymmetricMatrix extends Matrix {

constructor(size, element = (x, y) => undefined) {

super(size, size, (x, y) => {

      if (x < y) return element(y, x);

             else return element(x, y);

    });

}

set(x, y, value) {

   super.set(x, y, value);

     if (x != y) {

       super.set(y, x, value);

     }

  }

}

let matrix = new SymmetricMatrix(5, (x, y) => `${x},${y}`); console.log(matrix.get(2, 3));

// → 3,2

The use of the word extends indicates that this class shouldn’t be directly based on the default Object prototype but on some other class. This is called the superclass. The derived class is the subclassTo initialize a SymmetricMatrix instance, the constructor calls its superclass’s constructor through the super keyword. This is necessary because if this new object is to behave (roughly) like a Matrix, it is going to need the instance properties that matrices have. To ensure the matrix is symmetrical, the constructor wraps the content method to swap the coordinates for values below the diagonal. The set method again uses super but this time not to call the constructor but to call a specific method from the superclass’s set of methods. We are redefining set but do want to use the original behavior. Because this.set refers to the new set method, calling that wouldn’t work. Inside class methods, super provides a way to call methods as they were defined in the superclass.

Inheritance allows us to build slightly different data types from existing data types with relatively little work. It is a fundamental part of the object-oriented tradition, alongside encapsulation and polymorphism. But while the latter two are now generally regarded as wonderful ideas, inheritance is more controversial. Whereas encapsulation and polymorphism can be used to separate pieces of code from each other, reducing the tangledness of the overall program, inheritance fundamentally ties classes together, creating more tangle. When inheriting from a class, you usually have to know more about how it works than when simply using it. Inheritance can be a useful tool, and I use it now and then in my own programs, but it shouldn’t be the first tool you reach for, and you probably shouldn’t actively go looking for opportunities to construct class hierarchies (family trees of classes).

The instanceof operator

It is occasionally useful to know whether an object was derived from a specific class. For this, JavaScript provides a binary operator called instanceof.

console.log(

   new SymmetricMatrix(2) instanceof SymmetricMatrix);

// → true

console.log(new SymmetricMatrix(2) instanceof Matrix);

// → true

console.log(new Matrix(2, 2) instanceof SymmetricMatrix);

// → false

console.log([1] instanceof Array);

// → true

The operator will see through inherited types, so a SymmetricMatrix is an instance of Matrix. The operator can also be applied to standard constructors like Array. Almost every object is an instance of Object.

Summary

Objects and arrays (which are a specific kind of object) provide ways to group several values into a single value. Conceptually, this allows us to put a bunch of related things in a bag and run around with the bag, instead of wrapping our arms around all of the individual things and trying to hold on to them separately.

Most values in JavaScript have properties, the exceptions being null and undefined. Properties are accessed using value.prop or value[“prop”]. Objects tend to use names for their properties and store more or less a fixed set of them. Arrays, on the other hand, usually contain varying amounts of conceptually identical values and use numbers (starting from 0) as the names of their properties. There are some named properties in arrays, such as length and a number of methods. Methods are functions that live in properties and (usually) act on the value they are a property of. You can iterate over arrays using a special kind of for loop—for (let element of array).

Being able to pass function values to other functions is a deeply useful aspect of JavaScript. It allows us to write functions that model computations with “gaps” in them. The code that calls these functions can fill in the gaps by providing function values. Arrays provide a number of useful higher-order methods. You can use forEach to loop over the elements in an array. The filter method returns a new array containing only the elements that pass the predicate function. Transforming an array by putting each element through a function is done with map. You can use reduce to combine all the elements in an array into a single value. The some method tests whether any element matches a given predicate function. And findIndex finds the position of the first element that matches a predicate.

So objects do more than just hold their own properties. They have prototypes, which are other objects. They’ll act as if they have properties they don’t have as long as their prototype has that property. Simple objects have Object. prototype as their prototype. Constructors, which are functions whose names usually start with a capital letter, can be used with the new operator to create new objects. The new object’s prototype will be the object found in the prototype property of the constructor. You can make good use of this by putting the properties that all values of a given type share into their prototype. There’s a class notation that provides a clear way to define a constructor and its prototype.

You can define getters and setters to secretly call methods every time an object’s property is accessed. Static methods are methods stored in a class’s constructor, rather than its prototype. The instanceof operator can, given an object and a constructor, tell you whether that object is an instance of that constructor. One useful thing to do with objects is to specify an interface for them and tell everybody that they are supposed to talk to your object only through that interface. The rest of the details that make up your object are now encapsulated, hidden behind the interface.

More than one type may implement the same interface. Code written to use an interface automatically knows how to work with any number of different objects that provide the interface. This is called polymorphismWhen implementing multiple classes that differ in only some details, it can be helpful to write the new classes as subclasses of an existing class, inheriting part of its behavior.

Practice Project: A Robot

In “practice project” , we’ll stop pummeling you with new theory for a brief moment, and instead we’ll work through a program together. Theory is necessary to learn to program, but reading and understanding actual programs is just as important. Our project  is to build an automaton, a little program that performs a task in a virtual world. Our automaton will be a mail-delivery robot picking up and dropping off parcels.

Meadowfield

The village of Meadowfield isn’t very big. It consists of 11 places with 14 roads between them. It can be described with this array of roads:

const roads = [

“Alice’s House-Bob’s House”, “Alice’s House-Cabin”,

“Alice’s House-Post Office”, “Bob’s House-Town Hall”,

“Daria’s House-Ernie’s House”, “Daria’s House-Town Hall”,

“Ernie’s House-Grete’s House”, “Grete’s House-Farm”,

“Grete’s House-Shop”, “Marketplace-Farm”,

“Marketplace-Post Office”, “Marketplace-Shop”,

“Marketplace-Town Hall”, “Shop-Town Hall”

];

The network of roads in the village forms a graph. A graph is a collection of points (places in the village) with lines between them (roads). This graph will be the world that our robot moves through. The array of strings isn’t very easy to work with. What we’re interested in is the destinations that we can reach from a given place. Let’s convert the list of roads to a data structure that, for each place, tells us what can be reached from there.

function buildGraph(edges) {

let graph = Object.create(null);

function addEdge(from, to) {

if (graph[from] == null) {

function buildGraph(edges) {
let graph = Object.create(null);
function addEdge(from, to) {
if (graph[from] == null) {
graph[from] = [to];
} else {
graph[from].push(to);

} }

for (let [from, to] of edges.map(r => r.split(“-“))) {

addEdge(from, to);
addEdge(to, from);

}
return graph;
}

const roadGraph = buildGraph(roads);

Given an array of edges, buildGraph creates a map object that, for each node, stores an array of connected nodes. It uses the split method to go from the road strings, which have the form “Start-End”, to two-element arrays containing the start and end as separate strings.

The task

Our robot will be moving around the village. There are parcels in various places, each addressed to some other place. The robot picks up parcels when it comes to them and delivers them when it arrives at their destinations. The automaton must decide, at each point, where to go next. It has finished its task when all parcels have been delivered. To be able to simulate this process, we must define a virtual world that can describe it. This model tells us where the robot is and where the parcels are. When the robot has decided to move somewhere, we need to update the model to reflect the new situation.

If you’re thinking in terms of object-oriented programming, your first impulse might be to start defining objects for the various elements in the world: a class for the robot, one for a parcel, maybe one for places. These could then hold properties that describe their current state, such as the pile of parcels at a location, which we could change when updating the world. This is wrong. At least, it usually is. The fact that something sounds like an object does not automatically mean that it should be an object in your program. Reflexively writing classes for every concept in your application tends to leave you with a collection of interconnected objects that each have their own internal, changing state. Such programs are often hard to understand and thus easy to break.

Instead, let’s condense the village’s state down to the minimal set of values that define it. There’s the robot’s current location and the collection of undelivered parcels, each of which has a current location and a destination address. That’s it. And while we’re at it, let’s make it so that we don’t change this state when the robot moves but rather compute a new state for the situation after the move.

class VillageState {
constructor(place, parcels) {
this.place = place;
this.parcels = parcels;
}

move(destination) {
if (!roadGraph[this.place].includes(destination)) {return this;
} else {
let parcels = this.parcels.map(p => {
if (p.place != this.place) return p;
return {place: destination, address: p.address};
}).filter(p => p.place != p.address);
return new VillageState(destination, parcels);
}

} }

The move method is where the action happens. It first checks whether there is a road going from the current place to the destination, and if not, it returns the old state since this is not a valid move.

Then it creates a new state with the destination as the robot’s new place. But it also needs to create a new set of parcels—parcels that the robot is carrying (that are at the robot’s current place) need to be moved along to the new place. And parcels that are addressed to the new place need to be delivered—that is, they need to be removed from the set of undelivered parcels. The call to map takes care of the moving, and the call to filter does the delivering. Parcel objects aren’t changed when they are moved but recreated. The move method gives us a new village state but leaves the old one entirely intact.

let first = new VillageState(

“Post Office”,

[{place: “Post Office”, address: “Alice’s House”}]

);

let next = first.move(“Alice’s House”);

console.log(next.place);

// → Alice’s House

console.log(next.parcels);

// → []

console.log(first.place);

// → Post Office

The move causes the parcel to be delivered, and this is reflected in the next state. But the initial state still describes the situation where the robot is at the post office and the parcel is undelivered.

Persistent data

Data structures that don’t change are called immutable or persistent. They behave a lot like strings and numbers in that they are who they are and stay that way, rather than containing different things at different times. In JavaScript, just about everything can be changed, so working with values that are supposed to be persistent requires some restraint. There is a function called Object.freeze that changes an object so that writing to its properties is ignored. You could use that to make sure your objects aren’t changed, if you want to be careful. Freezing does require the computer to do some extra work, and having updates ignored is just about as likely to confuse someone as having them do the wrong thing. Sowe usually prefer to just tell people that a given object shouldn’t be messed with and hope they remember it.

let object = Object.freeze({value: 5});

object.value = 10;

console.log(object.value);

// → 5

Why are we going out of our way to not change objects when the language is obviously expecting us to? Because it helps us understand our programs. This is about complexity management again. When the objects in my system are fixed, stable things, we can consider operations on them in isolation—moving to Alice’s house from a given start state always produces the same new state. When objects change over time, that adds a whole new dimension of complexity to this kind of reasoning.

For a small system like the one we are building, we could handle that bit of extra complexity. But the most important limit on what kind of systems we can build is how much we can understand. Anything that makes your code easier to understand makes it possible to build a more ambitious system. Unfortunately, although understanding a system built on persistent data structures is easier, designing one, especially when your programming language isn’t helping, can be a little harder. We’ll look for opportunities to use persistent data structures, but we’ll also be using changeable ones.

Simulation

A delivery robot looks at the world and decides in which direction it wants to move. As such, we could say that a robot is a function that takes a VillageState object and returns the name of a nearby place.Because we want robots to be able to remember things, so that they can make and execute plans, we also pass them their memory and allow them to return a new memory. Thus, the thing a robot returns is an object containing both the direction it wants to move in and a memory value that will be given back to it the next time it is called.

function runRobot(state, robot, memory) {

for (let turn = 0;; turn++) {

if (state.parcels.length == 0) {

console.log(`Done in ${turn} turns`);

break;

}

let action = robot(state, memory);

state = state.move(action.direction);

memory = action.memory;

console.log(`Moved to ${action.direction}`);

   }

}

Consider what a robot has to do to “solve” a given state. It must pick up all parcels by visiting every location that has a parcel and deliver them by visiting every location that a parcel is addressed to, but only after picking up the parcel. What is the dumbest strategy that could possibly work? The robot could just walk in a random direction every turn. That means, with great likelihood, it will eventually run into all parcels and then also at some point reach the place where they should be delivered. Here’s what that could look like:

function randomPick(array) {

let choice = Math.floor(Math.random() * array.length);

return array[choice];

}

function randomRobot(state) {

return {direction: randomPick(roadGraph[state.place])};

}

Remember that Math.random() returns a number between zero and one—but always below one. Multiplying such a number by the length of an array and then applying Math.floor to it gives us a random index for the array. Since this robot does not need to remember anything, it ignores its second argument (remember that JavaScript functions can be called with extra arguments without ill effects) and omits the memory property in its returned object.

To put this sophisticated robot to work, we’ll first need a way to create a new state with some parcels. A static method (written here by directly adding a property to the constructor) is a good place to put that functionality.

VillageState.random = function(parcelCount = 5) {

let parcels = [];

for (let i = 0; i < parcelCount; i++) {

let address = randomPick(Object.keys(roadGraph));

let place;

do {

place = randomPick(Object.keys(roadGraph));

} while (place == address);

parcels.push({place, address});

}

return new VillageState(“Post Office”, parcels);

};

We don’t want any parcels that are sent from the same place that they are addressed to. For this reason, the do loop keeps picking new places when it gets one that’s equal to the address. Let’s start up a virtual world.

runRobot(VillageState.random(), randomRobot);

// → Moved to Marketplace

// → Moved to Town Hall

// →…

// → Done in 63 turns

It takes the robot a lot of turns to deliver the parcels because it isn’t planning ahead very well. We’ll address that soon.

The mail truck’s route

We should be able to do a lot better than the random robot. An easy improvement would be to take a hint from the way real-world mail delivery works. If we find a route that passes all places in the village, the robot could run that route twice, at which point it is guaranteed to be done. Here is one such route (starting from the post office):

const mailRoute = [

“Alice’s House”, “Cabin”, “Alice’s House”, “Bob’s House”, “Town Hall”, “Daria’s House”, “Ernie’s House”, “Grete’s House”, “Shop”, “Grete’s House”, “Farm”, “Marketplace”, “Post Office”

];

To implement the route-following robot, we’ll need to make use of robot memory. The robot keeps the rest of its route in its memory and drops the first element every turn.

function routeRobot(state, memory) {

if (memory.length == 0) {

memory = mailRoute;

}

return {direction: memory[0], memory: memory.slice(1)};

}

This robot is a lot faster already. It’ll take a maximum of 26 turns (twice the 13-step route) but usually less.

Pathfinding

Still, we wouldn’t really call blindly following a fixed route intelligent behavior. The robot could work more efficiently if it adjusted its behavior to the actual work that needs to be done. To do that, it has to be able to deliberately move toward a given parcel or toward the location where a parcel has to be delivered. Doing that, even when the goal is more than one move away, will require some kind of route-finding function. The problem of finding a route through a graph is a typical search problem. We can tell whether a given solution (a route) is a valid solution, but we can’t directly compute the solution the way we could for 2 + 2. Instead, we have to keep creating potential solutions until we find one that works.

The number of possible routes through a graph is infinite. But when searching for a route from A to B, we are interested only in the ones that start at A. We also don’t care about routes that visit the same place twice—those are definitely not the most efficient route anywhere. So that cuts down on the number of routes that the route finder has to consider.

In fact, we are mostly interested in the shortest route. So we want to make sure we look at short routes before we look at longer ones. A good approach would be to “grow” routes from the starting point, exploring every reachable place that hasn’t been visited yet, until a route reaches the goal. That way, we’ll only explore routes that are potentially interesting, and we’ll find the shortest route (or one of the shortest routes, if there are more than one) to the goal. Here is a function that does this:

function findRoute(graph, from, to) {
let work = [{at: from, route: []}];
for (let i = 0; i < work.length; i++) { let {at, route} = work[i]; for (let place of graph[at]) { if (place == to) return route.concat(place); if (!work.some(w => w.at == place)) {
work.push({at: place, route: route.concat(place)});
}
}

}

}

The exploring has to be done in the right order—the places that were reached first have to be explored first. We can’t immediately explore a place as soon as we reach it because that would mean places reached from there would also be explored immediately, and so on, even though there may be other, shorter paths that haven’t yet been explored. Therefore, the function keeps a work list. This is an array of places that should be explored next, along with the route that got us there. It starts with just the start position and an empty route.

The search then operates by taking the next item in the list and exploring that, which means all roads going from that place are looked at. If one of them is the goal, a finished route can be returned. Otherwise, if we haven’t looked at this place before, a new item is added to the list. If we have looked at it before, since we are looking at short routes first, we’ve found either a longer route to that place or one precisely as long as the existing one, and we don’t need to explore it.

You can visually imagine this as a web of known routes crawling out from the start location, growing evenly on all sides (but never tangling back into itself). As soon as the first thread reaches the goal location, that thread is traced back to the start, giving us our route. Our code doesn’t handle the situation where there are no more work items on the work list because we know that our graph is connected, meaning that every location can be reached from all other locations. We’ll always be able to find a route between two points, and the search can’t fail.

function goalOrientedRobot({place, parcels}, route) {

     if (route.length == 0) {

        let parcel = parcels[0];

        if (parcel.place != place) {

            route = findRoute(roadGraph, place, parcel.place);

      } else {

          route = findRoute(roadGraph, place, parcel.address);

         }

}

    return {direction: route[0], memory: route.slice(1)};

}

This robot uses its memory value as a list of directions to move in, just like the route-following robot. Whenever that list is empty, it has to figure out what to do next. It takes the first undelivered parcel in the set and, if that parcel hasn’t been picked up yet, plots a route toward it. If the parcel has been picked up, it still needs to be delivered, so the robot creates a route toward the delivery address instead. This robot usually finishes the task of delivering 5 parcels in about 16 turns. That’s slightly better than routeRobot but still definitely not optimal.

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.