archives

Aggregations (e.g., sets) in Logic Programs

Prolog and its derivatives have lacked adequate ways to compute with aggregations, e.g., sets.

For example, suppose there is a ground-complete predicate Link[aNode, anotherNode, aCost]
that is true exactly when there is a path from aNode to anotherNode with aCost.

When ⊩ Path[aNode, aNode, aCost]→ // when a goal is set for a cost between aNode and itself
   ⊢ aCost=0▮           // assert that the cost from a node to itself is 0

The following goal-driven Logic Program works forward from start to find the cost to finish:

  
When ⊩ Path[start, finish, aCost]→ 
   ⊢ aCost=Minimum {nextCost + remainingCost
                     | ⊨ Link[start, next≠start, nextCost], Path[next, finish, remainingCost]}▮
          // a cost from start to finish is the minimum of the set of the sum of the
              // cost for the next node after start and
                   // the cost from that node to finish

The following goal-driven Logic Program works backward from finish to find the cost from start:

When ⊩ Path[start, finish, aCost]→ 
   ⊢ aCost=Minimum {remainingCost + previousCost 
                      |⊨ Link[previous≠finish, finish, previousCost], Path[start, previous, remainingCost]}▮
          // the cost from start to finish is the minimum of the set of the sum of the
              // cost for the previous node before finish and 
                  // the cost from start to that Node 

Note that the above Logic Programs work together concurrently providing information to each other.

For more information see Inconsistency Robustness for Logic Programs