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

  • Hint: Noone hinders you to use variables with pseudocode (and use these with an ernclosing loop). – πάντα ῥεῖ Feb 25 '20 at 17:10
  • "simple" pseudocode – Ewan Feb 25 '20 at 18:25
  • Looks fine to me. Surely you can avoid the goto, but I doubt this would increase readability. – Doc Brown Feb 25 '20 at 18:34
  • Pseudocode is just code, but with a made-up language instead of Java. It's not magic and it's not special. The only reason you use pseudocode is so that C# programmers and Java programmers and Python programmers and Haskell programmers can understand your code the same, and the computer doesn't need to run it. – user253751 Feb 25 '20 at 18:36
  • 1
    @Ewan Usually recursion isn't the best way to go. I am trying to avoid it like the pest. – πάντα ῥεῖ Feb 25 '20 at 19:43
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.

  • looks like this calls getConclusion more than required – Ewan Feb 26 '20 at 8: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 8: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 9: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

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.