# Lazy processing

**URL:** <https://swi-prolog.discourse.group/t/lazy-processing/8695>\
**Category:** General\
**Created:** [December 26, 2024, 10:50pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695 "2024-12-26T22:50:32Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 26, 2024, 10:50pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/1 "2024-12-26T22:50:32Z")

</div>

Say I’m doing some list processing in the usual way:

```prolog
process([X|Xs], Acc, Final) :-
   do_work(X,Y), !, process(Xs, [Y|Acc], Final).
process([], Final Final).

```

I want to put together a chain like this:

```prolog
process(In, [], Out1),
process(Out1, [], Out2),
process(Out2, [], Final),
foldl(do_more_work, Final, 0, Done).

```

However, I want it all to be lazy. That is, nothing should happen until foldl starts pulling items, and then the work should happen just in time. None of the intermediary lists nor the final list should ever be materialised.

How would you change the process predicate to make this sort of lazy processing possible? I am aware of lazy lists but it is not obvious to me how to convert process to use them.

Please assume process outputs items in the same order as the input (although that is not shown).

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 26, 2024, 11:35pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/3 "2024-12-26T23:35:25Z")

</div>

The problem there is that the source (random) is not a list, and the outputs do not chain lists. Both of these things are an issue for my use case.

Here is something that works for me it seems:

```prolog
do_work([], [], 0) :- false, !.
do_work([X|Xs], Xs, Final) :- Final is X + 1.

test(Total) :-
    lazy_list(do_work, [1,2,3,4], L1),
    lazy_list(do_work, L1, L2),
    lazy_list(do_work, L2, L3),
    foldl([X,V0,V]>>(V is V0+X), L3, 0, Total).

```

It is an example of piping do\_work into itself via list 3 times, and then using foldl to sum up the final output.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 26, 2024, 11:48pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/5 "2024-12-26T23:48:28Z")

</div>

Last thing I need is to be able to chain things which do not return 1-for-1 lists. For example, say at the top I insert [1,2,3] and the next process creates [4,5,6,7,8,9] from that input. I dont see an obvious way to do that with lazy lists or otherwise.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 27, 2024, 7:59am UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/7 "2024-12-27T07:59:54Z")

</div>

I’ve got what i need working with lazy\_list except its useless for the purpose since its about 20x slower than a fully materialized version. I had the same experience when using lazy\_findall/3.

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [December 27, 2024, 10:09am UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/8 "2024-12-27T10:09:43Z")

</div>

Sorry about the long reply 😃

> [@emiruz](#):
>
> Say I’m doing some list processing in the usual way:
> 
> ```prolog
> process([X|Xs], Acc, Final) :-
> do_work(X,Y), !, process(Xs, [Y|Acc], Final).
> process([], Final Final).
> 
> ```

This way you show is slightly unusual. It is impossible to tell without a concrete example, of course, so I am only guessing; still, the usual way would be more like:

```prolog
process([], []).
process([X|Xs], [Y|Ys]) :-
    do_work(X,Y),
    process(Xs, Ys).

```

… which of course is just a maplist:

```prolog
maplist(do_work, Xs, Ys).

```

(And I mean, the two are semantically equivalent, and if you have `library(apply_macros)`, they are also identical).

There could be reasons why this is not good enough, for example

- your `do_work/2` leaves choice points, but you know for certain that you don’t need them;
- you need to reverse the order;
- something else?

By reversing the order, here is a silly example to show what I mean:

```prolog
% your original definition
process([X|Xs], Acc, Final) :-
   do_work(X,Y), !, process(Xs, [Y|Acc], Final).
process([], Final, Final).

do_work(X, Y) :- char_code(X, Y).

```

and now:

```prolog
?- process([a,b,c], [], Ys).
Ys = [99, 98, 97].

```

In comparison:

```prolog
?- maplist(char_code, [a,b,c], Ys).
Ys = [97, 98, 99].

```

You should play around and see that reversing the order of the clauses makes no difference; and that in the specific case of char\_code/2, removing the cut makes not difference. For a non-deterministic predicate “do\_work” it will of course make a difference, you will get all possible combinations. Here is a silly example just to demonstrate:

```prolog
?- maplist(between(0), [1,2], Ys).
Ys = [0, 0] ;
Ys = [0, 1] ;
Ys = [0, 2] ;
Ys = [1, 0] ;
Ys = [1, 1] ;
Ys = [1, 2].

```

* * *

About lazy evaluation. The Prolog alternative to lazy evaluation is backtracking. You can get very far with it. The huge advantage is that it is very fast and needs far less memory; you never need to materialize any lists. The huge disadvantage is that you lose solutions on backtracking. If you can provide a concrete example, it might be easier to judge if you need lists or lazy lists.

---

<div class="post-metadata">

**Author:** ![ridgeworks](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/ridgeworks/32/886_2.png) [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)\
**Post date:** [December 27, 2024, 4:34pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/10 "2024-12-27T16:34:59Z")

</div>

> [@emiruz](#):
>
> I’ve got what i need working with lazy\_list except its useless for the purpose since its about 20x slower than a fully materialized version.

I assume you know that SWI Prolog lazy lists are implemented as constraints using attributed variables, and that unification of attributed variables is going to be orders of magnitude slower that unification that doesn’t involve attributed variables.

To make it concrete, the `attr_unify_hook` that gets invoked whenever a variable with a `lazy_list` attribute is unified:

```prolog
attr_unify_hook(State, Value) :-
    State = lazy_list(Next, Read),
    ( var(Read)
    -> call(Next, NewList, Tail),
        ( Tail == []
        -> nb_setarg(2, State, NewList)
        ; put_attr(Tail, lazy_lists, lazy_list(dummy, _)), % See (*)
            nb_setarg(2, State, NewList),
            arg(2, State, NewListCP),
            '$skip_list'(_, NewListCP, TailCP),
            get_attr(TailCP, lazy_lists, LazyList),
            nb_linkarg(1, LazyList, Next)
        ),
        arg(2, State, Value)
    ; Value = Read
    ).

```

Bottomline: if your focus includes performance, you should understand the tradeoffs involved in using lazy evaluation (i.e. constraints).

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [December 27, 2024, 4:43pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/11 "2024-12-27T16:43:12Z")

</div>

Note that several of the predicates involving lazy lists have a _chunk size_ argument or option. That reduces the number of wakeups. Still, there is quite a bit of work involved in extending the lazy list.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 27, 2024, 6:59pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/12 "2024-12-27T18:59:32Z")

</div>

Thanks, no I didn’t know any of those things, but it all makes sense now.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 27, 2024, 9:47pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/13 "2024-12-27T21:47:12Z")

</div>

[Here](https://github.com/emiruz/adventofcode2024/blob/9197b7c265c89bbf9c542cd08988a5694ee285a4/22.prolog) is an example of me trying to use lazy lists to solve an AoC2024 problem. Ironically the memory blows up at the default limit, I’ve no idea why.

```prolog
% 353,135,695 inferences, 32.161 CPU in 32.171 seconds (100% CPU, 10980304 Lips)
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 2Kb, global: 1.0Gb, trail: 78.1Mb
ERROR: Stack depth: 1,967, last-call: 99%, Choice points: 7
ERROR: In:
ERROR: [1,967] '$attvar':uhook(lazy_lists, <compound lazy_list/2>, [length:1|_2157958])
ERROR: [1,966] '$attvar':call_all_attr_uhooks(<compound att/3>, [length:1|_2157996])
ERROR: [1,965] '$attvar':'$wakeup'(<compound wakeup/3>)
ERROR: [1,964] lists:append([length:1,546], _2158052, [length:1|_2158066])
ERROR: [1,513] user:tree([length:451|_2158100], 1996, _2158094)
ERROR: 
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.

```

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 27, 2024, 11:00pm UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/15 "2024-12-27T23:00:49Z")

</div>

The lazy\_list abstraction is practical. It’d be great if you could write something using a similar contract which can be used to pipe lists into processes and processes into each other via lists.

I’m not really sure how memoisation fits into all this, but I think its strange that a lazy list ends up exploding the memory due to overhead.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [December 29, 2024, 8:46am UTC](https://swi-prolog.discourse.group/t/lazy-processing/8695/18 "2024-12-29T08:46:27Z")

</div>

2 posts were split to a new topic: [Fold over answers](https://swi-prolog.discourse.group/t/fold-over-answers/8697)