paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Hyperfunctions: Communicating Continuations

超函数(Hyperfunctions):通信延续
POPL 10(POPL)2026匹配度 1/10 · 该论文研究函数式编程中的 hyperfunction、继续与并发形式语义,并给出 CCS 的全抽象语义与 Haskell 协程库,属于纯 PL/形式语义方向;与用户核心关注的 LLM/Agent 与静态分析、浮点程序分析、贝叶斯程序分析等交叉方向基本无关。引用 1 inbox
Donnacha Oisín Kidney, Nicolas Wu
crossref: 2026-09-10

AI 速览

一句话:识别多种算法中隐藏的 hyperfunction 共同模式,建立统一框架,并用于 CCS 全抽象语义与 Haskell 协程库。

Hyperfunction 是一种类似延续的结构,可用于在并发语境下实现通信,但长期被反复发明却仍显晦涩:它曾出现在代数效应处理器、协程和广度优先遍历等实现中而未被识别。本文指出这些算法背后隐藏的 hyperfunction 类型,提炼其共同模式,并构建一套用于操作与推理 hyperfunction 的框架。借助该框架,作者解决了一个长期问题:为并发演算 CCS(Calculus of Communicating Systems)给出基于延续的全抽象语义;最后还用 hyperfunction 实现了一个 Haskell 单子库,支持高效的一等协程。

问题
Hyperfunction 虽能用于并发通信且反复出现在效应处理器、协程与遍历中,但一直未被明确识别,也缺乏统一的理解与推理框架;并发演算 CCS 也缺少基于延续的全抽象语义。
方法
作者从若干已知算法中识别出隐藏的 hyperfunction,提炼其共同模式,并建立用于操作与推理 hyperfunction 的框架。
评估
作者用该框架为 CCS 构造基于延续的全抽象语义,并实现 Haskell 单子库以支持高效的一等协程。
原文摘要(Abstract)

A hyperfunction is a continuation-like construction that can be used to implement communication in the context of concurrency. Though it has been reinvented many times, it remains obscure: since its definition by Launchbury et al. , hyperfunctions have been used to implement certain algebraic effect handlers, coroutines, and breadth-first traversals; however, in each of these examples, the hyperfunction type went unrecognised. We identify the hyperfunctions hidden in all of these algorithms, and we exposit the common pattern between them, building a framework for working with and reasoning about hyperfunctions. We use this framework to solve a long-standing problem: giving a fully-abstract continuation-based semantics for a concurrent calculus, the Calculus of Communicating Systems. Finally, we use hyperfunctions to build a monadic Haskell library for efficient first-class coroutines.

链接与引用

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

BibTeX
@article{KidneyW26,
  title = {Hyperfunctions: Communicating Continuations},
  author = {Donnacha Oisín Kidney and Nicolas Wu},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {POPL},
  year = {2026},
  doi = {10.1145/3776649}
}