1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2016-2025, VU University Amsterdam 7 CWI Amsterdam 8 SWI-Prolog Solutions b.v. 9 All rights reserved. 10 11 Redistribution and use in source and binary forms, with or without 12 modification, are permitted provided that the following conditions 13 are met: 14 15 1. Redistributions of source code must retain the above copyright 16 notice, this list of conditions and the following disclaimer. 17 18 2. Redistributions in binary form must reproduce the above copyright 19 notice, this list of conditions and the following disclaimer in 20 the documentation and/or other materials provided with the 21 distribution. 22 23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 31 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 33 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 POSSIBILITY OF SUCH DAMAGE. 35*/ 36 37:- module(lazy_lists, 38 [ lazy_list/2, % :Next, -List 39 lazy_list/3, % :Next, +State0, -List 40 % Utilities 41 lazy_list_materialize/1, % ?List 42 lazy_list_length/2, % +List, -Len 43 44 lazy_findall/3, % ?Templ, :Goal, -List 45 lazy_findall/4, % +ChunkSize, ?Templ, :Goal, -List 46 % Interators 47 lazy_get_codes/4, % +Stream, +N, -List, -Tail 48 lazy_read_terms/4, % +Stream, +Options, -List, -Tail 49 lazy_read_lines/4, % +Stream, +Options, -List, -Tail 50 51 lazy_message_queue/4, % +Queue, +Options, -List, -Tail 52 lazy_engine_next/4, % +Engine, +N, -List, -Tail 53 54 lazy_list_iterator/4 % +Iterator, -Next, :GetNext, 55 % :TestEnd 56 ]). 57:- autoload(library(error), 58 [type_error/2,instantiation_error/1,must_be/2]). 59:- autoload(library(lists),[append/3]). 60:- autoload(library(option),[select_option/4,option/3]). 61:- autoload(library(readutil), 62 [read_line_to_string/2,read_line_to_codes/2]). 63 64 65:- meta_predicate 66 lazy_list(2, -), 67 lazy_list(3, +, -), 68 lazy_findall(?, 0, -), 69 lazy_findall(+, ?, 0, -).

Lazy list handling

This module builds a lazy list from a predicate that fetches a slice of this list. In addition it provides interactors (slice constructors) for several common use cases for lazy lists, such as reading objects of several sizes from files (characters, lines, terms), reading messages from message queues and reading answers from engines.

Lazy lists are lists that end in a constraint. Trying to unify the constraint forces the next slice of the list to be fetched and added to the list.

The typical use case for lazy lists is to run a DCG grammar on it. For example, an agent may be listening on a socket and turn the line-based message protocol into a list using the fragment below.

        ...,
        tcp_open(Socket, Read, Write),
        lazy_list(lazy_read_lines(Read, [as(codes)]), List),
        phrase(action, List).

Typically, the iterator works on a globally allocated object that is not always subject to garbage collection. In such cases, the skeleton usage follows the pattern below:

        setup_call_cleanup(
            <open resource>(R),
            (  lazy_list(<iterator>(R), List),
               process_list(List)
            ),
            <close resource>(R))

This is rather unfortunately, but there is no way we can act on the fact that List is no further accessed. In some cases, e.g., message queues or engines, the resource is subject to (atom) garbage collection. */

112:- predicate_options(lazy_read_terms/4, 2, 113 [ chunk(positive_integer), 114 pass_to(read_term/3, 3) 115 ]). 116:- predicate_options(lazy_read_lines/4, 2, 117 [ chunk(positive_integer), 118 as(oneof([atom,string,codes,chars])) 119 ]). 120:- predicate_options(lazy_message_queue/4, 2, 121 [ chunk(positive_integer), 122 pass_to(thread_get_message/3, 3) 123 ]).

138lazy_list(Next, List) :- 139 put_attr(List, lazy_lists, lazy_list(Next, _)). 140 141% (*) We need a copy of the list where the copy must include the new 142% attributed variable to avoid that backtracking makes the list 143% non-lazy. We do want to avoid copying `Next`. So, we add a dummy and 144% then replace this using nb_linkarg/3 with our Next. 145 146attr_unify_hook(State, Value) :- 147 State = lazy_list(Next, Read), 148 ( var(Read) 149 -> call(Next, NewList, Tail), 150 ( Tail == [] 151 -> nb_setarg(2, State, NewList) 152 ; put_attr(Tail, lazy_lists, lazy_list(dummy, _)), % See (*) 153 nb_setarg(2, State, NewList), 154 arg(2, State, NewListCP), 155 '$skip_list'(_, NewListCP, TailCP), 156 get_attr(TailCP, lazy_lists, LazyList), 157 nb_linkarg(1, LazyList, Next) 158 ), 159 arg(2, State, Value) 160 ; Value = Read 161 ). 162 163attribute_goals(X) --> 164 { get_attr(X, lazy_lists, lazy_list(Next, _)) }, 165 [lazy_list(Next, X)].

197lazy_list(Next, State0, List) :- 198 lazy_list(lazy_state(Next, s(State0)), List). 199 200lazy_state(Pred, LState, [H|T], T) :- 201 LState = s(State0), 202 call(Pred, State0, State1, H), 203 !, 204 nb_setarg(1, LState, State1). 205lazy_state(_, _, [], []). 206 207 208 /******************************* 209 * OPERATIONS ON LAZY LISTS * 210 *******************************/

216lazy_list_materialize(List) :- 217 '$skip_list'(_, List, Tail), 218 ( var(Tail), 219 Tail = [_|T2] 220 -> lazy_list_materialize(T2) 221 ; Tail = [] 222 -> true 223 ; type_error(list, Tail) 224 ).

232lazy_list_length(List, Len) :- 233 lazy_list_length(List, 0, Len). 234 235lazy_list_length(List, L0, L) :- 236 !, 237 '$skip_list'(N, List, Tail), 238 ( var(Tail), 239 Tail = [_|T2] 240 -> L1 is L0+N+1, 241 lazy_list_length(T2, L1, L) 242 ; Tail = [] 243 -> L is L0+N 244 ; type_error(list, Tail) 245 ). 246 247 248 /******************************* 249 * INTERATORS * 250 *******************************/ 251 252lazy_list_expand_handler( 253 lazy_list_iterator(Handler, Next, Get1, TestEnd), 254 Clauses) :- 255 negate(TestEnd, NotTestEnd), 256 extend_goal(Handler, [N, List, Tail], Head), 257 extend_goal(Handler, [N2,T,Tail], Recurse), 258 general_goal(Handler, Handler2), 259 extend_goal(Handler2, [_, Tail,Tail], Head2), 260 Clauses = [ (Head :- 261 succ(N2, N), !, 262 ( Get1, 263 NotTestEnd 264 -> List = [Next|T], 265 Recurse 266 ; List = [], 267 Tail = [] 268 )), 269 (Head2) 270 ]. 271 272negate(A==B, A\==B) :- !. 273negate(fail, true) :- !. 274negate(false, true) :- !. 275negate(Goal, \+ Goal). 276 277extend_goal(Var, _, _) :- 278 var(Var), 279 !, 280 instantiation_error(Var). 281extend_goal(M:G, Args, M:GX) :- 282 !, 283 extend_goal(G, Args, GX). 284extend_goal(Name, Args, GX) :- 285 atom(Name), 286 !, 287 compound_name_arguments(GX, Name, Args). 288extend_goal(G, XArgs, GX) :- 289 compound_name_arguments(G, Name, Args0), 290 append(Args0, XArgs, Args), 291 compound_name_arguments(GX, Name, Args). 292 293general_goal(Var, Var) :- 294 var(Var), 295 !. 296general_goal(M:G, M:GG) :- 297 !, 298 general_goal(G, GG). 299general_goal(Atom, Atom) :- 300 atom(Atom), 301 !. 302general_goal(G, GG) :- 303 !, 304 compound_name_arity(G, Name, Arity), 305 compound_name_arity(GG, Name, Arity). 306 307:- multifile 308 system:term_expansion/2. 309 310system:term_expansion((:- lazy_list_iterator(It, One, GetNext, TestEnd)), 311 Expanded) :- 312 lazy_list_expand_handler( 313 lazy_list_iterator(It, One, GetNext, TestEnd), 314 Expanded).

321lazy_list_iterator(Iterator, Next, GetNext, TestEnd) :- 322 throw(error(context_error(nodirective, 323 lazy_list_iterator(Iterator, Next, 324 GetNext, TestEnd)), 325 _)).

349lazy_read_terms(Stream, Options, List, Tail) :- 350 select_option(chunk(N), Options, ReadOptions, 10), 351 lazy_read_terms_(Stream, ReadOptions, N, List, Tail). 352 353:- lazy_list_iterator(lazy_read_terms_(Stream, Options), Term, 354 read_term(Stream, Term, Options), 355 Term == end_of_file).

367lazy_read_lines(Stream, Options, List, Tail) :- 368 option(chunk(ChunkSize), Options, 10), 369 option(as(Type), Options, string), 370 must_be(positive_integer, ChunkSize), 371 must_be(oneof([atom,string,codes,chars]), Type), 372 lazy_read_lines(Type, Stream, ChunkSize, List, Tail). 373 374lazy_read_lines(string, Stream, ChunkSize, List, Tail) :- 375 lazy_read_string_lines(Stream, ChunkSize, List, Tail). 376lazy_read_lines(atom, Stream, ChunkSize, List, Tail) :- 377 lazy_read_atom_lines(Stream, ChunkSize, List, Tail). 378lazy_read_lines(codes, Stream, ChunkSize, List, Tail) :- 379 lazy_read_codes_lines(Stream, ChunkSize, List, Tail). 380lazy_read_lines(chars, Stream, ChunkSize, List, Tail) :- 381 lazy_read_chars_lines(Stream, ChunkSize, List, Tail). 382 383:- lazy_list_iterator(lazy_read_string_lines(Stream), Line, 384 read_line_to_string(Stream, Line), 385 Line == end_of_file). 386:- lazy_list_iterator(lazy_read_codes_lines(Stream), Line, 387 read_line_to_codes(Stream, Line), 388 Line == end_of_file). 389:- lazy_list_iterator(lazy_read_chars_lines(Stream), Line, 390 read_line_to_chars(Stream, Line), 391 Line == end_of_file). 392:- lazy_list_iterator(lazy_read_atom_lines(Stream), Line, 393 read_line_to_atom(Stream, Line), 394 Line == -1). 395 396read_line_to_chars(Stream, Chars) :- 397 read_line_to_string(Stream, String), 398 ( String == end_of_file 399 -> Chars = String 400 ; string_chars(String, Chars) 401 ). 402 403read_line_to_atom(Stream, Atom) :- 404 read_line_to_string(Stream, String), 405 ( String == end_of_file 406 -> Atom = -1 407 ; atom_string(Atom, String) 408 ).

427lazy_message_queue(Queue, Options, List, Tail) :- 428 select_option(chunk(ChunkSize), Options, QueueOptions, 1), 429 lazy_message_queue_(Queue, QueueOptions, ChunkSize, List, Tail). 430 431:- lazy_list_iterator(lazy_message_queue_(Queue, Options), Message, 432 thread_get_message(Queue, Message, Options), 433 fail).

458lazy_findall(Templ, Goal, List) :- 459 lazy_findall(1, Templ, Goal, List). 460lazy_findall(Chunk, Templ, Goal, List) :- 461 engine_create(Templ, Goal, Engine), 462 lazy_list(lazy_engine_next(Engine, Chunk), List). 463 464 465 /******************************* 466 * SANDBOX * 467 *******************************/ 468 469:- multifile 470 sandbox:safe_meta_predicate/1. 471 472sandbox:safe_meta_predicate(lazy_lists:lazy_findall/3). 473sandbox:safe_meta_predicate(lazy_lists:lazy_findall/4). 474sandbox:safe_meta_predicate(lazy_lists:lazy_list/2). 475sandbox:safe_meta_predicate(lazy_lists:lazy_list/3). 476 477 /******************************* 478 * SUPPRESS AUTOLOAD WARNINGS * 479 *******************************/ 480 481'$nowarn_autoload'(_, _)