Philosophy:Matching logic

Matching logic is a family of formal systems that were created mainly to specify and reason about computer programs and their correctness. Compared to classical logics such as first-order logic, matching logic's formulas, called patterns, are interpreted as, not elements, but power sets of the underlying carrier set(s), with the intuition that a pattern is matched by the set of elements that "match" it. This way, matching logic is said to admit a semantics based on pattern matching.

Matching logic was initially coined by Grigore Rosu and finalized with Xiaohong Chen in 2019. Matching logic is the logical foundation of the K framework.

History

Early development

The term "matching logic" was coined in 2009. and has been used to refer to a couple of formal systems since then. In the early days, matching logic was represented in the literature as a formal system to specify and reason about computer programs' configurations. Together with a set of rules, it was used to specify and reason about the dynamic behaviors of computer programs.

The latter was later developed into reachability logic, which is a language-agnostic formal system with a fixed number of rules that provides sound and relatively complete formal verification capability for all programming languages. In these works of literature, matching logic is presented as an independent component of reachability logic.

Formalization as a standalone logic

The first paper that establishes matching logic as a standalone formal logic was published in 2017. There, matching logic was given an independent definition of its syntax, semantics, and proof system for the first time. In 2019, fixpoint constructors and proof rules were added to matching logic.

More recently, researchers have shown increasing interest in simplifying matching logic to a bare minimum. They aim to keep its expressive power intact during this process. All these formalizations exist in today's literature and sometimes appear under the same name "matching logic''.

Variants

We list them below in the chronological order:

1. "Matching logic", which is a many-sorted logic but has no fixpoint operators.
2. "Matching $\mu$-logic", which extends the LMCS'17 formalization with fixpoint operators and proof rules.
3. "Applicative matching logic", which is a restricted fragment that requires the signatures to include only one sort and only one non-constant symbol that is a binary symbol.

Since then, the term "matching logic" has been used to refer to any of the above formalizations in the literature. To avoid confusion, we shall present the formalization of the most complete version, matching $\mu$-logic. Then, we will present the other formalizations as variants.

Formal definition

Matching $\mu$-logic is defined through its syntax and semantics, which are detailed below.

Syntax

The syntax of matching logic specifies how patterns are constructed using variables, symbols, and logical connectives.

Signatures and variables

Matching logic is parametric on a many-sorted signature $(S,\mathrm{\Sigma })$ that has a set $S$ of sorts and an $(S^{*}\times S)$-indexed set $\mathrm{\Sigma }$ of many-sorted symbols, or simply symbols. A symbol $\sigma \in {\mathrm{\Sigma }}_{s_1\dots s_n,s}$ means that it takes $n$ arguments of sorts $s_1$, ..., $s_n$, respectively, and returns a value of sort $s$.

Let $(S,\mathrm{\Sigma })$ be a many-sorted signature. Let $\mathrm{E}\mathrm{V}={{\mathrm{\{}\mathrm{E}\mathrm{V}}_s\}}_{s\in S}$ and $\mathrm{S}\mathrm{V}={{\mathrm{\{}\mathrm{S}\mathrm{V}}_s\}}_{s\in S}$ be two disjoint families of $S$-indexed sets of variables. We call elements in $\mathrm{E}\mathrm{V}$ element variables, denoted $x:s$, $y:s$, ... and elements in $\mathrm{S}\mathrm{V}$ set variables, denoted $X:s$, $Y:s$, ...

Patterns

Matching logic formulas are called patterns. The set of $(S,\mathrm{\Sigma })$-patterns, or simply patterns, is an $S$-indexed set $\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}={{\mathrm{\{}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s\}}_{s\in S}$. We write ${\phi }_s\in \mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}$ or $\phi \in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$ to denote a pattern of a sort $s$. The set of all patterns is inductively defined by the following grammar rules:

• $x:s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$.
• $X:s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$.
• $\sigma ({\phi }_{s_1},\dots ,{\phi }_{s_n})\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$ for any $\sigma \in \mathrm{\Sigma }{s}_1\dots s_n,s$.
• ${\mathrm{\perp }}_s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$.
• ${\phi }_s\to \phi {\text{'}}_s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$.
• $\mathrm{\exists }x:s^{\prime }\cdot {\phi }_s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$. Note that $s^{\prime }$ and $s$ need not be the same.
• $\mu X:s\cdot {\phi }_s\in {\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}}_s$ if ${\phi }_s$ is positive in $X:s$.

Here, ${\phi }_s$ is positive in $X:s$ if every occurrence of $X:s$ lies within an even number of implication left-hand sides. For example, $X:s\to Y:s$ is positive in $Y:s$ but not in $X:s$. In contrast, $(X:s\to Y:s)\to X:s$ is positive in $X:s$ but not in $Y:s$.

Common notations

Notations can be defined in the usual way. The following are some standard notations:

• $\mathrm{\neg }{\phi }_s\equiv {\phi }_s\to {\mathrm{\perp }}_s$
• ${\mathrm{\top }}_s\equiv \mathrm{\neg }{\mathrm{\perp }}_s$
• ${\phi }_s\vee \phi {\text{'}}_s\equiv \mathrm{\neg }{\phi }_s\to \phi {\text{'}}_s$
• ${\phi }_s\wedge \phi {\text{'}}_s\equiv \mathrm{\neg }(\mathrm{\neg }{\phi }_s\wedge \mathrm{\neg }\phi {\text{'}}_s)$
• ${\phi }_s\leftrightarrow {{\phi }_s}^{\prime }\equiv ({\phi }_s\to \phi {\text{'}}_s)\wedge ({\phi }_s\to \phi {\text{'}}_s)$
• $\mathrm{\forall }x:s^{\prime }\cdot {\phi }_s\equiv \mathrm{\neg }\mathrm{\exists }x:s^{\prime }\cdot \mathrm{\neg }{\phi }_s$
• $\nu X:s\cdot {\phi }_s\equiv \mathrm{\neg }\mu X:s\cdot \mathrm{\neg }{\phi }_s[\mathrm{\neg }X:s/X:s]$

Here, ${\phi }_s[\mathrm{\neg }X:s/X:s]$ is the result of substituting every occurrence of $X:s$ for its negation $\mathrm{\neg }X:s$. One can verify that $\nu X:s\cdot {\phi }_s$ is well-formed if ${\phi }_s$ is positive in $X:s$.

Semantics

The semantics of matching logic defines how patterns are interpreted over models and valuations.

Interpretation of patterns

Matching logic formulas, called patterns, are interpreted not as true/false values, but as sets. Intuitively, a matching logic pattern $\phi$ is interpreted as the set of elements that "match" it.

Let $(S,\mathrm{\Sigma })$ be a signature. An $(S,\mathrm{\Sigma })$-model, or simply a model, is denoted $M=(\{M_s{\}}_{s\in S},{\{{\sigma }_M\}}_{\sigma \in \mathrm{\Sigma }})$. It consists of:

• A nonempty carrier set $M_s$ for every $s\in S$.
• A function ${\sigma }_M:M_{s_1}\times \dots \times M_{s_n}\to {𝒫}(M_s)$ for every $\sigma \in {\mathrm{\Sigma }}_{s_1\dots s_n,s}$.

Here, ${𝒫}(M_s)$ denotes the power set of $M_s$.

A valuation $\rho$ maps every element variable of sort $s$ to an element in $M_s$. It also maps every set element of sort $s$ to a subset of $M_s$. That is, $\rho (x:s)\in M_s$ and $\rho (X:s)\subseteq M_s$. Given a model $M$ and a valuation $\rho$, the interpretation of a pattern is ${\left|{\phi }_s\right|}_{M,\rho }\subseteq M_s$. This interpretation is inductively defined in the following way:

• ${\left|x:s\right|}_{M,\rho }=\{\rho (x:s)\}$
• ${|X:s|}_{M,\rho }=\rho (X:s)$
• ${|\sigma ({\phi }_{s_1},\dots ,{\phi }_{s_n})|}_{M,\rho }=\bigcup _{a_1\in {\left|{\phi }_{s_1}\right|}_{M,\rho }}\dots \bigcup _{a_n\in {\left|{\phi }_{s_n}\right|}_{M,\rho }}{\sigma }_M(a_1,\dots ,a_n)$
• ${\left|{\mathrm{\perp }}_x\right|}_{M,\rho }=\mathrm{\varnothing }$, the empty set.
• ${|{\phi }_s\to \phi {\text{'}}_s|}_{M,\rho }=M_s\setminus ({\left|{\phi }_s\right|}_{M,\rho }\setminus {\left|\phi {\text{'}}_s\right|}_{M,\rho })$, where "$\setminus$" denotes set difference.
• ${|\mathrm{\exists }x:s^{\prime }\cdot {\phi }_s|}_{M,\rho }=\bigcup _{a\in M_{s^{\prime }}}{\left|{\phi }_s\right|}_{M,\rho [a/x:s^{\prime }]}$, where $\rho [a/x:s^{\prime }]$ is the valuation that is identical to $\rho$ except that it maps to $x:s^{\prime }$ to $a$.
• ${|\mu X:s\cdot {\phi }_s|}_{M,\rho }=\bigcap \{A\subseteq M_s\mid {\left|{\phi }_s\right|}_{M,\rho [A/X:s]}\subseteq A\}$

Fixpoints and properties

By the Knaster-Tarski Fixpoint Theorem, $\mu X:s\cdot {\phi }_s$ is the least fixpoint of the function that maps $A\subseteq M_s$ to ${\left|{\phi }_s\right|}_{M,\rho [A/X:s]}$.

The following properties hold for common notations:

• ${\left|\mathrm{\neg }{\phi }_s\right|}_{M,\rho }=M_s\setminus {\left|{\phi }_s\right|}_{M,\rho }$
• ${\left|{\mathrm{\top }}_s\right|}_{M,\rho }=M_s$
• ${|{\phi }_s\vee \phi {\text{'}}_s|}_{M,\rho }={\left|{\phi }_s\right|}_{M,\rho }\cup {\left|\phi {\text{'}}_s\right|}_{M,\rho }$
• ${|{\phi }_s\wedge \phi {\text{'}}_s|}_{M,\rho }={\left|{\phi }_s\right|}_{M,\rho }\cap {\left|\phi {\text{'}}_s\right|}_{M,\rho }$
• ${|{\phi }_s\leftrightarrow \phi {\text{'}}_s|}_{M,\rho }=M_s\setminus ({\left|{\phi }_s\right|}_{M,\rho }\mathrm{\Delta }{\left|\phi {\text{'}}_s\right|}_{M,\rho })$, where "$\mathrm{\Delta }$" denotes the symmetric difference operator.
• ${|\mathrm{\forall }x:s^{\prime }\cdot {\phi }_s|}_{M,\rho }=\bigcap _{a\in M_{s^{\prime }}}{\left|{\phi }_s\right|}_{M,\rho [a/x:s^{\prime }]}$
• ${|\nu X:s\cdot {\phi }_s|}_{M,\rho }=\bigcup \{A\subseteq M_s\mid A\subseteq {\left|{\phi }_s\right|}_{M,\rho [A/X:s]}\subseteq A\}$

Applications

Matching logic is used with reachability logic by the K Framework to specify operational semantics and use them directly for formal verification, which forms an alternative approach to Hoare logic.

The fixpoint-free fragment of matching logic can be converted to first-order logic with equality. This conversion allows the K Framework to use existing Satisfiability modulo theories (SMT) solvers. These solvers help to find proofs for theorems.

See also

• Separation logic
• Hoare logic
• Regular expression, which matches sets of strings