The cursor, made visible#

A pattern is a value#

Not syntax. A value — of its own distinct type, on equal footing with an integer or a string.

Built once. Stored in a variable. Passed to a function. Matched against many subjects over its lifetime.

Built from exactly two operators#

• concatenation — plain juxtaposition, same as week 4’s strings
• alternation — |

Closed under both. Gimpel (1973) shows both are associative, and that concatenation distributes over alternation from the right.

What closure buys you#

Build a small library of named patterns once —

WORD, NUMBER, WHITESPACE

— and combine them into a larger pattern without writing a single new primitive matching procedure.

Two things a match happens over#

Subject: a string. Never modified by a match attempt.

Cursor: an integer sitting between characters — position 0 is before the first character, position n is after the last.

Griswold’s three conditions#

Any correct matching procedure must:

1. not change the value of the subject
2. leave the cursor between where it started and the end of the subject — never backward, within one successful step
3. on failure, leave the cursor exactly where it found it

Every primitive obeys exactly these three rules#

A literal. ANY. BREAK. ARB. Everything weeks 8 and 9 add.

Nothing more, nothing less.

'--1B-A-' (ANY('AB') | '1' ABORT)#

What do you expect?

What actually happens#

All alternatives of | are tried at the current cursor position before the cursor is ever allowed to advance.

Only once every alternative fails at a position does the cursor move forward — and the whole set gets tried again.

Tracing it#

At cursor 0: -. Neither alternative matches. Cursor advances.

…repeats until cursor reaches 1.

At 1: the second alternative matches — and hits ABORT.

The match fails outright. The matcher never reaches the B.

Unlearning the habit#

The fastest way: trace it by hand, or watch an instrumented matcher print every cursor position it visits.

ANY('AB') does not scan ahead. It has no memory of what’s further along the string.

The same design, decades later, independently#

GNAT’s GNAT.Spitbol.Patterns Ada library: a chain of pattern nodes with a successor pointer, and an explicit stack of (cursor, node) pairs.

Two implementations, decades apart, different languages — same shape. Not an accident of 1970s assembly conventions.

OCaml hands you exactly that stack#

“Try the next alternative” → an ordinary recursive call.

“Give up and backtrack” → a return from that call.

The OCaml runtime’s call stack does the bookkeeping SIL’s PDLPTR/PDLHED history list does by hand.

Not a lesser version#

Griswold’s three-condition contract places no requirement on how backtracking is implemented — only on what a procedure preserves.

Either strategy satisfies it. Either can also violate it, if built carelessly.

What the hand-maintained version costs#

Profiling the real 1981 IBM/360 build: procedure call/return bookkeeping and eight-byte descriptor moves together account for very roughly half of all measured execution time.

Building your own stack discipline by hand is not free just because you control it directly.