Functions and the call stack

01 · NAMED STEPS

Functions: named, reusable steps

You already know one: a recipe. "Make the sauce" is a name for a list of steps, and the main recipe just says the name instead of repeating them. A function does the same for code. You define it once, with the keyword function, a name, and a body in braces. Then you call it by writing its name followed by brackets.

On the stage, area is a machine. Each call drops two values into its hoppers, the body runs (the gears), and one value slides out of the chute. The caller on the left doesn't need to know how it works inside, only what goes in and what comes out.

// Without a function: the same idea, written out three times
console.log(4 * 3);
console.log(2 * 5);
console.log(6 * 6);
​
// With one: name the idea once, then use the name
function area(width, height) {
  return width * height;
}
​
console.log(area(4, 3));
console.log(area(2, 5));
console.log(area(6, 6));

Why bother? Three reasons, which matter more as programs grow. No repetition: one fix fixes every use. A name explains intent: area(4, 3) says what it means, 4 * 3 doesn't. Hiding detail: you can use Math.sqrt without knowing how square roots are computed. That last idea is called abstraction, and it is how people build programs too big for one head.

Every language has functions; they look much the same everywhere:

def area(width, height):
    return width * height
 
print(area(4, 3))   # 12

int area(int width, int height) {
    return width * height;
}
 
printf("%d\n", area(4, 3));   /* 12 */

02 · IN AND OUT

Parameters in, a return value out

The names in the definition's brackets are parameters: blanks to be filled. The values in a call are arguments: what fills them. In area(4, 3), the argument 4 lands in the parameter width and 3 in height, by position. On the stage the hoppers are labelled with the parameter names, and show the value each call drops in.

return does two things: it hands a value back to the caller, and it ends the function right there. A function with no return still finishes, but hands back undefined.

// name and greeting are PARAMETERS: blanks the caller fills in
function greet(name, greeting = "Hello") {
  return greeting + ", " + name + "!";
}
​
// "Ada" and "Hi" are ARGUMENTS: the values that fill them
console.log(greet("Ada"));
console.log(greet("Alan", "Hi"));
​
// no return statement: the caller gets undefined
function forgetful(x) {
  x * 2;          // worked out, then thrown away
}
console.log(forgetful(5));
​
// return also STOPS the function, there and then
function sign(n) {
  if (n < 0) return "negative";
  if (n === 0) return "zero";
  return "positive";
}
console.log(sign(-3), sign(0), sign(7));

One subtle thing, worth learning now: parameters get copies of values. A number is copied, so the function can't change the caller's variable. But the "value" of an array or object is a reference to it, so the function receives a second arrow pointing at the same thing, and can change it.

// a number is copied into the parameter
function bump(n) {
  n = n + 1;
  return n;
}
let score = 1;
bump(score);
console.log(score);       // still 1
​
// an array or object is NOT copied: the parameter points at the same one
function addItem(list) {
  list.push("milk");
}
const shopping = [];
addItem(shopping);
console.log(shopping);    // [ 'milk' ]

03 · SCOPE

Scope: which names a function can see

A variable made inside a function is local: it exists only inside that function, and only while it runs. That is what lets you call two different functions' variables i without them clashing. The region of code where a name exists is its scope.

Scopes nest, like glass rooms inside rooms. Code inside can see out through every wall; code outside can't see in. When inner uses a name, JavaScript looks in inner's room first, then outer's, then the global scope, and stops at the first match. On the stage the green probe goes looking for street, city and planet in turn, then a probe from outside tries to look in and is stopped at the wall.

const planet = "Earth";             // global scope
​
function outer() {
  const city = "Reykjavík";         // outer's scope
  function inner() {
    const street = "Laugavegur";    // inner's scope
    console.log(street, city, planet);   // looks outwards: finds all three
  }
  inner();
  console.log(typeof street);       // can't look inwards
}
​
outer();

This is called lexical scope: which names you can see depends on where the code is written, not on who calls it. Since 2015, let and const also make a scope out of every { } block, which is why modern code avoids the older var.

// let and const live in the nearest { block }
if (true) {
  let inside = "only in here";
  var leaky = "var ignores blocks";
}
console.log(typeof inside);   // "undefined"
console.log(leaky);           // var belongs to the whole function
​
// shadowing: an inner name hides an outer one with the same name
const x = "outer x";
function show() {
  const x = "inner x";
  return x;
}
console.log(show(), "/", x);

04 · CLOSURES

Closures: functions that remember

Functions are values: you can store them in variables and return them from other functions. Put that together with scope and something surprising happens. makeCounter makes a local count, then returns a little function that uses it. makeCounter has finished, so count should be gone. It isn't.

function makeCounter() {
  let count = 0;              // makeCounter's local variable...
  return function () {
    count = count + 1;        // ...still reachable from in here
    return count;
  };
}
​
const a = makeCounter();
const b = makeCounter();
console.log(a(), a(), a());   // 1 2 3
console.log(b());             // 1: b has its own count

The returned function carries a link to the scope it was born in. That pair, a function plus the variables it can see, is a closure. On the stage, each function is tethered to its own count; the frame that created it fades away, but the variable stays, because something can still reach it. a and b came from separate calls, so they have separate counts.

Closures are everywhere in real code: every click handler that remembers which button it belongs to, every callback, and the simplest way to keep data private:

// a closure is the simplest way to hide state
function makeAccount(start) {
  let balance = start;                 // nobody outside can touch this
  return {
    deposit(amount) { balance += amount; return balance; },
    get() { return balance; },
  };
}
​
const acct = makeAccount(100);
acct.deposit(50);
console.log(acct.get());          // 150
console.log(acct.balance);        // undefined: not reachable from outside

05 · THE CALL STACK

The call stack: how the computer keeps its place

When sumOfSquares calls square, it pauses half-way through a line. When square returns, the computer must know where to carry on, and what a, b and x were. It keeps that in a stack frame: one box per running call, holding its parameters, its local variables and its place in the code.

Frames pile up like plates: a call puts a new one on top, a return takes the top one off and hands its value to the one below. Last in, first out: a stack. Watch the tower: main, then sumOfSquares(3, 4), then square(3) on top; it returns 9 and pops; square(4) takes its place and returns 16; then 25 drops to the bottom.

function square(n) {
  return n * n;
}
​
function sumOfSquares(a, b) {
  const x = square(a);
  const y = square(b);
  return x + y;
}
​
const result = sumOfSquares(3, 4);
console.log(result);

The stack is also how an error knows where it happened. A JavaScript Error takes a snapshot of the stack when it is made: the "stack trace" you will read every day as a programmer.

function c() {
  // an Error records the call stack at the moment it is made
  const lines = new Error().stack.split("\n");
  console.log(lines.slice(1, 4).map((l) => l.trim().split(" (")[0]).join("\n"));
}
function b() { c(); }
function a() { b(); }
​
a();

Underneath, it is real memory. On an x86-64 CPU, a call instruction pushes the return address onto a stack in memory and jumps; ret pops it and jumps back. Here is what a C compiler (gcc, no optimisation) makes of square:

square:
    push rbp                 ; save the caller's frame pointer
    mov  rbp, rsp            ; this frame starts here
    mov  [rbp-4], edi        ; store n in the frame
    mov  eax, [rbp-4]
    imul eax, eax            ; n * n, the return value goes in eax
    pop  rbp                 ; drop this frame
    ret                      ; pop the return address and jump back
sumOfSquares:
    ...
    call square              ; push the return address, jump to square
    mov  ebx, eax            ; x = what square returned

The 6502 in Inside the CPU does the same with JSR and RTS, and keeps its whole stack in one 256-byte page of memory. The ECMAScript standard calls the JavaScript version the execution context stack.

06 · RECURSION

Recursion: a function that calls itself

A function can call any function, including itself. That sounds like a loop with no end, and it would be, except for one rule: every recursive function needs a base case, a problem small enough to answer directly, and a recursive case that hands a smaller problem to another copy of itself.

4! (four factorial) is 4 × 3 × 2 × 1. It is also 4 × 3!, which is a smaller factorial. So factorial(4) asks factorial(3), which asks factorial(2), down to factorial(1), which just answers 1. On the tower, four frames of the same function stack up, each with its own n, each waiting. Then the answers come back down: 1, 2, 6, 24.

function factorial(n) {
  if (n <= 1) return 1;          // base case: small enough to answer
  return n * factorial(n - 1);   // recursive case: a smaller problem
}
​
console.log(factorial(4));
console.log(factorial(10));

Each frame keeps its own n: that is the whole trick. Indenting by depth makes the stack visible in plain text:

function factorial(n, depth = 0) {
  const pad = "  ".repeat(depth);       // indent one step per frame
  console.log(pad + "factorial(" + n + ")");
  if (n <= 1) {
    console.log(pad + "returns 1");
    return 1;
  }
  const result = n * factorial(n - 1, depth + 1);
  console.log(pad + "returns " + result);
  return result;
}
​
factorial(4);

Factorial is easier as a loop, honestly. Recursion shines when the data is recursive: folders inside folders, comments with replies, a web page's elements, the parse tree from chapter 1. The function mirrors the shape of the data:

// recursion fits data that contains smaller copies of itself
const folder = {
  name: "projects", size: 0, children: [
    { name: "notes.txt", size: 12 },
    { name: "photos", size: 0, children: [
      { name: "cat.jpg", size: 300 },
      { name: "dog.jpg", size: 250 },
    ] },
  ],
};
​
function totalSize(item) {
  let sum = item.size;
  for (const child of item.children ?? []) {
    sum += totalSize(child);       // the same question, one level down
  }
  return sum;
}
​
console.log(totalSize(folder));

07 · STACK OVERFLOW

Stack overflow: when the tower hits the ceiling

The stack is a fixed slab of memory, set aside before the program runs. Forget the base case, and every call pushes another frame with no pop to come. The tower grows until it hits the limit, and the engine stops the program rather than letting it scribble over other memory. That is a stack overflow; in JavaScript it is a RangeError.

function forever(n) {
  return forever(n + 1);   // no base case: it never stops calling
}
​
forever(0);

How tall can the tower get? It depends on the engine, the thread, and how big each frame is. Measure it:

let depth = 0;
function dive() {
  depth++;
  dive();
}
​
try {
  dive();
} catch (e) {
  console.log(e.name + ": " + e.message);
}
console.log("frames before it gave up:", depth);

Python is stricter on purpose: it counts frames and stops at 1,000 by default, long before the real stack runs out.

import sys
print(sys.getrecursionlimit())    # 1000 by default
 
def forever(n):
    return forever(n + 1)
 
forever(0)
# RecursionError: maximum recursion depth exceeded

The site Stack Overflow is named after this error, which tells you how often programmers meet it. The usual causes: a missing base case, a base case that is never reached (say, n === 0 when n goes 3, 1, −1 …), or genuinely deep data handled recursively.

08 · TAIL CALLS

Tail calls: recursion without the pile

Look at what factorial's frame does after its call returns: it still has to multiply by n. So it must wait, and the frames pile up. Now move the multiplying into the arguments, carrying the answer so far in an accumulator. Then the recursive call is the very last thing the function does: a tail call. Nothing is left to do afterwards, so the frame could simply be reused.

// NOT a tail call: after factorial(n - 1) returns,
// this frame still has to multiply, so it must wait
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
​
// a TAIL call: the call is the very last thing. The answer so far
// travels in acc, so nothing is left to do when the call returns
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);
}
​
console.log(factorial(5), factorialTail(5));

On the stage, one frame is rewritten in place: factorial(4, 1), (3, 4), (2, 12), (1, 24). The faint outlines are the frames an ordinary call would have stacked. Reusing the frame is called tail call optimisation; it makes a tail-recursive function run in constant stack space, exactly like a loop.

The catch: since ES2015 the JavaScript standard requires proper tail calls in strict mode, but only Safari's engine (JavaScriptCore) implements them. V8, in Chrome and Node, and Firefox's SpiderMonkey keep every frame. So here, this still overflows:

function sumTo(n, acc = 0) {
  if (n === 0) return acc;
  return sumTo(n - 1, acc + n);    // a tail call...
}
​
console.log(sumTo(1000));          // fine
console.log(sumTo(100000));        // ...but this engine still keeps every frame

In JavaScript the dependable fix is to turn the tail call into a loop yourself (the parameters become variables you update), or to use a trampoline: return the next step as a function, and let a loop call it.

// the dependable fix: a tail call is a loop in disguise
function sumTo(n) {
  let acc = 0;
  while (n > 0) {
    acc = acc + n;    // what the next call's acc would have been
    n = n - 1;        // what the next call's n would have been
  }
  return acc;
}
console.log(sumTo(100000));
​
// or a trampoline: return "the next step" instead of calling it
function trampoline(fn) {
  return (...args) => {
    let r = fn(...args);
    while (typeof r === "function") r = r();
    return r;
  };
}
const sumToT = trampoline(function go(n, acc = 0) {
  return n === 0 ? acc : () => go(n - 1, acc + n);
});
console.log(sumToT(100000));

Other languages promise it. Scheme's standard requires tail calls to run in constant space, so Scheme programmers write loops as recursion. And an optimising C compiler often does it without being asked:

;; Scheme guarantees tail calls: this runs in constant space
(define (sum-to n acc)
  (if (= n 0)
      acc
      (sum-to (- n 1) (+ acc n))))
 
(sum-to 1000000 0)   ; => 500000500000, no overflow

long factorial_tail(long n, long acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);
}
/* gcc -O2 turns this into a loop. Abridged output (x86-64):
factorial_tail:
    mov  rax, rsi       ; acc
.L2:
    imul rax, rdi       ; acc = acc * n
    ...                 ; n = n - 1 (unrolled twice)
    jne  .L2            ; jump back: no call, no new frame
    ret */

09 · THE BLOW-UP

The exponential blow-up

The Fibonacci numbers go 0, 1, 1, 2, 3, 5, 8, 13 …: each is the sum of the two before. That definition turns straight into code with two recursive calls, and the calls form a tree instead of a tower. The stage draws every call fib(5) makes, in the order they happen. The lit path from the top to the cursor is the call stack at that moment; the tree is every stack the program ever had, laid side by side.

let calls = 0;
​
function fib(n) {
  calls++;
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}
​
console.log("fib(5) =", fib(5), "in", calls, "calls");
​
for (const n of [10, 20, 25]) {
  calls = 0;
  const v = fib(n);
  console.log("fib(" + n + ") =", v, "in", calls, "calls");
}

Count the boxes: f(3) is worked out twice, f(2) three times, f(1) five times. Every extra 1 on n multiplies the work by about 1.6 (the golden ratio), so the calls grow exponentially: 2·fib(n+1) − 1 of them.

The fix is to remember. A memo stores each answer the first time; after that, asking again costs one lookup. In the second half of the stage loop the repeated subtrees go dark and the gold boxes are memo hits: 9 calls instead of 15. For fib(70) it is 139 calls instead of about 600 trillion.

const memo = new Map();
let calls = 0;
​
function fibMemo(n) {
  calls++;
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);     // answered before: reuse it
  const v = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, v);
  return v;
}
​
console.log(fibMemo(5), "in", calls, "calls");
calls = 0;
memo.clear();
console.log(fibMemo(70), "in", calls, "calls");

// or skip recursion: build up from the bottom, keeping two numbers
function fibLoop(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  return a;
}
console.log(fibLoop(70));

10 · MAP, FILTER, REDUCE

Higher-order functions: map, filter, reduce

Because functions are values, a function can take another function as an argument, or return one. A function that does either is a higher-order function. You have already met one: makeCounter returns a function. The three you will use most take one, and they replace most loops over lists:

• map(fn): a new list with fn applied to every item.
• filter(fn): a new list of the items where fn says true.
• reduce(fn, start): combine all the items into one value, carrying a running result.

On the conveyor: 1 to 6 go through map and come out squared, filter drops the odd ones off the side, and reduce pours what is left into one total, 4 + 16 + 36 = 56.

const nums = [1, 2, 3, 4, 5, 6];
​
const squares = nums.map((x) => x * x);             // change each one
const evens = squares.filter((x) => x % 2 === 0);  // keep some
const total = evens.reduce((sum, x) => sum + x, 0); // combine into one
​
console.log(squares);
console.log(evens);
console.log(total);

There is no magic inside them. map is a loop you write once and never again:

// a function that takes a function: that's all "higher-order" means
function myMap(list, fn) {
  const out = [];
  for (const item of list) out.push(fn(item));
  return out;
}
​
// a function that returns a function
function multiplyBy(k) {
  return (x) => x * k;            // a closure over k
}
​
const triple = multiplyBy(3);
console.log(myMap([1, 2, 3], triple));
console.log(myMap(["a", "b"], (s) => s.toUpperCase()));

The same three ideas appear in every language, sometimes in disguise. Python prefers list comprehensions; SQL builds them into the language:

nums = [1, 2, 3, 4, 5, 6]
 
squares = [x * x for x in nums]
evens = [x for x in squares if x % 2 == 0]
total = sum(evens)            # functools.reduce does the general case
 
print(squares, evens, total)  # [1, 4, ..., 36] [4, 16, 36] 56

-- SQL says WHAT you want; map, filter and reduce are built in
SELECT SUM(x * x)          -- map (x * x), then reduce (SUM)
FROM nums
WHERE (x * x) % 2 = 0;     -- filter
-- 56

Because map treats every item separately, the items can be done in any order, or all at once. That is what a GPU does with pixels. In 2004 Google described MapReduce, a system that runs a map step and a reduce step over thousands of machines, named after these very functions (more in The Cluster).

11 · PURE VS SIDE EFFECTS

Pure functions and side effects

A pure function depends only on its arguments and does nothing but return a value. Same input, same output, every time, and nothing else in the world changes. addTax(100) is 125 today, tomorrow and on every computer.

Anything else a function does is a side effect: printing, changing a variable outside itself, writing a file, sending a request. Reading something hidden counts too: the clock, a random number, outside state. On the stage, the right-hand box is wired to all of them, and the same input, 100, gives 100, then 200, then 300.

// PURE: the answer depends only on the inputs, and nothing else changes
function addTax(price) {
  return price * 1.25;
}
​
// IMPURE: reads and changes the world outside it
let total = 0;
function addToTotal(price) {
  total = total + price;                  // changes outside state
  console.log("total is now", total);     // output is a side effect too
  return total;
}
​
console.log(addTax(100), addTax(100), addTax(100));
console.log(addToTotal(100), addToTotal(100), addToTotal(100));

// hidden inputs make a function impure too: same call, new answer
console.log(Math.random(), Math.random());
console.log(Date.now());
​
// mutating an argument is a side effect the caller may not expect
const scores = [30, 10, 20];
const sorted = scores.toSorted((a, b) => a - b);  // a new array
console.log(sorted, scores);                       // scores unchanged
scores.sort((a, b) => a - b);                      // sorts in place
console.log(scores);

Side effects aren't bad: they are the only reason to run a program (chapter 1 called them output). But pure functions are far easier to test, to reuse, to run in parallel and to cache (the memo trick only works on pure functions). So good programs keep a pure core, where the thinking happens, and push side effects out to a thin layer at the edge.