Many functionallogic languages are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction mechanism of functional languages and the resolution principle of logic languages. Needed...
详细信息
Many functionallogic languages are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction mechanism of functional languages and the resolution principle of logic languages. Needed narrowing is an optimal evaluation strategy which constitutes the basis of modern (narrowing-based) lazy functionallogic languages. In this work, we present the fundamentals of partial evaluation in such languages. We provide correctness results for partial evaluation based on needed narrowing and show that the nice properties of this strategy are essential for the specialization process. In particular, the structure of the original program is preserved by partial evaluation and, thus, the same evaluation strategy can be applied for the execution of specialized programs. This is in contrast to other partial evaluation schemes for lazy functionallogic programs which may change the program structure in a negative way. Recent proposals for the partial evaluation of declarative multi-paradigm programs use (some form of) needed narrowing to perform computations at partial evaluation time. Therefore, our results constitute the basis for the correctness of such partial evaluators.
We propose a general framework for first-order functional logic programming, supporting lazy functions, non-determinism and polymorphic datatypes whose data constructors obey a set C of equational axioms. On top of a ...
详细信息
We propose a general framework for first-order functional logic programming, supporting lazy functions, non-determinism and polymorphic datatypes whose data constructors obey a set C of equational axioms. On top of a given C, we specify a program as a set R of C-based conditional rewriting rules for defined functions. We argue that equational logic does not supply the proper semantics for such programs. Therefore, we present an alternative logic which includes W-based rewriting calculi and a notion of model. We get soundness and completeness for C-based rewriting w.r.t. models, existence of free models for all programs, and type preservation results. As operational semantics, we develop a sound and complete procedure for goal solving, which is based on the combination of lazy narrowing with unification modulo C. Our framework is quite expressive for many purposes, such as solving action and change problems, or realizing the GAMMA computation model.
This work introduces a transformation methodology for functionallogic programs based on needed narrowing, the optimal and complete operational principle for modem declarative languages which integrate the best featur...
详细信息
This work introduces a transformation methodology for functionallogic programs based on needed narrowing, the optimal and complete operational principle for modem declarative languages which integrate the best features of functional and logicprogramming. We provide correctness results for the transformation system w.r.t. the set of computed values and answer substitutions and show that the prominent properties of needed narrowing-namely, the optimality w.r.t. the length of derivations and the number of computed solutions-carry over to the transformation process and the transformed programs. We illustrate the power of the system by taking on in our setting two well-known transformation strategies (composition and tapling). We also provide an implementation of the transformation system which, by means of some experimental results, highlights the potentiality of our approach. (C) 2003 Elsevier B.V. All rights reserved.
Needed narrowing is a complete and optimal operational principle for modern declarative languages which integrate the best features of lazy functional and logicprogramming. We investigate the formal relation between ...
详细信息
Needed narrowing is a complete and optimal operational principle for modern declarative languages which integrate the best features of lazy functional and logicprogramming. We investigate the formal relation between needed narrowing and another (not so lazy) narrowing strategy which is the basis for popular implementations of lazy function at logic languages. We demonstrate that needed narrowing and lazy narrowing are computationally equivalent over the class of uniform programs. We also introduce a complete refinement of lazy narrowing, called uniform lazy narrowing, which is still equivalent to needed narrowing over the aforementioned class. Since actual implementations of functionallogic languages are based on the transformation of the original program into a uniform one-which is then executed using a lazy narrowing strategy-our results can be thought of as a formal basis for the correctness of these implementations.
This paper abstracts the contents of a PhD dissertation entitled "Partial Evaluation of Lazy functionallogic Programs" which has been defended at the Technical University of Valencia, promoted by Prof. Mari...
详细信息
This paper abstracts the contents of a PhD dissertation entitled "Partial Evaluation of Lazy functionallogic Programs" which has been defended at the Technical University of Valencia, promoted by Prof. Maria Alpuente. Partial evaluation is an automatic program transformation technique that aims the specialization of programs, with regard to parts of their input, while preserving program semantics. Partial evaluation has been first applied to functionallogic languages in [6] where it is shown that the correctness of the transformation is dependent of the narrowing strategy used by the specialization algorithm. This thesis studies how to solve the problems arisen when lazy narrowing (a valuable strategy for functional logic programming) is used as the basic operational mechanism during the partial evaluation process. Also, we develop some methods that improve the efficiency of the specialization.
This paper deals with a framework to program autonomous robots in the declarative multi-paradigm language Curry. Our goal is to apply a high-level declarative programming language for the programming of embedded syste...
详细信息
This paper deals with a framework to program autonomous robots in the declarative multi-paradigm language Curry. Our goal is to apply a high-level declarative programming language for the programming of embedded systems. For this purpose, we use a specialization of Curry called Embedded Curry. We show the basic ideas of our framework and an implementation that translates Embedded Curry programs into C.
This paper abstracts the contents of a PhD dissertation entitled 'Transformation Rules and Strategies for functional-logic Programs' which has been recently defended. These techniques are based on fold/unfold ...
详细信息
This paper abstracts the contents of a PhD dissertation entitled 'Transformation Rules and Strategies for functional-logic Programs' which has been recently defended. These techniques are based on fold/unfold transformations and they can be used to optimize integrated (functional-logic) programs for a wide class of applications. Experimental results shows that typical examples in the field of Artificial Intelligence are successfully enhanced by our transformation system SYNTH. The thesis presents the first approach of these methods for declarative languages that integrate the best features from functional and logicprogramming.
This paper abstracts the contents of a PhD dissertation entitled 'Partial evaluation of multi-paradigm declarative languages: foundations, control, algorithms and efficiency' which has been recently defended. ...
详细信息
This paper abstracts the contents of a PhD dissertation entitled 'Partial evaluation of multi-paradigm declarative languages: foundations, control, algorithms and efficiency' which has been recently defended. Partial evaluation is an automatic technique for program optimization whose range of potential applications covers a wide spectrum of problem-specific optimizations. For instance, there are successful experiences in the field of artificial intelligence, like the optimization (by partial evaluation) on simulators for neural network training. The thesis presents novel methods and techniques for the partial evaluation of multi-paradigm declarative languages, which integrate features from functional and logicprogramming.
Modern multi-paradigm declarative languages integrate features from functional, logic, and concurrent programming. Since programs in these languages make extensive use of fist-processing functions, we consider of much...
详细信息
ISBN:
(纸本)3540414282
Modern multi-paradigm declarative languages integrate features from functional, logic, and concurrent programming. Since programs in these languages make extensive use of fist-processing functions, we consider of much interest the development of list-processing optimization techniques. In this work, we consider the adaptation of the well-known difference-lists transformation from the logicprogramming paradigm to our integrated setting. Unfortunately, the use of difference-lists is impractical due to the absence of non-strict equality in lazy (call-by-name) languages. Despite all, we have developed a novel, stepwise transformation which achieves a similar effect over functionallogic programs. We also show a simple and practical approach to incorporate the optimization into a real compiler. Finally, we have conducted a number of experiments which show the practicality of our proposal.
Languages that integrate functional and logicprogramming styles with a complete operational semantics are based on narrowing. In order to avoid useless computations, lazy narrowing strategies have been proposed in th...
详细信息
Languages that integrate functional and logicprogramming styles with a complete operational semantics are based on narrowing. In order to avoid useless computations, lazy narrowing strategies have been proposed in the past. This paper presents an improvement of lazy narrowing by incorporating deterministic simplification steps into lazy narrowing derivations. These simplification steps reduce the search space so that in some cases infinite search spaces are reduced to finite ones. We consider two classes of programs where this strategy can be applied. Firstly, we show soundness and completeness of our strategy for functionallogic programs based on ground confluent and terminating rewrite systems. Then, we show similar results for constructor-based weakly orthogonal (not necessarily terminating) rewrite systems. Finally, we demonstrate the improved operational behavior by means of several examples. Since most functionallogic languages are based on programs belonging to one of these classes, our result is a significant step to improve the operational semantics of existing functionallogic languages. (C) 1997 Elsevier Science Ltd. All rights reserved.
暂无评论