Runtime Variables / Caching Execution Graph Delegates

[G3Kappa]

Ergo is built on an immutable base layer. Terms, predicates, scopes. Everything is immutable by default -- and this plays nice with the interpreter as per the original architecture.

The switch to a VM-based architecture, however, is pointing out one obvious flaw with the immutable model: efficiency. Profiling reveals that most of the time spent while tail-recursing over for/3 is actually spent instantiating and substituting predicates (and their associated knowledge graphs). The time spent actually compiling the graph is rather small by comparison, but still significant.

And this makes sense to a degree, because when substituting multiple copies of the same variable a lot of redundant operations have to be performed. Additionally, terms have to be traversed fully every time.

A runtime-friendly model would represent variables as mutable so that multiple copies can be updated with one operation and so that terms are updated automatically without ever having to traverse them, by just applying a substitution to the corresponding RuntimeVariable and having the effect propagate through all terms that reference it.

One issue with this approach is that Variables were never meant to be mutable in the initial architecture. Therefore they are readonly structs that can't be inherited from. If I made a RuntimeVariable wrapper that inherited AbstractTerm, then there would be a few problems:

• Some places in the code check, e.g., if(term is Variable { Ignored: true }). Since RuntimeVariable can't inherit from Variable, this would require a workaround, possibly an IVariable interface.
• Dictionaries have an Either<Atom, Variable> functor, and this presents similar challenges as the previous point.
• A mechanism to separate runtime terms from immutable terms would still be required, encapsulating them inside predicates (or a runtime version of predicates) might work as they are the entry point for compilation.

[G3Kappa]

Considerations

I would much rather have a separate RuntimePredicate as the entry point for runtime code. It makes sense that all runtime logic ends up being confined there. The only real difference between an immutable predicate and a runtime one is that the runtime one has dynamic variables that handle mutable state in place of the traditional immutable variables. And it has a lifetime that starts when it's initialized and ends after it's executed.

As mentioned above, instantiation and substitution need to happen instantly for all copies of the same variable regardless of how deeply nested they are, and they should be performed only once. So a runtime predicate needs to hold a list of its runtime variables, and apply all substitutions to those variables instead of creating a new term from scratch for the head and body.

[G3Kappa]

Runtime variables (and mutable terms, in general) are still on the table -- but the caching of compiled predicates has mostly been solved.

[G3Kappa]

Breakthrough

The branch termvm contains an exciting new approach that seems to work well so far. It requires extensive refactoring but it promises unparalleled execution speed when it comes to unification. Using this approach, substitution becomes redundant as it is applied automatically when unification succeeds.

The approach consists of having a designated object that represents a "term memory" area that can contain constants, variables, structures and information about abstract terms. This memory area is populated with all terms that the vm needs in order to compile its query, except that they are stored in a compressed form and passed around as pointers. Unification acts on this intermediate representation, which is expanded back into a regular term only at the very end, when it is consumed by whatever predicate it ended up in.

Ideally, this should allow me to implement tiny "islands" that use this new approach and progressively expand them until the old approach becomes obsolete.