如何在 Prolog 中模拟软剪辑?
How can I simulate a soft cut in Prolog?
如何模拟 soft cut I *-> T; E 在 ISO Prolog 中?我有副作用,所以我可以不多次调用它。
除了最后一个要求,我认为以下定义有效:
if_(I, T, E) :-
not(not(I)) ->
call((I, T));
call((not(I), E)).
(我实际上在使用 XSB 序言;XSB 的解决方案对我也很有用。)
你的定义没有实现soft-cut语义:当测试成功时,你可以回溯到它。这是有用的控制结构(我用它来实现 Logtalk 中的共同归纳)但不幸的是不能在 Prolog 级别以 可移植 方式实现,当然在 ISO Prolog 标准的限制内。好消息是越来越多的 Prolog 系统实现了这种控制结构。这些包括(排名不分先后)SWI-Prolog、YAP、SICStus Prolog、GNU Prolog、CxProlog、ECLiPSe、Jekejeke Prolog 和 Ciao。但是请注意,虽然某些系统使用 *->/2
运算符,但少数系统(SICStus Prolog 和 Ciao)使用 if/3
谓词(YAP 两者都有)。此外,语义在极端情况下有所不同(Logtalk 发行版包括一个 Prolog 一致性套件,它也检查 *->/2
变体)。
Yes, we can 在 ISO Prolog 甚至 XSB 中实现它,但效率不高。为了提高效率,您需要一些 "selective cut"。此外,XSB 没有实现符合 ISO 标准的整数,因此溢出必须单独处理。
:- dynamic(if_counter/1).
if_counter(0).
:- dynamic(no_if_answer/1).
if(If_0, Then_0, Else_0) :-
once(if_counter(Id)),
Idx is Id+1,
( Idx > Id -> true
; throw(error(representation_error(max_integer),
'XSB misses ISO conforming integers'))
),
retractall(if_counter(_)),
asserta(if_counter(Idx)),
asserta(no_if_answer(Id)),
( If_0,
retractall(no_if_answer(Id)),
Then_0
; retract(no_if_answer(Id)) ->
Else_0
).
效率低下的主要原因是对于确定的条件If_0
,仍然有一个选择点。 可以想象 几乎无法想象,一旦 retractall(no_if_answer(Id))
执行后,实施可以得出 retract(no_if_answer(Id))
将永远失败的结论,但我怀疑实施者是否会投资于此类优化。编辑:这看起来极不可能的原因是实施必须保证断言的数字总是上升。
请注意,软剪辑会以与剪辑相同的方式产生不完整。考虑:
| ?- if(X = a, T = equal, T = not_equal).
X = a
T = equal;
no
这显然漏掉了答案!要了解原因,请取 X = b
:
| ?- X = b, if(X = a, T = equal, T = not_equal).
X = b
T = not_equal;
no
| ?- if(X = a, T = equal, T = not_equal), X = b.
no % bad!!
合取应该是可交换的(取模不终止、错误、副作用)。
如果您对声明性合理的条件句感兴趣,这些条件句也非常有效并且通常比不纯的条件句更快,请考虑 if_/3
. See library(reif)
的 SICStus,它给出了所有正确答案:
| ?- if_(X = a, T = equal, T = not_equal).
X = a,
T = equal ? ;
T = not_equal,
prolog:dif(X,a) ? ;
no
好吧,让我们发挥创意...您基本上需要一种方法来记住(通过回溯)If 条件至少有一个解决方案。动态谓词对我来说是禁忌,但还有其他选择吗?好吧,ISO-Prolog 定义了一种匿名对象,stream-term,它可以(ab)用于以这种相当优雅的方式实现不可回溯标志:
if(If, Then, Else) :-
open(., read, S),
(
If,
close(S, [force(true)]),
Then
;
catch(close(S), error(existence_error(stream,_),_), fail), % fail if already closed
Else
).
我们关闭流以表明 If
有一个解决方案,然后通过 else 分支中的关闭尝试检测到。这在像 ECLiPSe 这样的系统中完美且无泄漏。然而,许多系统(包括 XSB)重复使用封闭流的标识符(ISO 并未禁止),使得该解决方案不可移植。
但是等等,流有一个 position 属性,可以设置,并且在回溯过程中保留其值!使用这个技巧,以下适用于 XSB:
if(If, Then, Else) :-
% open('ReadableAndNonemptyFile', read, S), % general ISO
open(atom(a), read, S), % XSB (needs no file)
stream_property(S, position(Zero)),
get_char(S, _),
(
catch(If, Ball, (close(S),throw(Ball))),
set_stream_position(S, Zero),
Then
; stream_property(S, position(Zero)) ->
close(S),
fail
;
close(S),
Else
).
遗憾的是,open(atom(...),...)
功能是 XSB 特定的,对于严格的 ISO-Prolog,您需要一个虚拟文件...
问题是,软剪辑应该相当聪明,但不应该
当其参数不留下选择点时留下选择点。
SWI-Prolog 中没有选择点:
Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.4)
?- X=1 *-> Y=1; true.
X = Y, Y = 1.
?-
Jekejeke Prolog 中没有选择点:
Jekejeke Prolog 3, Runtime Library 1.3.6
?- X=1 *-> Y=1; true.
X = 1,
Y = 1
?-
到目前为止 none 公认的创造性解决方案已在此处归档,因此其中 none 可以有效地替换本机实现。
Jekejeke Prolog 执行 determinism check,然后
删除分离选择点。否则,它标志着
分离选择点。来自模块 "logic":
:- set_predicate_property(;/2, sys_nobarrier).
A *-> B; C :- sys_local_cut, sys_soft_cond(A, B, C).
:- set_predicate_property(sys_soft_cond/3, sys_nobarrier).
sys_soft_cond(A, B, _) :- sys_safe(A), sys_soft_local_cut, B.
sys_soft_cond(_, _, C) :- C.
如何模拟 soft cut I *-> T; E 在 ISO Prolog 中?我有副作用,所以我可以不多次调用它。
除了最后一个要求,我认为以下定义有效:
if_(I, T, E) :-
not(not(I)) ->
call((I, T));
call((not(I), E)).
(我实际上在使用 XSB 序言;XSB 的解决方案对我也很有用。)
你的定义没有实现soft-cut语义:当测试成功时,你可以回溯到它。这是有用的控制结构(我用它来实现 Logtalk 中的共同归纳)但不幸的是不能在 Prolog 级别以 可移植 方式实现,当然在 ISO Prolog 标准的限制内。好消息是越来越多的 Prolog 系统实现了这种控制结构。这些包括(排名不分先后)SWI-Prolog、YAP、SICStus Prolog、GNU Prolog、CxProlog、ECLiPSe、Jekejeke Prolog 和 Ciao。但是请注意,虽然某些系统使用 *->/2
运算符,但少数系统(SICStus Prolog 和 Ciao)使用 if/3
谓词(YAP 两者都有)。此外,语义在极端情况下有所不同(Logtalk 发行版包括一个 Prolog 一致性套件,它也检查 *->/2
变体)。
Yes, we can 在 ISO Prolog 甚至 XSB 中实现它,但效率不高。为了提高效率,您需要一些 "selective cut"。此外,XSB 没有实现符合 ISO 标准的整数,因此溢出必须单独处理。
:- dynamic(if_counter/1).
if_counter(0).
:- dynamic(no_if_answer/1).
if(If_0, Then_0, Else_0) :-
once(if_counter(Id)),
Idx is Id+1,
( Idx > Id -> true
; throw(error(representation_error(max_integer),
'XSB misses ISO conforming integers'))
),
retractall(if_counter(_)),
asserta(if_counter(Idx)),
asserta(no_if_answer(Id)),
( If_0,
retractall(no_if_answer(Id)),
Then_0
; retract(no_if_answer(Id)) ->
Else_0
).
效率低下的主要原因是对于确定的条件If_0
,仍然有一个选择点。 可以想象 几乎无法想象,一旦 retractall(no_if_answer(Id))
执行后,实施可以得出 retract(no_if_answer(Id))
将永远失败的结论,但我怀疑实施者是否会投资于此类优化。编辑:这看起来极不可能的原因是实施必须保证断言的数字总是上升。
请注意,软剪辑会以与剪辑相同的方式产生不完整。考虑:
| ?- if(X = a, T = equal, T = not_equal).
X = a
T = equal;
no
这显然漏掉了答案!要了解原因,请取 X = b
:
| ?- X = b, if(X = a, T = equal, T = not_equal).
X = b
T = not_equal;
no
| ?- if(X = a, T = equal, T = not_equal), X = b.
no % bad!!
合取应该是可交换的(取模不终止、错误、副作用)。
如果您对声明性合理的条件句感兴趣,这些条件句也非常有效并且通常比不纯的条件句更快,请考虑 if_/3
. See library(reif)
的 SICStus,它给出了所有正确答案:
| ?- if_(X = a, T = equal, T = not_equal).
X = a,
T = equal ? ;
T = not_equal,
prolog:dif(X,a) ? ;
no
好吧,让我们发挥创意...您基本上需要一种方法来记住(通过回溯)If 条件至少有一个解决方案。动态谓词对我来说是禁忌,但还有其他选择吗?好吧,ISO-Prolog 定义了一种匿名对象,stream-term,它可以(ab)用于以这种相当优雅的方式实现不可回溯标志:
if(If, Then, Else) :-
open(., read, S),
(
If,
close(S, [force(true)]),
Then
;
catch(close(S), error(existence_error(stream,_),_), fail), % fail if already closed
Else
).
我们关闭流以表明 If
有一个解决方案,然后通过 else 分支中的关闭尝试检测到。这在像 ECLiPSe 这样的系统中完美且无泄漏。然而,许多系统(包括 XSB)重复使用封闭流的标识符(ISO 并未禁止),使得该解决方案不可移植。
但是等等,流有一个 position 属性,可以设置,并且在回溯过程中保留其值!使用这个技巧,以下适用于 XSB:
if(If, Then, Else) :-
% open('ReadableAndNonemptyFile', read, S), % general ISO
open(atom(a), read, S), % XSB (needs no file)
stream_property(S, position(Zero)),
get_char(S, _),
(
catch(If, Ball, (close(S),throw(Ball))),
set_stream_position(S, Zero),
Then
; stream_property(S, position(Zero)) ->
close(S),
fail
;
close(S),
Else
).
遗憾的是,open(atom(...),...)
功能是 XSB 特定的,对于严格的 ISO-Prolog,您需要一个虚拟文件...
问题是,软剪辑应该相当聪明,但不应该 当其参数不留下选择点时留下选择点。
SWI-Prolog 中没有选择点:
Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.4)
?- X=1 *-> Y=1; true.
X = Y, Y = 1.
?-
Jekejeke Prolog 中没有选择点:
Jekejeke Prolog 3, Runtime Library 1.3.6
?- X=1 *-> Y=1; true.
X = 1,
Y = 1
?-
到目前为止 none 公认的创造性解决方案已在此处归档,因此其中 none 可以有效地替换本机实现。
Jekejeke Prolog 执行 determinism check,然后 删除分离选择点。否则,它标志着 分离选择点。来自模块 "logic":
:- set_predicate_property(;/2, sys_nobarrier).
A *-> B; C :- sys_local_cut, sys_soft_cond(A, B, C).
:- set_predicate_property(sys_soft_cond/3, sys_nobarrier).
sys_soft_cond(A, B, _) :- sys_safe(A), sys_soft_local_cut, B.
sys_soft_cond(_, _, C) :- C.