GoKawiilAbstract machines for logic programs
06 Apr, 2026
[Based on conversations with Rob Simmons. Reader prerequisites: comfortable with inference rules, peano notation, state machines.]
The following inference rules, it can be argued, define addition: whenever plus N M P holds, the numbers N and M sum to P .
----------------- pz plus 0 N N plus N M P -------------------- ps plus (s N) M (s P)
With these rules, here's a derivation that 2 + 2 = 4:
----------------- pz plus 0 2 2 --------------- ps plus 1 2 3 --------------- ps plus 2 2 4
Inference rule sets aren't inherently programs, they are just definitions of relations. To use our definition of addition to calculate, we have to think of what we're doing as searching for a number X such that plus N M X holds, given N and M as inputs. The purpose of logic programming is to let us "run" a set of inference rules (perhaps together with a query) as a program. What mental model can we use to think about how a logic program runs, step by step?
Stack machines.
Here is a program, specified as a state machine, that evaluates queries of the form plus N M _ , where N and M are known (in logic programming lingo, they are ground, which means they contain no logic variables that need solving-for):
... continue reading