The goal of this research is the design and implementation of functional logic programming languages. A functional logic programming language is a programming language that joins in a single paradigm features of logic programming and functional programming. Each paradigm complements the other; e.g., logic programming contributes non-determinism, inversion and partial data structures, whereas functional programming contributes efficient evaluation and infinite data structures.An extensive set of pages on functional logic programming is hosted at http://www.informatik.uni-kiel.de/~mh/FLP/.
The expressiveness of functional logic programming can be appreciated by considering, for example, a program that checks whether a string is a well-formed regular expression. The definition of regular expression (Aho, Sethi and Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986, pp. 94) is translated into a program with a very modest effort. Operation digit defines an alphabet (of digits). The metasymbol "|" denotes alternatives. The argument of operation regexp is the alphabet of the regular expressions.
digit -> "0" | "1" | ... | "9" regexp X -> X | "(" ++ regexp X ++ ")" | regexp X ++ regexp X | regexp X ++ "*" | regexp X ++ "|" ++ regexp XOperation regexp generates one of the infinite regular expressions over an alphabet. In itself, this is not a useful computation. However, operation regexp greatly simplifies coding a parser or recognizer of regular expressions. For example, given a string S the expression:regexp digit = Ssucceeds if and only if S is a well formed regular expression of digits.The advantages of functional logic programming languages over pure functional or pure logic languages can be better understood by comparing the implementations of a textbook example of a well-known problem.
This research is or has been supported in part by the following grants: NSF CCR-0110496, Non-Deterministic Computations for Functional Logic Programs; NSF INT-9981317, Advanced Techniques for Multi-Paradigm Declarative Languages; NSF CCR-9406751, Needed Narrowing Strategies.
Curry is a general purpose programming language proposed as the lingua franca of the functional logic community. Various front- and back-ends of a Curry compiler are currently being developed at several sites around the world. I implemented one of the front-ends, using JavaCC, and I contributed to the design of a back-end in Prolog. The PAKCS distribution of Curry includes the results of these efforts.The following papers are representative of the results obtained by the research. Copies and bibliographic references are available from my "publications" page.
Functional Logic Design Patterns, 2002
We introduce a handful of software design patterns for functional logic languages. Following usual approaches, for each pattern we propose a name and we describe its intent, applicability, structure, consequences, etc. Our patterns deal with data type construction, identifier declarations, mappings, search, non-determinism and other fundamental aspects of the design and implementation of programs. We present some problems and we show fragments of programs that solve these problems using our patterns. The programming language of our examples is Curry. The complete programs are available from the FLP patterns archive.An Implementation of Narrowing Strategies, 2001This paper describes an implementation of narrowing, an essential component of implementations of modern functional logic languages. These implementations rely on narrowing, in particular on some optimal narrowing strategies, to execute functional logic programs. We translate functional logic programs into imperative (Java) programs without an intermediate abstract machine. A central idea of our approach is the explicit representation and processing of narrowing computations as data objects. This enables the implementation of operationally complete strategies (i.e., without backtracking) or techniques for search control (e.g., encapsulated search). Thanks to the use of an intermediate and portable representation of programs, our implementation is general enough to be used as a common back-end for a wide variety of functional logic languages.Compiling Multi-Paradigm Declarative Programs into Prolog, 2000This paper describes a high-level implementation of the concurrent constraint functional logic language Curry. The implementation, directed by the lazy pattern matching strategy of Curry, is obtained by transforming Curry programs into Prolog programs. Contrary to previous transformations of functional logic programs into Prolog, our implementation includes new mechanisms for both efficiently performing concurrent evaluation steps and sharing common subterms. The practical results show that our implementation is superior to previously proposed similar implementations of functional logic languages in Prolog and is competitive w.r.t. lower-level implementations of Curry in other target languages. An noteworthy advantage of our implementation is the ability to immediately employ in Curry existing constraint solvers for logic programming. In this way, we obtain with a relatively modest effort the implementation of a declarative language combining lazy evaluation, concurrency and constraint solving for a variety of constraint systems.Needed Narrowing in Prolog, 1996We describe the implementation of needed narrowing deployed in a compiler of a functional-logic language and present a few related concepts and results. Our implementation is obtained by translating rewrite rules into Prolog source code and optionally applying a set of optimizations to this code. We benchmark the effectiveness of each individual optimization. We show that our implementation is more efficient than all other previously proposed similar implementations. We measure both execution times, as is customarily done, and memory allocation that turns out to be a significant factor. We solve equations using a semi-strict equality relation that generalizes classic strict equality with sometimes a smaller search space. We give a new, more declarative and accessible formulation of a definitional tree, a crucial concept of our approach, and we present a simple algorithm to build definitional trees. We briefly explore a notion of simplification that is applicable to and sometimes beneficial for computations in inductively sequential systems, where classic simplification is not applicable.Goedel with User-Defined Evaluable Functions, 1995We report our experience extending a logic programming language with a first-order functional component. Functional expressions are evaluated by narrowing and can contain logic variables for a seamless integration with the logic component of the language. Our experiment shows that our extension is achievable with a modest effort. It also suggests some changes to the syntax and semantics of the initial logic component of the language that would ease the use and implementation of the functional component.Lazy Rewriting in Logic Programming, 1992We describe a technique enabling a logic program to perform lazy rewriting. Our technique is based on a transformation of a rewrite system in a set of Horn clauses. We characterize syntactically, in terms of a hierarchical structure of the rewrite rules of an operation, the systems accepted by our transformation and outline a design technique yielding systems with these characteristics. We define our transformation, prove its correctness and other properties, and relate the efficiency of resolution to that of rewriting. Improvements over previous similar efforts include using a more expressive and more powerful language, generating a more efficient logic program, providing efficient operational completeness, and establishing a tight bound on the length of a resolution as a function of the length of a corresponding reduction sequence. We compare our approach with several related efforts and discuss examples which also show the integration of lazy with eager evaluation and the possibility of narrowing in addition to rewriting.
For further information, contact Sergio Antoy at antoy@cs.pdx.edu.Romanian Translation courtesy of Alexandra Seremina.
Bulgarian Translation courtesy of Dimitar Teykiyski.
Polish Translation courtesy of Alexey Gnatuk.