Rules and Strategies for Contextual Specialization of Constraint Logic Programs

We address the problem of specializing a constraint logic program w.r.t. a constrained atom which specifies the context of use of the program. We follow an approach based on transformation rules and strategies. We introduce a novel transformation rule, called contextual constraint replacement, to be combined with variants of the traditional unfolding and folding rules. We present a general Partial Evaluation Strategy for automating the application of these rules, and two additional strategies: the Context Propagation Strategy which is instrumental for the application of our contextual constraint replacement rule, and the Invariant Promotion Strategy for taking advantage of invariance properties of the computation. We show through some examples the power of our method and we compare it with existing methods for partial deduction of constraint logic programs based on extensions of Lloyd and Shepherdson's approach.     

Deriving very efficient algorithms for evaluating linear recurrence relations using the program transformation technique

Summary Using the program transformation technique we derive some algorithms for evaluating linear recurrence relations in logarithmic time. The particular case of the Fibonacci function is first considered and a comparison with the conventional matrix exponentiation algorithm is made. This comparison allows us also to contrast the transformation technique and the stepwise refinement technique underlining some interesting features of the former one. Through the examples given we also explain why those features are interesting for a useful and reliable program construction methodology.     

Editorial

Higher-Order and Symbolic Computation -     

Constraint-based correctness proofs for logic program transformations

Many approaches proposed in the literature for proving the correctness of unfold/fold transformations of logic programs make use of measures associated with program clauses. When from a program P ₁ we derive a program P ₂ by applying a sequence of transformations, suitable conditions on the measures of the clauses in P ₂ guarantee that the transformation of P ₁ into P ₂ is correct, that is, P ₁ and P ₂ have the same least Herbrand model. In the approaches proposed so far, clause measures are fixed in advance, independently of the transformations to be proved correct. In this paper we propose a method for the automatic generation of clause measures which, instead, takes into account the particular program transformation at hand. During the application of a sequence of transformations we construct a system of linear equalities and inequalities over nonnegative integers whose unknowns are the clause measures to be found, and the correctness of the transformation is guaranteed by the satisfiability of that system. Through some examples we show that our method is more powerful and practical than other methods proposed in the literature. In particular, we are able to establish in a fully automatic way the correctness of program transformations which, by using other methods, are proved correct at the expense of fixing in advance sophisticated clause measures.     

Higher-order communications for concurrent programming

In Pettorossi and Skowron (1983) a recursive-equations language is introduced. Its operational semantics is specified by means of computing agents which communicate and exchange messages. Those communications are, so to speak, zero-order, in the sense that the exchanged messages are values of a data structure, possibly defined by the programmer.

In this paper we extend that approach and we consider also ‘higher-order’ communications by allowing the exchange of agents behaviours, i.e. sets of computations, among computing agents. This extension leads to a new programming methodology which makes use of proofs of computing agents behaviours and their related strategies.     

The List Introduction Strategy for the Derivation of Logic Programs

We present a new program transformation strategy based on the introduction of lists. This strategy is an extension of the tupling strategy which is based on the introduction of tuples of fixed length. The list introduction strategy overcomes some of the limitations of the tupling strategy and, in particular, it makes it possible to transform general recursive programs into linear recursive ones also in cases when this transformation cannot be performed by the tupling strategy. The linear recursive programs we derive by applying the list introduction strategy have in most cases very good time and space performance because they avoid repeated evaluations of goals and unnecessary constructions of data structures. Received December 2000 / Accepted in revised form January 2002     

Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.A preliminary version of this paper appears as: Reducing Nondeterminism while Specializing Logic Programs. Proceedings of the 24th Annual ACM Symposium on Principles of Programming Languages, Paris, France, January 15–17, 1997, ACM Press, 1997, pp. 414–427.     

Optokinetic and vestibular stimulation determines the spatial orientation of negative optokinetic afternystagmus in the rabbit

Prolonged binocular optokinetic stimulation (OKS) in the rabbit induces a high-velocity negative optokinetic afternystagmus (OKAN II) that persists for several hours. We have taken advantage of this uniform nystagmus to study how changes in static head orientation in the pitch plane might influence the orientation of the nystagmus. After horizontal OKS, the rotation axis of the OKAN II remained almost constant in space as it was kept aligned with the gravity vector when the head was pitched by as much as 80 degrees up and 35 degrees down. Moreover, during reorientation, slow-phase eye velocity decreased according to the head pitch angle. Thereafter, we analyzed the space orientation of OKAN II after optokinetic stimulation during which the head and/or the OKS were pitched upward and downward. The rotation axis of OKAN II did not remain aligned with an earth vertical axis nor a head vertical axis, but it tended to be aligned with that of the OKS respace. The slow-phase eye velocity of OKAN II was also affected by the head pitch angle during OKS, because maximal OKAN II velocity occurred at the same head pitch angle as that during optokinetic stimulation. We suggest that OKAN II is coded in gravity-centered rather than in head-centered coordinates, but that this coordinate system may be influenced by optokinetic and vestibular stimulation. Moreover, the velocity attenuation of OKAN II seems to depend on the mismatch between the space-centered nystagmus rotation axis orientation and that of the "remembered" head-centered optokinetic pathway activated by OKS.