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:- use_module(library(option)). 57:- use_module(library(lists)). 58:- use_module(library(error)). 59 60:- meta_predicate 61 lazy_list(2, -), 62 lazy_list(3, +, -), 63 lazy_findall(?, 0, -), 64 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. */

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

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

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

202lazy_list_materialize(List) :- 203 '$skip_list'(_, List, Tail), 204 ( var(Tail), 205 Tail = [_|T2] 206 -> lazy_list_materialize(T2) 207 ; Tail = [] 208 -> true 209 ; type_error(list, Tail) 210 ).

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

307lazy_list_iterator(Iterator, Next, GetNext, TestEnd) :- 308 throw(error(context_error(nodirective, 309 lazy_list_iterator(Iterator, Next, 310 GetNext, TestEnd)), 311 _)).

335lazy_read_terms(Stream, Options, List, Tail) :- 336 select_option(chunk(N), Options, ReadOptions, 10), 337 lazy_read_terms_(Stream, ReadOptions, N, List, Tail). 338 339:- lazy_list_iterator(lazy_read_terms_(Stream, Options), Term, 340 read_term(Stream, Term, Options), 341 Term == end_of_file).

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

413lazy_message_queue(Queue, Options, List, Tail) :- 414 select_option(chunk(ChunkSize), Options, QueueOptions, 1), 415 lazy_message_queue_(Queue, QueueOptions, ChunkSize, List, Tail). 416 417:- lazy_list_iterator(lazy_message_queue_(Queue, Options), Message, 418 thread_get_message(Queue, Message, Options), 419 fail).

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