paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Parametric polymorphism and operational improvement

参数多态与操作式改进
ICFP 2(ICFP)2018匹配度 3/10 · 该论文属于程序语言理论中的形式语义与程序优化证明,讨论参数性、时间开销与程序融合的正确性/改进,虽与形式化验证有边缘关联,但完全不涉及用户核心关注的 AI/LLM、Agentic 程序、静态分析、浮点或贝叶斯程序分析。引用 3 inbox
Jennifer Hackett, Graham Hutton
crossref: 2026-09-10

AI 速览

一句话:提出对时间开销敏感的操作式参数性理论,用于证明程序融合是时间改进。

参数性长期用于推理程序正确性,但现有理论对资源使用不敏感,无法刻画“一个程序比另一个使用更少资源”的程序改进。本文提出一种新的操作式参数性理论,将时间开销纳入语义,从而能够推理时间改进性质。作者通过证明若干著名程序融合技术——包括不动点融合、map 融合和 shortcut 融合——都是时间改进,展示了该理论的适用性。该工作为函数式程序的优化与资源敏感推理提供了语义基础。

问题
现有参数性理论不关心资源使用,无法用于推理程序改进(即一个程序比另一个使用更少资源)。
方法
提出一种对时间开销敏感的操作式参数性理论,建立可推理时间改进性质的语义框架。
评估
通过证明不动点融合、map 融合和 short cut 融合等著名融合技术都是时间改进,展示理论适用性。
原文摘要(Abstract)

Parametricity, in both operational and denotational forms, has long been a useful tool for reasoning about program correctness. However, there is as yet no comparable technique for reasoning about program improvement , that is, when one program uses fewer resources than another. Existing theories of parametricity cannot be used to address this problem as they are agnostic with regard to resource usage. This article addresses this problem by presenting a new operational theory of parametricity that is sensitive to time costs, which can be used to reason about time improvement properties. We demonstrate the applicability of our theory by showing how it can be used to prove that a number of well-known program fusion techniques are time improvements, including fixed point fusion, map fusion and short cut fusion.

链接与引用

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

BibTeX
@article{paperbot267,
  title = {Parametric polymorphism and operational improvement},
  author = {Jennifer Hackett and Graham Hutton},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {2},
  number = {ICFP},
  year = {2018},
  doi = {10.1145/3236763}
}