Search code examples
prologclojure-core.logicminikanren

Partial Dictionary/Record Unification?

I understand that some Prologs support dictionary-like associative data structures out of the box. For the implementations that do, do they support some notion of partial unification with another structure that doesn't actually contain all of the keys?

For example, in the syntax of core.logic/miniKanren:

(run* [q]
  (== {:foo 1 :bar 2} (partial-map :foo q)))

This would return a single result where q is bound to 1.

Do Prologs give this operation or this partial structure a name?

Solution

  • Some Prolog systems such as Eclipse have a record notation. This can be used when you know in advance the possible keys of your map. But it needs a type declaration. The record notation is also found in Prolog decendant languages such as Erlang.

    The idea is very simple. You first declare a record type (some syntax invented here):

    :- rectype T{K1,...,Kn}.

    Now you can use inside your Prolog program records, just write (again some syntax invented here):

    ... T{F1 = V1, .., Fn = Vm} ...

    At compile type the record will be converted into a compound and can then easily be used in normal unification. The conversion reorders the key value pairs according to the record type declaration, then drops the keys and uses the positions only. Unused positions are replaced by annonymous variables or by default values if the record type declaration also covers this.

    ... T(W1, ..., Wn) ...

    Your example would work as follows:

    :- rectype myrec{foo, bar}

?- myrec{foo=1,bar=2} = myrec{foo=q}

    The latter query would be internally executed as:

    ?- myrec(1,2) = myrec(q,_).

    For more details how Eclipse does it, see for example here:
    http://www.eclipseclp.org/doc/bips/kernel/syntax/struct-1.html

    For dynamic maps where the keyset is not static you can implement dynamic data structures as the other post about SWI-Prolog AVL trees shows. Or ask your Prolog system for a handle to a specific data structure. Implement these with a FFI (Foreign Function Interface) or access these which are already bundled with the Prolog system. Eclipse for example bundles a couple, see "Description" section in the below article:
    http://www.eclipseclp.org/doc/bips/kernel/record/index.html

    Bye