unification (was Re: mailing list)

[trb@cs.mu.OZ.AU]

   Date: Mon, 11 Jul 1994 14:18:49 +0800
   From: Randall.Smith@Eng.Sun.COM (Randy Smith)
   X-Sun-Charset: US-ASCII
   Content-Length: 7040

   Interesting ideas on unifying unification into Self!  Don't quite
   know how to unify two Self objects ... the slot by slot thing is a
   reasonbale idea, but could you just send "=" to the objects and see if
   they think they are equal?

Of course it should be done by message sending. I think two objects
should unify iff all their slots unify. (That might not be quite all -
if one of the slots is some kind of object id or name that would have
to be ignored.) I am not sure what the method should be called. When
thinking about unification it is useful to bear in mind that we should
not really have two different kinds of equals e.g. in Pascal ":=" and
"=" or in C "=" and "==". Unification does the work of *both*. So we
must not make the mistake of using one of these to do "unification".

It would be nice to call it "=", but that might already be defined as
assignment or equality testing. Anyway there might be a good case for
abolishing assignment and equality testing and replacing them by
unification. What effect does this have ?

Lets call unification "=", assignment ":=" and test for equality "==".

"=" can do the work of "==" just fine, because "==" only makes sense
when its arguments are instantiated.

Can "=" do the work of ":=" ? Well, "=" can set the value of an
uninstantiated variable, but it *cannot* change the value of an
already instantiated variable (which is probably a very good
thing). If the value of a variable cannot be monkeyed with after it
has been set, then there is much less opportunity to create
side-effects. In fact side-effects could be probably be made
impossible.

For example, you could not increment the value of a variable, because
N does not unify with N+1. You could try sending a message to a
counter object to read its value, then sending an increment message,
then reading the value again, but this wouldn't give side effects
because the two counter values returned would have to be bound to two
different variables, and the value of the second one would not be
available until the message sequence had been completed. Thus
referential transparency has been preserved.

At this point OO people start getting worried. If we can't have
side-effects or assignment, how can we have mutable-state ?

One solution to this problem is to only allow state changes *outside*
methods. In other words any modifications to the values of instance
variables must be the last actions taken by a method. This means that
we can't cause side-effects by referring to the value of an instance
variable, modifying it, then referring to it again.

The counter object can still be incremented - the increment is simply
the last action performed by the increment method.

The way to do this is to clearly distinguish local variables in a
method from instance variables. Local variables can be treated like
logic variables and "=" will do the work of both "==" and
":=". Instance variables would be treated the same way, except that
they would also have a destructive update operator, maybe "<-". A
destructive update could appear anywhere in a method, but it would
only take effect at the end of the method.

Not having side-effects in methods means that the order of statements
in a method is irrelevant, which would avoid a lot of bugs, and give
somewhat better semantics.

Alternatively "=" could be a special operation, alongside ":=" and
"==".

In either scenario an object would typically process "=" by sending
"=" to each of its members (with the corresponding member of the other
object as a parameter). "=" succeeds (returns true) iff all the member
calls succeed. This is a recursive process that eventually reaches
primitive objects e.g. integers, or uninstantiated variables. Unifying
these is straightforward: two instantiated variables unify iff they
are equal, if one is uninstantiated it takes the value of the other,
if both are uninstantiated they both delegate their values to a new
uninstantiated object.


Tim.