ICFP 2024
Mon 2 - Sat 7 September 2024 Milan, Italy
Thu 5 Sep 2024 11:24 - 11:42 at Green 1-2-3 - Refinement Types, Type Inference Chair(s): Dominic Orchard

Verification of higher-order probabilistic programs is a challenging problem. We present a verification method that supports several quantitative properties of higher-order probabilistic programs. Usually, extending verification methods to handle the quantitative aspects of probabilistic programs often entails extensive modifications to existing tools, reducing compatibility with advanced techniques developed for qualitative verification. In contrast, our approach necessitates only small amounts of modification, facilitating the reuse of existing techniques and implementations. On the theoretical side, we propose a dependent refinement type system for a generalised higher-order fixed point logic (HFL). Combined with continuation-passing style encodings of properties into HFL, our dependent refinement type system enables reasoning about several quantitative properties, including weakest pre-expectations, expected costs, moments of cost, and conditional weakest pre-expectations for higher-order probabilistic programs with continuous distributions and conditioning. The soundness of our approach is proved in a general setting using a framework of categorical semantics so that we don't have to repeat similar proofs for each individual problem. On the empirical side, we implement a type checker for our dependent refinement type system that reduces the problem of type checking to constraint solving. We introduce \emph{admissible predicate variables} and \emph{integrable predicate variables} to constrained Horn clauses (CHC) so that we can soundly reason about the least fixed points and samplings from probability distributions. Our implementation demonstrates that existing CHC solvers developed for non-probabilistic programs can be extended to a solver for the extended CHC with only small efforts. We also demonstrate the ability of our type checker to verify various concrete examples.

slides (slides.pdf)267KiB

Thu 5 Sep

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

10:30 - 12:00
Refinement Types, Type InferenceICFP Papers and Events / JFP First Papers at Green 1-2-3
Chair(s): Dominic Orchard University of Kent; University of Cambridge
10:30
18m
Talk
The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data StructuresDistinguished Paper
ICFP Papers and Events
Yijia Chen Hong Kong University of Science and Technology, Lionel Parreaux HKUST (The Hong Kong University of Science and Technology)
DOI
10:48
18m
Talk
Contextual Typing
ICFP Papers and Events
Xu Xue University of Hong Kong, Bruno C. d. S. Oliveira University of Hong Kong
DOI
11:06
18m
Talk
Synchronous Programming with Refinement Types
ICFP Papers and Events
Jiawei Chen University of Michigan at Ann Arbor, José Luiz Vargas de Mendonça University of Michigan at Ann Arbor, Bereket Shimels Ayele Addis Ababa Institute of Technology, Bereket Ngussie Bekele Addis Ababa Institute of Technology, Shayan Jalili University of Michigan at Ann Arbor, Pranjal Sharma University of Michigan at Ann Arbor, Nicholas Wohlfeil University of Michigan at Ann Arbor, Yicheng Zhang University of Michigan at Ann Arbor, Jean-Baptiste Jeannin University of Michigan at Ann Arbor
DOI
11:24
18m
Talk
Automated Verification of Higher-Order Probabilistic Programs via a Dependent Refinement Type System
ICFP Papers and Events
Satoshi Kura Waseda University, Hiroshi Unno Tohoku University
DOI File Attached
11:42
18m
Talk
Trace contractsJFP First Paper
JFP First Papers
Cameron Moy Northeastern University, Matthias Felleisen Northeastern University
DOI