The Software · Chapter 8
What is a language?

Watch the opener · 1:09

Transcript

What is a language? Last chapter's language could add A, B and C. A calculator does that much.

I figured a real language needs hundreds of features: multiply, divide, lists, everything. But ours never gets a multiply, and it multiplies anyway.

Add just three things. First, names that keep their values: product starts at zero. Second, steps that run one after another. Third, a loop: while i is less than B, run the body again. The body adds A to product, and adds one to i. With A as six and B as seven, the loop runs seven times. Product ends at forty-two. Nobody taught it to multiply. The loop did.

So a language is a calculator with memory, steps and a loop! State, sequencing and repetition are the whole of it, and they're enough.

Edit the loop below and run it. What else can you build from nothing but adding?

Chapter 7 ran a language of expressions. It could compute (a + b) + c, but only that: a fixed formula, evaluated once. A calculator does as much. This chapter asks what separates a programming language from a calculator, and the answer turns out to be small. Add three things, and the result can compute anything the machine can: a way to keep state, a way to do one thing after another, and a way to repeat.

A language has two halves. Syntax is the grammar: the rules that say which texts are programs and how they are shaped. Semantics is the meaning: what a program does once it is understood. This chapter builds both for a tiny imperative language, and uses them to compute something the expression language could not: multiplication expressed using only addition and repetition. This interpreter runs in Python with integers that do not wrap at eight bits. It retains the expression-tree idea, but it does not execute the CPU from Part I.

8.1 More than a calculator

The new language has statements, not just expressions. A statement changes the state of the program. There are two kinds. An assignment, name = expr ;, evaluates an expression and binds the result to a name, and a name can be reassigned: this is mutable state. A loop, while expr do …end, runs a block of statements over and over while a condition holds: this is control flow. Expressions are as before: sums of numbers, variables, and parenthesized groups, with one addition, a comparison a < b that yields 1 when true and 0 when false, so a loop has something to test.

State, sequencing, and repetition are the whole of it. They are also enough. With them, a program can build up a result step by step instead of in a single expression, and that is the leap from calculator to language.

Here is the program we will follow through the grammar, tree, and interpreter. Its inputs are a = 6 and b = 7; for multiplication, b must be a nonnegative integer.

product = 0;
i = 0;
while i < b do
  product = product + a;
  i = i + 1;
end

product starts at zero. Each pass adds a and advances i; once i reaches b, the comparison becomes zero.

8.2 Syntax: a grammar and a parser

The grammar is small enough to state in full:

A parser turns text that follows these rules into a tree, just as in Chapter 7, but now the tree has statement nodes above its expression nodes. Figure 8.2 shows the tree for the example program: two assignments, then a While whose body is two more assignments.

The parser is recursive descent again, with one method per grammar rule. The new rules are the statement-level ones: a method that reads a whole program as a list of statements, one that reads a single statement, and one that reads a loop, including its nested body.

Example 8-1. Recursive-descent parser for statements

class _Parser:
    """A recursive-descent parser for the statement and expression grammar."""

    def __init__(self, tokens: list[str]) -> None:
        self.tokens = tokens
        self.pos = 0

    def _peek(self) -> str | None:
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def _advance(self) -> str:
        if self.pos >= len(self.tokens):
            raise ValueError("unexpected end of input")
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def _expect(self, want: str) -> str:
        tok = self._advance()
        if tok != want:
            raise ValueError(f"expected {want!r}, got {tok!r}")
        return tok

    def program(self) -> list:
        """Parse statements until the tokens run out."""
        statements = []
        while self._peek() is not None:
            statements.append(self.statement())
        return statements

    def statement(self) -> tuple:
        """A statement is a while loop or an assignment."""
        if self._peek() == "while":1
            return self.loop()
        return self.assign()

    def loop(self) -> tuple:
        """while expr do <statements> end"""
        self._expect("while")
        cond = self.expr()
        self._expect("do")
        body = []
        while self._peek() not in (None, "end"):2
            body.append(self.statement())
        self._expect("end")
        return While(cond, body)

    def assign(self) -> tuple:
        """name = expr ;"""
        name = self._advance()
        if not name[0].isalpha():
            raise ValueError(f"expected a variable name, got {name!r}")
        self._expect("=")
        value = self.expr()
        self._expect(";")
        return Assign(name, value)

    def expr(self) -> tuple:
        """A sum, optionally compared with < to another sum."""
        left = self.addition()
        if self._peek() == "<":
            self._advance()
            return Less(left, self.addition())
        return left

    def addition(self) -> tuple:
        """A chain of atoms joined by +, grouped left to right."""
        node = self.atom()
        while self._peek() == "+":
            self._advance()
            node = Add(node, self.atom())
        return node

    def atom(self) -> tuple:
        """A number, variable name, or parenthesized expression."""
        tok = self._advance()
        if tok == "(":
            node = self.expr()
            self._expect(")")
            return node
        if tok[0].isdigit():
            return Num(int(tok))
        if tok[0].isalpha():
            return Var(tok)
        raise ValueError(f"unexpected token {tok!r}")

• a statement is a loop when it begins with while, otherwise an assignment; this single look-ahead is all the parser needs to choose
• a loop’s body is itself a list of statements, read until the matching end; because the body is read by the same statement method, loops nest inside loops with no extra machinery

8.3 Semantics: walking the tree

Syntax says how a program is shaped; semantics says what it means. The meaning is given by an interpreter, as in Chapter 7, but now it has two jobs. Evaluating an expression follows the same tree walk, now with ordinary integer sums and a comparison that returns 1 or 0. Executing a statement is the new part, and it is where state and control flow live.

Example 8-2. Executing a statement: assignment and the loop

def _exec(stmt: tuple, env: dict[str, int], steps: Iterator[int]) -> None:
    """Execute a statement, spending one step per assignment or condition test."""
    if isinstance(stmt, Assign):
        next(steps)
        env[stmt.name] = _eval(stmt.value, env)1
    else:  # a While loop runs its body until the condition is zero
        while True:
            next(steps)
            if _eval(stmt.cond, env) == 0:2
                break
            for inner in stmt.body:
                _exec(inner, env, steps)

• an assignment evaluates its right-hand side and writes the result into the environment, the dictionary of variable values; this is the mutable state, and it is what lets a later statement see an earlier one’s work
• the loop re-evaluates its condition and runs its body while the result is nonzero. This is the same branch-on-zero test the CPU’s JZ performs in Chapter 5: when the condition reaches zero, the loop ends.

The interpreter holds the program’s state in an ordinary dictionary and changes it as statements run, one after another. Sequencing is just the order of the statements; repetition is the while; state is the dictionary. That is the entire machinery of an imperative language.

The language itself permits nonterminating loops. To keep an experiment from running forever, this runner spends one step from a shared budget at every assignment and every condition test, including tests of an empty loop. The steps iterator supplies those steps; when it runs out, the outer interpreter raises an execution-limit error. The default is 10,000 steps across the whole program, including nested loops. Reaching the limit means the run was stopped, not that the program finished or has been proved nonterminating.

8.4 A loop turns addition into multiplication

Now the payoff. The machine of Part I has no multiply instruction; the expression language of Chapter 7 could only add. Yet the example program multiplies, by adding a to a running total b times:

inputs: {'a': 6, 'b': 7}
final state: {'a': 6, 'b': 7, 'product': 42, 'i': 7}
product = 42

With a as 6 and b as 7, the loop runs seven times, each pass adding 6, and product ends at 42. Multiplication was never added to the language or the machine. It emerged from a loop over addition. That is what control flow buys: expressiveness the hardware does not have on its own.

Figure 8.3 traces the loop, and names the Chapter 5 instructions that would run it. The condition is tested each pass. While it is nonzero, the body runs and an unconditional JUMP returns to the test. When the condition reaches zero, the JZ branch is taken, jumping past the body and ending the loop. JUMP has been in use since Chapter 6, but JZ, the conditional branch built in Chapter 5, at last shows what it is for: it is exactly what a loop needs to exit. This chapter interprets the comparison and loop directly. The next chapter changes the example to count down to zero, then runs the resulting jumps on a named-memory model with the same branch behavior.

The interactive version needs the in-browser runtime.

The interpreter walks the tree; the next chapter shows the concrete countdown source and compiles its loop into jumps.

Exercises

• Add an if-statement to the language, and run a program that uses it.
• Write a program in this language that sums the numbers from one to five, and interpret it.