Laziness with lazy_lists vs freeze

General
1

Hi

I am exploring lazy constructs in Prolog (and coroutines). I found out about lazy_lists and freeze and I was wondering what is the sense of the community about them.

Here is some code I wrote following the usual patterns seen in functional languages.

fibonacci_Sequence(FS) :-
    lazy_list(fib_seq, state(-, -), FS).

fib_seq(state(-, -), state(0, -), 0) :- !.
fib_seq(state(0, -), state(1, 0), 1) :- !.
fib_seq(state(F2, F1), state(F, F2), F) :-
    F is F1 + F2.

fib(N, F) :-
    fibonacci_sequence(FS),
    nth1(N, FS, F).

… and using freeze.

fibonacci_seqf([1, 1 | FS]) :-
    fib_seqf(1, 1, FS).


fib_seqf(1, 1, F2) :-
    freeze(F2, fib_seqf(1, 2, F2)), !.
fib_seqf(N2, N1, [N | FNS]) :-
    N is N2 + N1,
    freeze(FNS, fib_seqf(N1, N, FNS)), !.


fibf(N, F) :-
    fibonacci_seqf(FS),
    nth0(N, FS, F).

I believe the freeze versions are clearer, but that’s just me.

Apart from that, I was trying to also render in Prolog the following Haskell Fibonacci’s sequence, but I cannot get my head wrapped around it. Any suggestion will be appreciated.

fib = 1 : 1 : zipWith (+) fib (tail fib)

Thank you

all the best

MA

PS I can find the documentation for lazy_lists and freeze using search engines, but I cannot find an obvious entry in the Documentation menu on the web site.

2

library(lazy_lists) has a different purpose: the wakeup produces a permanent extension to the list. This implies that backtracking over the extension to the list does not shrink the list. It is primarily intended to deal with sources that cannot backtrack, such as reading from a non-repositional stream (e.g., a pipe or socket), message queues, etc.

Some libraries are not included in the reference manual. This one probably should. Nevertheless, the search of the website finds it as well.

3

Have you found those examples yet: SWI-Prolog -- Example 1: using tabling for memoizing

The short story is that Prolog implements “enumerating a possibly endless sequence” by providing a sequence of solutions on backtracking. It doesn’t need the lazy list mechanic for that.

Jan above explained how lazy lists are used in Prolog.

4

Hi @Boris

I understand the notion of backtracking for enumeration and I have no problem with that.

But “streams/lazy-lists/delayed-evaluation” is a bit different.

All the best

MA

5

Yes, they are used for different purposes in Prolog as compared to functional languages with lazy evaluation. I was confused about this part.

The “lazy” in Prolog is implemented as “leave a choice point and backtrack to it”. The delayed evaluation (coroutining) with freeze/2 and friends can be useful if you want to evaluate a goal later. Yet again lazy lists (as explained by Jan) use coroutining to make a stream look a bit more like a data structure you can backtrack over.

PS: the “evaluate a goal later” is a bit tricky to put in words. But I won’t repeat the docs.

7

Do the comments and code here provide any further details?

9

I might be totally wrong about that. The way I understood it is indeed, the list gets only longer; and you can backtrack over the list (say, using member/2).

11

I still have a weird feeling. This supposedly refers to the “number of byte of in a multibyte sequence” which is quoted in the docs as six (6).

13

Yes, you are right. The implementation is separate but look very similar.