Possible Solution for Left-Right Precedence and More when using Multimethods? (was re: oo)

[David Nolen]

Having thought a little about multiple inheritance when implementing Spinoza I also ran into this problem. However at the time I wasn't hindered by multifn dispatch as much as the fact that parents cannot be ordered (because calling parents on a tag returns a set) as pointed out by Mark. I understand Rich's point that hierarchies probably shouldn't be directional, but for the sake of practicality why not allow the programmer to specify that a tag (or even the whole hierarchy) should in fact have its relationships be ordered? In general prefer-method seemed to me (I could be wrong) to be a last attempt solution- when there is just no other way to resolve an ambiguity, and this ambiguity is not of the hierarchy, but of multimethod dispatch. As pointed out by Konrad & Rich, you can work around the limitation of hierarchies right now with a lot of prefer-methods.  But as Mikel points out, with current state of prefer-method you have to hunt through code to find out where these prefers were made and for what reason and they assume that you've already written your methods (this for me is the deal breaker).

In anycase my general feeling (in agreement with Mark) is that the problem isn't with multifns but rather with how hierarchies are constructed.

So the achilles heel of hierarchies seems to be that when you call parents (and related fns) on a tag you get a set - it has no order.  For single inheritance hierarchies this is fine, but for multiple inheritance I think this becomes a problem a very fast. Working on Spinoza, I realized I would have to keep my own ordered list of parents in order to support left-right precedence, basically keeping an ordered copy of the whole hierarchy. Again prefer-method is only useful for fixing method-level ambiguities.  There's no general way to say, type A always precedes type B without writing quite a bit of explicit code (or hiding the problem away with macros).

Here's something that might kick of a dicussion to a proper solution (I am sure there are some gaps in my logic), why not allow something like the following?

;; allow control of how tags get introduced into the hierarchy

(def h (make-hierarchy :parents-fn fn1 :ancestors-fn fn2 :descendants-fn fn3))

;; add a new parent insertion fn to a hierarchy

(add-parents-fn h fn4) ;; -> returns a new hierarchy with the parents fn set, all parents sets are converted into vectors

;; add a new parent insertion fn to a hierarchy for a specific key, only the parents of ::my-tag are converted into a vector

(add-parents-fn h fn4 ::my-tag)

;; a hierarchy fn might look something like the following

(defn my-parents-fn [parents new-key]

   (conj parents new-key))

If my thinking is correct this is pretty flexible. This doesn't break the meaning of hierarchy for any existing code.  It doesn't change the signature of multimethods.  Yet now a user can provide fns that sorts a hierarchy anyway they please, and it doesn't even have to be the entire hierarchy.  This code will probably live in one spot where anyone could look to understand how the hierarchy is being constructed.  All high-level precedence ambiguities can now be resolved by looking at the hierarchy.  prefer-method does only what it was intended to do- resolve method level ambiguity.

David

[mikel]

You can build a working generic functions implementation for any
domain that obeys a protocol consisting of four functions:

1. fn [v & [context]] -> t

A type-returning function that returns a usable type-value for any
input in its intended domain.

2. fn [t1 t2 & [context]] -> Boolean

A type-ordering function that returns true if t1 is to
be considered "more specific" than t2. This function
must yield values that permit a stable, monotonic
sort of types in the domain.

3. fn [t & [context]] -> s

Where s is a sequence of type-values. A supertypes function that,
given a type, returns a sequence of all types that are to be
considered supertypes of it.

4. fn [inits & [context]] -> t

A type-creating function that returns new type-values that
function (1) can produce when applied to domain values,
that (2) can order, and that (3) can take as input to yield
a canonical list of supertypes.

The optional context argument is necessary because some domains are
restricted, and operate only with respect to some specific context. An
example is a domain defined in terms of one or more ad hoc
hierarchies.

If you can implement this protocol for a domain, then you can have
generic functions that are defined for that domain, and you can have
deterministic dispatch and next-method for values in that domain.

There's no obvious way to implement (2) for types defined using
Clojure's ad hoc hierarchies, because (parents t) returns a set, which
is unordered. That doesn't mean there's no way at all to implement
(2); it means that any working implementation of (2) imposes an
ordering on (parents t). Since more than one such ordering is
possible, more than one implementation of (2) is possible, and
different ones constitute different domains.

You can even write an implementation of (2) that asks the user how to
order unordered type values when the question needs to be resolved
before processing can continue. That's the solution used by the
existing MultiFn dispatch mechanism, and with this protocol, you can
have it if you want it.

You can define any number of generic function domains that operate
side-by-side. It would be prudent in that context to be clear about
the domain you're defining, and maybe implement the protocol's
functions in a way that clearly identifies inputs that aren't in the
domain (if any). For example, if your type-returning function relies
on metadata, then if it encounters a value that doesn't support the
IMeta interface, it should raise an exception that complains that it's
being applied to a value not in its domain.

You also need to be careful that your type-creating function creates
types that the other functions can operate on correctly.

Strictly speaking, function (4) doesn't have anything to do with
generic functions; you only need functions (1), (2), and (3) to
implement them. Function (4) is a convenience: a constructor for
values in the domain defined by (1), (2), and (3). For some domains,
(4) might just be identity applied over some set of existing values.

[Rich Hickey]

Here are some problems/limitations of existing OO/GF systems that I
don't intend to repeat:

A) They provide only a single declaration point for all superclasses
of a class
B) They consider the local declaration order of superclasses to be
significant
C) They conflate hierarchies and graphs containing sideways edges
having nothing to do with hierarchy
D) They provide only a single slot for type/class per object
E) They allow conflicting local superclass declaration orders,
creating cycles in the graph not detected until subsequent derivation

Image:

(class Horse :supers [Animal])

Now suppose some user of Horses, but not the library author, wants to
consider Horses to be Transportation. Due to (A) they can't, without
convincing the author of the library to change the declaration to
include Transportation in the supers:

(class Horse :supers [Animal Transportation])

Here's where (B) rears its ugly head. At this point in time there may
be no significant basis for determining the order in which these
declarations should occur. It is not an inherent property of the
derivation relationship (C), but must be specified here and now due to
the fact that the derivation declaration does 2 jobs (derivation +
precedence). It might never matter, but if it does matter it will be
because eventually some method is defined on both Animal and
Transportation, and a decision needs to be made as to which should
apply to Horse, e.g.:

(allowed-on-road Animal) -> false
(allowed-on-road Transportation) -> true

in order to make (allowed-on-road Horse) work the way we want (i.e.
true), and presuming we want to inherit our behavior rather than
specify it (the laziness presumption), we'd prefer Transportation
precede Animal in the supers declaration of Horse. Another trip to the
library author.

Here's where (D) rears its ugly head - this is a global declaration
that universally applies. One could easily imagine another method
where it would be preferable that Animal preceded Transportation when
applied to Horses (the library author might say no)

As for (E), if we later create:

(class Camel :supers [Transportation Animal])

no advances in genetics can allow us to make a HorseCamel, since the
resulting graph can't be ordered. (We can't put HC on the front of a
merge of H->A->T and C->T->A that preserves their relative orders)

These are just OO devices, not logical systems - they are just
arbitrary mechanisms full of corner cases and creeping complexity. I
don't know why we are in such a hurry to recreate them.

----------------------------
Here's how I think about it:

- Hierarchies have nothing to do with multimethods/GFs per se.
- They are created by independent, atomic, logical statements about
derivation relationships
- Those statements can come in any order, or place
- The logical statements are validated to not create cycles (i.e. when
considered as a set of logical assertions, they include a transitivity
rule and one asserting a parent can't be a child of its child, plus a
consistency check)

This gives us a nice logical construct with general applicability.

We can then think about leveraging hierarchy in a dispatch mechanism.
Using a hierarchical system in dispatch matching means we can inherit
behavior, and, within a lineage, ensures a logical precedence due to
the, well, linear nature of lineages. Multiple inheritance is also not
a problem, as separate multimethods can be defined on separate trees
without conflict or ambiguity.

It is only when you have defined methods of the same multimethod on
two independent paths to the same child that things cannot be
logically resolved. This is something you should do only with great
reluctance, as it represents a true logical ambiguity, e.g. you've
said animals aren't allowed in the street, but transportation is, and
a horse is both. I still contend you'll encounter it most frequently
when trying to incorporate existing Java hierarchies. If you find you
need it frequently other than in that case, you have a sloppy design
IMO.

A monotonic ordering of the entire graph is not an essential property
of a hierarchy, in fact, I think it is more of a crutch than a
feature. Making logical ambiguities go away mechanically only
encourages more ambiguity and brittleness in the dependencies on the
mechanical resolution.

So, when there's an ambiguity we can always define a specific method,
and usually should. Being lazy, we also have prefer-method to resolve
it in favor of one inherited method, at the point we have the facts
about the particular ambiguity, and differently for each method if we
desire.

Here are the areas I'm looking to improve:

- There's no easy way to talk about "the method you would get if you
were dispatch value X". Note that this is not the same as call-next-
method, which reintroduces global ordering requirements, but allows
for easy explicit reuse of already-defined methods.

- Currently, a preference doesn't encompass the path through the
preferred value to its ancestors, but could.

- If you have a set of common preferences, there's no easy way to
create them in advance and share them among methods. There are issues
here related to ensuring preference consistency and caching.

Can we please move forward in trying to implement something better
than CLOS GFs? I have no interest in going backwards.

Rich

[mikel]

On Mar 31, 9:32 am, Rich Hickey <richhic...@gmail.com> wrote:


> Can we please move forward in trying to implement something better
> than CLOS GFs?

Maybe. Let me know when you think of something better, and I'll do the
same. When we agree, I'll toss my GF implementation out the door. In
the meantime, it's made my life better, so I'll keep using it. I can
stop talking about it in the Clojure group, if you like.

> I have no interest in going backwards.

Nice. Me either. I'll do my own navigating, though. I just got my
HorseCamel out of the weeds.

[Laurent PETIT]

Hi,

2009/3/31 Rich Hickey <richh...@gmail.com>

Here's how I think about it:

- Hierarchies have nothing to do with multimethods/GFs per se.

True,

So, along the lines of my previous post, could it be made possible to let the user provide its own multimethods "candidate dispatch-values filtering" and "candidate dispatch-values narrowing" if needed ?

And also, maybe, try to not add hierarchies concerns in general multimethods declarations :
Currently, defmulti accepts a hierarchy as an optional parameter, and it seems to me that it contradicts what you wrote above, that "Hierarchies have nothing to do with multimethods/GFs per se."

Or maybe it's a problem with my comprehension of a subtlety of english ?

Making multimethods more generic could also help the clojure ecosystem work on a solution to the problem of multimethods working on hierarchies (which could still be made the default "flavor" of multimethods, thus allowing the 'hierarchy' optional parameter to remain valid with the "clojure hierarchies" multimethods flavor), while still starting from the same "building block".


Sorry for using this thread as a way to speak one more time about the possibility to make multimethods more general, but since nobody reacted to my previous posts either bashing me or plussing me, I'm still not knowing if you consider it a good idea or not, and for which reasons.

Regards,

--
Laurent

[David Nolen]

Many thanks for the long and reasoned reply (and to mikel as well for adding his thoughts). I apologize for my slowness in understanding the nature of multimethods- it's tricky converting my existing knowledge ;)

On Tue, Mar 31, 2009 at 10:32 AM, Rich Hickey <richh...@gmail.com> wrote:

Here are the areas I'm looking to improve:

- There's no easy way to talk about "the method you would get if you
were dispatch value X". Note that this is not the same as call-next-
method, which reintroduces global ordering requirements, but allows
for easy explicit reuse of already-defined methods.

This is the last bit of multimethod reflection I would love to see. Combining prefers and this feature would make it simple to provide functionality like call-next-method/super in a performant way (I believe).

 

- Currently, a preference doesn't encompass the path through the
preferred value to its ancestors, but could. 

- If you have a set of common preferences, there's no easy way to
create them in advance and share them among methods. There are issues
here related to ensuring preference consistency and caching.

This would be awesome.

 

Can we please move forward in trying to implement something better
than CLOS GFs? I have no interest in going backwards.

Rich

I'm ready to move on, and these thoughts sound great. Onward! ;)

David

[Konrad Hinsen]

On Mar 31, 2009, at 16:32, Rich Hickey wrote:

> Here are some problems/limitations of existing OO/GF systems that I
> don't intend to repeat:

...

I agree that these are not desirable features. I have had to work
around some of them many times in the past. Traditional OO combines
aspects that should better be handled separately.

> Here are the areas I'm looking to improve:
>
> - There's no easy way to talk about "the method you would get if you
> were dispatch value X". Note that this is not the same as call-next-
> method, which reintroduces global ordering requirements, but allows
> for easy explicit reuse of already-defined methods.

That would be VERY nice to have. More than once I ended up writing a
private function that I then called from several methods in the same
multimethod, to avoid code duplication.

> - Currently, a preference doesn't encompass the path through the
> preferred value to its ancestors, but could.
>
> - If you have a set of common preferences, there's no easy way to
> create them in advance and share them among methods. There are issues
> here related to ensuring preference consistency and caching.

At the moment, a multimethod takes two dispatch-oriented parameters:
a hierarchy and a dispatch function that returns a single item from
the hierarchy.

How about generalizing the dispatch function in two ways:
- it can return a sequence of items that will be tried in order
- it can access the hierarchy

Accessing the hierarchy is a minor point since this is already
possible (write a dispatch function that uses parents, ancestors,
etc.; for a hierarchy other than the global one, make the dispatch
function a closure that refers to the hierarchy). Maybe it could be
made more convenient.

Returning a sequence should be sufficient to let the dispatch
function handle any kind of preference. prefer-method could thus go
away. Instead, there would be a set of utility functions to
facilitate writing dispatch functions for common cases. A single
dispatch function could be used for any number of multimethods.

I think this should be sufficient to cover all cases you mentioned,
but of course it needs to be tried in practice.

Konrad.

[Mark Engelberg]

On Tue, Mar 31, 2009 at 9:45 AM, Konrad Hinsen
<konrad...@laposte.net> wrote:
> I think this should be sufficient to cover all cases you mentioned,
> but of course it needs to be tried in practice.

I think your idea of specifying a sequence of items to try in the
dispatching function, at the point of definition for the multimethod,
violates the principle of allowing library consumers to easily extend
this on their own without having to contact the library designer.

[mikel]

I think the orthogonal elements of multifunction dispatch are type
computations, traversals, and matchers (and the functions being
dispatched to, of course).

"Dispatch function" is maybe an unfortunate name; those functions
aren't dispatchers, they're type-returning functions--functions that
compute selector values.

If you have a way to compute selector values from inputs and a way to
specify the order in which matches against them will be tried, and a
way to specify how matching is to be performed, then you have the
tools to specify any dispatching algorithm you like. Clojure presently
provides some tools for this: "dispatch functions" are type-returning
functions; hierarchies are graphs of selector values; isa? and prefer-
method are a control language for describing traversal, and isa? is
also a matching function.

But these are restricted versions: dispatch functions are meant to
return a restricted range of values--symbols, keywords, classes, and
certain collections of those values; multifunction dispatch supports
hierarchies, but not other kinds of graphs; isa? and prefer-method are
the only vocabulary we have for describing traversal, and isa? is the
only matcher (almost the first thing I wanted to do when using
MultiFns was replace isa? with my own matching function).

The tools can be more expressive. Multifunction dispatch can be built
on user-specified traversals of user-designed graphs of selector
values, computed by user-supplied type-returning functions, and using
user-specified matchers. The traversal order, the range of selector
values, the language for describing traversal, and the matching
procedure can all be more first-class and more orthogonal. Special
cases can be provided for specific combinations known to be especially
useful or efficient.

With a full set of tools for describing dispatch, any differences of
individual taste in function dispatching and type relationships
becomes moot, because the tools are there to implement whatever type
relationships and dispatching algorithm you want. Rich doesn't want to
enshrine a particular traversal order in Clojure; I want the power to
comprehensively specify traversal order in advance for certain uses;
very well, any traversal order (or no traversal order) may be defined,
as you like. He wants function dispatching and data definitions to be
separated and so do I; very well, we have the freedom to compute
whatever values we wish for use as types, and to arrange them in
whatever sorts of graphs we like. Everyone wants things to be
efficient, and likely people also want common use cases to be provided
ready-to-wear; very well, those cases can be provided as built-ins or
elements of libraries, with special treatment in the compiler where
it's warranted for important cases, and without compromising the
expressiveness of the basic mechanisms.

[Rich Hickey]

What about predicate, or rule based dispatch - why hardwire the notion
of types, traversal or matching?

This is simply an exhausting amount of talk - how about a prototype?

I'm skeptical there will be much utility left in the harness that
hosted all of these plugin components. With no knowledge of how the
pieces fit, it couldn't even do the most basic cache management or
consistency checking jobs.

Rich

[Konrad Hinsen]

Maybe I wasn't clear about one point: the return sequence is not the
sequence of concrete implementations to try (the dispatch function
wouldn't even necessarily know them), but a sequence of starting
points in the hierarchy from which the standard lookup would start.

Konrad.

[mikel]

On Mar 31, 2:25 pm, Rich Hickey <richhic...@gmail.com> wrote:
> On Mar 31, 2:18 pm, mikel <mev...@mac.com> wrote:


> What about predicate, or rule based dispatch - why hardwire the notion
> of types, traversal or matching?

Those are different names for the same pieces.

> This is simply an exhausting amount of talk - how about a prototype?

I promised to stop talking about my gf implementation.

> I'm skeptical there will be much utility left in the harness that
> hosted all of these plugin components. With no knowledge of how the
> pieces fit, it couldn't even do the most basic cache management or
> consistency checking jobs.

Okay. It works for me. No one else has to use it.

[Konrad Hinsen]

One night's sleep later, I see that this is not sufficient. The
dispatch function is defined before the multimethod, and thus
potentially inside some library, which cannot know all the needs of
its potential clients. So yes, there has to be a way to specify
preferences later on.

One possibility would be to make the dispatch function itself a
multimethod, or have it call one, but I am not sure that's a good
solution.

Konrad.

[Rich Hickey]

On Mar 31, 12:45 pm, Konrad Hinsen <konrad.hin...@laposte.net> wrote:
> On Mar 31, 2009, at 16:32, Rich Hickey wrote:
>
> > Here are some problems/limitations of existing OO/GF systems that I
> > don't intend to repeat:
>
> ...
>
> I agree that these are not desirable features. I have had to work
> around some of them many times in the past. Traditional OO combines
> aspects that should better be handled separately.
>
> > Here are the areas I'm looking to improve:
>
> > - There's no easy way to talk about "the method you would get if you
> > were dispatch value X". Note that this is not the same as call-next-
> > method, which reintroduces global ordering requirements, but allows
> > for easy explicit reuse of already-defined methods.
>
> That would be VERY nice to have. More than once I ended up writing a
> private function that I then called from several methods in the same
> multimethod, to avoid code duplication.
>

I've added get-method (SVN 1338).

(derive ::Circle ::Shape)
(derive ::Rect ::Shape)

(defmulti area :Shape)

;note - you can name methods
(defmethod area ::Shape area-shape [x] nil)

(get-method area ::Rect)
#<user$area_shape__43 user$area_shape__43@674a93a6>

(defmethod area ::Rect area-rect [r]
(* (:wd r) (:ht r)))
(defmethod area ::Circle area-circ [c]
(* (. Math PI) (* (:radius c) (:radius c))))

(get-method area ::Rect)
#<user$area_rect__18 user$area_rect__18@4e42751f>

(get-method area ::Circ) ;not there
nil

(get-method area ::Circle)
#<user$area_circ__20 user$area_circ__20@74da0c91>

;if you don't think squares are rectangles, you can still reuse
implementation (silly example)
(defmethod area ::Square area-square [sqr]
((get-method area ::Rect) {:wd (:dim sqr) :ht (:dim sqr)}))

(area {:Shape ::Square :dim 20})
400

Note how you can name methods for diagnostic purposes. This doesn't
introduce names into the namespace, just puts a name on the fn object.

Rich

[Konrad Hinsen]

On Apr 1, 2009, at 14:47, Rich Hickey wrote:

> I've added get-method (SVN 1338).

Great, thanks!

> Note how you can name methods for diagnostic purposes. This doesn't
> introduce names into the namespace, just puts a name on the fn object.

It's also useful for recursive calls, if you are sure you want to
stay inside the method and not do a new dispatch.

Konrad.

[David Nolen]

Very cool.