Abstract: Programs in functional logic languages usually have to satisfy a nonambiguity condition, that semantically ensures completeness of conditional narrowing and pragmatically ensures that the defined (non-boolean) functions are deterministic and do not yield different result values for the same argument tuples. The nonambiguity condition allows the dynamic detection of determinism in implementations of functional logic languages. In this paper we show how to achieve this and what can be gained by this optimization.
Abstract: Many recent proposals for the integration of functional and logic programming use conditional term rewriting systems (CTRS) as programs and narrowing as goal solving mechanism. This paper specifies a computation strategy for lazy conditional narrowing, based on the idea of transforming patterns into decision trees to control the computation. The specification is presented as a translation of CTRS into Prolog, which makes it executable and portable. Moreover, in comparison to related approaches, our method works for a wider class of CTRS.
Abstract: Functional logic languages are declarative programming languages that integrate the programming paradigms of functional and logic languages within a single framework. They are extensions of functional languages with principles derived from logic programming. Narrowing, the evaluation mechanism of functional logic languages, can be defined as a generalization of reduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectional unification known from logic programming languages. We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking, for which we fall back upon the methods of Warren's Prolog engine. The narrowing machine embodies an optimized treatment of deterministic computations. A complete specification of the reduction and the narrowing machine and of the translation of a sample language into abstract machine code is given. Comparative results of a C-implementation of the reduction and the narrowing machine show that the time overhead of the more complex narrowing evaluation is, in general, less than 10% of the reduction evaluation.
Abstract: We investigate the interaction of lazy evaluation and backtracking in the framework of functional logic languages, whose operational semantics is based on lazy narrowing. Technically, it is no problem to realize a lazy narrowing strategy by adapting the well-known techniques, which have been developed for functional languages, to the more general evaluation mechanism of functional logic languages. But, unfortunately, it turns out, that the use of a lazy strategy has some severe disadvantages. In particular, it may lead to nontermination in combination with backtracking, where an innermost strategy will determine a solution. The use of demandedness information for function arguments allows us to define a mixture between an eager and a lazy evaluation strategy, which partially helps to cope with these problems. The runtimes obtained for various example programs with respect to the different strategies, substantiate that the mixed strategy is a reasonable compromise between an eager and a lazy strategy for functional logic languages.
Abstract: Narrowing, the evaluation mechanism of functional logic languages, can be seen as a generalization of reduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectional unification known from logic programming languages. We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking. The latter has to be incorporated to handle nondeterministic computations. It turns out that the resulting narrowing machine can also be seen as an extension of Warren's Prolog engine. This extension enables a space efficient handling of nested expressions and embodies an optimized treatment of deterministic computations. As in Warren's machine the central component of the machine is a stack that contains environments, i.e. activation records of function calls, and choice points to keep track of possible alternative computations. It is ensured that choice points always contain the minimal amount of information that is necessary to restore a previous state on backtracking. A complete specification of the machine and of the translation of a sample language into abstract machine code is given. To test the feasibility of the new implementation technique a preliminary implementation has been developed in Miranda.
Abstract: The paper investigates the implementation of lazy narrowing in the framework of a graph reduction machine. By extending an appropriate architecture for purely functional languages an abstract graph narrowing machine for a functional logic language is constructed. The machine is capable of performing unification and backtracking. The techniques used in functional languages to cope with lazy evaluation are not directly applicable, but must be modified due to the logic component of the implemented language. A prototype implementation of the new machine has been developed.
Abstract: We describe in this paper a graph narrowing machine that has been desdigned for the implementation of a higher order functional logic language. To execute functional logic programs the machine must be capable of performing unification and backtracking. Some details about the implementation of the new machine on an Occam/transputer system are given.
Abstract: A new technique for the management of control structures in distributed implementations of dynamic process systems is presented. Instead of storing the runtime stacks of parallel processes as linked lists of function blocks in a heap structure, the local stacks of several parallel processes, which are executed on the same processor element, are stored in an interleaved manner on a single physical stack (within each processor element), called the meshed stack. The technique ensures that there is almost no overhead for the evaluation of single processes due to the parallel environment. In principle, the meshed stack technique is independent of the implemented language. We explain it for the parallel implementation of functional languages.
Abstract: We present a parallelizing compiler for lazy functional programs that uses strictness analysis to detect the implicit parallelism within programs and generates an intermediate functional program, where a new syntactic construct `letpar', which is semantically equivalent to the well-known let-construct, is used to indicate subexpressions for which a parallel execution is allowed. In order to avoid that the communication overhead outweighs the benefits of the parallel execution, the parallelizing compiler has to use some heuristics to estimate the complexity of expressions. Only for sufficiently complex expressions, a parallelization will be worthwhile. Using our distributed implementation of parallelized functional programs we investigated the impact of various parallelization strategies on the runtimes and speedups. The strategy, which only allows the parallel execution of non-predefined function calls in strict positions, shows the best runtimes and reasonable speedup results.
Abstract: Programmed graph reduction has been shown to be an efficient implementation technique for lazy functional languages on sequential machines. Considering programmed graph reduction as a generalization of conventional environment-based implementations where the activation records are allocated in a graph instead of on a stack it becomes very easy to use this technique for the execution of functional programs in a parallel machine with distributed memory. We describe in this paper the realization of programmed graph reduction in PAM --- a parallel abstract machine with distributed memory. Results of our implementation of PAM on an Occam-Transputersystem are given.