Compilation and delayed evaluation in APL
Compilation and delayed evaluation in APL
复制标题
APL 中的编译和延迟评估
DOI：
--
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
Douglas K. Wyatt
中科院分区：
文献类型：
--
作者：
L. Guibas;Douglas K. Wyatt
大多数现有的APL实现本质上是解释性的，也就是说，每次遇到一个APL语句时，它都是由一段完全通用的代码体执行的，也就是说，它能够计算任何APL表达式，而不是针对当前的语句进行定制。这种代价高昂的通用性据说是合理的，因为APL变量是无类型的，因此在程序执行期间可以在类型、形状和大小上任意变化。这个论点忽略了一个事实，即APL语句的操作语义不会因其变量的不同存储需求而改变。关于非完全解释性实现的第一个建议是P. Abrams[1]的论文，其中高级解释器可以通过编译必须稍后调用低级解释器执行的代码来推迟执行某些操作。这样做的好处是，从更广泛的上下文中收集的情报可以用于对子表达的评估。因此，在求（A+B）[I]时，只执行A[I]+B[I]的加法。最近，a . Perlis和他在耶鲁大学的几个学生[9,10]提出了一个可以编写成熟的APL编译器的方案。生成的编译代码可以在专门的硬件处理器上非常有效地执行。在新发布的HP/ 3000apl[12]中使用了类似的方案。本文以上述思想为基础，从几个方面对其进行了拓展。我们首先深入研究所有这些工作的两个共同的关键概念，即APL环境下的编译和延迟求值。延迟计算是指将中间结果的计算推迟到需要它们的时刻。因此，大的中间表达式没有内置在存储器中；相反，它们的元素在时间上是“流”的。延迟评估APL可能是Barton首先提出的（见[8]）。许多APL操作符并不对应于任何实际的数据操作。相反，它们的作用是重命名它们所作用的数组元素。我们将这些操作符称为网格选择器，可以通过将它们向下推到表达式树并将其效果合并到叶子访问器中来处理。从语义上讲，这相当于Abrams描述的拖拽转换。执行此优化将被证明是延迟求值的一个组成部分。为了使我们的注意力集中在上述问题上，我们做了一些简化的假设。我们将注意力集中在单个APL表达式的代码编译上，例如在“APL计算器”中可能出现的情况，其中不允许使用用户定义的函数。当然，我们将非常关注编译后代码的可重用性，以便将来进行评估。我们还忽略了各种APL基元类型之间的区别，并假设所有数组都是统一的数字类型。我们已经研究了没有这些简化假设的情况，但计划在其他地方报道这一点。以下是本文的主要贡献。我们提出了一种将选择符操作符合并到表达式树的叶子的访问器中的算法。该算法的运行时间与树的大小成正比，而不是与其路径长度成正比（[10]和[12]算法就是这种情况）。尽管上述算法不能处理任意形状，但有一种特别重要的情况可以处理：一致性形状的形状。如果ñB是a的后缀，那么重塑AñB就被称为符合。”通过使用一致的形状，我们可以从表达式树中消除内部和外部乘积，并将它们替换为标量算子和沿着最后一个维度的约简。为此，我们在product参数上引入适当的选择器，然后最终将这些选择器吸收到叶子访问器中。同样的机制处理标量扩展，使标量操作符的标量操作数符合任意数组的约定。一旦消除了乘积、标量扩展和选择器，剩下的就是一个完全由标量运算符和最后一个维度的约简组成的表达式树。因此，在执行期间，当前处理的维度遵循严格的类似堆栈的规则。这意味着我们可以生成非常高效的代码，而不依赖于参数的排列。一些APL操作符多次使用其操作数中的元素。纯粹的延迟评估策略需要多次重新评估。”我们引入了一种称为切片的通用缓冲机制，它允许重复保存子表达式的部分，以避免将来的重新计算。切片与需求评价机制很好地结合在一起。例如，当遇到中断流的操作符时，切片用于确定子表达式交付其结果的顺序与完整表达式需要它的顺序之间所需的最小缓冲区大小。编译后的代码非常高效。尽可能少地维护循环变量，并在尽可能多的表达式原子之间共享访问器。最后，生成的代码非常适合由普通的小型计算机（如PDP-11或Data General Nova）执行。我们已经在施乐PARC的Alto计算机上实现了这个编译器。本文的计划是这样的：我们从编译和延迟评估的一般讨论开始。然后，我们通过展示如何处理越来越广泛的原始APL操作符类来激发我们需要引入的结构和算法。我们将讨论为特定表达式定制求值器的各种方法。其中一些裁剪仅可以基于表达式本身，而其他优化则需要了解表达式中原子绑定的（大小）。读者应该时刻注意所使用的知识类型，因为这会影响语句重执行时编译代码的有效性。
Most existing APL implementations are interpretive in nature, that is, each time an APL statement is encountered it is executed by a body of code that is perfectly general, i.e. capable of evaluating any APL expression, and is in no way tailored to the statement on hand. This costly generality is said to be justified because APL variables are typeless and thus can vary arbitrarily in type, shape, and size during the execution of a program. What this argument overlooks is that the operational semantics of an APL statement are not modified by the varying storage requirements of its variables. The first proposal for a non fully interpretive implementation was the thesis of P. Abrams [1], in which a high level interpreter can defer performing certain operations by compiling code which a low level interpreter must later be called upon to execute. The benefit thus gained is that intelligence gathered from a wider context can be brought to bear on the evaluation of a subexpression. Thus on evaluating (A+B)[I], only the addition A[I]+B[I] will be performed. More recently, A. Perlis and several of his students at Yale [9,10] have presented a scheme by which a full-fledged APL compiler can be written. The compiled code generated can then be very efficiently executed on a specialized hardware processor. A similar scheme is used in the newly released HP/3000 APL [12]. This paper builds on and extends the above ideas in several directions. We start by studying in some depth the two key notions all this work has in common, namely compilation and delayed evaluation in the context of APL. By delayed evaluation we mean the strategy of deferring the computation of intermediate results until the moment they are needed. Thus large intermediate expressions are not built in storage; instead their elements are "streamed" in time. Delayed evaluation for APL was probably first proposed by Barton (see [8]). Many APL operators do not correspond to any real data operations. Instead their effect is to rename the elements of the array they act upon. A wide class of such operators, which we will call the grid selectors, can be handled by essentially pushing them down the expression tree and incorporating their effect into the leaf accessors. Semantically this is equivalent to the drag-along transformations described by Abrams. Performing this optimization will be shown to be an integral part of delayed evaluation. In order to focus our attention on the above issues, we make a number of simplifying assumptions. We confine our attention to code compilation for single APL expressions, such as might occur in an "APL Calculator", where user defined functions are not allowed. Of course we will be critically concerned with the re-usability of the compiled code for future evaluations. We also ignore the distinctions among the various APL primitive types and assume that all our arrays are of one uniform numeric type. We have studied the situation without these simplifying assumptions, but plan to report on this elsewhere. The following is a list of the main contributions of this paper. " We present an algorithm for incorporating the selector operators into the accessors for the leaves of the expression tree. The algorithm runs in time proportional to the size of the tree, as opposed to its path length (which is the case for the algorithms of [10] and [12]). Although arbitrary reshapes cannot be handled by the above algorithm, an especially important case can: that of a conforming reshape. The reshape AñB is called conforming if ñB is a suffix of A. " By using conforming reshapes we can eliminate inner and outer products from the expression tree and replace them with scalar operators and reductions along the last dimension. We do this by introducing appropriate selectors on the product arguments, then eventually absorbing these selectors into the leaf accessors. The same mechanism handles scalar extension, the convention of making scalar operands of scalar operators conform to arbitrary arrays. " Once products, scalar extensions, and selectors have been eliminated, what is left is an expression tree consisting entirely of scalar operators and reductions along the last dimension. As a consequence, during execution, the dimension currently being worked on obeys a strict stack-like discipline. This implies that we can generate extremely efficient code that is independent of the ranks of the arguments. Several APL operators use the elements of their operands several times. A pure delayed evaluation strategy would require multiple reevaluations. " We introduce a general buffering mechanism, called slicing, which allows portions of a subexpression that will be repeatedly needed to be saved, to avoid future recomputation. Slicing is well integrated with the evaluation on demand mechanism. For example, when operators that break the streaming are encountered, slicing is used to determine the minimum size buffer required between the order in which a subexpression can deliver its result, and the order in which the full expression needs it. " The compiled code is very efficient. A minimal number of loop variables is maintained and accessors are shared among as many expression atoms as possible. Finally, the code generated is well suited for execution by an ordinary minicomputer, such as a PDP-11, or a Data General Nova. We have implemented this compiler on the Alto computer at Xerox PARC. The plan of the paper is this: We start with a general discussion of compilation and delayed evaluation. Then we motivate the structures and algorithms we need to introduce by showing how to handle a wider and wider class of the primitive APL operators. We discuss various ways of tailoring an evaluator for a particular expression. Some of this tailoring is possible based only on the expression itself, while other optimizations require knowledge of the (sizes of) the atom bindings in the expression. The reader should always be alert to the kind of knowledge being used, for this affects the validity of the compiled code across reexecutions of a statement.