Lazy streams (and delimited continuations)

Resources
1

I’m trying to use lazy streams from https://github.com/ptarau/AnswerStreamGenerators to implement a simple example, in which first stream of nats is offset by some number, then the two streams are added up. I tried:

nat(N), drop(3, N, N1), sum(N, N1, S), show(3, S).  % [3, 4, 5].

(The result I was expecting was [0,1,2]+[3,4,5]=[3,5,7]).

I looked under the hood of lazy_streams and I realized that all streams are actually “destructive”, so even a simple show advances the stream forward. What confuses me a bit is the drop/3 predicate, which implies that the original stream is left untouched as it returns another stream.

How can I implement this example with the lazy_streams library?

I also tried to play a bit with delimited continuations to implement lazy streams:

ask(El, Stream, Stream2) :- reset(Stream, El, Stream2).

take(0, _, []) :- !.
take(N, Stream, List) :-
  reset(Stream, El, Cont), 
  (Cont = 0 -> List = [] ; succ(N1, N), take(N1, Cont, Rest), List = [El | Rest]).

drop(0, S, S) :- !.
drop(N, Stream, Stream2) :- succ(N1, N), ask(_, Stream, Stream1), drop(N1, Stream1, Stream2).

nat(From) :- shift(From), succ(From, From1), nat(From1).

map2(Predicate, S1, S2) :- ask(X, S1, E1), ask(Y, S2, E2),
  ((E1 = 0 ; E2 = 0) -> true ; call(Predicate, X, Y, Result), shift(Result), map2(Predicate, E1, E2)).

Using this ad-hoc implementation I was able to solve my contrived example:

N = nat(0), drop(3, N, N1), take(3, map2(plus, N, N1), L). % L = [3, 5, 7]

My second question is: is there some prior art on lazy streams using delimited continuations and why haven’t the authors of lazy_streams used them instead?

2

Will try to ‘answer’ only the last part of the second question…

I think that Paul Tarau work has more to do with high level structure of Prolog programs, in the sense that streams are produced by engines. Delimited continuations are a recent addition to the awesome arsenal of SWI-Prolog, introduced for tabling. Easier (just kidding) ways available before were constrained variables, that for instance power the pureinput library.

3

I’ve made some progress on the delimited continuation streams: https://gist.github.com/esad/c0acd7cb03e5044ff2541a5e77b03c3b

The approach is similar to lazy_streams, but instead using an explicit callable term that represents how next element should be generated, we can rely on continuations instead, allowing for “natural” recursive definitions. A stream in the above implementation is a delimited continuation that calls shift/1 to yield the next element. To end a stream, instead of separate “done” state, we can just not invoke the shift inside the continuation (or even fail), which is captured by the enclosing reset.

One more idea that I had was in regard to the composition. As streams are represented by callable terms, we don’t have to use predicates like drop/3 (that take the original and returns the new stream) - the call itself is a stream. So instead of e.g. drop(3, Input, Output) we can just write Output = drop(3, Input) and pass it to all predicates that expect streams.

Btw. I now think that the initial source of my problem is not inherent to the lazy_streams implementation technique but merely a bug in the library’s drop/3 implementation.

1 Like
4

Thanks for sharing, I would propose your code for inclusion in SWI-Prolog docs.