Re: mailing list

[tlb@endor.harvard.edu]

> Two objects would be unified by unifying all their slots. There are
> some interesting questions here, since slots are identified by name
> which is impossible in Prolog. The nearest thing Prolog has to objects
> is terms, and their components are identified by *position*. Clearly
> slots with the same name would have to unify for the whole unification
> to succeed, but it is unclear what to do if a named slot is present in
> one object but not the other. This could either be interpreted as
> failure, or the other object would get a copy of the slot. The latter
> produces an interesting kind of inheritance, but it is probably too
> permissive - two arbitrary objects will typically have mostly
> differently named slots and probably should not unify. Clearly
> unification should not be attempted on the names of objects, since
> this would always fail.

I think this is less useful than you might expect in designing
programs. A very nice feature of objects is that for a given
appearance of an object, it may have varying formats for the contained
data, for implementation reasons. You still want two objects to unify
if they represent the same thing, but have different stuff in their
slots.

> For logical and efficiency reasons it would be nice if the
> representation of values was unique i.e. two slots could have the same
> value if and only if they referred to the *same* object. That means it

Then any object will only unify with itself. You don't ever need to
check its slots. You have to be able to unify two distict graphs of
objects based on them having the same appearance.

I actually built a little system to do a weak form of unification in
Smalltalk. You just imbue your classes with a 'unifyWith:'
method. Numbers and Arrays and Symbols are easy. I
added an UninstantiatedLogicVariable class, which turns into a
delegate for an object when it gets instantiated. I defined reasonable
semantics for the application objects I cared about.

However, I balked at the problem of ensuring termination with
non-disjoint graphs. There are known solutions to this from the Prolog
community, but I didn't have the gumption to implement them (in fact
most commercial prologs have only a weak version of guaranteed
termination).

Example in a typical prolog:

?- A = x(B), B=x(C), C=x(A), L=x(M), M=x(L), A=L.

produces an answer, while in fact the correct answer is arguably 'no',
because you cannot unify a 2-cycle with a 3-cycle. In my
implementation, unification would never have terminated.

If you just want to use this sort of unification for pattern matching,
then it is probably perfectly adequate. The only tricky parts are
arranging for the instantiated UninstantiatedLogicVariable to handle
delegation (much easier with St V become: semantics), and defining
unification for your application classes.

In fact, I also wrote a nondeterministic execution system based on
continuations (which aren't too hard to implement in Smalltalk - I
don't know about Self). I then arranged to trail the binding of
UninstantiatedLogicVariable instantiations, and got a complete little
logic engine. I kept finding surprises in the semantics, though. Also,
it turns out that you need cuts, which I didn't implement.

Most of all, I found it was much harder to use than I thought. I like
and appreciate Prolog, but the Smalltalk class library just doesn't
really work with logic variables.

e.g. Does a Dictionary with 3->4 unify with a dictionary with 1->8 to
produce a dictionary with both? How about OrderedCollections, one of
which is the prefix of the other? But then collection1 size changes!
You get the idea.

--
Trevor Blackwell         tlb@das.harvard.edu          (617) 495-8912
(info and words of wit in my .plan)