Ershov, A.P. (1982). Mixed Computation: Potential Applications and Problems for Study. Theoretical Computer Science 18 18, 41-67.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....performing those of p s calculations that depend only on s, and by generating code for those calculations that depend on the as yet unavailable input d. A partial evaluator thus performs a mixture of execution and code generation actions the reason Ershov called the process mixed computation [3], hence the generically used name mix for a partial evaluator (which we call spec) Its output is often called the residual program, the term indicating that it is comprised of operations that could not be performed during specialization. 4.4.1 An example in more detail For a simple but ....

A.P Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41-67, 1982.

....those of p s calculations that depend only on known static s, and by generating code for those calculations that depend on the as yet unavailable input d. A partial evaluator performs a mixture of execution and code generation actions; for this reason Ershov called the process mixed computation [3], and partial evaluators are sometimes named mix. Three main partial evaluation techniques are well known from program transformation [2] symbolic computation, unfolding function calls, and function name specialization. The specialization shown in Figure 3.3 uses the rst two techniques; the ....

A.P Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41-67, 1982.

....those of p s computations that depend only on s. Program p s is thus (potentially) more ecient than program p: it need not perform the computations that depend only on s. 1.1 Self application Self application means specializing the partial evaluator itself. This is also known as autoprojection [Ers82]. Let us insert mix for p, p for s, and s for d in the equation de ning a residual program: mix(p; s) mix p (s) where mix p = mix(mix; p) Specializing p with respect to s may thus be done by running mix p (s) instead of the (potentially) slower mix(p; s) Notice that mix p is a curried ....

Andrei P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18:41-67, 1982.

....should make it possible to combine already de ned strategies and also to dynamically generate new strategies. The need for higher order manipulations has already emerged both in partial evaluation, where the concepts of generating extension and metasystem transition play an important role [63, 78, 146], and in unfold fold program transformation where, for instance, suitable generalization strategies may be applied after analyzing the outcome of other strategies [117] A theoretical issue to be addressed is the capability of those rules and strategies to derive programs with certi ed levels of ....

A. P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18(1):4167, 1982.

....1. the Schemata Approach (one may refer, for instance, to [Partsch 90] for a 51 survey in the functional case, and to [Brough Hogger 91, Deville Burnay 89, Fuchs Fromherz 92, Marakakis Gallagher 94, Seki Furukawa 87] in the logic case) 2. the Partial Evaluation (or Mixed Computation) technique [Ershov 82, Jones et al. 93] and 3. the Finite Differencing technique [Paige Koenig 82] and compare them with the strategies we have considered above. For other methods, such as: i) combinatory techniques [Turner 79] ii) supercombinator methods [Hughes 82] iii) local recursions [Bird 84a] iv) ....

Ershov, A. P.: Mixed Computation: Potential Applications and Problems for Study. Theoretical Computer Science 18 (1982) 41--67

....gives a very extensive and technical treatment of concepts in programming languages, the basics of PE, several PE systems ( mix, Logimix for Prolog, Similix, C Mix) aspects of PE in practice, plus more advanced topics. A book on program flow analysis is [27] Two very useful review papers are [19, 10]. 19] by Neil Jones, entitled Mix Ten Years Later is probably the best starting point for someone who wants to read about PE. With many problems for study and many critical comments, it was certainly my most useful reference. Ershov s paper Mixed Computation: Potential Applications and ....

....Jones, entitled Mix Ten Years Later is probably the best starting point for someone who wants to read about PE. With many problems for study and many critical comments, it was certainly my most useful reference. Ershov s paper Mixed Computation: Potential Applications and Problems for Study [10] is full of abstract understanding of the underlying issues, and apart from that, is a good read, with Ershov s Russianness coming through in every way. 4 Partial Evaluation and Imperative Languages Until fairly recently, PE has mainly been studied and implemented for functional or logic ....

A.P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....merits of equational reasoning for programs have been widely touted [2, 26, 35, 24, 27] results characterizing the power of formal systems required for such reasoning appear to be few and far between. Similarly, while partial evaluation has often been advocated as a means for optimizing programs [14, 15, 10, 7, 38], it is unusual to find a precise characterization of the transformational capabilities that a particular partial evaluator implements. In the sequel, we systematically derive the complete PIM logic as the culmination of a sequence of increasingly powerful equational systems starting from a ....

ERSHOV, A. Mixed computation: Potential applications and problems for study. Theoretical Computer Science 18 (1982), 41--67.

....of p s computations that depend only on s. Program p s is thus (potentially) more efficient than program p: it need not perform the computations that depend only on s. 1.1 Self application Self application means specializing the partial evaluator itself. This is also known as autoprojection [Ers82]. Let us insert mix for p, p for s, and s for d in the equation defining a residual program: mix(p; s) mix p (s) where mix p = mix(mix; p) Specializing p with respect to s may thus be done by running mix p (s) instead of the (potentially) slower mix(p; s) Notice that mix p is a curried ....

Andrei P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....basis of specific training examples. For some considerable time, the functional programmingcommunity, and more recently the logic programming community, has been discussing a technique called partial evaluation (PE) as a program optimisation method (see [Futamura, 1971] for an early paper on PE, [Ershov, 1982] for PE in functional programming, and [Komorowski, 1982] Venken, 1984] and [Takeuchi Furukawa, 1986] for PE in logic programming) This paper shows that, in the context of logic programming, the two techniques, although developed for different purposes, do in fact consist of the same ....

A.P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....Arne J. Glenstrup and Neil D. Jones, DIKU, University of Copenhagen e mail: fpanic;neilg diku.dk Abstract. A partial evaluator, given a program and a known static part of its input data, outputs a residual program in which computations depending only on the static data have been precomputed [3]. The ideal is a black box which discovers and performs nontrivial static computations whenever possible, and never fails to terminate. Practical partial evaluators fall short of this goal: they sometimes loop (typical of functional programing partial evaluation) or terminate but are ....

....only do simple operations: unfolding, symbolic computation, and definition of new specialised variants of p s functions. The specialiser s job is to perform certain of p s operations or commands possible using only static inputs, and to suspend, i.e. to generate code for, the remaining ones [3]. The key to termination of the specialiser is to recognise when static parameters can take only finitely many different values during specialisation, thus being of bounded static variation or BSV, formally defined later. When the specialiser encounters a conditional construct with dynamic test, ....

A.P. Ershov, `Mixed computation: potential applications and problems for study.' Theoretical Computer Science, 18:41--67, 1982.

....using first order rewriting. This is achieved by using partial evaluation to transform a class of higher order programs into first order ones. Partial evaluation aims at specializing a program with respect to part of its input (static parts) This process produces a specialized (residual) program [8]. This specialized program when applied to the remaining input value parts (dynamic parts) yields the same result as the original program applied to a complete input. In this paper we are using Schism [6] a partial evaluator for pure functional programs. Our goal is to use partial evaluation to ....

A. Ershov. Mixed computation: potential applications and problem for study. Theorical Computer Science, Vol. 18, pages 41-67, 1982.

....enabling a better control [1] We use off line techniques for the partial evaluation of Fortran. Constant folding is a familiar compiler optimization and is clearly an instance of partial evaluation. Partial evaluation encompasses a number of traditional optimization techniques, as explained in [16]. Example 1. Consider a program power computing the function x to the nth. The source program in Fortran is shown to the left, the specialized version to the right (assuming that n is static (9) and x is dynamic) c Compute x to the n th c Specialized with respect to n=9 INTEGER n, x, power ....

....than the original source program (due to the polyvariant specialization) In our experience the binding time analysis usually requires the smallest portion of the total run time. 6 Related Work Ershov and his group were the first who investigated imperative languages and mixed computation [15,16,11]. Pagan [24] describes several manual methods similar to the partial evaluation of imperative languages and studied the specialization of general parsers [23] The examples are taken from his works. The partial evaluator presented in this paper automates several of these techniques. Meyer ....

Ershov A. P., Mixed computation: potential applications and problems for study. In: Theoretical Computer Science, 18: 41-67, 1982.

....using first order rewriting. This is achieved by using partial evaluation to transform a class of higher order programs into first order ones. Partial evaluation aims at specializing a program with respect to part of its input (static parts) This process produces a specialized (residual) program [8]. This specialized program when applied to the remaining input value parts (dynamic parts) yields the same result as the original program applied to a complete input. In this paper we are using Schism [6] a partial evaluator for pure functional programs. Our goal is to use partial evaluation to ....

A. Ershov. Mixed computation: potential applications and problem for study. Theorical Computer Science, Vol. 18, pages 41-67, 1982.

....the performance of the continuous compilation model. In Chapter 7 we give some concluding remarks and discuss future work. 7 Chapter 2 Related Work 2. 1 Interpreters and Compilers The idea of combining interpreted and native code text could be traced back to early work by Ershov and others [2], and continues to this day, currently in the active field of partial evaluation. For languages such as C, which have long been implemented primarily by compilation to native code (an exception is the si system [4] interpreters are experiencing somewhat of a comeback. For one explanation, ....

A.P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....mentioned in this paper, because as we already said, these correspondences can be considered as common knowledge of the people working in the field. Let us simply mention among some other similar results, the following ones: i) the unfold fold view of the mixed computation technique described in [16], ii) the equivalence of driving in supercompilation and partial deduction shown in [25] for a particular class of programs, and iii) the straightforward way of using the unfold fold transformation technique to simulate partial deduction [44] We now present this simulation in a simple example. ....

A. P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18(1):41--67, 1982.

.... E mail: neil diku.dk 1 Introduction Partial evaluation has been the subject of rapidly increasing activity over the past decade since it provides a unifying paradigm for a broad spectrum of work in program optimization, compiling, interpretation and the generation of automatic program generators [7,14,25]. It is a program optimization technique, perhaps better called program specialization, closely related to but different from J rring and Scherlis staging transformations [27] It emphasizes, in comparison with [11,27] and other program transformation work, full automation and the generation of ....

....because the program s control is completely determined by n. If on the other hand x = 5 but n is unknown, specialization gives no significant speedup. A partial evaluator performs a mixture of execution and code generation actions surely why Ershov called the process mixed computation [14], hence the name mix. An Equational Description Programs are both input to and output from other programs. We will discuss several languages and so assume given a fixed set D of first order data values including all program texts. A suitable choice of D is the set of Lisp s list data as ....

[Article contains additional citation context not shown here]

A.P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....respect to some partially specified information using symbolic manipulations and program transformations. The specialized program should preserve the semantics of the original program while (hopefully) being more efficient. Ershov characterized these ideas in a general scheme of mixed computation [13]. Though slightly more involved, his definition subsumes the definition given by Jones et al. in the reading [A1] by capturing more general specification and use of input information: Definition 1 Let L = D; P ; V ) be an algorithmic language, where D = fdg is a domain of values, P = fpg is a ....

....compilers into multiple passes [17] or elaborate loop and vector code manipulation in powerful modern compilers [23] are usually not implied by partial evaluation since they seem to require some external insight about the program beyond the interpretive flow of computation. However, Ershov [13] envisioned mixed computation as part of a more general program manipulation system with just a few basic transformations. In this broader scope, mixed computation can be viewed as simply any set of powerful program transformations satisfying definition 1, that make good use of the available ....

A.P. Ershov. Mixed Computation: Potential Applications and Problems for Study. Theoretical Computer Science, 18:41--67, 1982.

....or space w.r.t. the initial programs, and (iii) Automation: the process of program derivation should be supported by suitable automatic tools. Some similarities between partial evaluation and unfold fold program transformation have been recognized and formalized during the last two decades (see [Ershov 1982, page 59] Jones et al. 1993, page 347] Pettorossi and Proietti 1994, page 308] In particular, in the case of functional and logic programming, the basic program manipulations performed by partial evaluation can be viewed as unfold fold transformation steps with the following restricted ....

....4 Delta Alberto Pettorossi and Maurizio Proietti fined strategies and also to dynamically generate new strategies. The need for higher order manipulations has already emerged both in partial evaluation, where the concepts of generating extension and metasystem transition play an important role [Ershov 1982; Gluck 1996; Turchin 1980] and in unfold fold program transformation where, for instance, suitable generalization strategies may be applied after analyzing the outcome of other strategies [Pettorossi and Proietti 1994] A theoretical issue to be addressed is the completeness of various sets of ....

Ershov, A. P. 1982. Mixed computation: Potential applications and problems for study.

....of p s computations that only depend on s. Program p s is thus (potentially) more efficient than program p: it need not perform the computations that depend only on s. 1.1 Self Application Self application means specializing the partial evaluator itself. This is also known as autoprojection [18]. Let us substitute mix for p, p for s, and s for d in the equation defining a residual program: mix(p; s) mix p (s) where mix p = mix(mix; p) Specializing p with respect to s may thus be achieved by running mix p (s) instead of the (potentially) slower mix(p; s) We may even go one step ....

Andrei P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

.... the program (which accepts the static parameters and computes the residual program) The Futamura projections even lead to the automatic generation of a binding time polyvariant compiler generator (or cogen a generator of generating extensions) at the (rather low) cost of writing the interpreter [13, 29, 11, 12]. The construction of a binding time polyvariant cogen is new. The following section is an introduction to the interpretive approach and its application to the polyvariant expansion problem. The next section defines the language of the subject programs. Section 3 defines a bindingtime domain and ....

.... Moreover, mapping an arbitrary b to the least b 0 in the restricted lattice can be regarded as a widening operator [8, 9, 10] The idea of using self application to obtain stand alone generating extensions came from Futamura [13] Turchin and Ershov later extended the idea to compiler generators [29, 11, 12]. 8 Conclusion We have implemented polyvariant expansion for higher order functional programs using the interpretive approach. Our method uses a fine grained abstract binding time domain. It fully automates Bulyonkov s method and extends it to higher order programs, and we have implemented it. In ....

A. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

.... the program (which accepts the static parameters and computes the residual program) The Futamura projections even lead to the automatic generation of a binding time polyvariant compiler generator (or cogen a generator of generating extensions) at the (rather low) cost of writing the interpreter [13, 29, 11, 12]. The construction of a binding time polyvariant cogen is new. The following section is an introduction to the interpretive approach and its application to the polyvariant expansion problem. The next section defines the language of the subject programs. Section 3 defines a bindingtime domain and ....

.... Moreover, mapping an arbitrary b to the least b 0 in the restricted lattice can be regarded as a widening operator [8, 9, 10] The idea of using self application to obtain stand alone generating extensions came from Futamura [13] Turchin and Ershov later extended the idea to compiler generators [29, 11, 12]. 8 Conclusion We have implemented polyvariant expansion for higher order functional programs using the interpretive approach. Our method uses a fine grained abstract binding time domain. It fully automates Bulyonkov s method and extends it to higher order programs, and we have implemented it. In ....

A. Ershov. Mixed computation: Potential applications and problems for study. In Mathematical Logic Methods in AI Problems and Systematic Programming, Part 1, pages 26--55. Vil'nyus, USSR, 1980. (In Russian).

....using first order rewriting. This is achieved by using partial evaluation to transform a class of higher order programs into first order ones. Partial evaluation aims at specializing a program with respect to part of its input (static parts) This process produces a specialized (residual) program [8]. This specialized program when applied to the remaining input value parts (dynamic parts) yields the same result as the original program applied to a complete input. In this paper we are using Schism [6] a partial evaluator for pure functional programs. Our goal is to use partial evaluation to ....

A. Ershov. Mixed computation: potential applications and problem for study. Theoritical Computer Science, Vol. 18, pages 41-67, 1982.

....of glacialness (Z axis) by stage level (X axis) for PERFECT suite (arrays) run time to compile time [13] This is very similar to partial evaluation. In fact, Ershov shows that what is traditionally called partial evaluation is a subset of what Jorring and Scherlis call staging transformations [6]. One of our results is that it is useful to separate the transformation rules from the decision of where to apply them. We call the combination of the where analysis and the what to do rule set, a staging transformation system. Early work consists only of the rules, and we add the supporting ....

A. Ershov. Mixed computation: The potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

....This was the background for the 1987 Workshop on Partial Evaluation and Mixed Computation [19, 39] Subsequent proceedings on partial evaluation may be found in [2, 3, 4, 5, 32, 88] 9. 2 Partial evaluators Imperative languages: Early papers on partial evaluation for imperative languages include [34, 36, 37]. Bulyonkov and Ershov reported a self applicable partial evaluator for a flow chart language [25] so did Gomard and Jones [50] Gluck et al. created a (non self applicable) specializer for numeral algorithms in Fortran [11, 47] Andersen [6, 8, 9] developed two systems for specialization of C ....

A.P. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41--67, 1982.

No context found.

Ershov, A.P. (1982). Mixed Computation: Potential Applications and Problems for Study. Theoretical Computer Science 18 18, 41-67.

No context found.

A.P. Ershov, `Mixed computation: potential applications and problems for study.' Theoretical Computer Science, 18:41--67, 1982.

No context found.

A. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41-67, 1982.

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.