[m-rev.] Proposal: move lazy.m from extras/ to library/

[Paul Bone]

Hi.

I'd like to move lazy.m from extras/lazy_evaluation/lazy.m to library/lazy.m or
perhaps deep_profiler/lazy.m

I've cleaned it up somewhat, this removes the foreign code and replaces it with
mutvars.  Should I commit this back to extras first?

This is my current version:


%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%-----------------------------------------------------------------------------%
% Copyright (C) 1999, 2006, 2009-2010 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%-----------------------------------------------------------------------------%
%
% lazy.m - provides support for optional lazy evaluation.
%
% Author: fjh, pbone.
% Stability: medium.
%
% This module provides the data type `lazy(T)' and the functions
% `val', `delay', and `force', which can be used to emulate lazy
% evaluation.
%
% Note that laziness is most useful for recursive data types,
% and for that case, you can't just use e.g. `lazy(list(T))',
% since that would only be lazy at the top-level; instead
% you need to define a new recursive data type lazy_list(T)
% which uses lazy(T) for the recursion.  See the module
% `lazy_list.m' for an example of how to do this.
%
% See the file README in extras/lazy_evaluation for additional documentation.
%
% This code has been copied and modified from extras/lazy_evaluation.  Foreign
% code has been removed.
%
%-----------------------------------------------------------------------------%

:- module lazy.
:- interface.

    % A lazy(T) is a value of type T which will only be evaluated on
    % demand.
    %
:- type lazy(T).

    % Convert a value from type T to lazy(T)
    %
:- func val(T) = lazy(T).

    % Construct a lazily-evaluated lazy(T) from a closure
    %
:- func delay((func) = T) = lazy(T).

    % Force the evaluation of a lazy(T), and return the result as type T.
    % Note that if the type T may itself contains subterms of type lazy(T),
    % as is the case when T is a recursive type like the lazy_list(T) type
    % defined in lazy_list.m, those subterms will not be evaluated --
    % force/1 only forces evaluation of the lazy/1 term at the top level.
    %
    % A second call to force will not re-evaluate the lazy expression, it will
    % simply return T.
    %
:- func force(lazy(T)) = T.

    % Test lazy values for equality.
    %
:- pred equal_values(lazy(T)::in, lazy(T)::in) is semidet.

:- pred compare_values(comparison_result::uo, lazy(T)::in, lazy(T)::in) is det.

%-----------------------------------------------------------------------------%
%
% The declarative semantics of the above constructs are given by the
% following equations:
%
%   val(X) = delay((func) = X).
%
%   force(delay(F)) = apply(F).
%
% The operational semantics satisfy the following:
%
% - val/1 and delay/1 both take O(1) time and use O(1) additional space.
%   In particular, delay/1 does not evaluate its argument using apply/1.
%
% - When force/1 is first called for a given term, it uses apply/1 to
%   evaluate the term, and then saves the result computed by destructively
%   modifying its argument; subsequent calls to force/1 on the same term
%   will return the same result.  So the time to evaluate force(X), where
%   X = delay(F), is O(the time to evaluate apply(F)) for the first call,
%   and O(1) time for subsequent calls.
%
% - Equality on values of type lazy(T) is implemented by calling force/1
%   on both arguments and comparing the results.  So if X and Y have type
%   lazy(T), and both X and Y are ground, then the time to evaluate X = Y
%   is O(the time to evaluate (X1 = force(X)) + the time to evaluate
%   (Y1 = force(Y)) + the time to unify X1 and Y1).
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- implementation.

:- import_module mutvar.

:- type lazy(T)
    --->    lazy(mutvar(lazy_state(T)))
    where equality is equal_values,
          comparison is compare_values.

    % Note that we use a user-defined equality predicate to ensure
    % that unifying two lazy(T) values will do the right thing.
    %
:- type lazy_state(T)
    --->    value(T)
    ;       closure((func) = T).

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

equal_values(X, Y) :-
    force(X) = force(Y).

compare_values(R, X, Y) :-
    compare(R, force(X), force(Y)).

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

val(X) = lazy(Mutvar) :-
    promise_pure (
        impure new_mutvar(value(X), Mutvar)
    ).

delay(F) = lazy(Mutvar) :-
    promise_pure (
        impure new_mutvar(closure(F), Mutvar)
    ).

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

force(Lazy) = Value :-
    % The promise_equivalent_solutions scope is needed to tell the compiler
    % that force will return equal answers given arguments that are equal
    % but that have different representations.
    promise_equivalent_solutions [Mutvar] (
        Lazy = lazy(Mutvar)
    ),
    promise_pure (
        impure get_mutvar(Mutvar, State),
        (
            State = value(Value)
        ;
            State = closure(Thunk),
            Value = apply(Thunk),
            impure set_mutvar(Mutvar, value(Value))
        )
    ).

%-----------------------------------------------------------------------------%
-------------- 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/20100929/9851fa85/attachment.sig>