我只与Prolog合作了几天.我理解一些事情,但这真让我感到困惑.
我想要编写一个带有列表并将其展平的函数.
?- flatten([a,[b,c],[[d],[],[e]]],Xs).
Xs = [a,b,c,d,e]. % expected result
该函数取出列表的内部结构.
这是我到目前为止:
flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
flatten2(List,RetList).
现在,这在我打电话时起作用:
?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e]. % works as expected!
但是当我打电话来查看我输入的列表是否已经展平时,将返回false而不是true:
?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false. % BAD result!
为什么一方面工作,另一方面又不工作？我觉得我错过了很简单的事情.
在CLP(FD)中,我们经常需要声明:"这是整数和有限域变量的列表(有时:严格地)升序/降序."
是否有任何CLP(FD)系统为此任务提供通用(参数化)内置约束？
SWI-Prolog提供了一个名为的约束chain/2,类似于我正在寻找的约束.但是,名称稍微过于具体,不能包含约束可以描述的所有关系(例如:#<不是部分顺序,但是可以接受chain/2,导致序列 - 作为一组整数 - 不再计算为链中定义的链数学顺序理论).因此,该名称并未完全描述约束实际实现的内容.
请给所述最一般相对于通常的二进制CLP(FD)约束定义-或包含至少一个合适的子集#<,#>,#=<和#>=- 包括根据代数结构的约束定义适当的名称.强加的条件是约束描述了在文献中具有正确名称的实际数学结构.
首先,请考虑使用SICStus Prolog或SWI:
:- use_module(library(clpfd)).
connex(Relation_2, List) :-
connex_relation(Relation_2),
connex_(List, Relation_2).
connex_relation(#=).
connex_relation(#<).
connex_relation(#=<).
connex_relation(#>).
connex_relation(#>=).
connex_([], _).
connex_([L|Ls], Relation_2) :-
foldl(adjacent(Relation_2), Ls, L, _).
adjacent(Relation_2, X, Prev, X) :- call(Relation_2, Prev, X).
示例案例:
?- connex(#<, [A,B,C]).
A#=<B+-1,
B#=<C+-1.
?- connex(#=, [A,B,C]).
A = B, B = C,
C in inf..sup. …我发现这个很好的片段用于解析Prolog中的lisp(从这里开始):
ws --> [W], { code_type(W, space) }, ws.
ws --> [].
parse(String, Expr) :- phrase(expressions(Expr), String).
expressions([E|Es]) -->
ws, expression(E), ws,
!, % single solution: longest input match
expressions(Es).
expressions([]) --> [].
% A number N is represented as n(N), a symbol S as s(S).
expression(s(A)) --> symbol(Cs), { atom_codes(A, Cs) }.
expression(n(N)) --> number(Cs), { number_codes(N, Cs) }.
expression(List) --> "(", expressions(List), ")".
expression([s(quote),Q]) --> "'", expression(Q).
number([D|Ds]) --> digit(D), number(Ds).
number([D]) --> digit(D).
digit(D) --> …我正在尝试构建一个简单的Prolog SAT求解器.我的想法是用户应该使用Prolog列表输入要在CNF(Conjuctive Normal Form)中解决的布尔公式,例如(A或B)和(B或C)应该表示为sat([[A,B]] ,[B,C]])和Prolog试图找到A,B,C的值.
我的以下代码不起作用,我不明白为什么.在这一行跟踪调用:(7)sat([[true,true]])？ 我期待start_solve_clause([_ G609,_G612]]).
免责声明:对不起几天前我甚至不知道Prolog或SAT问题的糟糕代码.
PS:欢迎提出解决SAT问题的建议.
跟踪
sat([[X, Y, Z], [X, Y]]).
Call: (6) sat([[_G609, _G612, _G615], [_G609, _G612]]) ? creep
Call: (7) start_solve_clause([_G609, _G612, _G615]) ? creep
Call: (8) solve_clause([_G615], _G726) ? creep
Call: (9) or(_G725, _G615, true) ? creep
Exit: (9) or(true, true, true) ? creep
Exit: (8) solve_clause([true], true) ? creep
Call: (8) or(_G609, _G612, true) ? creep
Exit: (8) or(true, true, true) ? creep
Exit: (7) start_solve_clause([true, …我有一个列表,在它的开头有一个未知数量的零,例如[0,0,0,1,2,0,3].我需要将这个列表去掉前导零,以便它看起来像[1,2,0,3].
这就是我所拥有的:
lead([Head | _], _) :- Head =\= 0.
lead([0 | Tail], _) :-
lead(Tail, Tail).
其输出只是True.读取跟踪显示它正在运行,直到它有一个没有前导零的列表,但随后答案不会传播回堆栈.我对Prolog很新,所以我无法弄清楚如何做到这一点.
到目前为止,我一直坚持 Prolog程序意味着:
如果对于一个查询
Q,有一个subtermS,使得存在一个术语T,使?- S=T, Q.成功虽然?- Q, S=T.失败,然后通过调用一个谓词Q是不踏实.
直觉上,我因此坚定地表示我们不能使用实例化来"欺骗"谓词来提供解决方案,否则这些解决方案不仅不会被给予,而是被拒绝.注意非终止程序的区别!
特别是,至少在我看来,逻辑纯度总是意味着坚定不移.
例子.为了更好地理解坚定性的概念,考虑这个属性的几乎经典的反例,在将高级学生引入Prolog的操作方面时经常引用,使用两个整数之间关系的错误定义及其最大值:
integer_integer_maximum(X, Y, Y) :-
Y >= X,
!.
integer_integer_maximum(X, _, X).
这个中的一个明显错误 - 我们应该说" 摇摆不定 " - 定义当然是以下查询错误地成功:
?- M = 0, integer_integer_maximum(0, 1, M). M = 0. % wrong!
而交换目标产生了正确的答案:
?- integer_integer_maximum(0, 1, M), M = 0. false.
这个问题的一个很好的解决方案是依靠 …
我有一个谓词,找到正确的解决方案,但接着找到不正确的解决方案.
?- data(D),data_threshold_nonredundantbumps(D,5,Bs),write(D).
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([11], [7]), bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8], [6]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D …如何使用谓词包含(b,l,t)正确地写出空(b,t)-action的效果公理如果桶b在时间t保持l升水,则谓词评估为True.
空(b,t):在时间t完全清空桶b.在时间t + 1可以看到转移的影响
转移(b,b',t):尽可能多的水从桶b转移到桶b',而不会在时间t溢出任何开始.在时间t + 1可以看到转移的影响.
铲斗1装满水并容纳7升水.铲斗2是空的并且容纳3升.目标状态是b2含有1升水.
我会说正确的解决方案是:
to any b,t,l( empty(b,t) -> contains(b,l,t))
这是正确的还是我应该将升的数量设置为l = 5,例如？
在下面,我只考虑纯 Prolog程序.这意味着我不是在谈论副作用和操作系统调用,它们会让逻辑领域做一些无法在Prolog中观察到的事情.
对于Prolog程序的运行时成本,有一个众所周知的抽象度量:逻辑推理的数量.通过"抽象",我的意思是这个度量独立于任何特定的Prolog实现和实际的具体硬件.从某种意义上说,它是一种衡量标准,它为我们提供了执行程序所需时间的一些信息.我们甚至可以通过说明它们每秒推断的数量 (LIPS)来在一定程度上指定Prolog系统的性能,并且这被广泛使用,人们可以称之为传统的系统性能测量.传统上,这个数字是通过特定的基准来衡量的,但"推理数量"的一般概念当然也扩展到其他更复杂的Prolog程序.
但是,据我所知,这个特殊的(我敢说:具体的)抽象测量并不能说明以下重要意义上的全部真相:
对于任何给定的Prolog目标G,让我们用t(G)表示:T →R在特定硬件上给定Prolog系统上G的实际执行时间,即从Herbrand项到实数的函数.让我们称一个度量α:T →R 真实 iff t(G)≈对于所有G的α(G),在这个意义上,这个值相差一个因子,该因子受所有目标G和所有"现实" 的常数限制硬件的类型(我必须稍微说明这一点,但为了简单起见,我在这里假设相同的Prolog实现在"典型"硬件上大致以相同的方式执行.我知道事实并非如此,并且相同实现可以在不同类型的硬件上表现出截然不同的特性.如果是这样,将定义限制为实现"大致"相同的硬件类型的子集.)
据我所知,逻辑推理的数量通常不是 Prolog目标的实际执行时间的真实度量,特别是因为执行统一所花费的时间不是由它来衡量的.可以构造这样的情况,即该度量与实际执行时间之间的差异不再受常数限制.
因此,我的问题是:对于Prolog目标的运行时间,是否有真实的抽象度量？如果它一般不存在,请指定一个有意义的Prolog程序子集,其中可以定义这样的度量.例如,通过限制可能发生的统一类型.
这个问题具有很高的实际意义,例如在使用Prolog实现智能合约时:在这种情况下,您希望抽象地测量运行Prolog程序所需的时间,即使您的程序在需要达成协议的不同机器上运行关于运行它的时间,但是你希望保留未来改进具体实现技术的可能性.因此,该度量应仅取决于实际给定的程序,而不取决于实现的任何具体特征,例如访问的存储器单元的数量.
有什么设计启发式的人必须掌握好写Prolog？我听说需要一名经验丰富的程序员大约两年才能熟练掌握Prolog.有效地使用递归是其中的一部分,但这似乎是一个相对较小的障碍.究竟是什么给程序员带来了这么多麻烦？我应该在示例代码中寻找什么来判断其质量？