Blog post derives stack-based abstract machines from moded inference rules, showing how mode assignments (i/i/o, i/o/i, o/o/i) map to addition, subtraction, and nondeterministic enumeration.
Key Takeaways
Mode assignments on relations like plus determine which arguments are inputs vs. outputs, directly generating distinct abstract machines for each direction.
The transformation from natural/big-step semantics to abstract machines follows Hannan and Miller (1992) and Ager (2004); Simmons and Zerny (2013) coined the term “logical correspondence” by analogy with Reynolds’ functional correspondence.
Stack frames act as first-order continuations; the only frame needed for the addition machine is s _, which increments the result on return.
Nondeterminism and partiality emerge naturally once a relation is run at a mode that admits multiple solutions or undefined cases (e.g., natural number subtraction getting stuck).
The author flags that the logical correspondence applies beyond PL operational semantics to any indexed inductive definitions, including dependently-typed languages.
Hacker News Comment Review
No substantive HN discussion yet; the one comment points to Danvy’s “Rational Reconstruction of the SECD Machine” as a related deconstruction-reconstruction framing the same transformation as a bridge between operational and denotational semantics.
