====================
Introduction / intro
====================
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. Subtract the number 11 from the value in memory location 2
5. If the value in memory location 2 is the number 0, continue with instruction 9
6. Add the value of memory location 1 to memory location 0
7. Add the number 1 to the value of memory location 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 |
http://steve-yegge.blogspot.com/2007/02/next-big-language.html] 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 code##. 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.
## 'Code' is the substance that programs are made of. Every piece of a
program, whether it is a single line or the whole thing, can be
referred to as 'code'.
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), the pages in this book will show a 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.
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.
---
Finally, the little face in the top-left corner of your screen can be
used to send me, the author, a message. If you have a comment, or you
find a passage ridiculously confusing, or you just spot a spelling
error, tell me about it. Sending a message can be done without leaving
the page, so it won't interrupt your reading.
==============================================================
Basic JavaScript: values, variables, and control flow / basics
==============================================================
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 bits##, 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 _value_s. 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.
## Bits are any kinds of two-valued things, usually described as |0|s
and |1|s. Inside the computer, they take forms like a high or low
electrical charge, a strong or weak signal, a shiny or dull spot on
the surface of a CD.
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 bits##:
## If you were expecting something like |10010000| here -- good call,
but read on. JavaScript's numbers are not stored as integers.
] 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^3 = 1000 different
numbers. With 64 binary digits, 2^64 different numbers can be written.
This is a lot, more than 10^19 (a one with nineteen zeroes).
Not all whole numbers below 10^19 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 bits##. Any whole number less than 2^52, which is over
10^15, 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.
## Actually, 53, because of a trick that can be used to get one bit
for free. Look up the 'IEEE 754' format if you are curious about the
details.
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^8 = 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 @_applying_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,
@_newline_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 character##.
## When you type string values at the console, you'll notice that they
will come back with the quotes and backslashes the way you typed them.
To get special characters to show properly, you can do |print("a\nb")|
-- why this works, we will see in a moment.
>> "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 operator_s,
while those that take one are called _unary operator_s. 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|.
***
>> ((4 >= 6) || ("grass" != "green")) &&
>> !(((12 * 2) == 144) && true)
Is this true? For readability, there are a lot of unnecessary
parentheses in there. This simple version means the same thing:
>> (4 >= 6 || "grass" != "green") &&
>> !(12 * 2 == 144 && true)
///
Yes, it is |true|. You can reduce it step by step like this:
>> (false || true) && !(false && true)
>> true && !false
>> true
I hope you noticed that |"grass" != "green"| is |true|. Grass may be
green, but it is not equal to green.
---
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 effect_s'. The statements in
the example above just produce the values |1| and |true|, and then
immediately throw them into the bit bucket##. This leaves no
impression on the world at all, and is not a side effect.
## The bit bucket is supposedly the place where old bits are kept. On
some systems, the programmer has to manually empty it now and then.
Fortunately, JavaScript comes with a fully-automatic bit-recycling
system.
---
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 one. 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("Also, your hair is on fire.");
@_|()|_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. The string value between the parentheses is
given to the function, which uses it as the text to show in the dialog
window. Values given to functions are called _parameter_s or
_argument_s. |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 two arguments and gives back the biggest of
the two:
> alert(Math.max(2, 4));
@_|Math.min|_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);
\\Cfunctions 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 _block_s. 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|.
*** power2
Use the techniques shown so far to write a program that calculates and
shows the value of 2^10 (2 to the 10th power). You are, obviously, not
allowed to use a cheap trick like just writing |2 * 2 * ...|.
If you are having trouble with this, try to see it in terms of the
even-numbers example. The program must perform an action a certain
amount of times. A counter variable with a |while| loop can be used
for that. Instead of printing the counter, the program must multiply
something by 2. This something should be another variable, in which
the result value is built up.
Don't worry if you don't quite see how this would work yet. Even if
you perfectly understand all the techniques this chapter covers, it
can be hard to apply them to a specific problem. Reading and writing
code will help develop a feeling for this, so study the solution, and
try the next exercise.
///
> var result = 1;
> var counter = 0;
> while (counter < 10) {
> result = result * 2;
> counter = counter + 1;
> }
> show(result);
The counter could also start at |1| and check for |<= 10|, but, for
reasons that will become apparent later on, it is a good idea to get
used to counting from 0.
Obviously, your own solutions aren't required to be precisely the same
as mine. They should work. And if they are very different, make sure
you also understand my solution.
***
With some slight modifications, the solution to the previous exercise
can be made to draw a triangle. And when I say 'draw a triangle' I
mean 'print out some text that almost looks like a triangle when you
squint'.
Print out ten lines. On the first line there is one '#' character. On
the second there are two. And so on.
How does one get a string with X '#' characters in it? One way is to
build it every time it is needed with an 'inner loop' -- a loop inside
a loop. A simpler way is to reuse the string that the previous
iteration of the loop used, and add one character to it.
///
> var line = "";
> var counter = 0;
> while (counter < 10) {
> line = line + "#";
> print(line);
> counter = counter + 1;
> }
---
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 the tab key 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 \\coo. 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
_keyword_s. There are also a number of @_reserved words_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.
***
Rewrite the solutions of the previous two exercises to use |for|
instead of |while|.
///
> var result = 1;
> for (var counter = 0; counter < 10; counter = counter + 1)
> result = result * 2;
> show(result);
Note that even if no block is opened with a '|{|', the statement in
the loop is still indented two spaces to make it clear that it
'belongs' to the line above it.
> var line = "";
> for (var counter = 0; counter < 10; counter = counter + 1) {
> line = line + "#";
> print(line);
> }
---
@_|+=|_@_|-=|_@_|/=|_@_|*=|_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 gotten 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.
***
Write a program to ask yourself, using |prompt|, what the value of 2 +
2 is. If the answer is "4", use |alert| to say something praising. If
it is "3" or "5", say "Almost!". In other cases, say something mean.
///
> var answer = prompt("You! What is the value of 2 + 2?", "");
> if (answer == "4")
> alert("You must be a genius or something.");
> else if (answer == "3" || answer == "5")
> alert("Almost!");
> else
> alert("You're an embarrassment.");
---
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 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.
***
Add a |while| and optionally a |break| to your solution for the
previous exercise, so that it keeps repeating the question until a
correct answer is given.
Note that |while (true) ...| can be used to create a loop that does
not end on its own account. This is a bit silly, you ask the program
to loop as long as |true| is |true|, but it is a useful trick.
///
> var answer;
> while (true) {
> answer = prompt("You! What is the value of 2 + 2?", "");
> if (answer == "4") {
> alert("You must be a genius or something.");
> break;
> }
> else if (answer == "3" || answer == "5") {
> alert("Almost!");
> }
> else {
> alert("You're an embarrassment.");
> }
> }
Because the first |if|'s body now has two statements, I added braces
around all the bodies. This is a matter of taste. Having an
|if|/|else| chain where some of the bodies are blocks and others are
single statements looks a bit lopsided to me, but you can make up your
own mind about that.
Another solution, arguably nicer, but without |break|:
> var value = null;
> while (value != "4") {
> value = prompt("You! What is the value of 2 + 2?", "");
> if (value == "4")
> alert("You must be a genius or something.");
> else if (value == "3" || value == "5")
> alert("Almost!");
> else
> alert("You're an embarrassment.");
> }
---
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);
@_type conversion_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
conversion_s 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.");
=====================
Functions / functions
=====================
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
_function_s 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,
\\cfp discusses the subtleties of functions in more depth.
---
@_pure function_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 obligatory##.
## Technically, this wouldn't have been necessary, but I suppose the
designers of JavaScript felt it would clarify things if function
bodies always had braces.
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 \\epower2, 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.
***
Write a function called |absolute|, which returns the absolute value
of the number it is given as its argument. The absolute value of a
negative number is the positive version of that same number, and the
absolute value of a positive number (or zero) is that number itself.
///
> function absolute(number) {
> if (number < 0)
> return -number;
> else
> return number;
> }
>
> show(absolute(-144));
---
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 context##. 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.
## Technically, a pure function can not use the value of any external
variables. These values might change, and this could make the function
return a different value for the same arguments. In practice, the
programmer may consider some variables 'constant' -- they are not
expected to change -- and consider functions that use only constant
variables pure. Variables that contain a function value are often good
examples of constant variables.
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 environment_s 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_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.
---
@_efficiency_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.
***
Write a function |greaterThan|, which takes one argument, a number,
and returns a function that represents a test. When this returned
function is called with a single number as argument, it returns a
boolean: |true| if the given number is greater than the number that
was used to create the test function, and |false| otherwise.
///
> function greaterThan(x) {
> return function(y) {
> return y > x;
> };
> }
>
> var greaterThanTen = greaterThan(10);
> show(greaterThanTen(9));
---
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.
==========================================
Data structures: Objects and Arrays / data
==========================================
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.)
---
[[[eyes.png]]]
---
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);
***
The solution for the cat problem talks about a 'set' of names. A _set_
is a collection of values in which no value may occur more than once.
If names are strings, can you think of a way to use an object to
represent a set of names?
Show how a name can be added to this set, how one can be removed, and
how you can check whether a name occurs in it.
///
This can be done by storing the content of the set as the properties
of an object. Adding a name is done by setting a property by that name
to a value, any value. Removing a name is done by deleting this
property. The |in| operator can be used to determine whether a certain
name is part of the set##.
## There are a few subtle problems with this approach, which will be
discussed and solved in \\coo. For this chapter, it works well enough.
> var set = {"Spot": true};
> // Add "White Fang" to the set
> set["White Fang"] = true;
> // Remove "Spot"
> delete set["Spot"];
> // See if "Asoka" is in the set
> show("Asoka" in set);
---
@_mutability_Object values, apparently, can change. The types of
values discussed in \\cbasics 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 \\coo 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. \\Cxhr 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 _array_s, 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.
*** range
Write a function |range| that takes one argument, a positive number,
and returns an array containing all numbers from 0 up to and including
the given number.
An empty array can be created by simply typing |[]|. Also remember
that adding properties to an object, and thus also to an array, can be
done by assigning them a value with the |=| operator. The |length|
property is automatically updated when elements are added.
///
> function range(upto) {
> var result = [];
> for (var i = 0; i <= upto; i++)
> result[i] = i;
> return result;
> }
> show(range(4));
Instead of naming the loop variable |counter| or |current|, as I have
been doing so far, it is now called simply |i|. Using single letters,
usually |i|, |j|, or |k| for loop variables is a widely spread habit
among programmers. It has its origin mostly in laziness: We'd rather
type one character than seven, and names like |counter| and |current|
do not really clarify the meaning of the variable much.
If a program uses too many meaningless single-letter variables, it can
become unbelievably confusing. In my own programs, I try to only do
this in a few common cases. Small loops are one of these cases. If the
loop contains another loop, and that one also uses a variable named
|i|, the inner loop will modify the variable that the outer loop is
using, and everything will break. One could use |j| for the inner
loop, but in general, when the body of a loop is big, you should come
up with a variable name that has some clear meaning.
---
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 \\coo.
Properties that contain functions are generally called _method_s, 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 no 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.
***
|split| and |join| are not precisely each other's inverse.
|string.split(x).join(x)| always produces the original value, but
|array.join(x).split(x)| does not. Can you give an example of an array
where |.join(" ").split(" ")| produces a different value?
///
> var array = ["a", "b", "c d"];
> show(array.join(" ").split(" "));
---
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");
***
Write a function called |startsWith| that takes two arguments, both
strings. It returns |true| when the first argument starts with the
characters in the second argument, and |false| otherwise.
///
> function startsWith(string, pattern) {
> return string.slice(0, pattern.length) == pattern;
> }
>
> show(startsWith("rotation", "rot"));
---
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 case_s, 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.
***
Can you write a function |catNames| that takes a paragraph as an
argument and returns an array of names?
Strings have an _|indexOf|_ method that can be used to find the
(first) position of a character or sub-string within that string. Also,
when |slice| is given only one argument, it will return the part of
the string from the given position all the way to the end.
It can be helpful to use the console to 'explore' functions. For
example, type |"foo: bar".indexOf(":")| and see what you get.
///
> function catNames(paragraph) {
> var colon = paragraph.indexOf(":");
> return paragraph.slice(colon + 2).split(", ");
> }
>
> show(catNames("born 20/09/2004 (mother Yellow Bess): " +
> "Doctor Hobbles the 2nd, Noog"));
The tricky part, which the original description of the algorithm
ignored, is dealing with spaces after the colon and the commas.
The |+ 2| used when slicing the string is needed to leave out the
colon itself and the space after it. The argument to |split| contains
both a comma and a space, because that is what the names are really
separated by, rather than just a comma.
This function does not do any checking for problems. We assume, in
this case, that the input is always correct.
---
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 _constructor_s,
and in \\coo 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());
***
] "died 27/04/2006: Black Leclère"
The date part is always in the exact same place of a paragraph. How
convenient. Write a function |extractDate| that takes such a paragraph
as its argument, extracts the date, and returns it as a date object.
///
> function extractDate(paragraph) {
> function numberAt(start, length) {
> return Number(paragraph.slice(start, start + length));
> }
> return new Date(numberAt(11, 4), numberAt(8, 2) - 1,
> numberAt(5, 2));
> }
>
> show(extractDate("died 27-04-2006: Black Leclère"));
It would work without the calls to |Number|, but as mentioned earlier,
I prefer not to use strings as if they are numbers. The inner function
was introduced to prevent having to repeat the |Number| and |slice|
part three times.
Note the |- 1| for the month number. Like most people, Aunt Emily
counts her months from 1, so we have to adjust the value before giving
it to the |Date| constructor. (The day number does not have this
problem, since |Date| objects count days in the usual human way.)
In \\cregexp we will see a more practical and robust way of extracting
pieces from strings that have a fixed structure.
---
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.
***
The thing that |extractMother| does can be expressed in a more general
way. Write a function |between| that takes three arguments, all of
which are strings. It will return the part of the first argument that
occurs between the patterns given by the second and the third
arguments.
So |between("born 15/11/2003 (mother Spot): White Fang", "(mother ",
")")| gives |"Spot"|.
|between("bu ] boo [ bah ] gzz", "[ ", " ]")| returns |"bah"|.
To make that second test work, it can be useful to know that |indexOf|
can be given a second, optional parameter that specifies at which
point it should start searching.
///
> function between(string, start, end) {
> var startAt = string.indexOf(start) + start.length;
> var endAt = string.indexOf(end, startAt);
> return string.slice(startAt, endAt);
> }
> show(between("bu ] boo [ bah ] gzz", "[ ", " ]"));
---
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 \\cerror, 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.
***
The |formatDate| function used by |catInfo| does not add a zero before
the month and the day part when these are only one digit long. Write a
new version that does this.
///
> function formatDate(date) {
> function pad(number) {
> if (number < 10)
> return "0" + number;
> else
> return number;
> }
> return pad(date.getDate()) + "/" + pad(date.getMonth() + 1) +
> "/" + date.getFullYear();
> }
> print(formatDate(new Date(2000, 0, 1)));
***
Write a function |oldestCat| which, given an object containing cats as
its argument, returns the name of the oldest living cat.
///
> function oldestCat(data) {
> var oldest = null;
>
> for (var name in data) {
> var cat = data[name];
> if (!("death" in cat) &&
> (oldest == null || oldest.birth > cat.birth))
> oldest = cat;
> }
>
> if (oldest == null)
> return null;
> else
> return oldest.name;
> }
>
> print(oldestCat(catData));
The condition in the |if| statement might seem a little intimidating.
It can be read as 'only store the current cat in the variable |oldest|
if it is not dead, and |oldest| is either |null| or a cat that was
born after the current cat'.
Note that this function returns |null| when there are no living cats
in |data|. What does your solution do in that case?
---
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));
***
Extend the |range| function from \\erange to take a second, optional
argument. If only one argument is given, it behaves as earlier and
produces a range from 0 to the given number. If two arguments are
given, the first indicates the start of the range, the second the end.
///
> function range(start, end) {
> if (arguments.length < 2) {
> end = start;
> start = 0;
> }
> var result = [];
> for (var i = start; i <= end; i++)
> result.push(i);
> return result;
> }
>
> show(range(4));
> show(range(2, 4));
The optional argument does not work precisely like the one in the
|add| example above. When it is not given, the first argument takes
the role of |end|, and |start| becomes |0|.
***
You may remember this line of code from the introduction:
!> print(sum(range(1, 10)));
We have |range| now. All we need to make this line work is a |sum|
function. This function takes an array of numbers, and returns their
sum. Write it, it should be easy.
///
> function sum(numbers) {
> var total = 0;
> for (var i = 0; i < numbers.length; i++)
> total += numbers[i];
> return total;
> }
>
> print(sum(range(1, 10)));
---
\\Cbasics 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.
@_|Math.round|_@_|Math.floor|_@_|Math.ceil|_|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 | https://developer.mozilla.org/en/JavaScript/Reference/].
---
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@_hidden properties_. 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 \\coo, it would be nice to be able to add methods to objects
without having them show up in our |for|/|in| loops.
---
@_read-only properties_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);
======================
Error Handling / error
======================
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 \\cdata 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
\\cfunctions. 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 \\coo.
===========================
Functional Programming / fp
===========================
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.
@_abstraction_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 \\cdata 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_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
\\cmodularity).
There are other popular approaches to abstraction, most notably
object-oriented programming, the subject of \\coo.
---
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 \\cdata 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
function_s. By operating on functions, they can talk about actions on
a whole new level. The |makeAddFunction| function from \\cfunctions 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 \\coo, 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.
***
Write a function |countZeroes|, which takes an array of numbers as its
argument and returns the amount of zeroes that occur in it. Use
|reduce|.
Then, write the higher-order function |count|, which takes an array
and a test function as arguments, and returns the amount of elements
in the array for which the test function returned |true|. Re-implement
|countZeroes| using this function.
///
> function countZeroes(array) {
> function counter(total, element) {
> return total + (element === 0 ? 1 : 0);
> }
> return reduce(counter, 0, array);
> }
@_|?:|_The weird part, with the question mark and the colon, uses a
new operator. In \\cbasics we have seen unary and binary operators.
This one is ternary -- it acts on three values. Its effect resembles
that of |if|/|else|, except that, where |if| conditionally executes
statements, this one conditionally chooses expressions. The first
part, before the question mark, is the condition. If this condition is
|true|, the expression after the question mark is chosen, |1| in this
case. If it is |false|, the part after the colon, |0| in this case, is
chosen.
Use of this operator can make some pieces of code much shorter. When
the expressions inside it get very big, or you have to make more
decisions inside the conditional parts, just using plain |if| and
|else| is usually more readable.
Here is the solution that uses a |count| function, with a function
that produces equality-testers included to make the final
|countZeroes| function even shorter:
> function count(test, array) {
> return reduce(function(total, element) {
> return total + (test(element) ? 1 : 0);
> }, 0, array);
> }
>
> function equals(x) {
> return function(element) {return x === element;};
> }
>
> function countZeroes(array) {
> return count(equals(0), array);
> }
---
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 '_tag_s'. 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:
]
]
] A quote
]
]
] A quote
]
] 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.
] -- Bjarne Stroustrup
]
] Mr. Stroustrup is the inventor of the C++ programming
] language, but quite an insightful person nevertheless.
] Also, here is a picture of an ostrich:
] 
]
]
Elements that contain text or other tags are first opened with
||, and afterwards finished with ||. 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 numbers## in their place.
5. Wrap each piece into the correct HTML tags.
6. Combine everything into a single HTML document.
## Like this...
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 \\cdata, you will realise that this
will do the trick:
> var paragraphs = recluseFile().split("\n\n");
> print("Found ", paragraphs.length, " paragraphs.");
***
Write a function |processParagraph| that, when given a paragraph
string as its argument, checks whether this paragraph is a header. If
it is, it strips off the '%' characters and counts their number. Then,
it returns an object with two properties, |content|, which contains
the text inside the paragraph, and |type|, which contains the tag that
this paragraph must be wrapped in, |"p"| for regular paragraphs,
|"h1"| for headers with one '%', and |"hX"| for headers with |X| '%'
characters.
Remember that strings have a |charAt| method that can be used to look
at a specific character inside them.
///
> function processParagraph(paragraph) {
> var header = 0;
> while (paragraph.charAt(0) == "%") {
> paragraph = paragraph.slice(1);
> header++;
> }
>
> return {type: (header == 0 ? "p" : "h" + header),
> content: paragraph};
> }
>
> show(processParagraph(paragraphs[0]));
---
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.
***
Build a function |splitParagraph| which, given a paragraph string,
returns an array of paragraph fragments. Think of a good way to
represent the fragments.
The method |indexOf|, which searches for a character or sub-string in
a string and returns its position, or |-1| if not found, will probably
be useful in some way here.
This is a tricky algorithm, and there are many not-quite-correct or
way-too-long ways to describe it. If you run into problems, just think
about it for a minute. Try to write inner functions that perform the
smaller actions that make up the algorithm.
///
Here is one possible solution:
> function splitParagraph(text) {
> function indexOrEnd(character) {
> var index = text.indexOf(character);
> return index == -1 ? text.length : index;
> }
>
> function takeNormal() {
> var end = reduce(Math.min, text.length,
> map(indexOrEnd, ["*", "{"]));
> var part = text.slice(0, end);
> text = text.slice(end);
> return part;
> }
>
> function takeUpTo(character) {
> var end = text.indexOf(character, 1);
> if (end == -1)
> throw new Error("Missing closing '" + character + "'");
> var part = text.slice(1, end);
> text = text.slice(end + 1);
> return part;
> }
>
> var fragments = [];
>
> while (text != "") {
> if (text.charAt(0) == "*")
> fragments.push({type: "emphasised",
> content: takeUpTo("*")});
> else if (text.charAt(0) == "{")
> fragments.push({type: "footnote",
> content: takeUpTo("}")});
> else
> fragments.push({type: "normal",
> content: takeNormal()});
> }
> return fragments;
> }
Note the over-eager use of |map| and |reduce| in the |takeNormal|
function. This is a chapter about functional programming, so program
functionally we will! Can you see how this works? The |map| produces
an array of positions where the given characters were found, or the
end of the string if they were not found, and the |reduce| takes the
minimum of them, which is the next point in the string that we have to
look at.
If you'd write that out without mapping and reducing you'd get
something like this:
] var nextAsterisk = text.indexOf("*");
] var nextBrace = text.indexOf("{");
] var end = text.length;
] if (nextAsterisk != -1)
] end = nextAsterisk;
] if (nextBrace != -1 && nextBrace < end)
] end = nextBrace;
Which is even more hideous. Most of the time, when a decision has to
be made based on a series of things, even if there are only two of
them, writing it as array operations is nicer than handling every
value in a separate |if| statement. (Fortunately, \\cregexp describes
an easier way to ask for the first occurrence of 'this or that
character' in a string.)
If you wrote a |splitParagraph| that stored fragments in a different
way than the solution above, you might want to adjust it, because the
functions in the rest of the chapter assume that fragments are objects
with |type| and |content| properties.
---
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 = "" + text + "";
> 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)]);
> }
***
Looking back at the example HTML document if necessary, write an
|image| function which, when given the location of an image file, will
create an |img| HTML element.
///
> function image(src) {
> return tag("img", [], {src: src});
> }
---
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, ">"]];
> 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 \\cregexp. 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, \\cregexp 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("");
> }
> }
>
> 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.)
***
Write a function |renderFragment|, and use that to implement another
function |renderParagraph|, which takes a paragraph object (with the
footnotes already filtered out), and produces the correct HTML element
(which might be a paragraph or a header, depending on the |type|
property of the paragraph object).
This function might come in useful for rendering the footnote
references:
> function footnote(number) {
> return tag("sup", [link("#footnote" + number,
> String(number))]);
> }
A |sup| tag will show its content as 'superscript', which means it
will be smaller and a little higher than other text. The target of the
link will be something like |"#footnote1"|. Links that contain a '#'
character refer to 'anchors' within a page, and in this case we will
use them to make it so that clicking on the footnote link will take
the reader to the bottom of the page, where the footnotes live.
The tag to render emphasised fragments with is |em|, and normal text
can be rendered without any extra tags.
///
> function renderParagraph(paragraph) {
> return tag(paragraph.type, map(renderFragment,
> paragraph.content));
> }
>
> function renderFragment(fragment) {
> if (fragment.type == "reference")
> return footnote(fragment.number);
> else if (fragment.type == "emphasised")
> return tag("em", [fragment.content]);
> else if (fragment.type == "normal")
> return fragment.content;
> }
---
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 anchor = tag("a", [], {name: "footnote" + footnote.number});
> var number = "[" + footnote.number + "] ";
> return tag("p", [tag("small", [anchor, number,
> 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
\\cmodularity, 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. @_|compose|_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|.
==================
Searching / search
==================
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.
[[Hiva Oa.png]]
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);
> // ...
***
In the above description, the string |"Point Kiukiu"| still occurs
three times in a row. We could make our description even more succinct
by allowing multiple roads to be specified in one line.
Write a function |makeRoads| that takes any uneven number of
arguments. The first argument is always the starting point of the
roads, and every pair of arguments after that gives an ending point
and a distance.
Do not duplicate the functionality of |makeRoad|, but have |makeRoads|
call |makeRoad| to do the actual road-making.
///
> function makeRoads(start) {
> for (var i = 1; i < arguments.length; i += 2)
> makeRoad(start, arguments[i], arguments[i + 1]);
> }
This function uses one named parameter, |start|, and gets the other
parameters from the |arguments| (quasi-) array. |i| starts at |1|
because it has to skip this first parameter. |i += 2| is short for |i
= i + 2|, as you might recall.
> var roads = {};
> makeRoads("Point Kiukiu", "Hanaiapa", 19,
> "Mt Feani", 15, "Taaoa", 15);
> makeRoads("Airport", "Hanaiapa", 6, "Mt Feani", 5,
> "Atuona", 4, "Mt Ootua", 11);
> makeRoads("Mt Temetiu", "Mt Feani", 8, "Taaoa", 4);
> makeRoads("Atuona", "Taaoa", 3, "Hanakee pearl lodge", 1);
> makeRoads("Cemetery", "Hanakee pearl lodge", 6, "Mt Ootua", 5);
> makeRoads("Hanapaoa", "Mt Ootua", 3);
> makeRoads("Puamua", "Mt Ootua", 13, "Point Teohotepapapa", 14);
>
> show(roads["Airport"]);
---
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. @_domain-specific language_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-random## 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|.
## Computers are deterministic machines: They always react in the same
way to the input they receive, so they can not produce truly random
values. Therefore, we have to make do with series of numbers that look
random, but are in fact the result of some complicated deterministic
computation.
---
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.
***
Before starting to generate routes, we need one more higher-order
function. This one is called _|filter|_. Like |map|, it takes a
function and an array as arguments, and produces a new array, but
instead of putting the results of calling the function in the new
array, it produces an array with only those values from the old array
for which the given function returns a true-like value. Write this
function.
///
> function filter(test, array) {
> var result = [];
> forEach(array, function (element) {
> if (test(element))
> result.push(element);
> });
> return result;
> }
>
> show(filter(partial(op[">"], 5), [0, 4, 8, 12]));
(If the result of that application of |filter| surprises you, remember
that the argument given to |partial| is used as the *first* argument
of the function, so it ends up to the left of the |>|.)
---
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.
***
Now that we have all possible routes, let us try to find the shortest
one. Write a function |shortestRoute| that, like |possibleRoutes|,
takes the names of a starting and ending location as arguments. It
returns a single route object, of the type that |possibleRoutes|
produces.
///
> function shortestRoute(from, to) {
> var currentShortest = null;
> forEach(possibleRoutes(from, to), function(route) {
> if (!currentShortest || currentShortest.length > route.length)
> currentShortest = route;
> });
> return currentShortest;
> }
The tricky thing in 'minimising' or 'maximising' algorithms is to not
screw up when given an empty array. In this case, we happen to know
that there is at least one road between every two places, so we could
just ignore it. But that would be a bit lame. What if the road from
Puamua to Mount Ootua, which is steep and muddy, is washed away by a
rainstorm? It would be a shame if this caused our function to break as
well, so it takes care to return |null| when no routes are found.
Then, the very functional, abstract-everything-we-can approach:
> function minimise(func, array) {
> var minScore = null;
> var found = null;
> forEach(array, function(element) {
> var score = func(element);
> if (minScore == null || score < minScore) {
> minScore = score;
> found = element;
> }
> });
> return found;
> }
>
> function getProperty(propName) {
> return function(object) {
> return object[propName];
> };
> }
>
> function shortestRoute(from, to) {
> return minimise(getProperty("length"), possibleRoutes(from, to));
> }
Unfortunately, it is three times longer than the other version. In
programs where you need to minimise several things it might be a good
idea to write the generic algorithm like this, so you can re-use it.
In most cases the first version is probably good enough.
Note the _|getProperty|_ function though, it is often useful when
doing functional programming with objects.
---
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:
[[height.png]]
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 level##. 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.
## No really, it is.
> 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)));
***
If we are going to find routes through this map, we will again need a
function to create 'signposts', lists of directions that can be taken
from a given point. Write a function |possibleDirections|, which takes
a point object as argument and returns an array of nearby points. We
can only move to adjacent points, both straight and diagonally, so
squares have a maximum of eight neighbours. Take care not to return
squares that lie outside of the map. For all we know the edge of the
map might be the edge of the world.
///
> function possibleDirections(from) {
> var mapSize = 20;
> function insideMap(point) {
> return point.x >= 0 && point.x < mapSize &&
> point.y >= 0 && point.y < mapSize;
> }
>
> var directions = [point(-1, 0), point(1, 0), point(0, -1),
> point(0, 1), point(-1, -1), point(-1, 1),
> point(1, 1), point(1, -1)];
> return filter(insideMap, map(partial(addPoints, from),
> directions));
> }
>
> show(possibleDirections(point(0, 0)));
I created a variable |mapSize|, for the sole purpose of not having to
write |20| two times. If, at some other time, we want to use this same
function for another map, it would be clumsy if the code was full of
|20|s, which all have to be changed. We could even go as far as making
the |mapSize| an argument to |possibleDirections|, so we can use the
function for different maps without changing it. I judged that that
was not necessary in this case though, such things can always be
changed when the need arises.
Then why didn't I also add a variable to hold the |0|, which also
occurs two times? I assumed that maps always start at |0|, so this one
is unlikely to ever change, and using a variable for it only adds
noise.
---
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 |push|ed 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());
\\Cbinaryheap discusses the implementation of this data structure,
which is quite interesting. After you have read \\coo, 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:
[[objectchain.png]]
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.
***
Write a function |estimatedDistance| that gives an optimistic estimate
of the distance between two points. It does not have to look at the
height data, but can assume a flat map. Remember that we are only
travelling straight and diagonally, and that we are counting the
diagonal distance between two squares as |141|.
///
> function estimatedDistance(pointA, pointB) {
> var dx = Math.abs(pointA.x - pointB.x),
> dy = Math.abs(pointA.y - pointB.y);
> if (dx > dy)
> return (dx - dy) * 100 + dy * 141;
> else
> return (dy - dx) * 100 + dx * 141;
> }
The strange formulae are used to decompose the path into a straight
and a diagonal part. If you have a path like this...
[[diagonalpath.png]]
... the path is |8| squares wide and |4| high, so you get |8 - 4 = 4|
straight moves, and |4| diagonal ones.
If you wrote a function that just computes the straight 'Pythagorean'
distance between the points, that would also work. What we need is an
optimistic estimate, and assuming you can go straight to the goal is
certainly optimistic. However, the closer the estimate is to the real
distance, the less useless paths our program has to try out.
***
We will use a binary heap for the open list. What would be a good data
structure for the reached list? This one will be used to look up
routes, given a pair of |x|, |y| coordinates. Preferably in a way that
is fast. Write three functions, |makeReachedList|, |storeReached|, and
|findReached|. The first one creates your data structure, the second
one, given a reached list, a point, and a route, stores a route in it,
and the last one, given a reached list and point, retrieves a route or
returns |undefined| to indicate that no route was found for that
point.
///
One reasonable idea would be to use an object with objects in it. One
of the coordinates in the points, say |x|, is used as a property name
for the outer object, and the other, |y|, for the inner object. This
does require some bookkeeping to handle the fact that, sometimes, the
inner object we are looking for is not there (yet).
> function makeReachedList() {
> return {};
> }
>
> function storeReached(list, point, route) {
> var inner = list[point.x];
> if (inner == undefined) {
> inner = {};
> list[point.x] = inner;
> }
> inner[point.y] = route;
> }
>
> function findReached(list, point) {
> var inner = list[point.x];
> if (inner == undefined)
> return undefined;
> else
> return inner[point.y];
> }
Another possibility is to merge the |x| and |y| of the point into a
single property name, and use that to store routes in a single object.
> function pointID(point) {
> return point.x + "-" + point.y;
> }
>
> function makeReachedList() {
> return {};
> }
>
> function storeReached(list, point, route) {
> list[pointID(point)] = route;
> }
>
> function findReached(list, point) {
> return list[pointID(point)];
> }
---
@_encapsulation_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 \\coo, 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 _search_ing 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.
================================
Object-oriented Programming / oo
================================
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 \\csearch 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 \\cfp. 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
_constructor_s. 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 \\cdata, 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());
@_|forEachIn|_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 \\cdata 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 type##, 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.
## Such types are usually called 'classes' in other programming
languages.
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 \\cdata 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 \\csearch. 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.
***
@_|Point|_The points on the grid will be represented by objects again.
In \\csearch we used three functions, |point|, |addPoints|, and
|samePoint| to work with points. This time, we will use a constructor
and two methods. Write the constructor |Point|, which takes two
arguments, the x and y coordinates of the point, and produces an
object with |x| and |y| properties. Give the prototype of this
constructor a method |add|, which takes another point as argument and
returns a *new* point whose |x| and |y| are the sum of the |x| and |y|
of the two given points. Also add a method |isEqualTo|, which takes a
point and returns a boolean indicating whether the |this| point refers
to the same coordinates as the given point.
Apart from the two methods, the |x| and |y| properties are also part
of the interface of this type of objects: Code which uses point
objects may freely retrieve and modify |x| and |y|.
///
> function Point(x, y) {
> this.x = x;
> this.y = y;
> }
> Point.prototype.add = function(other) {
> return new Point(this.x + other.x, this.y + other.y);
> };
> Point.prototype.isEqualTo = function(other) {
> return this.x == other.x && this.y == other.y;
> };
>
> show((new Point(3, 1)).add(new Point(2, 4)));
Make sure your version of |add| leaves the |this| point intact and
produces a new point object. A method which changes the current point
instead would be similar to the |+=| operator, whereas this one is
like the |+| operator.
---
When writing objects to implement a certain program, it is not always
very clear which functionality goes where. Some things are best
written as methods of your objects, other things are better expressed
as separate functions, and some things are best implemented by adding
a new type of object. To keep things clear and organised, it is
important to keep the amount of methods and responsibilities that an
object type has as small as possible. When an object does too much, it
becomes a big mess of functionality, and a formidable source of
confusion.
I said above that the terrarium object will be responsible for storing
its contents and for letting the bugs inside it move. Firstly, note
that it *lets* them move, it doesn't *make* them move. The bugs
themselves will also be objects, and these objects are responsible for
deciding what they want to do. The terrarium merely provides the
infrastructure that asks them what to do every half second, and if
they decide to move, it makes sure this happens.
Storing the grid on which the content of the terrarium is kept can get
quite complex. It has to define some kind of representation, ways to
access this representation, a way to initialise the grid from a 'plan'
array, a way to write the content of the grid to a string for the
|toString| method, and the movement of the bugs on the grid. It would
be nice if part of this could be moved into another object, so that
the terrarium object itself doesn't get too big and complex.
---
Whenever you find yourself about to mix data representation and
problem-specific code in one object, it is a good idea to try and put
the data representation code into a separate type of object. In this
case, we need to represent a grid of values, so I wrote a |Grid| type,
which supports the operations that the terrarium will need.
To store the values on the grid, there are two options. One can use an
array of arrays, like this:
> var grid = [["0,0", "1,0", "2,0"],
> ["0,1", "1,1", "2,1"]];
> show(grid[1][2]);
Or the values can all be put into a single array. In this case, the
element at |x|,|y| can be found by getting the element at position |x
+ y * width| in the array, where |width| is the width of the grid.
> var grid = ["0,0", "1,0", "2,0",
> "0,1", "1,1", "2,1"];
> show(grid[2 + 1 * 3]);
@_|Array|_I chose the second representation, because it makes it much
easier to initialise the array. |new Array(x)| produces a new array of
length |x|, filled with |undefined| values.
> function Grid(width, height) {
> this.width = width;
> this.height = height;
> this.cells = new Array(width * height);
> }
> Grid.prototype.valueAt = function(point) {
> return this.cells[point.y * this.width + point.x];
> };
> Grid.prototype.setValueAt = function(point, value) {
> this.cells[point.y * this.width + point.x] = value;
> };
> Grid.prototype.isInside = function(point) {
> return point.x >= 0 && point.y >= 0 &&
> point.x < this.width && point.y < this.height;
> };
> Grid.prototype.moveValue = function(from, to) {
> this.setValueAt(to, this.valueAt(from));
> this.setValueAt(from, undefined);
> };
***
We will also need to go over all the elements of the grid, to find the
bugs we need to move, or to convert the whole thing to a string. To
make this easy, we can use a higher-order function that takes an
action as its argument. Add the method |each| to the prototype of
|Grid|, which takes a function of two arguments as its argument. It
calls this function for every point on the grid, giving it the point
object for that point as its first argument, and the value that is on
the grid at that point as second argument.
Go over the points starting at |0|,|0|, one row at a time, so that
|1|,|0| is handled before |0|,|1|. This will make it easier to write
the |toString| function of the terrarium later. (Hint: Put a |for|
loop for the |x| coordinate inside a loop for the |y| coordinate.)
It is advisable not to muck about in the |cells| property of the grid
object directly, but use |valueAt| to get at the values. This way, if
we decide (for some reason) to use a different method for storing the
values, we only have to rewrite |valueAt| and |setValueAt|, and the
other methods can stay untouched.
///
> Grid.prototype.each = function(action) {
> for (var y = 0; y < this.height; y++) {
> for (var x = 0; x < this.width; x++) {
> var point = new Point(x, y);
> action(point, this.valueAt(point));
> }
> }
> };
---
Finally, to test the grid:
> var testGrid = new Grid(3, 2);
> testGrid.setValueAt(new Point(1, 0), "#");
> testGrid.setValueAt(new Point(1, 1), "o");
> testGrid.each(function(point, value) {
> print(point.x, ",", point.y, ": ", value);
> });
---
Before we can start to write a |Terrarium| constructor, we will have
to get a bit more specific about these 'bug objects' that will be
living inside it. Earlier, I mentioned that the terrarium will ask the
bugs what action they want to take. This will work as follows: Each
bug object has an |act| method which, when called, returns an
'action'. An action is an object with a |type| property, which names
the type of action the bug wants to take, for example |"move"|. For
most actions, the action also contains extra information, such as the
direction the bug wants to go.
Bugs are terribly myopic, they can only see the squares directly
around them on the grid. But these they can use to base their action
on. When the |act| method is called, it is given an object with
information about the surroundings of the bug in question. For each of
the eight directions, it contains a property. The property indicating
what is above the bug is called |"n"|, for North, the one
indicating what is above and to the right |"ne"|, for North-East, and
so on. To look up the direction these names refer to, the following
dictionary object is useful:
> var directions = new Dictionary(
> {"n": new Point( 0, -1),
> "ne": new Point( 1, -1),
> "e": new Point( 1, 0),
> "se": new Point( 1, 1),
> "s": new Point( 0, 1),
> "sw": new Point(-1, 1),
> "w": new Point(-1, 0),
> "nw": new Point(-1, -1)});
>
> show(new Point(4, 4).add(directions.lookup("se")));
When a bug decides to move, he indicates in which direction he wants
to go by giving the resulting action object a |direction| property
that names one of these directions. We can make a simple, stupid bug
that always just goes south, 'towards the light', like this:
> function StupidBug() {};
> StupidBug.prototype.act = function(surroundings) {
> return {type: "move", direction: "s"};
> };
---
Now we can start on the |Terrarium| object type itself. First, its
constructor, which takes a plan (an array of strings) as argument, and
initialises its grid.
> var wall = {};
>
> function Terrarium(plan) {
> var grid = new Grid(plan[0].length, plan.length);
> for (var y = 0; y < plan.length; y++) {
> var line = plan[y];
> for (var x = 0; x < line.length; x++) {
> grid.setValueAt(new Point(x, y),
> elementFromCharacter(line.charAt(x)));
> }
> }
> this.grid = grid;
> }
>
> function elementFromCharacter(character) {
> if (character == " ")
> return undefined;
> else if (character == "#")
> return wall;
> else if (character == "o")
> return new StupidBug();
> }
|wall| is an object that is used to mark the location of walls on the
grid. Like a real wall, it doesn't do much, it just sits there and
takes up space.
---
The most straightforward method of a terrarium object is |toString|,
which transforms a terrarium into a string. To make this easier, we
mark both the |wall| and the prototype of the |StupidBug| with a
property |character|, which holds the character that represents them.
> wall.character = "#";
> StupidBug.prototype.character = "o";
>
> function characterFromElement(element) {
> if (element == undefined)
> return " ";
> else
> return element.character;
> }
>
> show(characterFromElement(wall));
***
Now we can use the |each| method of the |Grid| object to build up a
string. But to make the result readable, it would be nice to have a
newline at the end of every row. The |x| coordinate of the positions
on the grid can be used to determine when the end of a line is
reached. Add a method |toString|, which takes no arguments and returns
a string which, when given to |print|, shows a nice two-dimensional
view of the terrarium.
///
> Terrarium.prototype.toString = function() {
> var characters = [];
> var endOfLine = this.grid.width - 1;
> this.grid.each(function(point, value) {
> characters.push(characterFromElement(value));
> if (point.x == endOfLine)
> characters.push("\n");
> });
> return characters.join("");
> };
And to try it out...
> var terrarium = new Terrarium(thePlan);
> print(terrarium.toString());
---
It is possible that, when trying to solve the above exercise, you have
tried to access |this.grid| inside the function that you pass as an
argument to the grid's |each| method. This will not work. Calling a
function always results in a new |this| being defined inside that
function, even when it is not used as a method. Thus, any |this|
variable outside of the function will not be visible.
Sometimes it is straightforward to work around this by storing the
information you need in a variable, like |endOfLine|, which *is*
visible in the inner function. If you need access to the whole |this|
object, you can store that in a variable too. The name |self| (or
|that|) is often used for such a variable.
But all these extra variables can get messy. Another good solution is
to use a function similar to |partial| from \\cfp. Instead of adding
arguments to a function, this one adds a |this| object, using the
first argument to the function's |apply| method:
> function bind(func, object) {
> return function(){
> return func.apply(object, arguments);
> };
> }
>
> var testArray = [];
> var pushTest = bind(testArray.push, testArray);
> pushTest("A");
> pushTest("B");
> show(testArray);
This way, you can |bind| an inner function to |this|, and it will have
the same |this| as the outer function.
***
In the expression |bind(testArray.push, testArray)| the name
|testArray| still occurs twice. Can you design a function _|method|_,
which allows you to bind an object to one of its methods *without*
naming the object twice?
///
It is possible to give the name of the method as a string. This way, the
|method| function can look up the correct function value for itself.
> function method(object, name) {
> return function() {
> object[name].apply(object, arguments);
> };
> }
>
> var pushTest = method(testArray, "push");
---
We will need |bind| (or |method|) when implementing the |step| method
of a terrarium. This method has to go over all the bugs on the grid,
ask them for an action, and execute the given action. You might be
tempted to use |each| on the grid, and just handle the bugs we come
across. But then, when a bug moves South or East, we will come across
it again in the same turn, and allow it to move again.
Instead, we first gather all the bugs into an array, and then process
them. This method gathers bugs, or other things that have an |act|
method, and stores them in objects that also contain their current
position:
> Terrarium.prototype.listActingCreatures = function() {
> var found = [];
> this.grid.each(function(point, value) {
> if (value != undefined && value.act)
> found.push({object: value, point: point});
> });
> return found;
> };
***
When asking a bug to act, we must pass it an object with information
about its current surroundings. This object will use the direction
names we saw earlier (|"n"|, |"ne"|, etcetera) as property names. Each
property holds a string of one character, as returned by
|characterFromElement|, indicating what the bug can see in that
direction.
Add a method |listSurroundings| to the |Terrarium| prototype. It takes
one argument, the point at which the bug is currently standing, and
returns an object with information about the surroundings of that
point. When the point is at the edge of the grid, use |"#"| for the
directions that go outside of the grid, so the bug will not try to
move there.
Hint: Do not write out all the directions, use the |each| method on
the |directions| dictionary.
///
> Terrarium.prototype.listSurroundings = function(center) {
> var result = {};
> var grid = this.grid;
> directions.each(function(name, direction) {
> var place = center.add(direction);
> if (grid.isInside(place))
> result[name] = characterFromElement(grid.valueAt(place));
> else
> result[name] = "#";
> });
> return result;
> };
Note the use of the |grid| variable to work around the |this| problem.
---
Both above methods are not part of the external interface of a
|Terrarium| object, they are internal details. Some languages provide
ways to explicitly declare certain methods and properties 'private',
and make it an error to use them from outside the object. JavaScript
does not, so you will have to rely on comments to describe the
interface to an object. Sometimes it can be useful to use some kind of
naming scheme to distinguish between external and internal properties,
for example by prefixing all internal ones with an underscore ('|_|').
This will make accidental uses of properties that are not part of an
object's interface easier to spot.
---
Next is one more internal method, the one that will ask a bug for an
action and carry it out. It takes an object with |object| and |point|
properties, as returned by |listActingCreatures|, as argument. For now,
it only knows about the |"move"| action:
> Terrarium.prototype.processCreature = function(creature) {
> var surroundings = this.listSurroundings(creature.point);
> var action = creature.object.act(surroundings);
> if (action.type == "move" && directions.contains(action.direction)) {
> var to = creature.point.add(directions.lookup(action.direction));
> if (this.grid.isInside(to) && this.grid.valueAt(to) == undefined)
> this.grid.moveValue(creature.point, to);
> }
> else {
> throw new Error("Unsupported action: " + action.type);
> }
> };
Note that it checks whether the chosen direction is inside of the grid
and empty, and ignores it otherwise. This way, the bugs can ask for
any action they like -- the action will only be carried out if it is
actually possible. This acts as a layer of insulation between the bugs
and the terrarium, and allows us to be less precise when writing the
bugs' |act| methods -- for example the |StupidBug| just always travels
South, regardless of any walls that might stand in its way.
---
These three internal methods then finally allow us to write the |step|
method, which gives all bugs a chance to do something (all elements
with an |act| method -- we could also give the |wall| object one if we
so desired, and make the walls walk).
> Terrarium.prototype.step = function() {
> forEach(this.listActingCreatures(),
> bind(this.processCreature, this));
> };
Now, let us make a terrarium and see whether the bugs move...
> var terrarium = new Terrarium(thePlan);
> print(terrarium);
> terrarium.step();
> print(terrarium);
---
Wait, how come the above calls |print(terrarium)| and ends up
displaying the output of our _|toString|_ method? |print| turns its
arguments to strings using the |String| function. Objects are turned
to strings by calling their |toString| method, so giving your own
object types a meaningful |toString| is a good way to make them
readable when printed out.
> Point.prototype.toString = function() {
> return "(" + this.x + "," + this.y + ")";
> };
> print(new Point(5, 5));
---
As promised, |Terrarium| objects also get |start| and |stop| methods
to start or stop their simulation. For this, we will use two functions
provided by the browser, called _|setInterval|_ and _|clearInterval|_.
The first is used to cause its first argument (a function, or a string
containing JavaScript code) to be executed periodically. Its second
argument gives the amount of milliseconds (1/1000 second) between
invocations. It returns a value that can be given to |clearInterval|
to stop its effect.
> var annoy = setInterval(function() {print("What?");}, 400);
And...
> clearInterval(annoy);
There are similar functions for one-shot time-based actions.
_|setTimeout|_ causes a function or string to be executed after a
given amount of milliseconds, and _|clearTimeout|_ cancels such an
action.
---
> Terrarium.prototype.start = function() {
> if (!this.running)
> this.running = setInterval(bind(this.step, this), 500);
> };
>
> Terrarium.prototype.stop = function() {
> if (this.running) {
> clearInterval(this.running);
> this.running = null;
> }
> };
---
Now we have a terrarium with some simple-minded bugs, and we can run
it. But to see what is going on, we have to repeatedly do
|print(terrarium)|, or we won't see what is going on. That is not very
practical. It would be nicer if it would print automatically. It would
also look better if, instead of printing a thousand terraria below
each other, we could update a single printout of the terrarium. For
that second problem, this page conveniently provides a function called
|inPlacePrinter|. It returns a function like |print| which, instead of
adding to the output, replaces its previous output.
> var printHere = inPlacePrinter();
> printHere("Now you see it.");
> setTimeout(partial(printHere, "Now you don't."), 1000);
To cause the terrarium to be re-printed every time it changes, we can
modify the |step| method as follows:
> Terrarium.prototype.step = function() {
> forEach(this.listActingCreatures(),
> bind(this.processCreature, this));
> if (this.onStep)
> this.onStep();
> };
Now, when an |onStep| property has been added to a terrarium, it will
be called on every step.
> var terrarium = new Terrarium(thePlan);
> terrarium.onStep = partial(inPlacePrinter(), terrarium);
> terrarium.start();
Note the use of |partial| -- it produces an in-place printer applied
to the terrarium. Such a printer only takes one argument, so after
partially applying it there are no arguments left, and it becomes a
function of zero arguments. That is exactly what we need for the
|onStep| property.
Don't forget to stop the terrarium when it is no longer interesting
(which should be pretty soon), so that it does not keep wasting your
computer's resources:
> terrarium.stop();
---
But who wants a terrarium with just one kind of bug, and a stupid bug
at that? Not me. It would be nice if we could add different kinds of
bugs. Fortunately, all we have to is to make the
|elementFromCharacter| function more general. Right now it contains
three cases which are typed in directly, or 'hard-coded':
> function elementFromCharacter(character) {
> if (character == " ")
> return undefined;
> else if (character == "#")
> return wall;
> else if (character == "o")
> return new StupidBug();
> }
The first two cases we can leave intact, but the last one is way too
specific. A better approach would be to store the characters and the
corresponding bug-constructors in a dictionary, and look for them
there:
> var creatureTypes = new Dictionary();
> creatureTypes.register = function(constructor) {
> this.store(constructor.prototype.character, constructor);
> };
>
> function elementFromCharacter(character) {
> if (character == " ")
> return undefined;
> else if (character == "#")
> return wall;
> else if (creatureTypes.contains(character))
> return new (creatureTypes.lookup(character))();
> else
> throw new Error("Unknown character: " + character);
> }
Note how the |register| method is added to |creatureTypes| -- this is
a dictionary object, but there is no reason why it shouldn't support
an additional method. This method looks up the character associated
with a constructor, and stores it in the dictionary. It should only be
called on constructors whose prototype does actually have a
|character| property.
|elementFromCharacter| now looks up the character it is given in
|creatureTypes|, and raises an exception when it comes across an
unknown character.
---
Here is a new bug type, and the call to register its character in
|creatureTypes|:
> function BouncingBug() {
> this.direction = "ne";
> }
> BouncingBug.prototype.act = function(surroundings) {
> if (surroundings[this.direction] != " ")
> this.direction = (this.direction == "ne" ? "sw" : "ne");
> return {type: "move", direction: this.direction};
> };
> BouncingBug.prototype.character = "%";
>
> creatureTypes.register(BouncingBug);
Can you figure out what it does?
*** drunkbug
Create a bug type called |DrunkBug| which tries to move in a random
direction every turn, never mind whether there is a wall there.
Remember the |Math.random| trick from \\csearch.
///
To pick a random direction, we will need an array of direction names.
We could of course just type |["n", "ne", ...]|, but that duplicates
information, and duplicated information makes me nervous. We could
also use the |each| method in |directions| to build the array, which
is better already.
But there is clearly a generality to be discovered here. Getting a
list of the property names in a dictionary sounds like a useful tool
to have, so we add it to the |Dictionary| prototype.
> Dictionary.prototype.names = function() {
> var names = [];
> this.each(function(name, value) {names.push(name);});
> return names;
> };
>
> show(directions.names());
A real neurotic programmer would immediately restore symmetry by also
adding a |values| method, which returns a list of the values stored in
the dictionary. But I guess that can wait until we [need it |
http://www.c2.com/cgi/wiki?YouArentGonnaNeedIt].
Here is a way to take a random element from an array:
> function randomElement(array) {
> if (array.length == 0)
> throw new Error("The array is empty.");
> return array[Math.floor(Math.random() * array.length)];
> }
>
> show(randomElement(["heads", "tails"]));
And the bug itself:
> function DrunkBug() {};
> DrunkBug.prototype.act = function(surroundings) {
> return {type: "move",
> direction: randomElement(directions.names())};
> };
> DrunkBug.prototype.character = "~";
>
> creatureTypes.register(DrunkBug);
---
So, let us test out our new bugs:
> var newPlan =
> ["############################",
> "# #####",
> "# ## ####",
> "# #### ~ ~ ##",
> "# ## ~ #",
> "# #",
> "# ### #",
> "# ##### #",
> "# ### #",
> "# % ### % #",
> "# ####### #",
> "############################"];
>
> var terrarium = new Terrarium(newPlan);
> terrarium.onStep = partial(inPlacePrinter(), terrarium);
> terrarium.start();
Notice the bouncing bugs bouncing off the drunk ones? Pure drama.
Anyway, when you are done watching this fascinating show, shut it
down:
> terrarium.stop();
---
We now have two kinds of objects that both have an |act| method and a
|character| property. Because they share these traits, the terrarium
can approach them in the same way. This allows us to have all kinds of
bugs, without changing anything about the terrarium code. This
technique is called _polymorphism_, and it is arguably the most
powerful aspect of object-oriented programming.
The basic idea of polymorphism is that when a piece of code is written
to work with objects that have a certain interface, any kind of object
that happens to support this interface can be plugged into the code,
and it will just work. We already saw simple examples of this, like
the |toString| method on objects. All objects that have a meaningful
|toString| method can be given to |print| and other functions that
need to convert values to strings, and the correct string will be
produced, no matter how their |toString| method chooses to build this
string.
Similarly, |forEach| works on both real arrays and the pseudo-arrays
found in the |arguments| variable, because all it needs is a |length|
property and properties called |0|, |1|, and so on, for the elements
of the array.
---
To make life in the terrarium more life-like, we will add to it the
concepts of food and reproduction. Each living thing in the terrarium
gets a new property, |energy|, which is reduced by performing actions,
and increased by eating things. When it has enough energy, a thing can
reproduce##, generating a new creature of the same kind.
## To keep things reasonably simple, the creatures in our terrarium
reproduce asexually, all by themselves.
If there are only bugs, wasting energy by moving around and eating
each other, a terrarium will soon succumb to the forces of entropy,
run out of energy, and become a lifeless wasteland. To prevent this
from happening (too quickly, at least), we add lichen to the
terrarium. Lichen do not move, they just use photo-synthesis to
gather energy, and reproduce.
To make this work, we will need a terrarium with a different
|processCreature| method. We could just replace the method of to the
|Terrarium| prototype, but we have become very attached to the
simulation of the bouncing and drunk bugs, and we would hate to break
our old terrarium.
What we can do is create a new constructor, |LifeLikeTerrarium|, whose
prototype is based on the |Terrarium| prototype, but which has a
different |processCreature| method.
---
There are a few ways to do this. We could go over the properties of
|Terrarium.prototype|, and add them one by one to
|LifeLikeTerrarium.prototype|. This is easy to do, and in some cases
it is the best solution, but in this case there is a cleaner way. If
we make the old prototype object the prototype of the new prototype
object (you may have to re-read that a few times), it will
automatically have all its properties.
@_|clone|_Unfortunately, JavaScript does not have a straightforward
way to create an object whose prototype is a certain other object. It
is possible to write a function that does this, though, by using the
following trick:
> function clone(object) {
> function OneShotConstructor(){}
> OneShotConstructor.prototype = object;
> return new OneShotConstructor();
> }
This function uses an empty one-shot constructor, whose prototype is
the given object. When using |new| on this constructor, it will create
a new object based on the given object.
> function LifeLikeTerrarium(plan) {
> Terrarium.call(this, plan);
> }
> LifeLikeTerrarium.prototype = clone(Terrarium.prototype);
> LifeLikeTerrarium.prototype.constructor = LifeLikeTerrarium;
The new constructor doesn't need to do anything different from the old
one, so it just calls the old one on the |this| object. We also have
to restore the |constructor| property in the new prototype, or it
would claim its constructor is |Terrarium| (which, of course, is only
really a problem when we make use of this property, which we don't).
---
It is now possible to replace some of the methods of the
|LifeLikeTerrarium| object, or add new ones. We have based a new
object type on an old one, which saved us the work of re-writing all
the methods which are the same in |Terrarium| and |LifeLikeTerrarium|.
This technique is called '_inheritance_'. The new type inherits the
properties of the old type. In most cases, this means the new type
will still support the interface of the old type, though it might also
support a few methods that the old type does not have. This way,
objects of the new type can be (polymorphically) used in all the
places where objects of the old type could be used.
In most programming languages with explicit support for
object-oriented programming, inheritance is a very straightforward
thing. In JavaScript, the language doesn't really specify a simple way
to do it. Because of this, JavaScript programmers have invented many
different approaches to inheritance. Unfortunately, none of them is
quite perfect. Fortunately, such a broad range of approaches allows a
programmer to choose the most suitable one for the problem he is
solving, and allows certain tricks that would be utterly impossible in
other languages.
At the end of this chapter, I will show a few other ways to do
inheritance, and the issues they have.
---
Here is the new |processCreature| method. It is big.
> LifeLikeTerrarium.prototype.processCreature = function(creature) {
> var surroundings = this.listSurroundings(creature.point);
> var action = creature.object.act(surroundings);
>
> var target = undefined;
> var valueAtTarget = undefined;
> if (action.direction && directions.contains(action.direction)) {
> var direction = directions.lookup(action.direction);
> var maybe = creature.point.add(direction);
> if (this.grid.isInside(maybe)) {
> target = maybe;
> valueAtTarget = this.grid.valueAt(target);
> }
> }
>
> if (action.type == "move") {
> if (target && !valueAtTarget) {
> this.grid.moveValue(creature.point, target);
> creature.point = target;
> creature.object.energy -= 1;
> }
> }
> else if (action.type == "eat") {
> if (valueAtTarget && valueAtTarget.energy) {
> this.grid.setValueAt(target, undefined);
> creature.object.energy += valueAtTarget.energy;
> }
> }
> else if (action.type == "photosynthese") {
> creature.object.energy += 1;
> }
> else if (action.type == "reproduce") {
> if (target && !valueAtTarget) {
> var species = characterFromElement(creature.object);
> var baby = elementFromCharacter(species);
> creature.object.energy -= baby.energy * 2;
> if (creature.object.energy > 0)
> this.grid.setValueAt(target, baby);
> }
> }
> else if (action.type == "wait") {
> creature.object.energy -= 0.2;
> }
> else {
> throw new Error("Unsupported action: " + action.type);
> }
>
> if (creature.object.energy <= 0)
> this.grid.setValueAt(creature.point, undefined);
> };
The function still starts by asking the creature for an action. Then,
if the action has a |direction| property, it immediately computes
which point on the grid this direction points to and which value is
currently sitting there. Three of the five supported actions need to
know this, and the code would be even uglier if they all computed it
separately. If there is no |direction| property, or an invalid one, it
leaves the variables |target| and |valueAtTarget| undefined.
After this, it goes over all the actions. Some actions require
additional checking before they are executed, this is done with a
separate |if| so that if a creature, for example, tries to walk
through a wall, we do not generate an |"Unsupported action"|
exception.
Note that, in the |"reproduce"| action, the parent creature loses
twice the energy that the newborn creature gets (childbearing is not
easy), and the new creature is only placed on the grid if the parent
had enough energy to produce it.
After the action has been performed, we check whether the creature is
out of energy. If it is, it dies, and we remove it.
---
Lichen is not a very complex organism. We will use the character |"*"|
to represent it. Make sure you have defined the |randomElement|
function from \\edrunkbug, because it is used again here.
> function Lichen() {
> this.energy = 5;
> }
> Lichen.prototype.act = function(surroundings) {
> var emptySpace = findDirections(surroundings, " ");
> if (this.energy >= 13 && emptySpace.length > 0)
> return {type: "reproduce", direction: randomElement(emptySpace)};
> else if (this.energy < 20)
> return {type: "photosynthese"};
> else
> return {type: "wait"};
> };
> Lichen.prototype.character = "*";
>
> creatureTypes.register(Lichen);
>
> function findDirections(surroundings, wanted) {
> var found = [];
> directions.each(function(name) {
> if (surroundings[name] == wanted)
> found.push(name);
> });
> return found;
> }
Lichen do not grow bigger than 20 energy, or they would get *huge*
when they are surrounded by other lichen and have no room to
reproduce.
***
Create a |LichenEater| creature. It starts with an energy of |10|, and
behaves in the following way:
* When it has an energy of 30 or more, and there is room near it, it reproduces.
* Otherwise, if there are lichen nearby, it eats a random one.
* Otherwise, if there is space to move, it moves into a random nearby empty square.
* Otherwise, it waits.
Use |findDirections| and |randomElement| to check the surroundings and
to pick directions. Give the lichen-eater |"c"| as its character
(pac-man).
///
> function LichenEater() {
> this.energy = 10;
> }
> LichenEater.prototype.act = function(surroundings) {
> var emptySpace = findDirections(surroundings, " ");
> var lichen = findDirections(surroundings, "*");
>
> if (this.energy >= 30 && emptySpace.length > 0)
> return {type: "reproduce", direction: randomElement(emptySpace)};
> else if (lichen.length > 0)
> return {type: "eat", direction: randomElement(lichen)};
> else if (emptySpace.length > 0)
> return {type: "move", direction: randomElement(emptySpace)};
> else
> return {type: "wait"};
> };
> LichenEater.prototype.character = "c";
>
> creatureTypes.register(LichenEater);
---
And try it out.
> var lichenPlan =
> ["############################",
> "# ######",
> "# *** **##",
> "# *##** ** c *##",
> "# *** c ##** *#",
> "# c ##*** *#",
> "# ##** *#",
> "# c #* *#",
> "#* #** c *#",
> "#*** ##** c **#",
> "#***** ###*** *###",
> "############################"];
>
> var terrarium = new LifeLikeTerrarium(lichenPlan);
> terrarium.onStep = partial(inPlacePrinter(), terrarium);
> terrarium.start();
Most likely, you will see the lichen quickly over-grow a large part of
the terrarium, after which the abundance of food makes the eaters so
numerous that they wipe out all the lichen, and thus themselves. Ah,
tragedy of nature.
> terrarium.stop();
---
Having the inhabitants of your terrarium go extinct after a few
minutes is kind of depressing. To deal with this, we have to teach our
lichen-eaters about long-term sustainable farming. By making them only
eat if they see at least two lichen nearby, no matter how hungry they
are, they will never exterminate the lichen. This requires some
discipline, but the result is a biotope that does not destroy itself.
Here is a new |act| method -- the only change is that it now only eats
when |lichen.length| is at least two.
> LichenEater.prototype.act = function(surroundings) {
> var emptySpace = findDirections(surroundings, " ");
> var lichen = findDirections(surroundings, "*");
>
> if (this.energy >= 30 && emptySpace.length > 0)
> return {type: "reproduce", direction: randomElement(emptySpace)};
> else if (lichen.length > 1)
> return {type: "eat", direction: randomElement(lichen)};
> else if (emptySpace.length > 0)
> return {type: "move", direction: randomElement(emptySpace)};
> else
> return {type: "wait"};
> };
Run the above |lichenPlan| terrarium again, and see how it goes.
Unless you are very lucky, the lichen-eaters will probably still go
extinct after a while, because, in a time of mass starvation, they
crawl aimlessly back and forth through empty space, instead of finding
the lichen that is sitting just around the corner.
***
Find a way to modify the |LichenEater| to be more likely to survive.
Do not cheat -- |this.energy += 100| is cheating. If you rewrite the
constructor, do not forget to re-register it in the |creatureTypes|
dictionary, or the terrarium will continue to use the old constructor.
///
One approach would be to reduce the randomness of its movement. By
always picking a random direction, it will often move back and forth
without getting anywhere. By remembering the last direction it went,
and preferring that direction, the eater will waste less time, and
find food faster.
> function CleverLichenEater() {
> this.energy = 10;
> this.direction = "ne";
> }
> CleverLichenEater.prototype.act = function(surroundings) {
> var emptySpace = findDirections(surroundings, " ");
> var lichen = findDirections(surroundings, "*");
>
> if (this.energy >= 30 && emptySpace.length > 0) {
> return {type: "reproduce",
> direction: randomElement(emptySpace)};
> }
> else if (lichen.length > 1) {
> return {type: "eat",
> direction: randomElement(lichen)};
> }
> else if (emptySpace.length > 0) {
> if (surroundings[this.direction] != " ")
> this.direction = randomElement(emptySpace);
> return {type: "move",
> direction: this.direction};
> }
> else {
> return {type: "wait"};
> }
> };
> CleverLichenEater.prototype.character = "c";
>
> creatureTypes.register(CleverLichenEater);
Try it out using the previous terrarium-plan.
***
A one-link food chain is still a bit rudimentary. Can you write a new
creature, |LichenEaterEater| (character |"@"|), which survives by
eating lichen-eaters? Try to find a way to make it fit in the
ecosystem without dying out too quickly. Modify the |lichenPlan| array
to include a few of these, and try them out.
///
You are on your own here. I failed to find a really good way to
prevent these creatures from either going extinct right away or
gobbling up all lichen-eaters and then going extinct. The trick of
only eating when it spots two pieces of food doesn't work very well
for them, because their food moves around so much it is rare to find
two in one place. What does seem to help is making the eater-eater
really fat (high energy), so that it can survive times when
lichen-eaters are scarce, and only reproduces slowly, which prevents
it from exterminating its food source too quickly.
The lichen and eaters go through a periodic movement -- sometimes
lichen are abundant, which causes a lot of eaters to be born, which
causes the lichen to become scarce, which causes the eaters to starve,
which causes the lichen to become abundant, and so on. You could try
to make the lichen-eater-eaters 'hibernate' (use the |"wait"| action
for a while), when they fail to find food for a few turns. If you
choose the right amount of turns for this hibernation, or have them
wake up automatically when they smell lots of food, this could be a
good strategy.
---
That concludes our discussion of terraria. The rest of the chapter is
devoted to a more in-depth look at inheritance, and the problems
related to inheritance in JavaScript.
---
First, some theory. Students of object-oriented programming can often
be heard having lengthy, subtle discussions about correct and
incorrect uses of inheritance. It is important to bear in mind that
inheritance, in the end, is just a trick that allows lazy##
programmers to write less code. Thus, the question of whether
inheritance is being used correctly boils down to the question of
whether the resulting code works correctly and avoids useless
repetitions. Still, the principles used by these students provide a
good way to start thinking about inheritance.
## Laziness, for a programmer, is not necessarily a sin. The kind of
people who will industriously do the same thing over and over again
tend to make great assembly-line workers and lousy programmers.
Inheritance is the creation of a new type of objects, the
'_sub-type_', based on an existing type, the '_super-type_'. The
sub-type starts with all the properties and methods of the super-type,
it inherits them, and then modifies a few of these, and optionally
adds new ones. Inheritance is best used when the thing modelled by the
sub-type can be said to *be* an object of the super-type.
Thus, a |Piano| type could be a sub-type of an |Instrument| type,
because a piano *is* an instrument. Because a piano has a whole array
of keys, one might be tempted to make |Piano| a sub-type of |Array|,
but a piano *is* no array, and implementing it like that is bound to
lead to all kinds of silliness. For example, a piano also has pedals.
Why would |piano[0]| give me the first key, and not the first pedal?
The situation is, of course, that a piano *has* keys, so it would be
better to give it a property |keys|, and possibly another property
|pedals|, both holding arrays.
It is possible for a sub-type to be the super-type of yet another
sub-type. Some problems are best solved by building a complex family
tree of types. You have to take care not to get too inheritance-happy,
though. Overuse of inheritance is a great way to make a program into a
big ugly mess.
---
The working of the |new| keyword and the |prototype| property of
constructors suggest a certain way of using objects. For simple
objects, such as the terrarium-creatures, this way works rather well.
Unfortunately, when a program starts to make serious use of
inheritance, this approach to objects quickly becomes clumsy. Adding
some functions to take care of common operations can make things a
little smoother. Many people define, for example, |inherit| and
|method| methods on objects.
> Object.prototype.inherit = function(baseConstructor) {
> this.prototype = clone(baseConstructor.prototype);
> this.prototype.constructor = this;
> };
> Object.prototype.method = function(name, func) {
> this.prototype[name] = func;
> };
>
> function StrangeArray(){}
> StrangeArray.inherit(Array);
> StrangeArray.method("push", function(value) {
> Array.prototype.push.call(this, value);
> Array.prototype.push.call(this, value);
> });
>
> var strange = new StrangeArray();
> strange.push(4);
> show(strange);
If you search the web for the words 'JavaScript' and 'inheritance',
you will come across scores of different variations on this, some of
them quite a lot more complex and clever than the above.
Note how the |push| method written here uses the |push| method from
the prototype of its parent type. This is something that is done often
when using inheritance -- a method in the sub-type internally uses a
method of the super-type, but extends it somehow.
---
The biggest problem with this basic approach is the duality between
constructors and prototypes. Constructors take a very central role,
they are the things that give an object type its name, and when you
need to get at a prototype, you have to go to the constructor and take
its |prototype| property.
Not only does this lead to a *lot* of typing (|"prototype"| is 9
letters), it is also confusing. We had to write an empty, useless
constructor for |StrangeArray| in the example above. Quite a few
times, I have found myself accidentally adding methods to a
constructor instead of its prototype, or trying to call |Array.slice|
when I really meant |Array.prototype.slice|. As far as I am concerned,
the prototype itself is the most important aspect of an object type,
and the constructor is just an extension of that, a special kind of
method.
---
With a few simple helper methods added to |Object.prototype|, it is
possible to create an alternative approach to objects and inheritance.
In this approach, a type is represented by its prototype, and we will
use capitalised variables to store these prototypes. When it needs to
do any 'constructing' work, this is done by a method called
|construct|. We add a method called |create| to the |Object|
prototype, which is used in place of the |new| keyword. It clones the
object, and calls its |construct| method, if there is such a method,
giving it the arguments that were passed to |create|.
> Object.prototype.create = function() {
> var object = clone(this);
> if (typeof object.construct == "function")
> object.construct.apply(object, arguments);
> return object;
> };
Inheritance can be done by cloning a prototype object and adding or
replacing some of its properties. We also provide a convenient
shorthand for this, an |extend| method, which clones the object it is
applied to and adds to this clone the properties in the object that it
is given as an argument.
> Object.prototype.extend = function(properties) {
> var result = clone(this);
> forEachIn(properties, function(name, value) {
> result[name] = value;
> });
> return result;
> };
In a case where it is not safe to mess with the |Object| prototype,
these can of course be implemented as regular (non-method) functions.
---
An example. If you are old enough, you may at one time have played a
'text adventure' game, where you move through a virtual world by
typing commands, and get textual descriptions of the things around you
and the actions you perform. Now those were games!
We could write the prototype for an item in such a game like this.
> var Item = {
> construct: function(name) {
> this.name = name;
> },
> inspect: function() {
> print("it is ", this.name, ".");
> },
> kick: function() {
> print("klunk!");
> },
> take: function() {
> print("you can not lift ", this.name, ".");
> }
> };
>
> var lantern = Item.create("the brass lantern");
> lantern.kick();
Inherit from it like this...
> var DetailedItem = Item.extend({
> construct: function(name, details) {
> Item.construct.call(this, name);
> this.details = details;
> },
> inspect: function() {
> print("you see ", this.name, ", ", this.details, ".");
> }
> });
>
> var giantSloth = DetailedItem.create(
> "the giant sloth",
> "it is quietly hanging from a tree, munching leaves");
> giantSloth.inspect();
Leaving out the compulsory |prototype| part makes things like calling
|Item.construct| from |DetailedItem|'s constructor slightly simpler.
Note that it would be a bad idea to just do |this.name = name| in
|DetailedItem.construct|. This duplicates a line. Sure, duplicating
the line is shorter than calling the |Item.construct| function, but if
we end up adding something to this constructor later, we have to add
it in two places.
---
Most of the time, a sub-type's constructor should start by calling the
constructor of the super-type. This way, it starts with a valid object
of the super-type, which it can then extend. In this new approach to
prototypes, types that need no constructor can leave it out. They will
automatically inherit the constructor of their super-type.
> var SmallItem = Item.extend({
> kick: function() {
> print(this.name, " flies across the room.");
> },
> take: function() {
> // (imagine some code that moves the item to your pocket here)
> print("you take ", this.name, ".");
> }
> });
>
> var pencil = SmallItem.create("the red pencil");
> pencil.take();
Even though |SmallItem| does not define its own constructor, creating
it with a |name| argument works, because it inherited the constructor
from the |Item| prototype.
---
JavaScript has an operator called _|instanceof|_, which can be used to
determine whether an object is based on a certain prototype. You give
it the object on the left hand side, and a constructor on the right
hand side, and it returns a boolean, |true| if the constructor's
|prototype| property is the direct or indirect prototype of the
object, and |false| otherwise.
When you are not using regular constructors, using this operator
becomes rather clumsy -- it expects a constructor function as its
second argument, but we only have prototypes. A trick similar to the
|clone| function can be used to get around it: We use a 'fake
constructor', and apply |instanceof| to it.
> Object.prototype.hasPrototype = function(prototype) {
> function DummyConstructor() {}
> DummyConstructor.prototype = prototype;
> return this instanceof DummyConstructor;
> };
>
> show(pencil.hasPrototype(Item));
> show(pencil.hasPrototype(DetailedItem));
---
Next, we want to make a small item that has a detailed description. It
seems like this item would have to inherit both from |DetailedItem|
and |SmallItem|. JavaScript does not allow an object to have multiple
prototypes, and even if it did, the problem would not be quite that
easy to solve. For example, if |SmallItem| would, for some reason,
also define an |inspect| method, which |inspect| method should the new
prototype use?
Deriving an object type from more than one parent type is called
_multiple inheritance_. Some languages chicken out and forbid it
altogether, others define complicated schemes for making it work in a
well-defined and practical way. It is possible to implement a decent
multiple-inheritance framework in JavaScript. In fact there are, as
usual, multiple good approaches to this. But they all are too complex
to be discussed here. Instead, I will show a very simple approach
which suffices in most cases.
---
A _mix-in_ is a specific kind of prototype which can be 'mixed into'
other prototypes. |SmallItem| can be seen as such a prototype. By
copying its |kick| and |take| methods into another prototype, we mix
smallness into this prototype.
> function mixInto(object, mixIn) {
> forEachIn(mixIn, function(name, value) {
> object[name] = value;
> });
> };
>
> var SmallDetailedItem = clone(DetailedItem);
> mixInto(SmallDetailedItem, SmallItem);
>
> var deadMouse = SmallDetailedItem.create(
> "Fred the mouse",
> "he is dead");
> deadMouse.inspect();
> deadMouse.kick();
Remember that |forEachIn| only goes over the object's *own*
properties, so it will copy |kick| and |take|, but not the constructor
that |SmallItem| inherited from |Item|.
---
Mixing prototypes gets more complex when the mix-in has a constructor,
or when some of its methods 'clash' with methods in the prototype that
it is mixed into. Sometimes, it is workable to do a 'manual mix-in'.
Say we have a prototype |Monster|, which has its own constructor, and
we want to mix that with |DetailedItem|.
> var Monster = Item.extend({
> construct: function(name, dangerous) {
> Item.construct.call(this, name);
> this.dangerous = dangerous;
> },
> kick: function() {
> if (this.dangerous)
> print(this.name, " bites your head off.");
> else
> print(this.name, " runs away, weeping.");
> }
> });
>
> var DetailedMonster = DetailedItem.extend({
> construct: function(name, description, dangerous) {
> DetailedItem.construct.call(this, name, description);
> Monster.construct.call(this, name, dangerous);
> },
> kick: Monster.kick
> });
>
> var giantSloth = DetailedMonster.create(
> "the giant sloth",
> "it is quietly hanging from a tree, munching leaves",
> true);
> giantSloth.kick();
But note that this causes |Item| constructor to be called twice when
creating a |DetailedMonster| -- once through the |DetailedItem|
constructor, and once through the |Monster| constructor. In this case
there is not much harm done, but there are situations where this would
cause a problem.
---
But don't let those complications discourage you from making use of
inheritance. Multiple inheritance, though extremely useful in some
situations, can be safely ignored most of the time. This is why
languages like Java get away with forbidding multiple inheritance. And
if, at some point, you find that you really need it, you can search
the web, do some research, and figure out an approach that works for
your situation.
Now that I think about it, JavaScript would probably be a great
environment for building a text adventure. The ability to change the
behaviour of objects at will, which is what prototypical inheritance
gives us, is very well suited for this. If you have an object
|hedgehog|, which has the unique habit of rolling up when it is
kicked, you can just change its |kick| method.
Unfortunately, the text adventure went the way of the vinyl record
and, while once very popular, is nowadays only played by a small
population of [enthusiasts | http://groups.google.com/group/rec.arts.int-fiction/topics].
=======================
Modularity / modularity
=======================
This chapter deals with the process of organising programs. In small
programs, organisation rarely becomes a problem. As a program grows,
however, it can reach a size where its structure and interpretation
become hard to keep track of. Easily enough, such a program starts to
look like a bowl of spaghetti, an amorphous mass in which everything
seems to be connected to everything else.
When structuring a program, we do two things. We separate it into
smaller parts, called _module_s, each of which has a specific role,
and we specify the relations between these parts.
In \\coo, while developing a terrarium, we made use of a number of
functions described in \\cfp. The chapter also defined a few new
concepts that had nothing in particular to do with terraria, such as
|clone| and the |Dictionary| type. All these things were haphazardly
added to the environment. One way to split this program into modules
would be:
* A module |FunctionalTools|, which contains the functions from \\cfp, and depends on nothing.
* Then |ObjectTools|, which contains things like |clone| and |create|, and depends on |FunctionalTools|.
* |Dictionary|, containing the dictionary type, and depending on |FunctionalTools|.
* And finally the |Terrarium| module, which depends on |ObjectTools| and |Dictionary|.
When a module _depend_s on another module, it uses functions or
variables from that module, and will only work when this module is
loaded.
It is a good idea to make sure dependencies never form a circle. Not
only do circular dependencies create a practical problem (if module
|A| and |B| depend on each other, which one should be loaded first?),
it also makes the relation between the modules less straightforward,
and can result in a modularised version of the spaghetti I mentioned
earlier.
---
Most modern programming languages have some kind of module system
built in. Not JavaScript. Once again, we have to invent something
ourselves. The most obvious way to start is to put every module in a
different file. This makes it clear which code belongs to which
module.
@_|script|_Browsers load JavaScript files when they find a |