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

At the heart of efficient program analysis implementations are incremental solutions to fixpoint problems. These solutions can be interpreted as the derivative of the underlying analysis function. Methods that describe how to systematically derive higher-order analyses from program semantics, such as Abstracting Abstract Machines, \emph{don’t} shed light on how to efficiently \emph{implement} those analyses. In this paper, we explore complementary techniques to optimize the derivative computation towards deriving efficient implementations. In particular we use static specializations (by partial evaluation and rewriting) and dynamic specializations (in the form of tracking dependencies during the fixpoint), yielding efficient incremental fixpoints. We present how these optimizations apply to an example analysis of continuation-passing-style lambda calculus, and describe how they pair particulary well with tunable and optimized workset-based fixpoint methods. We demonstrate the efficacy of this approach on a flow analysis for the Standard ML language, yielding an average speed-up of 56x over an existing fixpoint method for higher-order analyses from the literature.

Wed 4 Sep

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

10:30 - 12:00
Meta-Programming, Staging, Generic Programming, Partial EvaluationICFP Papers and Events / JFP First Papers at Green 1-2-3
Chair(s): Richard A. Eisenberg Jane Street
10:30
18m
Talk
Staged Compilation with Module Functors
ICFP Papers and Events
Tsung-Ju Chiang University of Toronto, Jeremy Yallop University of Cambridge, Leo White Jane Street, Ningning Xie University of Toronto; Google DeepMind
DOI Pre-print
10:48
18m
Talk
A Safe Low-Level Language for Computer Algebra and Its Formally Verified Compiler
ICFP Papers and Events
Guillaume Melquiond Université Paris-Saclay - CNRS - ENS Paris-Saclay - Inria, Josué Moreau Université Paris-Saclay - CNRS - ENS Paris-Saclay - Inria
DOI
11:06
18m
Talk
Deriving with Derivatives: Optimizing Incremental Fixpoints for Higher-Order Flow Analysis
ICFP Papers and Events
Benjamin Quiring University of Maryland at College Park, David Van Horn University of Maryland
DOI
11:24
18m
Talk
Compiled, Extensible, Multi-language DSLs (Functional Pearl)Functional Pearl
ICFP Papers and Events
Michael Ballantyne Northeastern University, Mitch Gamburg Unaffiliated, Jason Hemann Seton Hall University
DOI Pre-print
11:42
18m
Talk
Knuth–Morris–Pratt illustrated (JFP Functional Pearls )JFP First Paper
JFP First Papers
Cameron Moy Northeastern University
DOI