Algorithm explainers

The techniques cobble's field dataflow is built on, for engineers who have not met them before. Each page states a problem, walks a small COBOL program one statement at a time with the analysis state after each, and ends with the precise rule and where it goes wrong.

Read them in order; each page's "Read first" line names what it actually depends on.

1. Visiting a graph: BFS, DFS and reverse postorder — the standard orders for walking a program's statements, and why reverse postorder hands every statement its input complete.
2. Fixpoints and worklists — how an analysis handles loops: apply the rules until nothing changes, and why the visiting order matters for cost but not for the answer.
3. Gen/kill and reaching definitions — for every read, which writes could have produced the value it sees, and why only a certain overwrite may discard one.
4. Byte-extent aliasing — fields as byte ranges: how groups, REDEFINES and partial writes alias, and why overlapping is not the same as covering.
5. Value sets and dynamic calls — resolving CALL WS-PGM statically by tracking the values a field can hold, and the reasons that set may be incomplete.

Making it finish on a large corpus — the techniques that took the dynamic-call-target pipeline from not finishing to finishing, continuing the numbering above:

6. Area need — which bytes of a commarea, USING or RETRIEVE INTO area anyone actually reads, so the fixpoint tracks those and not the whole area.
7. Resolving a dynamic call site inside its own program — reaching definitions of literals decide where a site can go, so its program is charged only those callees' needs instead of everyone's.
8. Rounds across programs — area need settles in rounds, and each round after the first walks only the programs whose inputs changed.
9. Sweeps — a fixpoint with a budget of reverse-postorder sweeps, and a mark on every result that did not settle within it.
10. Answering every walk once — strongly connected components and a memo, so thousands of walks over the same places cost one walk; plus place identity and an edge index.
11. Bounding walks by crossings — a limit on program crossings per walk that marks every result it cut, and how to pick the limit.

Background — the COBOL and CICS vocabulary, and one graph technique several pages lean on:

• COBOL and CICS in 60 seconds — the minimum vocabulary to follow the explainers: fields, MOVE, PERFORM, REDEFINES, commarea, LINK, XCTL, and the CSD.
• Strongly connected components — the groups of statements, or programs, that can all reach each other, found in one depth-first walk with Tarjan’s algorithm; what answering every walk once, reducibility and DJ graphs build on.

Related — not part of cobble's own build-up, each pulled from wherever it actually came from:

• Dominance and reachability — from cobol-rekt's catalogue, and the post-dominator half from a separate Java method-narration tool; where a branch's arms come back together, exactly which statements are inside a loop, and why carrying one pointer per statement instead of a whole candidate set makes every visit cheap.
• Tree zippers — a data structure, not an analysis, from cobol-rekt's catalogue; a cursor into an immutable tree that remembers the way back up, so an edit deep inside never has to re-walk from the root to find the ancestors it must rebuild — shown as a simplified, ancestor-only variant of Huet's zipper.
• Reducibility and loop detection — also from cobol-rekt's catalogue; three ways to tell a loop with one entry from a loop with two, all three agreeing on the same three-node counter-example.
• DJ graphs and natural loop bodies — Sreedhar, Gao and Lee's technique behind reducibility's third method above; the exact statement set of every loop's body, nested ones told apart from the outer loops around them, in one bottom-up pass.
• Reaching conditions — also from cobol-rekt's catalogue; not to be confused with reaching definitions above — this is the boolean condition on the data that must hold to reach a statement at all, not which write a read sees.
• Eliminating GOTOs — also from cobol-rekt's catalogue; a forward jump becomes an IF, a backward jump becomes a loop, and a jump into an outer scope climbs there one level at a time.
• The structured program theorem — Böhm and Jacopini's guarantee that any flowchart can be rewritten with only sequence, selection and iteration, why that guarantee quietly needs an extra variable more often than the one-sentence version admits, and why that generic construction is a theoretical guarantee here, not something eliminating GOTOs' local rules ever run.