Implementing SNOBOL4#
Week 1 — Why SNOBOL
Bell Labs, 1962#
Holmdel, New Jersey. A department working on high-level, nonnumerical computation.
David J. Farber, Ralph E. Griswold, Ivan P. Polonsky needed a better tool for manipulating symbolic expressions in their own research — and built one, rather than waiting for one to exist.
Not a product. A tool that got used.#
SNOBOL was not commissioned. It grew out of what its own authors needed for their own work, then kept getting used because it kept working.
“SNOBOL, SNOBOL2, and SNOBOL3 [are] more properly considered separate languages than versions of one language.”
— Ralph Griswold, 1981
SNOBOL4: the fourth language, not the fourth patch#
- designed from 1966, running by 1967
- unlimited-length strings
- pattern matching promoted to a first-class data type
- arrays, tables
- SIL: a portable implementation strategy — a hypothetical assembly language for an abstract machine
SIL bought SNOBOL4 reach#
Write the interpreter against a small virtual instruction set, not any one machine’s assembler.
Result: roughly fifty machines and operating systems by the late 1970s.
The naming story — two tellings, neither fully verifiable#
Griswold’s own account: he coined “SNOBOL,” then reverse-engineered “StriNg Oriented symBOlic Language” afterward, as a joke.
Farber’s account: a “snowball’s chance in hell” moment, over coffee.
Why this course takes no side#
Both tellers were there. They disagree on the mechanism, not just the colour.
A small, concrete lesson about oral history vs. primary documents — and it matters more to how you read sources than the specific fact does.
Why SNOBOL4, specifically, in a compilers course#
Not sentiment. A structural reason.
What makes SNOBOL4 different#
A “build a compiler for a C-like language” course teaches you a lot. It does not teach you this:
pattern matching as a first-class, backtracking data type — not syntax bolted onto a regular-expression engine.
Where the semester actually goes#
| Movement | Weeks | What |
|---|---|---|
| I | 1–4 | Calculator that talks back |
| II | 5–6 | Programs that can fail |
| III | 7–9 | The pattern engine |
| IV | 10–12 | What kind of thing is a value |
Movement III is the centre of gravity. Everything before it is preparation, honestly framed as such.
A course designed not to be abandoned in week 6#
Weeks 1–4 already produce something you can run: a calculator. Small, but load-bearing — everything later sits on top of it, not beside it.
Why OCaml#
Two structural properties of SNOBOL4 map directly onto language features, not library support.
Property one: success/failure is the only branch#
No if. No while. No for.
Every SNOBOL4 statement succeeds or fails — that signal, not a boolean, is the language’s only control-flow primitive.
This is what a sum type is built to express.
Property two: every value is dynamically tagged#
A variable can hold a string, an integer, a real, a pattern, an array, a table, or a programmer-defined record.
In OCaml: one variant type, one constructor per SNOBOL type — the compiler checks every place that inspects a value handles every case.
Property three (arriving week 7): backtracking is a recursive interpreter#
Try an alternative; on failure, unwind and try the next one.
A standard shape for a small recursive interpreter in a language with pattern matching and sum types built in.
Andrew Appel’s Modern Compiler Implementation in ML builds an entire compiler this way — this course borrows the structure, swaps the toy source language for a real, historically significant one.
By the end of this week#
A toy calculator: read an integer literal, evaluate it.
A hand-rolled lexer — not ocamllex — because SNOBOL4’s blank-sensitive
operators need an explicit scan, not a generated automaton’s regex rules.
A hand-built or generator-built parser for the rest, whichever a given
week’s grammar calls for.