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