Wed 26 Aug 2026 11:06 - 11:24 at IP126 Auditorium - Languages and DSLs Chair(s): Benjamin Delaware

Verifying the functional correctness of real-world code with complex algorithms can be decomposed into two layers: verifying that the concrete code refines an abstract algorithmic description, and proving the correctness of the formal description. However, in practice the two layers do not stay cleanly separated. For example, in the verification of the Knuth-Morris-Pratt (KMP) algorithm, the implementation correctness proof often re-establishes algorithm properties that have already been proved, as the concrete implementation relies on invariants that the traditional two-layer method provides no mechanism to transfer. This makes it difficult to clearly separate the concerns of algorithm correctness and implementation correctness. In this pearl, we show how a clean separation can be achieved within the two-layer method by combining two simple ideas: expressing implementation correctness as a relational Hoare quadruple, and introducing assertion annotations into the abstract program to capture key invariants. Properties established in the algorithm proof are thereby transferred directly to the implementation proof, eliminating the need to re-prove them. We demonstrate the effectiveness of this approach through non-trivial case studies, including the Knuth-Morris-Pratt pattern-matching algorithm and the depth-first search algorithm, showing that it leads to simpler proofs and a more modular verification process.

Wed 26 Aug

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

10:30 - 12:00
Languages and DSLsICFP Papers at IP126 Auditorium
Chair(s): Benjamin Delaware Purdue University
10:30
18m
Talk
QuickChecking Convergence of Rewriting Systems (Functional Pearl)Remote
ICFP Papers
Koen Claessen Chalmers University of Technology
DOI
10:48
18m
Talk
Safety First: How to Safely Disregard Unsafe Behaviour in Compiler CalculationsRemote
ICFP Papers
Patrick Bahr IT University of Copenhagen
DOI Pre-print
11:06
18m
Talk
Assertions for Free: Transferring Invariants from Algorithm to Implementation Proofs (Functional Pearl)
ICFP Papers
Shushu Wu Shanghai Jiao Tong University, Chengxi Yang Shanghai Jiao Tong University, Xiwei Wu Shanghai Jiao Tong University, Qinxiang Cao Shanghai Jiao Tong University
DOI
11:24
18m
Talk
Package Managers à la Carte
ICFP Papers
Ryan Gibb University of Cambridge, Patrick Ferris University of Cambridge, UK, David Allsopp Jane Street, Thomas Gazagnaire Tarides, Anil Madhavapeddy University of Cambridge, UK
DOI
11:42
18m
Talk
Compositional Generator Equivalence
ICFP Papers
Anthony Vandikas University of Toronto, Kiarash Sotoudeh University of Toronto, Marsha Chechik University of Toronto
DOI