for review: lazy evaluation [round 2]

[Fergus Henderson]

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.

One thing I noticed was that the code for lazy_list was actually
quite a bit simpler using this approach than it was using the
three-functor approach.  I can post the code for that version
too for comparison, if you think that would be of interest.

Comments?

--------------------

Estimated hours taken: 16

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.

Index: extras/lazy_evaluation/lazy.m
===================================================================
RCS file: lazy.m
diff -N lazy.m
--- /dev/null	Sat Mar 13 20:05:00 1999
+++ lazy.m	Sat Mar 13 20:28:46 1999
@@ -0,0 +1,158 @@
+%-----------------------------------------------------------------------------%
+% 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.
+%
+%-----------------------------------------------------------------------------%
+
+:- 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.
+:- 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 implementation 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	Sat Mar 13 20:05:00 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	Sat Mar 13 20:05:00 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.