3

我正在尝试编写一个程序来检查学生程序是否可以实现某个目标。我可以做那部分。现在,我想检查学生程序是否实际上包含不必要的代码。为了解决这个问题,我想我需要知道学生程序是否包含对指定目标没有贡献的事实。但是,我无法弄清楚如何找到对目标没有贡献的事实。

为了更容易理解,让我们考虑一个更简单的例子。在这个例子中,指定的目标是:john 是 tomy 的祖父吗?

father(john, jim).
father(jim, tomy).
father(john, david).
father(bruce, anne).
mother(mary, jim).

grandfather(A,B) :- father(A, X), father(X,B).

goal:- grandfather(john, tomy).

实际上,只有以下事实才能满足目标:

father(john, jim).
father(jim, tomy).

我想知道的是哪些事实实际上对目标没有贡献。答案将是以下所有事实:

father(john, david).
father(bruce, anne).
mother(mary, jim).

非常感谢任何帮助。谢谢

4

3 回答 3

2

您的问题无法在 Prolog 中直接回答,但您可以使用failure-slice手动回答。只需将false目标添加到您的程序中,并始终测试是否goal仍然成功。这是我获得的最小程序。

父亲(约翰,吉姆)。
父亲(吉姆,托米)。
父亲(约翰,大卫):-  父亲(布鲁斯,安妮):-母亲(玛丽,吉姆):-。

祖父(A,B):-父亲(A,X),父亲(X,B)。

目标:-祖父(约翰,托米)。

每次你将一个目标false插入一个纯单调的程序时,你肯定知道解决方案集会减少(或保持不变)。因此,找到这样一个切片涉及与设定此类目标的地方一样多的试验。有时您可能想要添加目标X = term以进一步缩小计划范围。

当您想了解程序的终止属性时,故障切片特别有用,请参阅了解更多信息。

于 2013-05-28T21:03:25.680 回答
1

令人难以置信的是,这里有这个问题的部分解决方案。在这里复制相关部分是大量代码,所以让我澄清一下,这不是我自己的工作,我只是把工作包括在这里,以防上面的网站将来丢失。

首先,您需要一个元循环解释器:

mi_circ(true).
mi_circ((A,B)) :-
    mi_circ(A),
    mi_circ(B).
mi_circ(clause(A,B)) :-
    clause(A,B).
mi_circ(A \= B) :-
    A \= B.
mi_circ(G) :-
    G \= true,
    G \= (_,_),
    G \= (_\=_),
    G \= clause(_,_),
    clause(G, Body),
    mi_circ(Body).

这适用于\=/2clause/2。要将这种模式推广到所有内置谓词,我们可以使用 predicate_property/2 来识别它们,以便直接调用它们:

provable(true, _) :- !.
provable((G1,G2), Defs) :- !,
    provable(G1, Defs),
    provable(G2, Defs).
provable(BI, _) :-
    predicate_property(BI, built_in),
    !,
    call(BI).
provable(Goal, Defs) :-
    member(Def, Defs),
    copy_term(Def, Goal-Body),
    provable(Body, Defs).

这为您提供了一个具体的元解释器,这意味着您可以传递provable/2一个目标和一组定义,它会告诉您提供的定义是否足以证明目标。我敢打赌,你现在可以尝到我们离最终解决方案有多近了!

通过以下附加定义,我们可以使用此 MI 来识别某些谓词定义中的冗余事实​​:

redundant(Functor/Arity, Reds) :-
    functor(Term, Functor, Arity),
    findall(Term-Body, clause(Term, Body), Defs),
    setof(Red, Defs^redundant_(Defs, Red), Reds).

redundant_(Defs, Fact) :-
    select(Fact-true, Defs, Rest),
    once(provable(Fact, Rest)).

select/3用于一次分割一个定义,并查看谓词是否仍然可证明。通过在所有定义中执行此操作,您可以获得所有不必要的规则集。

给定定义:

as([]).
as([a]).   % redundant
as([a,a]). % redundant
as([A|As]) :-
    A = a,           % test built-in =/2
    5 is 2 + 3,      % test built-in is/2
    1 > 0,           % test built-in >/2
    as(As).

我们可以要求可以从所有(相应的)剩余条款中推导出来的事实,因此是多余的:

?- redundant(as/1, Reds).
Reds = [as([a]), as([a, a])]

唉,这在您的问题上不是开箱即用的,但我确实认为通过一些研究,您可以找到一种方法将这种技术应用于它并想出一些东西。例如,您可以创建一个元解释器,它接受一个事实列表来检查并执行相同类型的 remove-one-then-prove 循环来找到它们。

希望这会有所帮助,并且至少很有趣。

于 2013-06-05T16:17:14.693 回答
0

另一种选择是修改和使用一个单元测试框架来覆盖谓词子句。定义一个单元测试,其目标是找出哪些子句对其没有贡献。如有必要,修改位将修改覆盖率报告以识别这些条款。作为我的意思的一个例子,如果不清楚,请考虑lgtunit使用 Logtalk 分发中的示例之一的 Logtalk 工具的以下输出:

?- {ack(tester)}.
% 
% tests started at 2013/6/5, 19:54:9
% running tests from object tests
% file: /Users/pmoura/logtalk/examples/ack/tests.lgt
% ack_1: success
% ack_2: success
% ack_3: success
% 3 tests: 0 skipped, 3 passed, 0 failed
% completed tests from object tests
% ack: ack/3 - [1,2,3] (3/3)
% 1 unit declared in the test file containing 3 clauses
% 1 unit covered containing 3 clauses
% 3 out of 3 clauses covered, 100,000000% coverage
% tests ended at 2013/6/5, 19:54:9
% 
true.

该行:

% ack: ack/3 - [1,2,3] (3/3)

显示谓词的三个单元测试使用了哪些子句ack/3

于 2013-06-05T18:52:52.143 回答