) Turchin V., "The Concept of a Supercompiler," ACM Transactions on Programming Languages and Systems, 8, 3, pp. 292--325, July 1986.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....kildeprogrammet, via en sekvens af meningsbevarende trin, transformeret ind i malprogrammet; i vores begrebsramme observerer man hvordan kildeprogrammet opfrer sig, og ved hjlp af den information konstruerer man sa et malprogram. For en nrmere sammenligning af de to perspektiver se f.ex. Tur86, p. 293] iflge hvilken frstnvnte er suggested by axiomatic mathematics og sidstnvnte er a product of cybernetic thinking . En oversigt over afhandlingen . I kapitel 2 uddyber vi ovennvnte behandling af mange niveau transitionssystemer. Vi kigger pa flere velkendte teknikker for optimering ....

....(hopefully) meaning preserving steps is transformed into the target program; in our framework the behavior of the source program is observed , and by means of the information thus gained a target program is constructed. For a further discussion of the merits of the two perspectives see [Tur86, p. 293] according to which the former is suggested by axiomatic mathematics and the latter is a product of cybernetic thinking . 1.1 An overview of the thesis . In chapter 2 we elaborate on the concept of multilevel transition systems. In particular we examine several well known program ....

[Article contains additional citation context not shown here]

Valentin F. Turchin. The concept of a supercompiler. 8(3):292--325, July 1986.

....have started from naive, nondeterministic initial programs, while the corresponding derivations by partial deduction described in the literature, use initial programs which are deterministic. Our derivations also improve over the derivations performed by using supercompilation with perfect driving [15, 46] and generalized partial computation [12] which start from initial functional programs which already incorporate some ingenuity. A formal derivation of the Knuth Morris Pratt algorithm for pattern matching has also been presented in [3] This derivation follows the calculational approach which ....

.... by cases, which is a very well known technique in mechanical theorem proving (see, for instance, the Edinburgh LCF theorem prover [17] Forms of reasoning by cases have been incorporated in program specialization techniques such as the already mentioned supercompilation with perfect driving [15, 46] and generalized partial computation [12] However, the strategy presented in this paper is the rst fully automatic transformation technique which uses case reasoning to reduce nondeterminism of logic programs. Besides specializing programs and reducing nondeterminism, our strategy is able to ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292-325, 1986.

....subsidiary strategy, and (ii) the set of de nitions which are introduced for performing folding steps. In particular, for ensuring termination it may be necessary to consider suitable generalizations of the bodies of the clauses to be folded (see, for instance, the techniques presented in [5, 8, 12, 18, 20, 26]) However, the generalization technique required when applying the Determinization Strategy is more sophisticated than the ones proposed for the case of partial evaluation of (constraint) logic programs [8, 12, 20] This is due to the fact that the new de nitions which are introduced during the ....

V. F. Turchin. The concept of a supercompiler. ACM Toplas, 8(3):292-325, 1986.

....Computer Science, University of Copenhagen. One of the weaknesses [2] of such transformations is the inability to deforest programs using accumulating parameters. This is not just a deficiency of these techniques, for other program transformers su#er from the same weakness (e.g. supercompilation [22] , calculational methods [10] When composing a consumer of lists with a producer of lists, where the producer is written using an accumulating parameter, the intermediate list cannot be removed. For example, the expression rev (rev xs) cannot be fused into a single copy xs (let al..one ....

V. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3): 292--325, 1986.

....subsidiary strategy and (ii) the set of de nitions which are introduced for performing folding steps. In particular, for ensuring termination it may be necessary to consider suitable generalizations of the bodies of the clauses to be folded (see, for instance, 5] 7] 10] 15] 16] [22]) As a consequence of Theorem 1, if the Determinization Strategy terminates, then the specialized program Psp is equivalent to the initial program P in the following sense: for every constraint d, lm(P; D) j= 9(d c p(t1 ; t h ) i lm(Psp ; D) j= 9(d psp (X1 ; Xr ) ....

....We have introduced a new transformation rule, called clause splitting, which can be used for reducing the nondeterminism when specializing constrained logic programs. This rule allows us to reason by cases as often done in various specialization techniques (see, for instance, 9] 13] [22]) Clause splitting, together with the other familiar unfolding and folding rules, is applied according to the Determinization Strategy which is an enhancement of conjunctive partial deduction [5] Indeed, we allow new predicates to be de ned in terms of disjunctions of conjunctions of ....

V. F. Turchin. The concept of a supercompiler. ACM Toplas, 8(3):292-325, 1986.

....since we also present a transformation of accumulative into non accumulative programs, we obtain the equality of the classes of functions computed by the two paradigms. Well known techniques for eliminating intermediate results cannot improve p non : i) deforestation [24] and supercompilation [22, 20] su#er from the phenomenon of the obstructing function call [2] and (ii) shortcut deforestation [14, 13] is hampered by the unknown number of intermediate results. In [3] an extension of shortcut deforestation was developed which is based on type inference and splits function definitions into ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8:292--325, 1986.

....Regardless of which interpreter we use, the semantics modification we get is precisely what is intended (e.g. inverse computation) 3.4. Two Levels of Interpretation A non standard interpreter obtained from a semantics modifier is the result of two distinct metasystem transitions [51]. 0) Direct computation of N programs: out. 1) First transition from direct computation of N programs to their interpretation: intN [pgm, dat] # (2) Second transition from direct computation of N s interpretation to non standard computation of N s interpretation in M: Let intNL be an ....

....to apply them to programs written in any language via an interpretive definition. It is straightforward to define an equivalence transformer for any language N in M given a standard interpreter for N in L (Fig. 2) The experiments in Section 11 illustrate these ideas using supercompilation [51], a powerful transformation method capable of program specialization and program composition (see [45] and the projections in Section 13 show how an N#R M transformer can be obtained from an L#R M transformer and an N L interpreter. 6.2. A Program Specializer as Eqt Modifier A program ....

[Article contains additional citation context not shown here]

V. F. Turchin, "The concept of a supercompiler," Transactions on Programming Languages and Systems 8(3) (1986) 292--325.

....nondeterministic initial programs, 41 while the corresponding derivations by partial evaluation described in the literature, use initial programs which already incorporate some ingenuity. A similar remark also applies to the derivation performed by using supercompilation with perfect driving [12, 38] and generalized partial computation [9] A formal derivation of the Knuth Morris Pratt algorithm for pattern matching has also been presented in [2] This derivation follows the calculational approach which consists in applying equivalences of higher order functions. On the one hand the ....

.... by cases, which is a very well known technique in mechanical theorem proving (see, for instance, the Edinburgh LCF theorem prover [14] Forms of reasoning by cases have been incorporated in program specialization techniques such as the already mentioned supercompilation with perfect driving [12, 38] and generalized partial computation [9] However, the strategy presented in this paper is the rst fully automatic transformation technique which uses case reasoning to reduce nondeterminism of logic programs. Besides specializing programs and reducing nondeterminism, our strategy is able to ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292-325, 1986.

....for other program transformers su er from the same Research fellow of the Japan Society for the Promotion of Science y PRESTO, Japan Science and Technology Corporation (JST) on leave from DIKU, Dept. of Computer Science, University of Copenhagen 10 weakness (e.g. supercompilation [18], calculational methods [10] For example, the expression rev (rev xs) cannot be fused into a single copy xs (let al..one identity) when rev is the fast version of list reversal. When composing a consumer of lists with a producer of lists, where the producer is written using an accumulating ....

V. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3): 292-325, 1986.

....to have transformation techniques, which enable us to optimize functions written in the modular style, by eliminating intermediate data structures. Several such techniques have been studied in the literature, e.g. the fold unfold technique from [BD77] its algorithmic instances supercompilation [Tur86] and deforestation [Wad90] catamorphism fusion [Mal89, MFP91] and shortcut deforestation [GLP93] In this thesis, we follow an approach for eliminating intermediate results, which is based on the theory of tree transducers. Particularly, we consider Macro Tree Transducers [Eng80] which can ....

V.F. Turchin. The concept of a supercompiler. ACM Trans. on Prog. Lang. and Systems, 8:292-325, 1986.

....and provides binding time annotations which encode the control decisions to be made by the specialiser, so that the specialiser becomes much more simple and efficient. Partial evaluation of functional programs [8, 15] has mainly stressed off line approaches, while supercompilation of functional [32, 31] and partial deduction of logic programs [13, 3, 1, 30, 25, 20] have concentrated on on line control. On line methods, usually obtain better specialisation, because no control decisions have to be taken beforehand, i.e. at a point where the full specialisation 1 Formally, an SLDNF tree is ....

V. F. Turchin. The Concept of a Supercompiler. ACM Trans. Prog. Lang. Syst., 8(3):292--325, July 1986.

....B and a singlethreaded store S. Furthermore there is the outcome status O, which can be failed or completed. Y [T;B;S] datum(D) D 6=nothing give(Y;N) T;B;S] completed; N7 datum(D) S] Y [T;B;S] datum(D) not(D 6=nothing) give(Y;N) T;B;S] failed; S] 2 Positive supercompilation [12, 11] is a program specialization technique developed in the functional community. Its adaption to Prolog is not much different from partial evaluation of Prolog [5] Pass Separation . C C L1 Ln 2BIG DCAMG L1 2BIG AN 2BIG Ln 2BIG . AM L1 C L1 AM AN C AN AM Ln C ....

V.F. Turchin. The Concept of a Supercompiler. ACM TOPLAS, 8(3), 1986.

....for a particular usage. A lot of attention has been paid to specialisation of functional programs, where on line as well as o# line approaches have been followed. Research in the on line field include Fuse (Weise, Conybeare, Ruf, and Seligman 1991) and Turchin s original work on supercompilation (Turchin 1986), later on revisited by Srensen and others (Srensen 1994; Srensen and Gluck 1995; Srensen, Gluck, and Jones 1996) However, in the functional setting most work focuses on binding time analysis and o# line specialisation, originally motivated to achieve better self application (Futamura 1971; ....

.... setting, one can partially evaluate only those expressions that depend solely on static input, whereas in a logic programming setting, one can often reduce expressions that do depend on some dynamic input (Leuschel and Bruynooghe 2001) which relates the technique more to supercompilation (Turchin 1986; Srensen and Gluck 1995; Srensen, Gluck, and Jones 1996; Gluck and Srensen 1996; Srensen, Gluck, and Jones 1994) in functional languages and unfold fold transformation techniques (Burstall and Darlington 1977; Pettorossi and Proietti 1994) In the context of this thesis, we consider only pure ....

Turchin, V. F. (1986). The concept of a supercompiler. ACM Transactions on Programming Languages and Systems 8 (3), 292--325.

.... it would be interesting to integrate other techniques for the elimination of intermediate results into such a comparison, e.g. shortcut deforestation [GLP93, Gil96] program calculation techniques based on recursion operators [Mal89, MFP91, SF93, BdM96, HIT96, J ur00] and supercompilation [Tur86, SGJ96, SS99]. The theory provides other classes of tree transducers that might be employed for the elimination of intermediate results. For example, modular tree transducers [EV91] are used in [KGK01] to transform non accumulative functional programs into accumulative ones. It could be fruitful to consider ....

V.F. Turchin. The concept of a supercompiler. ACM Trans. on Prog. Lang. and Systems, 8:292-325, 1986.

....program transformation techniques, which enable us to optimize functions written in the modular style, by eliminating intermediate data structures. Several such techniques have been studied in the literature, e.g. the fold unfold technique from [BD77] its algorithmic instances supercompilation [Tur86, SGJ96, SS99] and deforestation [Wad90, Chi94] catamorphism fusion [Mal89, MFP91] and shortcut deforestation [GLP93, Gil96] In this paper we follow an approach for eliminating intermediate results, which is based on the theory of tree transducers [FV98] Particularly, we consider macro tree ....

V.F. Turchin. The concept of a supercompiler. ACM Trans. on Prog. Lang. and Systems, 8:292-325, 1986.

....else F ibonacci(1000) 2: To facilitate these transformations, we inline all function calls where the function is not de ned recursively. The power of these transformations depends on reasonings used in simplifying the conditionals, as have been studied in many program transformation methods [51, 45, 47, 18, 32]. At least syntactic equality can be used, which identi es the most obvious source of inaccuracy. These optimizations also speed up the symbolic evaluation, since now obviously infeasible execution paths are not searched. 15 These transformations have been implemented and applied on many test ....

V. F. Turchin. The concept of a supercompiler. ACM Trans. Program. Lang. Syst., 8(3):292-325, July 1986.

....in [122] for indicating a strategy which derives a new predicate de nition when a goal is recurrently generated during program transformation. This strategy is present in various forms in a number of di erent transformation techniques, such as the above mentioned tupling, supercompilation [147], compiling control [25] as well as various techniques for partial evaluation (see Section 3.3) Finally, the generalization strategy has its origin in the theorem proving area [18] where it is used to generate a new generalized conjecture allowing the application of an inductive hypothesis. ....

....of the SLD trees, nor can introduce disequalities. Thus, our de nition and folding rules which allow us to specialize programs w.r.t. disjunctions of conjunctions of goals, generalize conjunctive partial deduction. Supercompilation Supercompilation is a technique introduced and studied in [79, 147] for the semiautomatic improvement of programs by taking into consideration the various computation paths. However, those paths are considered in isolation and no relationship among them is exploited. Since our de nition and folding rules allow us to factorize common computations in di erent ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292325, 1986.

....whose de nition we refer to [20] In order to discover redundant computations of this kind, we may symbolically generate and examine the set of the SLD derivations starting from a given goal. Symbolic evaluation is a standard analysis technique used in various program transformation methods [6, 8, 30]. In particular, by constructing a nite upper portion of the SLD tree starting from the goal of interest, we may nd equal subgoals which have to be evaluated along distinct branches of that SLD tree, and thus, they produce redundant computations. The description of general analysis techniques ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292-325, 1986.

....by programs as metacomputation, a term that underlines the fact that this activity is one level higher than ordinary computation. Equivalence transformation of programs is the main possibility for metacomputation; in this paper we use program composition and program specialization (see e.g. [9,12,7,2]) We will not fix a particular method for metacomputation, but specify these two transformation tasks equationally. Definition 3 (Program composition) An M program Cpo is an AB composer if for every A program P, Q D, every input X D and x M, Cpo M = R such that R X B = P Q ....

Turchin V. F., The concept of a supercompiler. ACM TOPLAS, 8(3): 292-325, 1986.

....component, but never appear in the result of the whole program. The compositional style of programming has many advantages of clarity and higher level of modularity, but these intermediate data structures give rise to an efficiency problem. Inspired by Turchin s early work on the supercompiler [TNT82, Tur86], Wadler [Wad88] introduced the idea of deforestation to tackle this problem. His algorithm for deforestation eliminates arbitrary tree like intermediate data structures (including lists) when applied to treeless programs. There have been various attempts to extend his method ( Chi92, Sr94] but ....

V.F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, July 1986.

.... very successfully does specialization [Jones et al. 1993] deforestation [Wadler 1990] and fusion [Fegaras et al. 1994] optimize composition of particular forms of recursive functions, slicing [Weiser 1984] produces a program returning a subset of the original output, and supercompilation [Turchin 1986] addresses all of these problems. Program generation and degeneration can be seen as test cases for existing methods and may allow for several novel applications of specialization and composition [Gluck and Klimov 1995; Gluck and Klimov 1997b] 4 Delta Andrei V. Klimov Nevertheless, the main ....

Turchin, V. F. 1986. The concept of a supercompiler. Transactions on Programming Languages and Systems 8, 3, 292--325.

....we define an auxiliary function (i.e. a new node in GPC tree) for residual programs, it is better for folding to extend the domain of the function as much as possible. Generalization in program transformation was first dicussed by Burstall and Darlington [3] and in partial evaluation by Turchin [30]. However, the extension of the domain is opposite to the specialization of programs. Therefore, we have to do both specialization and generalization in at the same time (or nondeterministically) to produce optimal residual programs. In our current implementation, the domain of a new function ....

Turchin, V.F.: The concept of a supercompiler. ACM TOPLAS 8 (3) (1986) 292-- 325.

....of the algorithm to handle richer input languages, e.g. including higher order functions, and more powerful transformations. The more powerful methods which are also covered by these generalisations include a sourcelevel representation of Turchin s driving, as found in the supercompiler [35]. An essential component of all of these transformations is the ability to create new recursive structures. We provide what we believe to be the first correctness proof for any of this class of transformations, including deforestation, to deal explicitly and correctly with the recursion ....

.... as in our standard operational semantics (and as implicit in some other formulations of deforestation [7] passive contexts which enable transformations to be pushed deeper into a term, and basic rewrites which mimic those of ordinary evaluation, plus rules which also perform driving [35]. This strategy yields a very simple and uniform extension of the transformation to richer languages, including higher order functions, since extensions to the language (and its operational semantics) can be expressed in terms of additions to reduction contexts, passive contexts and basic ....

[Article contains additional citation context not shown here]

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8:292--325, July 1986.

....0. 6 Related Work Partial Evaluation Partial Evaluation (PE) is not a new invention; the term was coined in 1964 in the context of coping with incomplete information in LISP evaluation [81] First PE like optimizations can be traced back to the REFAL compiler [33] and Turchin s supercompiler [114, 115]; one theoretical milestone was the definition of the Futamura projections [52] cf. section 5.3) Due to its origins in LISP evaluation, most early PE systems were based on the on line principle, i.e. they reconstructed the program during its execution. An example is the REDFUN system [10, 56] ....

V.F. Turchin, The concept of a supercompiler, in: ACM Transactions on Programming Languages and Systems, 8(3), July 1986, pp. 292-325

....existing implementation components is a main activity when producing customized software. Unfortunately, program hierarchies and modularity do not come for free: they add intermediate data structures, redundant computations, interface code and error checking. Program composition techniques (e.g. [32, 36]) can remove such redundancies, and allow fusing components without paying an unacceptably high price. Runtime Code Generation systems allow libraries to generate customized code at run time. This makes it possible to perform optimizations which depend on information not available until run time, ....

.... module XD = XromasomeDemo; 2 Declare the Value type 3 export template[type T] 4 type[XD: NotRef(0) Value f 5 Annotation brackets export proc init(ref rdonly T) 6 var T v ; 7 g 8 Example uses of Value: 9 proc init( f 10 Module initialization var Value[int[32]] a; 11 Okay ref Value[int[32] b; 12 Okay 12 var Value[ref int[32] c; 13 Error g 14 g 15 End program module The keyword type (line 5) is similar to the C keyword class. Square brackets are used to denote template parameters (line 4) template arguments (lines 11 13) and ....

[Article contains additional citation context not shown here]

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, 1986.

....component fusion. 2 Background Darlington and Burstall showed how fold unfold transformations could be used (with human help) to produce singlepass function definitions from the composition of two or more other functions [DB76] Turchin applied similar ideas within his supercompilation process [Tur86]. The supervisingcompiler performed a symbolic execution of the program, building a residual program whenever computations could not be performed. Patterns in the nesting of recursive calls of functions were spotted and a single new recursive function produced. While the process showed a high ....

V.Turchin, The Concept of a Supercompiler. ACM TOPLAS, 8, 3, pp 292-325, 1986.

....This set of transformations is sufficiently fine grained that a wide range of program transformations can be composed from it. The missing piece in this approach is a fully automatic way of deciding when to apply the transformations. Partial evaluation [Consel and Danvy 1993] and supercompilation [Turchin 1980; 1986; Turchin et al. 1982] can be seen as fold unfold strategies for this transformational method. A comparison of these and other fold unfold strategies was undertaken by Srensen et al. 1994] They compared the fold unfold methods on their ability to perform the KMP optimization the optimization ....

Turchin, V. F. 1986. The concept of a supercompiler. ACM Trans. Program. Lang. Syst. 8, 3 (July), 292--325.

....Victoria A. Pinchuk, and Valentin F. Turchin A supercompiler is a program which can perform a deep transformation of programs using a principle which is similar to partial evaluation, and can be referred to as metacomputation. Supercompilers that have been in existence up to now (see [21] [20]) were not self applicable: this is a more difficult problem than self application of a partial evaluator, because of the more intricate logic of supercompilation. In the present paper we describe the first self applicable model of a supercompiler and present some tests. Three features distinguish ....

V. F. Turchin. The concept of a supercompiler. ACM Trans. Prog. Lang. Syst., 8(3):292--325, July 1986.

....whose definition we refer to [20] In order to discover redundant computations of this kind, we may symbolically generate and examine the set of the SLD derivations starting from a given goal. Symbolic evaluation is a standard analysis technique used in various program transformation methods [6, 8, 30]. In particular, by constructing a finite upper portion of the SLD tree starting from the goal of interest, we may find equal subgoals which have to be evaluated along distinct branches of that SLD tree, and thus, they produce redundant computations. The description of general analysis techniques ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292-- 325, 1986.

....rather than well founded orderings. Its merits are illustrated on several examples. 1 Introduction Program specialization has received much attention in the area of logic and functional languages, e.g. partial deduction [12, 11, 4] partial evaluation [9] and deforestation [26] Supercompilation [23] is a program transformation technique for functional languages that is strictly stronger than partial evaluation and deforestation. It is capable of theorem proving and program inversion [20, 21, 22] and of program optimization beyond partial evaluation and deforestation [5] Recent renewed ....

....a slight modification of our technique in order to shorten the examples and improve the results. Terms of the following three forms are called transient. e[case (c t 1 : t n ) of p 1 s 1 ; pm tm ] e[f t 1 : t n ] e[if b=b 0 then t else t 0 ] with b; b 0 ground Following [23] we proceed as follows. In every iteration of the while loop in Algorithm 4.10 with a transient term we perform an unfold step, a transient reduction, without checking ancestors for whistling. Moreover, for the remaining types of terms, when we compare to ancestors, we only compare to ancestors ....

[Article contains additional citation context not shown here]

V.F. Turchin. The Concept of a Supercompiler. TOPLAS. 8(3): 292-325, 1986.

....computation, and (iii) p may be non terminating while p is terminating. Of these, iii) is probably not a problem in practice; for instance, some transformers choose to ignore the possibility of changing non terminating programs into terminating ones, e.g. Fuse [Wei91] and the supercompiler [Tur86]. ii) is well known in deforestation. Figure 2 gives a CBN CPS version of the program in Fig. 1. The idea in CBN CPS is that every expression translates into a function :t that expects a continuation argument. Applying the function to a continuation evaluates the expression to weak head normal ....

V. F. Turchin. The Concept of a Supercompiler. In ACM Transactions on Programming Languages and Systems. Vol. 8, No. 3, pp. 292- 325, 1986.

....insights and developments, e.g. with respect to termination and generalization (abstraction) which are current research topics in both worlds. In the following we refer to Lloyd Shepherdson s partial deduction [Llo91, Kom92] and to positive driving [Glu93, Sor94c] a variant of Turchin s driving [Tur86] for a functional language with lists. Both transformation techniques developed independently, at different places and times. Komorowski introduced Supported by an Erwin Schrodinger Fellowship of the Austrian Science Foundation (FWF) under grant J0780 and J0964. partial deduction into logic ....

.... interest in this area, e.g. Kom92] The main theoretical results for partial deduction were developed by Lloyd and Shepherdson [Llo91] Driving was conceived in the early seventies by Turchin in the former USSR [Tur72] and developed into a comprehensive methodology summarized as supercompilation [Tur80a, Tur86]. It strictly contains partial evaluation as well as Wadler s more recent invention deforestation [Wad90] but driving and supercompilation have taken longer to be recognized in the context of program specialization, e.g. Jon94] However, the functional language used in this paper does not allow ....

V. F. Turchin. The Concept of a Supercompiler. In ACM TOPLAS. 8(3), 292325, 1986.

....1990 ] for indicating a strategy which derives a new predicate definition when a goal is recurrently generated during program transformation. This strategy is present in various forms in a number of different transformation techniques, such as the above mentioned tupling, supercompilation [ Turchin, 1986 ] compiling control [ Bruynooghe et al. 1989 ] as well as various techniques for partial evaluation (see Section 6) Finally, the generalization strategy has its origin in the automated theorem proving context [ Boyer and Moore, 1975 ] where it is used to generate a new generalized ....

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, 1986.

....the interactions that may occur while evaluating these subgoals. For functional and imperative programs, various transformation methods have been proposed in the literature, which can be classified under this category, e.g. finite differencing [40] deforestation [59] and super compilation [56, 51]. Loop merging, in Section 2.1.3, also called loop fusion by Debray [14] is one of the transformation techniques that was proposed for improving programs that were written in compositional style. This technique transforms the program for a relation that is defined as the composition of two ....

V.F. Turchin. The concept of a supercompiler. ACM TOPLAS 8(3):292-- 325, 1986.

....whereabstraction step computationally significant. This is why in the unfold fold technique one looks for final folding steps to be made at the end of the derivation. The same occurs, for instance, in the supercompilation technique where one looks for self sufficient models of the computation [52]. In the following sections we illustrate in some detail the general methodology for program transformation we have seen in action in this preliminary example. We also indicate the way in which various techniques for program transformation proposed in the literature fit into this general ....

....methodology, that is, the derivation of a new program from the initial one. Finiteness of the symbolic trace graphs is related to analogous properties which are required in other transformation techniques, such as self sufficiency of the graphs of states and transitions in supercompilation [52], foldability of the unfolding trees in unfold fold program transformation [43] and closedness in partial deduction [31] The extraction of the derived program is performed as we now indicate (see also Figure 3) new1( M : new2( new3( N : new4( i i i i i i) oe P P P ....

[Article contains additional citation context not shown here]

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, 1986.

....unfolding in a strict language, or optimizations for strict versions of data structures such as head(cons(x ; y) x . Transformations using inequalities in this direction will be called weak transformations. Such transformations are common in strict languages e.g. in Turchin s supercompiler[Tur86]. The following definition of transformation (weak transformation) will enable us to formulate the correctness problem and state some relatively standard partial correctness results. Definition 3.1 (Transformation) Weak Transformation) A transformation (weak transformation, respectively) of a ....

V. F. Turchin. The concept of a supercompiler. ToPLaS, 8:292--325, July 1986.

....matcher very similar to the Knuth Morris Pratt algorithm. Deforestation and traditional partial evaluation achieve this effect only after a non trivial hand rewriting of the general matcher. Capsule Review Supercompilation is a technique of function transformation developed originally by Turchin (1986) for a functional language Refal. The technique uses DRIVING (the forced unfolding guided by functional configurations) to construct a potentially infinite tree of states (configurations) and transitions. This tree is then converted into a self sufficient graph by reducing some of the ....

....for logic programs can do this optimization, e.g. Proietti and Pettorossi, 1991) 8. 3 Other effects Positive supercompilation can invert functions just like interpreters for logic programs, and can be used for theorem proving and problem solving (Turchin, Nirenberg, and Turchin, 1982; Turchin, 1986). In general, to obtain these effects, the additional power of positive supercompilation over deforestation is required. Most of these examples have been considered for Turchin s supercompiler, but positive supercompiler can achieve similar effects (as demonstrated by the KMP example above) ....

Turchin, V.F. 1986. The concept of a supercompiler. In ACM Transactions on Programming Languages and Systems, 8(3): 292--325.

....on the supercompiler as a theorem prover. In 1982, experiments with an implementation of the supercompiler were reported by Turchin and co workers [Tur82] In 1986 three papers appeared: Tur86a] describing Refal and containing a brief discussion on the philosophy underlying the project, and [Tur86b,Tur86c] describing the driving part of the supercomiler in detail. In 1987 Turchin published the paper [Tur87] which gives a foundation of mathematics in terms of metasystem transition. In 1988 the paper [Tur88] described the means of automatically ensuring termination of supercompilation. As far as the ....

....are, however, three problems with the complicated notion of pattern matching in Refal. i) It may be questioned whether the language is sufficiently minimal; metaalgorithms for expressing pattern matching, as are needed in an interpreter and in the supercompiler itself, are fairly complicated, see [Tur86b,Tur86c]. This means that it becomes complicated to reason about interpreters, supercompilers and other metaalgorithms. ii) It makes it hard to focus on the essence of supercompilation or, more specifically, the essence of driving. iii) It makes it hard to compare supercompilation with related program ....

[Article contains additional citation context not shown here]

V. F. Turchin. The Concept of a Supercompiler. In ACM Transactions on Programming Languages and Systems. Vol. 8, No. 3, pp. 292- 325, 1986.

.... program specialization and partial evaluation are treated almost as synonyms, although sometimes program specialization carries the nuance of expressing a broader perspective that encompasses a number of kindred techniques, such as generalized partial evaluation [7] supercompilation [33], bifurcation [23] and deforestation [35] However, this overlooks an often unappreciated fact, namely that program slicing can also be used to perform a kind of program specialization and one that is different from the kinds of specializations that partial evaluation and its close ....

Turchin, V.F., "The concept of a supercompiler," ACM Trans. Program. Lang. Syst. 8(3) pp. 292-325 (July 1986).

....for a program p is a model of p s computational behavior for a given set of initial states ci. In the following we refer to process graphs when we mean correct process graphs. Graph Developers. How can one construct a process graph for a program and an initial config uration Supercompilation [22,24] uses two methods for graph development: driving and folding . Driving . This is a general method for constructing a (potentially infinite) process tree (a process graph that happens to be a tree) by step wise exploring all possible computations of a program p starting from an initial ....

....methods for graph development: driving and folding . Driving . This is a general method for constructing a (potentially infinite) process tree (a process graph that happens to be a tree) by step wise exploring all possible computations of a program p starting from an initial configuration ci [20,22,24]. At any point during driving one has a perhaps incomplete process tree and a way to extend the process tree by adding a new node. Driving follows all possible computation processes starting from an initial configuration ci and continues until every leaf of the process tree represents only ....

[Article contains additional citation context not shown here]

Turchin V. F., The concept of a supercompiler. In: ACM TOPLAS, 8(3): 292-325, 1986.

....f (v : vs) ws v : f vs ws) Termination safe extensions of deforestation [Chi93, Sor94a] use automatically precomputed annotations to tell where to abstract ( generalize=extract) so that enough folding takes place to ensure termination. Supercompilation is a powerful technique due to Turchin [Tur86] (continuing Soviet work from the early 1970 s) which can achieve effects of both deforestation and partial evaluation. Supercompilation performs driving: unfolding and propagation of information, and generalization: a form of abstraction which enables folding. The decision when to generalize is ....

V. F. Turchin. The Concept of a Supercompiler. In ACM TOPLAS. Vol.8, No.3, pp.292-325, 1986.

....Then the operation and efficiency of the method is demonstrated by means of examples. Finally we compare our work to related work in supercompilation and partial evaluation. 1 Introduction Supercompilation 1 is a program specialization technique originally developed by Valentin F. Turchin (e.g. [Tur86]) for a language called Refal . Supercompilation is composed of four steps: driving, generalization, folding and post unfolding. Whereas in the original supercompiler positive and negative information, i.e. equality and inequality of variables and values was propagated, we restrict propagation to ....

....source language programs, we couldn t achieve quite as good results. We expect, that binding time improvements in the action interpreter would improve the results. 4 e.g. Typical speed ups for normal Prolog programs range from 3 to 20 . Sah90] 4 Related Work Valentin F. Turchin s (e.g. [Tur86]) system was written in and for a functional language called Refal , which was first developed in 1968 and although being very innovative has never achieved great attention in the western world. In Turchin s supercompiler positive and negative information, i.e. equality and inequality of variables ....

V.F. Turchin. The Concept of a Supercompiler. ACM TOPLAS, 8(3), 1986.

....rules also allow us to factorize common computations in different branches of the SLDNF trees. In a sense this factorization provides an extension of the basic supercompilation techniques, where the program improvements are achieved by taking into consideration single computation paths only [7, 19]. The use of the clause subsumption rule is motivated by the desire of increasing efficiency by avoiding redundant computations. Head generalizations are used for making equal the heads of several clauses and thus they allow us to perform folding steps. The case split rule is the crucial rule for ....

V.F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8(3):292--325, 1986.

No context found.

) Turchin V., "The Concept of a Supercompiler," ACM Transactions on Programming Languages and Systems, 8, 3, pp. 292--325, July 1986.

No context found.

V. F. Turchin. The concept of a supercompiler. ACM TOPLAS, 8:292-325, 1986.

No context found.

) Turchin, V. F., "The Concept of a Supercompiler," ACM TOPLAS, 8, 3, pp. 292-

No context found.

Turchin, Valentin F. "The Concept of a Supercompiler". ACM TOPLAS 8,3 (July 1986),292-325.

No context found.

V.F. Turchin. The concept of a supercompiler. ACM TOPLAS 8(3):292--325 (1986).

No context found.

V. F. Turchin. The concept of a supercompiler. ACM Trans. Prog. Lang. Syst., 8(3):292325, July 1986.

No context found.

Valentin F. Turchin. The Concept of a Supercompiler. In ACM Transactions on Programming Languages and Systems. Vol. 8, No. 3, 1986.

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.