Prolog 中的惰性列表？

发布于 2024-12-27 05:56:13 字数 109 浏览 1 评论 0原文

Prolog 中是否可以有惰性列表？类似以下内容：

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

尽管这显然并不像所写的那样工作。

原文

Is it possible to have lazy lists in Prolog? Something like the following:

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

Although this obviously doesn't work as it's written.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

太阳公公是暖光 2025-01-03 05:56:13

这是 Prolog 中使用“生成器习惯用法”的惰性列表汉明数。

我想得越多，我就越觉得 Haskell 的惰性列表只是开放式的（又名 “差异”< /a>) Prolog 列表，而 corecursion 只是一个奇特的的名称尾递归模 cons 的自上而下列表构建。此外，Haskell 是隐式设置一次语言，而 Prolog（非回溯子集）显式设置一次。

这种令人费解的“喜结连理”技术实际上只不过是笨拙地实现了后期变量实例化。而且，Haskell 中的一切都是生成器，记忆存储是通用访问中介。但无论如何，

以下实现了 head-forced 流（SICP 类型），其中如果一个元素被强制，列表中它前面的所有元素也都已经被强制。

:- 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 a 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 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.

% (* testing ... *)
2 ?- main(1000).
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
[51200000,51840000]
true.

很简单，嗯？对于 ones 我们只是定义

next( ones, 1, ones).

那里没有（变化）状态，然后将其称为例如

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

对于 Haskell 式的整数枚举，我们定义

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

并调用 take(8, fromBy(3, 2), A-[], _) 得到A = [3, 5, 7, 9, 11, 13, 15, 17]. 斐波那契数列简单

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

来说就是take(20, fib(0,1), FS-[], _)，定义了一个包含 20 个元素的斐波那契数列表 FS。

记忆斐波那契序列

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).

现在从以前使用的生成器重新启动不会重新计算数字，而是会重新获取以前计算的序列成员（如果有）。这种内部共享的开放式存储很容易被误用，即错误的实例化（编辑： 其尚未设置的最后一个尾指针变量）。这就是take为其答案构建新存储而不是暴露内部存储的原因。

Here's a lazy-list Hamming numbers in Prolog using a "generator idiom".

The more I think about it the more it seems to me the lazy lists of Haskell are just open-ended (a.k.a. "difference") lists of Prolog, and corecursion just a fancy name for the top-down list building of tail recursion modulo cons. Also, Haskell is implicitly set once language, while (non-backtracking subset of) Prolog is explicitly set once.

The mind-mangling "tying-the-knot" technique is actually nothing more than awkwardly implemented late variable instantiation. And, everything is a generator in Haskell, with memoizing storage a universal access mediator. But anyway,

The following implements the head-forced streams (of SICP variety), where if an element is forced, all the elements preceding it in the list are already forced as well.

:- 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 a 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 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.

% (* testing ... *)
2 ?- main(1000).
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
[51200000,51840000]
true.

Simple, eh? For ones we just define

next( ones, 1, ones).

as there is no (change in) state there, and then call it as e.g.

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

For Haskell-like integer enumerations we define

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

and call take(8, fromBy(3,2), A-[], _) to get A = [3, 5, 7, 9, 11, 13, 15, 17]. Fibonacci sequence is simply

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

With take(20, fib(0,1), FS-[], _), a 20-elements list FS of Fibonacci numbers is defined.

Memoizing Fibonacci sequence is

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).

Now restarting from a previously used generator won't recalculate the numbers but instead will re-fetch the previously calculated members of the sequence, where available. This internal shared open-ended storage is fragile to misuse i.e. wrongful instantiation (edit: of its not-yet-set last tail pointer variable). This is the reason for take building new storage for its answer, instead of exposing the internal one.

回复收藏 0 原文

∞琼窗梦回ˉ 2025-01-03 05:56:13

Markus Triska 放置在此处在公共领域一些代码值得研究：

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

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

文档的标题 (prost，用于 Prolog 流）可能会使文档有点难以找到，但很有意义。
引用上面的话：

这里，“流”的含义是“序列”、“延迟列表”、
计算机结构和解释中的“惰性列表”等
程序，不是 Prolog 输入/输出流意义上的程序。

Markus Triska placed here in public domain some code worth to study:

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

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

The title of the document (prost, for Prolog streams) maybe make the document a bit difficult to find, but make sense.
Quoting from the above:

Here, "stream" is used in the sense of "sequence", "delayed list",
"lazy list" etc. as in Structure and Interpretation of Computer
Programs, not in the sense of a Prolog input/output stream.

回复收藏 0 原文

一桥轻雨一伞开 2025-01-03 05:56:13

是的，Prolog 中可以有惰性列表。这是使用 freeze/2 的无限惰性列表。

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

在顶层使用它看起来像这样：

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

您可能还会喜欢 list_util pack< /a> （对于 SWI-Prolog）包含几个惰性列表谓词。

Yes, it's possible to have lazy lists in Prolog. Here's an infinite, lazy list of ones using freeze/2.

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

Using it at the top-level looks like this:

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

You might also enjoy the list_util pack (for SWI-Prolog) which contains several lazy list predicates.

回复收藏 0 原文

桃扇骨 2025-01-03 05:56:13

好吧，您可以将一个无限列表（或其他任何内容）定义为：

H = [1|H].

use:

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

当然，如果您想要一个素数/斐波那契/任何不那么微不足道的东西的列表，这将不起作用。

你可以编写一些谓词来模拟惰性列表的行为，但我不认为有任何库/标准化方法可以做到这一点（至少在 swi-prolog 中）（:( haskell 的惰性列表是一个很好的功能）。

well, you could define an infinite list of ones (or anything else) as:

H = [1|H].

use:

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

Of course, this won't work if you want a list of primes/fibonacci/anything not so trivial.

You could write some predicates that would emulate the behavior of a lazy list but I do not think that there are any libraries/standardized way to do it (at least in swi-prolog) (:( haskell's lazy list is such a nice feature).

回复收藏 0 原文

甲如呢乙后呢 2025-01-03 05:56:13

这是对惰性列表的稍微不同的看法，它使用暂停。它是用 ECLiPSe 编写的，但您应该能够在其他版本的 Prolog 中复制它。

它使用属性变量来记录惰性列表的当前长度，并在提高变量域的下限时构造列表的新成员。

我假设为构造列表成员而执行的谓词的数量为 3，并且三个参数是：in-state、out-state 和 result。不过，很容易使示例适应一般目标。

我还使用了“store”，它是一种非逻辑哈希存储，以便通过避免迭代列表来快速检索列表的第 n 个元素。使用存储并不是必需的，但一次又一次地迭代长列表可能会很昂贵。

这是创建惰性列表的谓词：

:- 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 是新列表，Store 是存储的句柄，Pred 谓词的函子生成列表成员，InitState 初始状态，以及 E 用于触发列表创建的变量。

当 E 的下限升高时，将创建新的列表成员。在这种情况下，generate_nth_el/6 被唤醒：

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)
    ).

谓词 generate_nth_el/6 纯粹供内部使用，不应由用户调用。

最后，这是一个检索第 n 个元素的谓词：

% 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.

它添加了一个约束，即 E 必须至少与 N 一样大。如果这增加了下限，则列表将被扩展。然后从存储中检索第 n 个元素。

作为一个例子，下面是上面代码中使用的斐波那契数谓词的版本，其中包含入状态和出状态：

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

下面是它的工作原理：

?- 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)

但请注意，惰性列表通常在其他语言中用于实现以下行为： Prolog可以通过简单的回溯来实现。

Here's a slightly different take on lazy lists, which uses suspensions. It's written in ECLiPSe, but you should be able to replicate it in other flavours of Prolog.

It uses an attributed variable to record the current length of the lazy list, and constructs new members of the list when the lower bound of the variable's domain is raised.

I assume that the predicate that is executed to construct list members has arity 3, and the three arguments are: in-state, out-state, and result. It's easy to adapt the example to general goals, though.

I also used a "store", which is a non-logical hash storage, in order to quickly retrieve the n-th element of the list by avoiding to iterate over the list. Using a store is not essential, but iterating over a long list again and again can be expensive.

Here's the predicate that makes the lazy list:

:- 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 is the new list, Store is a handle of a store, Pred the functor of the predicate that generates the list members, InitState the initial state, and E the variable that is used to trigger the list creation.

New list members are created when the lower bound of E is raised. In that case, generate_nth_el/6 is woken:

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)
    ).

The predicate generate_nth_el/6 is purely for internal use, and should not be called by the user.

Finally, here's a predicate to retrieve the n-th element:

% 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.

It adds a constraint that E must be at least as large as N. If this increases the lower bound, the list is extended. The n-th element is then retrieved from the store.

As an example, here's a version of the fibonacci number predicate with in- and out-states as used in the code above:

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

And here's how it works:

?- 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)

Note, though, that lazy lists are often used in other languages to achieve behaviour that in Prolog can be implemented through simple backtracking.

回复收藏 0 原文

尤怨 2025-01-03 05:56:13

% 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]).

% 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]).

回复收藏 0 原文

~没有更多了~