Implementation - rubyunworks/prime GitHub Wiki

Under the hood Prime works just like Prolog. It use a solution search algorithm call backtracking ...

Concurrency

Unlike traditional Prolog, Prime's algorithm is inherently concurrent, and massively concurrent at that. Prime can take advantage of as many processors as your system has available. It does this via Prime's backtracking algorithm. When ever Prime reaches a choice point it splits the search up into separate light-weight concurrent routines. It does up to a specific number of routines dependent on a systems architecture a runtime setting. As routines return new routines are made available other choice points.

TODO: Explain backtracking a bit here to make this clearer.

Lists

(NOTE: Is this alternate implementation of lists truly useful for Prime?)

Prolog lists are implemented as linked lists. A linked list consist of nodes with a value and a single link, which we can represent as:

a -> b -> c -> d -> e

Linked lists are great if all you want to do is process the nodes in sequence from beginning to end and add or remove nodes along the way. But to do anything beyond this, such as locate a node by it's position, or search a list from back to front, then we are either out of luck or we are going to be wasting a lot of compute cycles to process.

To overcome these limitations, Prime implements lists as special binary trees. This allows them to be manipulated in more arbitrary ways very efficiently. Each node in the tree has a value and a count along with it's two links. The left link is always consider prior to and the right link anterior to the current node. Hence we can represent a list [a,b,c,d,e] as:

       d,5
      /   \
    b,3    e,1
   /   \
 a,1   c,1

While linked lists would generally be enough for most problems, since solutions are found by sequential searching, there are data structures that would be difficult to model without this additional flexibility.

OPEN QUESTIONS

  • Have there been any advance in the area of backtracking? Are there alternative search mechanisms to backtracking?

  • Is there some fundamental way we can apply probability to the system? For example It would be awesome to be able to very easily apply Bayesian logic.