计算序言谓词的句法复杂度

Question

目前正在做一个练习，给定一些谓词，必须计算语法复杂度。一些谓词的句法复杂度计算如下：

如果谓词是原子的或函数，它的复杂度是 2。
如果谓词是一个变量，它的复杂度是1。

例如loyalty(father(bob, Y), X)的句法复杂度计算如下：

loyalty = 2 (function)
father = 2 (function)
bob = 2 (atom)
Y = 1 (variable)
X = 1 (variable)

Total = 8

采用的方法是如果谓词是嵌套列表的形式，即loyalty(father(bob, Y), X) = [loyalty, father, bob, Y, X]，则计算这样的复杂度，如下：

complexity([], 0).
complexity([H|L], C) :- atomic(H), complexity(L, C1), C is C1+2.
complexity([H|L], C) :- var(H), complexity(L, C1), C is C1+1.

剩下的问题是将谓词转换为平面列表，如上所示。 ..= 是有用的，但是它的输出并不完整，即：

loyalty(father(bob, Y), X) ..= ["loyalty", "father(bob, Y)", "X"]

如有任何帮助，我们将不胜感激。

Answer 1

您必须按如下方式递归应用=..：

% term_to_list(+Term, -List)

  term_to_list(Term, [Term]) :- var(Term), !.
  term_to_list(Term, [Term]) :- atomic(Term), !.
  term_to_list(Term, List) :-
      compound(Term),
      Term =.. Components,
      maplist(term_to_list, Components, ListOfLists),
      flatten(ListOfLists, List).

示例：

?- term_to_list(loyalty(father(bob, Y), X), L).
L = [loyalty, father, bob, Y, X].

或者，您可以定义 complexity/2 如下：

% complexity(+Term, -Complexity)
  
  complexity(Term, 1) :- var(Term), !.
  complexity(Term, 2) :- atomic(Term), !.
  complexity(Term, Complexity) :-
      compound(Term),
      Term =.. Components,
      maplist(complexity, Components, Complexities),
      sum_list(Complexities, Complexity).

示例：

?- complexity(loyalty(father(bob, Y), X), L).
L = 8.

备注 SWI-Prolog定义maplist/3和sum_list/2如下：

maplist(Goal, List1, List2) :-
    maplist_(List1, List2, Goal).

maplist_([], [], _).
maplist_([Elem1|Tail1], [Elem2|Tail2], Goal) :-
    call(Goal, Elem1, Elem2),
    maplist_(Tail1, Tail2, Goal).

sum_list(Xs, Sum) :-
    sum_list(Xs, 0, Sum).

sum_list([], Sum, Sum).
sum_list([X|Xs], Sum0, Sum) :-
    Sum1 is Sum0 + X,
    sum_list(Xs, Sum1, Sum).

计算序言谓词的句法复杂度

Calculating syntactic complexity of a prolog predicate

prolog