ICFP 2024
Mon 2 - Sat 7 September 2024 Milan, Italy
Mon 2 Sep 2024 11:00 - 11:30 at Orange 2 - Session 1

The concept of program equivalence in higher-order programming languages addresses the ability to determine when two syntactically different programs are nonetheless equivalent. Contextual equivalence considers two programs as equivalent when they behave identically in any given context, and contexts are modeled as programs written in the same language, making this definition self-contained. In a probabilistic setting, this definition can be made quantitative in a natural way, leading to a notion of contextual distance: the distance between two programs M, N is defined as the supremum of the difference that a context can observe in the behavior of N and M. However, it has been shown by Crubillé and Dal Lago that in a probabilistic language where all programs terminate with probability $1$, this definition of contextual distance actually lead to a trivial pseudo-metric: two programs are either equivalent, or they are as far away as possible of each other. The original proof of this fact by Crubillé and Dal Lago used techniques from real analysis with Bernstein’s theorem as a pivotal tool. In this talk proposal, we present a new proof that highlights the deep connection of this trivialization result with the law of large numbers, a standard result in probability theory.

Mon 2 Sep

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

11:00 - 12:30
Session 1HOPE at Orange 2
11:00
30m
Talk
Amplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers
HOPE
Raphaëlle Crubillé CNRS, Houssein Mansour Aix-Marseille Université
11:30
30m
Talk
An Incremental Approach to the Semantics of Borrowing
HOPE
Brianna Marshall Northeastern University, Andrew Wagner Northeastern University, John Li Northeastern University, Olek Gierczak Northeastern University, Amal Ahmed Northeastern University, USA
12:00
30m
Talk
Towards a linear functional translation for borrowing
HOPE