ICFP 2025
Sun 12 - Sat 18 October 2025 Singapore
co-located with ICFP/SPLASH 2025

This program is tentative and subject to change.

Mon 13 Oct 2025 16:25 - 16:50 at Orchid West - Semantics

One can perform equational reasoning about computational effects with a purely functional programming language thanks to monads. Even though equational reasoning for effectful programs is desirable, it is not yet mainstream. This is partly because it is difficult to maintain pencil-and-paper proofs of large examples. We propose a formalization of a hierarchy of effects using monads in the Coq proof assistant that makes monadic equational reasoning practical. Our main idea is to formalize the hierarchy of effects and algebraic laws as interfaces like it is done when formalizing hierarchy of algebras in dependent-type theory. Thanks to this approach, we clearly separate equational laws from models. We can then take advantage of the sophisticated rewriting capabilities of Coq and build libraries of lemmas to achieve concise proofs of programs. We can also use the resulting framework to leverage on Coq’s mathematical theories and formalize models of monads. In this article, we explain how we formalize a rich hierarchy of effects (nondeterminism, state, probability, etc.), how we mechanize examples of monadic equational reasoning from the literature, and how we apply our framework to the design of equational laws for a subset of ML with references.

This program is tentative and subject to change.

Mon 13 Oct

Displayed time zone: Perth change

16:00 - 17:40
16:00
25m
Paper
A contextual formalization of structural coinduction
JFP First Papers
Paul Downen University of Massachusetts at Lowell, Zena M. Ariola University of Oregon
DOI
16:25
25m
Paper
A practical formalization of monadic equational reasoning in dependent-type theory
JFP First Papers
Reynald Affeldt National Institute of Advanced Industrial Science and Technology (AIST), Japan, Jacques Garrigue , Takafumi Saikawa Nagoya University
DOI
16:50
25m
Talk
Almost Fair Simulations
ICFP Papers
Arthur Correnson CISPA Helmholtz Center for Information Security, Iona Kuhn Saarland University, Bernd Finkbeiner CISPA Helmholtz Center for Information Security
DOI
17:15
25m
Talk
Big Steps in Higher-Order Mathematical Operational Semantics
ICFP Papers
Sergey Goncharov University of Birmingham, Pouya Partow Birmingham University, Stelios Tsampas University of Southern Denmark
DOI