# Matching Logic

Operational semantics are typically used to derive concrete program behaviors, but not to specify and prove properties about programs. The latter are traditionally done using axiomatic semantics. Unfortunately, axiomatic semantics of real languages are rather complex, so correctness proofs are necessary in order to trust the proven properties. Moreover, such proofs have to be maintained as the language changes, which is generally perceived as a burden. Ideally, we would like to have *one* language semantics, with that semantics used both
for deriving program behaviors and for verifying programs.

Matching logic allows us to regard a language through both operational and axiomatic lenses at the same time, making no distinction between the two. A programming language is given a semantics as a set of rewrite rules. A language-independent proof system can then be used to derive both operational behaviors and formal properties of a program. In other words, one matching logic semantics fulfills the roles of both operational and axiomatic semantics in a uniform manner. The state structure plays a crucial role in matching logic semantics. Program states are represented as algebraic datatypes called (concrete) *configurations*, while program state specifications are represented as configuration terms, with variables and constraints over them, called (configuration) *patterns*. A pattern specifies those configurations that *match* it.

## Website

There is a dedicated website at http://matching-logic.org

## Quick Overview

- Latest: PPTX PDF
- The K and matching logic webpage at UIUC, which contains slides and an interview.

## Download and Online Interface

We have implemented a proof-of-concept matching logic verifier for a fragment of C, called MatchC.

- --- This link provides an online interface to running MatchC
- Download --- We recommend to first try it online (see the link above)

We have formalized the proof system in Coq, including the soundness proof and applications. The Coq latest files are available here.

## Select Publications

Here are the most relevant publications on matching logic:

- A language-independent matching logic reachability proof system for conditional operational semantics (like big-step and small-step):

*One-Path Reachability Logic*- Grigore Rosu and Andrei Stefanescu and Stefan Ciobaca and Brandon Moore
, IEEE, pp 358-367. 2013**LICS'13**

PDF, Slides(PPTX), Reachability Logic, LICS'13, BIB

- A language-independent program verification framework, including the MatchC verifier, with soundness and relative completeness proofs:

*Checking Reachability using Matching Logic*- Grigore Rosu and Andrei Stefanescu
, ACM, pp 555-574. 2012**OOPSLA'12**

PDF, Slides(pptx), Slides(pdf), Matching Logic, OOPSLA'12, BIB

- The relationship to Hoare logic, including a mechanical translation of Hoare logic proofs into matching logic reachability proofs:

*From Hoare Logic to Matching Logic Reachability*- Grigore Rosu and Andrei Stefanescu
, LNCS 7436, pp 387-402. 2012**FM'12**

PDF, Slides(pptx), Slides(pdf), Matching Logic, FM'12, , BIB

- A language-independent matching logic reachability proof system for unconditional operational semantics (like evaluation contexts):

*Towards a Unified Theory of Operational and Axiomatic Semantics*- Grigore Rosu and Andrei Stefanescu
, LNCS 7392, pp 351-363. 2012**ICALP'12**

PDF, Slides(pptx), Slides(pdf), Matching Logic, ICALP'12, BIB

## Other

### Older slides

### Old implementations

### Complete list of Publications (reverse chronological order)

Checking Reachability using Matching Logic- Grigore Rosu and Andrei Stefanescu
, ACM, pp 555-574. 2012OOPSLA'12

PDF, Slides(pptx), Slides(pdf), Matching Logic, OOPSLA'12, BIBReachability Logic- Grigore Rosu, Andrei Stefanescu, Stefan Ciobaca and Brandon Moore
http://hdl.handle.net/2142/32952, July 2012Technical Report

PDF, TR@UIUCFrom Hoare Logic to Matching Logic Reachability- Grigore Rosu and Andrei Stefanescu
, LNCS 7436, pp 387-402. 2012FM'12

PDF, Slides(pptx), Slides(pdf), Matching Logic, FM'12, , BIBTowards a Unified Theory of Operational and Axiomatic Semantics- Grigore Rosu and Andrei Stefanescu
, LNCS 7392, pp 351-363. 2012ICALP'12

PDF, Slides(pptx), Slides(pdf), Matching Logic, ICALP'12, BIBMatching Logic Rewriting: Unifying Operational and Axiomatic Semantics in a Practical and Generic Framework- Grigore Rosu and Andrei Stefanescu
http://hdl.handle.net/2142/28357, November 2011Technical Report

PDF, Matching Logic, TR@UIUC, , BIBThe Rewriting Logic Semantics Project: A Progress Report- Jose Meseguer and Grigore Rosu
, LNCS 6914, pp 1-37. Invited talk. 2011FCT'11

PDF, K Tool, FCT'11, BIBMatching Logic: A New Program Verification Approach (NIER Track)- Grigore Rosu and Andrei Stefanescu
, ACM, pp. 868-871. 2011ICSE'11

PDF, Slides(pptx), Slides(pdf), Poster(pptx), Poster(pdf), Matching Logic, ACM, NIER ICSE'11, BIBMatching Logic: A New Program Verification Approach- Grigore Rosu and Andrei Stefanescu
. 2010UV'10

PDF, Slides(pptx), Slides(pdf), Matching Logic, K framework, UV'10, BIBMatching Logic: An Alternative to Hoare/Floyd Logic- Grigore Rosu, Chucky Ellison and Wolfram Schulte
, LNCS 6486, pp 142-162. 2010AMAST'10

PDF, Slides(PPT), Slides(PDF), LNCS, AMAST'10, BIBFrom Rewriting Logic Executable Semantics to Matching Logic Program Verification- Grigore Rosu, Chucky Ellison and Wolfram Schulte
http://hdl.handle.net/2142/13159, July 2009Technical Report

PDF, TR@UIUC, BIBMatching Logic --- Extended Report- Grigore Rosu and Wolfram Schulte
UIUCDCS-R-2009-3026, January 2009Technical Report

TR@UIUC, BIB