3

我的最终目标是制作 automaton/3 的具体版本,如果传递给它的序列中有任何变量,它就会冻结。即我不希望自动机实例化变量。

(fd_length/3、if_/3 等由其他人在这里定义)。

首先,我对单个变量进行了具体测试:

var_t(X,T):-
  var(X) ->
  T=true;
  T=false.

这使我能够实现:

if_var_freeze(X,Goal):-
  if_(var_t(X),freeze(X,Goal),Goal).

所以我可以做类似的事情:

?-X=bob,Goal =format("hello ~w\n",[X]),if_var_freeze(X,Goal).

其行为与以下内容相同:

?-Goal =format("hello ~w\n",[X]),if_var_freeze(X,Goal),X=bob.

如何扩展它以处理变量列表,以便在所有变量都已实例化时只调用一次 Goal?

在这种方法中,如果我有多个变量,我可以获得我不想要的这种行为:

?-List=[X,Y],Goal = format("hello, ~w and ~w\n",List),
if_var_freeze(X,Goal),
if_var_freeze(Y,Goal),X=bob.

hello, bob and _G3322
List = [bob, Y],
X = bob,
Goal = format("hello, ~w and ~w\n", [bob, Y]),
freeze(Y, format("hello, ~w and ~w\n", [bob, Y])).

我努力了:

freeze_list(List,Goal):-
  freeze_list_h(List,Goal,FrozenList),
  call(FrozenList).

freeze_list_h([X],Goal,freeze(X,Goal)).
freeze_list_h(List,Goal,freeze(H,Frozen)):-
  List=[H|T],
  freeze_list_h(T,Goal,Frozen).

其工作原理如下:

 ?- X=bob,freeze_list([X,Y,Z],format("Hello ~w, ~w and ~w\n",[X,Y,Z])),Y=fred.
 X = bob,
 Y = fred,
 freeze(Z, format("Hello ~w, ~w and ~w\n", [bob, fred, Z])) .

?- X=bob,freeze_list([X,Y,Z],format("Hello ~w, ~w and ~w\n",[X,Y,Z])),Y=fred,Z=sue.
Hello bob, fred and sue
X = bob,
Y = fred,
Z = sue .

这看起来不错,但我无法将其应用于自动机/3。重申一下目标是制作 automaton/3 的具体版本,如果传递给它的序列中有任何变量,它就会冻结。即我不希望自动机实例化变量。

这就是我所拥有的:

ga(Seq,G) :-
    G=automaton(Seq, [source(a),sink(c)],
                     [arc(a,0,a), arc(a,1,b),
                      arc(b,0,a), arc(b,1,c),
                      arc(c,0,c), arc(c,1,c)]).

max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each member of seq
  maplist(=(false),Var_T_List),  %check that all are false i.e no  uninstaninated vars
  call(A),!,
  T=true.
max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each member of seq
  maplist(=(false),Var_T_List),  %check that all are false i.e no uninstaninated vars
  \+call(A),!,
  T=false.
max_seq_automaton_t(Max,Seq,A,true):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each
  memberd_t(true,Var_T_List,true), %at least one var
    freeze_list_h(Seq,A,FrozenList),
  call(FrozenList),
  call(A).
max_seq_automaton_t(Max,Seq,A,false):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each
  memberd_t(true,Var_T_List,true), %at least one var
    freeze_list_h(Seq,A,FrozenList),
    call(FrozenList),
  \+call(A).

哪个不起作用,在实例化 X 之前,应冻结以下目标:

?- Seq=[X,1],ga(Seq,A),max_seq_automaton_t(3,Seq,A,T).
Seq = [1, 1],
X = 1,
A = automaton([1, 1], [source(a), sink(c)], [arc(a, 0, a), arc(a, 1, b), arc(b, 0, a), arc(b, 1, c), arc(c, 0, c), arc(c, 1, c)]),
T = true 

更新这就是我现在所拥有的,我认为它可以按照我最初的意图工作,但我正在消化@Mat 所说的想法,如果这真的是我想要的。明天继续更新。

goals_to_conj([G|Gs],Conj) :- 
  goals_to_conj_(Gs,G,Conj).

goals_to_conj_([],G,nonvar(G)).
goals_to_conj_([G|Gs],G0,(nonvar(G0),Conj)) :-
  goals_to_conj_(Gs,G,Conj).

max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each member of seq
  maplist(=(false),Var_T_List),  %check that all are false i.e no uninstaninated vars
  call(A),!,
  T=true.
max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each member of seq
  maplist(=(false),Var_T_List),  %check that all are false i.e no uninstaninated vars
  \+call(A),!,
  T=false.
max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each
  memberd_t(true,Var_T_List,true), %at least one var
  goals_to_conj(Seq,GoalForWhen),
  when(GoalForWhen,(A,T=true)).
max_seq_automaton_t(Max,Seq,A,T):-
  Max #>=L,
  fd_length(Seq,L),
  maplist(var_t,Seq,Var_T_List), %find var_t for each
  memberd_t(true,Var_T_List,true), %at least one var
  goals_to_conj(Seq,GoalForWhen),
  when(GoalForWhen,(\+A,T=false)).
4

3 回答 3

4

在我看来,您在 Prolog 方面取得了很大进展。在这一点上,尽管采取更谨慎的态度是有道理的。原则上,您所要求的所有事情都可以轻松解决。您只需要 的泛化freeze/2,它可用作when/2

然而,让我们退后一步,更深入地考虑一下这里实际发生了什么。

声明式地,当我们声明一个约束时,我们的意思是它成立。我们并不是说“它仅在所有内容都被实例化时才成立”,因为这会将约束减少到单纯的检查器,从而导致“生成和测试”方法。约束点就是尽可能地修剪,在许多情况下会导致搜索空间大大减少。

对于具体化的约束,情况完全相同。当我们发布一个具体化的约束时,我们声明该具体化成立。不仅在一切都被实例化的情况下,而且总是. 关键是(具体化的)约束可以在所有方向上使用。如果被具体化的约束已经存在,我们就会了解它。同样,如果它不能成立,我们就会了解它。如果可能是这种情况,我们需要明确搜索解决方案,或者确定不存在。如果我们要坚持被具体化的约束成立,那是很容易实现的;等等

然而,在所有情况下,关键在于我们可以专注于约束的声明性语义,而无需考虑额外的逻辑、程序性考虑,例如实例化什么以及何时实例化。如果我回答了您的字面问题,它将使您更接近操作考虑,比您实际上可能需要或想要的更接近。

因此,我不会回答你的字面问题。但我会给你一个解决你实际的潜在问题的方法。

关键是要具体化 automaton/3。约束具体化本身不会修剪任何东西,只要它是开放的,无论被具体化的约束是否实际成立。只有当我们坚持被具体化的约束成立时,才会发生传播。

automaton/3通过具体化构成其分解的约束的合取,它很容易具体化。这是一种方法,基于 SWI-Prolog 中免费提供的代码:

:- use_module(library(clpfd)).

automaton(Vs, Ns, As, T) :-
        must_be(list(list), [Vs,Ns,As]),
        include_args1(source, Ns, Sources),
        include_args1(sink, Ns, Sinks),
        phrase((arcs_relation(As, Relation),
                nodes_nums(Sinks, SinkNums0),
                nodes_nums(Sources, SourceNums0)), [[]-0], _),
        phrase(transitions(Vs, Start, End), Tuples),
        list_to_drep(SinkNums0, SinkDrep),
        list_to_drep(SourceNums0, SourceDrep),
        (   Start in SourceDrep #/\
            End in SinkDrep #/\
            tuples_in(Tuples, Relation)) #<==> T.


include_args1(Goal, Ls0, As) :-
        include(Goal, Ls0, Ls),
        maplist(arg(1), Ls, As).

list_to_drep([L|Ls], Drep) :-
        foldl(drep_, Ls, L, Drep).

drep_(L, D0, D0\/L).

transitions([], S, S) --> [].
transitions([Sig|Sigs], S0, S) --> [[S0,Sig,S1]],
        transitions(Sigs, S1, S).

nodes_nums([], []) --> [].
nodes_nums([Node|Nodes], [Num|Nums]) -->
        node_num(Node, Num),
        nodes_nums(Nodes, Nums).

arcs_relation([], []) --> [].
arcs_relation([arc(S0,L,S1)|As], [[From,L,To]|Rs]) -->
        node_num(S0, From),
        node_num(S1, To),
        arcs_relation(As, Rs).

node_num(Node, Num), [Nodes-C] --> [Nodes0-C0],
        { (   member(N-I, Nodes0), N == Node ->
              Num = I, C = C0, Nodes = Nodes0
          ;   Num = C0, C is C0 + 1, Nodes = [Node-C0|Nodes0]
          ) }.

sink(sink(_)).

source(source(_)).

请注意,只要未知,这不会传播任何内容。T

我现在对一些示例查询使用以下定义:

seq(Seq, T) :-
        automaton(Seq, [source(a),sink(c)],
                       [arc(a,0,a), arc(a,1,b),
                        arc(b,0,a), arc(b,1,c),
                        arc(c,0,c), arc(c,1,c)], T).

例子:

?- seq([X,1], T).

结果(省略):发布了约束,没有传播任何内容。

下一个例子:

?- seq([X,1], T), X = 3.
X = 3,
T = 0.

显然,具体化的automaton/3约束在这种情况下不成立。但是,物化约束当然仍然像往常一样,这就是为什么T=0在这种情况下的原因。

下一个例子:

?- seq([1,1], T), indomain(T).
T = 0 ;
T = 1.

哦-哦!这里发生了什么?约束怎么可能既是真又是假呢?这是因为我们没有看到此示例中实际发布的所有约束。用call_residue_vars/2来看全部真相。

事实上,试试更简单的例子:

?- call_residue_vars(seq([1,1],0), Vs).

在这种情况下仍需要满足的未决剩余约束是:

_G1496 in 0..1,
_G1502#/\_G1496#<==>_G1511,
tuples_in([[_G1505,1,_G1514]], [[0,0,0],[0,1,1],[1,0,0],[1,1,2],[2,0,2], [2,1,2]])#<==>_G825,
tuples_in([[_G831,1,_G827]], [[0,0,0],[0,1,1],[1,0,0],[1,1,2],[2,0,2],[2,1,2]])#<==>_G826,
_G829 in 0#<==>_G830,
_G830 in 0..1,
_G830#/\_G828#<==>_G831,
_G828 in 0..1,
_G827 in 2#<==>_G828,
_G829 in 0..1,
_G829#/\_G826#<==>0,
_G826 in 0..1,
_G825 in 0..1

因此,仅这些被称为仍然比目鱼的约束也成立时,上述内容才成立。

这是一个辅助定义,可帮助您标记剩余的有限域变量。这个例子就足够了:

finite(V) :-
        fd_dom(V, L..U),
        dif(L, inf),
        dif(U, sup).

我们现在可以粘贴残差程序(由 CLP(FD) 约束组成),并用于label_fixpoint/1标记域是有限的变量:

?- Vs0 = [_G1496, _G1499, _G1502, _G1505, _G1508, _G1511, _G1514, _G1517, _G1520, _G1523, _G1526],
  _G1496 in 0..1,
  _G1502#/\_G1496#<==>_G1511,
  tuples_in([[_G1505,1,_G1514]], [[0,0,0],[0,1,1],[1,0,0],[1,1,2],[2,0,2], [2,1,2]])#<==>_G825,
  tuples_in([[_G831,1,_G827]], [[0,0,0],[0,1,1],[1,0,0],[1,1,2],[2,0,2],[2,1,2]])#<==>_G826,
  _G829 in 0#<==>_G830, _G830 in 0..1,
  _G830#/\_G828#<==>_G831, _G828 in 0..1,
  _G827 in 2#<==>_G828, _G829 in 0..1,
  _G829#/\_G826#<==>0, _G826 in 0..1, _G825 in 0..1,
  include(finite, Vs0, Vs),
  label(Vs).

注意我们不能在原程序中直接使用labeling,即不能这样做:

?- call_residue_vars(seq([1,1],0), Vs), <label subset of Vs>.

因为call_residue_vars/2也使内部变量浮出水面,尽管它们具有分配的域并且看起来像常规 CLP(FD) 变量,但并不意味着直接参与任何标记。

相比之下,残差程序可以毫无问题地用于进一步推理,实际上它就是这样使用的。

在这个具体的例子中,在标记了上面例子中域仍然有限的变量之后,仍然存在一些约束。它们的形式为:

tuples_in([[_G1487,1,_G1496]], [[0,0,0],[0,1,1],[1,0,0],[1,1,2],[2,0,2],[2,1,2]])#<==>_G1518

练习:是否由此间接得出原始查询,即 ,seq([1,1],0)不能成立

所以,总结一下:

  1. 约束具体化本身不会导致正在被具体化的约束的传播。
  2. 约束具体化通常可以让您检测到约束不能成立。
  3. 一般来说,CLP(FD) 传播必然是不完整的,即我们不能仅仅因为我们的查询成功就确定存在解决方案。
  4. labeling/2让您看看是否有具体的解决方案,如果域是有限的。
  5. 要查看所有未决约束,请将您的查询包装在call_residue_vars/2.
  6. 只要未决的约束仍然存在,这只是一个有条件的答案。

建议:为确保不存在挣扎的约束,请将您的查询包装起来call_residue_vars/2并在顶层查找任何剩余约束。

于 2015-10-14T16:57:10.187 回答
2

考虑使用广泛可用的谓词when/2(有关详细信息,请考虑阅读SICStus Prolog 手册页when/2)。

请注意,原则上您可以freeze/2这样实现:

freeze(V,Goal) :-
   when(nonvar(V),Goal).
于 2015-10-14T18:55:44.793 回答
1

在我看来,您正在实施的内容是以下内容的变体:

delay_until_ground_t(目标,T):-
   (地面(目标)
   ->(呼叫(目标)
      -> T = 真
      ; T = 假
      )
   ; T = true, when(ground(Goal),once(Goal))
   ; T = false, when(ground(Goal), \+(Goal))
   )。

延迟目标可能是一个非常好的功能,但要注意永远延迟的危险。

请务必阅读并消化@mat 关于的上述答案call_residue_vars/2

于 2015-10-16T20:49:02.817 回答