Lazy evaluation
Author(s): Amadeo Casas (http://www.cs.unm.edu/~amadeo, University of New Mexico), Jose F. Morales (minor modifications).This library package allows the use of lazy evaluation in a Ciao module/program.
Lazy Evaluation is a program evaluation technique used particularly in functional languages. When using lazy evaluation, an expression is not evaluated as soon as it is assigned, but rather when the evaluator is forced to produce the value of the expression. Although the when or freeze control primitives present in many modern logic programming systems are more powerful than lazy evaluation, they lack the simplicity of use and cleaner semantics of functional lazy evaluation.
The objective of this package is to allow evaluating the functions lazily. Functions are the subset of relations (predicates) which have a designated argument through which a single output is obtained for any set of inputs (the other arguments). In logic programming systems which have syntactic support for functions (including Ciao), functions are typically translated to predicates whose last argument is designated as a (single value) output and the rest as inputs.
In our proposal, a function can be declared as lazy via the following declaration:
:- lazy fun_eval f/N.
This function could be represented as:
:- lazy fun_eval f(~_,_,_,_).
where ~ indicates the argument through which the single output will be obtained. Another possible representation may be:
:- lazy fun_return f(~_,_,_,_).
In order to achieve the intended behavior, the execution of each function declared as lazy is suspended until the return value of the function is needed.
A simple example of the use of lazy evaluation would be the definition of a function which returns the (potentially) infinite list of integers starting with a given one:
:- lazy fun_eval nums_from/1. nums_from(X) := [X | nums_from(X+1)].
While lazy functions certainly increase the overhead in the execution, they also allow the user to develop in an easy way predicates which can handle infinite terms, and this is the main advantage of the proposed functionality.
Lazy evaluation can be also a better option than eager evaluation when a function in a different module is used and it returns a big amount of data. As an example, we have the following module module1:
:- module(module1, [test/1], [fsyntax, lazy, hiord]). :- use_module(library(lazy(lazy_lib)), [nums_from/2, takeWhile/3]). :- use_module(module2, [squares/2]). :- use_module(library(arithpreds)). :- fun_eval test/0. test := ~takeWhile((”(X) :- X < 10000), ~squares(~nums_from(1))).
and another module module2:
:- module(module1, [test/1], [fsyntax, lazy, hiord]). :- use_module(library(lazy(lazy_lib)), [nums_from/2, takeWhile/3]). :- use_module(module2, [squares/2]). :- use_module(library(arithpreds)). :- fun_eval test/0. test := ~takeWhile((”(X) :- X < 10000), ~squares(~nums_from(1))).
Function test/0 in module m1 needs to execute function squares/1, in module m2, which will return a very long list (in the case of this example this list will be infinite, but the conclusions also apply with finite but long lists). If squares/1 were executed eagerly then the entire list would be returned, to immediately execute the take/2 function with the entire list, but creating this intermediate result is wasteful in terms of memory requirements. In order to solve this problem, the squares/1 function could be moved to module m1 and merged with take/2 (or, also, they could exchange a size parameter). But rearranging the program is not always possible and may perhaps complicate other aspects of the overall program design.
If instead the squares/1 function is evaluated lazily, it is possible to keep the definitions unchanged and in different modules and there will be a smaller memory penalty for storing the intermediate result. As more values are needed by the take/2 function, more values in the list returned by squares/1 are built (in this example, only 10 values). These values that have been consumed and passed over will be recovered by the garbage collector and the corresponding memory freed. The query:
?- test(X).
will compute X = [1,4,9,16,25,36,49,64,81,100].
A library of useful functions has been added to this package to allow the programmer to develop lazy functions easily and with a well-defined syntax. This library is called lazy_lib.pl and it provides the following functions:
- nums_from(+X,-List): List is unified with an infinite list of successive numbers starting in X.
- nums_from_inc(+X,+Y,-List): List is unified with an infinite list of successive numbers starting in X with an increment of Y.
- repeat(+X,-List): List is unified with an infinite list of the term Y.
- cycle(+X,-List): List is unified with an infinite list of the term Y repeated infinite times.
- take(+X,+ListA,-ListR): ListR is unified with the first X elements of the infinite list ListA.
- takeWhile(+P,+ListA,-ListR): ListR is unified with the first elements of the infinite list ListA while the condition P is true.
- drop(+X,+ListA,-ListR): ListR is unified with the infinite list ListA dropping the first X elements.
- dropWhile(+P,+ListA,-ListR): ListR is unified with the infinite list ListA dropping the first elements while the condition P is true.
- splitAt(+X,+ListA,-Res): Res is unified with a tuple of lists where the first list is composed by the first X elements of the list ListA and the second list is composed by the rest of the elements of ListA.
- span(+P,+ListA,-Res): Res is unified with a tuple of lists where the first list is composed by the elements of ListA which verify the condition P and the second list is composed by the rest of the elements of the initial list.
- tail(+ListA,-ListR): ListR is unified with the tail of the infinite list ListA.
- lazy_map(+ListA,+P,-ListR): Version of the map/3 predicate to be executed lazily.
- lazy_foldl(+ListA,+X,+P,-ListR): Version of the foldl/3 predicate to be executed lazily.
- zipWith(+P,+ListA,+ListB,-ListR): ListR is a list whose elements are calculated from the function P and the elements of input lists ListA and ListB occuring at the same position in both lists.
Usage and interface
- Library usage:
:- use_package(lazy). or :- module(...,...,[lazy]). - New operators defined:
lazy/1 [1170,fx]. - Imports:
- System library modules:
freeze/freeze. - Packages:
prelude, nonpure, assertions.
- System library modules:
Other information
The translation of the code in order to execute it lazily is explained below.A sentence translation is provided to handle the lazy directives. The translation of a lazy function into a predicate is done in two steps. First, the function is converted into a predicate (using the fsyntax package). Then, the resulting predicate is transformed to suspend its execution until the value of the last variable (i.e., the output variable) is needed. This suspension is achieved by the use of the freeze/1 control primitive that many modern logic programming systems implement quite efficiently (block or when declarations can obviously also be used, but we explain the transformation in terms of freeze because it is more widespread). The translation will rename the original predicate to an internal name and add a bridge predicate with the original name which invokes the internal predicate through a call to freeze/1. This will delay the execution of the internal predicate until its result is required, which will be detected as a binding (i.e., demand) of its output variable.
We show now an example of the use of lazy evaluation, and how a lazy function is translated by this package. The following code returns an (infinite) list of fibonacci numbers:
:- lazy fun_eval fiblist/0.
fiblist := [0, 1 | ~zipWith(add, FibL, ~tail(FibL))]
:- FibL = fiblist.
which is translated into:
fiblist(X) :-
freeze(X, 'fiblist_$$lazy$$'(X)).
'fiblist_$$lazy$$'([0, 1 | Rest]) :-
fiblist(FibL),
tail(FibL, T),
zipWith(add, FibL, T, Rest).
In the fiblist function defined, any element in the resulting infinite list of fibonacci numbers can be referenced, as for example, nth(X, ~fiblist, Value).. The other functions used in the definition are tail/2 and zipWith/3. These two functions can be found in the lazy_lib.pl runtime file.
