On the Relation Between a Rewriting Computational Model for Functional Logic Languages and Or-Parallelism

Manuel M. T. Chakravarty

In S. Breitinger, H. Kröger, and R. Loogen, editors, Proceedings of the 5th International Workshop on Functional and Logic Programming, University of Marburg, 1996.

The programming language Escher introduced a rewriting computational model for functional logic languages. In this model, computation is regarded as the application of successive rewrite steps to a goal expression until the expression reaches a normal form. This is in contrast to the common operational basis of logic programming, namely the depth-first traversal of a search tree, which is usually adopted for functional logic languages also; Escher's model is more in spirit of the functional programming tradition of rewriting an expression with respect to a set of equations.

This paper relates the ideas of rewriting and of traversing a search tree as well as it introduces a new approach to the implementation of the rewriting computational model; this approach is inspired by the work on the implementation of or-parallelism and, especially, from the AKL-model of computation. The new implementation technique is substantially different from that used in AKL for two principal reasons: (i) it makes fundamental use of multi-threading, and (ii) the implemented language subsumes higher-order, lazy functional languages and is based on equational instead of clausal abstraction.

DVI version and PostScript version (16 pages)

This page is part of Manuel Chakravarty's WWW-stuff.