giovinazzo-kevin / Ergo

Other
4 stars 0 forks source link

Knowledge Base Refactor #75

Open giovinazzo-kevin opened 11 months ago

giovinazzo-kevin commented 11 months ago

The current knowledge base is a somewhat static object that needs to be updated manually every time.

This works fine in simple cases but the integration with Fiero has shown that sometimes you want to partially share a knowledge base, and update it after its creation.

The new knowledge base needs to:

giovinazzo-kevin commented 11 months ago

See also #66. Ideally the new KB should implement the logical update view. Immutability should help in general, though this concerns dynamic predicates which need to be concurrent. Maybe a mix of both approaches can work.

giovinazzo-kevin commented 10 months ago

The new KB should also implicitly encapsulate the dependency graph, as the two are so tightly coupled that they may as well be the same object.

EDIT: Or maybe this can be done at the interpreter scope level, before the KB is populated.

giovinazzo-kevin commented 10 months ago

So, at a high level, the new KB should be a tree.

Each node has a parent, though there's no need to store its children because we only need to traverse the tree back to the root. Doing so gives us a full representation of the database.

When asserting a new predicate, it is inserted in the current node. When retracting, the current node is tried first, and on failure the parent is tried recursively. This makes it possible to isolate the predicates of a standard library from the predicates defined in user space, and makes it possible to reuse the standard library across different contexts. TODO: Figure out scoping. Calls to assert and retract should target the correct node.

The whole tree shares an index. The index is composed of the predicate's signature and up to N arguments, allowing fast retrieval of facts by sidestepping unification unless strictly necessary.

In order to adhere to the logical update view, the knowledge base should have a "generation" id that is increased each time it is modified. This value, like the index, is shared by the entire tree. When clauses are retracted, they are not immediately erased from the database. Instead, their "erased" value is set the current generation. Once the current goal stops backtracking, these clauses can presumably be removed permanently from the knowledge base.

Each time an assertion or retraction happens:

giovinazzo-kevin commented 5 months ago

See termvm improvements mentioned by #77. If the data representing the predicates in the knowledge base is compiled as well, unification becomes very fast.