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