paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Program adverbs and Tlön embeddings

程序副词与 Tlön 嵌入
ICFP 6(ICFP)2022匹配度 2/10 · 该论文属于纯 PL 理论基础工作,研究带效应语言的形式语义与自由单子的替代结构(program adverbs、Tlön embeddings),既未涉及 LLM/Agent,也未涉及静态分析、浮点程序分析或贝叶斯程序分析,与用户的核心研究问题仅有极远的 PL 领域背景关联。引用 6 inbox
Yao Li, Stephanie Weirich
crossref: 2026-09-10

AI 速览

一句话:提出程序副词及 Tlön 嵌入,为带效应语言提供比自由单子更灵活且保留更多语法结构的形式语义。

自由单子及其变体已成为在证明助手中表示带效应程序语义的通用工具,但它们并非组织效应计算的唯一方式。受 applicative functor、selective functor 等结构启发,本文定义了一组称为“程序副词”(program adverbs)的数据结构与理论,用以刻画多种计算模式;这些程序副词自身可组合,因而能描述具有多种计算模式的语言语义。作者进一步以程序副词为基础提出一类新的语义嵌入,称为 Tlön 嵌入。与基于自由单子的嵌入相比,Tlön 嵌入在效应计算建模上更灵活,同时保留更多关于程序语法结构的信息。

问题
自由单子虽然流行,但不足以统一刻画多种效应计算模式,并且会丢失程序语法结构信息。
方法
受 applicative functor 和 selective functor 等结构启发,定义可组合的程序副词数据结构与理论,并构造 Tlön 嵌入作为语义嵌入。
评估
通过与基于自由单子的嵌入进行概念比较,说明 Tlön 嵌入在效应建模灵活性和语法结构保留方面的优势。
原文摘要(Abstract)

Free monads (and their variants) have become a popular general-purpose tool for representing the semantics of effectful programs in proof assistants. These data structures support the compositional definition of semantics parameterized by uninterpreted events, while admitting a rich equational theory of equivalence. But monads are not the only way to structure effectful computation, why should we limit ourselves? In this paper, inspired by applicative functors, selective functors, and other structures, we define a collection of data structures and theories, which we call program adverbs, that capture a variety of computational patterns. Program adverbs are themselves composable, allowing them to be used to specify the semantics of languages with multiple computation patterns. We use program adverbs as the basis for a new class of semantic embeddings called Tlön embeddings. Compared with embeddings based on free monads, Tlön embeddings allow more flexibility in computational modeling of effects, while retaining more information about the program's syntactic structure.

链接与引用

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

BibTeX
@article{paperbot1478,
  title = {Program adverbs and Tlön embeddings},
  author = {Yao Li and Stephanie Weirich},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {ICFP},
  year = {2022},
  doi = {10.1145/3547632}
}