On Sat, Jun 30, 2012 at 10:24 AM, Warren Lynn <wrn.lynn <at> gmail.com> wrote:

This is a continuation of issues raised in the thread about making the core "last" function behave in a polymorphic manner.

The separation of interfaces from implementation in Java serves several purposes, but one thing it does is it allows the creation of abstract data types, i.e., a type that is defined in terms of what it can do, rather than what it is comprised of or how it is implemented. 

Right now, in Clojure, ISeq is an interface, and by extension, it is an abstract type.  One benefit this has is that we can polymorphically dispatch, via a protocol, for example, on whether something is an ISeq.  We can easily create a function that applies to anything to which you can "first" and "rest", and at the same time, we can leave the function open to extension by other types.

However, once ISeq is made into a protocol (which has already been done in ClojureScript and may conceivably be done in the future in Clojure), there is a problem.  No longer can you dispatch via protocols on whether something is an ISeq.  In other words, by using a protocol to define ISeq. we have lost its capabilities to express an abstract data type.  Protocols provide a way to polymorphically dispatch to various concrete data types but appear to lose the ability to dispatch based on the abstract data type, i.e., dispatching on what the object can *do*.

A hypothetical polymorphic last function, proposed in that previous thread, is a great example of why one would want to do this.  A naive implementation of a polymorphic last could take the form "(cond (vector? s) ... (seq? s) ...)", but this is a closed implementation.  If we want to keep the implementation open for extension, you could use something like the protocol-based code I wrote there, but it absolutely relies on these abstract data types being represented as Java interfaces rather than other protocols.

David says that in 10,000 lines of code, there hasn't yet been something that required protocols to dispatch on other protocols, but in nearly the same breath he says that a polymorphic last function is impractical because of this limitation.  The difficulty, he notes, is that a hypothetical ILast protocol can't be made to automatically work for all implementers of ISeq.  Every single person who ever wanted to implement ISeq would also have to implement ILast.  I would argue that as soon as you're ruling out ideas such as a polymorphic last function specifically because it would make it too difficult to maintain in a protocol-based system, that is clear evidence that indeed, we *are* running into a real limitation of protocols.

So, I would like to better understand this limitation, and brainstorm with everyone about workarounds.

I have some thoughts and ideas about this, but I want to better understand the ClojureScript architecture first.  David, could you walk me through the implementation of nth, which is a very similar kind of function?  I was able to find the part of the code on Github where you define an IIndexed protocol which provides a protocol for nth.  However, I was unable to find the place in the code where you implement nth in linear time for all those who implement ISeq and faster for random-access collections.  Can you point me to the relevant source code?  Is nth open to extension to other abstract data types?  Is nth guaranteed to work and gain the default implementation for new data types that implement ISeq?  Do coders need to remember to implement IIndexed any time ISeq is implemented, and if so, how is that documented?

Thanks!

Look at the implementation of nth. Or how polymorphic unification works in ClojureScript core.logic for ISequential. I misspoke a bit, should have clearer that I simply meant that ILast (probably something else entirely) needs to be carefully considered since the logic needs too be moved to the actual fn or into a protocol default case in order to cover ISeq (which isn't a good idea anyway - IBoundedSeq or some such makes more sense to me).

On Saturday, June 30, 2012, Mark Engelberg wrote:

This is a continuation of issues raised in the thread about making the core "last" function behave in a polymorphic manner.

The separation of interfaces from implementation in Java serves several purposes, but one thing it does is it allows the creation of abstract data types, i.e., a type that is defined in terms of what it can do, rather than what it is comprised of or how it is implemented. 

Right now, in Clojure, ISeq is an interface, and by extension, it is an abstract type.  One benefit this has is that we can polymorphically dispatch, via a protocol, for example, on whether something is an ISeq.  We can easily create a function that applies to anything to which you can "first" and "rest", and at the same time, we can leave the function open to extension by other types.

However, once ISeq is made into a protocol (which has already been done in ClojureScript and may conceivably be done in the future in Clojure), there is a problem.  No longer can you dispatch via protocols on whether something is an ISeq.  In other words, by using a protocol to define ISeq. we have lost its capabilities to express an abstract data type.  Protocols provide a way to polymorphically dispatch to various concrete data types but appear to lose the ability to dispatch based on the abstract data type, i.e., dispatching on what the object can *do*.

A hypothetical polymorphic last function, proposed in that previous thread, is a great example of why one would want to do this.  A naive implementation of a polymorphic last could take the form "(cond (vector? s) ... (seq? s) ...)", but this is a closed implementation.  If we want to keep the implementation open for extension, you could use something like the protocol-based code I wrote there, but it absolutely relies on these abstract data types being represented as Java interfaces rather than other protocols.

David says that in 10,000 lines of code, there hasn't yet been something that required protocols to dispatch on other protocols, but in nearly the same breath he says that a polymorphic last function is impractical because of this limitation.  The difficulty, he notes, is that a hypothetical ILast protocol can't be made to automatically work for all implementers of ISeq.  Every single person who ever wanted to implement ISeq would also have to implement ILast.  I would argue that as soon as you're ruling out ideas such as a polymorphic last function specifically because it would make it too difficult to maintain in a protocol-based system, that is clear evidence that indeed, we *are* running into a real limitation of protocols.

So, I would like to better understand this limitation, and brainstorm with everyone about workarounds.

I have some thoughts and ideas about this, but I want to better understand the ClojureScript architecture first.  David, could you walk me through the implementation of nth, which is a very similar kind of function?  I was able to find the part of the code on Github where you define an IIndexed protocol which provides a protocol for nth.  However, I was unable to find the place in the code where you implement nth in linear time for all those who implement ISeq and faster for random-access collections.  Can you point me to the relevant source code?  Is nth open to extension to other abstract data types?  Is nth guaranteed to work and gain the default implementation for new data types that implement ISeq?  Do coders need to remember to implement IIndexed any time ISeq is implemented, and if so, how is that documented?

Thanks!

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure <at> googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+unsubscribe <at> googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

On Sat, Jun 30, 2012 at 9:36 PM, David Nolen <dnolen.lists <at> gmail.com> wrote:

Never mind, found it.

OK, I get it now.

Protocols are attached to very specific capabilities.

With this structure, it is easy to:

Write a function that operates on an input that fulfills a specific protocol.
Write a function that operates on an input that fulfills (all of) multiple protocols.
Write a function that operates on a closed (non-extensible by outsiders) union of abstract data types (i.e., it satisfies *either* this protocol or that protocol).
Write a function that has a default case, and can be extended by other concrete data types.
Write a function that supports a closed union of abstract data types, but can still be extended by other concrete types.

Pretty much the only thing you can't do with protocols is:

Write a function that supports an open union of abstract data types, for example:
"I want this function to be able to work with objects that support nth, or objects that support the protocol for queues, and I want to leave it open to other kinds of abstract protocols I might not be able to think of right now."

It's a limitation for sure.  It is easy to think of scenarios like last where you want to offer one implementation for the abstract concept of sequential types, one for the abstract concept of reversible types, one for the abstract concept of random access types, and possibly leave it open for extension.  But I can see why this kind of need for abstract extensibility might be rare, given the many other combinations that are well-supported by protocols.

Regarding the specific use-case of last, in theory, I think it could be done in almost exactly the same way that nth is implemented.  last would dispatch to a protocol containing -last to provide an extension point for concrete data types, and in a cond could test to see if various abstract protocols were satisfied, and if so use the corresponding last implementation.  There's no point of extension for other abstract protocols, but that's not a huge deal (and certainly no worse than the current implementation which only supports one abstract protocol!)  I don't feel strongly about last specifically, but if people wanted it to behave polymorphically, I'd be happy to volunteer to write the code.

In any case, I feel like I understand better how you've structured things in ClojureScript and what can and can't be done easily with protocols.  Thanks!