[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