Formal languages, and the three that selfie is made of: EBNF, C*, and RISC-U.
Marks on paper. Finite, discrete, checkable, copyable. 1 + 1, a staff of crotchets, H₂O, a line of code, this sentence.
What the marks are about. The number two. Sound in a room. A molecule that dissolves salt. A machine's behaviour over all inputs.
A semantics is a function from notation to meaning. Defining that function precisely is the founding act of every exact discipline — and computer science is where it was done most sharply, because a machine does exactly what the marks say and nothing else.
"I saw the man with the telescope." Two readings, one string. English resolves it with a shared world you and I already have. That shared world is why English is powerful — and why it cannot be a foundation. Its semantics is us, and we differ.
A formal language pays a price — narrowness, pedantry, effort — to buy one thing: a meaning that does not depend on who is reading.
| natural | formal |
|---|---|
| ambiguous | single-valued |
| elastic, forgiving | brittle, exact |
| persuades | proves |
| needs a mind | needs a machine |
| learned by living | defined by decree |
Prompting an AI in English is negotiation. Writing a test, a type, a schema, a unit, a contract is legislation.
= defines. | is or. { } is any number of, including none. [ ] is optional. ( ) groups. Quotes hold the literal characters. A full stop ends the rule.
So an integer is a digit followed by any number of digits: 0, 42, 007. A while statement is the word, a parenthesised expression, and either one statement or a braced block of them.
The synopsis of week 2 was this notation's cousin, a regular expression: braces, brackets, bars, and nothing else.
Every rule on the previous slide is a sentence of this language, these nine included. Check one: integer is a non_terminal, an =, an expression of one term of two factors, and a full stop.
Nothing strange happens: the text is finite, the reading terminates, the checker is the same stack machine as for any grammar. A text about texts is just another text.
Hold this example. It returns three times, harder each time: a compiler compiling itself, week 8; a program asked about its own halting, week 9; a kernel isolating itself, week 10. The same move on meaning, where the limits live.
Five statements: assignment, while, if-else, procedure call, return. Arithmetic + − * / %, comparison == != < > <= >=, the * that reads a pointer — hence the star in the name. No other types, no arrays, no Boolean operators.
It is a real subset of C: any C compiler compiles C*. And it is enough to write a compiler for itself, an emulator, and a hypervisor, which is the only argument for its size.
| group | instruction | what it does |
|---|---|---|
| initialise | lui rd,imm · addi rd,rs1,imm | put a number into a register |
| memory | ld rd,imm(rs1) · sd rs2,imm(rs1) | load a word from memory, store one |
| arithmetic | add · sub · mul · divu · remu | rd = rs1 ∘ rs2, unsigned |
| comparison | sltu rd,rs1,rs2 | rd = 1 if rs1 < rs2, else 0 |
| control | beq rs1,rs2,imm · jal rd,imm · jalr rd,imm(rs1) | branch if equal, jump and link, jump to a register |
| system | ecall | ask the operating system for something |
Every instruction is 32 bits. Every one of them also does pc = pc + 4, or says where pc goes instead. That is the entire machine language, and the machine chapter gives each line its exact meaning.
Source. while (c < 7) c = c + 1; — for you.
Assembly. Nine instructions with names — for the person reading the machine.
Bits. 0xFF01B283 and eight more words — the only thing the machine sees. Three notations. One meaning. The last one is the one that runs.
A finite state machine reads one character at a time and remembers only which circle it is in. That is enough for integers, identifiers, and the whole synopsis — anything a regular expression describes.
It is not enough for parentheses: matching every ( with its ) means counting without bound. Add a stack and you can: expressions, statements, procedures, all of C*, all of EBNF itself.
Regular inside context-free inside … — notation comes in sizes, a ladder, and week 9 says where it ends.
A grammar is a finite text. A program is a finite text. The binary the compiler produced is a finite sequence of bytes. The machine language is a table with fourteen rows.
Finite things from a finite alphabet can be listed: all of length one, then two, then three. Next week we do the listing, and it turns out that every program that will ever be written has a number — and that a compiler and an emulator are just arithmetic on those numbers.
Week 2: one prefix, two meanings. Week 3: one byte, five. Week 4: three notations, one meaning, fixed by decree. The decree is a program, and it is written in one of the three notations. That loop is the subject of week 8.
Countability: everything you can write down can be listed, so every program has a number — and a binary is one number, 188,392 bytes long. The compiler compiles itself and gets the same number twice.
Mozart · Symphony No. 41 “Jupiter” — Böhm, Vienna Philharmonic, 1979. The finale: a four-note motif and four other themes, combined by the rules of counterpoint in every way the rules allow. A grammar, derived to the end.
Introduction to the Theory of Computation — Sipser: regular and context-free languages done properly, chapters 1 and 2. And, more technical, What can we do about the unnecessary diversity of notation for syntactic definitions? — Wirth, 1977: the one page that gave us EBNF.