[m-dev.] Laziness modules

Ralph Becket rafe at csse.unimelb.edu.au
Tue May 5 17:04:53 AEST 2009


I put a couple of modules providing support for lazy computation
together at the weekend.  Is there any interest in adding these to the
library?  Laziness gives us what in the C# and Java worlds they call
"enumerables" and are using to good effect.

-- Ralph

%-----------------------------------------------------------------------------%
% lazy.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Fri Apr 17 15:50:59 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
% Basic lazy evaluation support.
%
%-----------------------------------------------------------------------------%

:- module lazy.

:- interface.

    % The type of suspended computations.
    %
:- type lazy(T).

    % Construct a suspension which will be evaulated at most once.
    %
:- func susp((func) = T) = lazy(T).

    % Convert a constant into a lazy value.
    %
:- func lazy(T) = lazy(T).

    % Extract the value of a lazy(T).
    %
:- func value(lazy(T)) = T.

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

:- implementation.

% It should be possible to merge the lazyrep with the C representation to
% avoid the need for two allocations per lazy construction, but passing
% higher order functions (like apply/N) to C is so painful that I stuck
% with the more obvious solution.

:- pragma foreign_type("C", lazy(T), "MR_Word *", [can_pass_as_mercury_type]).

:- type lazyrep(T)
    --->    unevaluated((func) = T)
    ;       evaluated(T).

:- impure pred new_lazy(lazy(T)::out) is det.

:- pragma foreign_proc("C", new_lazy(L::out),
    [will_not_call_mercury],
"
    L = (MR_Word *)MR_GC_NEW(MR_Word *);
").

:- semipure pred get_lazyrep(lazy(T)::in, lazyrep(T)::out) is det.

:- pragma foreign_proc("C", get_lazyrep(L::in, R::out),
    [promise_semipure, will_not_call_mercury],
"
    R = *L;
").

:- impure pred set_lazyrep(lazy(T)::in, lazyrep(T)::in) is det.

:- pragma foreign_proc("C", set_lazyrep(L::in, R::in),
    [will_not_call_mercury],
"
    *L = R;
").

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

susp(S) = L :-
    promise_pure (
        impure new_lazy(L),
        impure set_lazyrep(L, unevaluated(S))
    ).

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

value(L) = X :-
    promise_pure (
        semipure get_lazyrep(L, R),
        (
            R = unevaluated(S),
            X = apply(S),
            impure set_lazyrep(L, evaluated(X))
        ;
            R = evaluated(X)
        )
    ).

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

lazy(X) = L :-
    promise_pure (
        impure new_lazy(L),
        impure set_lazyrep(L, evaluated(X))
    ).

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



%-----------------------------------------------------------------------------%
% lazy_list.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Fri Apr 17 15:50:59 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
% Simple lazy list evaluation.
%
%-----------------------------------------------------------------------------%

:- module lazy_list.

:- interface.

:- import_module int.
:- import_module lazy.
:- import_module list.

    % The type of lazy lists.
    %
:- type lazy_list(T)
    --->    empty_lazy_list
    ;       lazy_list(T, lazy(lazy_list(T))).

    % The lazy list constructor.
    %
:- func cons(T, (func) = lazy_list(T)) = lazy_list(T).

    % The lazy list deconstructor.
    %
:- pred decons(lazy_list(T)::in, T::out, lazy_list(T)::out) is semidet.

    % Convert between ordinary lists and lazy lists.
    %
:- func list_to_lazy_list(list(T)) = lazy_list(T).

:- func lazy_list_to_list(lazy_list(T)) = list(T).

    % Append, map, filter, fold, take, drop for lazy lists.
    %
:- func lazy_list(T) ++ lazy_list(T) = lazy_list(T).

:- func map(func(T1) = T2, lazy_list(T1)) = lazy_list(T2).

:- func filter(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

:- func filter_out(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

:- func foldl(func(T1, T2) = T2, lazy_list(T1), T2) = T2.

:- func foldr(func(T1, T2) = T2, lazy_list(T1), T2) = T2.

:- func foldr_lazy(func(T1, lazy(T2)) = T2, lazy_list(T1), T2) = T2.

    % take(N, Xs) is the first N items of Xs or Xs itself if it has
    % fewer than N items.
    %
:- func take(int, lazy_list(T)) = lazy_list(T).

    % drop(N, Xs) is the remainder of Xs after the first N items have
    % been removed or the empty list if Xs has fewer than N items.
    %
:- func drop(int, lazy_list(T)) = lazy_list(T).

    % The following take or drop elements of a lazy_list while/until
    % an item satisfying some condition is found.
    %
:- func take_while(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

:- func drop_while(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

:- func take_until(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

:- func drop_until(pred(T)::in(pred(in) is semidet), lazy_list(T)::in) =
        (lazy_list(T)::out) is det.

% Lazy integer sequences.

    % ints(Lo, Hi) is the lazy_list [Lo, Lo + 1, ..., Hi].
    %
:- func ints(int, int) = lazy_list(int).

    % ints(Lo, Hi, Step) is the lazy_list [Lo, Lo + Step, ..., Max]
    % where Max is the largest integer <= Hi.
    %
:- func ints_with_step(int, int, int) = lazy_list(int).

    % ints_from(Lo) is the lazy_list [Lo, Lo + 1, ...].
    %
:- func ints_from(int) = lazy_list(int).

    % ints_from_with_step(Lo, Step) is the lazy_list [Lo, Lo + Step, ...].
    %
:- func ints_from_with_step(int, int) = lazy_list(int).

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

:- implementation.

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

cons(X, Susp) = lazy_list(X, susp(Susp)).

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

decons(lazy_list(X, LLXs), X, value(LLXs)).

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

list_to_lazy_list([]) = empty_lazy_list.

list_to_lazy_list([X | Xs]) =
    lazy_list(X, susp((func) = list_to_lazy_list(Xs))).

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

lazy_list_to_list(empty_lazy_list) = [].

lazy_list_to_list(lazy_list(X, LXs)) = [X | lazy_list_to_list(value(LXs))].

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

empty_lazy_list ++ Ys = Ys.

lazy_list(X, LXs) ++ Ys = cons(X, (func) = value(LXs) ++ Ys).

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

map(_, empty_lazy_list) = empty_lazy_list.

map(F, lazy_list(X, LXs)) = cons(F(X), (func) = map(F, value(LXs))).

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

filter(_, empty_lazy_list) = empty_lazy_list.

filter(P, lazy_list(X, LXs)) =
    ( if P(X) then
        cons(X, (func) = filter(P, value(LXs)))
      else
        filter(P, value(LXs))
    ).

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

filter_out(_, empty_lazy_list) = empty_lazy_list.

filter_out(P, lazy_list(X, LXs)) =
    ( if P(X) then
        filter_out(P, value(LXs))
      else
        cons(X, (func) = filter_out(P, value(LXs)))
    ).

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

foldl(_, empty_lazy_list, A) = A.

foldl(F, lazy_list(X, LXs), A) = foldl(F, value(LXs), F(X, A)).

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

foldr(_, empty_lazy_list, A) = A.

foldr(F, lazy_list(X, LXs), A) = F(X, foldr(F, value(LXs), A)).

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

foldr_lazy(_, empty_lazy_list, A) = A.

foldr_lazy(F, lazy_list(X, LXs), A) =
    F(X, susp((func) = foldr_lazy(F, value(LXs), A))).

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

take(N, Xs) =
    ( if N > 0, Xs = lazy_list(X, LXs) then
        cons(X, (func) = take(N - 1, value(LXs)))
      else
        empty_lazy_list
    ).

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

drop(N, Xs) =
    ( if N > 0, Xs = lazy_list(_, LXs) then
        drop(N - 1, value(LXs))
      else
        Xs
    ).

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

take_while(_, empty_lazy_list) = empty_lazy_list.

take_while(P, lazy_list(X, LXs)) =
    ( if P(X) then
        cons(X, (func) = take_while(P, value(LXs)))
      else
        empty_lazy_list
    ).

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

drop_while(_, empty_lazy_list) = empty_lazy_list.

drop_while(P, Xs @ lazy_list(X, LXs)) =
    ( if P(X) then
        drop_while(P, value(LXs))
      else
        Xs
    ).

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

take_until(_, empty_lazy_list) = empty_lazy_list.

take_until(P, lazy_list(X, LXs)) =
    ( if P(X) then
        empty_lazy_list
      else
        cons(X, (func) = take_until(P, value(LXs)))
    ).

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

drop_until(_, empty_lazy_list) = empty_lazy_list.

drop_until(P, Xs @ lazy_list(X, LXs)) =
    ( if P(X) then
        Xs
      else
        drop_until(P, value(LXs))
    ).

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

ints(Lo, Hi) =
    ( if Lo =< Hi then
        cons(Lo, (func) = ints(Lo + 1, Hi))
      else
        empty_lazy_list
    ).

ints_with_step(Lo, Hi, Step) =
    ( if Lo =< Hi then
        cons(Lo, (func) = ints_with_step(Lo + Step, Hi, Step))
      else
        empty_lazy_list
    ).

ints_from(Lo) =
    cons(Lo, (func) = ints_from(Lo + 1)).

ints_from_with_step(Lo, Step) =
    cons(Lo, (func) = ints_from_with_step(Lo + Step, Step)).

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



%-----------------------------------------------------------------------------%
% lazy_primes.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Tue May  5 13:33:30 EST 2009
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
%-----------------------------------------------------------------------------%

:- module lazy_primes.

:- interface.

:- import_module io.



:- pred main(io::di, io::uo) is cc_multi.

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

:- implementation.

:- import_module int.
:- import_module lazy.
:- import_module lazy_list.
:- import_module list.
:- import_module solutions.
:- import_module string.

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

main(!IO) :-
    io.command_line_arguments(Args, !IO),
    ( if
        Args = []
      then
        Max = 100
      else if
        Args = [MaxStr],
        string.to_int(MaxStr, Max0)
      then
        Max = Max0
      else
        io.format(stderr_stream,
            "usage: lazy_primes max\n  assuming 100\n", [], !IO),
        Max = 100
    ),
    InRange = ( pred(X::in) is semidet :- X =< Max ),
    PrintPrime = ( pred(X::in, IO0::di, IO::uo) is det :-
        format("%d ", [i(X)], IO0, IO)
    ),
    Primes = lazy_list.take_while(InRange, primes),
    solutions.unsorted_aggregate(enumerate_nondet(Primes), PrintPrime, !IO),
    io.nl(!IO).

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

:- pred enumerate_nondet(lazy_list(int)::in, int::out) is nondet.

enumerate_nondet(lazy_list(X, LXs), Y) :-
    (
        Y = X
    ;
        enumerate_nondet(value(LXs), Y)
    ).

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

:- func primes = lazy_list(int).

primes = primes_2(ints_from(2)).

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

:- func primes_2(lazy_list(int)) = lazy_list(int).

primes_2(empty_lazy_list) = empty_lazy_list.

primes_2(lazy_list(X, LXs)) =
        cons(X, (func) = primes_2(filter_out(multiple_of(X), value(LXs)))).

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

:- pred multiple_of(int::in, int::in) is semidet.

multiple_of(X, Y) :- Y mod X = 0.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the developers mailing list