Laziness

Lazy Evaluation

Lazy evaluation is a key feature in functional programming.
Lazy evaluation must play a similar role in functional-logic languages.
Main advantages of lazy evaluation:
- Functions can be defined more independently without interaction among them.
- The interaction is provided by the lazy mode of evaluation.
- => Modularity
- => Reusability
- Partial and non strict functions
- Infinite objects: Separate definition of the generation of the solutions to a problem from the termination condition.
- Faster than innermost evaluation in some cases.

Expressivity of Lazy Evaluation

Problem: Prime numbers

Generate prime numbers by the Erathostenes Sieve method.
Try to solve it in your favourite language before you check the solution in a functional logic language

Laziness - Implementation -

Narrowing strategy

Lazy narrowing is a strategy which only evaluates the arguments of a function application, if their evaluation is really demanded.
It has been proved to be complete for constructor-based languages GLMP91, Moreno-Navarro, Rodríguez-Artalejo 88, 92, Antoy, Echahed, Hanus 94.
Translation to PROLOG

The implementation of lazy functional logic languages by translation to Prolog has been investigated in several papers.
The flattening procedure must be combined with a different selection rule Bosco, Giovanetti 88.
The computation is controlled by storing function call as PROLOG terms, and evaluating them incrementally on demand. Cheong 92, Jiménez-Martín, Mariño, Moreno-Navarro 92, Loogen, López-Fraguas, Rodríguez-Artalejo 93.
Abstract Machine Implementation

WAM modification: The K-WAM for K-LEAF Bosco, Cecchi, Moiso 89
Graph machine: LBAM for BABEL , Moreno-Navarro, Kuchen, Loogen, Rodríguez-Artalejo 90.
Stack machine: SBAM Hans, Loogen, Winkler 92

Problems

There are some problems to combine lazy evaluation with the presence of logical variables and backtracking.

The program can (unnecessarily) diverge.
The evaluation of an expression e is delayed until its value is demanded by a lhs to be unified with a term t.
If this unification fails, an alternative computation for e will be tried, but e could have infinitely many solutions different to t. No other rule is tried, and the corresponding solutions will not be found.
The Eager strategy would find these solutions.
Arguments may need to be reevaluated several times.
Evaluation of an argument expression e of a function f is delayed until e is demanded
=> the choice point for f will be created before the choice points corresponding to e
=> e has to be reevaluated for every rule for f which is tried.

Solution: Evaluate the arguments of a function f as early as possible without sacrificing laziness.

By making all the arguments demanded or not demanded by all the rules -> transforming the programs in uniform programs, Moreno-Navarro, Kuchen, Loogen, Rodríguez-Artalejo 90
Used in the LBAM and in the JUMP machine.
Demandedness analysis:
A kind of strictness analysis, used to detect the shape of the arguments that all the rules demand for them.
Very efficient approach. Incorporated into the LBAM and in the compilation to PROLOG Moreno-Navarro, Kuchen, Mariño, Hans, Winkler 93, Herranz, Mariño, Moreno-Navarro 93, reporting some speedups.
Needed narrowing: Evaluate the functions in the right order Antoy, Echahed, Hanus 94, Loogen, López-Fraguas, Rodríguez-Artalejo 93.

Go to index