B. Paige and S. Koenig. Finite di#erencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-- 454, 1986.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....results used in computing the output f(x) also need to be maintained for efficient incremental computation of f(x Phi y) Moreover, certain auxiliary information about x may need to be discovered and maintained as well. Numerous techniques for incremental computation have been developed, e.g. [3, 4, 16, 20, 21, 24, 31, 36, 38, 40, 43, 44, 47, 52]. In [31] we give a systematic transformational approach for deriving an incremental program f from a given program f and an input change Phi. The basic idea is to identify in the computation of f(x Phi y) those subcomputations that are also performed in the computation of f(x) and whose ....

....useful intermediate results. Some methods in incremental computation exploit certain kinds of auxiliary information, e.g. auxiliary arithmetic associated with some classical strength reduction rules [3] dynamic mappings maintained by finite differencing rules for aggregate primitives in SETL [36] and INC [52] and auxiliary data structures for problems with certain properties like stable decomposition [40] and other decomposition properties [15] However, until now, the systematic discovery of auxiliary information for general problems has been a subject left completely open for study. ....

[Article contains additional citation context not shown here]

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, July 1982.

.... techniques to well worn examples, he was applying his theories of program transformation to new problems, and discovering new algorithms [16, 48, 52] The secret of his success lay partly in his insistence on the study of general algorithm design strategies (in particular nite di erencing [47, 51] and data structure selection [19] rather than the study of tiny derivational steps that some of the working group had focussed on. His success in the systematic discovery of new algorithms was in itself remarkable, but perhaps even more impressive was the fact that he succeeded in automating ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):401-454, 1982.

....which avoid repeated subcomputations (see the Context free Parsing example of Section 7. 5) In this respect our strategy is similar to the tupling strategy for functional programs [33] Finally, our specialization strategy is related to the program derivation techniques called nite di erencing [32] and incrementalization [26] These techniques use program invariants to avoid costly, repeated calculations of function calls. Our specialization strategy implicitly discovers and exploits program invariants when using the folding rule. It should be noticed, however, that it is dicult to ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, 1982.

....emphasizing that the architecture builds on fundamental research in programming languages. It integrates one way constraints pioneered in the Sketchpad and ThingLab object oriented systems [24, 4] and generalizes them to accommodate nite di erencing techniques on algebraic and set expressions [19, 29]. It also encapsulates ecient incremental graph algorithms [21, 1] and uses polymorphism heavily to obtain its compositional nature. Observe also that the resulting architecture has some avor of aspect oriented programming [13] since constraints represent and maintain properties across a wide ....

....guarantees that every pair hvariable; invarianti is propagate at most once during a propagation cycle. Invariants are classi ed into two main categories: static and dynamic invariants. Static invariants such as x y z are well studied in the programming language community (e.g. [19, 29]) These invariants are appealing because they make the dependencies between their variables explicit. As a consequence, it is simple in general to nd a partial ordering for the propagation steps that guarantees that each pair hvariable; invarianti is considered at most once. This assumes, of ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, July 1982.

....Sorting: Expression Optimization After performing algorithm design and datatype refinement, there are often opportunities for optimizing various subexpressions. Transformation rules and optimization tactics, such as equational rewriting, context dependent simplification [5] finite differencing [3], partial evaluation, and other more specialized techniques can result in dramatic improvements in the complexity of the final implementation. We show how at least some optimization techniques can be captured as refinements, and can be applied in the same manner as refinements that express ....

....we can assume the negation of the test of the conditional. spec Expression and Context is op C : D Boolean axiom C(x) expr(x) new expr(x) spec Context Dependent Simplification is import Expression and Context theorem C(x) expr(x) new expr(x) 24 Finite Differencing [3] is a less basic optimization and it has nondegenerate structure in the codomain of its represention as a refinement. The idea in finite differencing is to replace an expensive expression in a loop by incremental computation, making use of some extra variables. The following refinement expresses ....

Paige, R., and Koenig, S. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 402--454.

....are represented as dynamic sized arrays and memoisation is used to avoid the recomputation of these arrays. This method requires the use of suitable analysis techniques to compute at compile time safe bounds of the sizes of the arrays. The transformation methods based on nite di erencing [PaK82] and static incrementalization [LiS99] make use of invariants to eciently compute, from a collection of function calls relative to the input x, a new collection of function calls relative to a new input of the form: x , where is a suitable increment function. Our list introduction strategy ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, 1982.

.... techniques to well worn examples, he was applying his theories of program transformation to new problems, and discovering new algorithms [17, 49, 53] The secret of his success lay partly in his insistence on the study of general algorithm design strategies (in particular nite di erencing [48, 52] and data structure selection [20] rather than the study of tiny derivational steps that some of the working group had focussed on. His success in the systematic discovery of new algorithms was in itself remarkable, but perhaps even more impressive was the fact that he succeeded in automating ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):401-454, 1982.

....are represented as dynamic sized arrays and memoization is used to avoid the recomputation of these arrays. This method requires the use of suitable analysis techniques to compute at compile time safe bounds of the sizes of the arrays. The transformation methods based on nite di erencing [PaK82] and static incrementalization [LiS99] make use of invariants to eciently compute, from a collection of function calls relative to the input x, a new collection of function calls relative to a new input of the form: x , where is a suitable increment function. Our list introduction strategy ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, 1982.

....avoid repeated subcomputations (see the Context free Parsing example of Section 6. 5) In this respect our strategy is similar to the tupling strategy for functional programs [26] Finally, our specialization strategy is related to the program derivation techniques called nite 42 di erencing [25] and incrementalization [21] These techniques use program invariants to avoid costly, repeated calculations of function calls. Our specialization strategy implicitly discovers and exploits program invariants by using the folding rule. It should be noticed, however, that it is dicult to establish ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, 1982.

.... techniques to well worn examples, he was applying his theories of program transformation to new problems, and discovering new algorithms [17, 49, 53] The secret of his success lay partly in his insistence on the study of general algorithm design strategies (in particular nite di erencing [48, 52] and data structure selection [20] rather than the study of tiny derivational steps that some of the working group had focussed on. His success in the systematic discovery of new algorithms was in itself remarkable, but perhaps even more impressive was the fact that he succeeded in automating ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):401-454, 1982.

....and coroutining, and 24 2. the transformation of the given program into a semantically equivalent one which can be more e ciently evaluated by a non improved, standard evaluator. In the imperative and functional cases, various transformation methods have been proposed, such as nite di erencing [112], composition or deforestation [66, 150] and tupling [116] See also [67, 113, 118] for surveys. For logic programs two main methods have been considered: loop fusion [52] and elimination of unnecessary variables [125] The aim of loop fusion is to transform a program which computes a ....

....some algorithmic forms of theorem proving may also be added to the system. iv) Auxiliary transformation techniques. The transformation systems should allow an easy application of various transformation techniques such as: continuation based transformations [152] nite di erencing [112], schema transformations (see [113] for a survey) and changes of data structures [117] Acknowledgements We would like to thank A. Jung, E. Ritter, and the members of the Programme Committee of the ESSLLI 2000 European Summer School on Logic, Language, and Information. We are very happy that ....

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402454, 1982.

....is profitable or not. A global caching strategy has been proposed in [FRS93] For any given rule r in a program, a heuristic based algorithm decides which data to cache in terms of the kinds of dependencies that r has with the entire rule program. More precisely, the strategy, in the tradition of [PK82], Pai86] and [PH87] consists of extracting subexpressions in a rule that (i) can be efficiently differentiated with respect to the changes induced by the entire rule program, and (ii) whose caching, most probably, avoids repeated calculations. The important point is that all algorithms, ....

R. Paige and S. Koenig. Finite Differencing of Computable Expressions. ACM Transactions on Programming Languages and Systems, 4(3), 1982.

....the best choice would be the KIDS 18 [Smi90] system (or a descendant) BGG 94] Even if the specification of O is processible, the use of KIDS would be very useful because it contains several tools which could be of great help during our synthesis process. For instance, finite differencing [PK82, Smi90] simplification and partial evaluation would be helpful in order to transform the expression O(x 0 ; solu [ flcg) from the greedy program code (see p.28) into 18 Kestrel Interactive Development System. 48 more efficient expressions. And last but not least, KIDS covers many different ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

....is profitable or not. A global caching strategy has been proposed in [FRS93] For any given rule r in a program, a heuristic based algorithm decides which data to cache in terms of the kinds of dependencies that r has with the entire rule program. More precisely, the strategy, in the tradition of [PK82], Pai86] and [PH87] consists of extracting subexpressions in a rule that (i) can be efficiently differentiated with respect to the changes induced by the entire rule program, and (ii) whose caching, most probably, avoids repeated calculations. The important point is that all algorithms, whether ....

R. Paige and S. Koenig. Finite Differencing of Computable Expressions. ACM Transactions on Programming Languages and Systems, 4(3), 1982.

....discerned. The simple accumulation strategy allows only the derivation of accumulator versions of functions, as in the above examples. Embedding of the domain (a parameter is added to a function) is the underlying strategy for accumulation, but also for other strategies like finite differencing [PK82] Continuation based transformation strategies also allow the derivation of programs with functions as parameters. All three strategies rely on the generalisation of a constant to a parameter; the constant may not always be visible, however. 6 On the equivalence of certain computations In the ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-- 454, July 1982.

....in an efficient way and, in particular, the generalization step proposed in Section 6 requires in practice only a very limited search. The idea of specializing logic programs w.r.t. complex contexts is strongly related to the techniques of internal specialization [14] and finite differencing [12], in the case of functional and set based imperative languages, respectively. However, it is hard to establish a formal relationship among these techniques, because of the different formalisms used. In the field of functional programming various extensions of the partial evaluation technique have ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

....and 2. the transformation of the given program into a semantically equivalent one which can be more efficiently evaluated by a non improved, standard evaluator. In the imperative and functional cases, various transformation methods have been proposed, such as, for instance: finite differencing [ Paige and Koenig, 1982 ] composition or deforestation [ Feather, 1982; Wadler, 1990 ] and tupling [ Pettorossi, 1977 ] See also [ Feather, 1987; Partsch, 1990; Pettorossi and Proietti, 1996 ] for surveys. For logic programs two main methods have been considered: loop fusion [ Debray, 1988 ] and unnecessary ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

....3, 10, 11, 20, 22, 42] is a classical loop optimization technique in optimizing compilers. The idea is to replace certain operations in loop bodies by faster operations. For example, a multiplication involving an induction variable can sometimes be transformed into an addition. Finite differencing [34, 35, 36] generalizes strength reduction to languages with expressions composed of aggregate operations like set operations. Basically, a set of finite differencing rules are developed to transform aggregate operations in loop bodies into more efficient incremental operations. The essence of these ....

....of our algorithm is larger. We plan to analyze complexity on certain classes of problems. Inductively computable constructs in very high level languages [16, 17, 18] generalize conventional strength reduction and the elimination of induction variables to set based languages. Finite differencing [34, 35, 36] and fixed point recomputation [9] systematically reduce strength of programs that use fixed point iteration and set theoretic notations as the initial program specification. These techniques do not handle function abstractions, conditionals, or data types other than sets, as we do. In general, ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, July 1982.

....the question of producing efficient programs attracted attention [Fea82, BW82, PP86, Par90] In particular, recursion elimination is addressed. According to [Boi92] the strategies of the cited papers can be divided into the following categories: accumulation, finite differencing (cf. e.g. [PK82]) algorithm theories, and inverting the order of evaluation. In [Kla88] an alternative way of getting rid of structural recursion in functional programming languages is suggested. Roughly speaking, there the recursion elimination is integrated into the compiler and the resulting iteration is ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

....is the case then it is possible to avoid intermediate data structures by introducing a finite number of new function definitions which correspond to (a subset of) the terms generated by unfolding. Finally, among other techniques for program derivation we want to consider also finite differencing [35, 36]. The revisitation of this technique as an instance of our general methodology is not very straightforward. However, the three steps of finite differencing, which are: i) syntactic recognition of computational bottlenecks appearing within a program P , ii) choosing invariants whose maintenance ....

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

....Sorting: Expression Optimization After performing algorithm design and datatype refinement, there are often opportunities for optimizing various subexpressions. Transformation rules and optimization tactics, such as equational rewriting, context dependent simplification [5] finite differencing [3], partial evaluation, and other more specialized techniques can result in dramatic improvements in the complexity of the final implementation. We show how at least some optimization techniques can be captured as refinements, and can be applied in the same manner as refinements that express ....

....of the conditional. spec Expression and Context is import Expression op C : D Boolean op new expr : D Q axiom C(x) expr(x) new expr(x) end spec spec Context Dependent Simplification is import Expression and Context theorem C(x) expr(x) new expr(x) end spec Finite Differencing [3] is a less basic optimization and it has nondegenerate structure in the codomain of its represention as a refinement. The idea in finite differencing is to replace an expensive expression in a loop by incremental computation, making use of some extra variables. The following refinement expresses ....

Paige, R., and Koenig, S. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 402--454.

....results used in computing the output f(x) also need to be maintained for efficient incremental computation of f(x Phi y) Moreover, certain auxiliary information about x may need to be discovered and maintained as well. Numerous techniques for incremental computation have been developed, e.g. [3, 4, 16, 20, 21, 24, 31, 36, 38, 40, 43, 44, 47, 52]. In [31] we give a systematic transformational approach for deriving an incremental program f 0 from a given program f and an input change Phi. The basic idea is to identify in the computation of f(x Phi y) those subcomputations that are also performed in the computation of f(x) and whose ....

....the useful intermediate results. Some methods in incremental computation exploit certain kinds of auxiliary information, e.g. auxiliary arithmetic associated with some classical strength reduction rules [3] dynamic mappings maintained by finite differencing rules for aggregate primitives in SETL [36] and INC [52] and auxiliary data structures for problems with certain properties like stable decomposition [40] and other decomposition properties [15] However, until now, the systematic discovery of auxiliary information for general problems has been a subject left completely open for study. ....

[Article contains additional citation context not shown here]

R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, July 1982.

No context found.

B. Paige and S. Koenig. Finite di#erencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-- 454, 1986.

No context found.

R. Paige and S. Koenig. Finite dierencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402-454, July 1982.

No context found.

R. Paige and S. Koenig. Finite di#erencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3):402--454, 1982.

First 50 documents

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.