:chap_num: 3

:prev_link: 02_program_structure

:next_link: 04_data

= Functions =

(((function)))You've seen function values, and how to call them, in

the previous chapter. Functions are the bread and butter of JavaScript

programming. The concept of wrapping a piece of program in a value has

many uses. It is a tool to create structure in programs, to reduce

repetition, to associate names with sub-programs, and to isolate these

sub-programs from each other.

The most obvious application of functions is defining new vocabulary.

Creating new words left and right in regular, human-language prose is

usually very bad style. In programming, it is indispensible.

Typical adult English speakers have some twenty thousand words in

their vocabulary. Very few programming languages come with twenty

thousand concepts built in. And the vocabulary that _is_ available

tends to be more precisely defined, and thus less flexible, than

spoken language words. Thus, we usually _have_ to add some of our own

vocabulary to avoid repeating ourselves all too much.

== Defining a function ==

(((function,definition)))A function definition is

just a regular variable definition where the value given to the

variable happens to be a function. For example, this defines the

variable `square` to refer to a function that produces the square of a

given number:

[source,javascript]

----

var square = function(x) {

return x * x;

};

console.log(square(12));

// → 144

----

(((function, keyword)))(((function,body)))A function is created with

an expression that starts with the keyword `function`. Functions have

a set of parameters (in this case, only `x`), and a “body”, containing

the statements that are to be executed when the function is called.

These must always be wrapped in braces, even when the body consists of

only a single statement (as in the example).

A function can have multiple parameters, or no parameters at all.

[source,javascript]

----

var makeNoise = function() {

console.log("Pling!");

};

var power = function(base, exponent) {

var result = 1;

for (var count = 0; count < exponent; count++)

result *= base;

return result;

}

power(2, 10);

// → 1024

----

(((return keyword)))Some functions produce a value, such as `power`

and `square`, and some don't, such as `makeNoise` (which only has a

side effect). A `return` statement is used to determine the value the

function returns. When control comes across such a statement, it

immediately jumps out of the current function and gives the returned

value to the code that called the function. The `return` keyword

without an expression after it will cause the function to return

`undefined`.

== Parameters and scopes ==

(((variable)))The parameters to a function behave like variables—but

ones that are given an initial value by the _caller_ of the function,

not the code in the function itself.

(((variable,scope)))(((local variable)))A very important property of

functions is that the variables created inside of them, including

their parameters, are _local_ to the function. This means, for

example, that the `result` variable in the `power` example will be

newly created every time the function is called and will no longer

exist after the function returns.

indexsee:[top-level variable,global variable]

(((var keyword)))(((global variable)))This “localness” of variables

applies only to the parameters and variables declared with the `var`

keyword inside the function body. It is possible to access _global_

(nonlocal) variables from inside a function, as long as you haven't

declared a local variable with the same name.

The following code demonstrates this. It defines (and calls) two

functions that both change the value of the variable `x`. The first

one does not declare the variable as local and thus changes the global

variable defined at the start of the example. The second does declare

it, and thus all references to `x` inside of it refer to the local

`x`, which is an entirely different variable than the global `x`.

[source,javascript]

----

var x = "A";

var setXToB = function() {

x = "B";

};

setXToB();

console.log(x);

// → "B";

var setXToC = function() {

var x;

x = "C";

};

setXToC();

console.log(x);

// → "B";

----

This behavior helps prevent accidental interference between functions.

If all variables were shared by the whole program, it'd take a lot of

effort, in program that aren't trivially small, to make sure no name

is used twice. And if you _did_ reuse a variable name, you would see

strange effects, as unrelated code messes with the value of your

variable. By treating function-local variables as existing only within

the function, the language makes it easier to read and understand

functions as small universes, with little action-at-a-distance to

complicate things.

== Nested scope ==

(((variable,scope)))(((inner function)))(((nested functions)))

(((lexical scoping)))In JavaScript, the distinction is not just

between _global_ and _local_ variables. In fact, there are degrees of

locality. Functions can be created anywhere in the program, including

inside other functions.

For example, this rather nonsensical function has two functions inside

of it:

[source,javascript]

----

var landscape = function() {

var result = "";

var flat = function(size) {

for (var count = 0; count < size; count++)

result += "_";

};

var mountain = function(size) {

result += "/";

for (var count = 0; count < size; count++)

result += "'";

result += "\";

};

flat(3);

mountain(4);

flat(6);

mountain(1);

flat(1);

return result;

};

console.log(landscape());

// → "___/''''\______/'\_"

----

The `flat` and `mountain` function can “see” the variable called

`result`, since they are inside of the function that defines it. But

they can not see each other's `count` variables, only their own, since

they are outside of each other.

In short, each local scope can also see all the local scopes that it

is inside of. The set of variables 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_.

((({} (block))))People who have experience with other programming

languages might expect that any block of code (between braces)

produces a new local environment. But in JavaScript, functions are the

only things that create a new scope. You are allowed to use

free-standing blocks:

[source,javascript]

----

var something = 1;

{

var something = 2;

// Do stuff with variable something...

}

// Outside of the block again...

----

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 only useful to group the body of an `if`

statement or a loop.

If you find this odd, you're not alone. The next version of JavaScript

will introduce a `let` keyword, which works like `var`, but creates a

variable that is local to the enclosing _block_, not the enclosing

_function_.

== Functions as values ==

(((function,as value)))Usually, function variables simply act as names

for a specific piece of the program. They are defined once, and never

change. This makes it easy to start confusing the function and its

name.

But the two are different. A function value can do all the things that

other values can do—you can use it in all kinds of expressions, not

just call it. It is possible to store such a value in a new place, or

pass it an argument to a function, and so on. Similarly, a variable

that holds a function is still just a regular variable, and can be

assigned a new value.

[source,javascript]

----

var announce = function(text) {

console.log("Hey dude, " + text + "!");

};

if (prompt("Who are you?", "") == "royalty") {

announce = function(text) {

console.log("Your majesty, " + text + ".");

}

}

announce("it is done");

----

In REF(fp), we will discuss the wonderful things that can be done by

passing around function values to other functions.

== Declaration notation ==

There is a slightly shorter way to say `var x = function...`. The

`function` keyword can also be used at the start of a statement, to

produce a function declaration statement.

[source,javascript]

----

function square(x) {

return x * x;

}

----

This defines the variable `square` and points it at the given

function. So far so good. There is one subtlety with this form of

function definition:

[source,javascript]

----

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

function future() {

return "We STILL have no flying cars.";

}

----

Such definitions are not part of the regular top-to-bottom flow of

control. They are conceptually moved to the top, and can be used by

all the code in the same scope. This is sometimes useful—it allows you

to put the interesting code at the top, and still use functions

defined further down.

What happens when you put such a function definition inside of a

conditional (`if`) block, or a loop? Well, don't do that. Different

JavaScript platforms (in browsers) have traditionally done different

things in that situation, and the latest standard actually forbids it.

So if you want your programs to behave consistently, only use this

form of function-defining statements in the outermost block in a

function or program.

[source,javascript]

----

function example() {

function a() {} // Okay

if (something) {

function b() {} // Danger!

}

}

----

== The call stack ==

indexsee:[stack,call stack]

(((call stack)))(((function,application)))I believe it will be helpful

to take a closer look at the way control flows through functions. Here

is a simple program making a few function calls:

[source,javascript]

----

function greet(who) {

console.log("Hello " + who);

}

greet("Harry");

console.log("Bye");

----

A run through this program goes roughly like this: The call to `greet`

causes control to jump to the start of that function (line 2), which

calls `console.log` (a built-in browser function), allowing that take

control. It eventually finishes, causing control to return to line 2.

We reach the end of the `greet` function, so we return back to place

that called it, at line 4. The line after that calls `console.log`

again. We could show the flow of control schematically like this:

....

top

greet

console.log

greet

top

console.log

top

....

Since a function, when returning, has to jump back to the place of the

call, the computer must remember the context from which the function

was called. In once case, `console.log` had to jump back to the

`greet` function. In the other case, it jumps back to the end of the

program.

The place where this context is stored is the _call stack_. Every time

a function is called, the current context is put on top of this

“stack” of contexts. When the function returns, it takes the top

context from the stack, and uses it to continue execution.

(((stack overflow)))(((recursion)))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.” The following code illustrates that—it asks the

computer a really hard question, which causes an infinite

back-and-forth between two functions. Or rather, it would be infinite,

if we had an infinite stack. As it is, it will run out of space, or

“blow the stack.”

[source,javascript]

----

function chicken() {

return egg();

}

function egg() {

return chicken();

}

console.log(chicken() + " came first.");

----

== Optional Arguments ==

(((argument)))(((function,application)))The following call to `alert`

is allowed:

[source,javascript]

----

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

----

(((alert function)))The function `alert` officially accepts only one

argument. Yet when you call it like this, it does not complain. It

simply ignores the other arguments and shows you `Hello`.

(((undefined value)))JavaScript is notoriously easy-going about the

amount of arguments you pass to a function. If you pass too many, the

extra ones are ignored. If you pass too few, the variables for the

missing parameters get the value `undefined`.

The downside of this is that it is possible—likely, even—that you'll

accidentally pass the wrong number of arguments to functions... and no

one will tell you about it.

indexsee:[optional argument,argument optional]

(((argument,optional)))The upside is that it can be used to have a

function take “optional” arguments. For example, this version of

`power` can be called either with two arguments or with a single

argument, in which case the exponent is assumed to be two, and it

behaves like `square`.

[source,javascript]

----

function power(base, exponent) {

var result = 1;

if (exponent == undefined)

exponent = 2;

for (var count = 0; count < exponent; count++)

result *= base;

return result;

}

console.log(power(4));

// → 16

console.log(power(4, 3));

// → 64

----

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. This is helpful

because it makes it possible for a function to accept any number of

arguments. `console.log` makes use of this—it outputs all of the

values it is given.

[source,javascript]

----

console.log("R", 2, "D", 2);

----

== Closure ==

(((closure)))(((variable,scope)))The ability to treat functions as

values, combined with the fact that local variables are “recreated”

every time a function is called, brings up an interesting question.

What happens to local variables when the function call that created

them is no longer active? The following code illustrates this:

[source,javascript]

----

function wrapNumber(n) {

var localVariable = n;

return function(){ return localVariable; };

}

var wrap1 = wrapNumber(1);

var wrap2 = wrapNumber(2);

console.log(wrap1());

// → 1

console.log(wrap2());

// → 2

----

When `wrapNumber` is called, it creates a local variable that stores

its parameter, and then returns a function that returns this local

variable. This is allowed, and works as you'd expect—the variable

survives. In fact, multiple instances of the variable can be alive at

the same time, which is another good illustration of the concept that

local variables really are recreated for every call—different calls

can not trample on each other's local variables.

This feature, being able to reference specific instance of local

variables in an enclosing function, is called _closure_. A function

that “closes over” some local variables is called _a closure_. This

behavior not only frees you from having to worry about lifetimes of

variables, but also allows for some creative use of function values.

With a slight change, we can turn the example function into a way to

create functions that multiply by an arbitrary amount:

[source,javascript]

----

function multiplier(factor) {

return function(number) {

return number * factor;

};

}

var twice = multiplier(2);

console.log(twice(5));

// → 10

----

The explicit local variable from the `wrapNumber` example isn't

needed, since a parameter is itself a local variable.

== Recursion ==

(((recursion)))(((function,application)))It is perfectly okay for a

function to call itself. A function that calls itself is called

_recursive_. Recursion allows for some interesting function

definitions. For example this alternate implementation of `power`:

[source,javascript]

----

function power(base, exponent) {

if (exponent == 0)

return 1;

else

return base * power(base, exponent - 1);

}

console.log(power(2, 3));

// → 8

----

This is rather close to the way mathematicians define exponentiation,

and arguably describes the concept in a much more elegant way. Instead

of using a loop, the function calls itself multiple times to achieve

the repeated multiplication.

(((stack overflow)))There is one important problem: In typical

JavaScript implementations, this second version is about 10 times

slower than the first one. Running running through a simple loop is a

_lot_ cheaper than calling a function multiple times. On top of that,

using a sufficiently large exponent to this function might cause the

stack to overflow.

(((efficiency)))The dilemma of speed versus (((elegance)))elegance is

an interesting one. Almost any program can be made faster by making it

bigger and more convoluted. You can see this as a kind of continuum

between human-friendliness and processor-friendliness.

In the case of the earlier `power` function, the inelegant (looping)

version is still sufficiently simple and easy to read. It does not

make 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

you know for sure that the program is too slow. When it is, find out

which parts are taking up the most time, and start exchanging elegance

for efficiency in those parts.

Of course, the previous 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.

(((premature optimization)))The reason I am stressing this is that

surprisingly many beginning 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.

Anyway, 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 by 3

and then adding 5 twice. The number 15 cannot be reached at all.

Here is a recursive solution:

[source,javascript]

----

function findSolution(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");

}

findSolution(24);

// → (((1 * 3) + 5) * 3)

----

Note that it doesn't necessarily find the _shortest_ sequence of

operations—it is satisfied when it finds any sequence at all.

I don't necessarily expect you to see how it works right away. But let

us work through it, since it makes for a great exercise in recursive

thinking.

The inner function `find` does the actual recursing. It takes two

arguments, the current number and a string that records how we reached

this number, and returns either a string that shows how to get to the

goal number, or `null`.

(((|| operator)))(((shortcut evaluation)))In order to do this, it

performs one of three actions. If the current number is the goal

number, the current history is a way to reach the goal, so it is

simply returned. If the current number is greater than the goal, there

is no sense in further exploring this history, since both of the

possible steps will only make the number bigger. And finally, if we're

still below the goal, the function tries all possible paths that start

from the current number, by calling itself twice, once for both of the

allowed next steps. If the first call returns something that is not

`null`, it is returned. Otherwise, the second call is returned

(regardless of whether it produces a string or `null`).

How does this simple function produce the effect we are looking for?

Let us look at a the calls to `find` that are made when searching for

a solution for the number 13:

....

find(1, "1")

find(6, "(1 + 5)")

find(11, "((1 + 5) + 5)")

find(16, "(((1 + 5) + 5) + 5)")

too big

find(33, "((1 + 5) + 5)")

too big

find(18, "((1 + 5) * 3)")

too big

find(3, "(1 * 3)")

find(8, "((1 * 3) + 5)")

find(13, "(((1 * 3) + 5) + 5)")

found!

....

The indentation suggests the depth of the call stack. The first call

to `find` itself calls `find` twice, to explore the solutions that

start with `(1 + 5)` and `(1 * 3)`. The first call fails to find a

solution that starts with `(1 + 5)`—using recursion, it explores _all_

such solutions that yield a number smaller than the goal number. Thus,

it returns `null`, and the `||` operator causes the call to explore

`(1 * 3)` to happen. This one has more luck, its first recursive call,

through _another_ recursive call, hits upon our goal number 13. Thus,

a string is returned, and each of the `||` operators in the

intermediate calls ends up returning that string, which is our

solution.

== Growing functions ==

There are two more or less natural ways for functions to be introduced

into programs.

The first is that you find yourself writing very similar code multiple

times. We want to avoid doing that—having more code means more space

for mistakes to hide, and more material to read for people trying to

understand the program. So we take the repeated functionality, find a

good name for it, and put it into a function.

The second way is that you find you need some functionality that you

haven't written yet, and that sounds like it deserves its own

function. You'll start by naming the function, and then write its

body. You might even first write another piece of code that already

uses the function, before you create the function itself.

How difficult it is to find a good name for a function is a good

indication of how clear a concept it is that you're trying to wrap.

Let us go through an example.

We want to write a program that prints two numbers, the amounts of

cows and chickens on our farm, with the words `Cows` and `Chickens`

after them, and zeroes padded before both numbers so that they are

always three digits long.

....

007 Cows

011 Chickens

....

Well, that clearly is a function of two arguments. Let's get coding.

[source,javascript]

----

function printFarmInventory(cows, chickens) {

var cowString = String(cows);

while (cowString.length < 3)

cowString = "0" + cowString;

console.log(cowString + " Cows");

var chickenString = String(chickens);

while (chickenString.length < 3)

chickenString = "0" + chickenString;

console.log(chickenString + " Chickens");

}

----

Adding `.length` after a string value will give us the length of that

string. Thus, whe `while` loops keep putting zeroes in front of the

number strings until they are at least three characters long.

Mission accomplished! But just as we want to send him the code (along

with a hefty invoice), the farmer calls and tells us he's also started

keeping pigs, and couldn't we please extend the software to also print

pigs.

We sure can. But just as we're in the process of copy-pasting those

four lines one more time, we stop and reconsider. There has to be a

better way. Here's a first attempt:

[source,javascript]

----

function printZeroPaddedWithLabel(number, label) {

var numberString = String(number);

while (numberString.length < 3)

numberString = "0" + numberString;

console.log(numberString + " " + label);

}

function printFarmInventory(cows, chickens, pigs) {

printZeroPaddedWithLabel(cows, "Cows");

printZeroPaddedWithLabel(chickens, "Chickens");

printZeroPaddedWithLabel(pigs, "Pigs");

}

----

It works! But that name, `printZeroPaddedWithLabel`, is a little

awkward. It conflates three things, printing, zero-padding, and adding

a label, in a single function.

If, instead of lifting out the repeated part of our program wholesale,

we try to pick out a _concept_, we can do better:

[source,javascript]

----

function zeroPad(number, width) {

var string = String(number);

while (string.length < width)

string = "0" + string;

return string;

}

function printFarmInventory(cows, chickens, pigs) {

console.log(zeroPad(cows, 3) + " Cows");

console.log(zeroPad(chickens, 3) + " Chickens");

console.log(zeroPad(pigs, 3) + " Pigs");

}

----

`zeroPad` has a nice, obvious name, which makes it easier for someone

who reads the code to figure out what it does. And it is useful in

more situations that just this specific program. For example, you

could use it to print nicely aligned tables of numbers.

How smart and versatile should our function be? We could write

anything from a terribly simple function that simply pads a number so

that it's three characters wide, to a complicated generalized

number-formatting system that handles fractional numbers, negative

numbers, aligning of dots, padding with different characters, and so

on.

A useful principle is to not add cleverness unless you are absolutely

sure you are going to need it. It can be tempting to write general

“frameworks” for every little bit of functionality you need. Resist

that urge. You won't get any real work done, and you'll end up writing

a lot of code that no one will ever use.

== Functions and side effects ==

(((side effect)))(((pure function)))(((function,purity)))Functions can

roughly be divided into those that are called for their side effects,

and those that are called for their return value. (It is also possible

to have both side effects and return a value, of course.)

The first helper function in the farm example,

`printZeroPaddedWithLabel`, is called for its side effect (it prints a

line). The second, `zeroPad`, is called for its return value. It is no

coincidence that the second is useful in more situations than the

first. Functions that create values are easier to combine in new ways

than functions that directly perform a side effect.

A _pure_ function is a specific kind of value-producing function that

not only has no side effects, but also doesn't rely on side effects

from other code—for example, it doesn't read variables that are

occasionally changed by other code. A pure function has the pleasant

property that, when called with the same arguments, it always produces

the same value (and doesn't do anything else). This makes it easy to

think about—a call to it can be mentally substituted by its result

without changing the meaning of the code. When you are not sure that

such a function is working correctly, you can test it by simply

calling it and know that if it works in that context, it will work in

any context. Nonpure functions might return different values based on

all kinds of factors and have side effects that might be hard to test

and think about.

Still, there is no need to feel bad when writing functions that are

not pure, no need to start a holy war and purge all code of

impurities. Side effects are often useful. There'd be no way to write

a pure `console.log`, for example, and `console.log` is certainly

useful. Some operations also become more expensive when done without

side effect, since all data involved must be copied, rather than

modified.

== Summary ==

This chapter taught how to write our own functions. The `function`

keyword, when used as an expression, can create a function value. When

used as a statement, it can be used to declare a variable and give it

a function as its value.

[source,javascript]

----

// Create a function and immediately call it

(function (a) { console.log(a + 2); })(4);

// Declare f to be a function

function f(a, b) {

return a * b * 3.5;

}

----

A key aspect in understanding functions is understanding local scopes.

Parameters and variables declared inside a function are local to the

function, recreated every time the function is called, and not visible

from the outside. Functions declared inside another function do have

access to the outer function's local scope.

Separating the different tasks your program performs into different

functions is helpful. You won't have to repeat yourself so much, and

it helps people reading the program in the same way that chapters and

sections are helpful when reading regular text.

== Exercises ==

=== Minimum ===

The previous chapter introduced the standard function `Math.min` that

returns the smallest of its arguments. We can do that ourselves now.

Write a function `min` that takes two arguments and returns the

smallest.

''''

If you have trouble putting braces and parentheses in the right place

to get a valid function definition, simply start by copying one of the

examples in this chapter and modifying it.

A function can have multiple `return` statements.

=== Recursion ===

We've seen that `% 2` (the remainder operator) can be used to test

whether a number is divisible by 2, i.e. whether it is even or odd.

Here's another way to define whether a (positive, whole) number is

even or odd:

- Zero is even.

- One is odd.

- For any other number N, the evenness is the same as N - 2.

Define a recursive function `isEven` corresponding to this

description. The function accepts a number parameter and returns a

boolean.

Test it out on 50 and 75. See how it behaves on -1. Why?

''''

Your function will somewhat similar to the inner `find` function in

the recursive `findSolution` example in this chapter. It has an

`if`/`else if`/`else` chain that tests which of the three cases

applies, with the final `else` making a recursive call. Each of the

branches should contain a `return` statement, or in some other way

arrange for a specific value to be returned.

When given a negative number, the function will recurse again and

again, giving itself an ever more negative number, and thus only

getting further and further away from the input that allows it to

return a result. It will eventually run out of stack space and abort.

=== 3rd exercise ===

FIXME fill this in