SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Wed 20 Oct 2021 16:10 - 16:25 at Zurich G - OOPSLA 2020 Papers 3 Chair(s): Anders Miltner

Automation of fixpoint reasoning has been extensively studied for various mathematical structures, logical formalisms, and computational domains, resulting in specialized fixpoint provers for heaps, for streams, for term algebras, for temporal properties, for program correctness, and for many other formal systems and inductive and coinductive properties. However, in spite of great theoretical and practical interest, there is no unified framework for automated fixpoint reasoning. Although several attempts have been made, there is no evidence that such a unified framework is possible, or practical. In this paper, we propose a candidate based on matching logic, a formalism that is recently shown to theoretically unify the above mentioned formal systems. Unfortunately, the Knaster-Tarski proof rule of matching logic, which enables inductive reasoning, is not syntax-driven. Worse, it can be applied at any step during a proof, making automation seem hopeless. Inspired by recent advances in automation of inductive proofs in separation logic, we propose an alternative proof system for matching logic, which is amenable for automation. We then discuss our implementation of it, which although not superior to specialized state-of-the-art automated provers for specific domains, we believe brings some evidence and hope that a unified framework for automated reasoning is not out of reach.

Wed 20 Oct

Displayed time zone: Central Time (US & Canada) change

15:40 - 17:00
OOPSLA 2020 Papers 3SIGPLAN Papers at Zurich G
Chair(s): Anders Miltner The University of Texas at Austin, Texas, USA
15:40
15m
Talk
DynamiTe: Dynamic Termination and Non-termination Proofs
SIGPLAN Papers
Ton Chanh Le Stevens Institute of Technology, Timos Antonopoulos Yale University, Parisa Fathololumi Stevens Institute of Technology, Eric Koskinen Stevens Institute of Technology, ThanhVu Nguyen George Mason University
15:55
15m
Talk
TacTok: Semantics-Aware Proof Synthesis
SIGPLAN Papers
Emily First University of Massachusetts at Amherst, Yuriy Brun University of Massachusetts Amherst, Arjun Guha Northeastern University
Link to publication DOI Pre-print
16:10
15m
Talk
Towards A Unified Proof Framework for Automated Fixpoint Reasoning Using Matching Logic
SIGPLAN Papers
Xiaohong Chen University of Illinois at Urbana-Champaign, Minh-Thai Trinh Advanced Digital Sciences Center, Nishant Rodrigues University of Illinois at Urbana-Champaign, Lucas Peña University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign
16:25
15m
Talk
Verifying and Improving Halide’s Term Rewriting System with Program Synthesis
SIGPLAN Papers
Julie L. Newcomb University of Washington, Andrew Adams Adobe, Steven Johnson Google, Rastislav Bodík University of Washington, Shoaib Kamil Adobe Research
16:40
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers