N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206:81125, 1998.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

....during the construction of P 0 ; Pn ; 2) the head predicate of 1 ; m does not depend on itself in Pn . Then lm(P 0 [ Defs n ; D) lm(Pn ; D) The rules listed above are an extension of the rules for transforming logic programs and constraint logic programs presented in [2, 6, 8, 14, 23, 25]. In particular, the folding rules considered in [2, 6, 8, 25] allow us to fold only one clause at a time, while by using our rule R3 we can fold m ( 1) clauses simultaneously. Our rule R3 is an adaptation to the case of CLP programs of the folding rules considered in [14, 23] Our clause ....

....of 1 ; m does not depend on itself in Pn . Then lm(P 0 [ Defs n ; D) lm(Pn ; D) The rules listed above are an extension of the rules for transforming logic programs and constraint logic programs presented in [2, 6, 8, 14, 23, 25] In particular, the folding rules considered in [2, 6, 8, 25] allow us to fold only one clause at a time, while by using our rule R3 we can fold m ( 1) clauses simultaneously. Our rule R3 is an adaptation to the case of CLP programs of the folding rules considered in [14, 23] Our clause splitting rule R7 generalizes to constraint logic programs the case ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theor. Comp. Sci., 206:81-125, 1998.

....us to separate the issue of deriving a correct program from that of deriving an efficient program. The program transformation methodology has been developed in a number of different language paradigms, such as, functional programming [13] logic programming [80] and constraint logic programming [9, 25, 51]. C A I J 1. We will be concerned with the development of automatic techniques for the transformation of programs written in a constraint logic language. Constraint Logic Programming [38] extends the usual logic programming framework [49] by allowing constraints over a generic domain Z) ....

....transformation approach based on rules and strategies. We will present a set of transformation rules and fully automatic strategies for the specialization of constraint logic programs over a generic constraint domain Z) In particular, we will adapt some of the unfold fold rules considered in [9, 25, 51] and we will introduce new transformation rules which allow us: i) to perform program optimizations which cannot be done by using the transformation rules already presented in the literature, and (ii) to specialize constraint logic programs with locally stratified negation (see Section 3.1) ....

[Article contains additional citation context not shown here]

BENSAOU, }X., AND GUESSARIAN, I. Transforming constraint logic programs. Theoretical Computer Science 206 (1998), 81-125.

....unfolded during the construction of P0 ; Pn ; or (2) the head predicate of 1 ; m does not depend on itself in Pn . Then lm(P0 [ Defsn ; D) lm(Pn ; D) The rules listed above are an extension of the rules for transforming logic programs and constraint logic programs presented in [2], 6] 7] 12] 19] 21] In particular, the folding rules considered in [2] 6] 7] 21] allow us to fold only one clause at a time, while by using our rule R3 we can fold m ( 1) clauses simultaneously. Our rule R3 is an adaptation to the case of CLP programs of the folding rules ....

....of 1 ; m does not depend on itself in Pn . Then lm(P0 [ Defsn ; D) lm(Pn ; D) The rules listed above are an extension of the rules for transforming logic programs and constraint logic programs presented in [2] 6] 7] 12] 19] 21] In particular, the folding rules considered in [2], 6] 7] 21] allow us to fold only one clause at a time, while by using our rule R3 we can fold m ( 1) clauses simultaneously. Our rule R3 is an adaptation to the case of CLP programs of the folding rules considered in [12] 19] Our clause splitting rule R7 generalizes to constraint logic ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theor. Comp. Sci., 206:81-125, 1998.

....obtained from program P k by applying one of the transformation rules listed below. These rules are variants, tailored to the veri cation technique presented in this paper, of the rules considered in the literature for transforming logic programs and constraint logic programs (see, in particular, [5, 14, 17, 28, 37, 41]) R1. Constrained Atomic De nition. We introduce the clause, called a de nition, newp(X 1 ; Xm ) c; A where: i) newp is a predicate symbol not occurring in P 0 ; P k , ii) vars(A) fX 1 ; Xm g, iii) FV (c) fX 1 ; Xm g, and (iv) the predicate of A ....

....the transformation rules considered in this section with other sets of transformation rules which have been presented in the literature. The rules listed above are an extension to locally strati ed CLP programs of the rules presented in [17] for the case of de nite CLP programs. The rules of [5, 14] are extensions of Tamaki Sato s unfold fold rules [41] to the case of de nite CLP programs. If we consider de nite CLP programs only, the de nition and folding rules of [5, 14] are more general than ours, because they allow the body of a de nition to be a nonatomic constrained goal. However, ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian, \Transforming constraint logic programs," Theoretical Computer Science, vol. 206, pp. 81-125, 1998. 34.

....of the partial evaluation of CLP programs by means of transformation rules and strategies, similarly to what has been done in [17] for the case of partial evaluation of definite logic programs. To this end, we consider variants of the unfolding and folding rules for CLP programs presented in [1,4,13]. In Section 3 we present an extra rule, called contextual constraint replacement, and an extra strategy, called context propagation strategy, which allow us to specialize a set of clauses defining a predicate, say p, with respect to a constraint when this constraint is known to hold for every ....

....programs w.r.t. properties of their context of use [3,19] 2 Rules and Strategies for Partial Evaluation of CLP In this section we introduce a set of transformation rules and a strategy for partial evaluation of CLP programs over a domain D. Our rules differ from those studied in previous papers [1,4,13] in that they are tailored to partial evaluation. Throughout the paper we will use the following conventions. FV ( denotes the set of the free variables of the formula . We will write 8X 1 : Xm also as 8X , where X denotes the set fX 1 ; Xm g. Analogously for 9, instead of 8. ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, (206):81--125, 1998.

....of constraint logic programs based on transformation rules and strategies. In particular, I will consider the transformation methodology based on unfold fold rules, taking advantage of the results obtained in functional programming [3] logic programming [15] and constraint logic programming [1, 4, 12]. The process of deriving programs by transformation can be formalized as a sequence P 0 ; Pn of programs where, for k = 0; n 1, program P k 1 is obtained from program P k by applying a semantics preserving transformation rule. Thus, if the initial program P 0 is correct w.r.t. a ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, (206):81125, 1998.

....and proved their correctness w.r.t. the least Herbrand model semantics. Since then, several researchers have investigated various aspects of the unfold fold transformation approach. They also considered its extension to deal with negation [6,29,48,64,70,71] disjunctive programs [30] constraints [4,22], and concurrency [23] In this chapter we have essentially followed the approach of Tamaki and Sato where the correctness of the transformations is ensured by conditions on the sequence of the transformation rules which are applied during program derivation [74] The main novelty w.r.t. other ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206:81125, 1998.

.... answers, nite failure, pure Prolog, and left termination (see [14, 39, 77, 92, 100, 105, 123] The transformational approach has also been considered in the case of various extensions of de nite logic programs, such as logic programs with negation (see Section 5) constraint logic programs [8, 64, 106], and concurrent constraint programs [65, 148] General methods for proving the correctness of transformation rules are studied in [133] for the case of higher order functional languages, and [126] for programming languages whose semantics is speci ed by inductive de nitions, like that of Section ....

....in those elds and are of relevance to the transformation methodology and its applications. Some of these techniques have been developed also in the area of functional programming, and they have been partially extended to the case of concurrent logic programs [148] and constraint logic programs [8, 64, 83, 106]. Let us begin by considering some program analysis techniques by which the programmer can investigate various program properties. Those properties may then be used for improving program e ciency by applying transformation methods. Program properties which are often useful for program ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. In 11th Symp. on Theoretical Aspects of Computer Science, STACS '94, Lecture Notes in Computer Science 775, pages 3346. Springer-Verlag, 1994.

....of the partial evaluation of CLP programs by means of transformation rules and strategies, similarly to what has been done in [16] for the case of partial evaluation of de nite logic programs. To this end, we consider variants of the unfolding and folding rules for CLP programs presented in [1, 4, 13]. In Section 3 we present an extra rule, called contextual constraint replacement, and an extra strategy, called context propagation strategy, which allow us to specialize a set of clauses de ning a predicate, say p, with respect to a constraint when this is known to hold for all calls of p. As ....

....5 we present the related work and some concluding remarks. 2 Rules and Strategies for Partial Evaluation of CLP We will introduce here a set of transformation rules and a strategy for partial evaluation of CLP programs over the domain D. Our rules di er from those studied in previous papers [1, 4, 13] in that they are tailored to partial evaluation. Throughout the paper we will use the following conventions. FV ( denotes the set of the free variables of the formula . We will write 8X 1 : Xm also as 8X , where X denotes the set fX 1 ; Xm g. Analogously for 9, instead of 8. ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206:81125, 1998.

.... specialization and optimization [Kom82] Tamaki and Sato in [TS84] proposed a general framework for the unfold fold transformation of logic programs, which has remained in the years the main historical reference of the eld, and has recently been extended to constraint logic programming (CLP) in [Mah93, EG96, BG98] (for an overview of the subject, see the survey by Pettorossi and Proietti [PP94] As shown by a number of z The work of the third author was partially supported by the MURST 40 project: Tecniche speciali per la veri ca, l analisi, la sintesi e la trasformazione di programmi . 1 ....

.... instance of A, i.e. when d has the form H C[A ] in this case the folding operation is applicable only if satis es speci c conditions described in [TS84] for logic programs and in [EG96] for CLP) This extended operation would actually correspond to the (most) usual de nition of folding as in [TS84, EG96, BG98]. In our system such an extended operation is formally not needed, as it can be obtained by combining together the folding operation with the tell introduction. 12 In fact, assume that we would like to fold the de nition d : H C[A ] 2 D by using the de nition f : B A 2 D 0 In the rst ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206(1-2):81-125, 1998. 30

.... which focus exclusively on the manipulation of the constraint for compile time [18, 19] and for low level local optimization [15] On the other hand there are techniques such as the unfold fold transformation systems, which were developed initially for Logic Programs [28] and then applied to CLP [16, 1, 8] and to ccp in [9] These ones focus primarily on the declarative side of the program. The Replacement is a program transformation technique exible enough to encompass both the above kinds of optimization: it can be pro tably used to manipulate both the constraint and the declarative side of a ....

....the above kinds of optimization: it can be pro tably used to manipulate both the constraint and the declarative side of a program. In fact the replacement operation, which was introduced in the eld of Logic Programming by Tamaki and Sato [28] and later further developed and applied to CLP in [16, 1, 7], syntactically consists in replacing an agent in the body of a program de nition by another one. It is therefore a very general operation and it is able to mimic many other transformations, such as thinning, fattening [3] and folding. In the logic programming area, a lot of research [4, 5, 1, 6, ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206(1-2):81-125, 1998.

....rules and strategies. This approach has the advantage of separating the issue of proving the correctness of program specialization from that of guaranteeing the eciency of the specialized programs. We consider adaptations of the usual unfolding and folding rules [3, 19] and variants of these rules [1, 5, 14] for the case of CLP programs. We also consider an extra rule, called contextual constraint replacement, which allows us to specialize a set of clauses which de ne a predicate, say p, with respect to a constraint which is known to hold for the calls of p. Indeed, the example of program ....

....clause) In Section 3 we present our transformation rules and we give some applicability conditions which ensure that they preserve the least D model of any CLP program when used in the speci ed context. These applicability conditions are not implied by those for the various rules considered in [1, 5, 14], and indeed we show that when the folding rule of [1, 5] is combined with our contextual constraint replacement rule, then correctness is not preserved. The folding rule considered in [14] is always correct, but at the price of strong restrictions. In Section 4 we outline a general strategy ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, (206):81-125, 1998.

....of programs. Finally, we would like to mention that the transformation and specialization techniques considered in this chapter have been partially extended to the case of concurrent logic programs [ Ueda and Furukawa, 1988 ] and constraint logic programs [ Hickey and Smith, 1991; Maher, 1993; Bensaou and Guessarian, 1994; Etalle and Gabbrielli, 1996 ] Conclusions We have looked at the theoretical foundations of the so called rules strategies approach to logic program transformation. We have established a unified framework for presenting and comparing the various rules which have been proposed in the ....

N. Bensaou and I. Guessarian. Transforming constraint logic programs. In 11th Symp. on Theoretical Aspects of Computer Science, STACS '94, Lecture Notes in Computer Science 775, pages 33--46. Springer-Verlag, 1994.

....the transformations we performed satisfied O1: O4. Therefore Theorem 4.3 guarantees that the final program will behave exactly as the initial one, even in this modular setting. 2 5 Conclusions The works most closely related to this paper are Maher s [15] and the one of Bensaou and Guessarian [1]. Maher considers several transformations for deductive databases modules with constraints (allowing negation in the bodies of the clauses) and refers to the perfect model semantics. However the folding operation proposed in [15] is quite restrictive since it lacks the possibility of introducing ....

....module composition is more general than the one considered in [15] since the latter assumes each predicate is defined within a single module and does not allow mutual recursion among modules. An extension of the Tamaki Sato method to CLP programs has also been proposed by Bensaou and Guessarian [1], yet there are some substantial differences between [1] and our proposal. Firstly, since in an Unfold Fold transformation sequence we allow more operations, we obtain a more powerful system. For instance, the transformation performed in Example 3.2 is not feasible with the tools of [1] 5 . ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming Constraint Logic Programs. In F. Turini, editor, Proc. Fourth Workshop on Logic Program Synthesis and Transformation, 1994.

....the various semantics available for normal programs. For instance, the new system was then adapted by Sato to full first order programs [33] Related work has been done by Maher [29] Gardner and Shepherdson [16] Aravidan and Dung [2] Seki [35] Bossi and Cocco [5] and Bensaou and Guessarian [3]. Among these papers only [29] and [3] treated the case of Constrain Logic Programming. We defer to section 7 a comparison of these approaches with ours. All the (unfold fold) transformation systems proposed so far for logic programming and for CLP, with the only exception of [29] assume that the ....

....normal programs. For instance, the new system was then adapted by Sato to full first order programs [33] Related work has been done by Maher [29] Gardner and Shepherdson [16] Aravidan and Dung [2] Seki [35] Bossi and Cocco [5] and Bensaou and Guessarian [3] Among these papers only [29] and [3] treated the case of Constrain Logic Programming. We defer to section 7 a comparison of these approaches with ours. All the (unfold fold) transformation systems proposed so far for logic programming and for CLP, with the only exception of [29] assume that the entire program is available at the ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming Constraint Logic Programs. In F. Turini, editor, Proc. Fourth Workshop on Logic Program Synthesis and Transformation, 1994.

.... compiled into imperative statements) 23] Compile time optimizations based on static analysis have also been investigated [29] On the other hand there are techniques such as the unfold fold transformation systems, which were developed initially for Logic Programs [38] and then applied to CLP [28, 3, 13]. These ones focus primarily on the declarative side of the program. Replacement is a program transformation technique flexible enough to encompass both the above kind of optimization: it can be profitably used to manipulate both the constraint and the declarative side of a CLP program. In fact ....

....to encompass both the above kind of optimization: it can be profitably used to manipulate both the constraint and the declarative side of a CLP program. In fact the replacement operation, which was introduced in the field of Logic Programming by Tamaki and Sato [38] and later applied to CLP in [28, 3], syntactically consists in replacing a conjunction of atoms in the body of a program clause by another conjunction. It is therefore a very general operation and it is able to mimic many other transformations, such as thinning, fattening [5] and folding (see [32] for a survey on transformation ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming Constraint Logic Programs. In F. Turini, editor, Proc. Fourth Workshop on Logic Program Synthesis and Transformation, 1994.

.... specialization and optimization [11] Tamaki and Sato in [22] proposed a general framework for the unfold fold transformation of logic programs, which has remained in the years the main historical reference of the field, and has recently been extended to constraint logic programming (CLP) in [1, 5, 13] (for an overview of the subject, see the survey by Pettorossi and Proietti [16] As shown by a number of applications, these techniques provide powerful methodology for the development and optimization of large programs, and can be regarded as the basic transformations techniques, which might ....

N. Bensaou and I. Guessarian. Transforming Constraint Logic Programs. In F. Turini, editor, Proc. Fourth Workshop on Logic Program Synthesis and Transformation, 1994.

....[1] C. Aravindan and P. Dung. Partial deduction of logic programs wrt well founded semantics. New Generation Computing, 13(1) 45 74, 1994. 2] K. Benkerimi and J. C. Shepherdson. Partial deduction of updateable definite logic programs. The Journal of Logic Programming, 18(1) 1 27, January 1994. [3] A. Bossi and S. Etalle. Transforming acyclic programs. ACM Transactions on Programming Languages and Systems (TOPLAS) 16(4) 1081 1096, July 1994. 4] M. Codish, M. Falaschi, and K. Marriott. Suspension analyses for concurrent logic programs. ACM Transactions on Programming Languages and Systems ....

....pages 43 60. Springer Verlag, 1994. 2] M. Alpuente, M. Falaschi, M. Ramis, and G. Vidal. A Compositional Semantics for Conditional Term Rewriting Systems. In H. Bal, editor, Proc. 1994 Int l Conf. on Computer Languages ICCL 94, Toulouse, France, pages 171 182. IEEE Computer Society Press, 1994. [3] M. Alpuente, M. Falaschi, and G. Vidal. Compositional Analysis for Equational Horn Programs. In G. Levi and M. Rodr iguez Artalejo, editors, Proceedings of the Fourth International Conference on Algebraic and Logic Programming, Lecture Notes in Computer Science 850, pages 77 94, Madrid, Spain, ....

I. Bensaou, N. Guessarian. Transforming constraint logic programs. In Logic Program Synthesis and Transformation. Proceedings of LOPSTR'94, Pisa, Italy, 1994. To be published.

....[1] C. Aravindan and P. Dung. Partial deduction of logic programs wrt well founded semantics. New Generation Computing, 13(1) 45 74, 1994. 2] K. Benkerimi and J. C. Shepherdson. Partial deduction of updateable definite logic programs. The Journal of Logic Programming, 18(1) 1 27, January 1994. [3] A. Bossi and S. Etalle. Transforming acyclic programs. ACM Transactions on Programming Languages and Systems (TOPLAS) 16(4) 1081 1096, July 1994. 4] M. Codish, M. Falaschi, and K. Marriott. Suspension analyses for concurrent logic programs. ACM Transactions on Programming Languages and Systems ....

....pages 43 60. Springer Verlag, 1994. 2] M. Alpuente, M. Falaschi, M. Ramis, and G. Vidal. A Compositional Semantics for Conditional Term Rewriting Systems. In H. Bal, editor, Proc. 1994 Int l Conf. on Computer Languages ICCL 94, Toulouse, France, pages 171 182. IEEE Computer Society Press, 1994. [3] M. Alpuente, M. Falaschi, and G. Vidal. Compositional Analysis for Equational Horn Programs. In G. Levi and M. Rodr iguez Artalejo, editors, Proceedings of the Fourth International Conference on Algebraic and Logic Programming, Lecture Notes in Computer Science 850, pages 77 94, Madrid, Spain, ....

I. Bensaou, N. Guessarian. Transforming constraint logic programs. In Logic Program Synthesis and Transformation. Proceedings of LOPSTR'94, Pisa, Italy, 1994. To be published.

.... imperative statements) JMM91] Compile time optimizations based on static analysis have also been investigated [MS90] On the other hand, there are techniques such as the unfold fold transformation systems, which were developed initially for logic programs [TS84] and then applied to CLP [Mah93, BG94, EG95a] These focus primarily on the declarative side of the program. Replacement is a program transformation technique flexible enough to encompass both of the above types of optimizations: it can be profitably used to manipulate the constraint and the declarative sides of a CLP program. In ....

....both of the above types of optimizations: it can be profitably used to manipulate the constraint and the declarative sides of a CLP program. In fact, the replacement operation, which was introduced in the field of logic programming by Tamaki and Sato [TS84] and later applied to CLP [Mah93, BG94] syntactically consists in replacing a conjunction of atoms in the body of a program clause by another conjunction. It is therefore a very general operation, and it can mimic many other transformations, such as thinning, fattening [BC93] and folding (see [PP94b] for a survey on transformation ....

[Article contains additional citation context not shown here]

N. Bensaou and I. Guessarian. Transforming constraint logic programs. In F. Turini, editor, Proceedings of The Fourth Workshop on Logic Program Synthesis and Transformation, Berlin, 1994. Springer-Verlag.

No context found.

N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206:81125, 1998.

No context found.

N. Bensaou and I. Guessarian. Transforming Constraint Logic Programs. In F. Turini, editor, Proc. Fourth Workshop on Logic Program Synthesis and Transformation, 1994.

No context found.

I. Bensaou, N. Guessarian. Transforming Constraint Logic Programs. In Logic Program Synthesis and Transformation. Proceedings of LOPSTR'94, Pisa, Italy, 1994.

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.