Week 7 Studio: Building the backtracking search

Literal, concatenation, and alternation as pattern values, matched against a subject with an explicit backtracking stack — or OCaml's own call stack, your choice

5 April 2027

Before the session#

Bring Movement II’s complete statement executor: labeled statements, the goto field, and DEFINEd functions with call frames. This session starts a new movement and a new value type rather than extending anything from Movement I or II directly — a pattern doesn’t need statements or function calls to exist, only a subject string and a cursor.

In the session#

• Give patterns a type. Define an OCaml variant wide enough for this week’s three primitives: a literal string, concatenation of two patterns, and alternation of two patterns. Nothing here needs mutable state — a pattern is inert data until it is matched against something, which is exactly what makes it reusable.
• Write a matching procedure that respects the cursor contract. Whatever shape your matcher takes, it must satisfy the three conditions from this week’s lecture: never touch the subject string; only ever move the cursor forward, or leave it where it is, while succeeding; and restore it exactly on failure. Get this right for the three primitives above before adding anything else — every later week’s primitive depends on it holding.
• Pick a backtracking strategy, and know that you are picking one. Implement alternation’s retry-on-failure behaviour either with an explicit stack of pending alternatives (mirroring the real runtime’s Pattern-Matching History List, as covered in lecture) or by using OCaml’s own recursion and letting the call stack do the bookkeeping. Try the explicit-stack version at least once this session, even if you end up preferring recursion for the rest of the course — building it by hand once is what makes the lecture’s tradeoff concrete rather than abstract.
• Reproduce the illusion, in miniature. Instrument your matcher (a print statement is enough) to log every cursor position it visits and every alternative it tries, then run a small alternation of literals — something in the shape of ("A"|"B") — against a subject, unanchored, where a B occurs earlier than any A. Confirm the trace shows both alternatives tried at position 0 before the cursor ever advances, and that the match found is the earliest position where either alternative succeeds, not the earliest occurrence of whichever alternative happens to be written first.

Sample transcript#

Genuine captured output from this course’s own week-7 reference matcher, run against an alternation pattern (once plain, once with a --trace flag added for this session) and a DEFINEd predicate function built from alternation:

$ dune exec bin/main.exe -- examples/alt.sno
MATCHED

$ dune exec bin/main.exe -- examples/alt.sno --trace
matching against "ZZBA"
  trying match at position 0
    at 0: trying first alternative, recording second on the history list
    "A" fails at 0
    backtrack: resuming recorded alternative at 0
    "B" fails at 0
  trying match at position 1
    at 1: trying first alternative, recording second on the history list
    "A" fails at 1
    backtrack: resuming recorded alternative at 1
    "B" fails at 1
  trying match at position 2
    at 2: trying first alternative, recording second on the history list
    "A" fails at 2
    backtrack: resuming recorded alternative at 2
    "B" matches at 2
    matched, cursor now at 3
MATCHED

$ dune exec bin/main.exe -- examples/define_match.sno
NO
YES

The trace is worth reading line by line: at every position from 0 to 2, "A" is tried and fails before "B" is ever tried — even though 'B' occurs earlier in the subject "ZZBA" than 'A' does — which is exactly the “both alternatives tried at this position before the cursor advances” behaviour this week’s spec asks you to demonstrate, not a coincidence of this particular subject.

This week’s real starter — the pattern type in place, with the matcher’s backtracking left as the gap to fill in — is downloadable at week-07-starter.zip.

Afterwards#

You now have a pattern value, a cursor that behaves correctly under the three-condition contract, and a working backtracking search over concatenation and alternation. Next week adds the primitives that make patterns actually useful against real text — ANY, NOTANY, SPAN, BREAK, ARB, ARBNO, BAL — on top of exactly this search, with no change to how backtracking itself works.