Wiki Discussion: Prolog Many Worlds

Wiki Discussion
1

This is a topic to discuss the Wiki

Prolog Many Worlds

2

Before writing the Wiki, think about doing many examples of all of the module predicates and then alternatives such as the way Paulo does Many Worlds in Logtalk, using Tabling, rewriting the module property of a predicate (if that is even possible), etc. Then also lay the foundation for how a theoretical Many Worlds would work and then show how to implement it in SWI-Prolog, hopefully with a clean solution.

Other ideas: (ref 1) (ref 2)

Yes. a clean solution requires some self notion. Logtalk has that by design. In plain (SWI-)Prolog you have some options, roughly:

  • (Mis)use meta predicates. Problem is that this indeed requires a lot of book keeping, although it isn’t that hard to automate that.
  • Use the SWI-Prolog stack introspection to get some goal on the stack from which we can derive self . This is fairly simple to program and “not so bad”. Can be a little slow if the stacks are deep. It is still a design pattern for which I at some plan want better (means faster and cheaper) support.
  • Notably for this case, where the combination of a thread and a module are used, put the self in a global variable, so you get
    nb_getval(self, Self),
    Self:fact(X).

Of note: predicates, modules and functors (name/arity pairs) are not garbage collected.
Includes example code demonstrating issue. (ref)

EDIT

The idea of this,self or Me is something that might be needed with one possible way to implement Many Worlds.

In thinking about Many Worlds, one of the stumbling points I ran into was that I could not find a formal definition of World.

The commonality that I am seeing is

  1. The use of the word World relates back to the Prolog database being a Closed World
  2. The Worlds are based on the Prolog database of facts and predicates.
  3. There is a way to distinguish Worlds.
  4. If a comparison is made of two Worlds, there is a difference.

Questions:

  1. Should a World allow for dynamic predicates? At present that seems reasonable, but in practice may be hard to implement.
  2. How should the Worlds be created?
  3. Can worlds communicate with other worlds? This can be tricky if worlds are composed from other worlds.
  4. Will the garbage collector have to be considered?
  5. If a World is copied, and worlds have references, is it a copy of the reference or the values in the World. This is tricky if the worlds are composed from other worlds. This reminds me of Retroactive data structure. It also reminds me of TerminusDB.
  6. Are there different types of Many worlds? Are the some worlds composed of other worlds? Are all of the worlds flat, not composed of other worlds? Are there worlds that change and become identical to other worlds? Can worlds span new worlds? Can worlds have Sub-worlds? When trying to define the operators of Many Worlds, this is reminding me of Category Theory and in trying to identify ways to classify Many Worlds this reminds me of Multiverse.
  7. Do worlds survive backtracking?
  8. Do worlds have to be ground?

EDIT

Asked about Many Worlds at the the TeminusDB forum. Here is the reply from @gavin.mendel.gleason

TerminusDB was designed with the idea of many worlds in mind conceptually. Queries occur at a given state of the world, and updates are actually transitions to new worlds. You can also create branches, which allows you to have a tree of worlds. It is even possible to do meta-reasoning about the multiverse by looking at multiple worlds simultaneously in a query.

Currently our only merge strategy is rebasing which means that our worlds are always only accessible by a tree like branching. However in the future we will introduce proper merges, in which case the associated Kripke structure will be a DAG (directed acyclic graph).

Kripke structure (Wikipedia)

Click to expand

Dynamic Dispatch.

How do you discover worlds? current_module/1
How do you know about a world once you discover it? predicate_property/2 e.g. predicate_property(<world>:Predicates).
With tabling the query results to the worlds could be tabled, but tabling AFIAK is a tree structure and not a graph. But maybe it does not matter as the execution of code is a tree and not a graph. Could the execution be a DAG with tabling?

Software build, List of build automation software, Artifact (software development)
JavaScript module systems - See What are CJS, AMD, UMD, and ESM in Javascript?

Starting to think that the the code that is run is an artifacts of a build process, and that the build process is based on a query with operations specific to creating the artifact. In so thinking there has to be an atom, think the smallest part that can not be divided, which would be either the head or body, but not predicate. For the body it would have to be able to select out individual clauses of a predicate. Also this may require the redesign of predicates so that they have no internal use of ; but instead rely on multiple clauses. The code may even have to be pure for this to work.

Some of the kinds of operations would be, select, order, group (thinking something like reexport for modules), where (thinking predicate indicator or Type, mode and determinism declaration headers ), selection by identity (IIRC clauses have an identity internally). This is looking more like SQL, but I should check out the TerminusDB query language. This does not take into account a temporal variable.

Modularity in Mathematics
Locales: a Module System for Mathematical Theories

Starting to bump into the notion that predicates and facts might need to be handled differently, e.g. Loading fact files, is this still the preferred means?

Child Modules for Erlang and Prolog

6

The extensions to Prolog and Planner-like languages for MW that I’ve seen (need to find refs) basically look something like this:

  • new_world(W) - create new “world”

  • new_world(W,WP) - create new world, inheriting from parent world

  • assert(T) - assert term in current world

  • assert(T,W) - assert term in explicit world

  • (similarly for retract)

  • copy_world(W,W1)

  • get_parent_world(W,PW)

  • call_in_world(G,W)

  • call_in_new_world(G,PW) - short for new+call

  • merge_worlds(Ws, W)

  • set_current_word(W)

  • add_current_world(W)

  • remove_current_world(W)

  • push_world(W)

  • pop_world(W)

The last set (set/add/push,etc.) is important, as you are setting/adding/removing current database(s) that the Prolog default dynamic predicate lookups operate on – so you change the behavior of existing, unmodified Prolog code that gets called in the context of the new world(s).

FWIR, inheritance is dynamic (newly asserted terms in parent worlds are visible to children) so if you want a “snapshot” you need to take it first – but if you wanted parents to be immutable, that is another option, or “locked” worlds at runtime can be an option. Here call_in_world is shorthand for a protected push/call/pop chain, but it’s also possible to have call_in_world be the only way to call execute in the context of a new world, rather than have it happen by default using the concept of a current world(s).

Rather than have all dynamic predicates operate on the current world, I could also see the option of opting-in with something like:

:- multi_world( [hypothesis/3, position/2] )

1 Like