  This paper presents the Relational Machine Calculus (RMC): a simple,
foundational model of first-order relational programming. The RMC originates
from the Functional Machine Calculus (FMC), which generalizes the
lambda-calculus and its standard call-by-name stack machine in two directions.
One, "locations", introduces multiple stacks, which enable effect operators to
be encoded into the abstraction and application constructs. The second,
"sequencing", introduces the imperative notions of "skip" and "sequence",
similar to kappa-calculus and concatenative programming languages. The key
observation of the RMC is that the first-order fragment of the FMC exhibits a
latent duality which, given a simple decomposition of the relevant
constructors, can be concretely expressed as an involution on syntax.
Semantically, this gives rise to a sound and complete calculus for string
diagrams of Frobenius monoids. We consider unification as the corresponding
symmetric generalization of beta-reduction. By further including standard
operators of Kleene algebra, the RMC embeds a range of computational models:
the kappa-calculus, logic programming, automata, Interaction Nets, and Petri
Nets, among others. These embeddings preserve operational semantics, which for
the RMC is again given by a generalization of the standard stack machine for
the lambda-calculus. The equational theory of the RMC (which supports reasoning
about its operational semantics) is conservative over both the first-order
lambda-calculus and Kleene algebra, and can be oriented to give a confluent
reduction relation.
