Lazy lists in Prolog?

Question

Is it possible to have lazy lists in Prolog? Something like the following:

ones([1 | Y]) :- ones(Y).

Although this obviously doesn't work as it's written.

Mortar

a tweak for what you wrote does the job: ones([1|Y]):- freeze(Y, ones(Y)).. – Moschatel

Answer 1

Markus Triska placed here in public domain some code worth to study:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Prolog stream/lazy list demonstration

   Written 2005 by Markus Triska ([email protected])
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

The title of the document (prost, for Prolog streams) maybe make the document a bit difficult to find, but make sense. Quoting from the above:

Here, "stream" is used in the sense of "sequence", "delayed list", "lazy list" etc. as in Structure and Interpretation of Computer Programs, not in the sense of a Prolog input/output stream.

Godart

Answer 2

Here's a lazy-list Hamming numbers in Prolog using a "generator idiom".

The more I think about it the more it seems to me the lazy lists of Haskell are just open-ended (a.k.a. "difference") lists of Prolog, and corecursion just a fancy name for the top-down list building of tail recursion modulo cons. Also, Haskell is implicitly set once language, while (non-backtracking subset of) Prolog is explicitly set once.

The mind-mangling "tying-the-knot" technique is actually nothing more than awkwardly implemented late variable instantiation. And, everything is a generator in Haskell, with memoizing storage a universal access mediator. But anyway,

The following implements the head-forced streams (of SICP variety), where if an element is forced, all the elements preceding it in the list are already forced as well.

:- dynamic( next/3 ).

% (* collect N elements produced by a generator in a row: *)
take( 0, Next, Z-Z, Next) :- !.
take( N, Next, [A|B]-Z, NextZ) :- N > 0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

% (* a "generator" provides a specific `next/3` implementation *)
next( hamm( A2,B, C3,D, E5,F, [H|G]), H, hamm( X,U, Y,V, Z,W, G) ) :- 
  H is min(A2, min(C3, E5)),
  (   A2 =:= H ->  B = [N2|U], X is N2*2  ;  (X,U) = (A2,B) ),
  (   C3 =:= H ->  D = [N3|V], Y is N3*3  ;  (Y,V) = (C3,D) ),
  (   E5 =:= H ->  F = [N5|W], Z is N5*5  ;  (Z,W) = (E5,F) ).

% (* Hamming numbers generator init state: *)
mkHamm( hamm( 1,X, 1,X, 1,X, X) ).       

% (* A calling example: main( +Number) *)
main(N) :- 
    mkHamm(G),        take(20,G,A-[],_),  write(A), nl,  
    take(N-1,G,_,G2), take(2,G2,B-[],_),  write(B), nl.

% (* testing ... *)
2 ?- main(1000).
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
[51200000,51840000]
true.

Simple, eh? For ones we just define

next( ones, 1, ones).

as there is no (change in) state there, and then call it as e.g.

take( N, ones, A-[], _), writeln(A).

For Haskell-like integer enumerations we define

next( fromBy(F,B), F, fromBy(F2,B)) :- F2 is F+B.

and call take(8, fromBy(3,2), A-[], _) to get A = [3, 5, 7, 9, 11, 13, 15, 17]. Fibonacci sequence is simply

next( fib(A,B), A, fib(B,C)) :- C is A+B.

With take(20, fib(0,1), FS-[], _), a 20-elements list FS of Fibonacci numbers is defined.

Memoizing Fibonacci sequence is

mkFibs( fibs([0|L], L) ) :- L = [1|_].
next( fibs([A|L], L), A, fibs(L, L2) ):- 
    L = [B|L2], L2 = [C|_], (var(C) -> C is A+B ; true).

Now restarting from a previously used generator won't recalculate the numbers but instead will re-fetch the previously calculated members of the sequence, where available. This internal shared open-ended storage is fragile to misuse i.e. wrongful instantiation (edit: of its not-yet-set last tail pointer variable). This is the reason for take building new storage for its answer, instead of exposing the internal one.

Moschatel

Answer 3

Yes, it's possible to have lazy lists in Prolog. Here's an infinite, lazy list of ones using freeze/2.

ones(L) :-
  freeze(L, (L=[1|T],ones(T)) ).

Using it at the top-level looks like this:

?- ones(Ones), [A,B,C|_] = Ones.
A = B = C = 1.

You might also enjoy the list_util pack (for SWI-Prolog) which contains several lazy list predicates.

Fearfully

how would the infinite Fibonacci sequence look like? – Moschatel

@WillNess I put together an infinite, lazy Fibonacci sequence for you gist.github.com/4644762 It's not as concise as Haskell, but still fun. – Fearfully

thank you very much for the example. ... I personally would prefer the name delay in place of freeze. The latter is so final, and implies - for me - the need to explicitly call thaw on a freezed var. While the former is more intuitive. I'm used to delay of Scheme, so it makes more sense to me. :) – Moschatel

@WillNess: What is thaw? Seems to be something opposed to freeze. – Judsonjudus

@Judsonjudus I was referring to my misreading of the name freeze, my first impression about it, having not read the manual. :) – Moschatel

@WillNess: I suspected somewhat that you were referring to freeze(Term, Frozen) and melt(Frozed, Thawed) which had very problematic semantic properties. – Judsonjudus

@Judsonjudus is this TAoP's freeze and melt_new? Are they at all related to the delaying freeze as used here? I didn't quite get where and for what are they needed, from the book. Is there any link to some discussion about them, and the associated problems? Google search didn't bring up much. ... I tried reading Boizumault once but the use of freeze there was confusing to me, having just read TAoP. Will appreciate any pointers. :) – Moschatel

@WillNess: TAoP's constructs permit to relate a variable to a corresponding atom (and vice versa). That in itself is semantically pretty problematic and has not been adapted by other systems. It was an attempt to make meta-programming cleaner. I'd say it failed. Boizumault's freeze/2 is the same as the one in SICStus, SWI, YAP, B and others. – Judsonjudus

Answer 4

well, you could define an infinite list of ones (or anything else) as:

H = [1|H].

use:

4 ?- H=[1|H], [A1|T1] = H, [A2|T2] = T1, T1=T2.
H = [1|**],
A1 = 1,
T1 = [1|**],
A2 = 1,
T2 = [1|**].

Of course, this won't work if you want a list of primes/fibonacci/anything not so trivial.

You could write some predicates that would emulate the behavior of a lazy list but I do not think that there are any libraries/standardized way to do it (at least in swi-prolog) (:( haskell's lazy list is such a nice feature).

Shipley

+1. Incomplete data structures are the closest to lazy lists that Prolog has to offer. – Greenwald

Don't you think that when/2, freeze/2, dif/2 can be used to simulate laziness ? – Omer

@Omer yup, I think that they are indeed useful building blocks to simulate laziness – Shipley

@joel76: yes, see my answer, which uses suspensions (ECLiPSe's equivalent to SWI's when/2 and freeze/2) – Shovelhead

Answer 5

Here's a slightly different take on lazy lists, which uses suspensions. It's written in ECLiPSe, but you should be able to replicate it in other flavours of Prolog.

It uses an attributed variable to record the current length of the lazy list, and constructs new members of the list when the lower bound of the variable's domain is raised.

I assume that the predicate that is executed to construct list members has arity 3, and the three arguments are: in-state, out-state, and result. It's easy to adapt the example to general goals, though.

I also used a "store", which is a non-logical hash storage, in order to quickly retrieve the n-th element of the list by avoiding to iterate over the list. Using a store is not essential, but iterating over a long list again and again can be expensive.

Here's the predicate that makes the lazy list:

:- lib(ic). % load IC library (constraints over intervals)

% make new lazy list
% lazy_list(-,-,-,++,++)
lazy_list(List, Store, E, Pred, InitState) :-
    store_create(Store),
    E #>= 0,
    suspend(generate_nth_el(E, 0, List, Store, Pred, InitState), 3, E->ic:min).

List is the new list, Store is a handle of a store, Pred the functor of the predicate that generates the list members, InitState the initial state, and E the variable that is used to trigger the list creation.

New list members are created when the lower bound of E is raised. In that case, generate_nth_el/6 is woken:

generate_nth_el(E, Last, List, Store, Pred, LastState) :-
    This is Last+1,
    List = [NextVal|Tail],
    Goal =.. [Pred, LastState, NextState, NextVal],
    call(Goal),  % create next element
    store_set(Store, This, NextVal), % add next element to store
    get_min(E, MinE),
    (
        This == MinE
    ->
        % when reached the lower bound, suspend again
        suspend(generate_nth_el(E, This, Tail, Store, Pred, NextState), 3, E->ic:min)
    ;
        % else continue with extending the list
        generate_nth_el(E, This, Tail, Store, Pred, NextState)
    ).

The predicate generate_nth_el/6 is purely for internal use, and should not be called by the user.

Finally, here's a predicate to retrieve the n-th element:

% nth_el(++,+,++,-)
nth_el(N, E, Store, V) :-
    N > 0,
    E #>= N,                % force creation of new elements
    store_get(Store, N, V). % get nth element from store.

It adds a constraint that E must be at least as large as N. If this increases the lower bound, the list is extended. The n-th element is then retrieved from the store.

As an example, here's a version of the fibonacci number predicate with in- and out-states as used in the code above:

fib((0,0), (0,1), 0) :- !.
fib(StateIn, StateOut, B) :-
    StateIn  = (A, B),
    StateOut = (B, C),
    C is A+B.

And here's how it works:

?- lazy_list(List, Store, E, fib, (0,0)),
   nth_el(5, E, Store, F5),
   nth_el(3, E, Store, F3),
   nth_el(10, E, Store, F10).
List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34|_1179]
Store = 'STORE'(16'8ee279a0)
E = E{10 .. 1.0Inf}
F5 = 3
F3 = 1
F10 = 34
There is 1 delayed goal.
Yes (0.00s cpu)

Note, though, that lazy lists are often used in other languages to achieve behaviour that in Prolog can be implemented through simple backtracking.

Shovelhead

Answer 6

% A simple generic solution using SWI-Prolog 

% Returns a prefix of a lazy sequence

prefix(Prefix,PrefixLength,LazySequenceName) :-
    apply(LazySequenceName,[LazySequence]),
    length(Prefix,PrefixLength),
    append(Prefix,_,LazySequence).

% Lazy sequence of natural numbers

nat(LazySequence) :- 
    nat(0,LazySequence).
nat(Item,LazySequence) :-
    freeze(LazySequence,
      (LazySequence=[Item|Rest], Next is Item+1, nat(Next,Rest)) ).

% Lazy sequence of Fibonacci numbers

fib(LazySequence) :- 
    fib(1,0,LazySequence).
fib(A,B,LazySequence) :-
    freeze(LazySequence,
       (LazySequence=[C|Rest], C is A+B, fib(B,C,Rest))).

% Examples

test :-
    prefix(N,10,nat), format('Ten first natural numbers: ~w~n',[N]),
    prefix(F,10,fib), format('Ten first Fibonacci numbers: ~w~n',[F]),
    fib(S), nth1(100,S,X), format('The hundredth Fibonacci number: ~w~n',[X]).

Chace