[m-rev.] Moved lazy_list.m from extras/ to samples/

Paul Bone pbone at csse.unimelb.edu.au
Mon Aug 29 16:13:19 AEST 2011


Move lazy list eample code from extras/ to samples/

extras/lazy_evaluation/*:
    Removed old code.

samples/lazy_list/README:
samples/lazy_list/lazy_list.m:
samples/lazy_list/lazy_list_test.m:
    Code copied from old location.

    lazy_list.m has been modified to ensure that it works with the current
    version of library/lazy.m

extras/README:
    Removed old description of lazy_evaluation

samples/README:
    Describe the exitance of samples/lazy_list

Index: extras/README
===================================================================
RCS file: /home/mercury1/repository/mercury/extras/README,v
retrieving revision 1.29
diff -u -p -b -r1.29 README
--- extras/README	2 Aug 2011 07:55:09 -0000	1.29
+++ extras/README	29 Aug 2011 06:06:42 -0000
@@ -36,11 +36,6 @@ graphics	Some packages for doing graphic
 		GLUT, a simplified binding to Xlib, a binding
 		to Allegro/AllegroGL and a Mercury binding to Cairo.
 
-lazy_evaluation
-		Some examples of the use of the standard library's
-		`lazy' module, including a module `lazy_list' that defines
-		a lazy list data type.
-
 lex		A lexer package for Mercury that works over the I/O state,
 		strings, and so forth.  It comes with a rich set of
 		standard regular expressions and the user is free to add
Index: extras/lazy_evaluation/Mmakefile
===================================================================
RCS file: extras/lazy_evaluation/Mmakefile
diff -N extras/lazy_evaluation/Mmakefile
--- extras/lazy_evaluation/Mmakefile	16 Jan 2003 10:44:17 -0000	1.2
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,11 +0,0 @@
-#-----------------------------------------------------------------------------#
-# Copyright (C) 2002-2003 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.
-#-----------------------------------------------------------------------------#
-INSTALL_PREFIX := $(INSTALL_PREFIX)/extras
--include ../Mmake.params
-default_target: all
-depend: lazy_list.depend lazy_list_test.depend
-all: liblazy_list lazy_list_test
-install: liblazy_list.install
Index: extras/lazy_evaluation/README
===================================================================
RCS file: extras/lazy_evaluation/README
diff -N extras/lazy_evaluation/README
--- extras/lazy_evaluation/README	7 Oct 2010 05:03:12 -0000	1.3
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,73 +0,0 @@
-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_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.
-
-Mercury's standard library contains.
-    
-    lazy.m:
-		This module defines the lazy(T) type, and the force/1
-		and delay/1 functions.
-
-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 reasons 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_list.m
===================================================================
RCS file: extras/lazy_evaluation/lazy_list.m
diff -N extras/lazy_evaluation/lazy_list.m
--- extras/lazy_evaluation/lazy_list.m	5 Aug 2010 06:55:43 -0000	1.4
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,137 +0,0 @@
-%-----------------------------------------------------------------------------%
-% vim: ts=4 sw=4 et ft=mercury
-%-----------------------------------------------------------------------------%
-%
-% 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 foreign_proc').
-% :-(
-
-:- func list_inst_cast(lazy_list(T)) = lazy_list(T).
-:- mode list_inst_cast(in) = out(lazy_list) is det.
-
-:- pragma foreign_proc("C",
-    list_inst_cast(F::in) = (F2::out(lazy_list)),
-    [promise_pure, 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: extras/lazy_evaluation/lazy_list_test.m
diff -N extras/lazy_evaluation/lazy_list_test.m
--- extras/lazy_evaluation/lazy_list_test.m	15 Mar 1999 08:56:59 -0000	1.1
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,27 +0,0 @@
-%-----------------------------------------------------------------------------%
-%
-% 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
-
-%-----------------------------------------------------------------------------%
Index: samples/README
===================================================================
RCS file: /home/mercury1/repository/mercury/samples/README,v
retrieving revision 1.13
diff -u -p -b -r1.13 README
--- samples/README	8 Jul 2011 04:08:27 -0000	1.13
+++ samples/README	29 Aug 2011 05:47:53 -0000
@@ -72,3 +72,8 @@ muz			This directory contains a syntax c
 
 solver_types		This directory contains an example solver type
 			implementation and some sample applications.
+
+lazy_list		This directory contains an example of the lazy module
+			can be used to implement lazy data structures, in this
+			case a lazy list.
+
Index: samples/lazy_list/README
===================================================================
RCS file: samples/lazy_list/README
diff -N samples/lazy_list/README
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/README	29 Aug 2011 05:56:20 -0000
@@ -0,0 +1,69 @@
+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_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.
+
+Mercury's standard library contains.
+    
+    lazy.m:
+		This module defines the lazy(T) type, and the force/1
+		and delay/1 functions.
+
+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.  This is
+because the lazy(T) type currently uses two levels of indirection, whereas it
+could be implemented with only one.
+
Index: samples/lazy_list/lazy_list.m
===================================================================
RCS file: samples/lazy_list/lazy_list.m
diff -N samples/lazy_list/lazy_list.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/lazy_list.m	29 Aug 2011 05:44:52 -0000
@@ -0,0 +1,111 @@
+%-----------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%-----------------------------------------------------------------------------%
+%
+% 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).
+% Modified by Paul Bone (2011) for compatibilty with the lazy module in
+% Mercury's standard library.
+
+:- 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))].
+
+%-----------------------------------------------------------------------------%
+
+    % force evaluation of (the top level of) a lazy list
+:- func force_list(lazy(lazy_list(T))) = lazy_list(T).
+
+%-----------------------------------------------------------------------------%
+
+    % Convert a lazy_list to an ordinary list.
+:- func to_list(lazy_list(T)) = list(T).
+
+    % Convert an ordinary list to a lazy_list.
+:- func from_list(list(T)) = lazy_list(T).
+
+%-----------------------------------------------------------------------------%
+
+    % 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).
+
+    % member(Elem, List) :
+    %    True iff `List' contains `Elem'.
+:- pred member(T, lazy_list(T)).
+:- mode member(in, in) is semidet.
+:- mode member(out, in) 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 is det.
+
+    % take(N, L) returns the first N elements of L
+:- func take(int, lazy_list(T)) = lazy_list(T).
+
+    % 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) = out is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+force_list(Xs) = force(Xs).
+
+%-----------------------------------------------------------------------------%
+
+to_list([]) = [].
+to_list([X | Xs]) = [X | to_list(force_list(Xs))].
+
+from_list([]) = [].
+from_list([X | Xs]) =
+    [X | val(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: samples/lazy_list/lazy_list_test.m
===================================================================
RCS file: samples/lazy_list/lazy_list_test.m
diff -N samples/lazy_list/lazy_list_test.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/lazy_list_test.m	29 Aug 2011 05:35:08 -0000
@@ -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::di, io::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
+
+%-----------------------------------------------------------------------------%

Index: extras/README
===================================================================
RCS file: /home/mercury1/repository/mercury/extras/README,v
retrieving revision 1.29
diff -u -p -b -r1.29 README
--- extras/README	2 Aug 2011 07:55:09 -0000	1.29
+++ extras/README	29 Aug 2011 06:06:42 -0000
@@ -36,11 +36,6 @@ graphics	Some packages for doing graphic
 		GLUT, a simplified binding to Xlib, a binding
 		to Allegro/AllegroGL and a Mercury binding to Cairo.
 
-lazy_evaluation
-		Some examples of the use of the standard library's
-		`lazy' module, including a module `lazy_list' that defines
-		a lazy list data type.
-
 lex		A lexer package for Mercury that works over the I/O state,
 		strings, and so forth.  It comes with a rich set of
 		standard regular expressions and the user is free to add
Index: extras/lazy_evaluation/Mmakefile
===================================================================
RCS file: extras/lazy_evaluation/Mmakefile
diff -N extras/lazy_evaluation/Mmakefile
--- extras/lazy_evaluation/Mmakefile	16 Jan 2003 10:44:17 -0000	1.2
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,11 +0,0 @@
-#-----------------------------------------------------------------------------#
-# Copyright (C) 2002-2003 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.
-#-----------------------------------------------------------------------------#
-INSTALL_PREFIX := $(INSTALL_PREFIX)/extras
--include ../Mmake.params
-default_target: all
-depend: lazy_list.depend lazy_list_test.depend
-all: liblazy_list lazy_list_test
-install: liblazy_list.install
Index: extras/lazy_evaluation/README
===================================================================
RCS file: extras/lazy_evaluation/README
diff -N extras/lazy_evaluation/README
--- extras/lazy_evaluation/README	7 Oct 2010 05:03:12 -0000	1.3
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,73 +0,0 @@
-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_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.
-
-Mercury's standard library contains.
-    
-    lazy.m:
-		This module defines the lazy(T) type, and the force/1
-		and delay/1 functions.
-
-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 reasons 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_list.m
===================================================================
RCS file: extras/lazy_evaluation/lazy_list.m
diff -N extras/lazy_evaluation/lazy_list.m
--- extras/lazy_evaluation/lazy_list.m	5 Aug 2010 06:55:43 -0000	1.4
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,137 +0,0 @@
-%-----------------------------------------------------------------------------%
-% vim: ts=4 sw=4 et ft=mercury
-%-----------------------------------------------------------------------------%
-%
-% 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 foreign_proc').
-% :-(
-
-:- func list_inst_cast(lazy_list(T)) = lazy_list(T).
-:- mode list_inst_cast(in) = out(lazy_list) is det.
-
-:- pragma foreign_proc("C",
-    list_inst_cast(F::in) = (F2::out(lazy_list)),
-    [promise_pure, 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: extras/lazy_evaluation/lazy_list_test.m
diff -N extras/lazy_evaluation/lazy_list_test.m
--- extras/lazy_evaluation/lazy_list_test.m	15 Mar 1999 08:56:59 -0000	1.1
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,27 +0,0 @@
-%-----------------------------------------------------------------------------%
-%
-% 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
-
-%-----------------------------------------------------------------------------%
Index: samples/README
===================================================================
RCS file: /home/mercury1/repository/mercury/samples/README,v
retrieving revision 1.13
diff -u -p -b -r1.13 README
--- samples/README	8 Jul 2011 04:08:27 -0000	1.13
+++ samples/README	29 Aug 2011 05:47:53 -0000
@@ -72,3 +72,8 @@ muz			This directory contains a syntax c
 
 solver_types		This directory contains an example solver type
 			implementation and some sample applications.
+
+lazy_list		This directory contains an example of the lazy module
+			can be used to implement lazy data structures, in this
+			case a lazy list.
+
Index: samples/lazy_list/README
===================================================================
RCS file: samples/lazy_list/README
diff -N samples/lazy_list/README
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/README	29 Aug 2011 05:56:20 -0000
@@ -0,0 +1,69 @@
+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_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.
+
+Mercury's standard library contains.
+    
+    lazy.m:
+		This module defines the lazy(T) type, and the force/1
+		and delay/1 functions.
+
+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.  This is
+because the lazy(T) type currently uses two levels of indirection, whereas it
+could be implemented with only one.
+
Index: samples/lazy_list/lazy_list.m
===================================================================
RCS file: samples/lazy_list/lazy_list.m
diff -N samples/lazy_list/lazy_list.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/lazy_list.m	29 Aug 2011 05:44:52 -0000
@@ -0,0 +1,111 @@
+%-----------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%-----------------------------------------------------------------------------%
+%
+% 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).
+% Modified by Paul Bone (2011) for compatibilty with the lazy module in
+% Mercury's standard library.
+
+:- 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))].
+
+%-----------------------------------------------------------------------------%
+
+    % force evaluation of (the top level of) a lazy list
+:- func force_list(lazy(lazy_list(T))) = lazy_list(T).
+
+%-----------------------------------------------------------------------------%
+
+    % Convert a lazy_list to an ordinary list.
+:- func to_list(lazy_list(T)) = list(T).
+
+    % Convert an ordinary list to a lazy_list.
+:- func from_list(list(T)) = lazy_list(T).
+
+%-----------------------------------------------------------------------------%
+
+    % 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).
+
+    % member(Elem, List) :
+    %    True iff `List' contains `Elem'.
+:- pred member(T, lazy_list(T)).
+:- mode member(in, in) is semidet.
+:- mode member(out, in) 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 is det.
+
+    % take(N, L) returns the first N elements of L
+:- func take(int, lazy_list(T)) = lazy_list(T).
+
+    % 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) = out is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+force_list(Xs) = force(Xs).
+
+%-----------------------------------------------------------------------------%
+
+to_list([]) = [].
+to_list([X | Xs]) = [X | to_list(force_list(Xs))].
+
+from_list([]) = [].
+from_list([X | Xs]) =
+    [X | val(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: samples/lazy_list/lazy_list_test.m
===================================================================
RCS file: samples/lazy_list/lazy_list_test.m
diff -N samples/lazy_list/lazy_list_test.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ samples/lazy_list/lazy_list_test.m	29 Aug 2011 05:35:08 -0000
@@ -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::di, io::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
+
+%-----------------------------------------------------------------------------%
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 489 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20110829/ca96a266/attachment.sig>


More information about the reviews mailing list