1

I have problems to write my first simple pseudocode.

The input of the algorithm is an ontology which contains axioms and an inference set, exactly an inference is defined as an object with set of premises and an conclusion.

The output of the algorithm should be the set of conclusion that we can derive from the given ontology using the inference set.

A conclusion is derivable if there exits an inference which has as conclusion such conclusion and in turn its premises are derivable.

I wrote the pseudocode, but i think it is not the best solution due to the goto instruction. I think it can be remove and i can add some data structure that takes care of the phase of propagation. I hope that i was clear:)

enter image description here

Christophe
  • 74,672
  • 10
  • 115
  • 187
marouane nadir
  • 39
  • 2

1 Answers1

3

Improving the pseudocode structure

In line 7 it appears that you restart every time you find a new element to add to D. However, in pseudocode and mathematical language, you have no guarantee about the order in which foreach takes the elements of I.

Therefore, you could as well continue the loop to the end of the foreach and add an outer loop: 

D ← { O }
repeat 
  retry ← false
  foreach  ∈ I do
     P ← getPremises()
     if P ∈ D then
        C ← getConclusion()
        if C ∉ D then 
           D ← D ∪ { C }
           retry ← true
  until not retry
return D

If you do not like repeat/until, you could also go for a while but you'd need to initalize retry in consequence.

If the order of evaluation matters, you'd replace the set I with an ordered list or a priority queue, and use the same approach than before but break the inner loop after setting retry to true.

Correcting the notation

Instead of !, you'd better use the more readable not, or the more comprehensive ∉.

This being said, if O is a set, and if D is a set that should at start contain all the elements of O, O should not be shown as a set element, and line 1 should be: 

D ← O

If P is in fact a set and not elements, line 5 should use set operators instead of element operators: 

if P ⊂ D then
   ...

Improving algorithm

The restart in your original algorithm after the firing of a rule leads to think that the intent is to re-evaluate all the rules due to changed of situation.

However from the comments, it appears that a rule may have an effect on D only once. So there's no need to fire again a rule that already fired. This may lead to an improved algorithm: 

D ← O          
K ← I       // K is the set of rules that could still fire
n ← true    // n is true when new facts were added to D
while n do 
  n ← false
  foreach  ∈ K do
     P ← getPremises()
     if P ⊂ D then
        K  ← K - {  }          // or K ← {x∈K|x≠ }
        C ← getConclusion()
        if C ∉ D then 
           D ← D ∪ { C }
           n ← true
return D

Now K contains the rules which did not fire yet.

Depending on the number of rules and the complexity of firing them, you could even go further and remove from K any other rule that could give the same C as conclusion, whether they are ready to be fired or not, since they would never change the final D.

Christophe
  • 74,672
  • 10
  • 115
  • 187
  • looks like this calls getConclusion more than required – Ewan Feb 26 '20 at 08:22
  • @Ewan it may indeed. Avoiding it would require to split I into two sets or adding a map that for each element of I tells if it already fired. This is a substantial change in the logic which is beyond the simple goto removal. On the other hand, having written inference engines on my own, I suspect that unless there is a single premise, D should be a parameter of getConclusion as well. In this case you’d need to re-conclude whenever D changed. – Christophe Feb 26 '20 at 08:42
  • @Christophe honestly i thought that the goto instruction might be replaced the **while** instruction, i wanted right to avoid the restart of the foreach loop any times when D changes. I thought to record the inferences which i cannot apply at that time and then propagate the changing of D to such inferences. – marouane nadir Feb 26 '20 at 09:48
  • @marouanenadir I had the impression that the restart was on purpose. can you confirm that once a rule is fired because its premises are in D, it will not change its conclusion and needs no firing again? – Christophe Feb 26 '20 at 10:17
  • Not exactly, i know that if D changes, then i would take care of the possibility that inferences which cannot be fired before, now they can be fired. But it has no sense every time loop inferences which are already fired. In additional, i have only to check inferences which have as premises the new element added in D and so on in case a new conclusion is added in D. – marouane nadir Feb 26 '20 at 10:35
  • @marouanenadir I think you could expand more on the input. Its just an empty set here but obvs that is not the case in your code. Could you not just recurse the tree? – Ewan Feb 26 '20 at 13:11
  • @marouanenadir I see. I’ll edit my answer. But could you confirm before that getPremises and getConclusion both return a single element and not sets ? – Christophe Feb 26 '20 at 13:43
  • @Ewan based on the comments of OP it appears that the rules create a graph between premisses and conclusions. A simple graph traversal algorithms could then allow to fire only the relevant rules. However, since we start with an empty set, we’d always find the same result. And this makes the whole thing look weird. – Christophe Feb 26 '20 at 13:53
  • i dont think you do start with an empty set. you start with a ontology structure. other wise the code would always produce an empty set – Ewan Feb 26 '20 at 13:57
  • @Christophe No the input is the ontology O which contains axioms. In line 1 D is assigned the axioms contained in O. The main goal of such algorithm is to define the set of conclusions derivable from O using the rules. Line 5 is wrong, instead ∈ should be the symbol subset , since P indicate a set of axioms, instead the conclusion in an axiom. – marouane nadir Feb 26 '20 at 14:08
  • @marouanenadir This was indeed my question: I was confused by things that look like a set (P, C, O) but are used in notations that suggest they are individual elements. Can we say that D is a set of propositions, initially composed of the ontology's axioms and enriched by firing the rules ? Similarly, P and C would also be sets of propositions ? – Christophe Feb 26 '20 at 14:25
  • @Christophe yes we can say that D is a set of propositions( subset of O), P is a set but instead C represents a proposition, which indicates the proposition obtained by applied the "current" rule. – marouane nadir Feb 26 '20 at 14:51
  • @marouanenadir I edited my answer (now significantly longer, sorry for that) to propose a revised algorithm that fires rules only once. – Christophe Feb 26 '20 at 15:06
  • @Erwan thanks, I misunderstood the scripted O as an empty set. Taking into consideration the additional remarks of OP I've edited the answer. – Christophe Feb 26 '20 at 15:09
  • @Christophe for the improving algorithm which is the complexity? it is quadratic, right? – marouane nadir Feb 28 '20 at 10:21
  • The worst case is when in every iteration only one rule fires and that every rule will get fired in the end. In this case you‘ll have n iterations that take n rules the first time, n-1 the second time and so on. So it‘ll be n+(n-1)+...+ 1=n*(n+1)/2 so indeed quadratic in the worst case. In the best case it‘ll just iterate over the n rules. – Christophe Feb 28 '20 at 13:35
  • @Christophe As i imagined, in your opinion is it possible to implement an algorithm which works in linear time? – marouane nadir Feb 29 '20 at 16:59
  • @marouanenadir I think that if you construct a graph and just propagate through the graph you should reach linear time: a first pass builds the graph structure adding propositions as nodes and rules as edges. A second pass would would follow the edges starting from elements in D. That‘s 2n, so linear. A trick is required for rules with multiple premise, adding a virtual „and“ node. – Christophe Feb 29 '20 at 17:17
  • This answer is ok in general, but I think the first "improved" version is actually no improvement (and should not pretend it is). Just because it does not contain "goto" any more literally, emulating "goto" by using a `while` loop and a boolean flag does not make the (pseudo) code more readable - in fact. it demonstrated what I had in mind when I wrote my first comment below the original question. – Doc Brown Mar 03 '20 at 06:29
  • @DocBrown do you speak of the section „improved structure“ (which indeed mainly removes the goto, but may also perform less evaluations of the premisses, by firing all the possible rules before to restart from the beginning) ? Or do you speak about the section „improved algorithm“ in which the conclusions are evaluated once per rule at maximum whereas it is nxn in the original algorithm? – Christophe Mar 03 '20 at 07:07
  • The first one. Sure, one could say it is an improvement because it *might* perform less evaluations. But there seems to be a superstitious believe (probably some decades old) that code without "goto" is automatically "better" than code containing one. – Doc Brown Mar 03 '20 at 12:03
  • @DocBrown that was not at all my argument. My argument is base on the unnecessary restart of the outer loop. It is not an hypothetical improvement: you can demonstrate that on the average case it does less unnecessary evaluation when you do not restart from scratch at every firing. Gotos can be perfectly justified, [as the 100.000 gotos in the linux kernel demonstrate](https://softwareengineering.stackexchange.com/a/334419/209774). But there is no reason to defend it here. – Christophe Mar 03 '20 at 12:41