ICFP 2024
Mon 2 - Sat 7 September 2024 Milan, Italy

This program is tentative and subject to change.

Wed 4 Sep 2024 15:30 - 15:48 - Verification and Cost Analysis

Lazy evaluation is a powerful tool that enables better compositionality and potentially better performance in functional programming, but it is challenging to analyze its computation cost. Existing works either require manually annotating sharing, or rely on separation logic to reason about heaps of mutable cells. In this paper, we propose a bidirectional demand semantics that allows for extrinsic reasoning about the computation cost of lazy programs without relying on special program logics. To show the effectiveness of our approach, we apply the demand semantics to a variety of case studies including insertion sort, selection sort, Okasaki’s banker’s queue, and the implicit queue. We formally prove that the banker’s queue and the implicit queue are both amortized and persistent using the Rocq Prover (formerly known as Coq). We also propose the reverse physicist’s method, a novel variant of the classical physicist’s method, which enables mechanized, modular and compositional reasoning about amortization and persistence with the demand semantics.

This program is tentative and subject to change.

Wed 4 Sep

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

15:30 - 16:42
Verification and Cost AnalysisJFP First Papers / ICFP Papers and Events
15:30
18m
Talk
Story of Your Lazy Function’s Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy Programs
ICFP Papers and Events
Li-yao Xia , Laura Israel Portland State University, Maite Kramarz University of Toronto, Nicholas Coltharp Portland State University, Koen Claessen Chalmers University of Technology and Epic Games, Stephanie Weirich University of Pennsylvania, Yao Li Portland State University
DOI Pre-print
15:48
18m
Talk
Level-p-complexity of Boolean functions using thinning, memoization, and polynomialsJFP First Paper
JFP First Papers
Julia Jansson , Patrik Jansson Chalmers University of Technology and University of Gothenbrug
DOI
16:06
18m
Talk
CCLemma: E-Graph Guided Lemma Discovery for Inductive Equational Proofs
ICFP Papers and Events
Cole Kurashige UCSD, Ruyi Ji Peking University, Aditya Giridharan UCSD, Mark Barbone UCSD, Daniel Noor Technion, Shachar Itzhaky Technion, Ranjit Jhala University of California, San Diego, Nadia Polikarpova University of California at San Diego
16:24
18m
Talk
Contract Lenses: Reasoning about Bidirectional Programs via CalculationJFP First Paper
JFP First Papers
Hanliang Zhang University of Bristol, UK, Wenhao Tang University of Edinburgh, Ruifeng Xie Peking University, Meng Wang University of Bristol, Zhenjiang Hu Peking University
DOI