Re: Semantics of Multiple Values (updated RCR)

At 23:39 27/04/2004 +0900, you wrote:
>|*  Comparing multiple values
>|*  Unify operator
>
>I have to confess I couldn't understand those two proposals, how they
>behave, and how they are useful.
>
>                                                         matz.

I have some Prolog background and I believe Prolog is the
language where unification is central.

First, I have to say that what I proposed is a "poor man's unification".
Not that its value is low, only it does not turn Ruby into Prolog.

Q. So, what is a "poor man's unify".
A. Well... it is Unification. But without a key aspect of it: Backtracking.

Q. Backtracking ?
A. Backtracking is what happen when a function can return many values,
once a time, like a generator if you wish. So let's forget about that.

What remains is a mechanism that does two things at once:
   - comparison
   - assignment

Q. You mean, I can have my cake and eat it too ?
A. Cool, isn't it ?

Comparison: ==
   We know what it is already. It depends either on the identity of objects
   or on their value. Let's skip the easy one.

Comparison by value:
   For scalar type, it's easy, "a" is "a" and 1 is 1.
   For collection, it's slightly more complex. You compare (note the
   recursivity introduced here) each element of the collections.

Q. That's not exactly true, .==() is called.
A. True. Let's assume that the unification algorithm walk the collections
itself, calling some .unify() instead.

So far, so good, known stuff.

Now, Assignment: =
   Assignment is about setting the value of a Variable.
   Before the assignment, there exists 2 cases:
     - The variable exists already. It is "Bound" to something
     - The variable does not exit.  It is "Free"
   After the assignment the variable is bound to some value.

Finally, Comparison + Assignment:
   Let's assume that, in addition to a scalar and collection, a
   value can be a reference to a variable (not the case in Ruby today).

Q. Then, what happens with comparison ?
A. That's easy:
     - For a variable that exists already, you pick it's value and
       you use it to do the comparison. "Bound" case.
     - For a variable that does not already exists, it is even easier,
       you assume that the comparison succeed and, as a side effect,
       you "create" the variable with the value it was compared against.

Q. That's it !
A. Yes !

Q. Now, what about the consequences/impacts on Ruby ?

A. First and paramount is that when building a value, in the context
of a "Comparison + Assignment", you cannot proceed as usual. i.e.
unify [a,b], [c,d] is not like [a,b] == [c,d].

Q. OK. How ?
A. When you evaluate the later (==), you build values getting rid of the
variables, i.e. you use the value of the variable in place of the
variable itself.

Whereas with unify, you don't. Instead, whenever there is a variable,
you keep it.

Q. How is that possible ?
A. Well, it is... you need something that does not exists in Ruby so far,
an object that describes a variable. In such a way that, instead
of using the variable's value, you reference the variable itself.

Q. In C, this is &var, the "address of var", similar ?
A. Yes, pretty much the same.

So, if a is 1, b is 2... then
   [a,b] == [c,d] is about comparing [1,2] with [3,4] and...
unify [a,b], [c,d] is about [&a,&b] and [&c,&d] (using C's syntax)

That's an additional level of indirection.

Q. OK. Nice. But where is it useful ?
A. Very often ! It is already there in Ruby actually !

Q. No kidding ?
A. No, look.

def f( a, b, c ); ... end
When f is invoked, some unification occur:
   unify f's args, [a,b,c]

a, b, c = f()
When assignment with multiple values occur:
   unify [a,b,c], f() # Q. Almost... what if f() returns [1,2] ?
                      # Q. What if a, b or c already exists ?

p = proc( { |a,b,c| ... }
p.call( 1, 2, 3)
When Proc get their parameters:
   unify [a,b,c], proc's actual parameters

A. "unify" is there but not exactly with the same semantic:
   - Assignment always occur, even if variable is already bound.
   - nil is assigned to the variable when there is no better value.
That behaviour is what I call "assign", versus "unify".

  "unify" and "assign" work even better if a new type of
value is introduced (in addition to the one introduced already,
the one that is a & reference to a variable).

The new type is "FreeClass", much like TrueClass. That is
a Singleton too.

Q. What is it for ?
A. a = FreeClass.instance() is the way to "free" the "bound"
variable named "a". Shorthand: a = free

Now, some examples, explained.

def test()
   unify a, 1
   p a        # => 1, a was free, now it is bound
   a = free
   p a        # free, a is free again
   unify a, 2
   p a       # => 2, a was free
   unify a, 3
   p a      # => 2, a was bound, unify failed.
   a = free
   unify [a,b], [] # Fails (evaluate to false)
   unify [a,b], [1,2]
   p a, b   # => 1 2, unify succeeded.
   unify [free,b], [1,2] # Succeeds
   unify [free,b], [1,3] # Fails
   unify [free,b], [1,c] # Succeeds
   p c      # => 2... it works both ways
   a = b = c = free
   unify [a,b], [1,2,3]
   p a, b  # nil nil, unify failed
   assign [a,b], [1,2,3]
   p a, b  # 1, 2, assign is more tolerant
   assign [2,b], [1,3]
   p b     # 2, assign failed, no assignments done
end

I hope that this explanation, way too long, gives you
some idea about how powerful an "assign" and "unify"
operators could be and how close they are to what
already exists.

Nota: *, like in f( *args), makes them even more powerful !

Yours,

Jean-Hugues