Richard S. Bird. Addendum to "The promotion and accumulation strategies in transformational programming". ACM Transactions on Programming Languages and Systems, 7(3):490--492, July 1985.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....One of the most important techniques used to improve program performance involves incrementally updating results of computations as their parameters change rather than computing the results from scratch. This problem has received much attention in the transformational programming literature [7, 12, 35, 37, 45], where it is commonly known as finite differencing. However, general techniques of incremental computation have far broader application throughout software, e.g. loop optimizations in optimizing compilers [2, 3, 11, 14, 46] interactive systems like editors [6, 13, 43] and programming ....

....thus i 1 by i Gamma 1) b[i; j] b[i Gamma 1; j] Gamma c[i Gamma 1; j] c[i m; j] 12) In summary, only four Sigma operations are needed for each pixel, no matter how large m is. Thus the whole program takes only O(n ) time. 11 6. 3 Path Sequence Problem This example is taken from [7]. Given a directed acyclic graph, and a string whose elements are vertices in the graph, the problem is to compute the length of the longest subsequence in the string that forms a path in the graph. We focus on the second half where an exponential time recursive solution is improved (incorrectly ....

[Article contains additional citation context not shown here]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, October 1984.

....general and systematic. Second, it stores only values that are necessary for the optimization; it also shows exactly when and where subproblems not in the original computation have to be included. Our method is based on a number of static analyses and transformations studied previously by others [6, 9, 21, 42, 47, 55, 56, 62] and ourselves [30, 37, 38, 39] and improves them. Each of the caching, incrementalization, and pruning steps is simple, automatable, and ecient and has been implemented in a prototype system, CACHET. The system has been used in optimizing many programs written as straightforward recursions, ....

.... arg aux info original program s running time optimized prog s running time Fibonacci function [45] O(2 ) O(n) binomial coecients [45] O(2 ) O(n k) longest common subsequence [15] matrix chain multiplication [15] string editing distance [52] O(3 dag path sequence [6] optimal polygon triangulation [15] optimal binary search tree [2] paragraph formatting [15] paragraph formatting 2 ) O(n width) 0 1 knapsack [15] a O(2 ) O(n weight) context free grammar parsing [2] p p a O(n (2 size 1) size) Figure 3: ....

[Article contains additional citation context not shown here]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

....(4, 10) 5, 15) 6, 21) With the same trick, we can eliminate the other four. Consequently, the aggregate predicates can be expressed in the form of f (head) g (last) It should be noted that this preprocessing does not raise additional cost by using accumulation and fusion techniques [Bir84, Chi92]. Normalization of Composite Property Next, let us turn our attention to the composite property. With respect to it, we have the following Lemma holds. Lemma 2 (Normalization) Any composite predicate can be expressed in its canonical form, that is, the disjunction of a number of conjunction of ....

R. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

....program, the programmer is faced with a tension between correctness and efficiency. A program that is easy to understand and whose correctness is obvious to see often fails to be efficient, while a more efficient program often compromises clarity. Transformational programming [BD77, Fea87, Dar81, Bir84, Bir86, Bir87, Bac95] is a well known methodology to address this difficulty. In transformational programming, one does not attempt to produce directly a program that is correct, understandable and efficient, rather one initially concentrates on producing a program which is as clear and ....

....ignoring any question of efficiency. Having satisfied himself that he has a correct program he successively transforms it to more and more efficient versions using methods guaranteed to preserve the meaning of the program. Although quite a lot of creative, elegant and efficient algorithms [Bir84, Bir86, PP96] have been derived in this manner showing the impetus of the transformational approach to programming, there remain two major problems. 1 September 1999, METR 99 06 ffl Insightful rules for big step jumps can be difficult to find. While creative algorithms are interesting to ....

[Article contains additional citation context not shown here]

R. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

....with a list elimination approach by shortcut deforestation for polymorphically recursive workers in Section 7.1. Example 3. Consider the following specification of a function inits that returns the list of initial segments of its argument list e.g. inits [1. 4] 1] 1, 2] 1, 2,3] [1, 2,3,4]] inits : inits [ inits (x : xs) map (x : inits xs) By abstracting from the list constructors of the outer result list including map and using Theorem 3, inits can be replaced by: l = vanish ,rev,map (ln c a r m let f [ c n f (x : ....

....eliminate such substitution functions from top down tree transducer modules by introducing accumulating parameters. Their integration step could also be realized in the framework of our methodology, thus generalizing their accumulation technique to arbitrary functions that produce trees. Bird [4], Hu et al. 11] use calculational methods to derive accumulative programs in their setting higher order folds over algebraic data types from first order folds, such as transforming rev from the previous subsection into rev (which none of the other accumulation methods discussed here ....

R. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. on Prog. Lang. and Systems, 6:487--504, 1984.

....of the resulting algorithm. Equally or more important are the assurance of correctness for the algorithm and implementation developed and the ability to develop them easily and quickly. Much previous research has answered these questions positively for subclasses of problems, e.g. [4, 7, 8, 9, 10, 11, 13, 14, 16, 19, 30, 31, 34, 37]. This paper describes a method that uni es and generalizes existing classes of problems that can be solved systematically. Important and interesting questions in detail are: How are appropriate data structures determined In case multiple choices exist, how can they be compared Two fundamental ....

.... Examples original program s running time optimized prog s running time Fibonacci function [29] O(2 ) O(n) binomial coecients [29] O(2 ) O(n k) longest common subsequence [12] O(2 matrix chain multiplication [12] O(n 3 string editing distance [33] O(3 dag path sequence [8] O(2 optimal polygon triangulation [12] O(n 3 optimal binary search tree [1] O(n 3 paragraph formatting [12] O(n 2 paragraph formatting 2 [19] O(n 2 ) O(n width) 0 1 knapsack [12] O(2 ) O(n weight) context free grammar parsing [1] O(n (2 size 1) ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

....x i changed to a pair (x i , s i ) and reduce aggregate sum property to a transitive total order relation between the leftmost and rightmost elements of the concerned segment. It is worth noting that this preprocessing does not raise additional cost by using accumulation and fusion technique [Bir84]. With the same trick, the other four aggregate predicates can also be normalized into the primitive form. Accordingly, we further have the following selfevident lemma hold for the composite property. Lemma 2 (Disjunctive Normal Form) Any composite predicate can be expressed in its canonical ....

R. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

....performance degradation, especially with the increasingly large data sets that many applications are facing, yet methods for eliminating overlapping aggregate array redundancy have been lacking. Optimizations similar to incrementalization have been studied for various language features, e.g. [8, 16, 34, 52, 51, 53, 57, 58, 59, 71, 79], but no systematic technique handles aggregate computations on arrays. At the same time, many optimizations have been studied for arrays, e.g. 1, 2, 3, 4, 6, 22, 29, 31, 37, 41, 55, 56, 63, 69, 74] but none of them achieves incrementalization. This paper presents a method and algorithms for ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

.... = f apply law (3) map(f,map(g,xs) map(f g,xs) g tails( x] atten(map(tails (x: inits(xs) After several steps, we are still unable to fold as we encountered a slightly enlarged expression of the form atten(map(tails (x: inits(xs) As reported elsewhere [Bir84] and [HIT99] this calls for the use of an accumulation tactic which generalizes (x: to (w ) asegs (w,xs) atten(map(tails (w ) inits(xs) A subsequent fusion transformation obtains: asegs (w, x] tails(w [x] asegs (w,x:xs) tails(w [x] asegs (w [x] xs) In general, this ....

Richard S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. on Programming Languages and Systems, 6(4):487-504, October 1984.

....We also show that the notion of downwards accumulation developed by Gibbons is subsumed by our notion of accumulation. 1 Introduction often called accumulators [20, 5, 15] In functional programming, the notion of accumulation is usually associated with the so called accumulation technique [8, 4, 18, 3], which transforms recursive definitions by the introduction of additional arguments over which intermediate results are computed. The accumulation technique is strongly connected with the familiar procedure of generalization for induction that arises in the field of theorem proving [7, 1, 26] A ....

.... X A) Examples of the use of these laws can be found in [29] 4 Accumulations Accumulations are recursive functions that keep intermediate results in additional parameters, known as accumulating parameters or accumulators, which are eventually used in later stages of the computation (see e.g. [4, 20, 5, 15]) In this section we define a generic operator that permits us to represent structural recursive accumulations on inductive types. The operator is obtained by a small modification in the definition of pfold. Let us start with an example of an accumulation. Consider the function that computes the ....

R.S. Bird. The Promotion and Accumulation Strategies in Transformational Programming. ACM Transactions on Programming Languages and Systems, 6(4), October 1984.

....guration is generated, and thus eciency is improved. By applying our proposed list introduction strategy we will mechanically derive a program which is similar to the accumulator program version of [StS94] Indeed, this strategy will allow us to realise the so called lter promotion described in [Bir84, Dar78], by which the safeness test is promoted into the generation process and the number of generated unsafe board con gurations is decreased. A similar e ect may also be achieved by the compiling control technique described in [BDK89] which works by transforming a given initial program into a new ....

.... of Cohen [Coh83] by which arrays whose dimensions depend on the size of the input are introduced, ii) the continuation based transformations of Wand [Wan80] whereby one exploits the power of higher order arguments which store sequences of function calls, iii) the accumulation technique of Bird [Bir84], which works by introducing variables to collect a number of previously computed values. All these techniques follow a schemata approach, by which program transformations are expressed as a catalogue of conditional equivalences between program schemata. In order to apply a transformation to a ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Toplas, 6(4):487{ 504, 1984.

....guration is generated, and thus, eciency is improved. By applying our proposed list introduction strategy we will mechanically derive a program which is similar to the accumulator program version of [StS94] Indeed, this strategy will allow us to realize the so called lter promotion described in [Bir84, Dar78], by which the safeness test is promoted into the generation process and the number of generated unsafe board con gurations is decreased. A similar e ect may also be achieved by the compiling control technique described in [BDK89] which works by transforming a given initial program into a new ....

.... of Cohen [Coh83] by which arrays whose dimensions depend on the size of the input are introduced, ii) the continuation based transformations of Wand [Wan80] whereby one exploits the power of higher order arguments which store sequences of function calls, iii) the accumulation technique of Bird [Bir84], which works by introducing variables to collect a number of previously computed values. All these techniques follow a schemata approach, by which program transformations are expressed as a catalog of conditional equivalences between program schemata. In order to apply a transformation to a ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Toplas, 6(4):487{ 504, 1984.

....of the speedup of the resulting algorithm. Equally or more important are the assurance of correctness for the algorithm and implementation developed and the ability to develop them easily and quickly. Much previous research has answered these questions positively for subclasses of problems, e.g. [10, 3, 27, 7, 24, 4, 12, 6, 29, 9, 25, 5, 14]. This paper describes a method that uni es and generalizes existing classes of problems that can be solved systematically. Important and interesting questions in detail are: How are appropriate data structures determined In case multiple choices exist, how can they be compared Two fundamental ....

.... optimized prog s running time Fibonacci function [23] O(2 n ) O(n) binomial coecients [23] O(2 n ) O(n k) longest common subsequence [8] O(2 n m ) O(n m) matrix chain multiplication [8] O(n 3 n ) O(n 3 ) string editing distance [26] O(3 n m ) O(n m) dag path sequence [4] O(2 n ) O(n 2 ) optimal polygon triangulation [8] O(n 3 n ) O(n 3 ) optimal binary search tree [1] O(n 3 n ) O(n 3 ) paragraph formatting [8] O(n 2 n ) O(n 2 ) paragraph formatting 2 [14] O(n 2 n ) O(n width) 0 1 knapsack [8] O(2 n ) O(n weight) ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

....function length which computes the number of elements of a set, and to denote the lter operator on set: p s produces a new set whose elements are all from the set s but satisfy the predicate p. The lter operator enjoys the lter map property (that is commonly used in program derivation e.g. Bir84] p ) x : x : p (x : 1) and the lter pipeline property: p ) q ) x: p x q x) 2) In addition, xs ys is true if xs is a sublist (i.e. subset) of ys, and false otherwise: ys = T rue (x : xs) ys = xs ys x 2 ys: So much for our speci cation ....

....the readers are familiar with the Haskell language [Bir98] in this paper. In addition, we say that our Haskell programs are pseudo in the sense that they include some additional notations for sets. 4 by using the known calculation techniques of fusion [Chi92] generalization (accumulation) Bir84, HIT99] base case lter promotion [Chi90] and tabulation [Bir80, CH95] Our derivation strategy is rather standard for program optimization and can be summarized as follows. First, we eliminate as much unnecessary intermediate data structures as possible by fusion of composition of recursive ....

[Article contains additional citation context not shown here]

R. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487-504, 1984.

....the Accumulation Promotion Theorems. 1 ] Deriving an accumulation for subs This derivation has been already given in Example 4.2. The result is as follows. subs xs = 1 5 2 ] F1 F2 xs ffl where 1 ( y = f[y]g 2 (x; p) y = p y [ y : 3 (p x) where F 1 = 1 and F 2 = a 2 I . [ 2 ] Manipulating (path ) ffi subs After obtaining the accumulation for subs, we step to derive an accumulation for the composition of the function path with the subs based on Theorem 5.1. Let k = path . We calculate 1 ; 2 from 1 ; 2 and k based on the 18 Zhenjiang HU, Hideya IWASAKI, Masato ....

....= x; p 0 ) y: p 0 y) if arc y x y 6= ffl then (y : 3 (p 0 x) else (p 0 x) ffi F 2 (kffi) Thus we get 2 defined as 2 (x; p) y = p y) h where h = if arc y x y 6= ffl then (y : 3 (p x) else (p x) Finally, according to Theorem 5. 1, we obtain ( path ) ffi subs) xs = [ 1 5 2 ]) xs ffl: 3 ] Promoting max ffi (length3) into the obtained accumulation We continue promoting max ffi length3 into the derived accumulation according to the Accumulation Promotion Theorems, as we did above. We omit the detail calculation but give the last result. psp xs = j 1 5 j 2 ] xs ....

) Bird, R. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems 6, 4 (1984), 487--504.

....another, making use of the previously computed output in computing a new output, instead of computing the new output from scratch. Incremental computation is a fundamental issue relevant throughout computer software, e.g. optimizing compilers [2,3,17,23,78] transformational program development [8,20,62,65,77], and interactive systems [5,6,10,22,33,41,71,72] Numerous techniques for incremental computation have been developed, e.g. 3,4,25,34 36,56,64,68,70,73,76,79,86] Strengthening invariants for incrementalization. We are engaged in an ambitious e ort to derive incremental extended programs ....

....enables further optimizations on the overall loop structure, as discussed in [47] 25 6. 2 Promotion and accumulation in transformational programming: path sequence problem This example was used by Bird to illustrate important program transformation strategies called promotion and accumulation [8]. Given a directed acyclic graph, and a string whose elements are vertices in the graph, the problem is to compute the length of the longest subsequence in the string that forms a path in the graph. We focus on the second half of the example, where an exponential time recursive solution is ....

[Article contains additional citation context not shown here]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

....general and systematic. Second, it stores only values that are necessary for the optimization; it also shows exactly when and where subproblems not in the original computation have to be included. Our method is based on a number of static analyses and transformations studied previously by others [6, 9, 21, 42, 47, 55, 56, 61] and ourselves [30, 37, 38, 39] and improves them. Each of the caching, incrementalization, and pruning steps is simple, automatable, and ecient and has been implemented in a prototype system, CACHET. The system has been used in optimizing many programs written as straightforward recursions, ....

.... prog s running time Fibonacci function [45] O(2 n ) O(n) binomial coecients [45] O(2 n ) O(n k) longest common subsequence [15] p O(2 n m ) O(n m) matrix chain multiplication [15] p O(n 3 n ) O(n 3 ) string editing distance [52] O(3 n m ) O(n m) dag path sequence [6] p O(2 n ) O(n 2 ) optimal polygon triangulation [15] p O(n 3 n ) O(n 3 ) optimal binary search tree [2] p O(n 3 n ) O(n 3 ) paragraph formatting [15] p O(n 2 n ) O(n 2 ) paragraph formatting 2 p O(n 2 n ) O(n width) 0 1 knapsack [15] p a O(2 n ) O(n ....

[Article contains additional citation context not shown here]

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Trans. Program. Lang. Syst., 6(4):487-504, Oct. 1984.

....control technique one can improve generate and test programs by simulating a computation rule which selects test predicates as soon as the relevant data become available. A similar idea has also been investigated in the area of functional programming, within the so called lter promotion strategy [9, 46]. Some other transformation techniques for improving generate and test logic programs which are closely related to the compiling control technique and the lter promotion strategy, can be found in [23, 136] The problem of compiling a given computation rule C can be described as follows: given ....

R. S. Bird. The promotion and accumulation strategies in transformational programming. ACM Toplas, 6(4):487504, 1984.

No context found.

Richard S. Bird. Addendum to "The promotion and accumulation strategies in transformational programming". ACM Transactions on Programming Languages and Systems, 7(3):490--492, July 1985.

No context found.

Richard S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, October 1984. See also [3].

No context found.

R.S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

No context found.

R. Bird, "The Promotion and Accumulation Strategies in Transformational Programming", ACM Transactions on Programming Languages and Systems, vol. 6, no. 4, pages 487--504, 1984.

No context found.

R.S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

No context found.

R.S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487--504, 1984.

No context found.

R.S. Bird. The promotion and accumulation strategies in transformational programming. ACM Transactions on Programming Languages and Systems, 6(4):487-504, October 1984.

First 50 documents  Next 50

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.