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

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

137lazy_list(Next, List) :- 138 put_attr(List, lazy_lists, lazy_list(Next, _)). 139 140attr_unify_hook(State, Value) :- 141 State = lazy_list(Next, Read), 142 ( var(Read) 143 -> call(Next, NewList, Tail), 144 ( Tail == [] 145 -> nb_setarg(2, State, NewList) 146 ; lazy_list(Next, Tail), 147 nb_setarg(2, State, NewList) 148 ), 149 arg(2, State, Value) 150 ; Value = Read 151 ). 152 153attribute_goals(X) --> 154 { get_attr(X, lazy_lists, lazy_list(Next, _)) }, 155 [lazy_list(Next, X)].

187lazy_list(Next, State0, List) :- 188 lazy_list(lazy_state(Next, s(State0)), List). 189 190lazy_state(Pred, LState, [H|T], T) :- 191 LState = s(State0), 192 call(Pred, State0, State1, H), 193 !, 194 nb_setarg(1, LState, State1). 195lazy_state(_, _, [], []). 196 197 198 /******************************* 199 * OPERATIONS ON LAZY LISTS * 200 *******************************/

206lazy_list_materialize(List) :- 207 '$skip_list'(_, List, Tail), 208 ( var(Tail), 209 Tail = [_|T2] 210 -> lazy_list_materialize(T2) 211 ; Tail = [] 212 -> true 213 ; type_error(list, Tail) 214 ).

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

311lazy_list_iterator(Iterator, Next, GetNext, TestEnd) :- 312 throw(error(context_error(nodirective, 313 lazy_list_iterator(Iterator, Next, 314 GetNext, TestEnd)), 315 _)).

339lazy_read_terms(Stream, Options, List, Tail) :- 340 select_option(chunk(N), Options, ReadOptions, 10), 341 lazy_read_terms_(Stream, ReadOptions, N, List, Tail). 342 343:- lazy_list_iterator(lazy_read_terms_(Stream, Options), Term, 344 read_term(Stream, Term, Options), 345 Term == end_of_file).

357lazy_read_lines(Stream, Options, List, Tail) :- 358 option(chunk(ChunkSize), Options, 10), 359 option(as(Type), Options, string), 360 must_be(positive_integer, ChunkSize), 361 must_be(oneof([atom,string,codes,chars]), Type), 362 lazy_read_lines(Type, Stream, ChunkSize, List, Tail). 363 364lazy_read_lines(string, Stream, ChunkSize, List, Tail) :- 365 lazy_read_string_lines(Stream, ChunkSize, List, Tail). 366lazy_read_lines(atom, Stream, ChunkSize, List, Tail) :- 367 lazy_read_atom_lines(Stream, ChunkSize, List, Tail). 368lazy_read_lines(codes, Stream, ChunkSize, List, Tail) :- 369 lazy_read_codes_lines(Stream, ChunkSize, List, Tail). 370lazy_read_lines(chars, Stream, ChunkSize, List, Tail) :- 371 lazy_read_chars_lines(Stream, ChunkSize, List, Tail). 372 373:- lazy_list_iterator(lazy_read_string_lines(Stream), Line, 374 read_line_to_string(Stream, Line), 375 Line == end_of_file). 376:- lazy_list_iterator(lazy_read_codes_lines(Stream), Line, 377 read_line_to_codes(Stream, Line), 378 Line == end_of_file). 379:- lazy_list_iterator(lazy_read_chars_lines(Stream), Line, 380 read_line_to_chars(Stream, Line), 381 Line == end_of_file). 382:- lazy_list_iterator(lazy_read_atom_lines(Stream), Line, 383 read_line_to_atom(Stream, Line), 384 Line == -1). 385 386read_line_to_chars(Stream, Chars) :- 387 read_line_to_string(Stream, String), 388 ( String == end_of_file 389 -> Chars = String 390 ; string_chars(String, Chars) 391 ). 392 393read_line_to_atom(Stream, Atom) :- 394 read_line_to_string(Stream, String), 395 ( String == end_of_file 396 -> Atom = -1 397 ; atom_string(Atom, String) 398 ).

417lazy_message_queue(Queue, Options, List, Tail) :- 418 select_option(chunk(ChunkSize), Options, QueueOptions, 1), 419 lazy_message_queue_(Queue, QueueOptions, ChunkSize, List, Tail). 420 421:- lazy_list_iterator(lazy_message_queue_(Queue, Options), Message, 422 thread_get_message(Queue, Message, Options), 423 fail).

448lazy_findall(Templ, Goal, List) :- 449 lazy_findall(1, Templ, Goal, List). 450lazy_findall(Chunk, Templ, Goal, List) :- 451 engine_create(Templ, Goal, Engine), 452 lazy_list(lazy_engine_next(Engine, Chunk), List). 453 454 455 /******************************* 456 * SANDBOX * 457 *******************************/ 458 459:- multifile 460 sandbox:safe_meta_predicate/1. 461 462sandbox:safe_meta_predicate(lazy_lists:lazy_findall/3). 463sandbox:safe_meta_predicate(lazy_lists:lazy_findall/4). 464sandbox:safe_meta_predicate(lazy_lists:lazy_list/2). 465sandbox:safe_meta_predicate(lazy_lists:lazy_list/3)