paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A pretty but not greedy printer (functional pearl)

一个漂亮但不贪婪的美化打印器(函数式珠玑)
ICFP 1(ICFP)2017匹配度 1/10 · 论文关注函数式美化打印的规约与线性时间实现,属于函数式编程/程序输出布局方向,与用户的静态分析、Agentic 程序、LLM 交叉、浮点程序分析和贝叶斯程序分析等核心方向无直接关联。引用 6 inbox
Jean-Philippe Bernardy
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:提出要求输出全局最短且可任意对齐子文档的美化打印规约,并给出线性时间的非贪婪函数式实现。

本文对美化打印(pretty printing)提出一种比现有技术更强的规约:要求输出尽可能短,同时允许按需对齐子文档。作者指出,这一规约排除了贪婪式实现,因为局部最优选择无法保证全局最短与对齐约束。尽管如此,论文仍给出一个运行时间与输出规模呈线性的实现,并通过函数式编程方法从规约推导得到。该工作展示了函数式编程方法论如何用于设计非贪婪算法、分析复杂度并论证实现满足更强规范。

问题
如何在要求输出全局最短并支持任意子文档对齐的更强规约下实现美化打印,同时避免贪婪策略的局限。
方法
采用函数式编程方法从规约系统性地推导出非贪婪实现,并分析其复杂度。
评估
通过论证规约排除贪婪实现、展示线性复杂度实现及推导过程来评估,未报告实验基准。
原文摘要(Abstract)

This paper proposes a new specification of pretty printing which is stronger than the state of the art: we require the output to be the shortest possible, and we also offer the ability to align sub-documents at will. We argue that our specification precludes a greedy implementation. Yet, we provide an implementation which behaves linearly in the size of the output. The derivation of the implementation demonstrates functional programming methodology.

链接与引用

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

BibTeX
@article{Bernardy17,
  title = {A pretty but not greedy printer (functional pearl)},
  author = {Jean-Philippe Bernardy},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {1},
  number = {ICFP},
  year = {2017},
  doi = {10.1145/3110250}
}