Lazy functional/Logic Programming

Appeared in Volume 7/1, February 1994

fs@cs.tulane.edu
Frank Silbermann
10th September 1993

Though Babel is described as a lazy functional-logic language (Moreno-Navarro and Rodriguez-Artalejo), the implementation described by Andy Mueck ("CAMEL: An Extension of the CAM to Compile Functional/Logic Programs), and the implementation described by Kuchen, Loogen and Moreno-Navarro (Graph-based Implementation of a Functional Logic Language) are both strict. What has been published with respect to implementing lazy functional-logic programming? (By 'lazy' I am not necessarily restricting the topic to graph reduction, but any implementation that has the semantics of normal-order evaluation).

I know that Uday Reddy discussed lazy narrowing in 1985, and Darlington, in his paper on Absolute Set Abstraction and Hope, suggested that lazy evaluation could be compatible with his idea, But I am interested in implementations, not just theory.

A fairly recent paper by Hans, Loogen and Winkler, "On the Interaction of Lazy Evaluation and Backtracking" (anybody know where this was published - my copy doesn't say), states that a lazy strategy may lead to nontermination in combination with backtracking, where an innermost strategy will determine a solution. (e.g. where an argument has an infinite number of narrowings, each of which will cause the function's first program clause to fail, but which might succeed if the second program clause were tried). They then describe a compromise strategy that avoids the problem for many programs, but state that it is impossible to find a strategy that is safe and avoids the nontermination problems of lazy narrowing plus backtracking, in general.

I'm surprised that such a problem had not revealed itself earlier. Is this the first paper to seriously study the implementation of lazy narrowing and/or lazy functional/logic programming?

I know that Tetsuo Ida and Satoshi Okui at the Univ. of Tsukuba, Japan, have been doing experiments with lazy narrowing. Is there any other work I should be aware of?

lee@munta.cs.mu.oz.au
Lee Naish
13th September 1993

The following paper describes an extension of NU-Prolog with lazy function definitions (which are transformed into Prolog). There are other similar proposals around. There is a need for a good survey paper on this topic.

Lee Naish, Adding equations to NU-Prolog, In Proc. of The Third Int. Symp. on Prog. Lang. Implementation and LP, Passau, Germany, Springer-Verlag, LNCS 528, August, 1991, pp.15-26, Technical Report 91/2, Dept. of Computer Science, Univ. of Melbourne

labman@judith.ls.fi.upm.es
Julio Marino Carballo
13th September 1993

A first text on the implementation of lazy Babel is "Lazy Narrowing in a Graph Machine" [1]. This paper also addresses the nontermination problem and proposes a transformation scheme to a normal form - Uniform Babel programs. The authors identify the source of the non-termination problem - there is only a finite number of rules matching a redex but a (possibly) infinite number of outcomes - and propose a program transformation that implements backtracking in the proper order: try different reductions of arguments first, then try the different rules for each reduction. There is a implementation of the lazy abstract machine (lBAM). You can contact us for more details.

This partially solved the nontermination problem but made some others more evident. Subsequent research in the Babel project was aimed at dealing with the interaction between laziness and backtracking. Note that normal order reduction is just a "forward evaluation" concept. The paper "On the Interaction of Lazy Evaluation and Backtracking" [2] can be found in the proceedings of PLILP'92. Another intrinsic problem with the interaction of laziness and nondeterminism is reevaluation - delayed computations may be carried out several times. This was first discussed in a Compulog meeting in Pisa, April 1992, I think. The re-evaluation problem suggests evaluating the arguments of a function call as soon as possible. Of course, this should be done without affecting (much) the lazy nature of the language. For these reasons, in [3,4] a new approach is taken: to use static analysis to detect necessary reductions so that they be performed earlier, i.e. to safely control the degree of operational laziness. This is called demandedness analysis and can be seen as a broad generalization of the classical strictness analysis for FP. The evaluation strategy in [3] is again a mixed one, not fully lazy. This gets a little better in [4] which also includes a compilation scheme. The overhead introduced by this scheme is overcome with the techniques in [5]. A further extension to demandedness analysis will appear in [6].

[1] J.J.Moreno-Navarro and H.Kuchen and R.Loogen and M.Rodriguez-Artalejo, Lazy Narrowing in a Graph Machine, Proc. of the 2nd Int. Conf. on Algebraic and LP, Nancy, France, Springer-Verlag, LNCS 463, 1990, pp.298-317

[2] R.Loogen and W.Hans and S.Winkler, On the Interaction of Lazy Evaluation and Backtracking, Proc.of the 4th Int. Symp. on Prog. Lang. Implementation and LP, Leuven, Belgium, Springer-Verlag, LNCS 631, 1992, pp.355-369

[3] J.A.Jimènez-Martin and J.Marino and J.J.Moreno-Navarro, Some Techniques for the Efficient Compilation of Lazy Narrowing into Prolog, Proc. of LOPSTR'92, Manchester, UK, Springer-Verlag, Workshops in computer science, 1993

[4] J.J.Moreno-Navarro and H.Kuchen and J.Marino and W.Hans and S.Winkler, Efficient Lazy Narrowing using Demandedness Information, Proc. of the 5th Int. Symp. on PLILP Tallinn, Estonia, Springer-Verlag, LNCS 714, 1993, pp.167-183

[5] Angel Herranz Nievaand Julio Marino Carballo, Specialized Compilation of Lazy Functional Logic Programs, Segundo Congreso Nacional de Programacion Declarativa PRODE'93, 1993, Blanes, Girona, Spanish Conf. on Declarative Programming

[6] Julio Marino Carballo and Angel Herranz Nieva and J.J. Moreno Navarro, Demandedness Analysis with Dependence Information for Functional Logic Languages, Int. LP Symp., 1993, Vancouver, Canada, Workshop on Global Compilation

thiemann@informatik.uni-tuebingen.de
Peter Thiemann
13th September 1993

Frank Silbermann writes:
A fairly recent paper by Hans, Loogen and Winkler, "On the Interaction of Lazy Evaluation and Backtracking"

It is published as:

Werner Hans and Rita Loogen and Stefan Winkler, On the Interaction of Lazy Evaluation and Backtracking, PLILP '92 Prog. Lang. Implementation and LP M. Bruynooghe and M. Wirsing (eds). Springer LNCS 631, Leuven, Belgium, August 1992, pp.355-369

narain@latour.bellcore.com
Sanjai Narain
15th September 1993

Laziness and backtracking were discussed in my 1989 paper "Optimization by non-deterministic lazy rewriting" in the 3rd Conf. on Rewriting Techniques and Applications, LNCS 355. An earlier result is reported in "A technique for doing lazy evaluation in logic" in Journal of Logic Programming, October 1986.

Efficient lazy functional programming in Prolog was discussed in my 1990 paper "Lazy evaluation in logic programming" in the Int. Conf. on Computer Languages.

The context for these papers is rewriting, not narrowing. However, the techniques described are efficient.

fs@cs.tulane.edu
Frank Silbermann
13th September 1993

Julio Marino Carballo writes:
A first text on the implementation of lazy Babel is "Lazy Narrowing in a Graph Machine" [1]. This paper also addresses the nontermination problem and proposes a transformation scheme to a normal form - Uniform Babel programs.

Would the trying of different ways to reduce the arguments be interleaved with the trying of the different rules? For instance, would you:
1. Look for a way to reduce the arguments that haven't yet been tried;
2. If found, then try all the rules with this reduction;
3. Go to 1.

Is this what you mean?

You continue:
This partially solved the nontermination problem but made some others more evident.

Which sort of nontermination problems were made worse by this scheme?

By the way, how do other lazy functional logic languages (e.g. KLEAF) face these problems?

labman@judith.ls.fi.upm.es
Julio Marino Carballo
15th September 1993

Yes, that's the idea. The current problem is that different rules may need different degrees of evaluation for their arguments. The solution proposed was to transform the rules in such a way that all the heads had a similar shape in homologous positions. The problems I referred to in my last posting were with this translation aggravating reevaluation. As you will see in the paper, this would move some computations deeper into the evaluation tree, thus increasing the risk of reevaluations and delaying the detection of failures.

For instance, the program:

f 0 X 0 1 := 0.
f 1 1 Y 1 := 1.

f 0 X Y 1 := f1 Y.
f 1 X Y 1 := f2 X.
f1 0 := 0.
f2 1 := 1.

antoy@antares.cs.pdx.edu
Sergio Antoy
20th December 1993

Frank Silbermann writes:
Is this indeed the first paper to seriously study the implementation of lazy narrowing and/or lazy functional/logic programming?

A paper with several references to the problem can be obtained by anonymous FTP from:
ftp://potemkin.cs.pdx.edu/pub/faculty/antoy/A-Needed-Narrowing-Strategy.ps.Z

The paper is about a narrowing strategy that performs only steps that are unavoidable (these steps are technically called needed and are the essense of laziness). A shorter version of this paper will appear in the Proc. of the 21st ACM Symp. on Principles of Prog. Lang., pages 268-279, Portland, Oregon, January 1994.