On the Efficient Synthesis of Efficient Programs
On the Efficient Synthesis of Efficient Programs
复制标题
论高效程序的高效合成
DOI：
10.1016/0004-3702(83)90009-7
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
E. Kant
中科院分区：
文献类型：
--
作者：
E. Kant
效率是自动编程中的一个问题，无论是在产生的程序还是在合成过程本身。效率问题的出现是因为许多目标语言程序（在时间和空间性能上各不相同）通常满足一个抽象规范。本文提出了一个框架，使用分析和搜索知识，以指导程序综合的逐步细化范例。一个特定的实现框架，calledlibra，描述。给定一个程序规范，包括大小和频率注释，要最小化的性能度量，以及对合成资源的一些限制，库选择算法和数据表示，并决定是否使用“优化”转换。通过应用增量，代数程序分析，明确的规则，合理的实现，并根据决策的重要性分配资源，librahas引导自动执行的一些程序在域中的符号处理。
Efficiency is a problem in automatic programming—both in the programs produced and in the synthesis process itself. The efficiency problem arises because many target-language programs (which vary in their time and space performance) typically satisfy one abstract specification. This paper presents a framework for using analysis and searching knowledge to guide program synthesis in a stepwise refinement paradigm. A particular implementation of the framework, calledlibra, is described. Given a program specification that includes size and frequency notes, the performance measure to be minimized, and some limits on synthesis resources,libraselects algorithms and data representations and decides whether to use ‘optimizing’ transformations. By applying incremental, algebraic program analysis, explicit rules about plausible implementations, and resource allocation on the basis of decision importance,librahas guided the automatic implementation of a number of programs in the domain of symbolic processing.