A Complementary Approach to Incorrectness Typing
Celia Mengyue Li, Sophie Pull, Steven Ramsay
Abstract
We introduce a new two-sided type system for verifying the correctness and incorrectness of functional programs with atoms and pattern matching. A key idea in the work is that types should range over sets of normal forms, rather than sets of values, and this allows us to define a complement operator on types that acts as a negation on typing formulas. We show that the complement allows us to derive a wide range of refutation principles within the system, including the type-theoretic analogue of co-implication, and we use them to certify that a number of Erlang-like programs go wrong. An expressive axiomatisation of the complement operator via subtyping is shown decidable, and the type system as a whole is shown to be not only sound, but also complete for normal forms.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Concurrent incorrectness separation logic cites Incorrectness logic
- Trace-Guided Synthesis of Effectful Test Generators cites Incorrectness logic
- Trace-Guided Synthesis of Effectful Test Generators cites Finding real bugs in big programs with incorrectness logic
- Trace-Guided Synthesis of Effectful Test Generators cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
- Finding real bugs in big programs with incorrectness logic cites Concurrent incorrectness separation logic
- Finding real bugs in big programs with incorrectness logic cites Incorrectness logic
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Concurrent incorrectness separation logic
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Incorrectness logic
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Finding real bugs in big programs with incorrectness logic
Cited by top-tier papers1
Builds on12
- Incorrectness logicPeter W. O'HearnPOPL 2020 · 122 citations
- Finding real bugs in big programs with incorrectness logicQuang Loc Le, Azalea Raad, Jules Villard, Josh Berdine et al.OOPSLA 2022 · 52 citations
- Outcome Logic: A Unifying Foundation for Correctness and Incorrectness ReasoningNoam Zilberstein, Derek Dreyer, Alexandra SilvaOOPSLA 2023 · 39 citations
- MLstruct: principal type inference in a Boolean algebra of structural typesLionel Parreaux, Chun Yin ChauOOPSLA 2022 · 31 citations
- Concurrent incorrectness separation logicAzalea Raad, Josh Berdine, Derek Dreyer, Peter W. O'HearnPOPL 2022 · 24 citations
Related papers
- Ill-Typed Programs Don't EvaluateSteven Ramsay, Charlie WalpolePOPL 2024 · 3 citations
- Semantic-Type-Guided Bug FindingKelvin Qian, Scott F. Smith, Brandon Stride, Shiwei Weng et al.OOPSLA 2024 · 2 citations
- Intensional datatype refinement: with application to scalable verification of pattern-match safetyEddie Jones, Steven J. RamsayPOPL 2021 · 3 citations
- Type-level programming with match typesOlivier Blanvillain, Jonathan Immanuel Brachthäuser, Maxime Kjaer, Martin OderskyPOPL 2022 · 10 citations
- Imperative Compositional Programming: Type Sound Distributive Intersection Subtyping with References via Bidirectional TypingWenjia Ye, Yaozhu Sun, Bruno C. d. S. OliveiraOOPSLA 2024 · 1 citation
