Prolog recursion and accumulators

问题:

I am new to Prolog programming. I am doing recursive classification predicate with accumulator (I believe I need accumulator). Suppose I have following rules:

species(tiger).
species(carnivora).
species(ferae).
species(scrotifera).
species(laurasiatheria).

isa(tiger,carnivora).
isa(carnivora,ferae).
isa(ferae,scrotifera).
isa(scrotifera,laurasiatheria).
isa(laurasiatheria, mammalia).

I need classification predicate that returns hierarchy of classes for given specie. Here is what I do:

classification_aux(mammalia,[H|T],[]).
classification_aux(Specie, Class, Accum) :-
    isa(Specie, Y),
    classification_aux(Y, [Y|Class], Accum).    

classification(Specie, Class) :- classification_aux(Specie,Class,[]).

Here is sample how it should work:

classification(gray_tree_frog, X).
X = [amphibia, anura, hylidae, hyla].

EDIT: I improved my code. Now it seems to work according to trace. But nothing is returned.

回答1:

based only on hierarchical description (since species/1 seems at least a misunderstanding of the complex terminology involved in biology)

classification(Specie, Classification) :-
    isa(Specie, Class) ->
      Classification = [Class|SuperClasses],
      classification(Class, SuperClasses)
    ; Classification = [].

yields

?- classification(tiger, X).
X = [carnivora, ferae, scrotifera, laurasiatheria, mammalia].

edit

in case you're interested, this snippet

:- use_module(carlo(snippets/genealogy/pqGraphviz_emu)).

classification :-
    graph_window(build_graph, []).

build_graph(G) :-
    forall(species(S), make_node(G, S, [shape=diamond], _)),
    forall(isa(X, Y), (lookup_node(G, X, Xp), lookup_node(G, Y, Yp), new_edge(G, Xp, Yp))).

lookup_node(G, N, Np) :-
    find_node(G, N, Np) -> true ; make_node(G, N, Np).

produces this SVG file

The interface is available from github, requires Graphviz installed.

回答2:

You are pretty close to getting this right.

The first thing to think about is how to solve the problem without an accumulator. Accumulators are most often optional in that they help performance rather than help you get the right answer.

Start with working out a spec for your predicate: classification(S,L) should be true if L is the heirarchy for S.

Now you can write an axiom: the classification heierarchy for mammalia is [mammalia].

And you can write a rule: the classification hierarchy for some specie S is the list with S at the front and some value R at the tail, if you can show that S classifies as P and the hierarchy for P is R. Or alternatively phrased: given an S we first find the class of S (call it P), and the hierarchy of P (call it R), then the hierarchy for S is [S|R].

Hopefully those descriptions should be enough for you to write the clauses.

Now to the issue of an accumulator: classification_aux(S,C,A) should be true if the classification heirarchy of S with an already accumulated hierarchy of C is A.

If you now match this on to your clauses you can see what's wrong:

classification_aux(mammalia,[H|T],[]).

This says that the classification of mammalia with current hierarchy [H|T] is []. This clearly doesn't match the spec. What you want instead is that the classification of mammalia with current hierarchy L is [mammalia|L]

classification_aux(Specie, Class, Accum) :-
isa(Specie, Y),
classification_aux(Y, [Y|Class], Accum).    

This says: the classification of Specie with a current class heierachy Class is Accum if Specie is a Y and the classification of Y with heirarchy [Y|Class] is Accum. Which I think is fine.

However, if you try both of these you'll find that the accumulator version produces the hierarchy in the reversed order. This is due to the [mammalia|L] and [Y|Class] putting the classes on the front of the list instead of the end. You could fix this by using append instead (slow) or difference lists (more complicated) or just use the non-accumulator version.