¶ When personal computers were first introduced, most of them came equipped with a simple programming language, usually a variant of BASIC. Interacting with the computer was closely integrated with this language, and thus every computer-user, whether he wanted to or not, would get a taste of it. Now that computers have become plentiful and cheap, typical users don't get much further than clicking things with a mouse. For most people, this works very well. But for those of us with a natural inclination towards technological tinkering, the removal of programming from every-day computer use presents something of a barrier.

¶ Fortunately, as an effect of developments in the World Wide Web, it so happens that every computer equipped with a modern web-browser also has an environment for programming JavaScript. In today's spirit of not bothering the user with technical details, it is kept well hidden, but a web-page can make it accessible, and use it as a platform for learning to program.

¶ That is what this (hyper-)book tries to do.

I do not enlighten those who are not eager to learn, nor arouse those who are not anxious to give an explanation themselves. If I have presented one corner of the square and they cannot come back to me with the other three, I should not go over the points again.

― Confucius

¶ Besides explaining JavaScript, this book tries to be an introduction to the basic principles of programming. Programming, it turns out, is hard. The fundamental rules are, most of the time, simple and clear. But programs, while built on top of these basic rules, tend to become complex enough to introduce their own rules, their own complexity. Because of this, programming is rarely simple or predictable. As Donald Knuth, who is something of a founding father of the field, says, it is an art.

¶ To get something out of this book, more than just passive reading is required. Try to stay sharp, make an effort to solve the exercises, and only continue on when you are reasonably sure you understand the material that came before.

The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs.

― Joseph Weizenbaum, Computer Power and Human Reason

¶ A program is many things. It is a piece of text typed by a programmer, it is the directing force that makes the computer do what it does, it is data in the computer's memory, yet it controls the actions performed on this same memory. Analogies that try to compare programs to objects we are familiar with tend to fall short, but a superficially fitting one is that of a machine. The gears of a mechanical watch fit together ingeniously, and if the watchmaker was any good, it will accurately show the time for many years. The elements of a program fit together in a similar way, and if the programmer knows what he is doing, the program will run without crashing.

¶ A computer is a machine built to act as a host for these immaterial machines. Computers themselves can only do stupidly straightforward things. The reason they are so useful is that they do these things at an incredibly high speed. A program can, by ingeniously combining many of these simple actions, do very complicated things.

¶ To some of us, writing computer programs is a fascinating game. A program is a building of thought. It is costless to build, weightless, growing easily under our typing hands. If we get carried away, its size and complexity will grow out of control, confusing even the one who created it. This is the main problem of programming. It is why so much of today's software tends to crash, fail, screw up.

¶ When a program works, it is beautiful. The art of programming is the skill of controlling complexity. The great program is subdued, made simple in its complexity.

¶ Today, many programmers believe that this complexity is best managed by using only a small set of well-understood techniques in their programs. They have composed strict rules about the form programs should have, and the more zealous among them will denounce those who break these rules as bad programmers.

¶ What hostility to the richness of programming! To try to reduce it to something straightforward and predictable, to place a taboo on all the weird and beautiful programs. The landscape of programming techniques is enormous, fascinating in its diversity, still largely unexplored. It is certainly littered with traps and snares, luring the inexperienced programmer into all kinds of horrible mistakes, but that only means you should proceed with caution, keep your wits about you. As you learn, there will always be new challenges, new territory to explore. The programmer who refuses to keep exploring will surely stagnate, forget his joy, lose the will to program (and become a manager).

¶ As far as I am concerned, the definite criterion for a program is whether it is correct. Efficiency, clarity, and size are also important, but how to balance these against each other is always a matter of judgement, a judgement that each programmer must make for himself. Rules of thumb are useful, but one should never be afraid to break them.

¶ In the beginning, at the birth of computing, there were no programming languages. Programs looked something like this:

00110001 00000000 00000000
00110001 00000001 00000001
00110011 00000001 00000010
01010001 00001011 00000010
00100010 00000010 00001000
01000011 00000001 00000000
01000001 00000001 00000001
00010000 00000010 00000000
01100010 00000000 00000000

¶ That is a program to add the numbers from one to ten together, and print out the result (1 + 2 + ... + 10 = 55). It could run on a very simple kind of computer. To program early computers, it was necessary to set large arrays of switches in the right position, or punch holes in strips of cardboard and feed them to the computer. You can imagine how this was a tedious, error-prone procedure. Even the writing of simple programs required much cleverness and discipline, complex ones were nearly inconceivable.

¶ Of course, manually entering these arcane patterns of bits (which is what the 1s and 0s above are generally called) did give the programmer a profound sense of being a mighty wizard. And that has to be worth something, in terms of job satisfaction.

¶ Each line of the program contains a single instruction. It could be written in English like this:

1. Store the number 0 in memory location 0
2. Store the number 1 in memory location 1
3. Store the value of memory location 1 in memory location 2
4. Decrement the value in memory location 2 by the number 11
5. If the value in memory location 2 is the number 0, continue with instruction 9
6. Increment the value in memory location 0 by the value in memory location 1
7. Increment the value in memory location 1 by the number 1
8. Continue with instruction 3
9. Output the value of memory location 0

¶ While that is more readable than the binary soup, it is still rather unpleasant. It might help to use names instead of numbers for the instructions and memory locations:

 Set 'total' to 0
 Set 'count' to 1
[loop]
 Set 'compare' to 'count'
 Subtract 11 from 'compare'
 If 'compare' is zero, continue at [end]
 Add 'count' to 'total'
 Add 1 to 'count'
 Continue at [loop]
[end]
 Output 'total'

¶ At this point it is not too hard to see how the program works. Can you? The first two lines give two memory locations their starting values: total will be used to build up the result of the program, and count keeps track of the number that we are currently looking at. The lines using compare are probably the weirdest ones. What the program wants to do is see if count is equal to 11, in order to decide whether it can stop yet. Because the machine is so primitive, it can only test whether a number is zero, and make a decision (jump) based on that. So it uses the memory location labelled compare to compute the value of count - 11, and makes a decision based on that value. The next two lines add the value of count to the result, and increment count by one every time the program has decided that it is not 11 yet.

¶ Here is the same program in JavaScript:

var total = 0, count = 1;
while (count <= 10) {
  total += count;
  count += 1;
}
print(total);

¶ This gives us a few more improvements. Most importantly, there is no need to specify the way we want the program to jump back and forth anymore. The magic word while takes care of that. It continues executing the lines below it as long as the condition it was given holds: count <= 10, which means 'count is less than or equal to 10'. Apparently, there is no need anymore to create a temporary value and compare that to zero. This was a stupid little detail, and the power of programming languages is that they take care of stupid little details for us.

¶ Finally, here is what the program could look like if we happened to have the convenient operations range and sum available, which respectively create a collection of numbers within a range and compute the sum of a collection of numbers:

print(sum(range(1, 10)));

¶ The moral of this story, then, is that the same program can be expressed in long and short, unreadable and readable ways. The first version of the program was extremely obscure, while this last one is almost English: print the sum of the range of numbers from 1 to 10. (We will see in later chapters how to build things like sum and range.)

¶ A good programming language helps the programmer by providing a more abstract way to express himself. It hides uninteresting details, provides convenient building blocks (such as the while construct), and, most of the time, allows the programmer to add building blocks himself (such as the sum and range operations).

¶ JavaScript is the language that is, at the moment, mostly being used to do all kinds of clever and horrible things with pages on the World Wide Web. Some people claim that the next version of JavaScript will become an important language for other tasks too. I am unsure whether that will happen, but if you are interested in programming, JavaScript is definitely a useful language to learn. Even if you do not end up doing much web programming, the mind-bending programs I will show you in this book will always stay with you, haunt you, and influence the programs you write in other languages.

¶ There are those who will say terrible things about JavaScript. Many of these things are true. When I was for the first time required to write something in JavaScript, I quickly came to despise the language. It would accept almost anything I typed, but interpret it in a way that was completely different from what I meant. This had a lot to do with the fact that I did not have a clue what I was doing, but there is also a real issue here: JavaScript is ridiculously liberal in what it allows. The idea behind this design was that it would make programming in JavaScript easier for beginners. In actuality, it mostly makes finding problems in your programs harder, because the system will not point them out to you.

¶ However, the flexibility of the language is also an advantage. It leaves space for a lot of techniques that are impossible in more rigid languages, and it can be used to overcome some of JavaScript's shortcomings. After learning it properly, and working with it for a while, I have really learned to like this language.

¶ Contrary to what the name suggests, JavaScript has very little to do with the programming language named Java. The similar name was inspired by marketing considerations, rather than good judgement. In 1995, when JavaScript was introduced by Netscape, the Java language was being heavily marketed and gaining in popularity. Apparently, someone thought it a good idea to try and ride along on this marketing. Now we are stuck with the name.

¶ Related to JavaScript is a thing called ECMAScript. When browsers other than Netscape started to support JavaScript, or something that looked like it, a document was written to describe precisely how the language should work. The language described in this document is called ECMAScript, after the organisation that standardised it.

¶ ECMAScript describes a general-purpose programming language, and does not say anything about the integration of this language in an Internet browser. JavaScript is ECMAScript plus extra tools for dealing with Internet pages and browser windows.

¶ A few other pieces of software use the language described in the ECMAScript document. Most importantly, the ActionScript language used by Flash is based on ECMAScript (though it does not precisely follow the standard). Flash is a system for adding things that move and make lots of noise to web-pages. Knowing JavaScript won't hurt if you ever find yourself learning to build Flash movies.

¶ JavaScript is still evolving. Since this book came out, ECMAScript 5 has been released, which is compatible with the version described here, but adds some of the functionality we will be writing ourselves as built-in methods. The newest generation of browsers provides this expanded version of JavaScript. As of 2011, 'ECMAScript harmony', a more radical extension of the language, is in the process of being standardised. You should not worry too much about these new versions making the things you learn from this book obsolete. For one thing, they will be an extension of the language we have now, so almost everything written in this book will still hold.

¶ Most chapters in this book contain quite a lot of code1. In my experience, reading and writing code is an important part of learning to program. Try to not just glance over these examples, but read them attentively and understand them. This can be slow and confusing at first, but you will quickly get the hang of it. The same goes for the exercises. Don't assume you understand them until you've actually written a working solution.

¶ Because of the way the web works, it is always possible to look at the JavaScript programs that people put in their web-pages. This can be a good way to learn how some things are done. Because most web programmers are not 'professional' programmers, or consider JavaScript programming so uninteresting that they never properly learned it, a lot of the code you can find like this is of a very bad quality. When learning from ugly or incorrect code, the ugliness and confusion will propagate into your own code, so be careful who you learn from.

¶ To allow you to try out programs, both the examples and the code you write yourself, this book makes use of something called a console. If you are using a modern graphical browser (Internet Explorer version 6 or higher, Firefox 1.5 or higher, Opera 9 or higher, Safari 3 or higher, Chrome), the pages in this book will show a blueish bar at the bottom of your screen. You can open the console by clicking on the little arrow on the far right of this bar. (Note that I am not talking about your browser's built-in console.)

¶ The console contains three important elements. There is the output window, which is used to show error messages and things that programs print out. Below that, there is a line where you can type in a piece of JavaScript. Try typing in a number, and pressing the enter key to run what you typed. If the text you typed produced something meaningful, it will be shown in the output window. Now try typing wrong!, and press enter again. The output window will show an error message. You can use the arrow-up and arrow-down keys to go back to previous commands that you typed.

¶ For bigger pieces of code, those that span multiple lines and which you want to keep around for a while, the field on the right can be used. The 'Run' button is used to execute programs written in this field. It is possible to have multiple programs open at the same time. Use the 'New' button to open a new, empty buffer. When there is more than one open buffer, the menu next to the 'Run' button can be used to choose which one is being shown. The 'Close' button, as you might expect, closes a buffer.

¶ Example programs in this book always have a small button with an arrow in their top-right corner, which can be used to run them. The example we saw earlier looked like this:

var total = 0, count = 1;
while (count <= 10) {
  total += count;
  count += 1;
}
print(total);

¶ Run it by clicking the arrow. There is also another button, which is used to load the program into the console. Do not hesitate to modify it and try out the result. The worst that could happen is that you create an endless loop. An endless loop is what you get when the condition of the while never becomes false, for example if you choose to add 0 instead of 1 to the count variable. Now the program will run forever.

¶ Fortunately, browsers keep an eye on the programs running inside them. Whenever one of them is taking suspiciously long to finish, they will ask you if you want to cut it off.

¶ In some later chapters, we will build example programs that consist of many blocks of code. Often, you have to run every one of them for the program to work. As you may have noticed, the arrow in a block of code turns purple after the block has been run. When reading a chapter, try to run every block of code you come across, especially those that 'define' something new (you will see what that means in the next chapter).

¶ It is, of course, possible that you can not read a chapter in one sitting. This means you will have to start halfway when you continue reading, but if you don't run all the code starting from the top of the chapter, some things might not work. By holding the shift key while pressing the 'run' arrow on a block of code, all blocks before that one will be run as well, so when you start in the middle of a chapter, hold shift the first time you run a piece of code, and everything should work as expected.

¶ Inside the computer's world, there is only data. That which is not data, does not exist. Although all data is in essence just a sequence of bits1, and is thus fundamentally alike, every piece of data plays its own role. In JavaScript's system, most of this data is neatly separated into things called values. Every value has a type, which determines the kind of role it can play. There are six basic types of values: Numbers, strings, booleans, objects, functions, and undefined values.

¶ To create a value, one must merely invoke its name. This is very convenient. You don't have to gather building material for your values, or pay for them, you just call for one and woosh, you have it. They are not created from thin air, of course. Every value has to be stored somewhere, and if you want to use a gigantic number of them at the same time you might run out of computer memory. Fortunately, this is only a problem if you need them all simultaneously. As soon as you no longer use a value, it will dissipate, leaving behind only a few bits. These bits are recycled to make the next generation of values.

¶ Values of the type number are, as you might have deduced, numeric values. They are written the way numbers are usually written:

144

¶ Enter that in the console, and the same thing is printed in the output window. The text you typed in gave rise to a number value, and the console took this number and wrote it out to the screen again. In a case like this, that was a rather pointless exercise, but soon we will be producing values in less straightforward ways, and it can be useful to 'try them out' on the console to see what they produce.

¶ This is what 144 looks like in bits2:

0100000001100010000000000000000000000000000000000000000000000000

¶ The number above has 64 bits. Numbers in JavaScript always do. This has one important repercussion: There is a limited amount of different numbers that can be expressed. With three decimal digits, only the numbers 0 to 999 can be written, which is 10³ = 1000 different numbers. With 64 binary digits, 2⁶⁴ different numbers can be written. This is a lot, more than 10¹⁹ (a one with nineteen zeroes).

¶ Not all whole numbers below 10¹⁹ fit in a JavaScript number though. For one, there are also negative numbers, so one of the bits has to be used to store the sign of the number. A bigger issue is that non-whole numbers must also be represented. To do this, 11 bits are used to store the position of the fractional dot within the number.

¶ That leaves 52 bits3. Any whole number less than 2⁵² (which is more than 10¹⁵) will safely fit in a JavaScript number. In most cases, the numbers we are using stay well below that, so we do not have to concern ourselves with bits at all. Which is good. I have nothing in particular against bits, but you do need a terrible lot of them to get anything done. When at all possible, it is more pleasant to deal with bigger things.

¶ Fractional numbers are written by using a dot.

9.81

¶ For very big or very small numbers, one can also use 'scientific' notation by adding an e, followed by the exponent of the number:

2.998e8

¶ Which is 2.998 * 10⁸ = 299800000.

¶ Calculations with whole numbers (also called integers) that fit in 52 bits are guaranteed to always be precise. Unfortunately, calculations with fractional numbers are generally not. The same way that π (pi) can not be precisely expressed by a finite amount of decimal digits, many numbers lose some precision when only 64 bits are available to store them. This is a shame, but it only causes practical problems in very specific situations. The important thing is to be aware of it, and treat fractional digital numbers as approximations, not as precise values.

¶ The main thing to do with numbers is arithmetic. Arithmetic operations such as addition or multiplication take two number values and produce a new number from them. Here is what they look like in JavaScript:

100 + 4 * 11

¶ The + and * symbols are called operators. The first stands for addition, and the second for multiplication. Putting an operator between two values will apply it to those values, and produce a new value.

¶ Does the example mean 'add 4 and 100, and multiply the result by 11', or is the multiplication done before the adding? As you might have guessed, the multiplication happens first. But, as in mathematics, this can be changed by wrapping the addition in parentheses:

(100 + 4) * 11

¶ For subtraction, there is the - operator, and division can be done with /. When operators appear together without parentheses, the order in which they are applied is determined by the precedence of the operators. The first example shows that multiplication has a higher precedence than addition. Division and multiplication always come before subtraction and addition. When multiple operators with the same precedence appear next to each other (1 - 1 + 1) they are applied left-to-right.

¶ Try to figure out what value this produces, and then run it to see if you were correct...

115 * 4 - 4 + 88 / 2

¶ These rules of precedence are not something you should worry about. When in doubt, just add parentheses.

¶ There is one more arithmetic operator which is probably less familiar to you. The % symbol is used to represent the remainder operation. X % Y is the remainder of dividing X by Y. For example 314 % 100 is 14, 10 % 3 is 1, and 144 % 12 is 0. Remainder has the same precedence as multiplication and division.

¶ The next data type is the string. Its use is not as evident from its name as with numbers, but it also fulfills a very basic role. Strings are used to represent text, the name supposedly derives from the fact that it strings together a bunch of characters. Strings are written by enclosing their content in quotes:

"Patch my boat with chewing gum."

¶ Almost anything can be put between double quotes, and JavaScript will make a string value out of it. But a few characters are tricky. You can imagine how putting quotes between quotes might be hard. Newlines, the things you get when you press enter, can also not be put between quotes, the string has to stay on a single line.

¶ To be able to have such characters in a string, the following trick is used: Whenever a backslash ('\') is found inside quoted text, it indicates that the character after it has a special meaning. A quote that is preceded by a backslash will not end the string, but be part of it. When an 'n' character occurs after a backslash, it is interpreted as a newline. Similarly, a 't' after a backslash means a tab character4.

"This is the first line\nAnd this is the second"

¶ Note that if you type this into the console, it'll display it back in 'source' form, with the quotes and backslash escapes. To see only the actual text, you can type print("a\nb"). What that does precisely will be clarified a little further on.

¶ There are of course situations where you want a backslash in a string to be just a backslash, not a special code. If two backslashes follow each other, they will collapse right into each other, and only one will be left in the resulting string value:

"A newline character is written like \"\\n\"."

¶ Strings can not be divided, multiplied, or subtracted. The + operator can be used on them. It does not add, but it concatenates, it glues two strings together.

"con" + "cat" + "e" + "nate"

¶ There are more ways of manipulating strings, but these are discussed later.

¶ Not all operators are symbols, some are written as words. For example, the typeof operator, which produces a string value naming the type of the value you give it.

typeof 4.5

¶ The other operators we saw all operated on two values, typeof takes only one. Operators that use two values are called binary operators, while those that take one are called unary operators. The minus operator can be used both as a binary and a unary operator:

- (10 - 2)

¶ Then there are values of the boolean type. There are only two of these: true and false. Here is one way to produce a true value:

3 > 2

¶ And false can be produced like this:

3 < 2

¶ I hope you have seen the > and < signs before. They mean, respectively, 'is greater than' and 'is less than'. They are binary operators, and the result of applying them is a boolean value that indicates whether they hold in this case.

¶ Strings can be compared in the same way:

"Aardvark" < "Zoroaster"

¶ The way strings are ordered is more or less alphabetic. More or less... Uppercase letters are always 'less' than lowercase ones, so "Z" < "a" (upper-case Z, lower-case a) is true, and non-alphabetic characters ('!', '@', etc) are also included in the ordering. The actual way in which the comparison is done is based on the Unicode standard. This standard assigns a number to virtually every character one would ever need, including characters from Greek, Arabic, Japanese, Tamil, and so on. Having such numbers is practical for storing strings inside a computer ― you can represent them as a list of numbers. When comparing strings, JavaScript just compares the numbers of the characters inside the string, from left to right.

¶ Other similar operators are >= ('is greater than or equal to'), <= (is less than or equal to), == ('is equal to'), and != ('is not equal to').

"Itchy" != "Scratchy"

5e2 == 500

¶ There are also some useful operations that can be applied to boolean values themselves. JavaScript supports three logical operators: and, or, and not. These can be used to 'reason' about booleans.

¶ The && operator represents logical and. It is a binary operator, and its result is only true if both of the values given to it are true.

true && false

¶ || is the logical or, it is true if either of the values given to it is true:

true || false

¶ Not is written as an exclamation mark, !, it is a unary operator that flips the value given to it, !true is false, and !false is true.

¶ It is not always obvious when parentheses are needed. In practice, one can usually get by with knowing that of the operators we have seen so far, || has the lowest precedence, then comes &&, then the comparison operators (>, ==, etcetera), and then the rest. This has been chosen in such a way that, in simple cases, as few parentheses as possible are necessary.

¶ All the examples so far have used the language like you would use a pocket calculator. Make some values and apply operators to them to get new values. Creating values like this is an essential part of every JavaScript program, but it is only a part. A piece of code that produces a value is called an expression. Every value that is written directly (such as 22 or "psychoanalysis") is an expression. An expression between parentheses is also an expression. And a binary operator applied to two expressions, or a unary operator applied to one, is also an expression.

¶ There are a few more ways of building expressions, which will be revealed when the time is ripe.

¶ There exists a unit that is bigger than an expression. It is called a statement. A program is built as a list of statements. Most statements end with a semicolon (;). The simplest kind of statement is an expression with a semicolon after it. This is a program:

1;
!false;

¶ It is a useless program. An expression can be content to just produce a value, but a statement only amounts to something if it somehow changes the world. It could print something to the screen ― that counts as changing the world ― or it could change the internal state of the program in a way that will affect the statements that come after it. These changes are called 'side effects'. The statements in the example above just produce the values 1 and true, and then immediately throw them into the bit bucket5. This leaves no impression on the world at all, and is not a side effect.

¶ How does a program keep an internal state? How does it remember things? We have seen how to produce new values from old values, but this does not change the old values, and the new value has to be immediately used or it will dissipate again. To catch and hold values, JavaScript provides a thing called a variable.

var caught = 5 * 5;

¶ A variable always has a name, and it can point at a value, holding on to it. The statement above creates a variable called caught and uses it to grab hold of the number that is produced by multiplying 5 by 5.

¶ After running the above program, you can type the word caught into the console, and it will retrieve the value 25 for you. The name of a variable is used to fetch its value. caught + 1 also works. A variable name can be used as an expression, and thus can be part of bigger expressions.

¶ The word var is used to create a new variable. After var, the name of the variable follows. Variable names can be almost every word, but they may not include spaces. Digits can be part of variable names, catch22 is a valid name, but the name must not start with a digit. The characters '$' and '_' can be used in names as if they were letters, so $_$ is a correct variable name.

¶ If you want the new variable to immediately capture a value, which is often the case, the = operator can be used to give it the value of some expression.

¶ When a variable points at a value, that does not mean it is tied to that value forever. At any time, the = operator can be used on existing variables to yank them away from their current value and make them point to a new one.

caught = 4 * 4;

¶ You should imagine variables as tentacles, rather than boxes. They do not contain values, they grasp them ― two variables can refer to the same value. Only the values that the program still has a hold on can be accessed by it. When you need to remember something, you grow a tentacle to hold on to it, or re-attach one of your existing tentacles to a new value: To remember the amount of dollars that Luigi still owes you, you could do...

var luigiDebt = 140;

¶ Then, every time Luigi pays something back, this amount can be decremented by giving the variable a new number:

luigiDebt = luigiDebt - 35;

¶ The collection of variables and their values that exist at a given time is called the environment. When a program starts up, this environment is not empty. It always contains a number of standard variables. When your browser loads a page, it creates a new environment and attaches these standard values to it. The variables created and modified by programs on that page survive until the browser goes to a new page.

¶ A lot of the values provided by the standard environment have the type 'function'. A function is a piece of program wrapped in a value. Generally, this piece of program does something useful, which can be invoked using the function value that contains it. In a browser environment, the variable alert holds a function that shows a little dialog window with a message. It is used like this:

alert("Avocados");

¶ Executing the code in a function is called invoking, calling, or applying it. The notation for doing this uses parentheses. Every expression that produces a function value can be invoked by putting parentheses after it. In the example, the value "Avocados" is given to the function, which uses it as the text to show in the dialog window. Values given to functions are called parameters or arguments. alert needs only one of them, but other functions might need a different number.

¶ Showing a dialog window is a side effect. A lot of functions are useful because of the side effects they produce. It is also possible for a function to produce a value, in which case it does not need to have a side effect to be useful. For example, there is a function Math.max, which takes any number of numeric arguments and gives back the greatest:

alert(Math.max(2, 4));

¶ When a function produces a value, it is said to return it. Because things that produce values are always expressions in JavaScript, function calls can be used as a part of bigger expressions:

alert(Math.min(2, 4) + 100);

¶ Chapter 3 discusses writing your own functions.

¶ As the previous examples show, alert can be useful for showing the result of some expression. Clicking away all those little windows can get on one's nerves though, so from now on we will prefer to use a similar function, called print, which does not pop up a window, but just writes a value to the output area of the console. print is not a standard JavaScript function, browsers do not provide it for you, but it is made available by this book, so you can use it on these pages.

print("N");

¶ A similar function, also provided on these pages, is show. While print will display its argument as flat text, show tries to display it the way it would look in a program, which can give more information about the type of the value. For example, string values keep their quotes when given to show:

show("N");

¶ The standard environment provided by browsers contains a few more functions for popping up windows. You can ask the user an OK/Cancel question using confirm. This returns a boolean, true if the user presses 'OK', and false if he presses 'Cancel'.

show(confirm("Shall we, then?"));

¶ prompt can be used to ask an 'open' question. The first argument is the question, the second one is the text that the user starts with. A line of text can be typed into the window, and the function will return this as a string.

show(prompt("Tell us everything you know.", "..."));

¶ It is possible to give almost every variable in the environment a new value. This can be useful, but also dangerous. If you give print the value 8, you won't be able to print things anymore. Fortunately, there is a big 'Reset' button on the console, which will reset the environment to its original state.

¶ One-line programs are not very interesting. When you put more than one statement into a program, the statements are, predictably, executed one at a time, from top to bottom.

var theNumber = Number(prompt("Pick a number", ""));
print("Your number is the square root of " +
      (theNumber * theNumber));

¶ The function Number converts a value to a number, which is needed in this case because the result of prompt is a string value. There are similar functions called String and Boolean which convert values to those types.

¶ Consider a program that prints out all even numbers from 0 to 12. One way to write this is:

print(0);
print(2);
print(4);
print(6);
print(8);
print(10);
print(12);

¶ That works, but the idea of writing a program is to make something less work, not more. If we needed all even numbers below 1000, the above would be unworkable. What we need is a way to automatically repeat some code.

var currentNumber = 0;
while (currentNumber <= 12) {
  print(currentNumber);
  currentNumber = currentNumber + 2;
}

¶ You may have seen while in the introduction chapter. A statement starting with the word while creates a loop. A loop is a disturbance in the sequence of statements ― it may cause the program to repeat some statements multiple times. In this case, the word while is followed by an expression in parentheses (the parentheses are compulsory here), which is used to determine whether the loop will loop or finish. As long as the boolean value produced by this expression is true, the code in the loop is repeated. As soon as it is false, the program goes to the bottom of the loop and continues as normal.

¶ The variable currentNumber demonstrates the way a variable can track the progress of a program. Every time the loop repeats, it is incremented by 2, and at the beginning of every repetition, it is compared with the number 12 to decide whether to keep on looping.

¶ The third part of a while statement is another statement. This is the body of the loop, the action or actions that must take place multiple times. If we did not have to print the numbers, the program could have been:

var currentNumber = 0;
while (currentNumber <= 12)
  currentNumber = currentNumber + 2;

¶ Here, currentNumber = currentNumber + 2; is the statement that forms the body of the loop. We must also print the number, though, so the loop statement must consist of more than one statement. Braces ({ and }) are used to group statements into blocks. To the world outside the block, a block counts as a single statement. In the earlier example, this is used to include in the loop both the call to print and the statement that updates currentNumber.

¶ You will have noticed the spaces I put in front of some statements. These are not required: The computer will accept the program just fine without them. In fact, even the line breaks in programs are optional. You could write them as a single long line if you felt like it. The role of the indentation inside blocks is to make the structure of the code clearer to a reader. Because new blocks can be opened inside other blocks, it can become hard to see where one block ends and another begins in a complex piece of code. When lines are indented, the visual shape of a program corresponds to the shape of the blocks inside it. I like to use two spaces for every open block, but tastes differ.

¶ The field in the console where you can type programs will help you by automatically adding these spaces. This may seem annoying at first, but when you write a lot of code it becomes a huge time-saver. Pressing shift+tab will re-indent the line your cursor is currently on.

¶ In some cases, JavaScript allows you to omit the semicolon at the end of a statement. In other cases, it has to be there or strange things will happen. The rules for when it can be safely omitted are complex and weird. In this book, I won't leave out any semicolons, and I strongly urge you to do the same in your own programs.

¶ The uses of while we have seen so far all show the same pattern. First, a 'counter' variable is created. This variable tracks the progress of the loop. The while itself contains a check, usually to see whether the counter has reached some boundary yet. Then, at the end of the loop body, the counter is updated.

¶ A lot of loops fall into this pattern. For this reason, JavaScript, and similar languages, also provide a slightly shorter and more comprehensive form:

for (var number = 0; number <= 12; number = number + 2)
  show(number);

¶ This program is exactly equivalent to the earlier even-number-printing example. The only change is that all the statements that are related to the 'state' of the loop are now on one line. The parentheses after the for should contain two semicolons. The part before the first semicolon initialises the loop, usually by defining a variable. The second part is the expression that checks whether the loop must still continue. The final part updates the state of the loop. In most cases this is shorter and clearer than a while construction.

¶ I have been using some rather odd capitalisation in some variable names. Because you can not have spaces in these names ― the computer would read them as two separate variables ― your choices for a name that is made of several words are more or less limited to the following: fuzzylittleturtle, fuzzy_little_turtle, FuzzyLittleTurtle, or fuzzyLittleTurtle. The first one is hard to read. Personally, I like the one with the underscores, though it is a little painful to type. However, the standard JavaScript functions, and most JavaScript programmers, follow the last one. It is not hard to get used to little things like that, so I will just follow the crowd and capitalise the first letter of every word after the first.

¶ In a few cases, such as the Number function, the first letter of a variable is also capitalised. This was done to mark this function as a constructor. What a constructor is will become clear in chapter 8. For now, the important thing is not to be bothered by this apparent lack of consistency.

¶ Note that names that have a special meaning, such as var, while, and for may not be used as variable names. These are called keywords. There are also a number of words which are 'reserved for use' in future versions of JavaScript. These are also officially not allowed to be used as variable names, though some browsers do allow them. The full list is rather long:

abstract boolean break byte case catch char class const continue
debugger default delete do double else enum export extends false
final finally float for function goto if implements import in
instanceof int interface long native new null package private
protected public return short static super switch synchronized
this throw throws transient true try typeof var void volatile
while with

¶ Don't worry about memorising these for now, but remember that this might be the problem when something does not work as expected. In my experience, char (to store a one-character string) and class are the most common names to accidentally use.

¶ A program often needs to 'update' a variable with a value that is based on its previous value. For example counter = counter + 1. JavaScript provides a shortcut for this: counter += 1. This also works for many other operators, for example result *= 2 to double the value of result, or counter -= 1 to count downwards.

¶ For counter += 1 and counter -= 1 there are even shorter versions: counter++ and counter--.

¶ Loops are said to affect the control flow of a program. They change the order in which statements are executed. In many cases, another kind of flow is useful: skipping statements.

¶ We want to show all numbers below 20 which are divisible both by 3 and by 4.

for (var counter = 0; counter < 20; counter++) {
  if (counter % 3 == 0 && counter % 4 == 0)
    show(counter);
}

¶ The keyword if is not too different from the keyword while: It checks the condition it is given (between parentheses), and executes the statement after it based on this condition. But it does this only once, so that the statement is executed zero or one time.

¶ The trick with the remainder (%) operator is an easy way to test whether a number is divisible by another number. If it is, the remainder of their division, which is what remainder gives you, is zero.

¶ If we wanted to print all numbers below 20, but put parentheses around the ones that are not divisible by 4, we can do it like this:

for (var counter = 0; counter < 20; counter++) {
  if (counter % 4 == 0)
    print(counter);
  if (counter % 4 != 0)
    print("(" + counter + ")");
}

¶ But now the program has to determine whether counter is divisible by 4 two times. The same effect can be obtained by appending an else part after an if statement. The else statement is executed only when the if's condition is false.

for (var counter = 0; counter < 20; counter++) {
  if (counter % 4 == 0)
    print(counter);
  else
    print("(" + counter + ")");
}

¶ To stretch this trivial example a bit further, we now want to print these same numbers, but add two stars after them when they are greater than 15, one star when they are greater than 10 (but not greater than 15), and no stars otherwise.

for (var counter = 0; counter < 20; counter++) {
  if (counter > 15)
    print(counter + "**");
  else if (counter > 10)
    print(counter + "*");
  else
    print(counter);
}

¶ This demonstrates that you can chain if statements together. In this case, the program first looks if counter is greater than 15. If it is, the two stars are printed and the other tests are skipped. If it is not, we continue to check if counter is greater than 10. Only if counter is also not greater than 10 does it arrive at the last print statement.

¶ When a loop does not always have to go all the way through to its end, the break keyword can be useful. It immediately jumps out of the current loop, continuing after it. This program finds the first number that is greater than or equal to 20 and divisible by 7:

for (var current = 20; ; current++) {
  if (current % 7 == 0)
    break;
}
print(current);

¶ The for construct shown above does not have a part that checks for the end of the loop. This means that it is dependent on the break statement inside it to ever stop. The same program could also have been written as simply...

for (var current = 20; current % 7 != 0; current++)
  ;
print(current);

¶ In this case, the body of the loop is empty. A lone semicolon can be used to produce an empty statement. Here, the only effect of the loop is to increment the variable current to its desired value. But I needed an example that uses break, so pay attention to the first version too.

¶ In the solution to the previous exercise there is a statement var answer;. This creates a variable named answer, but does not give it a value. What happens when you take the value of this variable?

var mysteryVariable;
show(mysteryVariable);

¶ In terms of tentacles, this variable ends in thin air, it has nothing to grasp. When you ask for the value of an empty place, you get a special value named undefined. Functions which do not return an interesting value, such as print and alert, also return an undefined value.

show(alert("I am a side effect."));

¶ There is also a similar value, null, whose meaning is 'this variable is defined, but it does not have a value'. The difference in meaning between undefined and null is mostly academic, and usually not very interesting. In practical programs, it is often necessary to check whether something 'has a value'. In these cases, the expression something == undefined may be used, because, even though they are not exactly the same value, null == undefined will produce true.

¶ Which brings us to another tricky subject...

show(false == 0);
show("" == 0);
show("5" == 5);

¶ All these give the value true. When comparing values that have different types, JavaScript uses a complicated and confusing set of rules. I am not going to try to explain them precisely, but in most cases it just tries to convert one of the values to the type of the other value. However, when null or undefined occur, it only produces true if both sides are null or undefined.

¶ What if you want to test whether a variable refers to the value false? The rules for converting strings and numbers to boolean values state that 0 and the empty string count as false, while all the other values count as true. Because of this, the expression variable == false is also true when variable refers to 0 or "". For cases like this, where you do not want any automatic type conversions to happen, there are two extra operators: === and !==. The first tests whether a value is precisely equal to the other, and the second tests whether it is not precisely equal.

show(null === undefined);
show(false === 0);
show("" === 0);
show("5" === 5);

¶ All these are false.

¶ Values given as the condition in an if, while, or for statement do not have to be booleans. They will be automatically converted to booleans before they are checked. This means that the number 0, the empty string "", null, undefined, and of course false, will all count as false.

¶ The fact that all other values are converted to true in this case makes it possible to leave out explicit comparisons in many situations. If a variable is known to contain either a string or null, one could check for this very simply...

var maybeNull = null;
// ... mystery code that might put a string into maybeNull ...
if (maybeNull)
  print("maybeNull has a value");

¶ ... except in the case where the mystery code gives maybeNull the value "". An empty string is false, so nothing is printed. Depending on what you are trying to do, this might be wrong. It is often a good idea to add an explicit === null or === false in cases like this to prevent subtle mistakes. The same occurs with number values that might be 0.

¶ The line that talks about 'mystery code' in the previous example might have looked a bit suspicious to you. It is often useful to include extra text in a program. The most common use for this is adding some explanations in human language to a program.

// The variable counter, which is about to be defined, is going
// to start with a value of 0, which is zero.
var counter = 0;
// Now, we are going to loop, hold on to your hat.
while (counter < 100 /* counter is less than one hundred */)
/* Every time we loop, we INCREMENT the value of counter,
   Seriously, we just add one to it. */
  counter++;
// And then, we are done.

¶ This kind of text is called a comment. The rules are like this: '/*' starts a comment that goes on until a '*/' is found. '//' starts another kind of comment, which goes on until the end of the line.

¶ As you can see, even the simplest programs can be made to look big, ugly, and complicated by simply adding a lot of comments to them.

¶ There are some other situations that cause automatic type conversions to happen. If you add a non-string value to a string, the value is automatically converted to a string before it is concatenated. If you multiply a number and a string, JavaScript tries to make a number out of the string.

show("Apollo" + 5);
show(null + "ify");
show("5" * 5);
show("strawberry" * 5);

¶ The last statement prints NaN, which is a special value. It stands for 'not a number', and is of type number (which might sound a little contradictory). In this case, it refers to the fact that a strawberry is not a number. All arithmetic operations on the value NaN result in NaN, which is why multiplying it by 5, as in the example, still gives a NaN value. Also, and this can be disorienting at times, NaN == NaN equals false, checking whether a value is NaN can be done with the isNaN function. NaN is another (the last) value that counts as false when converted to a boolean.

¶ These automatic conversions can be very convenient, but they are also rather weird and error prone. Even though + and * are both arithmetic operators, they behave completely different in the example. In my own code, I use + to combine strings and non-strings a lot, but make it a point not to use * and the other numeric operators on string values. Converting a number to a string is always possible and straightforward, but converting a string to a number may not even work (as in the last line of the example). We can use Number to explicitly convert the string to a number, making it clear that we might run the risk of getting a NaN value.

show(Number("5") * 5);

¶ When we discussed the boolean operators && and || earlier, I claimed they produced boolean values. This turns out to be a bit of an oversimplification. If you apply them to boolean values, they will indeed return booleans. But they can also be applied to other kinds of values, in which case they will return one of their arguments.

¶ What || really does is this: It looks at the value to the left of it first. If converting this value to a boolean would produce true, it returns this left value, otherwise it returns the one on its right. Check for yourself that this does the correct thing when the arguments are booleans. Why does it work like that? It turns out this is very practical. Consider this example:

var input = prompt("What is your name?", "Kilgore Trout");
print("Well hello " + (input || "dear"));

¶ If the user presses 'Cancel' or closes the prompt dialog in some other way without giving a name, the variable input will hold the value null or "". Both of these would give false when converted to a boolean. The expression input || "dear" can in this case be read as 'the value of the variable input, or else the string "dear"'. It is an easy way to provide a 'fallback' value.

¶ The && operator works similarly, but the other way around. When the value to its left is something that would give false when converted to a boolean, it returns that value, otherwise it returns the value on its right.

¶ Another property of these two operators is that the expression to their right is only evaluated when necessary. In the case of true || X, no matter what X is, the result will be true, so X is never evaluated, and if it has side effects they never happen. The same goes for false && X.

false || alert("I'm happening!");
true || alert("Not me.");

¶ A program often needs to do the same thing in different places. Repeating all the necessary statements every time is tedious and error-prone. It would be better to put them in one place, and have the program take a detour through there whenever necessary. This is what functions were invented for: They are canned code that a program can go through whenever it wants. Putting a string on the screen requires quite a few statements, but when we have a print function we can just write print("Aleph") and be done with it.

¶ To view functions merely as canned chunks of code doesn't do them justice though. When needed, they can play the role of pure functions, algorithms, indirections, abstractions, decisions, modules, continuations, data structures, and more. Being able to effectively use functions is a necessary skill for any kind of serious programming. This chapter provides an introduction into the subject, chapter 6 discusses the subtleties of functions in more depth.

¶ Pure functions, for a start, are the things that were called functions in the mathematics classes that I hope you have been subjected to at some point in your life. Taking the cosine or the absolute value of a number is a pure function of one argument. Addition is a pure function of two arguments.

¶ The defining properties of pure functions are that they always return the same value when given the same arguments, and never have side effects. They take some arguments, return a value based on these arguments, and do not monkey around with anything else.

¶ In JavaScript, addition is an operator, but it could be wrapped in a function like this (and as pointless as this looks, we will come across situations where it is actually useful):

function add(a, b) {
  return a + b;
}

show(add(2, 2));

¶ add is the name of the function. a and b are the names of the two arguments. return a + b; is the body of the function.

¶ The keyword function is always used when creating a new function. When it is followed by a variable name, the resulting function will be stored under this name. After the name comes a list of argument names, and then finally the body of the function. Unlike those around the body of while loops or if statements, the braces around a function body are obligatory1.

¶ The keyword return, followed by an expression, is used to determine the value the function returns. When control comes across a return statement, it immediately jumps out of the current function and gives the returned value to the code that called the function. A return statement without an expression after it will cause the function to return undefined.

¶ A body can, of course, have more than one statement in it. Here is a function for computing powers (with positive, integer exponents):

function power(base, exponent) {
  var result = 1;
  for (var count = 0; count < exponent; count++)
    result *= base;
  return result;
}

show(power(2, 10));

¶ If you solved exercise 2.2, this technique for computing a power should look familiar.

¶ Creating a variable (result) and updating it are side effects. Didn't I just say pure functions had no side effects?

¶ A variable created inside a function exists only inside the function. This is fortunate, or a programmer would have to come up with a different name for every variable he needs throughout a program. Because result only exists inside power, the changes to it only last until the function returns, and from the perspective of code that calls it there are no side effects.

¶ Pure functions have two very nice properties. They are easy to think about, and they are easy to re-use.

¶ If a function is pure, a call to it can be seen as a thing in itself. When you are not sure that it is working correctly, you can test it by calling it directly from the console, which is simple because it does not depend on any context2. It is easy to make these tests automatic ― to write a program that tests a specific function. Non-pure functions might return different values based on all kinds of factors, and have side effects that might be hard to test and think about.

¶ Because pure functions are self-sufficient, they are likely to be useful and relevant in a wider range of situations than non-pure ones. Take show, for example. This function's usefulness depends on the presence of a special place on the screen for printing output. If that place is not there, the function is useless. We can imagine a related function, let's call it format, that takes a value as an argument and returns a string that represents this value. This function is useful in more situations than show.

¶ Of course, format does not solve the same problem as show, and no pure function is going to be able to solve that problem, because it requires a side effect. In many cases, non-pure functions are precisely what you need. In other cases, a problem can be solved with a pure function but the non-pure variant is much more convenient or efficient.

¶ Thus, when something can easily be expressed as a pure function, write it that way. But never feel dirty for writing non-pure functions.

¶ Functions with side effects do not have to contain a return statement. If no return statement is encountered, the function returns undefined.

function yell(message) {
  alert(message + "!!");
}

yell("Yow");

¶ The names of the arguments of a function are available as variables inside it. They will refer to the values of the arguments the function is being called with, and like normal variables created inside a function, they do not exist outside it. Aside from the top-level environment, there are smaller, local environments created by function calls. When looking up a variable inside a function, the local environment is checked first, and only if the variable does not exist there is it looked up in the top-level environment. This makes it possible for variables inside a function to 'shadow' top-level variables that have the same name.

function alertIsPrint(value) {
  var alert = print;
  alert(value);
}

alertIsPrint("Troglodites");

¶ The variables in this local environment are only visible to the code inside the function. If this function calls another function, the newly called function does not see the variables inside the first function:

var variable = "top-level";

function printVariable() {
  print("inside printVariable, the variable holds '" +
        variable + "'.");
}

function test() {
  var variable = "local";
  print("inside test, the variable holds '" + variable + "'.");
  printVariable();
}

test();

¶ However, and this is a subtle but extremely useful phenomenon, when a function is defined inside another function, its local environment will be based on the local environment that surrounds it instead of the top-level environment.

var variable = "top-level";
function parentFunction() {
  var variable = "local";
  function childFunction() {
    print(variable);
  }
  childFunction();
}
parentFunction();

¶ What this comes down to is that which variables are visible inside a function is determined by the place of that function in the program text. All variables that were defined 'above' a function's definition are visible, which means both those in function bodies that enclose it, and those at the top-level of the program. This approach to variable visibility is called lexical scoping.

¶ People who have experience with other programming languages might expect that a block of code (between braces) also produces a new local environment. Not in JavaScript. Functions are the only things that create a new scope. You are allowed to use free-standing blocks like this...

var something = 1;
{
  var something = 2;
  print("Inside: " + something);
}
print("Outside: " + something);

¶ ... but the something inside the block refers to the same variable as the one outside the block. In fact, although blocks like this are allowed, they are utterly pointless. Most people agree that this is a bit of a design blunder by the designers of JavaScript, and ECMAScript Harmony will add some way to define variables that stay inside blocks (the let keyword).

¶ Here is a case that might surprise you:

var variable = "top-level";
function parentFunction() {
  var variable = "local";
  function childFunction() {
    print(variable);
  }
  return childFunction;
}

var child = parentFunction();
child();

¶ parentFunction returns its internal function, and the code at the bottom calls this function. Even though parentFunction has finished executing at this point, the local environment where variable has the value "local" still exists, and childFunction still uses it. This phenomenon is called closure.

¶ Apart from making it very easy to quickly see in which part of a program a variable will be available by looking at the shape of the program text, lexical scoping also allows us to 'synthesise' functions. By using some of the variables from an enclosing function, an inner function can be made to do different things. Imagine we need a few different but similar functions, one that adds 2 to its argument, one that adds 5, and so on.

function makeAddFunction(amount) {
  function add(number) {
    return number + amount;
  }
  return add;
}

var addTwo = makeAddFunction(2);
var addFive = makeAddFunction(5);
show(addTwo(1) + addFive(1));

¶ To wrap your head around this, you should consider functions to not just package up a computation, but also an environment. Top-level functions simply execute in the top-level environment, that much is obvious. But a function defined inside another function retains access to the environment that existed in that function at the point when it was defined.

¶ Thus, the add function in the above example, which is created when makeAddFunction is called, captures an environment in which amount has a certain value. It packages this environment, together with the computation return number + amount, into a value, which is then returned from the outer function.

¶ When this returned function (addTwo or addFive) is called, a new environment―-in which the variable number has a value―-is created, as a sub-environment of the captured environment (in which amount has a value). These two values are then added, and the result is returned.

¶ On top of the fact that different functions can contain variables of the same name without getting tangled up, these scoping rules also allow functions to call themselves without running into problems. A function that calls itself is called recursive. Recursion allows for some interesting definitions. Look at this implementation of power:

function power(base, exponent) {
  if (exponent == 0)
    return 1;
  else
    return base * power(base, exponent - 1);
}

¶ This is rather close to the way mathematicians define exponentiation, and to me it looks a lot nicer than the earlier version. It sort of loops, but there is no while, for, or even a local side effect to be seen. By calling itself, the function produces the same effect.

¶ There is one important problem though: In most browsers, this second version is about ten times slower than the first one. In JavaScript, running through a simple loop is a lot cheaper than calling a function multiple times.

¶ The dilemma of speed versus elegance is an interesting one. It not only occurs when deciding for or against recursion. In many situations, an elegant, intuitive, and often short solution can be replaced by a more convoluted but faster solution.

¶ In the case of the power function above the un-elegant version is still sufficiently simple and easy to read. It doesn't make very much sense to replace it with the recursive version. Often, though, the concepts a program is dealing with get so complex that giving up some efficiency in order to make the program more straightforward becomes an attractive choice.

¶ The basic rule, which has been repeated by many programmers and with which I wholeheartedly agree, is to not worry about efficiency until your program is provably too slow. When it is, find out which parts are too slow, and start exchanging elegance for efficiency in those parts.

¶ Of course, the above rule doesn't mean one should start ignoring performance altogether. In many cases, like the power function, not much simplicity is gained by the 'elegant' approach. In other cases, an experienced programmer can see right away that a simple approach is never going to be fast enough.

¶ The reason I am making a big deal out of this is that surprisingly many programmers focus fanatically on efficiency, even in the smallest details. The result is bigger, more complicated, and often less correct programs, which take longer to write than their more straightforward equivalents and often run only marginally faster.

¶ But I was talking about recursion. A concept closely related to recursion is a thing called the stack. When a function is called, control is given to the body of that function. When that body returns, the code that called the function is resumed. While the body is running, the computer must remember the context from which the function was called, so that it knows where to continue afterwards. The place where this context is stored is called the stack.

¶ The fact that it is called 'stack' has to do with the fact that, as we saw, a function body can again call a function. Every time a function is called, another context has to be stored. One can visualise this as a stack of contexts. Every time a function is called, the current context is thrown on top of the stack. When a function returns, the context on top is taken off the stack and resumed.

¶ This stack requires space in the computer's memory to be stored. When the stack grows too big, the computer will give up with a message like "out of stack space" or "too much recursion". This is something that has to be kept in mind when writing recursive functions.

function chicken() {
  return egg();
}
function egg() {
  return chicken();
}
print(chicken() + " came first.");

¶ In addition to demonstrating a very interesting way of writing a broken program, this example shows that a function does not have to call itself directly to be recursive. If it calls another function which (directly or indirectly) calls the first function again, it is still recursive.

¶ Recursion is not always just a less-efficient alternative to looping. Some problems are much easier to solve with recursion than with loops. Most often these are problems that require exploring or processing several 'branches', each of which might branch out again into more branches.

¶ Consider this puzzle: By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number?

¶ For example, the number 13 could be reached by first multiplying 1 by 3, and then adding 5 twice. The number 15 can not be reached at all.

¶ Here is the solution:

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

print(findSequence(24));

¶ Note that it doesn't necessarily find the shortest sequence of operations, it is satisfied when it finds any sequence at all.

¶ The inner find function, by calling itself in two different ways, explores both the possibility of adding 5 to the current number and of multiplying it by 3. When it finds the number, it returns the history string, which is used to record all the operators that were performed to get to this number. It also checks whether the current number is bigger than goal, because if it is, we should stop exploring this branch, it is not going to give us our number.

¶ The use of the || operator in the example can be read as 'return the solution found by adding 5 to start, and if that fails, return the solution found by multiplying start by 3'. It could also have been written in a more wordy way like this:

else {
  var found = find(start + 5, "(" + history + " + 5)");
  if (found == null)
    found = find(start * 3, "(" + history + " * 3)");
  return found;
}

¶ Even though function definitions occur as statements between the rest of the program, they are not part of the same time-line:

print("The future says: ", future());

function future() {
  return "We STILL have no flying cars.";
}

¶ What is happening is that the computer looks up all function definitions, and stores the associated functions, before it starts executing the rest of the program. The same happens with functions that are defined inside other functions. When the outer function is called, the first thing that happens is that all inner functions are added to the new environment.

¶ There is another way to define function values, which more closely resembles the way other values are created. When the function keyword is used in a place where an expression is expected, it is treated as an expression producing a function value. Functions created in this way do not have to be given a name (though it is allowed to give them one).

var add = function(a, b) {
  return a + b;
};
show(add(5, 5));

¶ Note the semicolon after the definition of add. Normal function definitions do not need these, but this statement has the same general structure as var add = 22;, and thus requires the semicolon.

¶ This kind of function value is called an anonymous function, because it does not have a name. Sometimes it is useless to give a function a name, like in the makeAddFunction example we saw earlier:

function makeAddFunction(amount) {
  return function (number) {
    return number + amount;
  };
}

¶ Since the function named add in the first version of makeAddFunction was referred to only once, the name does not serve any purpose and we might as well directly return the function value.

¶ Try the following:

alert("Hello", "Good Evening", "How do you do?", "Goodbye");

¶ The function alert officially only accepts one argument. Yet when you call it like this, the computer does not complain at all, but just ignores the other arguments.

show();

¶ You can, apparently, even get away with passing too few arguments. When an argument is not passed, its value inside the function is undefined.

¶ In the next chapter, we will see a way in which a function body can get at the exact list of arguments that were passed to it. This can be useful, as it makes it possible to have a function accept any number of arguments. print makes use of this:

print("R", 2, "D", 2);

¶ Of course, the downside of this is that it is also possible to accidentally pass the wrong number of arguments to functions that expect a fixed amount of them, like alert, and never be told about it.

¶ This chapter will be devoted to solving a few simple problems. In the process, we will discuss two new types of values, arrays and objects, and look at some techniques related to them.

¶ Consider the following situation: Your crazy aunt Emily, who is rumoured to have over fifty cats living with her (you never managed to count them), regularly sends you e-mails to keep you up to date on her exploits. They usually look like this:

Dear nephew,

Your mother told me you have taken up skydiving. Is this true? You watch yourself, young man! Remember what happened to my husband? And that was only from the second floor!

Anyway, things are very exciting here. I have spent all week trying to get the attention of Mr. Drake, the nice gentleman who moved in next door, but I think he is afraid of cats. Or allergic to them? I am going to try putting Fat Igor on his shoulder next time I see him, very curious what will happen.

Also, the scam I told you about is going better than expected. I have already gotten back five 'payments', and only one complaint. It is starting to make me feel a bit bad though. And you are right that it is probably illegal in some way.

(... etc ...)

Much love, Aunt Emily

died 27/04/2006: Black Leclère

born 05/04/2006 (mother Lady Penelope): Red Lion, Doctor Hobbles the 3rd, Little Iroquois

¶ To humour the old dear, you would like to keep track of the genealogy of her cats, so you can add things like "P.S. I hope Doctor Hobbles the 2nd enjoyed his birthday this Saturday!", or "How is old Lady Penelope doing? She's five years old now, isn't she?", preferably without accidentally asking about dead cats. You are in the possession of a large quantity of old e-mails from your aunt, and fortunately she is very consistent in always putting information about the cats' births and deaths at the end of her mails in precisely the same format.

¶ You are hardly inclined to go through all those mails by hand. Fortunately, we were just in need of an example problem, so we will try to work out a program that does the work for us. For a start, we write a program that gives us a list of cats that are still alive after the last e-mail.

¶ Before you ask, at the start of the correspondence, aunt Emily had only a single cat: Spot. (She was still rather conventional in those days.)

¶ It usually pays to have some kind of clue what one's program is going to do before starting to type. Here's a plan:

1. Start with a set of cat names that has only "Spot" in it.
2. Go over every e-mail in our archive, in chronological order.
3. Look for paragraphs that start with "born" or "died".
4. Add the names from paragraphs that start with "born" to our set of names.
5. Remove the names from paragraphs that start with "died" from our set.

¶ Where taking the names from a paragraph goes like this:

1. Find the colon in the paragraph.
2. Take the part after this colon.
3. Split this part into separate names by looking for commas.

¶ It may require some suspension of disbelief to accept that aunt Emily always used this exact format, and that she never forgot or misspelled a name, but that is just how your aunt is.

¶ First, let me tell you about properties. A lot of JavaScript values have other values associated with them. These associations are called properties. Every string has a property called length, which refers to a number, the amount of characters in that string.

¶ Properties can be accessed in two ways:

var text = "purple haze";
show(text["length"]);
show(text.length);

¶ The second way is a shorthand for the first, and it only works when the name of the property would be a valid variable name ― when it doesn't have any spaces or symbols in it and does not start with a digit character.

¶ The values null and undefined do not have any properties. Trying to read properties from such a value produces an error. Try the following code, if only to get an idea about the kind of error-message your browser produces in such a case (which, for some browsers, can be rather cryptic).

var nothing = null;
show(nothing.length);

¶ The properties of a string value can not be changed. There are quite a few more than just length, as we will see, but you are not allowed to add or remove any.

¶ This is different with values of the type object. Their main role is to hold other values. They have, you could say, their own set of tentacles in the form of properties. You are free to modify these, remove them, or add new ones.

¶ An object can be written like this:

var cat = {colour: "grey", name: "Spot", size: 46};
cat.size = 47;
show(cat.size);
delete cat.size;
show(cat.size);
show(cat);

¶ Like variables, each property attached to an object is labelled by a string. The first statement creates an object in which the property "colour" holds the string "grey", the property "name" is attached to the string "Spot", and the property "size" refers to the number 46. The second statement gives the property named size a new value, which is done in the same way as modifying a variable.

¶ The keyword delete cuts off properties. Trying to read a non-existent property gives the value undefined.

¶ If a property that does not yet exist is set with the = operator, it is added to the object.

var empty = {};
empty.notReally = 1000;
show(empty.notReally);

¶ Properties whose names are not valid variable names have to be quoted when creating the object, and approached using brackets:

var thing = {"gabba gabba": "hey", "5": 10};
show(thing["5"]);
thing["5"] = 20;
show(thing[2 + 3]);
delete thing["gabba gabba"];

¶ As you can see, the part between the brackets can be any expression. It is converted to a string to determine the property name it refers to. One can even use variables to name properties:

var propertyName = "length";
var text = "mainline";
show(text[propertyName]);

¶ The operator in can be used to test whether an object has a certain property. It produces a boolean.

var chineseBox = {};
chineseBox.content = chineseBox;
show("content" in chineseBox);
show("content" in chineseBox.content);

¶ When object values are shown on the console, they can be clicked to inspect their properties. This changes the output window to an 'inspect' window. The little 'x' at the top-right can be used to return to the output window, and the left-arrow can be used to go back to the properties of the previously inspected object.

show(chineseBox);

¶ Object values, apparently, can change. The types of values discussed in chapter 2 are all immutable, it is impossible to change an existing value of those types. You can combine them and derive new values from them, but when you take a specific string value, the text inside it can not change. With objects, on the other hand, the content of a value can be modified by changing its properties.

¶ When we have two numbers, 120 and 120, they can for all practical purposes be considered the precise same number. 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:

var object1 = {value: 10};
var object2 = object1;
var object3 = {value: 10};

show(object1 == object2);
show(object1 == object3);

object1.value = 15;
show(object2.value);
show(object3.value);

¶ object1 and object2 are two variables grasping the same value. There is only one actual object, which is why changing object1 also changes the value of object2. The variable object3 points to another object, which initially contains the same properties as object1, but lives a separate life.

¶ JavaScript's == operator, when comparing objects, will only return true if both values given to it are the precise same value. Comparing different objects with identical contents will give false. This is useful in some situations, but impractical in others.

¶ Object values can play a lot of different roles. Behaving like a set is only one of those. We will see a few other roles in this chapter, and chapter 8 shows another important way of using objects.

¶ In the plan for the cat problem ― in fact, call it an algorithm, not a plan, that makes it sound like we know what we are talking about ― in the algorithm, it talks about going over all the e-mails in an archive. What does this archive look like? And where does it come from?

¶ Do not worry about the second question for now. Chapter 14 talks about some ways to import data into your programs, but for now you will find that the e-mails are just magically there. Some magic is really easy, inside computers.

¶ The way in which the archive is stored is still an interesting question. It contains a number of e-mails. An e-mail can be a string, that should be obvious. The whole archive could be put into one huge string, but that is hardly practical. What we want is a collection of separate strings.

¶ Collections of things are what objects are used for. One could make an object like this:

var mailArchive = {"the first e-mail": "Dear nephew, ...",
                   "the second e-mail": "..."
                   /* and so on ... */};

¶ But that makes it hard to go over the e-mails from start to end ― how does the program guess the name of these properties? This can be solved by more predictable property names:

var mailArchive = {0: "Dear nephew, ... (mail number 1)",
                   1: "(mail number 2)",
                   2: "(mail number 3)"};

for (var current = 0; current in mailArchive; current++)
  print("Processing e-mail #", current, ": ", mailArchive[current]);

¶ Luck has it that there is a special kind of objects specifically for this kind of use. They are called arrays, and they provide some conveniences, such as a length property that contains the amount of values in the array, and a number of operations useful for this kind of collection.

¶ New arrays can be created using brackets ([ and ]):

var mailArchive = ["mail one", "mail two", "mail three"];

for (var current = 0; current < mailArchive.length; current++)
  print("Processing e-mail #", current, ": ", mailArchive[current]);

¶ In this example, the numbers of the elements are not specified explicitly anymore. The first one automatically gets the number 0, the second the number 1, and so on.

¶ Why start at 0? People tend to start counting from 1. As unintuitive as it seems, numbering the elements in a collection from 0 is often more practical. Just go with it for now, it will grow on you.

¶ Starting at element 0 also means that in a collection with X elements, the last element can be found at position X - 1. This is why the for loop in the example checks for current < mailArchive.length. There is no element at position mailArchive.length, so as soon as current has that value, we stop looping.

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

var doh = "Doh";
print(typeof doh.toUpperCase);
print(doh.toUpperCase());

¶ 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. Guess what that does.

¶ Notice that, even though the call to toUpperCase does not pass any arguments, the function does somehow have access to the string "Doh", the value of which it is a property. How this works precisely is described in chapter 8.

¶ Properties that contain functions are generally called methods, as in 'toUpperCase is a method of a string object'.

var mack = [];
mack.push("Mack");
mack.push("the");
mack.push("Knife");
show(mack.join(" "));
show(mack.pop());
show(mack);

¶ The method push, which is associated with arrays, can be used to add values to it. It could have been used in the last exercise, as an alternative to result[i] = i. Then there is pop, the opposite of push: it takes off and returns the last value in the array. join builds a single big string from an array of strings. The parameter it is given is pasted between the values in the array.

¶ Coming back to those cats, we now know that an array would be a good way to store the archive of e-mails. On this page, the function retrieveMails can be used to (magically) get hold of this array. Going over them to process them one after another is not rocket science anymore either:

var mailArchive = retrieveMails();

for (var i = 0; i < mailArchive.length; i++) {
  var email = mailArchive[i];
  print("Processing e-mail #", i);
  // Do more things...
}

¶ We have also decided on a way to represent the set of cats that are alive. The next problem, then, is to find the paragraphs in an e-mail that start with "born" or "died".

¶ The first question that comes up is what exactly a paragraph is. In this case, the string value itself can't help us much: JavaScript's concept of text does not go any deeper than the 'sequence of characters' idea, so we must define paragraphs in those terms.

¶ Earlier, we saw that there is such a thing as a newline character. These are what most people use to split paragraphs. We consider a paragraph, then, to be a part of an e-mail that starts at a newline character or at the start of the content, and ends at the next newline character or at the end of the content.

¶ And we don't even have to write the algorithm for splitting a string into paragraphs ourselves. Strings already have a method named split, which is (almost) the opposite of the join method of arrays. It splits a string into an array, using the string given as its argument to determine in which places to cut.

var words = "Cities of the Interior";
show(words.split(" "));

¶ Thus, cutting on newlines ("\n"), can be used to split an e-mail into paragraphs.

¶ Paragraphs that do not start with either "born" or "died" can be ignored by the program. How do we test whether a string starts with a certain word? The method charAt can be used to get a specific character from a string. x.charAt(0) gives the first character, 1 is the second one, and so on. One way to check whether a string starts with "born" is:

var paragraph = "born 15-11-2003 (mother Spot): White Fang";
show(paragraph.charAt(0) == "b" && paragraph.charAt(1) == "o" &&
     paragraph.charAt(2) == "r" && paragraph.charAt(3) == "n");

¶ But that gets a bit clumsy ― imagine checking for a word of ten characters. There is something to be learned here though: when a line gets ridiculously long, it can be spread over multiple lines. The result can be made easier to read by lining up the start of the new line with the first element on the original line that plays a similar role.

¶ Strings also have a method called slice. It copies out a piece of the string, starting from the character at the position given by the first argument, and ending before (not including) the character at the position given by the second one. This allows the check to be written in a shorter way.

show(paragraph.slice(0, 4) == "born");

¶ What happens when charAt or slice are used to take a piece of a string that does not exist? Will the startsWith I showed still work when the pattern is longer than the string it is matched against?

show("Pip".charAt(250));
show("Nop".slice(1, 10));

¶ charAt will return "" when there is no character at the given position, and slice will simply leave out the part of the new string that does not exist.

¶ So yes, that version of startsWith works. When startsWith("Idiots", "Most honoured colleagues") is called, the call to slice will, because string does not have enough characters, always return a string that is shorter than pattern. Because of that, the comparison with == will return false, which is correct.

¶ It helps to always take a moment to consider abnormal (but valid) inputs for a program. These are usually called corner cases, and it is very common for programs that work perfectly on all the 'normal' inputs to screw up on corner cases.

¶ The only part of the cat-problem that is still unsolved is the extraction of names from a paragraph. The algorithm was this:

1. Find the colon in the paragraph.
2. Take the part after this colon.
3. Split this part into separate names by looking for commas.

¶ This has to happen both for paragraphs that start with "died", and paragraphs that start with "born". It would be a good idea to put it into a function, so that the two pieces of code that handle these different kinds of paragraphs can both use it.

¶ All that remains now is putting the pieces together. One way to do that looks like this:

var mailArchive = retrieveMails();
var livingCats = {"Spot": true};

for (var mail = 0; mail < mailArchive.length; mail++) {
  var paragraphs = mailArchive[mail].split("\n");
  for (var paragraph = 0;
       paragraph < paragraphs.length;
       paragraph++) {
    if (startsWith(paragraphs[paragraph], "born")) {
      var names = catNames(paragraphs[paragraph]);
      for (var name = 0; name < names.length; name++)
        livingCats[names[name]] = true;
    }
    else if (startsWith(paragraphs[paragraph], "died")) {
      var names = catNames(paragraphs[paragraph]);
      for (var name = 0; name < names.length; name++)
        delete livingCats[names[name]];
    }
  }
}

show(livingCats);

¶ That is quite a big dense chunk of code. We'll look into making it a bit lighter in a moment. But first let us look at our results. We know how to check whether a specific cat survives:

if ("Spot" in livingCats)
  print("Spot lives!");
else
  print("Good old Spot, may she rest in peace.");

¶ But how do we list all the cats that are alive? The in keyword has a somewhat different meaning when it is used together with for:

for (var cat in livingCats)
  print(cat);

¶ A loop like that will go over the names of the properties in an object, which allows us to enumerate all the names in our set.

¶ Some pieces of code look like an impenetrable jungle. The example solution to the cat problem suffers from this. One way to make some light shine through it is to just add some strategic blank lines. This makes it look better, but doesn't really solve the problem.

¶ What is needed here is to break the code up. We already wrote two helper functions, startsWith and catNames, which both take care of a small, understandable part of the problem. Let us continue doing this.

function addToSet(set, values) {
  for (var i = 0; i < values.length; i++)
    set[values[i]] = true;
}

function removeFromSet(set, values) {
  for (var i = 0; i < values.length; i++)
    delete set[values[i]];
}

¶ These two functions take care of the adding and removing of names from the set. That already cuts out the two most inner loops from the solution:

var livingCats = {Spot: true};

for (var mail = 0; mail < mailArchive.length; mail++) {
  var paragraphs = mailArchive[mail].split("\n");
  for (var paragraph = 0;
       paragraph < paragraphs.length;
       paragraph++) {
    if (startsWith(paragraphs[paragraph], "born"))
      addToSet(livingCats, catNames(paragraphs[paragraph]));
    else if (startsWith(paragraphs[paragraph], "died"))
      removeFromSet(livingCats, catNames(paragraphs[paragraph]));
  }
}

¶ Quite an improvement, if I may say so myself.

¶ Why do addToSet and removeFromSet take the set as an argument? They could use the variable livingCats directly, if they wanted to. The reason is that this way they are not completely tied to our current problem. If addToSet directly changed livingCats, it would have to be called addCatsToCatSet, or something similar. The way it is now, it is a more generally useful tool.

¶ Even if we are never going to use these functions for anything else, which is quite probable, it is useful to write them like this. Because they are 'self sufficient', they can be read and understood on their own, without needing to know about some external variable called livingCats.

¶ The functions are not pure: They change the object passed as their set argument. This makes them slightly trickier than real pure functions, but still a lot less confusing than functions that run amok and change any value or variable they please.

¶ We continue breaking the algorithm into pieces:

function findLivingCats() {
  var mailArchive = retrieveMails();
  var livingCats = {"Spot": true};

  function handleParagraph(paragraph) {
    if (startsWith(paragraph, "born"))
      addToSet(livingCats, catNames(paragraph));
    else if (startsWith(paragraph, "died"))
      removeFromSet(livingCats, catNames(paragraph));
  }

  for (var mail = 0; mail < mailArchive.length; mail++) {
    var paragraphs = mailArchive[mail].split("\n");
    for (var i = 0; i < paragraphs.length; i++)
      handleParagraph(paragraphs[i]);
  }
  return livingCats;
}

var howMany = 0;
for (var cat in findLivingCats())
  howMany++;
print("There are ", howMany, " cats.");

¶ The whole algorithm is now encapsulated by a function. This means that it does not leave a mess after it runs: livingCats is now a local variable in the function, instead of a top-level one, so it only exists while the function runs. The code that needs this set can call findLivingCats and use the value it returns.

¶ It seemed to me that making handleParagraph a separate function also cleared things up. But this one is so closely tied to the cat-algorithm that it is meaningless in any other situation. On top of that, it needs access to the livingCats variable. Thus, it is a perfect candidate to be a function-inside-a-function. When it lives inside findLivingCats, it is clear that it is only relevant there, and it has access to the variables of its parent function.

¶ This solution is actually bigger than the previous one. Still, it is tidier and I hope you'll agree that it is easier to read.

¶ The program still ignores a lot of the information that is contained in the e-mails. There are birth-dates, dates of death, and the names of mothers in there.

¶ To start with the dates: What would be a good way to store a date? We could make an object with three properties, year, month, and day, and store numbers in them.

var when = {year: 1980, month: 2, day: 1};

¶ But JavaScript already provides a kind of object for this purpose. Such an object can be created by using the keyword new:

var when = new Date(1980, 1, 1);
show(when);

¶ Just like the notation with braces and colons we have already seen, new is a way to create object values. Instead of specifying all the property names and values, a function is used to build up the object. This makes it possible to define a kind of standard procedure for creating objects. Functions like this are called constructors, and in chapter 8 we will see how to write them.

¶ The Date constructor can be used in different ways.

show(new Date());
show(new Date(1980, 1, 1));
show(new Date(2007, 2, 30, 8, 20, 30));

¶ As you can see, these objects can store a time of day as well as a date. When not given any arguments, an object representing the current time and date is created. Arguments can be given to ask for a specific date and time. The order of the arguments is year, month, day, hour, minute, second, milliseconds. These last four are optional, they become 0 when not given.

¶ The month numbers these objects use go from 0 to 11, which can be confusing. Especially since day numbers do start from 1.

¶ The content of a Date object can be inspected with a number of get... methods.

var today = new Date();
print("Year: ", today.getFullYear(), ", month: ",
      today.getMonth(), ", day: ", today.getDate());
print("Hour: ", today.getHours(), ", minutes: ",
      today.getMinutes(), ", seconds: ", today.getSeconds());
print("Day of week: ", today.getDay());

¶ All of these, except for getDay, also have a set... variant that can be used to change the value of the date object.

¶ Inside the object, a date is represented by the amount of milliseconds it is away from January 1st 1970. You can imagine this is quite a large number.

var today = new Date();
show(today.getTime());

¶ A very useful thing to do with dates is comparing them.

var wallFall = new Date(1989, 10, 9);
var gulfWarOne = new Date(1990, 6, 2);
show(wallFall < gulfWarOne);
show(wallFall == wallFall);
// but
show(wallFall == new Date(1989, 10, 9));

¶ Comparing dates with <, >, <=, and >= does exactly what you would expect. When a date object is compared to itself with == the result is true, which is also good. But when == is used to compare a date object to a different, equal date object, we get false. Huh?

¶ As mentioned earlier, == will return false when comparing two different objects, even if they contain the same properties. This is a bit clumsy and error-prone here, since one would expect >= and == to behave in a more or less similar way. Testing whether two dates are equal can be done like this:

var wallFall1 = new Date(1989, 10, 9),
    wallFall2 = new Date(1989, 10, 9);
show(wallFall1.getTime() == wallFall2.getTime());

¶ In addition to a date and time, Date objects also contain information about a timezone. When it is one o'clock in Amsterdam, it can, depending on the time of year, be noon in London, and seven in the morning in New York. Such times can only be compared when you take their time zones into account. The getTimezoneOffset function of a Date can be used to find out how many minutes it differs from GMT (Greenwich Mean Time).

var now = new Date();
print(now.getTimezoneOffset());

¶ Storing cats will work differently from now on. Instead of just putting the value true into the set, we store an object with information about the cat. When a cat dies, we do not remove it from the set, we just add a property death to the object to store the date on which the creature died.

¶ This means our addToSet and removeFromSet functions have become useless. Something similar is needed, but it must also store birth-dates and, later, the mother's name.

function catRecord(name, birthdate, mother) {
  return {name: name, birth: birthdate, mother: mother};
}

function addCats(set, names, birthdate, mother) {
  for (var i = 0; i < names.length; i++)
    set[names[i]] = catRecord(names[i], birthdate, mother);
}
function deadCats(set, names, deathdate) {
  for (var i = 0; i < names.length; i++)
    set[names[i]].death = deathdate;
}

¶ catRecord is a separate function for creating these storage objects. It might be useful in other situations, such as creating the object for Spot. 'Record' is a term often used for objects like this, which are used to group a limited number of values.

¶ So let us try to extract the names of the mother cats from the paragraphs.

"born 15/11/2003 (mother Spot): White Fang"

¶ One way to do this would be...

function extractMother(paragraph) {
  var start = paragraph.indexOf("(mother ") + "(mother ".length;
  var end = paragraph.indexOf(")");
  return paragraph.slice(start, end);
}

show(extractMother("born 15/11/2003 (mother Spot): White Fang"));

¶ Notice how the start position has to be adjusted for the length of "(mother ", because indexOf returns the position of the start of the pattern, not its end.

¶ Having between makes it possible to express extractMother in a simpler way:

function extractMother(paragraph) {
  return between(paragraph, "(mother ", ")");
}

¶ The new, improved cat-algorithm looks like this:

function findCats() {
  var mailArchive = retrieveMails();
  var cats = {"Spot": catRecord("Spot", new Date(1997, 2, 5),
              "unknown")};

  function handleParagraph(paragraph) {
    if (startsWith(paragraph, "born"))
      addCats(cats, catNames(paragraph), extractDate(paragraph),
              extractMother(paragraph));
    else if (startsWith(paragraph, "died"))
      deadCats(cats, catNames(paragraph), extractDate(paragraph));
  }

  for (var mail = 0; mail < mailArchive.length; mail++) {
    var paragraphs = mailArchive[mail].split("\n");
    for (var i = 0; i < paragraphs.length; i++)
      handleParagraph(paragraphs[i]);
  }
  return cats;
}

var catData = findCats();

¶ Having that extra data allows us to finally have a clue about the cats aunt Emily talks about. A function like this could be useful:

function formatDate(date) {
  return date.getDate() + "/" + (date.getMonth() + 1) +
         "/" + date.getFullYear();
}

function catInfo(data, name) {
  if (!(name in data))
    return "No cat by the name of " + name + " is known.";

  var cat = data[name];
  var message = name + ", born " + formatDate(cat.birth) +
                " from mother " + cat.mother;
  if ("death" in cat)
    message += ", died " + formatDate(cat.death);
  return message + ".";
}

print(catInfo(catData, "Fat Igor"));

¶ The first return statement in catInfo is used as an escape hatch. If there is no data about the given cat, the rest of the function is meaningless, so we immediately return a value, which prevents the rest of the code from running.

¶ In the past, certain groups of programmers considered functions that contain multiple return statements sinful. The idea was that this made it hard to see which code was executed and which code was not. Other techniques, which will be discussed in chapter 5, have made the reasons behind this idea more or less obsolete, but you might still occasionally come across someone who will criticise the use of 'shortcut' return statements.

¶ Now that we are familiar with arrays, I can show you something related. Whenever a function is called, a special variable named arguments is added to the environment in which the function body runs. This variable refers to an object that resembles an array. It has a property 0 for the first argument, 1 for the second, and so on for every argument the function was given. It also has a length property.

¶ This object is not a real array though, it does not have methods like push, and it does not automatically update its length property when you add something to it. Why not, I never really found out, but this is something one needs to be aware of.

function argumentCounter() {
  print("You gave me ", arguments.length, " arguments.");
}
argumentCounter("Death", "Famine", "Pestilence");

¶ Some functions can take any number of arguments, like print does. These typically loop over the values in the arguments object to do something with them. Others can take optional arguments which, when not given by the caller, get some sensible default value.

function add(number, howmuch) {
  if (arguments.length < 2)
    howmuch = 1;
  return number + howmuch;
}

show(add(6));
show(add(6, 4));

¶ Chapter 2 mentioned the functions Math.max and Math.min. With what you know now, you will notice that these are really the properties max and min of the object stored under the name Math. This is another role that objects can play: A warehouse holding a number of related values.

¶ There are quite a lot of values inside Math, if they would all have been placed directly into the global environment they would, as it is called, pollute it. The more names have been taken, the more likely one is to accidentally overwrite the value of some variable. For example, it is not a far shot to want to name something max.

¶ Most languages will stop you, or at least warn you, when you are defining a variable with a name that is already taken. Not JavaScript.

¶ In any case, one can find a whole outfit of mathematical functions and constants inside Math. All the trigonometric functions are there ― cos, sin, tan, acos, asin, atan. π and e, which are written with all capital letters (PI and E), which was, at one time, a fashionable way to indicate something is a constant. pow is a good replacement for the power functions we have been writing, it also accepts negative and fractional exponents. sqrt takes square roots. max and min can give the maximum or minimum of two values. round, floor, and ceil will round numbers to the closest whole number, the whole number below it, and the whole number above it respectively.

¶ There are a number of other values in Math, but this text is an introduction, not a reference. References are what you look at when you suspect something exists in the language, but need to find out what it is called or how it works exactly. Unfortunately, there is no one comprehensive complete reference for JavaScript. This is mostly because its current form is the result of a chaotic process of different browsers adding different extensions at different times. The ECMA standard document that was mentioned in the introduction provides a solid documentation of the basic language, but is more or less unreadable. For most things, your best bet is the Mozilla Developer Network.

¶ Maybe you already thought of a way to find out what is available in the Math object:

for (var name in Math)
  print(name);

¶ But alas, nothing appears. Similarly, when you do this:

for (var name in ["Huey", "Dewey", "Loui"])
  print(name);

¶ You only see 0, 1, and 2, not length, or push, or join, which are definitely also in there. Apparently, some properties of objects are hidden. There is a good reason for this: All objects have a few methods, for example toString, which converts the object into some kind of relevant string, and you do not want to see those when you are, for example, looking for the cats that you stored in the object.

¶ Why the properties of Math are hidden is unclear to me. Someone probably wanted it to be a mysterious kind of object.

¶ All properties your programs add to objects are visible. There is no way to make them hidden, which is unfortunate because, as we will see in chapter 8, it would be nice to be able to add methods to objects without having them show up in our for/in loops.

¶ Some properties are read-only, you can get their value but not change it. For example, the properties of a string value are all read-only.

¶ Other properties can be 'active'. Changing them causes things to happen. For example, lowering the length of an array causes excess elements to be discarded:

var array = ["Heaven", "Earth", "Man"];
array.length = 2;
show(array);

¶ Writing programs that work when everything goes as expected is a good start. Making your programs behave properly when encountering unexpected conditions is where it really gets challenging.

¶ The problematic situations that a program can encounter fall into two categories: Programmer mistakes and genuine problems. If someone forgets to pass a required argument to a function, that is an example of the first kind of problem. On the other hand, if a program asks the user to enter a name and it gets back an empty string, that is something the programmer can not prevent.

¶ In general, one deals with programmer errors by finding and fixing them, and with genuine errors by having the code check for them and perform some suitable action to remedy them (for example, asking for the name again), or at least fail in a well-defined and clean way.

¶ It is important to decide into which of these categories a certain problem falls. For example, consider our old power function:

function power(base, exponent) {
  var result = 1;
  for (var count = 0; count < exponent; count++)
    result *= base;
  return result;
}

¶ When some geek tries to call power("Rabbit", 4), that is quite obviously a programmer error, but how about power(9, 0.5)? The function can not handle fractional exponents, but, mathematically speaking, raising a number to the halfth power is perfectly reasonable (Math.pow can handle it). In situations where it is not entirely clear what kind of input a function accepts, it is often a good idea to explicitly state the kind of arguments that are acceptable in a comment.

¶ If a function encounters a problem that it can not solve itself, what should it do? In chapter 4 we wrote the function between:

function between(string, start, end) {
  var startAt = string.indexOf(start) + start.length;
  var endAt = string.indexOf(end, startAt);
  return string.slice(startAt, endAt);
}

¶ If the given start and end do not occur in the string, indexOf will return -1 and this version of between will return a lot of nonsense: between("Your mother!", "{-", "-}") returns "our mother".

¶ When the program is running, and the function is called like that, the code that called it will get a string value, as it expected, and happily continue doing something with it. But the value is wrong, so whatever it ends up doing with it will also be wrong. And if you are unlucky, this wrongness only causes a problem after having passed through twenty other functions. In cases like that, it is extremely hard to find out where the problem started.

¶ In some cases, you will be so unconcerned about these problems that you don't mind the function misbehaving when given incorrect input. For example, if you know for sure the function will only be called from a few places, and you can prove that these places give it decent input, it is generally not worth the trouble to make the function bigger and uglier so that it can handle problematic cases.

¶ But most of the time, functions that fail 'silently' are hard to use, and even dangerous. What if the code calling between wants to know whether everything went well? At the moment, it can not tell, except by re-doing all the work that between did and checking the result of between with its own result. That is bad. One solution is to make between return a special value, such as false or undefined, when it fails.

function between(string, start, end) {
  var startAt = string.indexOf(start);
  if (startAt == -1)
    return undefined;
  startAt += start.length;
  var endAt = string.indexOf(end, startAt);
  if (endAt == -1)
    return undefined;

  return string.slice(startAt, endAt);
}

¶ You can see that error checking does not generally make functions prettier. But now code that calls between can do something like:

var input = prompt("Tell me something", "");
var parenthesized = between(input, "(", ")");
if (parenthesized != undefined)
  print("You parenthesized '", parenthesized, "'.");

¶ In many cases returning a special value is a perfectly fine way to indicate an error. It does, however, have its downsides. Firstly, what if the function can already return every possible kind of value? For example, consider this function that gets the last element from an array:

function lastElement(array) {
  if (array.length > 0)
    return array[array.length - 1];
  else
    return undefined;
}

show(lastElement([1, 2, undefined]));

¶ So did the array have a last element? Looking at the value lastElement returns, it is impossible to say.

¶ The second issue with returning special values is that it can sometimes lead to a whole lot of clutter. If a piece of code calls between ten times, it has to check ten times whether undefined was returned. Also, if a function calls between but does not have a strategy to recover from a failure, it will have to check the return value of between, and if it is undefined, this function can then return undefined or some other special value to its caller, who in turn also checks for this value.

¶ Sometimes, when something strange occurs, it would be practical to just stop doing what we are doing and immediately jump back to a place that knows how to handle the problem.

¶ Well, we are in luck, a lot of programming languages provide such a thing. Usually, it is called exception handling.

¶ The theory behind exception handling goes like this: It is possible for code to raise (or throw) an exception, which is a value. Raising an exception somewhat resembles a super-charged return from a function ― it does not just jump out of the current function, but also out of its callers, all the way up to the top-level call that started the current execution. This is called unwinding the stack. You may remember the stack of function calls that was mentioned in chapter 3. An exception zooms down this stack, throwing away all the call contexts it encounters.

¶ If they always zoomed right down to the base of the stack, exceptions would not be of much use, they would just provide a novel way to blow up your program. Fortunately, it is possible to set obstacles for exceptions along the stack. These 'catch' the exception as it is zooming down, and can do something with it, after which the program continues running at the point where the exception was caught.

¶ An example:

function lastElement(array) {
  if (array.length > 0)
    return array[array.length - 1];
  else
    throw "Can not take the last element of an empty array.";
}

function lastElementPlusTen(array) {
  return lastElement(array) + 10;
}

try {
  print(lastElementPlusTen([]));
}
catch (error) {
  print("Something went wrong: ", error);
}

¶ throw is the keyword that is used to raise an exception. The keyword try sets up an obstacle for exceptions: When the code in the block after it raises an exception, the catch block will be executed. The variable named in parentheses after the word catch is the name given to the exception value inside this block.

¶ Note that the function lastElementPlusTen completely ignores the possibility that lastElement might go wrong. This is the big advantage of exceptions ― error-handling code is only necessary at the point where the error occurs, and the point where it is handled. The functions in between can forget all about it.

¶ Well, almost.

¶ Consider the following: A function processThing wants to set a top-level variable currentThing to point to a specific thing while its body executes, so that other functions can have access to that thing too. Normally you would of course just pass the thing as an argument, but assume for a moment that that is not practical. When the function finishes, currentThing should be set back to null.

var currentThing = null;

function processThing(thing) {
  if (currentThing != null)
    throw "Oh no! We are already processing a thing!";

  currentThing = thing;
  /* do complicated processing... */
  currentThing = null;
}

¶ But what if the complicated processing raises an exception? In that case the call to processThing will be thrown off the stack by the exception, and currentThing will never be reset to null.

¶ try statements can also be followed by a finally keyword, which means 'no matter what happens, run this code after trying to run the code in the try block'. If a function has to clean something up, the cleanup code should usually be put into a finally block:

function processThing(thing) {
  if (currentThing != null)
    throw "Oh no! We are already processing a thing!";

  currentThing = thing;
  try {
    /* do complicated processing... */
  }
  finally {
    currentThing = null;
  }
}

¶ A lot of errors in programs cause the JavaScript environment to raise an exception. For example:

try {
  print(Sasquatch);
}
catch (error) {
  print("Caught: " + error.message);
}

¶ In cases like this, special error objects are raised. These always have a message property containing a description of the problem. You can raise similar objects using the new keyword and the Error constructor:

throw new Error("Fire!");

¶ When an exception goes all the way to the bottom of the stack without being caught, it gets handled by the environment. What this means differs between the different browsers, sometimes a description of the error is written to some kind of log, sometimes a window pops up describing the error.

¶ The errors produced by entering code in the console on this page are always caught by the console, and displayed among the other output.

¶ Most programmers consider exceptions purely an error-handling mechanism. In essence, though, they are just another way of influencing the control flow of a program. For example, they can be used as a kind of break statement in a recursive function. Here is a slightly strange function which determines whether an object, and the objects stored inside it, contain at least seven true values:

var FoundSeven = {};

function hasSevenTruths(object) {
  var counted = 0;

  function count(object) {
    for (var name in object) {
      if (object[name] === true) {
        counted++;
        if (counted == 7)
          throw FoundSeven;
      }
      else if (typeof object[name] == "object") {
        count(object[name]);
      }
    }
  }

  try {
    count(object);
    return false;
  }
  catch (exception) {
    if (exception != FoundSeven)
      throw exception;
    return true;
  }
}

¶ The inner function count is recursively called for every object that is part of the argument. When the variable counted reaches seven, there is no point in continuing to count, but just returning from the current call to count will not necessarily stop the counting, since there might be more calls below it. So what we do is just throw a value, which will cause the control to jump right out of any calls to count, and land at the catch block.

¶ But just returning true in case of an exception is not correct. Something else might be going wrong, so we first check whether the exception is the object FoundSeven, created specifically for this purpose. If it is not, this catch block does not know how to handle it, so it raises it again.

¶ This is a pattern that is also common when dealing with error conditions ― you have to make sure that your catch block only handles exceptions that it knows how to handle. Throwing string values, as some of the examples in this chapter do, is rarely a good idea, because it makes it hard to recognise the type of the exception. A better idea is to use unique values, such as the FoundSeven object, or to introduce a new type of objects, as described in chapter 8.

¶ As programs get bigger, they also become more complex and harder to understand. We all think ourselves pretty clever, of course, but we are mere human beings, and even a moderate amount of chaos tends to baffle us. And then it all goes downhill. Working on something you do not really understand is a bit like cutting random wires on those time-activated bombs they always have in movies. If you are lucky, you might get the right one ― especially if you are the hero of the movie and strike a suitably dramatic pose ― but there is always the possibility of blowing everything up.

¶ Admittedly, in most cases, breaking a program does not cause any large explosions. But when a program, by someone's ignorant tinkering, has degenerated into a ramshackle mass of errors, reshaping it into something sensible is a terrible labour ― sometimes you might just as well start over.

¶ Thus, the programmer is always looking for ways to keep the complexity of his programs as low as possible. An important way to do this is to try and make code more abstract. When writing a program, it is easy to get sidetracked into small details at every point. You come across some little issue, and you deal with it, and then proceed to the next little problem, and so on. This makes the code read like a grandmother's tale.

Yes, dear, to make pea soup you will need split peas, the dry kind. And you have to soak them at least for a night, or you will have to cook them for hours and hours. I remember one time, when my dull son tried to make pea soup. Would you believe he hadn't soaked the peas? We almost broke our teeth, all of us. Anyway, when you have soaked the peas, and you'll want about a cup of them per person, and pay attention because they will expand a bit while they are soaking, so if you aren't careful they will spill out of whatever you use to hold them, so also use plenty water to soak in, but as I said, about a cup of them, when they are dry, and after they are soaked you cook them in four cups of water per cup of dry peas. Let it simmer for two hours, which means you cover it and keep it barely cooking, and then add some diced onions, sliced celery stalk, and maybe a carrot or two and some ham. Let it all cook for a few minutes more, and it is ready to eat.

¶ Another way to describe this recipe:

Per person: one cup dried split peas, half a chopped onion, half a carrot, a celery stalk, and optionally ham.

Soak peas overnight, simmer them for two hours in four cups of water (per person), add vegetables and ham, and cook for ten more minutes.

¶ This is shorter, but if you don't know how to soak peas you'll surely screw up and put them in too little water. But how to soak peas can be looked up, and that is the trick. If you assume a certain basic knowledge in the audience, you can talk in a language that deals with bigger concepts, and express things in a much shorter and clearer way. This, more or less, is what abstraction is.

¶ How is this far-fetched recipe story relevant to programming? Well, obviously, the recipe is the program. Furthermore, the basic knowledge that the cook is supposed to have corresponds to the functions and other constructs that are available to the programmer. If you remember the introduction of this book, things like while make it easier to build loops, and in chapter 4 we wrote some simple functions in order to make other functions shorter and more straightforward. Such tools, some of them made available by the language itself, others built by the programmer, are used to reduce the amount of uninteresting details in the rest of the program, and thus make that program easier to work with.

¶ Functional programming, which is the subject of this chapter, produces abstraction through clever ways of combining functions. A programmer armed with a repertoire of fundamental functions and, more importantly, the knowledge on how to use them, is much more effective than one who starts from scratch. Unfortunately, a standard JavaScript environment comes with deplorably few essential functions, so we have to write them ourselves or, which is often preferable, make use of somebody else's code (more on that in chapter 9).

¶ There are other popular approaches to abstraction, most notably object-oriented programming, the subject of chapter 8.

¶ One ugly detail that, if you have any good taste at all, must be starting to bother you is the endlessly repeated for loop going over an array: for (var i = 0; i < something.length; i++) .... Can this be abstracted?

¶ The problem is that, whereas most functions just take some values, combine them, and return something, such a loop contains a piece of code that it must execute. It is easy to write a function that goes over an array and prints out every element:

function printArray(array) {
  for (var i = 0; i < array.length; i++)
    print(array[i]);
}

¶ But what if we want to do something else than print? Since 'doing something' can be represented as a function, and functions are also values, we can pass our action as a function value:

function forEach(array, action) {
  for (var i = 0; i < array.length; i++)
    action(array[i]);
}

forEach(["Wampeter", "Foma", "Granfalloon"], print);

¶ And by making use of an anonymous function, something just like a for loop can be written with less useless details:

function sum(numbers) {
  var total = 0;
  forEach(numbers, function (number) {
    total += number;
  });
  return total;
}
show(sum([1, 10, 100]));

¶ Note that the variable total is visible inside the anonymous function because of the lexical scoping rules. Also note that this version is hardly shorter than the for loop and requires a rather clunky }); at its end ― the brace closes the body of the anonymous function, the parenthesis closes the function call to forEach, and the semicolon is needed because this call is a statement.

¶ You do get a variable bound to the current element in the array, number, so there is no need to use numbers[i] anymore, and when this array is created by evaluating some expression, there is no need to store it in a variable, because it can be passed to forEach directly.

¶ The cat-code in chapter 4 contains a piece like this:

var paragraphs = mailArchive[mail].split("\n");
for (var i = 0; i < paragraphs.length; i++)
  handleParagraph(paragraphs[i]);

¶ This can now be written as...

forEach(mailArchive[mail].split("\n"), handleParagraph);

¶ On the whole, using more abstract (or 'higher level') constructs results in more information and less noise: The code in sum reads 'for each number in numbers add that number to the total', instead of... 'there is this variable that starts at zero, and it counts upward to the length of the array called numbers, and for every value of this variable we look up the corresponding element in the array and add this to the total'.

¶ What forEach does is take an algorithm, in this case 'going over an array', and abstract it. The 'gaps' in the algorithm, in this case, what to do for each of these elements, are filled by functions which are passed to the algorithm function.

¶ Functions that operate on other functions are called higher-order functions. By operating on functions, they can talk about actions on a whole new level. The makeAddFunction function from chapter 3 is also a higher-order function. Instead of taking a function value as an argument, it produces a new function.

¶ Higher-order functions can be used to generalise many algorithms that regular functions can not easily describe. When you have a repertoire of these functions at your disposal, it can help you think about your code in a clearer way: Instead of a messy set of variables and loops, you can decompose algorithms into a combination of a few fundamental algorithms, which are invoked by name, and do not have to be typed out again and again.

¶ Being able to write what we want to do instead of how we do it means we are working at a higher level of abstraction. In practice, this means shorter, clearer, and more pleasant code.

¶ Another useful type of higher-order function modifies the function value it is given:

function negate(func) {
  return function(x) {
    return !func(x);
  };
}
var isNotNaN = negate(isNaN);
show(isNotNaN(NaN));

¶ The function returned by negate feeds the argument it is given to the original function func, and then negates the result. But what if the function you want to negate takes more than one argument? You can get access to any arguments passed to a function with the arguments array, but how do you call a function when you do not know how many arguments you have?

¶ Functions have a method called apply, which is used for situations like this. It takes two arguments. The role of the first argument will be discussed in chapter 8, for now we just use null there. The second argument is an array containing the arguments that the function must be applied to.

show(Math.min.apply(null, [5, 6]));

function negate(func) {
  return function() {
    return !func.apply(null, arguments);
  };
}

¶ Unfortunately, on the Internet Explorer browser a lot of built-in functions, such as alert, are not really functions... or something. They report their type as "object" when given to the typeof operator, and they do not have an apply method. Your own functions do not suffer from this, they are always real functions.

¶ Let us look at a few more basic algorithms related to arrays. The sum function is really a variant of an algorithm which is usually called reduce or fold:

function reduce(combine, base, array) {
  forEach(array, function (element) {
    base = combine(base, element);
  });
  return base;
}

function add(a, b) {
  return a + b;
}

function sum(numbers) {
  return reduce(add, 0, numbers);
}

¶ reduce combines an array into a single value by repeatedly using a function that combines an element of the array with a base value. This is exactly what sum did, so it can be made shorter by using reduce... except that addition is an operator and not a function in JavaScript, so we first had to put it into a function.

¶ The reason reduce takes the function as its first argument instead of its last, as in forEach, is partly that this is tradition ― other languages do it like that ― and partly that this allows us to use a particular trick, which will be discussed at the end of this chapter. It does mean that, when calling reduce, writing the reducing function as an anonymous function looks a bit weirder, because now the other arguments follow after the function, and the resemblance to a normal for block is lost entirely.

¶ One other generally useful 'fundamental algorithm' related to arrays is called map. It goes over an array, applying a function to every element, just like forEach. But instead of discarding the values returned by function, it builds up a new array from these values.

function map(func, array) {
  var result = [];
  forEach(array, function (element) {
    result.push(func(element));
  });
  return result;
}

show(map(Math.round, [0.01, 2, 9.89, Math.PI]));

¶ Note that the first argument is called func, not function, this is because function is a keyword and thus not a valid variable name.

¶ There once was, living in the deep mountain forests of Transylvania, a recluse. Most of the time, he just wandered around his mountain, talking to trees and laughing with birds. But now and then, when the pouring rain trapped him in his little hut, and the howling wind made him feel unbearably small, the recluse felt an urge to write something, wanted to pour some thoughts out onto paper, where they could maybe grow bigger than he himself was.

¶ After failing miserably at poetry, fiction, and philosophy, the recluse finally decided to write a technical book. In his youth, he had done some computer programming, and he figured that if he could just write a good book about that, fame and recognition would surely follow.

¶ So he wrote. At first he used fragments of tree bark, but that turned out not to be very practical. He went down to the nearest village and bought himself a laptop computer. After a few chapters, he realised he wanted to put the book in HTML format, in order to put it on his web-page...

¶ Are you familiar with HTML? It is the method used to add mark-up to pages on the web, and we will be using it a few times in this book, so it would be nice if you know how it works, at least generally. If you are a good student, you could go search the web for a good introduction to HTML now, and come back here when you have read it. Most of you probably are lousy students, so I will just give a short explanation and hope it is enough.

¶ HTML stands for 'HyperText Mark-up Language'. An HTML document is all text. Because it must be able to express the structure of this text, information about which text is a heading, which text is purple, and so on, a few characters have a special meaning, somewhat like backslashes in JavaScript strings. The 'less than' and 'greater than' characters are used to create 'tags'. A tag gives extra information about the text in the document. It can stand on its own, for example to mark the place where a picture should appear in the page, or it can contain text and other tags, for example when it marks the start and end of a paragraph.

¶ Some tags are compulsory, a whole HTML document must always be contained in between html tags. Here is an example of an HTML document:

<html>
  <head>
    <title>A quote</title>
  </head>
  <body>
    <h1>A quote</h1>
    <blockquote>
      <p>The connection between the language in which we
      think/program and the problems and solutions we can imagine
      is very close.  For this reason restricting language
      features with the intent of eliminating programmer errors is
      at best dangerous.</p>
      <p>-- Bjarne Stroustrup</p>
    </blockquote>
    <p>Mr. Stroustrup is the inventor of the C++ programming
    language, but quite an insightful person nevertheless.</p>
    <p>Also, here is a picture of an ostrich:</p>
    <img src="img/ostrich.png"/>
  </body>
</html>

¶ Elements that contain text or other tags are first opened with <tagname>, and afterwards finished with </tagname>. The html element always contains two children: head and body. The first contains information about the document, the second contains the actual document.

¶ Most tag names are cryptic abbreviations. h1 stands for 'heading 1', the biggest kind of heading. There are also h2 to h6 for successively smaller headings. p means 'paragraph', and img stands for 'image'. The img element does not contain any text or other tags, but it does have some extra information, src="img/ostrich.png", which is called an 'attribute'. In this case, it contains information about the image file that should be shown here.

¶ Because < and > have a special meaning in HTML documents, they can not be written directly in the text of the document. If you want to say '5 < 10' in an HTML document, you have to write '5 < 10', where 'lt' stands for 'less than'. '>' is used for '>', and because these codes also give the ampersand character a special meaning, a plain '&' is written as '&'.

¶ Now, those are only the bare basics of HTML, but they should be enough to make it through this chapter, and later chapters that deal with HTML documents, without getting entirely confused.

¶ The JavaScript console has a function viewHTML that can be used to look at HTML documents. I stored the example document above in the variable stroustrupQuote, so you can view it by executing the following code:

viewHTML(stroustrupQuote);

¶ If you have some kind of pop-up blocker installed or integrated in your browser, it will probably interfere with viewHTML, which tries to show the HTML document in a new window or tab. Try to configure the blocker to allow pop-ups from this site.

¶ So, picking up the story again, the recluse wanted to have his book in HTML format. At first he just wrote all the tags directly into his manuscript, but typing all those less-than and greater-than signs made his fingers hurt, and he constantly forgot to write & when he needed an &. This gave him a headache. Next, he tried to write the book in Microsoft Word, and then save it as HTML. But the HTML that came out of that was fifteen times bigger and more complicated than it had to be. And besides, Microsoft Word gave him a headache.

¶ The solution that he eventually came up with was this: He would write the book as plain text, following some simple rules about the way paragraphs were separated and the way headings looked. Then, he would write a program to convert this text into precisely the HTML that he wanted.

¶ The rules are this:

1. Paragraphs are separated by blank lines.
2. A paragraph that starts with a '%' symbol is a header. The more '%' symbols, the smaller the header.
3. Inside paragraphs, pieces of text can be emphasised by putting them between asterisks.
4. Footnotes are written between braces.

¶ After he had struggled painfully with his book for six months, the recluse had still only finished a few paragraphs. At this point, his hut was struck by lightning, killing him, and forever putting his writing ambitions to rest. From the charred remains of his laptop, I could recover the following file:

% The Book of Programming

%% The Two Aspects

Below the surface of the machine, the program moves. Without effort,
it expands and contracts. In great harmony, electrons scatter and
regroup. The forms on the monitor are but ripples on the water. The
essence stays invisibly below.

When the creators built the machine, they put in the processor and the
memory. From these arise the two aspects of the program.

The aspect of the processor is the active substance. It is called
Control. The aspect of the memory is the passive substance. It is
called Data.

Data is made of merely bits, yet it takes complex forms. Control
consists only of simple instructions, yet it performs difficult
tasks. From the small and trivial, the large and complex arise.

The program source is Data. Control arises from it. The Control
proceeds to create new Data. The one is born from the other, the
other is useless without the one. This is the harmonious cycle of
Data and Control.

Of themselves, Data and Control are without structure. The programmers
of old moulded their programs out of this raw substance. Over time,
the amorphous Data has crystallised into data types, and the chaotic
Control was restricted into control structures and functions.

%% Short Sayings

When a student asked Fu-Tzu about the nature of the cycle of Data and
Control, Fu-Tzu replied 'Think of a compiler, compiling itself.'

A student asked 'The programmers of old used only simple machines and
no programming languages, yet they made beautiful programs. Why do we
use complicated machines and programming languages?'. Fu-Tzu replied
'The builders of old used only sticks and clay, yet they made
beautiful huts.'

A hermit spent ten years writing a program. 'My program can compute
the motion of the stars on a 286-computer running MS DOS', he proudly
announced. 'Nobody owns a 286-computer or uses MS DOS anymore.',
Fu-Tzu responded.

Fu-Tzu had written a small program that was full of global state and
dubious shortcuts. Reading it, a student asked 'You warned us against
these techniques, yet I find them in your program. How can this be?'
Fu-Tzu said 'There is no need to fetch a water hose when the house is
not on fire.'{This is not to be read as an encouragement of sloppy
programming, but rather as a warning against neurotic adherence to
rules of thumb.}

%% Wisdom

A student was complaining about digital numbers. 'When I take the root
of two and then square it again, the result is already inaccurate!'.
Overhearing him, Fu-Tzu laughed. 'Here is a sheet of paper. Write down
the precise value of the square root of two for me.'

Fu-Tzu said 'When you cut against the grain of the wood, much strength
is needed. When you program against the grain of a problem, much code
is needed.'

Tzu-li and Tzu-ssu were boasting about the size of their latest
programs. 'Two-hundred thousand lines', said Tzu-li, 'not counting
comments!'. 'Psah', said Tzu-ssu, 'mine is almost a *million* lines
already.' Fu-Tzu said 'My best program has five hundred lines.'
Hearing this, Tzu-li and Tzu-ssu were enlightened.

A student had been sitting motionless behind his computer for hours,
frowning darkly. He was trying to write a beautiful solution to a
difficult problem, but could not find the right approach. Fu-Tzu hit
him on the back of his head and shouted '*Type something!*' The student
started writing an ugly solution. After he had finished, he suddenly
understood the beautiful solution.

%% Progression

A beginning programmer writes his programs like an ant builds her
hill, one piece at a time, without thought for the bigger structure.
His programs will be like loose sand. They may stand for a while, but
growing too big they fall apart{Referring to the danger of internal
inconsistency and duplicated structure in unorganised code.}.

Realising this problem, the programmer will start to spend a lot of
time thinking about structure. His programs will be rigidly
structured, like rock sculptures. They are solid, but when they must
change, violence must be done to them{Referring to the fact that
structure tends to put restrictions on the evolution of a program.}.

The master programmer knows when to apply structure and when to leave
things in their simple form. His programs are like clay, solid yet
malleable.

%% Language

When a programming language is created, it is given syntax and
semantics. The syntax describes the form of the program, the semantics
describe the function. When the syntax is beautiful and the semantics
are clear, the program will be like a stately tree. When the syntax is
clumsy and the semantics confusing, the program will be like a bramble
bush.

Tzu-ssu was asked to write a program in the language called Java,
which takes a very primitive approach to functions. Every morning, as
he sat down in front of his computer, he started complaining. All day
he cursed, blaming the language for all that went wrong. Fu-Tzu
listened for a while, and then reproached him, saying 'Every language
has its own way. Follow its form, do not try to program as if you
were using another language.'

¶ To honour the memory of our good recluse, I would like to finish his HTML-generating program for him. A good approach to this problem goes like this:

1. Split the file into paragraphs by cutting it at every empty line.
2. Remove the '%' characters from header paragraphs and mark them as headers.
3. Process the text of the paragraphs themselves, splitting them into normal parts, emphasised parts, and footnotes.
4. Move all the footnotes to the bottom of the document, leaving numbers1 in their place.
5. Wrap each piece into the correct HTML tags.
6. Combine everything into a single HTML document.

¶ This approach does not allow footnotes inside emphasised text, or vice versa. This is kind of arbitrary, but helps keep the example code simple. If, at the end of the chapter, you feel like an extra challenge, you can try to revise the program to support 'nested' mark-up.

¶ The whole manuscript, as a string value, is available on this page by calling recluseFile function.

¶ Step 1 of the algorithm is trivial. A blank line is what you get when you have two newlines in a row, and if you remember the split method that strings have, which we saw in chapter 4, you will realise that this will do the trick:

var paragraphs = recluseFile().split("\n\n");
print("Found ", paragraphs.length, " paragraphs.");

¶ This is where we can try out the map function we saw earlier.

var paragraphs = map(processParagraph,
                     recluseFile().split("\n\n"));

¶ And bang, we have an array of nicely categorised paragraph objects. We are getting ahead of ourselves though, we forgot step 3 of the algorithm:

Process the text of the paragraphs themselves, splitting them into normal parts, emphasised parts, and footnotes.

¶ Which can be decomposed into:

1. If the paragraph starts with an asterisk, take off the emphasised part and store it.
2. If the paragraph starts with an opening brace, take off the footnote and store it.
3. Otherwise, take off the part until the first emphasised part or footnote, or until the end of the string, and store it as normal text.
4. If there is anything left in the paragraph, start at 1 again.

¶ We can now wire processParagraph to also split the text inside the paragraphs, my version can be modified like this:

function processParagraph(paragraph) {
  var header = 0;
  while (paragraph.charAt(0) == "%") {
    paragraph = paragraph.slice(1);
    header++;
  }

  return {type: (header == 0 ? "p" : "h" + header),
          content: splitParagraph(paragraph)};
}

¶ Mapping that over the array of paragraphs gives us an array of paragraph objects, which in turn contain arrays of fragment objects. The next thing to do is to take out the footnotes, and put references to them in their place. Something like this:

function extractFootnotes(paragraphs) {
  var footnotes = [];
  var currentNote = 0;

  function replaceFootnote(fragment) {
    if (fragment.type == "footnote") {
      currentNote++;
      footnotes.push(fragment);
      fragment.number = currentNote;
      return {type: "reference", number: currentNote};
    }
    else {
      return fragment;
    }
  }

  forEach(paragraphs, function(paragraph) {
    paragraph.content = map(replaceFootnote,
                            paragraph.content);
  });

  return footnotes;
}     

¶ The replaceFootnote function is called on every fragment. When it gets a fragment that should stay where it is, it just returns it, but when it gets a footnote, it stores this footnote in the footnotes array, and returns a reference to it instead. In the process, every footnote and reference is also numbered.

¶ That gives us enough tools to extract the information we need from the file. All that is left now is generating the correct HTML.

¶ A lot of people think that concatenating strings is a great way to produce HTML. When they need a link to, for example, a site where you can play the game of Go, they will do:

var url = "http://www.gokgs.com/";
var text = "Play Go!";
var linkText = "<a href=\"" + url + "\">" + text + "</a>";
print(linkText);

¶ (Where a is the tag used to create links in HTML documents.) ... Not only is this clumsy, but when the string text happens to include an angular bracket or an ampersand, it is also wrong. Weird things will happen on your website, and you will look embarrassingly amateurish. We wouldn't want that to happen. A few simple HTML-generating functions are easy to write. So let us write them.

¶ The secret to successful HTML generation is to treat your HTML document as a data structure instead of a flat piece of text. JavaScript's objects provide a very easy way to model this:

var linkObject = {name: "a",
                  attributes: {href: "http://www.gokgs.com/"},
                  content: ["Play Go!"]};

¶ Each HTML element contains a name property, giving the name of the tag it represents. When it has attributes, it also contains an attributes property, which contains an object in which the attributes are stored. When it has content, there is a content property, containing an array of other elements contained in this element. Strings play the role of pieces of text in our HTML document, so the array ["Play Go!"] means that this link has only one element inside it, which is a simple piece of text.

¶ Typing in these objects directly is clumsy, but we don't have to do that. We provide a shortcut function to do this for us:

function tag(name, content, attributes) {
  return {name: name, attributes: attributes, content: content};
}

¶ Note that, since we allow the attributes and content of an element to be undefined if they are not applicable, the second and third argument to this function can be left off when they are not needed.

¶ tag is still rather primitive, so we write shortcuts for common types of elements, such as links, or the outer structure of a simple document:

function link(target, text) {
  return tag("a", [text], {href: target});
}

function htmlDoc(title, bodyContent) {
  return tag("html", [tag("head", [tag("title", [title])]),
                      tag("body", bodyContent)]);
}

¶ When we have created a document, it will have to be reduced to a string. But building this string from the data structures we have been producing is very straightforward. The important thing is to remember to transform the special characters in the text of our document...

function escapeHTML(text) {
  var replacements = [[/&/g, "&"], [/"/g, """],
                      [/</g, "&lt;"], [/>/g, "&gt;"]];
  forEach(replacements, function(replace) {
    text = text.replace(replace[0], replace[1]);
  });
  return text;
}

¶ The replace method of strings creates a new string in which all occurrences of the pattern in the first argument are replaced by the second argument, so "Borobudur".replace(/r/g, "k") gives "Bokobuduk". Don't worry about the pattern syntax here ― we'll get to that in chapter 10. The escapeHTML function puts the different replacements that have to be made into an array, so that it can loop over them and apply them to the argument one by one.

¶ Double quotes are also replaced, because we will also be using this function for the text inside the attributes of HTML tags. Those will be surrounded by double quotes, and thus must not have any double quotes inside of them.

¶ Calling replace four times means the computer has to go over the whole string four times to check and replace its content. This is not very efficient. If we cared enough, we could write a more complex version of this function, something that resembles the splitParagraph function we saw earlier, to go over it only once. For now, we are too lazy for this. Again, chapter 10 shows a much better way to do this.

¶ To turn an HTML element object into a string, we can use a recursive function like this:

function renderHTML(element) {
  var pieces = [];

  function renderAttributes(attributes) {
    var result = [];
    if (attributes) {
      for (var name in attributes) 
        result.push(" " + name + "=\"" +
                    escapeHTML(attributes[name]) + "\"");
    }
    return result.join("");
  }

  function render(element) {
    // Text node
    if (typeof element == "string") {
      pieces.push(escapeHTML(element));
    }
    // Empty tag
    else if (!element.content || element.content.length == 0) {
      pieces.push("<" + element.name +
                  renderAttributes(element.attributes) + "/>");
    }
    // Tag with content
    else {
      pieces.push("<" + element.name +
                  renderAttributes(element.attributes) + ">");
      forEach(element.content, render);
      pieces.push("</" + element.name + ">");
    }
  }

  render(element);
  return pieces.join("");
}

¶ Note the in loop that extracts the properties from a JavaScript object in order to make HTML tag attributes out of them. Also note that in two places, arrays are being used to accumulate strings, which are then joined into a single result string. Why didn't I just start with an empty string and then add the content to it with the += operator?

¶ It turns out that creating new strings, especially big strings, is quite a lot of work. Remember that JavaScript string values never change. If you concatenate something to them, a new string is created, the old ones stay intact. If we build up a big string by concatenating lots of little strings, new strings have to be created at every step, only to be thrown away when the next piece is concatenated to them. If, on the other hand, we store all the little strings in an array and then join them, only one big string has to be created.

¶ So, let us try out this HTML generating system...

print(renderHTML(link("http://www.nedroid.com", "Drawings!")));

¶ That seems to work.

var body = [tag("h1", ["The Test"]),
            tag("p", ["Here is a paragraph, and an image..."]),
            image("img/sheep.png")];
var doc = htmlDoc("The Test", body);
viewHTML(renderHTML(doc));

¶ Now, I should probably warn you that this approach is not perfect. What it actually renders is XML, which is similar to HTML, but more structured. In simple cases, such as the above, this does not cause any problems. However, there are some things, which are correct XML, but not proper HTML, and these might confuse a browser that is trying to show the documents we create. For example, if you have an empty script tag (used to put JavaScript into a page) in your document, browsers will not realise that it is empty and think that everything after it is JavaScript. (In this case, the problem can be fixed by putting a single space inside of the tag, so that it is no longer empty, and gets a proper closing tag.)

¶ We are almost finished. The only thing that we do not have a rendering function for yet are the footnotes. To make the "#footnote1" links work, an anchor must be included with every footnote. In HTML, an anchor is specified with an a element, which is also used for links. In this case, it needs a name attribute, instead of an href.

function renderFootnote(footnote) {
  var number = "[" + footnote.number + "] ";
  var anchor = tag("a", [number], {name: "footnote" + footnote.number});
  return tag("p", [tag("small", [anchor, footnote.content])]);
}

¶ Here, then, is the function which, when given a file in the correct format and a document title, returns an HTML document:

function renderFile(file, title) {
  var paragraphs = map(processParagraph, file.split("\n\n"));
  var footnotes = map(renderFootnote,
                      extractFootnotes(paragraphs));
  var body = map(renderParagraph, paragraphs).concat(footnotes);
  return renderHTML(htmlDoc(title, body));
}

viewHTML(renderFile(recluseFile(), "The Book of Programming"));

¶ The concat method of an array can be used to concatenate another array to it, similar to what the + operator does with strings.

¶ In the chapters after this one, elementary higher-order functions like map and reduce will always be available and will be used by code examples. Now and then, a new useful tool is added to this. In chapter 9, we develop a more structured approach to this set of 'basic' functions.

¶ When using higher-order functions, it is often annoying that operators are not functions in JavaScript. We have needed add or equals functions at several points. Rewriting these every time, you will agree, is a pain. From now on, we will assume the existence of an object called op, which contains these functions:

var op = {
  "+": function(a, b){return a + b;},
  "==": function(a, b){return a == b;},
  "===": function(a, b){return a === b;},
  "!": function(a){return !a;}
  /* and so on */
};

¶ So we can write reduce(op["+"], 0, [1, 2, 3, 4, 5]) to sum an array. But what if we need something like equals or makeAddFunction, in which one of the arguments already has a value? In that case we are back to writing a new function again.

¶ For cases like that, something called 'partial application' is useful. You want to create a new function that already knows some of its arguments, and treats any additional arguments it is passed as coming after these fixed arguments. This can be done by making creative use of the apply method of a function:

function asArray(quasiArray, start) {
  var result = [];
  for (var i = (start || 0); i < quasiArray.length; i++)
    result.push(quasiArray[i]);
  return result;
}

function partial(func) {
  var fixedArgs = asArray(arguments, 1);
  return function(){
    return func.apply(null, fixedArgs.concat(asArray(arguments)));
  };
}

¶ We want to allow binding multiple arguments at the same time, so the asArray function is necessary to make normal arrays out of the arguments objects. It copies their content into a real array, so that the concat method can be used on it. It also takes an optional second argument, which can be used to leave out some arguments at the start.

¶ Also note that it is necessary to store the arguments of the outer function (partial) into a variable with another name, because otherwise the inner function can not see them ― it has its own arguments variable, which shadows the one of the outer function.

¶ Now equals(10) could be written as partial(op["=="], 10), without the need for a specialized equals function. And you can do things like this:

show(map(partial(op["+"], 1), [0, 2, 4, 6, 8, 10]));

¶ The reason map takes its function argument before its array argument is that it is often useful to partially apply map by giving it a function. This 'lifts' the function from operating on a single value to operating on an array of values. For example, if you have an array of arrays of numbers, and you want to square them all, you do this:

function square(x) {return x * x;}

show(map(partial(map, square), [[10, 100], [12, 16], [0, 1]]));

¶ One last trick that can be useful when you want to combine functions is function composition. At the start of this chapter I showed a function negate, which applies the boolean not operator to the result of calling a function:

function negate(func) {
  return function() {
    return !func.apply(null, arguments);
  };
}

¶ This is a special case of a general pattern: call function A, and then apply function B to the result. Composition is a common concept in mathematics. It can be caught in a higher-order function like this:

function compose(func1, func2) {
  return function() {
    return func1(func2.apply(null, arguments));
  };
}

var isUndefined = partial(op["==="], undefined);
var isDefined = compose(op["!"], isUndefined);
show(isDefined(Math.PI));
show(isDefined(Math.PIE));

¶ Here we are defining new functions without using the function keyword at all. This can be useful when you need to create a simple function to give to, for example, map or reduce. However, when a function becomes more complex than these examples, it is usually shorter (not to mention more efficient) to just write it out with function.

¶ This chapter does not introduce any new JavaScript-specific concepts. Instead, we will go through the solution to two problems, discussing some interesting algorithms and techniques along the way. If this does not sound interesting to you, it is safe to skip to the next chapter.

¶ Let me introduce our first problem. Take a look at this map. It shows Hiva Oa, a small tropical island in the Pacific Ocean.

¶ The grey lines are roads, and the numbers next to them are the lengths of these roads. Imagine we need a program that finds the shortest route between two points on Hiva Oa. How could we approach that? Think about this for a moment.

¶ No really. Don't just steamroll on to the next paragraph. Try to seriously think of some ways you could do this, and consider the issues you would come up against. When reading a technical book, it is way too easy to just zoom over the text, nod solemnly, and promptly forget what you have read. If you make a sincere effort to solve a problem, it becomes your problem, and its solution will be more meaningful.

¶ The first aspect of this problem is, again, representing our data. The information in the picture does not mean much to our computer. We could try writing a program that looks at the map and extracts the information in it... but that can get complicated. If we had twenty-thousand maps to interpret, this would be a good idea, in this case we will do the interpretation ourself and transcribe the map into a more computer-friendly format.

¶ What does our program need to know? It has to be able to look up which locations are connected, and how long the roads between them are. The places and roads on the island form a graph, as mathematicians call it. There are many ways to store graphs. A simple possibility is to just store an array of road objects, each of which contains properties naming its two endpoints and its length...

var roads = [{point1: "Point Kiukiu", point2: "Hanaiapa", length: 19},
             {point1: "Point Kiukiu", point2: "Mt Feani", length: 15}
             /* and so on */];

¶ However, it turns out that the program, as it is working out a route, will very often need to get a list of all the roads that start at a certain location, like a person standing on a crossroads will look at a signpost and read "Hanaiapa: 19km, Mount Feani: 15km". It would be nice if this was easy (and quick) to do.

¶ With the representation given above, we have to sift through the whole list of roads, picking out the relevant ones, every time we want this signpost list. A better approach would be to store this list directly. For example, use an object that associates place-names with signpost lists:

var roads = {"Point Kiukiu": [{to: "Hanaiapa", distance: 19},
                              {to: "Mt Feani", distance: 15},
                              {to: "Taaoa", distance: 15}],
             "Taaoa": [/* et cetera */]};

¶ When we have this object, getting the roads that leave from Point Kiukiu is just a matter of looking at roads["Point Kiukiu"].

¶ However, this new representation does contain duplicate information: The road between A and B is listed both under A and under B. The first representation was already a lot of work to type in, this one is even worse.

¶ Fortunately, we have at our command the computer's talent for repetitive work. We can specify the roads once, and have the correct data structure be generated by the computer. First, initialise an empty object called roads, and write a function makeRoad:

var roads = {};
function makeRoad(from, to, length) {
  function addRoad(from, to) {
    if (!(from in roads))
      roads[from] = [];
    roads[from].push({to: to, distance: length});
  }
  addRoad(from, to);
  addRoad(to, from);
}

¶ Nice, huh? Notice how the inner function, addRoad, uses the same names (from, to) for its parameters as the outer function. These will not interfere: inside addRoad they refer to addRoad's parameters, and outside it they refer to makeRoad's parameters.

¶ The if statement in addRoad makes sure that there is an array of destinations associated with the location named by from, if there isn't already one it puts in an empty array. This way, the next line can assume there is such an array and safely push the new road onto it.

¶ Now the map information looks like this:

makeRoad("Point Kiukiu", "Hanaiapa", 19);
makeRoad("Point Kiukiu", "Mt Feani", 15);
makeRoad("Point Kiukiu", "Taaoa", 15);
// ...

¶ We managed to considerably shorten our description of the road-information by defining some convenient operations. You could say we expressed the information more succinctly by expanding our vocabulary. Defining a 'little language' like this is often a very powerful technique ― when, at any time, you find yourself writing repetitive or redundant code, stop and try to come up with a vocabulary that makes it shorter and denser.

¶ Redundant code is not only a bore to write, it is also error-prone, people pay less attention when doing something that doesn't require them to think. On top of that, repetitive code is hard to change, because structure that is repeated a hundred times has to be changed a hundred times when it turns out to be incorrect or suboptimal.

¶ If you ran all the pieces of code above, you should now have a variable named roads that contains all the roads on the island. When we need the roads starting from a certain place, we could just do roads[place]. But then, when someone makes a typo in a place name, which is not unlikely with these names, he will get undefined instead of the array he expects, and strange errors will follow. Instead, we will use a function that retrieves the road arrays, and yells at us when we give it an unknown place name:

function roadsFrom(place) {
  var found = roads[place];
  if (found == undefined)
    throw new Error("No place named '" + place + "' found.");
  else
    return found;
}

show(roadsFrom("Puamua"));

¶ Here is a first stab at a path-finding algorithm, the gambler's method:

function gamblerPath(from, to) {
  function randomInteger(below) {
    return Math.floor(Math.random() * below);
  }
  function randomDirection(from) {
    var options = roadsFrom(from);
    return options[randomInteger(options.length)].to;
  }

  var path = [];
  while (true) {
    path.push(from);
    if (from == to)
      break;
    from = randomDirection(from);
  }
  return path;
}

show(gamblerPath("Hanaiapa", "Mt Feani"));

¶ At every split in the road, the gambler rolls his dice to decide which road he shall take. If the dice sends him back the way he came, so be it. Sooner or later, he will arrive at his destination, since all places on the island are connected by roads.

¶ The most confusing line is probably the one containing Math.random. This function returns a pseudo-random1 number between 0 and 1. Try calling it a few times from the console, it will (most likely) give you a different number every time. The function randomInteger multiplies this number by the argument it is given, and rounds the result down with Math.floor. Thus, for example, randomInteger(3) will produce the number 0, 1, or 2.

¶ The gambler's method is the way to go for those who abhor structure and planning, who desperately search for adventure. We set out to write a program that could find the shortest route between places though, so something else will be needed.

¶ A very straightforward approach to solving such a problem is called 'generate and test'. It goes like this:

1. Generate all possible routes.
2. In this set, find the shortest one that actually connects the start point to the end point.

¶ Step two is not hard. Step one is a little problematic. If you allow routes with circles in them, there is an infinite amount of routes. Of course, routes with circles in them are unlikely to be the shortest route to anywhere, and routes that do not start at the start point do not have to be considered either. For a small graph like Hiva Oa, it should be possible to generate all non-cyclic (circle-free) routes starting from a certain point.

¶ But first, we will need some new tools. The first is a function named member, which is used to determine whether an element is found within an array. The route will be kept as an array of names, and when arriving at a new place, the algorithm calls member to check whether we have been at that place already. It could look like this:

function member(array, value) {
  var found = false;
  forEach(array, function(element) {
    if (element === value)
      found = true;
  });
  return found;
}

print(member([6, 7, "Bordeaux"], 7));

¶ However, this will go over the whole array, even if the value is found immediately at the first position. What wastefulness. When using a for loop, you can use the break statement to jump out of it, but in a forEach construct this will not work, because the body of the loop is a function, and break statements do not jump out of functions. One solution could be to adjust forEach to recognise a certain kind of exceptions as signalling a break.

var Break = {toString: function() {return "Break";}};

function forEach(array, action) {
  try {
    for (var i = 0; i < array.length; i++)
      action(array[i]);
  }
  catch (exception) {
    if (exception != Break)
      throw exception;
  }
}

¶ Now, if the action function throws Break, forEach will absorb the exception and stop looping. The object stored in the variable Break is used purely as a thing to compare with. The only reason I gave it a toString property is that this might be useful to figure out what kind of strange value you are dealing with if you somehow end up with a Break exception outside of a forEach.

¶ Having a way to break out of forEach loops can be very useful, but in the case of the member function the result is still rather ugly, because you need to specifically store the result and later return it. We could add yet another kind of exception, Return, which can be given a value property, and have forEach return this value when such an exception is thrown, but this would be terribly ad-hoc and messy. What we really need is a whole new higher-order function, called any (or sometimes some). It looks like this:

function any(test, array) {
  for (var i = 0; i < array.length; i++) {
    var found = test(array[i]);
    if (found)
      return found;
  }
  return false;
}

function member(array, value) {
  return any(partial(op["==="], value), array);
}

print(member(["Fear", "Loathing"], "Denial"));

¶ any goes over the elements in an array, from left to right, and applies the test function to them. The first time this returns a true-ish value, it returns that value. If no true-ish value is found, false is returned. Calling any(test, array) is more or less equivalent to doing test(array[0]) || test(array[1]) || ... etcetera.

¶ Just like && is the companion of ||, any has a companion called every:

function every(test, array) {
  for (var i = 0; i < array.length; i++) {
    var found = test(array[i]);
    if (!found)
      return found;
  }
  return true;
}

show(every(partial(op["!="], 0), [1, 2, -1]));

¶ Another function we will need is flatten. This function takes an array of arrays, and puts the elements of the arrays together in one big array.

  function flatten(arrays) {
    var result = [];
    forEach(arrays, function (array) {
      forEach(array, function (element){result.push(element);});
    });
    return result;
  }

¶ The same could have been done using the concat method and some kind of reduce, but this would be less efficient. Just like repeatedly concatenating strings together is slower than putting them into an array and then calling join, repeatedly concatenating arrays produces a lot of unnecessary intermediary array values.

¶ Imagine what an algorithm to generate routes would look like ― it starts at the starting location, and starts to generate a route for every road leaving there. At the end of each of these roads it continues to generate more routes. It doesn't run along one road, it branches out. Because of this, recursion is a natural way to model it.

function possibleRoutes(from, to) {
  function findRoutes(route) {
    function notVisited(road) {
      return !member(route.places, road.to);
    }
    function continueRoute(road) {
      return findRoutes({places: route.places.concat([road.to]),
                         length: route.length + road.distance});
    }

    var end = route.places[route.places.length - 1];
    if (end == to)
      return [route];
    else
      return flatten(map(continueRoute, filter(notVisited,
                                               roadsFrom(end))));
  }
  return findRoutes({places: [from], length: 0});
}

show(possibleRoutes("Point Teohotepapapa", "Point Kiukiu").length);
show(possibleRoutes("Hanapaoa", "Mt Ootua"));

¶ The function returns an array of route objects, each of which contains an array of places that the route passes, and a length. findRoutes recursively continues a route, returning an array with every possible extension of that route. When the end of a route is the place where we want to go, it just returns that route, since continuing past that place would be pointless. If it is another place, we must go on. The flatten/map/filter line is probably the hardest to read. This is what it says: 'Take all the roads going from the current location, discard the ones that go to places that this route has already visited. Continue each of these roads, which will give an array of finished routes for each of them, then put all these routes into a single big array that we return.'

¶ That line does a lot. This is why good abstractions help: They allow you to say complicated things without typing screenfulls of code.

¶ Doesn't this recurse forever, seeing how it keeps calling itself (via continueRoute)? No, at some point, all outgoing roads will go to places that a route has already passed, and the result of filter will be an empty array. Mapping over an empty array produces an empty array, and flattening that still gives an empty array. So calling findRoutes on a dead end produces an empty array, meaning 'there are no ways to continue this route'.

¶ Notice that places are appended to routes by using concat, not push. The concat method creates a new array, while push modifies the existing array. Because the function might branch off several routes from a single partial route, we must not modify the array that represents the original route, because it must be used several times.

¶ Let us see what route our algorithm comes up with between Point Kiukiu and Point Teohotepapapa...

show(shortestRoute("Point Kiukiu", "Point Teohotepapapa").places);

¶ On a small island like Hiva Oa, it is not too much work to generate all possible routes. If you try to do that on a reasonably detailed map of, say, Belgium, it is going to take an absurdly long time, not to mention an absurd amount of memory. Still, you have probably seen those online route-planners. These give you a more or less optimal route through a gigantic maze of roads in just a few seconds. How do they do it?

¶ If you are paying attention, you may have noticed that it is not necessary to generate all routes all the way to the end. If we start comparing routes while we are building them, we can avoid building this big set of routes, and, as soon as we have found a single route to our destination, we can stop extending routes that are already longer than that route.

¶ To try this out, we will use a 20 by 20 grid as our map:

¶ What you see here is an elevation map of a mountain landscape. The yellow spots are the peaks, and the blue spots the valleys. The area is divided into squares with a size of a hundred meters. We have at our disposal a function heightAt, which can give us the height, in meters, of any square on that map, where squares are represented by objects with x and y properties.

print(heightAt({x: 0, y: 0}));
print(heightAt({x: 11, y: 18}));

¶ We want to cross this landscape, on foot, from the top left to the bottom right. A grid can be approached like a graph. Every square is a node, which is connected to the squares around it.

¶ We do not like wasting energy, so we would prefer to take the easiest route possible. Going uphill is heavier than going downhill, and going downhill is heavier than going level2. This function calculates the amount of 'weighted meters', between two adjacent squares, which represents how tired you get from walking (or climbing) between them. Going uphill is counted as twice as heavy as going downhill.

function weightedDistance(pointA, pointB) {
  var heightDifference = heightAt(pointB) - heightAt(pointA);
  var climbFactor = (heightDifference < 0 ? 1 : 2);
  var flatDistance = (pointA.x == pointB.x || pointA.y == pointB.y ? 100 : 141);
  return flatDistance + climbFactor * Math.abs(heightDifference);
}

¶ Note the flatDistance calculation. If the two points are on the same row or column, they are right next to each other, and the distance between them is a hundred meters. Otherwise, they are assumed to be diagonally adjacent, and the diagonal distance between two squares of this size is a hundred times the square root of two, which is approximately 141. One is not allowed to call this function for squares that are further than one step apart. (It could double-check this... but it is too lazy.)

¶ Points on the map are represented by objects containing x and y properties. These three functions are useful when working with such objects:

function point(x, y) {
  return {x: x, y: y};
}

function addPoints(a, b) {
  return point(a.x + b.x, a.y + b.y);
}

function samePoint(a, b) {
  return a.x == b.x && a.y == b.y;
}

show(samePoint(addPoints(point(10, 10), point(4, -2)),
               point(14, 8)));

¶ To find a route on this map without having our browser cut off the program because it takes too long to finish, we have to stop our amateurish attempts and implement a serious algorithm. A lot of work has gone into problems like this in the past, and many solutions have been designed (some brilliant, others useless). A very popular and efficient one is called A* (pronounced A-star). We will spend the rest of the chapter implementing an A* route-finding function for our map.

¶ Before I get to the algorithm itself, let me tell you a bit more about the problem it solves. The trouble with searching routes through graphs is that, in big graphs, there are an awful lot of them. Our Hiva Oa path-finder showed that, when the graph is small, all we needed to do was to make sure our paths didn't revisit points they had already passed. On our new map, this is not enough anymore.

¶ The fundamental problem is that there is too much room for going in the wrong direction. Unless we somehow manage to steer our exploration of paths towards the goal, a choice we make for continuing a given path is more likely to go in the wrong direction than in the right direction. If you keep generating paths like that, you end up with an enormous amount of paths, and even if one of them accidentally reaches the end point, you do not know whether that is the shortest path.

¶ So what you want to do is explore directions that are likely to get you to the end point first. On a grid like our map, you can get a rough estimate of how good a path is by checking how long it is and how close its end is to the end point. By adding path length and an estimate of the distance it still has to go, you can get a rough idea of which paths are promising. If you extend promising paths first, you are less likely to waste time on useless ones.

¶ But that still is not enough. If our map was of a perfectly flat plane, the path that looked promising would almost always be the best one, and we could use the above method to walk right to our goal. But we have valleys and hillsides blocking our paths, so it is hard to tell in advance which direction will be the most efficient path. Because of this, we still end up having to explore way too many paths.

¶ To correct this, we can make clever use of the fact that we are constantly exploring the most promising path first. Once we have determined that path A is the best way to get to point X, we can remember that. When, later on, path B also gets to point X, we know that it is not the best route, so we do not have to explore it further. This can prevent our program from building a lot of pointless paths.

¶ The algorithm, then, goes something like this...

¶ There are two pieces of data to keep track of. The first one is called the open list, it contains the partial routes that must still be explored. Each route has a score, which is calculated by adding its length to its estimated distance from the goal. This estimate must always be optimistic, it should never overestimate the distance. The second is a set of nodes that we have seen, together with the shortest partial route that got us there. This one we will call the reached list. We start by adding a route that contains only the starting node to the open list, and recording it in the reached list.

¶ Then, as long as there are any nodes in the open list, we take out the one that has the lowest (best) score, and find the ways in which it can be continued (by calling possibleDirections). For each of the nodes this returns, we create a new route by appending it to our original route, and adjusting the length of the route using weightedDistance. The endpoint of each of these new routes is then looked up in the reached list.

¶ If the node is not in the reached list yet, it means we have not seen it before, and we add the new route to the open list and record it in the reached list. If we had seen it before, we compare the score of the new route to the score of the route in the reached list. If the new route is shorter, we replace the existing route with the new one. Otherwise, we discard the new route, since we have already seen a better way to get to that point.

¶ We continue doing this until the route we fetch from the open list ends at the goal node, in which case we have found our route, or until the open list is empty, in which case we have found out that there is no route. In our case the map contains no unsurmountable obstacles, so there is always a route.

¶ How do we know that the first full route that we get from the open list is also the shortest one? This is a result of the fact that we only look at a route when it has the lowest score. The score of a route is its actual length plus an optimistic estimate of the remaining length. This means that if a route has the lowest score in the open list, it is always the best route to its current endpoint ― it is impossible for another route to later find a better way to that point, because if it were better, its score would have been lower.

¶ Try not to get frustrated when the fine points of why this works are still eluding you. When thinking about algorithms like this, having seen 'something like it' before helps a lot, it gives you a point of reference to compare the approach to. Beginning programmers have to do without such a point of reference, which makes it rather easy to get lost. Just realise that this is advanced stuff, globally read over the rest of the chapter, and come back to it later when you feel like a challenge.

¶ I am afraid that, for one aspect of the algorithm, I'm going to have to invoke magic again. The open list needs to be able to hold a large amount of routes, and to quickly find the route with the lowest score among them. Storing them in a normal array, and searching through this array every time, is way too slow, so I give you a data structure called a binary heap. You create them with new, just like Date objects, giving them a function that is used to 'score' its elements as argument. The resulting object has the methods push and pop, just like an array, but pop always gives you the element with the lowest score, instead of the one that was pushed last.

function identity(x) {
  return x;
}

var heap = new BinaryHeap(identity);
forEach([2, 4, 5, 1, 6, 3], function(number) {
  heap.push(number);
});
while (heap.size() > 0)
  show(heap.pop());

¶ Appendix 2 discusses the implementation of this data structure, which is quite interesting. After you have read chapter 8, you might want to take a look at it.

¶ The need to squeeze out as much efficiency as we can has another effect. The Hiva Oa algorithm used arrays of locations to store routes, and copied them with the concat method when it extended them. This time, we can not afford to copy arrays, since we will be exploring lots and lots of routes. Instead, we use a 'chain' of objects to store a route. Every object in the chain has some properties, such as a point on the map, and the length of the route so far, and it also has a property that points at the previous object in the chain. Something like this:

¶ Where the cyan circles are the relevant objects, and the lines represent properties ― the end with the dot points at the value of the property. Object A is the start of a route here. Object B is used to build a new route, which continues from A. It has a property, which we will call from, pointing at the route it is based on. When we need to reconstruct a route later, we can follow these properties to find all the points that the route passed. Note that object B is part of two routes, one that ends in D and one that ends in E. When there are a lot of routes, this can save us much storage space ― every new route only needs one new object for itself, the rest is shared with other routes that started the same way.

¶ Defining a type of data structure by providing a set of functions to create and manipulate such structures is a useful technique. It makes it possible to 'isolate' the code that makes use of the structure from the details of the structure itself. Note that, no matter which of the above two implementations is used, code that needs a reached list works in exactly the same way. It doesn't care what kind of objects are used, as long as it gets the results it expected.

¶ This will be discussed in much more detail in chapter 8, where we will learn to make object types like BinaryHeap, which are created using new and have methods to manipulate them.

¶ Here we finally have the actual path-finding function:

function findRoute(from, to) {
  var open = new BinaryHeap(routeScore);
  var reached = makeReachedList();

  function routeScore(route) {
    if (route.score == undefined)
      route.score = estimatedDistance(route.point, to) +
                    route.length;
    return route.score;
  }
  function addOpenRoute(route) {
    open.push(route);
    storeReached(reached, route.point, route);
  }
  addOpenRoute({point: from, length: 0});

  while (open.size() > 0) {
    var route = open.pop();
    if (samePoint(route.point, to))
      return route;
    
    forEach(possibleDirections(route.point), function(direction) {
      var known = findReached(reached, direction);
      var newLength = route.length +
                      weightedDistance(route.point, direction);
      if (!known || known.length > newLength){
        if (known)
          open.remove(known);        
        addOpenRoute({point: direction,
                      from: route,
                      length: newLength});
      }
    });
  }
  return null;
}

¶ First, it creates the data structures it needs, one open list and one reached list. routeScore is the scoring function given to the binary heap. Note how it stores its result in the route object, to prevent having to re-calculate it multiple times.

¶ addOpenRoute is a convenience function that adds a new route to both the open list and the reached list. It is immediately used to add the start of the route. Note that route objects always have the properties point, which holds the point at the end of the route, and length, which holds the current length of the route. Routes which are more than one square long also have a from property, which points at their predecessors.

¶ The while loop, as was described in the algorithm, keeps taking the lowest-scoring route from the open list and checks whether this gets us to the goal point. If it does not, we must continue by expanding it. This is what the forEach takes care of. It looks up this new point in the reached list. If it is not found there, or the node found has a longer length than the new route, a new route object is created and added to the open list and reached list, and the existing route (if any) is removed from the open list.

¶ What if the route in known is not on the open list? It has to be, because routes are only removed from the open list when they have been found to be the most optimal route to their endpoint. If we try to remove a value from a binary heap that is not on it, it will throw an exception, so if my reasoning is wrong, we will probably see an exception when running the function.

¶ When code gets complex enough to make you doubt certain things about it, it is a good idea to add some checks that raise exceptions when something goes wrong. That way, you know that there are no weird things happening 'silently', and when you break something, you immediately see what you broke.

¶ Note that this algorithm does not use recursion, but still manages to explore all those branches. The open list more or less takes over the role that the function call stack played in the recursive solution to the Hiva Oa problem ― it keeps track of the paths that still have to be explored. Every recursive algorithm can be rewritten in a non-recursive way by using a data structure to store the 'things that must still be done'.

¶ Well, let us try our path-finder:

var route = findRoute(point(0, 0), point(19, 19));

¶ If you ran all the code above, and did not introduce any errors, that call, though it might take a few seconds to run, should give us a route object. This object is rather hard to read. That can be helped by using the showRoute function which, if your console is big enough, will show a route on a map.

showRoute(route);

¶ You can also pass multiple routes to showRoute, which can be useful when you are, for example, trying to plan a scenic route, which must include the beautiful viewpoint at 11, 17.

showRoute(findRoute(point(0, 0), point(11, 17)),
          findRoute(point(11, 17), point(19, 19)));

¶ Variations on the theme of searching an optimal route through a graph can be applied to many problems, many of which are not at all related to finding a physical path. For example, a program that needs to solve a puzzle of fitting a number of blocks into a limited space could do this by exploring the various 'paths' it gets by trying to put a certain block in a certain place. The paths that ends up with insufficient room for the last blocks are dead ends, and the path that manages to fit in all blocks is the solution.

¶ In the early nineties, a thing called object-oriented programming stirred up the software industry. Most of the ideas behind it were not really new at the time, but they had finally gained enough momentum to start rolling, to become fashionable. Books were being written, courses given, programming languages developed. All of a sudden, everybody was extolling the virtues of object-orientation, enthusiastically applying it to every problem, convincing themselves they had finally found the right way to write programs.

¶ These things happen a lot. When a process is hard and confusing, people are always on the lookout for a magic solution. When something looking like such a solution presents itself, they are prepared to become devoted followers. For many programmers, even today, object-orientation (or their view of it) is the gospel. When a program is not 'truly object-oriented', whatever that means, it is considered decidedly inferior.

¶ Few fads have managed to stay popular for as long as this one, though. Object-orientation's longevity can largely be explained by the fact that the ideas at its core are very solid and useful. In this chapter, we will discuss these ideas, along with JavaScript's (rather eccentric) take on them. The above paragraphs are by no means meant to discredit these ideas. What I want to do is warn the reader against developing an unhealthy attachment to them.

¶ As the name suggests, object-oriented programming is related to objects. So far, we have used objects as loose aggregations of values, adding and altering their properties whenever we saw fit. In an object-oriented approach, objects are viewed as little worlds of their own, and the outside world may touch them only through a limited and well-defined interface, a number of specific methods and properties. The 'reached list' we used at the end of chapter 7 is an example of this: We used only three functions, makeReachedList, storeReached, and findReached to interact with it. These three functions form an interface for such objects.

¶ The Date, Error, and BinaryHeap objects we have seen also work like this. Instead of providing regular functions for working with the objects, they provide a way to create such objects, using the new keyword, and a number of methods and properties that provide the rest of the interface.

¶ One way to give an object methods is to simply attach function values to it.

var rabbit = {};
rabbit.speak = function(line) {
  print("The rabbit says '", line, "'");
};

rabbit.speak("Well, now you're asking me.");

¶ In most cases, the method will need to know who it should act on. For example, if there are different rabbits, the speak method must indicate which rabbit is speaking. For this purpose, there is a special variable called this, which is always present when a function is called, and which points at the relevant object when the function is called as a method. A function is called as a method when it is looked up as a property, and immediately called, as in object.method().

function speak(line) {
  print("The ", this.adjective, " rabbit says '", line, "'");
}
var whiteRabbit = {adjective: "white", speak: speak};
var fatRabbit = {adjective: "fat", speak: speak};

whiteRabbit.speak("Oh my ears and whiskers, how late it's getting!");
fatRabbit.speak("I could sure use a carrot right now.");

¶ I can now clarify the mysterious first argument to the apply method, for which we always used null in chapter 6. This argument can be used to specify the object that the function must be applied to. For non-method functions, this is irrelevant, hence the null.

speak.apply(fatRabbit, ["Yum."]);

¶ Functions also have a call method, which is similar to apply, but you can give the arguments for the function separately instead of as an array:

speak.call(fatRabbit, "Burp.");

¶ The new keyword provides a convenient way of creating new objects. When a function is called with the word new in front of it, its this variable will point at a new object, which it will automatically return (unless it explicitly returns something else). Functions used to create new objects like this are called constructors. Here is a constructor for rabbits:

function Rabbit(adjective) {
  this.adjective = adjective;
  this.speak = function(line) {
    print("The ", this.adjective, " rabbit says '", line, "'");
  };
}

var killerRabbit = new Rabbit("killer");
killerRabbit.speak("GRAAAAAAAAAH!");

¶ It is a convention, among JavaScript programmers, to start the names of constructors with a capital letter. This makes it easy to distinguish them from other functions.

¶ Why is the new keyword even necessary? After all, we could have simply written this:

function makeRabbit(adjective) {
  return {
    adjective: adjective,
    speak: function(line) {/*etc*/}
  };
}

var blackRabbit = makeRabbit("black");

¶ But that is not entirely the same. new does a few things behind the scenes. For one thing, our killerRabbit has a property called constructor, which points at the Rabbit function that created it. blackRabbit also has such a property, but it points at the Object function.

show(killerRabbit.constructor);
show(blackRabbit.constructor);

¶ Where did the constructor property come from? It is part of the prototype of a rabbit. Prototypes are a powerful, if somewhat confusing, part of the way JavaScript objects work. Every object is based on a prototype, which gives it a set of inherent properties. The simple objects we have used so far are based on the most basic prototype, which is associated with the Object constructor. In fact, typing {} is equivalent to typing new Object().

var simpleObject = {};
show(simpleObject.constructor);
show(simpleObject.toString);

¶ toString is a method that is part of the Object prototype. This means that all simple objects have a toString method, which converts them to a string. Our rabbit objects are based on the prototype associated with the Rabbit constructor. You can use a constructor's prototype property to get access to, well, their prototype:

show(Rabbit.prototype);
show(Rabbit.prototype.constructor);

¶ Every function automatically gets a prototype property, whose constructor property points back at the function. Because the rabbit prototype is itself an object, it is based on the Object prototype, and shares its toString method.

show(killerRabbit.toString == simpleObject.toString);

¶ Even though objects seem to share the properties of their prototype, this sharing is one-way. The properties of the prototype influence the object based on it, but the properties of this object never change the prototype.

¶ The precise rules are this: When looking up the value of a property, JavaScript first looks at the properties that the object itself has. If there is a property that has the name we are looking for, that is the value we get. If there is no such property, it continues searching the prototype of the object, and then the prototype of the prototype, and so on. If no property is found, the value undefined is given. On the other hand, when setting the value of a property, JavaScript never goes to the prototype, but always sets the property in the object itself.

Rabbit.prototype.teeth = "small";
show(killerRabbit.teeth);
killerRabbit.teeth = "long, sharp, and bloody";
show(killerRabbit.teeth);
show(Rabbit.prototype.teeth);

¶ This does mean that the prototype can be used at any time to add new properties and methods to all objects based on it. For example, it might become necessary for our rabbits to dance.

Rabbit.prototype.dance = function() {
  print("The ", this.adjective, " rabbit dances a jig.");
};

killerRabbit.dance();

¶ And, as you might have guessed, the prototypical rabbit is the perfect place for values that all rabbits have in common, such as the speak method. Here is a new approach to the Rabbit constructor:

function Rabbit(adjective) {
  this.adjective = adjective;
}
Rabbit.prototype.speak = function(line) {
  print("The ", this.adjective, " rabbit says '", line, "'");
};

var hazelRabbit = new Rabbit("hazel");
hazelRabbit.speak("Good Frith!");

¶ The fact that all objects have a prototype and receive some properties from this prototype can be tricky. It means that using an object to store a set of things, such as the cats from chapter 4, can go wrong. If, for example, we wondered whether there is a cat called "constructor", we would have checked it like this:

var noCatsAtAll = {};
if ("constructor" in noCatsAtAll)
  print("Yes, there definitely is a cat called 'constructor'.");

¶ This is problematic. A related problem is that it can often be practical to extend the prototypes of standard constructors such as Object and Array with new useful functions. For example, we could give all objects a method called properties, which returns an array with the names of the (non-hidden) properties that the object has:

Object.prototype.properties = function() {
  var result = [];
  for (var property in this)
    result.push(property);
  return result;
};

var test = {x: 10, y: 3};
show(test.properties());

¶ And that immediately shows the problem. Now that the Object prototype has a property called properties, looping over the properties of any object, using for and in, will also give us that shared property, which is generally not what we want. We are interested only in the properties that the object itself has.

¶ Fortunately, there is a way to find out whether a property belongs to the object itself or to one of its prototypes. Unfortunately, it does make looping over the properties of an object a bit clumsier. Every object has a method called hasOwnProperty, which tells us whether the object has a property with a given name. Using this, we could rewrite our properties method like this:

Object.prototype.properties = function() {
  var result = [];
  for (var property in this) {
    if (this.hasOwnProperty(property))
      result.push(property);
  }
  return result;
};

var test = {"Fat Igor": true, "Fireball": true};
show(test.properties());

¶ And of course, we can abstract that into a higher-order function. Note that the action function is called with both the name of the property and the value it has in the object.

function forEachIn(object, action) {
  for (var property in object) {
    if (object.hasOwnProperty(property))
      action(property, object[property]);
  }
}

var chimera = {head: "lion", body: "goat", tail: "snake"};
forEachIn(chimera, function(name, value) {
  print("The ", name, " of a ", value, ".");
});

¶ But, what if we find a cat named hasOwnProperty? (You never know.) It will be stored in the object, and the next time we want to go over the collection of cats, calling object.hasOwnProperty will fail, because that property no longer points at a function value. This can be solved by doing something even uglier:

function forEachIn(object, action) {
  for (var property in object) {
    if (Object.prototype.hasOwnProperty.call(object, property))
      action(property, object[property]);
  }
}

var test = {name: "Mordecai", hasOwnProperty: "Uh-oh"};
forEachIn(test, function(name, value) {
  print("Property ", name, " = ", value);
});

¶ (Note: This example does not currently work correctly in Internet Explorer 8, which apparently has some problems with overriding built-in prototype properties.)

¶ Here, instead of using the method found in the object itself, we get the method from the Object prototype, and then use call to apply it to the right object. Unless someone actually messes with the method in Object.prototype (don't do that), this should work correctly.

¶ hasOwnProperty can also be used in those situations where we have been using the in operator to see whether an object has a specific property. There is one more catch, however. We saw in chapter 4 that some properties, such as toString, are 'hidden', and do not show up when going over properties with for/in. It turns out that browsers in the Gecko family (Firefox, most importantly) give every object a hidden property named __proto__, which points to the prototype of that object. hasOwnProperty will return true for this one, even though the program did not explicitly add it. Having access to the prototype of an object can be very convenient, but making it a property like that was not a very good idea. Still, Firefox is a widely used browser, so when you write a program for the web you have to be careful with this. There is a method propertyIsEnumerable, which returns false for hidden properties, and which can be used to filter out strange things like __proto__. An expression such as this one can be used to reliably work around this:

var object = {foo: "bar"};
show(Object.prototype.hasOwnProperty.call(object, "foo") &&
     Object.prototype.propertyIsEnumerable.call(object, "foo"));

¶ Nice and simple, no? This is one of the not-so-well-designed aspects of JavaScript. Objects play both the role of 'values with methods', for which prototypes work great, and 'sets of properties', for which prototypes only get in the way.

¶ Writing the above expression every time you need to check whether a property is present in an object is unworkable. We could put it into a function, but an even better approach is to write a constructor and a prototype specifically for situations like this, where we want to approach an object as just a set of properties. Because you can use it to look things up by name, we will call it a Dictionary.

function Dictionary(startValues) {
  this.values = startValues || {};
}
Dictionary.prototype.store = function(name, value) {
  this.values[name] = value;
};
Dictionary.prototype.lookup = function(name) {
  return this.values[name];
};
Dictionary.prototype.contains = function(name) {
  return Object.prototype.hasOwnProperty.call(this.values, name) &&
    Object.prototype.propertyIsEnumerable.call(this.values, name);
};
Dictionary.prototype.each = function(action) {
  forEachIn(this.values, action);
};

var colours = new Dictionary({Grover: "blue",
                              Elmo: "orange",
                              Bert: "yellow"});
show(colours.contains("Grover"));
show(colours.contains("constructor"));
colours.each(function(name, colour) {
  print(name, " is ", colour);
});

¶ Now the whole mess related to approaching objects as plain sets of properties has been 'encapsulated' in a convenient interface: one constructor and four methods. Note that the values property of a Dictionary object is not part of this interface, it is an internal detail, and when you are using Dictionary objects you do not need to directly use it.

¶ Whenever you write an interface, it is a good idea to add a comment with a quick sketch of what it does and how it should be used. This way, when someone, possibly yourself three months after you wrote it, wants to work with the interface, they can quickly see how to use it, and do not have to study the whole program.

¶ Most of the time, when you are designing an interface, you will soon find some limitations and problems in whatever you came up with, and change it. To prevent wasting your time, it is advisable to document your interfaces only after they have been used in a few real situations and proven themselves to be practical. ― Of course, this might make it tempting to forget about documentation altogether. Personally, I treat writing documentation as a 'finishing touch' to add to a system. When it feels ready, it is time to write something about it, and to see if it sounds as good in English (or whatever language) as it does in JavaScript (or whatever programming language).

¶ The distinction between the external interface of an object and its internal details is important for two reasons. Firstly, having a small, clearly described interface makes an object easier to use. You only have to keep the interface in mind, and do not have to worry about the rest unless you are changing the object itself.

¶ Secondly, it often turns out to be necessary or practical to change something about the internal implementation of an object type1, to make it more efficient, for example, or to fix some problem. When outside code is accessing every single property and detail in the object, you can not change any of them without also updating a lot of other code. If outside code only uses a small interface, you can do what you want, as long as you do not change the interface.

¶ Some people go very far in this. They will, for example, never include properties in the interface of object, only methods ― if their object type has a length, it will be accessible with the getLength method, not the length property. This way, if they ever want to change their object in such a way that it no longer has a length property, for example because it now has some internal array whose length it must return, they can update the function without changing the interface.

¶ My own take is that in most cases this is not worth it. Adding a getLength method which only contains return this.length; mostly just adds meaningless code, and, in most situations, I consider meaningless code a bigger problem than the risk of having to occasionally change the interface to my objects.

¶ Adding new methods to existing prototypes can be very convenient. Especially the Array and String prototypes in JavaScript could use a few more basic methods. We could, for example, replace forEach and map with methods on arrays, and make the startsWith function we wrote in chapter 4 a method on strings.

¶ However, if your program has to run on the same web-page as another program (either written by you or by someone else) which uses for/in naively ― the way we have been using it so far ― then adding things to prototypes, especially the Object and Array prototype, will definitely break something, because these loops will suddenly start seeing those new properties. For this reason, some people prefer not to touch these prototypes at all. Of course, if you are careful, and you do not expect your code to have to coexist with badly-written code, adding methods to standard prototypes is a perfectly good technique.

¶ In this chapter we are going to build a virtual terrarium, a tank with insects moving around in it. There will be some objects involved (this is, after all, the chapter on object-oriented programming). We will take a rather simple approach, and make the terrarium a two-dimensional grid, like the second map in chapter 7. On this grid there are a number of bugs. When the terrarium is active, all the bugs get a chance to take an action, such as moving, every half second.

¶ Thus, we chop both time and space into units with a fixed size ― squares for space, half seconds for time. This usually makes things easier to model in a program, but of course has the drawback of being wildly inaccurate. Fortunately, this terrarium-simulator is not required to be accurate in any way, so we can get away with it.

¶ A terrarium can be defined with a 'plan', which is an array of strings. We could have used a single string, but because JavaScript strings must stay on a single line it would have been a lot harder to type.

var thePlan =
  ["############################",
   "#      #    #      o      ##",
   "#                          #",
   "#          #####           #",
   "##         #   #    ##     #",
   "###           ##     #     #",
   "#           ###      #     #",
   "#   ####                   #",
   "#   ##       o             #",
   "# o  #         o       ### #",
   "#    #                     #",
   "############################"];

¶ The "#" characters are used to represent the walls of the terrarium (and the ornamental rocks lying in it), the "o"s represent bugs, and the spaces are, as you might have guessed, empty space.

¶ Such a plan-array can be used to create a terrarium-object. This object keeps track of the shape and content of the terrarium, and lets the bugs inside move. It has four methods: Firstly toString, which converts the terrarium back to a string similar to the plan it was based on, so that you can see what is going on inside it. Then there is step, which allows all the bugs in the terrarium to move one step, if they so desire. And finally, there are start and stop, which control whether the terrarium is 'running'. When it is running, step is automatically called every half second, so the bugs keep moving.