[m-dev.] for review: lazy evaluation [round 2]

[Fergus Henderson]

On 13-Mar-1999, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> Clearly my original proposal didn't generate enough consensus
> for it to belong in the standard library.  So this time
> I'm putting it in extras.  I've also included some examples
> and added a lot of documentation.

Here's what I will commit.  The two README file changes are new.
I've also made some minor changes to the documentation
in lazy.m; relative diff included below.
I'm going to commit these without waiting for review,
since I think the additional documentation can hardly
harm things, but review comments on the READMEs would
still be appreciated.

Estimated hours taken: 16

extras/README:
extras/lazy_evaluation/README:
	Document the stuff in this new directory.

extras/lazy_evaluation/lazy.m:
	New module for lazy evaluation.

extras/lazy_evaluation/lazy_list.m:
extras/lazy_evaluation/lazy_list_test.m:
	A demo of using lazy lists.

diff -u backup/lazy.m ./lazy.m
--- backup/lazy.m	Sat Mar 13 21:01:39 1999
+++ ./lazy.m	Mon Mar 15 18:40:51 1999
@@ -20,26 +20,32 @@
 % which uses lazy(T) for the recursion.  See the module
 % `lazy_list.m' for an example of how to do this.
 %
+% See the file README in this directory
+%
 %-----------------------------------------------------------------------------%
 
 :- module lazy.
 :- interface.
 
-% a lazy(T) is a value of type T which will only be evaluated on demand.
+% A lazy(T) is a value of type T which will only be evaluated on demand.
 :- type lazy(T).
 
 % :- inst lazy(I).  % abstract
 :- inst lazy == lazy(ground).
 
-% convert a value from type T to lazy(T)
+% Convert a value from type T to lazy(T)
 :- func val(T) = lazy(T).
 :- mode val(in) = out(lazy) is det.
 
-% construct a lazily-evaluated lazy(T) from a closure
+% Construct a lazily-evaluated lazy(T) from a closure
 :- func delay((func) = T) = lazy(T).
 :- mode delay((func) = out is det) = out(lazy) is det.
 
-% force the evaluation of a lazy(T), and return the result as type T.
+% Force the evaluation of a lazy(T), and return the result as type T.
+% Note that if the type T may itself contains subterms of type lazy(T),
+% as is the case when T is a recursive type like the lazy_list(T) type
+% defined in lazy_list.m, those subterms will not be evaluated --
+% force/1 only forces evaluation of the lazy/1 term at the top level.
 :- func force(lazy(T)) = T.
 :- mode force(in(lazy)) = out is det.
 
@@ -144,7 +150,7 @@
 :-        mode update_closure(in, in) is det.
 
 % Note that the implementation of this impure predicate relies on
-% some implementation details of the Mercury implementation.
+% some details of the Mercury implementation.
 :- pragma c_code(
 	update_closure(MercuryTerm::in, NewValue::in),
 	[will_not_call_mercury],
Index: extras/README
===================================================================
RCS file: /home/mercury1/repository/mercury/extras/README,v
retrieving revision 1.4
diff -u -r1.4 README
--- README	1998/12/07 01:55:01	1.4
+++ README	1999/03/15 04:31:42
@@ -23,6 +23,12 @@
 		and GUIs in Mercury: a Mercury interface to tcl/tk
 		and a Mercury binding to OpenGL.
 
+lazy_evaluation
+		A library module `lazy' containing support for optional
+		lazy evaluation in Mercury, together with some examples
+		of its use, including a module `lazy_list' that defines
+		a lazy list data type.
+
 odbc		A Mercury interface to ODBC (Open Database Connectivity),
 		for interfacing to standard relational database packages.
 
Index: extras/lazy_evaluation/README
===================================================================
RCS file: README
diff -N README
--- /dev/null	Mon Mar 15 19:46:19 1999
+++ README	Mon Mar 15 16:51:11 1999
@@ -0,0 +1,71 @@
+This directory contains support for optional lazy evaluation.
+Using the modules defined here, you can write Mercury code that
+makes use of lazily evaluated data structures. 
+
+Our implementation of lazy evaluation requires you to use a different
+type, lazy(T), whenever you want things to be lazily evaluated, and
+requires you to insert explicit calls to delay/1 or force/1 whenever
+lazy evaluation requires the creation or evaluation of closures.
+
+This directory contains the following files:
+
+	lazy.m:
+		This module defines the lazy(T) type, and the force/1
+		and delay/1 functions.
+
+	lazy_list.m:
+		This module defines a type lazy_list(T) using the lazy(T) type,
+		and also defines a few functions and predicates that operate
+		on lazy lists.
+
+	lazy_list_test.m:
+		This is just a very simple example showing the use of lazy
+		lists.
+
+In comparison with lazy functional languages, the disadvantage of our
+approach is that inserting the lazy(T) types and the explicit calls to
+force/1 and delay/1 requires additional work when you are writing your
+code.  Fortunately the Mercury compiler's static type checking will
+ensure that the calls to force/1 and delay/1 are consistent with the
+use of lazy(T) types.  But even so, putting all the calls to force/1
+and delay/1 in the right place can still be rather tedious. 
+
+In return, however, we get several important advantages.
+
+The first is that there are absolutely no efficiency costs resulting
+from lazy evaluation if you don't use it.  This is in contrast to many
+implementations of lazy functional languages, where you often pay a
+significant efficiency cost simply because things *might* be lazy, even
+when in actual fact they are not.  Compilers for lazy functional
+languages often try to avoid these costs by performing strictness
+analysis, but current compilers can only infer strictness of functions,
+not data types; using lazy data types rather than strict data types can
+have a very large impact on efficiency (e.g. a factor of 5).  Also, in
+the presence of separate compilation, compilers may need to make
+conservative assumptions about strictness.
+
+The second advantage is that the creation and evaluation of closures is
+explicit in the source code, which makes it much easier to reason about
+the performance of your programs.  Programs in languages where laziness
+is the default often suffer from space leaks or unexpectedly high
+memory usage, and these problems can be _extremely_ difficult to track
+down and understand, even for very experienced programmers.
+
+The third advantage is that supporting lazy evaluation via a library
+module keeps the language and its semantics simple.  We're not really
+providing lazy evaluation per se, we just _emulating_ it by passing
+lambda expressions as arguments.  So the "Semantics" chapter of the
+language reference manual does not need to be modified at all.
+Supporting lazy evaluation via a library module also keeps the
+implementation simple -- the module lazy.m requires only a very
+small amount of implementation-dependent code, and none of the
+rest of the implementation need change.
+
+Our current implementation of lazy evaluation is not very efficient.
+There are several for this.  One is that promise_only_solution/1,
+which is used in the implementation of force/1, is currently implemented
+rather inefficiently.  Another is that the lazy(T) type currently uses
+two levels of indirection, whereas it really ought to use only one.
+Finally, for maximum efficiency, we would need to inline delay/1,
+but that is not possible in the current implementation.  Solving these
+latter two issues would require a bit more compiler support.
Index: extras/lazy_evaluation/lazy.m
===================================================================
RCS file: lazy.m
diff -N lazy.m
--- /dev/null	Mon Mar 15 19:46:19 1999
+++ lazy.m	Mon Mar 15 18:40:51 1999
@@ -0,0 +1,164 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 1999 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% lazy.m - provides support for optional lazy evaluation.
+%
+% Author: fjh.
+% Stability: medium.
+%
+% This module provides the data type `lazy(T)' and the functions
+% `val', `delay', and `force', which can be used to emulate lazy
+% evaluation.
+%
+% Note that laziness is most useful for recursive data types,
+% and for that case, you can't just use e.g. `lazy(list(T))',
+% since that would only be lazy at the top-level; instead
+% you need to define a new recursive data type lazy_list(T)
+% which uses lazy(T) for the recursion.  See the module
+% `lazy_list.m' for an example of how to do this.
+%
+% See the file README in this directory for additional documentation.
+%
+%-----------------------------------------------------------------------------%
+
+:- module lazy.
+:- interface.
+
+% A lazy(T) is a value of type T which will only be evaluated on demand.
+:- type lazy(T).
+
+% :- inst lazy(I).  % abstract
+:- inst lazy == lazy(ground).
+
+% Convert a value from type T to lazy(T)
+:- func val(T) = lazy(T).
+:- mode val(in) = out(lazy) is det.
+
+% Construct a lazily-evaluated lazy(T) from a closure
+:- func delay((func) = T) = lazy(T).
+:- mode delay((func) = out is det) = out(lazy) is det.
+
+% Force the evaluation of a lazy(T), and return the result as type T.
+% Note that if the type T may itself contains subterms of type lazy(T),
+% as is the case when T is a recursive type like the lazy_list(T) type
+% defined in lazy_list.m, those subterms will not be evaluated --
+% force/1 only forces evaluation of the lazy/1 term at the top level.
+:- func force(lazy(T)) = T.
+:- mode force(in(lazy)) = out is det.
+
+%
+% The declarative semantics of the above constructs are given by the
+% following equations:
+%
+%	val(X) = delay((func) = X).
+%
+%	force(delay(F)) = apply(F).
+%
+% The operational semantics satisfy the following:
+%
+% - val/1 and delay/1 both take O(1) time and use O(1) additional space.
+%   In particular, delay/1 does not evaluate its argument using apply/1.
+%
+% - When force/1 is first called for a given term, it uses apply/1 to
+%   evaluate the term, and then saves the result computed by destructively
+%   modifying its argument; subsequent calls to force/1 on the same term
+%   will return the same result.  So the time to evaluate force(X), where
+%   X = delay(F), is O(the time to evaluate apply(F)) for the first call,
+%   and O(1) time for subsequent calls.
+%
+% - Equality on values of type lazy(T) is implemented by calling force/1
+%   on both arguments and comparing the results.  So if X and Y have type
+%   lazy(T), and both X and Y are ground, then the time to evaluate X = Y
+%   is O(the time to evaluate (X1 = force(X)) + the time to evaluate
+%   (Y1 = force(Y)) + the time to unify X1 and Y1).
+%
+% -----------------------------------------------------------------------------%
+
+% The following may be needed occaisionally, in case
+% the compiler can't infer the right higher-order inst...
+% It just returns its argument, cast to the correct inst.
+:- func inst_cast(lazy(T)) = lazy(T).
+:- mode inst_cast(in) = out(lazy) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+:- interface.
+
+% implementation details
+:- inst lazy(I) ---> value(I) ; closure((func) = out(I) is det).
+
+:- implementation.
+
+% Note that we use a user-defined equality predicate to ensure
+% that unifying two lazy(T) values will do the right thing.
+:- type lazy(T) ---> value(T) ; closure((func) = T)
+	where equality is equal_values.
+
+:- pred equal_values(lazy(T), lazy(T)).
+:- mode equal_values(in, in) is semidet.
+equal_values(X, Y) :-
+	force(inst_cast(X)) = force(inst_cast(Y)).
+
+:- pragma c_code(inst_cast(F::in) = (F2::out(lazy)),
+	[will_not_call_mercury, thread_safe], "F2 = F;").
+
+%-----------------------------------------------------------------------------%
+
+val(X) = value(X).
+delay(F) = closure(F).
+
+% If the compiler were to evaluate calls to delay/1 at compile time,
+% it could put the resulting closure/1 term in read-only memory,
+% which would make destructively updating it rather dangerous.
+% So we'd better not let the compiler inline delay/1.
+:- pragma no_inline(delay/1).
+
+%-----------------------------------------------------------------------------%
+
+% The call to promise_only_solution is needed to tell the
+% compiler that force will return equal answers given
+% arguments that are equal but that have different representations.
+force(Lazy) = promise_only_solution(do_force(Lazy)).
+
+:- pred do_force(lazy(T), T).
+:- mode do_force(in(lazy), out) is cc_multi.
+
+% The pragma promise_pure is needed to tell the compiler that
+% do_force is pure, even though it calls impure code.
+:- pragma promise_pure(do_force/2).
+
+do_force(Lazy, Value) :-
+	(	
+		Lazy = value(Value)
+	;
+		Lazy = closure(Func),
+		Value = apply(Func),
+
+		% Destructively update the closure with a new
+		% closure that immediately returns the same value,
+		% to avoid having to recompute the same result
+		% next time.
+		NewFunc = ((func) = Result :- Result = Value),
+		impure update_closure(Lazy, NewFunc)
+	).
+
+:- impure pred update_closure(T1, T2).
+:-        mode update_closure(in, in) is det.
+
+% Note that the implementation of this impure predicate relies on
+% some details of the Mercury implementation.
+:- pragma c_code(
+	update_closure(MercuryTerm::in, NewValue::in),
+	[will_not_call_mercury],
+"{
+	/* strip off tag bits */
+	Word *ptr = (Word *) strip_tag(MercuryTerm);
+	/* destructively update value */
+	*ptr = NewValue;
+}").
+
+%-----------------------------------------------------------------------------%
Index: extras/lazy_evaluation/lazy_list.m
===================================================================
RCS file: lazy_list.m
diff -N lazy_list.m
--- /dev/null	Mon Mar 15 19:46:19 1999
+++ lazy_list.m	Sat Mar 13 20:19:06 1999
@@ -0,0 +1,131 @@
+%-----------------------------------------------------------------------------%
+%
+% This is an example of how to use the `lazy' module to define
+% a recursive lazy data type, in this case lazy lists.
+% It also defines a small number of functions and predicates
+% that operate on lazy lists.
+%
+% See also lazy_list_test.m, which is an example program using this module.
+%
+% This source file is hereby placed in the public domain.  -fjh (the author).
+
+:- module lazy_list.
+:- interface.
+:- import_module lazy, int, list.
+
+%-----------------------------------------------------------------------------%
+
+	% The definition of the type `lazy_list(T)':
+	%	A lazy lazy_list is either an empty lazy_list, denoted `[]',
+	%	or an element `Head' of type `T' followed by a lazily
+	%	evaluated tail `Tail', of type `lazy(lazy_list(T))',
+	%	denoted `[Head | Tail]'.
+
+:- type lazy_list(T) ---> [] ; [T | lazy(lazy_list(T))].
+
+:- inst lazy_list(I) ---> [] ; [I | lazy(lazy_list(I))].
+:- inst lazy_list == lazy_list(ground).
+
+:- inst nonempty_lazy_list(I) ---> [I | lazy(lazy_list(I))].
+:- inst nonempty_lazy_list == nonempty_lazy_list(ground).
+
+%-----------------------------------------------------------------------------%
+
+	% force evaluation of (the top level of) a lazy list
+:- func force_list(lazy(lazy_list(T))) = lazy_list(T).
+:- mode force_list(in(lazy(lazy_list))) = out(lazy_list) is det.
+
+%-----------------------------------------------------------------------------%
+
+	% Convert a lazy_list to an ordinary list.
+:- func to_list(lazy_list(T)) = list(T).
+:- mode to_list(in(lazy_list)) = out is det.
+
+	% Convert an ordinary list to a lazy_list.
+:- func from_list(list(T)) = lazy_list(T).
+:- mode from_list(in) = out(lazy_list) is det.
+
+%-----------------------------------------------------------------------------%
+
+	% A lazy_list function version of the usual append predicate:
+	% append(Start, End) = List is true iff
+	% `List' is the result of concatenating `Start' and `End'.
+	%
+:- func append(lazy_list(T), lazy(lazy_list(T))) = lazy_list(T).
+:- mode append(in(lazy_list), in(lazy(lazy_list))) = out(lazy_list)
+	is det.
+
+	% member(Elem, List) :
+	%	True iff `List' contains `Elem'.
+:- pred member(T, lazy_list(T)).
+:- mode member(in, in(lazy_list)) is semidet.
+:- mode member(out, in(nonempty_lazy_list)) is multi.
+:- mode member(out, in(lazy_list)) is nondet.
+
+%-----------------------------------------------------------------------------%
+
+	% iterate(F, X0) = [X0, F(X0), F(F(X0)), F(F(F(X0))), ...]
+:- func iterate(func(T) = T, T) = lazy_list(T).
+:- mode iterate(func(in) = out is det, in) = out(lazy_list) is det.
+
+	% take(N, L) returns the first N elements of L
+:- func take(int, lazy_list(T)) = lazy_list(T).
+:- mode take(in, in(lazy_list)) = out(lazy_list) is det.
+
+	% map(F, [X0, X1, X2, ...]) = [F(X0), F(X1), F(X2), ...].
+:- func map(func(X) = Y, lazy_list(X)) = lazy_list(Y).
+:- mode map(func(in) = out is det, in(lazy_list)) = out(lazy_list) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+force_list(Xs) = list_inst_cast(force(Xs)).
+
+% Because the Mercury mode system is not properly polymorphic,
+% it doesn't always infer the right inst.  We sometimes need
+% to use inst casts (which can be implemented using `pragma c_code').
+% :-(
+
+:- func list_inst_cast(lazy_list(T)) = lazy_list(T).
+:- mode list_inst_cast(in) = out(lazy_list) is det.
+
+:- pragma c_code(list_inst_cast(F::in) = (F2::out(lazy_list)),
+	[will_not_call_mercury, thread_safe], "F2 = F;").
+
+%-----------------------------------------------------------------------------%
+
+to_list([]) = [].
+to_list([X | Xs]) = [X | to_list(force_list(Xs))].
+
+from_list([]) = [].
+from_list([X | Xs]) =
+	[X | delay((func) = R :- R = from_list(Xs))].
+
+%-----------------------------------------------------------------------------%
+
+append([], Ys) = force_list(Ys).
+append([X | Xs], Ys) =
+	[X | delay((func) = R :- R = append(force_list(Xs), Ys))].
+
+member(X, [X | _]).
+member(X, [_ | Xs]) :-
+	member(X, force_list(Xs)).
+
+%-----------------------------------------------------------------------------%
+
+map(_, []) = [].
+map(F, [H|T]) = [F(H) | delay((func) = R :- R = map(F, force_list(T)))].
+
+iterate(F, X0) = [X0 | delay((func) = R :- R = iterate(F, F(X0)))].
+
+take(_, []) = [].
+take(N, [X|Xs]) =
+	(if N > 0 then
+		[X | delay((func) = R :- R = take(N-1, force_list(Xs)))]
+	else
+		[]
+	).
+
+%-----------------------------------------------------------------------------%
Index: extras/lazy_evaluation/lazy_list_test.m
===================================================================
RCS file: lazy_list_test.m
diff -N lazy_list_test.m
--- /dev/null	Mon Mar 15 19:46:19 1999
+++ lazy_list_test.m	Sat Mar 13 20:15:41 1999
@@ -0,0 +1,27 @@
+%-----------------------------------------------------------------------------%
+%
+% lazy_list_test.m:
+%	This is a trivial example of the use of lazy lists.
+%
+% This source file is hereby placed in the public domain.  -fjh (the author).
+
+:- module lazy_list_test.
+:- interface.
+:- import_module io.
+
+:- pred main(io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+:- import_module lazy, lazy_list, int.
+
+:- func double(int) = int.
+double(X) = 2 * X.
+
+main -->
+	{ L = iterate(double, 1) },	% construct an infinite list...
+	{ L10 = take(10, L) },		% extract the first 10 elements
+	print(to_list(L10)), nl.	% print them
+
+%-----------------------------------------------------------------------------%
-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.