listing - Listas perezosas en Prolog?

prolog listing example

Question

¿Es posible tener listas perezosas en Prolog? Algo como lo siguiente:

ones([1 | Y]) :- ones(Y).

Aunque esto obviamente no funciona como está escrito.

Answer 1

Aquí hay una lista perezosa de números de Hamming en Prolog usando un "lenguaje de generador".

Cuanto más lo pienso, más me parece que las listas perezosas de Haskell son solo listas abiertas (también conocidas como "diferencia") de Prolog, y corecursion solo un nombre elegante para la construcción de lista de arriba hacia abajo de la recursión de la cola. . Además, Haskell está implícitamente establecido una vez en el idioma, mientras que (el subconjunto que no retrocede) de Prolog se establece explícitamente una vez.

La técnica de "atar el nudo" para destrozar el cerebro no es en realidad nada más que una instanciación variable tardía implementada de manera incómoda. Y, todo es un generador en Haskell, con almacenamiento de memoria un mediador de acceso universal. Pero de todos modos,

Lo siguiente implementa los flujos forzados en la cabeza (de la variedad SICP), donde si un elemento es forzado, todos los elementos que lo preceden en la lista también están forzados.

:- dynamic( next/3 ).

%// collect N elements produced by a generator in a row: 
take( 0, Next, Z-Z, Next):- !.
take( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

%// a "generator" provides specific `next/3` implementation 
next( hamm( A2,B,C3,D,E5,F,[H|G] ), H, hamm(X,U,Y,V,Z,W,G) ):- 
  H is min(A2, min(C3,E5)),
  (   A2 =:= H -> B=[N2|U], X is N2*2 ; (X,U)=(A2,B) ),
  (   C3 =:= H -> D=[N3|V], Y is N3*3 ; (Y,V)=(C3,D) ),
  (   E5 =:= H -> F=[N5|W], Z is N5*5 ; (Z,W)=(E5,F) ).

%// Hamming numbers generator''s init state:
mkHamm( hamm(1,X,1,X,1,X,X) ).       

%// A calling example: main( +Number)
main(N) :- 
    mkHamm(G), take(20,G,A-[],_),          write(A), nl,  
    take(N-1,G,_,G2), take(2,G2,B-[],_),   write(B), nl.

Simple, ¿eh? Para ones que acabamos de definir

next( ones, 1, ones).

ya que no hay (cambiar) el estado allí, y luego llámelo como, por ejemplo,

take(N, ones, A-[], _), writeln(A).

Para las enumeraciones de enteros similares a Haskell definimos

next( fromBy(F,B), F, fromBy(F2,B)):- F2 is F+B.

y llame a take(8, fromBy(3,2), A-[], _) para obtener A = [3, 5, 7, 9, 11, 13, 15, 17]. La secuencia de Fibonacci es simplemente

next( fib(A,B), A, fib(B,C)):- C is A+B.

Con take(20, fib(0,1), FS-[], _) , se define una lista de 20 elementos FS de números de Fibonacci.

La secuencia de Fibonacci que memoriza es

mkFibs( fibs([0|L], L) ):- L=[1|_].
next( fibs([A|L], L), A, fibs(L, L2) ):- 
    L=[B|L2], L2=[C|_], (var(C)-> C is A+B ; true).

Ahora, reiniciar desde un generador utilizado anteriormente no volverá a calcular los números, sino que volverá a recuperar los miembros de la secuencia calculados anteriormente, cuando estén disponibles. Este almacenamiento interno compartido de extremo abierto es frágil debido a un mal uso, es decir, a la creación de instancias erróneas ( edición: de su última variable de puntero de cola aún no establecida ). Esta es la razón por la que take crear un nuevo almacenamiento para su respuesta, en lugar de exponer el interno.

Answer 2

Aquí hay una versión ligeramente diferente de las listas perezosas, que utiliza suspensiones. Está escrito en ECLiPSe, pero debería poder replicarlo en otros sabores de Prolog.

Utiliza una variable atribuida para registrar la longitud actual de la lista diferida y construye nuevos miembros de la lista cuando se levanta el límite inferior del dominio de la variable.

Supongo que el predicado que se ejecuta para construir miembros de la lista tiene aridad 3, y los tres argumentos son: in-state, out-state y result. Sin embargo, es fácil adaptar el ejemplo a los objetivos generales.

También utilicé una "tienda", que es un almacenamiento de hash no lógico, para recuperar rápidamente el elemento n-th de la lista evitando iterar sobre la lista. Usar una tienda no es esencial, pero iterar una larga lista una y otra vez puede ser costoso.

Aquí está el predicado que hace la lista perezosa:

:- lib(ic). % load IC library (constraints over intervals)

% make new lazy list
% lazy_list(-,-,-,++,++)
lazy_list(List, Store, E, Pred, InitState) :-
    store_create(Store),
    E #>= 0,
    suspend(generate_nth_el(E, 0, List, Store, Pred, InitState), 3, E->ic:min).

List es la nueva lista, Store es un identificador de una tienda, Pred el functor del predicado que genera los miembros de la lista, InitState el estado inicial y E la variable que se utiliza para desencadenar la creación de la lista.

Los nuevos miembros de la lista se crean cuando se levanta el límite inferior de E En ese caso, el generate_nth_el/6 se despierta:

generate_nth_el(E, Last, List, Store, Pred, LastState) :-
    This is Last+1,
    List = [NextVal|Tail],
    Goal =.. [Pred, LastState, NextState, NextVal],
    call(Goal),  % create next element
    store_set(Store, This, NextVal), % add next element to store
    get_min(E, MinE),
    (
        This == MinE
    ->
        % when reached the lower bound, suspend again
        suspend(generate_nth_el(E, This, Tail, Store, Pred, NextState), 3, E->ic:min)
    ;
        % else continue with extending the list
        generate_nth_el(E, This, Tail, Store, Pred, NextState)
    ).

El predicado generate_nth_el/6 es puramente para uso interno, y no debe ser llamado por el usuario.

Finalmente, aquí hay un predicado para recuperar el elemento n-th:

% nth_el(++,+,++,-)
nth_el(N, E, Store, V) :-
    N > 0,
    E #>= N,                % force creation of new elements
    store_get(Store, N, V). % get nth element from store.

Agrega una restricción de que E debe ser al menos tan grande como N Si esto aumenta el límite inferior, la lista se extiende. El elemento n-th se recupera de la tienda.

Como ejemplo, aquí hay una versión del predicado del número de fibonacci con estados internos y externos, tal como se utiliza en el código anterior:

fib((0,0), (0,1), 0) :- !.
fib(StateIn, StateOut, B) :-
    StateIn  = (A, B),
    StateOut = (B, C),
    C is A+B.

Y así es como funciona:

?- lazy_list(List, Store, E, fib, (0,0)),
   nth_el(5, E, Store, F5),
   nth_el(3, E, Store, F3),
   nth_el(10, E, Store, F10).
List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34|_1179]
Store = ''STORE''(16''8ee279a0)
E = E{10 .. 1.0Inf}
F5 = 3
F3 = 1
F10 = 34
There is 1 delayed goal.
Yes (0.00s cpu)

Sin embargo, tenga en cuenta que las listas perezosas a menudo se usan en otros idiomas para lograr un comportamiento que en Prolog puede implementarse a través de un seguimiento simple.

Answer 3

Bueno, podrías definir una lista infinita de unidades (o cualquier otra cosa) como:

H = [1|H].

utilizar:

4 ?- H=[1|H], [A1|T1] = H, [A2|T2] = T1, T1=T2.
H = [1|**],
A1 = 1,
T1 = [1|**],
A2 = 1,
T2 = [1|**].

Por supuesto, esto no funcionará si desea una lista de números primos / fibonacci / algo no tan trivial.

Podría escribir algunos predicados que emularían el comportamiento de una lista perezosa, pero no creo que haya ninguna biblioteca / forma estandarizada de hacerlo (al menos en swi-prolog) (:( la lista perezosa de haskell es una característica muy agradable) .

Answer 4

Markus Triska colocó aquí en dominio público un código que vale la pena estudiar:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Prolog stream/lazy list demonstration

   Written 2005 by Markus Triska ([email protected])
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

El título del documento ( prost , para las transmisiones Prolog) puede hacer que el documento sea un poco difícil de encontrar, pero tiene sentido. Citando de lo anterior:

Aquí, "flujo" se usa en el sentido de "secuencia", "lista retrasada", "lista lenta", etc., como en Estructura e interpretación de programas de computadora, no en el sentido de un flujo de entrada / salida de Prolog.

Answer 5

Sí, es posible tener listas perezosas en Prolog. Aquí hay una lista infinita y perezosa de las que usan freeze/2 .

ones(L) :-
  freeze(L, (L=[1|T],ones(T)) ).

Usándolo en el nivel superior se ve así:

?- ones(Ones), [A,B,C|_] = Ones.
A = B = C = 1.

También puede disfrutar del paquete list_util (para SWI-Prolog) que contiene varios predicados de listas perezosas.

Answer 6

% A simple generic solution using SWI-Prolog 

% Returns a prefix of a lazy sequence

prefix(Prefix,PrefixLength,LazySequenceName) :-
    apply(LazySequenceName,[LazySequence]),
    length(Prefix,PrefixLength),
    append(Prefix,_,LazySequence).

% Lazy sequence of natural numbers

nat(LazySequence) :- 
    nat(0,LazySequence).
nat(Item,LazySequence) :-
    freeze(LazySequence,
      (LazySequence=[Item|Rest], Next is Item+1, nat(Next,Rest)) ).

% Lazy sequence of Fibonacci numbers

fib(LazySequence) :- 
    fib(1,0,LazySequence).
fib(A,B,LazySequence) :-
    freeze(LazySequence,
       (LazySequence=[C|Rest], C is A+B, fib(B,C,Rest))).

% Examples

test :-
    prefix(N,10,nat), format(''Ten first natural numbers: ~w~n'',[N]),
    prefix(F,10,fib), format(''Ten first Fibonacci numbers: ~w~n'',[F]),
    fib(S), nth1(100,S,X), format(''The hundredth Fibonacci number: ~w~n'',[X]).