Calculating syntactic complexity of a prolog predicate

user_11481011 0
Viewed 95

Currently working on an exercise where, given some predicate, the syntactic complexity has to be calculated. The syntactic complexity of some predicate is calculated as follows:

  • If the predicate is atomic or a function, its complexity is 2.
  • If the predicate is a variable, its complexity is 1.

For example, the syntactic complexity of loyalty(father(bob, Y), X) is worked out as follows:

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

Total = 8

The approach taken was calculating such complexity if the predicate was in the form of a nested list, i.e. loyalty(father(bob, Y), X) = [loyalty, father, bob, Y, X], as follows:

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.

The remaining issue is converting the predicate to a flat list, as shown above. The ..= is useful, but its output is not complete, that is:

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

Any help would be appreciated.

prolog
1 Answers

You must apply =.. recursively as follows:

% 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).

Example:

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

Alternatively, you can define complexity/2 as follows:

% 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).

Example:

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

Remark SWI-Prolog defines maplist/3 and sum_list/2 as follows:

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).
user_115359400
Related