2

I deal with a problem; I want to calculate how many recursions a recursive rule of my code does.

My program examines whether an object is component of a computer hardware or not(through component(X,Y) predicate).E.g component(computer,motherboard) -> true.

It does even examine the case an object is not directly component but subcomponent of another component. E.g. subcomponent(computer,ram) -> true. (as ram is component of motherboard and motherboard is component of computer)

Because my code is over 400 lines I will present you just some predicates of the form component(X,Y) and the rule subcomponent(X,Y).

So, some predicates are below:

component(computer,case).
component(computer,power_supply).
component(computer,motherboard).
component(computer,storage_devices).
component(computer,expansion_cards).
component(case,buttons).
component(case,fans).
component(case,ribbon_cables).
component(case,cables).

component(motherboard,cpu).
component(motherboard,chipset).
component(motherboard,ram).
component(motherboard,rom).
component(motherboard,heat_sink).
component(cpu,chip_carrier).
component(cpu,signal_pins).
component(cpu,control_pins).
component(cpu,voltage_pins).
component(cpu,capacitors).
component(cpu,resistors).

and so on....

My rule is: 

subcomponent(X,Z):- component(X,Z).
subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).

Well, in order to calculate the number of components that a given component X to a given component Y has-that is the number of recursions that the recursive rule subcomponents(X,Y), I have made some attempts that failed. However, I present them below:

i) 

 number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y).
 number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).

In this case I get this error: "ERROR: is/2: Arguments are not sufficiently instantiated".

ii)

number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
                        length(L,N),
                        write(N).

In this case I get as a result either 1 or 11 and after this number true and that's all. No logic at all!

iii)

count_elems_acc([], Total, Total).
count_elems_acc([Head|Tail], Sum, Total) :-
      Count is Sum + 1, 
      count_elems_acc(Tail, Count, Total).


number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L),
                        count_elems_acc(L,0,Total),
                        write(Total).

In this case I get as results numbers which are not right according to my knowledge base.(or I mistranslate them-because this way seems to have some logic)

So, what am I doing wrong and what should I write instead?

I am looking forward to reading your answers!

false
  • 10,264
  • 13
  • 101
  • 209
Jimbo_ai
  • 167
  • 1
  • 13

2 Answers2

3

One thing you could do is iterative deepening with call_with_depth_limit/3. You call your predicate (in this case, subcomponent/2). You increase the limit until you get a result, and if you get a result, the limit is the deepest recursion level used. You can see the documentation for this.

However, there is something easier you can do. Your database can be represented as an unweighted, directed, acyclic graph. So, stick your whole database in a directed graph, as implemented in library(ugraphs), and find its transitive closure. In the transitive closure, the neighbours of a component are all its subcomponents. Done!

To make the graph:

findall(C-S, component(C, S), Es),
vertices_edges_to_ugraph([], Es, Graph)

To find the transitive closure:

transitive_closure(Graph, Closure)

And to find subcomponents:

neighbours(Component, Closure, Subcomponents)

The Subcomponents will be a list, and you can just get its length with length/2.

EDIT

Some random thoughts: in your case, your database seems to describe a graph that is by definition both directed and acyclic (the component-subcomponent relationship goes strictly one way, right?). This is what makes it unnecessary to define your own walk through the graph, as for example nicely demonstrated in this great question and answers. So, you don't need to define your own recursive subcomponent predicate, etc.

One great thing about representing the database as a term when working with it, instead of keeping it as a flat table, is that it becomes trivial to write predicates that manipulate it: you get Prolog's backtracking for free. And since the S-representation of a graph that library(ugraph) uses is well-suited for Prolog, you most probably end up with a more efficient program, too.

Community
  • 1
  • 1
  • @CapelliC (Note: the "u" in "ugraphs" stands for "unweighted", not "undirected".) The database in OP's question is exactly an unweighted, directed, acyclic graph. So this feels like the right data structure. And the library(ugraphs) has a few very useful predicates which you get for free. I think your answer is a really good one, mine just offers another approach. –  Jan 30 '16 at 05:43
  • yes, of course you're completely right (+1)... I was skimming the documentation, and deleted my silly comment meanwhile... – CapelliC Jan 30 '16 at 05:48
  • @Boris Should I create a rule `number_of_components(X,Y)` which includes the predicates you typed above or something else I didn't get it? – Jimbo_ai Feb 02 '16 at 11:53
  • @Jimbo_ai Yes. Or, if you consult a file with the `component/2` rules only, you can type those verbatim at the top level (with commas in between) and you will get the answers you are after. –  Feb 02 '16 at 12:01
  • @Jimbo_ai If I were you, I would do the following: first, make a file with only the `component/2` rules in it. Then, consult this from the top level. Then, try `findall(...)` as in my answer, and see what you get. Then, add `vertices_edges_to_ugraph(...)` to the query, and see what you get. Then, add `transitive_closure(...)` to the query, etc, etc. Once you know what is going on, you can start thinking about how to organize this in rules that you add to your program. –  Feb 02 '16 at 12:08
  • @Boris Are `transitive_closure/2` and `neighbours/3` built-in predicates? – Jimbo_ai Feb 02 '16 at 12:47
  • @Boris I have created the following rule: `number_of_components(X,Y):- findall(C-S, component(C, S), Es), vertices_edges_to_ugraph([], Es, Graph), transitive_closure(Graph, Closure), neighbours(Component, Closure, Subcomponents), write(length(Subcomponents,N)).` and whenever I call the rule in terminal I get false...only false! No number, not even a true! – Jimbo_ai Feb 02 '16 at 12:56
  • @Jimbo_ai Try this on the top level first! If you did, you might realize that the last two should read: `neighbours(X, Closure)` so that look for the component in the first argument to `number_of_components/2` and then `length(Subcomponents, Y)` to unify the length with the second argument. –  Feb 02 '16 at 13:01
  • @Boris Ok, I am doing this procedure step-by-step. The first three predicates are working perfect. The problem is lying on running the `neighbours(Component, Closure, Subcomponents)`. After inserted, a **false** is the only result I got, whereas beforehand I had got the lists I wanted..So, what's next? – Jimbo_ai Feb 02 '16 at 13:53
  • @Jimbo_ai The first argument to `neighbours/3` **must be** instantiated to an actual component. So, it should be for example `neighbours(case, Closure, Subcomponents)`. Read the documentation. –  Feb 02 '16 at 14:09
  • @Boris I did it, I modified it a little bit to be compatible with the rest of my code and the program is working perfect! Thank you very much and I appreciate your help!!! – Jimbo_ai Feb 02 '16 at 14:31
1

The number of calls of a predicate can be a difficult concept. I would say, use the tools that your system make available.

?- profile(number_of_components(computer,X)).
20===================================================================
Total time: 0.00 seconds
=====================================================================
Predicate                       Box Entries =    Calls+Redos     Time
=====================================================================
$new_findall_bag/0                        1 =        1+0         0.0%
$add_findall_bag/1                       20 =       20+0         0.0%
$free_variable_set/3                      1 =        1+0         0.0%
...
so:count_elems_acc/3                      1 =        1+0         0.0%
so:subcomponent/2                        22 =        1+21        0.0%
so:component/2                           74 =       42+32        0.0%
so:number_of_components/2                 2 =        1+1         0.0%

On the other hand, what is of utmost importance is the relation among clause variables. This is the essence of Prolog. So, try to read - let's say, in plain English - your rules.

i) number_of_components(X,Y,N,T) what relation N,T have to X ? I cannot say. So

?- leash(-all),trace.
?- number_of_components(computer,Y,N,T).
   Call: (7) so:number_of_components(computer, _G1931, _G1932, _G1933)
   Call: (8) _G1933 is _G1932+1
ERROR: is/2: Arguments are not sufficiently instantiated
   Exception: (8) _G1933 is _G1932+1 ?

ii) number_of_components(X,Y) here would make much sense if Y would be the number_of_components of X. Then,

number_of_components(X,Y):- bagof(S,subcomponent(X,S),L), length(L,Y).

that yields

?- number_of_components(computer,X).
X = 20.

or better

?- aggregate(count, S^subcomponent(computer,S), N).
N = 20.

Note the usage of S. It is 'existentially quantified' in the goal where it appears. That is, allowed to change while proving the goal.

iii) count_elements_acc/3 is - more or less - equivalent to length/2, so the outcome (printed) seems correct, but again, it's the relation between X and Y that your last clause fails to establish. Printing from clauses should be used only when the purpose is to perform side effects... for instance, debugging...

CapelliC
  • 59,646
  • 5
  • 47
  • 90