What a program is

01 · INPUT → OUTPUT

Input, process, output

A calculator takes keypresses (input), does arithmetic (process) and shows digits (output). A music app takes a file and turns it into sound. A website takes your click and sends back a page. Under the variety, almost every program has the same shape.

The computer brings two things to this: it never gets bored, and it does exactly what it is told. It doesn't know what you meant. A modern processor core can carry out billions of simple instructions a second, so a program is really a way of breaking what you want into steps small and precise enough for a machine.

// INPUT: a value comes in
const celsius = 21;
​
// PROCESS: a rule turns it into a new value
const fahrenheit = celsius * 9 / 5 + 32;
​
// OUTPUT: the result goes somewhere you can see it
console.log(celsius + "°C is " + fahrenheit + "°F");

02 · SOURCE TEXT

Source code is just text

You write programs as text in a programming language: a language with rules strict enough that a machine can follow them. This is the program the 3D follows, in JavaScript, the language every web browser runs:

let total = 2 + 3;
console.log(total * 4);

It stores 2 + 3 under the name total, then prints total times 4. You can probably already see it will print 20. The computer can't "see" anything: to it this file is a row of numbers, one per character. The bars over the editor show them.

const source = "let total = 2 + 3;";
​
for (const ch of source) {
  console.log(JSON.stringify(ch), ch.codePointAt(0));
}

03 · TOKENS

Tokens: the lexer reads the words

The first thing any language implementation does is lexing (or scanning): it walks the characters and groups them into tokens, the language's words and punctuation. let is a keyword, total is a name, = and + are operators, 2 is a number, ; ends a statement. Spaces and comments are thrown away.

In the 3D, the program's text lifts off the editor and becomes sixteen tiles, coloured by kind. Here is a working lexer for a small slice of JavaScript, in 20 lines:

function tokenize(src) {
  const tokens = [];
  let i = 0;
  while (i < src.length) {
    const ch = src[i];
    if (ch === " ") {
      i++;                          // whitespace: skip it
    } else if (/[0-9]/.test(ch)) {
      let num = "";
      while (i < src.length && /[0-9]/.test(src[i])) num += src[i++];
      tokens.push(["number", num]);
    } else if (/[a-z]/i.test(ch)) {
      let word = "";
      while (i < src.length && /[a-z0-9]/i.test(src[i])) word += src[i++];
      tokens.push([word === "let" ? "keyword" : "name", word]);
    } else {
      tokens.push(["symbol", ch]);  // = + ; and friends
      i++;
    }
  }
  return tokens;
}
​
tokenize("let total = 2 + 3;");

Real lexers are the same idea with more cases: strings, comments, decimals, ===. V8, the engine in Chrome and Node.js, has a hand-tuned scanner, because every web page's JavaScript passes through it before anything else can happen.

04 · PARSE TREE

The parse tree: finding the structure

A list of tokens isn't enough. In 2 + 3 * 4, which happens first? The parser checks the tokens against the language's grammar and builds a tree that shows how they belong together. Operators that bind tighter, like *, end up lower in the tree, and the tree is worked out from the bottom up.

On the stage, the tokens rearrange into the tree for the whole program: a declaration of total holding a +, and a call to console.log holding a *. Punctuation like ; and ( ) has done its job and folds away. This tree is called an abstract syntax tree, or AST.

// The grammar, loosest-binding rule first:
//   sum     = product (("+" | "-") product)*
//   product = number  (("*" | "/") number)*
function parse(tokens) {
  let pos = 0;
  function sum() {
    let node = product();
    while (tokens[pos] === "+" || tokens[pos] === "-") {
      const op = tokens[pos++];
      node = { op, left: node, right: product() };
    }
    return node;
  }
  function product() {
    let node = Number(tokens[pos++]);
    while (tokens[pos] === "*" || tokens[pos] === "/") {
      const op = tokens[pos++];
      node = { op, left: node, right: Number(tokens[pos++]) };
    }
    return node;
  }
  return sum();
}
​
const tree = parse("2 + 3 * 4".split(" "));
console.log(JSON.stringify(tree, null, 2));

If the tokens don't fit the grammar, there is no tree, and the program never starts. That is a syntax error. Predict what this prints before you run it:

console.log("Does this line run?");
​
let total = ;

Nothing printed, not even the first line, because the whole file is parsed before any of it runs.

05 · BYTECODE

Bytecode: a list of tiny steps

A tree is easy to understand but slow to walk. So most language implementations compile it: they walk the tree once and write out a flat list of very simple instructions. Visit the children first, then the operator, and you get a perfect recipe for a stack machine: push the numbers, then combine them.

In the 3D, each bytecode instruction is born from the tree node it came from, in exactly that order. The lights on each brick are its opcode: in our toy machine PUSH is 1, ADD is 2, STORE is 3, and so on. To a computer, instructions are numbers too.

function compile(node, out = []) {
  if (typeof node === "number") {
    out.push("PUSH " + node);
  } else {
    compile(node.left, out);    // children first...
    compile(node.right, out);
    out.push({ "+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV" }[node.op]);
  }                             // ...then the operator
  return out;
}
​
// the tree for (2 + 3) * 4
const tree = { op: "*", left: { op: "+", left: 2, right: 3 }, right: 4 };
compile(tree);

06 · RUNNING IT

Running it: fetch, decode, execute

Now something has to run the instructions. A virtual machine is a loop: fetch the next instruction, decode what it means, execute it, move the program counter on, repeat. On the stage the PC arrow walks down the bricks, each one fires at the chip, and the stack of values rises and falls: 2, then 2 and 3, then 5 (stored as total), then 5 and 4, then 20.

const program = ["PUSH 2", "PUSH 3", "ADD", "PUSH 4", "MUL", "PRINT"];
const stack = [];
let pc = 0;                  // program counter: which instruction is next
​
while (pc < program.length) {
  const [op, arg] = program[pc].split(" ");
  if (op === "PUSH") stack.push(Number(arg));
  if (op === "ADD") stack.push(stack.pop() + stack.pop());
  if (op === "MUL") stack.push(stack.pop() * stack.pop());
  if (op === "PRINT") console.log(stack.pop());
  pc++;
}

A CPU does the same dance in hardware, billions of times a second, on machine code: instructions encoded as bytes it can decode directly. A virtual machine is itself a program running as machine code, so the toy stack machine above is running on a real one underneath. To watch a real fetch–decode–execute cycle tick by tick, open Inside the CPU.

07 · OUTPUT

Output: the program touches the world

Our PRINT became console.log, which sends the characters 2 and 0 to a console, which asks the operating system to draw them, which ends as pixels on your screen. Output is anything a program does to the world: text, pixels, sound, a file on disk, a packet on the network. Programmers call these side effects.

A common beginner mix-up: returning a value is not the same as printing it. A function that returns a value hands it back to the code that called it, silently. Only output reaches a person.

function double(n) {
  return n * 2;            // hands a value back; prints nothing
}
​
const x = double(21);
console.log("x is", x);    // output: something you can see
x * 10                     // the last value is shown below, after →

08 · LANGUAGES

Languages: compiled, interpreted, and both

Every language makes the same journey (text, tokens, tree, instructions) but stops at different places. Here is our program in two more languages:

total = 2 + 3
print(total * 4)

Python (the usual implementation, CPython) compiles your file to bytecode and then interprets that bytecode. Notice that it never adds 2 and 3 at run time: the compiler already folded them into 5, a trick called constant folding.

LOAD_CONST   5        # 2 + 3 was folded before it ran
STORE_NAME   total
LOAD_NAME    print
LOAD_NAME    total
LOAD_CONST   4
BINARY_OP    *
CALL         1

#include <stdio.h>
 
int main(void) {
    int total = 2 + 3;
    printf("%d\n", total * 4);
    return 0;
}

C is compiled ahead of time, all the way to machine code, into a file the CPU runs directly. Unoptimised, the arithmetic could look like this x86-64 code; the bytes on the right are the actual machine code. An optimising compiler would fold the whole thing to 20.

mov  eax, 2         ; bytes: b8 02 00 00 00
add  eax, 3         ; bytes: 83 c0 03
imul eax, eax, 4    ; bytes: 6b c0 04

JavaScript in V8 does both. It parses and compiles to bytecode, starts interpreting at once, watches which functions run hot, and compiles those to machine code while the program is running (Sparkplug, Maglev and TurboFan are its compilers). That is called just-in-time (JIT) compilation, and it is why "compiled or interpreted?" describes an implementation, not a language.