Partial Dictionary/Record Unification?

Question

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?

Dong

I've done a basic search, but have not found any Prolog offering hashtables. Could be because the Prolog rule base is usually implemented via a well crafted hashed table, thus hashing is 'intrisic' and more an 'implementation detail' than a widely needed feature. See for instance this post from the SWI-Prolog author. – Edgardo

don't know if this still interests you, but recently I posted here a very simple impl'n of extensible records, where I can call ?- attr(A, [foo-1, bar-2]), attr(A,[foo-Q]). and get back Q=1. the impl'n: attr(A, [N-V|R]):- memberchk( N-X, A), X=V, attr(A, R).; attr(_, []). that's all. – Derisible

Answer 1

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

Thimble

Thanks! I was looking for a specific example of support like this one. – Dong

Answer 2

In general one works around the poor selection of fundamental data types in Prolog the standard way: by adding libraries and using interfaces. SWI-Prolog, for example, comes with the assoc library that implements an AVL tree-based association data structure. (As an aside, balanced trees are more common in functional and logic programming than hash tables because it's easier to create "persistent" data structures on trees than hash tables—persistent in the FP sense of sharing internal structure.)

Using this library looks something like this:

?- [library(assoc)].
% library(assoc) compiled into assoc 0.00 sec, 97 clauses
true.

?- empty_assoc(Assoc).
Assoc = t.

?- empty_assoc(Assoc), get_assoc(test, Assoc, V).
false.

?- empty_assoc(Assoc), put_assoc(test, Assoc, foo, Assoc2).
Assoc = t,
Assoc2 = t(test, foo, -, t, t).

?- empty_assoc(Assoc), 
   put_assoc(test, Assoc, foo, Assoc2), 
   get_assoc(test, Assoc2, Value).
Assoc = t,
Assoc2 = t(test, foo, -, t, t),
Value = foo.

Once you have something that gives you an interface like this, you can define all kinds of logical relations on top of it. Once you have logical relations, Prolog's normal unification machinery will take care of the rest—no special support for this or that data type is required. Based on your requirements, I think what you want is like a subset relation, except checking both that all of one association are in the other and they all have the same value. I guess that would look something like this:

association_subset(Left, Right) :-
  forall(gen_assoc(Assoc, Left, Value), get_assoc(Assoc, Right, Value)).

This predicate will only be true if the Left association is a subset of the Right association, as defined above. We can test it and see if it's doing what we want:

simple(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, foo_test, V1),
  put_assoc(bar, V1, bar_test, Assoc).

complex(Assoc) :-
  simple(Assoc1),
  put_assoc(baz, Assoc1, bazzle, Assoc).

unrelated(Assoc) :-
  empty_assoc(Empty),
  put_assoc(baz, Empty, bazzle, Assoc).

...

?- simple(X), complex(Y), association_subset(X, Y).
X = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t),
Y = t(baz, bazzle, -, t(bar, bar_test, -, t, t), t(foo, foo_test, -, t, t)).

?- simple(X), simple(Y), association_subset(X, Y).
X = Y, Y = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t).

?- simple(X), unrelated(Y), association_subset(X, Y).
false.

?- complex(X), simple(Y), association_subset(X, Y).
false.

We can translate this to your exact question like so:

left(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, 1, Assoc).

right(Assoc) :-
  left(Assoc1),
  put_assoc(bar, Assoc1, 2, Assoc).

?- left(L), right(R), association_subset(L, R), get_assoc(foo, L, Q).
L = t(foo, 1, -, t, t),
R = t(foo, 1, <, t(bar, 2, -, t, t), t),
Q = 1.

I realize that this answer doesn't really answer the question you asked, but I hope it answers the question beneath the question. In other words, there doesn't need to be special support for these data structures—the above predicate could be defined over association lists as well, you can see that all you'd need is the usual ways of making empty associations, adding, testing for, and generating the keys/values of the association and the underlying data structure becomes irrelevant. No special support is necessary either data-structure-wise or unification-wise. Special syntax would certainly make it nicer to look at! But it isn't necessary to get the behavior you desire.

Cepheus

Thanks for explanation! I know I could have implemented it from scratch but I was curious if the pattern was common enough for Prologs to have specific support for it and if this support had a name. – Dong

Answer 3

It is not that clear to me what you actually want, (you have removed the hashing aspect), but maybe you rather want feature terms or feature structures?

They are popular to linguists and have been part of Life.

It is possible to implement them with the help of attributed variables, but so far, I have not seen much of a demand for them.

You can also simulate them a bit clumsily with syntactic unification. It is clumsy because you need to represent each feature with a separate argument (you can do this slightly better, but it is also more complex then). So if your program contains n features, a feature structure will contain n different arguments most of which will never be touched. However, unification will then work directly as intended.

Zedekiah

Yes the hashing aspect wasn't critical, just an associative data structure where key order doesn't matter to the user. Yes having to explicitly enumerate each argument would be less then ideal - the Eclipse sugar mentioned above seems to do what you describe without forcing the user to do this by hand. – Dong