Complete First-Order Reasoning for Properties of Functional Programs
Several practical tools for automatically verifying functional programs (e.g., Liquid Haskell and Leon for Scala programs) rely on a heuristic based on unrolling recursive function definitions followed by quantifier-free reasoning using SMT solvers. We uncover foundational theoretical properties of this heuristic, revealing that it can be generalized and formalized as a technique that is in fact <i>complete</i> for reasoning with combined First-Order theories of algebraic datatypes and background theories, where background theories support decidable quantifier-free reasoning. The theory developed in this paper explains the efficacy of these heuristics when they succeed, explain why they fail when they fail, and the precise role that user help plays in making proofs succeed.
Fri 27 OctDisplayed time zone: Lisbon change
14:00 - 15:30 | |||
14:00 18mTalk | Stuttering for Free OOPSLA Minki Cho Seoul National University, Youngju Song MPI-SWS, Dongjae Lee Seoul National University, Lennard Gäher MPI-SWS, Derek Dreyer MPI-SWS DOI | ||
14:18 18mTalk | Generating Proof Certificates for a Language-Agnostic Deductive Program Verifier OOPSLA Zhengyao Lin Carnegie Mellon University, Xiaohong Chen University of Illinois at Urbana-Champaign, Minh-Thai Trinh Advanced Digital Sciences Center, John Wang University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign DOI | ||
14:36 18mTalk | Complete First-Order Reasoning for Properties of Functional Programs OOPSLA Adithya Murali University of Illinois at Urbana-Champaign, Lucas Peña University of Illinois at Urbana-Champaign, Ranjit Jhala University of California at San Diego, P. Madhusudan University of Illinois at Urbana-Champaign DOI | ||
14:54 18mTalk | Counterexample Driven Quantifier Instantiations with Applications to Distributed Protocols OOPSLA Orr Tamir Tel Aviv University, Marcelo Taube Tel Aviv University, Kenneth L. McMillan University of Texas at Austin, Sharon Shoham Tel Aviv University, Jon Howell VMware Research, Guy Gueta VMware Research, Mooly Sagiv Tel Aviv University DOI | ||
15:12 18mTalk | A conceptual framework for safe object initialization: a principled and mechanized soundness proof of the Celsius model OOPSLA Link to publication DOI |