paperbot · PL 论文追踪

全部论文 待读 收藏

P2 HMCFA: A Precise and Practical Big-Step Control Flow Analysis for Effect Handlers

HMCFA:面向效应处理器的一种精确且实用的大步骤控制流分析
ICFP 10(ICFP)2026匹配度 3/10 · 论文是效应处理器的大步骤控制流分析与抽象解释,属于程序分析和形式语义,与用户画像中“静态分析”的方法论有边缘交集;但它不涉及 LLM/Agentic 程序、AI 与 PL 交叉、浮点程序分析或贝叶斯程序分析,因此与核心研究方向匹配度低。引用 0 inbox
Tim Whiting, Kimball Germane
crossref: 2026-09-10

AI 速览

一句话:提出首个实用的效应处理器大步骤控制流分析 HMCFA,用显式存储与双分量时间戳兼顾精度与可处理性。

效应处理器可通过捕获与恢复续延实现强大控制流,但此前缺乏其控制流分析;沿用其他定界控制算子方法会因 CPS 变换损失精度或计算不可行。本文提出 HMCFA:基于大步骤语义的首个实用控制流分析。它定义大步骤语义,将 denotables 与续延分配到显式 store,避免语法无界增长,并按 ADI 风格抽象;证明该语义与 Bauer-Pretnar 的替换式大步骤语义等价,且通过地址新鲜性证明抽象可靠。分析引入双分量时间戳,跟踪当前调用上下文与处理器安装上下文,使操作分派反映安装它的调用上下文。Koka 基准评估显示地址空间已有较好精度,时间戳能弥补大部分精度差距且保持可处理。

问题
效应处理器支持强大的控制流,但此前没有针对它的控制流分析;直接套用其他定界控制算子分析会因 CPS 变换损失精度或计算不可行。
方法
提出基于大步骤语义的 HMCFA,通过显式 store 分配 denotables 与续延并按 ADI 风格抽象;引入双分量时间戳区分当前调用上下文与处理器安装上下文。证明具体语义与 Bauer-Pretnar 替换式大步骤语义等价,并以地址新鲜性证明抽象可靠。
评估
在 Koka 基准上评估,显示地址空间即使不上下文敏感也具较好精度,时间戳能弥补大部分精度差距且保持可处理。
原文摘要(Abstract)

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 HMCFA, the first practical control flow analysis for effect handlers based on big-step semantics. Our key technical contributions are: (1) a big-step semantics for effect handlers that allocates denotables and continuations in an explicit store to avoid unbounded syntactic growth, enabling systematic abstraction in the style of Abstracting Definitional Interpreters (ADI); we prove this semantics equivalent to Bauer and Pretnar's substitution-based big-step semantics. (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 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. 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.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@article{WhitingG26,
  title = {HMCFA: A Precise and Practical Big-Step Control Flow Analysis for Effect Handlers},
  author = {Tim Whiting and Kimball Germane},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {ICFP},
  year = {2026},
  doi = {10.1145/3828703}
}