HMCFA: A Precise and Practical Big-Step Control Flow Analysis for Effect HandlersRemote
Effect handlers enable powerful control flow patterns by capturing and resuming continuations, but no control flow analysis exists for programs using them. Applying existing approaches for other delimited control operators would either lose precision through CPS translation or be computationally intractable. We present the first practical control flow analysis for effect handlers based on big-step semantics. Our key technical contributions are: (1) a novel big-step semantics for effect handlers using environments and stores to avoid unbounded syntactic growth, enabling systematic abstraction via Abstracting Definitional Interpreters [Darais et al. 2017], and (2) a two-component timestamp that tracks both the current call context and the context in which each handler was installed, so that when an operation is dispatched to a handler, its analysis reflects the invocation context that installed it. We prove our concrete semantics equivalent to Bauer and Pretnar’s Bauer and Pretnar 2014 and establish soundness of our abstraction via address freshness. An evaluation on Koka benchmarks shows that our address space has good precision even without context sensitivity, but that our timestamp can close most of the remaining gap in precision while still being tractable on our benchmark suite.
Thu 27 AugDisplayed time zone: Eastern Time (US & Canada) change
15:30 - 17:00 | Effects, Semantics, and Program AnalysisICFP Papers at IP126 Auditorium Chair(s): Ben Greenman University of Utah | ||
15:30 18mTalk | HMCFA: A Precise and Practical Big-Step Control Flow Analysis for Effect HandlersRemote ICFP Papers DOI | ||
15:48 18mTalk | When Types Intersect and Effects Get Handled ICFP Papers Stefano Catozi LIPN, Ugo Dal Lago University of Bologna & INRIA Sophia Antipolis, Taro Sekiyama National Institute of Informatics DOI | ||
16:06 18mTalk | Demand-on-Demand Control-Flow Analysis ICFP Papers DOI | ||
16:24 18mTalk | Adequacy for Predicate Transformer Semantics ICFP Papers Kazuki Watanabe National Institute of Informatics; SOKENDAI, Mirai Ikebuchi Kyoto University, Mayuko Kori Research Institute for Mathematical Sciences, Kyoto University DOI | ||
16:42 18mTalk | Misquoted No More: Securely Extracting F* Programs with IO ICFP Papers Cezar-Constantin Andrici MPI-SP, Abigail Pribisova MPI-SP and MPI-SWS, Danel Ahman University of Tartu, Cătălin Hriţcu MPI-SP, Exequiel Rivas Tallinn University of Technology; Ahrefs, Théo Winterhalter INRIA DOI | ||