for review: add lazy evaluation to library

[Fergus Henderson]

Hi,

I propose adding support for optional lazy evaluation to the
standard library.  Comments?
I'd appreciate any feedback.

And could someone please review my change?

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

library/lazy.m:
	New module, for lazy evaluation.

NEWS:
w3/news/newsdb.inc:
	Mention the new module.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.132
diff -u -u -r1.132 NEWS
--- NEWS	1998/12/06 06:23:38	1.132
+++ NEWS	1999/03/09 23:53:46
@@ -1,6 +1,13 @@
 NEWS since Mercury release 0.8:
 -------------------------------
 
+* We've added library support for optional lazy evaluation.
+
+  The Mercury standard library now includes a new module `lazy',
+  which provides support for optional lazy evaluation
+  via a type `lazy(T)', with `delay' and `force' operations.
+  See the Mercury Library Reference Manual for details.
+
 * We've added a new predicate to the Mercury standard library:
 	bag__count_value/3.	
 
@@ -9,4 +16,9 @@
   The interface is based on the C functions dlopen(), dlsym(), and co.,
   which are supported by most modern Unix systems.
   See the files in extras/dynamic_linking for details.
+
+* The debugger now supports interactive queries.
+
+  See the "Interactive query commands" subsection of the "Debugger commands"
+  section of the "Debugging" chapter of the Mercury User's Guide for details.
 
Index: w3/news/newsdb.inc
===================================================================
RCS file: /home/mercury1/repository/w3/news/newsdb.inc,v
retrieving revision 1.22
diff -u -u -r1.22 newsdb.inc
--- newsdb.inc	1999/03/07 14:02:35	1.22
+++ newsdb.inc	1999/03/09 23:50:58
@@ -18,6 +18,13 @@
 
 $newsdb = array(
 
+"9 Mar 1999" => array("Lazy evaluation",
+"The Mercury standard library now includes a new module \`lazy',
+which provides support for optional lazy evaluation,
+via a type \`lazy(T)', with \`delay' and \`force' operations.
+See the 
+<A HREF=\"http://www.cs.mu.oz.au/research/mercury/information/doc/library_toc.html\">Mercury Library Reference Manual</A> for details.
+
 "8 Mar 1999" => array("Interactive queries",
 
 "The Mercury debugger now includes support for interactive queries.
Index: library.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/library.m,v
retrieving revision 1.43
diff -u -u -r1.43 library.m
--- library.m	1998/09/29 05:10:45	1.43
+++ library.m	1999/03/10 00:00:01
@@ -27,7 +27,8 @@
 :- import_module bimap, bintree, bintree_set, bool.
 :- import_module bt_array, char, dir, eqvclass, float.
 :- import_module math, getopt, graph, group, int.
-:- import_module io, list, map, multi_map, pqueue, queue, random, relation.
+:- import_module io, list, lazy, map, multi_map.
+:- import_module pqueue, queue, random, relation.
 :- import_module require, set, set_bbbtree, set_ordlist, set_unordlist, stack.
 :- import_module std_util, string, term, term_io, tree234, varset.
 :- import_module store, rbtree, parser, lexer, ops.


library/lazy.m:
%-----------------------------------------------------------------------------%
% 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 - provides support for optional lazy evaluation.
%
% Author: fjh.
% Stability: medium.
%
%-----------------------------------------------------------------------------%

:- module lazy.
:- interface.

% a lazily-evaluted value of type T
:- type 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.
:- 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 following may be needed occaisionally, in case
% the compiler can't infer the right higher-order 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).
:- inst lazy == lazy(ground).

:- 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], "F = F2;").

%-----------------------------------------------------------------------------%

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;
}").

%-----------------------------------------------------------------------------%

-- 
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.