Racket generics and generic collections

[Alexis King]

I’ve recently made an attempt to implement a generic collection library for Racket using racket/generic. My implementation is a work in progress, but you can find it here:

https://github.com/lexi-lambda/racket-alexis-collections

Documentation is also available if you’re interested in taking a peek at how it works.

I’ve been discussing how to best handle this sort of project with Vincent on IRC. He has his own version of generic collections as well, located here, which takes a decidedly different approach. I think we’re both interested in having a discussion about how to best approach this problem, since having generic collections in the core would be a nice improvement, but that’s a long-term goal.

In a more immediate sense, I’ve run into a few issues with the current generics implementation that I think need to be solved in order to create an expressive enough system to adequately handle the different data structures Racket contains. I’ve written up some of the things that have come to my immediate attention on the wiki page on GitHub. I would appreciate any comments or feedback.

In addition to those problems, there are more collections-specific issues that would be helpful to untangle, such as how to handle operations such as map and append on heterogenous arguments, as well as the general structure of the interfaces. I will continue to attempt to create what my ideal implementation would look like, but, as Vincent has said, I think now is a good time to try out different approaches and weighing the pros and cons.

Sam has also suggested taking cues from Clojure, Scala, and Haskell with regards to their collections APIs, which probably provide good examples of the pros and cons of existing approaches. I haven’t done any extensive work in any of those languages, so if anyone is familiar with their strengths and weaknesses, it would be helpful to hear what you like and don’t like about them.

Alexis

[Matthias Felleisen]

I think the key is to develop clients for both yours and Vincent's design. See what trade-offs you encounter. Write down the pros and cons.

The designs of Clojure, Haskell, and Scala reflect their choices among these properties (presumably) plus the general programming philosophy (including its expressive power) of the language. You might want to compare to those.

-- Matthias

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/AE4CCA7C-6F88-499D-B415-90FA7A184338%40gmail.com.
> For more options, visit https://groups.google.com/d/optout.

[Alexis King]

I’ve turned my attention to this once again, and I think I need to illustrate the current roadblock I’ve hit to seek some advice.

Currently, there is no way to specify that implementing one generic interface automatically provides an implementation of another generic interface. This is actually a pretty big flaw. One of the most common uses of Haskell typeclasses is providing wrappers, such as Compose, which provide implementations of Applicative “for free”.

I think this is best explained via example, so I’ve put together some sample code here: https://gist.github.com/lexi-lambda/535b7985d4570d1e0222

That snippet includes two files, a.rkt and b.rkt. The first is how the generic system currently operates, while the second example will fail to compile. The first example illustrates a problem, and the second example is my current idea for a solution.

The basic idea is this: a generic interface, in this case gen:sequence, provides some basic operations, in this case cons, first, rest, and empty?. A separate generic interface is gen:iterable. Obviously, plenty of things that aren’t simple sequences can be iterable—for example, hash tables and sets—so it makes sense to have a separate interface.

The problem is that, while gen:iterable can be trivially implemented in terms of the methods of gen:sequence, there is no way to specify that all implementors of gen:sequence should also have implementations for gen:iterable defined in terms of gen:sequence’s methods. The current “solution” to this is to add a clause to gen:iterable’s #:defaults clause, as I’ve demonstrated in the first example. This does, indeed, make all implementations of gen:sequence also iterable. Unfortunately, this solution is inadequate for two reasons:

1. This creates a circular dependency between gen:iterable and gen:sequence. It becomes impossible to put these interfaces in separate modules. This means that all “subinterfaces” of gen:iterable must be defined in the same module as the iterable interface itself, which is, frankly, unacceptable.
   
   
2. Furthermore, and perhaps even more of a deal-breaker, this completely prevents user-defined interfaces from providing “automatic” implementations of gen:iterable. All of these must be manually encoded into the #:defaults clause, and if a user does not have the ability to modify the interface’s declaration, there is no solution.

The most elegant solution would be to add a way to make interfaces “inherit” other interfaces. I’ve provided a sample of what that might look like in the second example, b.rkt. By pulling the relationship out of gen:iterable’s #:defaults clause and moving into gen:sequence’s #:implements clause (analogous to #:methods on struct definitions), this alleviates both of the above problems.

I have become increasingly convinced that some kind of solution to these problems is fundamentally necessary to having an expressive enough generics system to adequately implement things like generic collections elegantly. Even if my proposed solution is not the right approach, I think something of the sort needs to be implemented before the issue of generic collections can be tackled.

This raises the question of how to actually implement such a thing. I’m not terribly familiar with how the generics system actually works—I know it’s really just implemented in terms of struct properties, but I’m unfamiliar with the precise details of that machinery—and though I’ve read through portions of racket/private/generic and racket/private/define-struct, no clear and obvious path to implementation is apparent to me. Perhaps someone with better experience in that area would be able to point me in the right direction.

The two main approaches that come to mind are implementing this as a derived concept via some sort of desugaring, or by encoding this into generic info itself. In the former case, using #:methods with a generic interface that included “super-interfaces” would simply expand to a separate #:methods clause linking the method definitions together. The latter would build it into the system in a more fundamental way.

As a final note, this does introduce the classic problem of multiple inheritance. If my understanding is correct, this problem could also possibly occur using Haskell’s typeclasses, so I do plan to investigate what the resulting behavior is in that case. That said, my guess is that true conflicts would be rare in practice (as is usually the case with systems that permit multiple inheritance), and providing the implementations as “defaults” rather than definitive method implementations would allow manual disambiguation. In fact, Java 8 supports precisely this sort of thing with its ability to define default interface method definitions, which should be pretty much directly analogous to this feature in generic interfaces.

Anyway, I apologize for the wall of text. I am highly interested in coming up with a solution to this problem, as I would like to continue work on my generic collections library, but I’m not sure how to proceed. I hope I’ve made myself clear without being too unnecessarily verbose. Feedback is, of course, appreciated, and any help even more so.

Thanks,

Alexis

[Alexis King]

I’ve been thinking about this more, and I think I’ve come up with a reasonable syntax for this. There are still a few annoying cases that I haven’t worked out yet with regards to the intended semantics, but I think this would be a good interface for the majority of use-cases.

I’ve thrown together a simple example of what I’d like this to look like here:

https://gist.github.com/lexi-lambda/6883bb6d72a3d6ca9988

The basic idea is that interfaces can inherit other interfaces. The semantics of this are as follows:

• An interface that inherits another interface automatically gains all of the inherited interface’s methods. Therefore, implementations of the sub-interface can provide super-interface method definitions in the sub-interface’s #:methods clause.
  
  
• The inheriting interfaces may provide default implementations of super-interface methods. Just like fallbacks, these can be overridden by specific implementations, but they’re used if those aren’t provided.
  
  
• Combining the two above points, sub-interfaces may also provide more specific method implementations that override super-interface fallbacks, even if those methods are part of an inherited interface.

I can only think of one annoying possibility when dealing with this sort of inheritance, and that’s the classic diamond problem. This is effectively multiple inheritance. As with other instances of multiple inheritance, I think the reasonable approach would be to require implementors which have two possible inherited implementations to provide an explicit implementation that overrides both of them.

Of course, this also means that it needs to be possible to refer to specific implementations of a given interface if needed, but this would be fairly straightforward by creating additional bindings that refer specifically to individual implementations. (To make this reasonable for the user due to the possible number of generated bindings, a generics-out provide transformer would be in order.)

This solution accommodates a number of problems I’ve run into when attempting to create a solid generic collections library.

• This eliminates the unresolvable circular dependency between generic interfaces when fallbacks must be used to simulate sub-interfaces but the two interfaces are declared in separate modules.
  
  
• It allows user-defined sub-interfaces to extend existing interfaces without having direct access to the original interface declaration (which is required for the fallback-based method).
  
  
• It prevents the redundant prefixed naming hell I ran into when implementing sub-interfaces. If you look at my current implementation of generic collections, you’ll see that the interface contains a lot of prefixed names (cons-ref, cons-append, cons-map, etc.). Since generics inheritance allows sub-interface implementations to reuse the super-interfaces’ method names, this prefixing is unnecessary.

I’m not sure if anyone on this mailing list would have any feedback, but I figured I’d type this up just in case, as well as to document my current model. The hard part, obviously, would be figuring out how to implement this on top of the existing generics model. After some consideration, I think building this into the generics system rather than trying to implement it via some form of complex de-sugaring would be necessary from both an practicality and feasibility point of view.

Any thoughts would be welcome; otherwise I may try and begin deciphering the racket/generic code to figure out how it ticks so I can figure out how to actually implement this. I think it would be a valuable addition that would make the generics system considerably more powerful.

Thanks,

Alexis

[Benjamin Greenman]

This is very exciting.

But I have a problem right now and want to ask the list: is anyone currently working on getting the existing racket/generic library to work in #lang typed/racket? If not, does anyone familiar with the implementation know or forsee any major difficulty adding bindings / contracts? (The wiki page only says "may require research".

(On the same issue, how about racket/generator and racket/stream?)

--

You received this message because you are subscribed to the Google Groups "Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/41ABB258-0446-433F-8020-A0BB0C49CD76%40gmail.com.

[Alexander D. Knauth]

On May 1, 2015, at 1:08 PM, Benjamin Greenman <bl...@cornell.edu> wrote:

> (On the same issue, how about racket/generator and racket/stream?)

For racket/stream, there’s this, and while it works in the current snapshot, it doesn’t work in 6.1.1 or earlier versions:
https://github.com/AlexKnauth/typed-racket-stream

[Alexis King]

With regards to generics, I don’t think anyone is actively working on them. I was interested in potentially attempting them a while back, but I realized it was probably far too big of a project for me to try and research right now. I think the primary problem of consideration was ensuring sound interop with untyped code, but another point of consideration is the fact that generics aren’t really used all that much in Racket right now, so it’s hard to say precisely what sort of patterns a typed version would need to cover (especially so if the generics system ends up getting extended).

I don’t believe any work has been done on generators, but I can say that I actually have attempted an implementation of streams. They mostly work, but the current problem is the fact that the implementation of stream-cons is a macro, since it needs to be lazy, and its expansion is currently too much for the inference to handle.

It might be possible to either improve the inference to typecheck the expansion or reimplement the expansion of stream-cons to be friendlier to the typechecker, but I haven’t pursued either of those routes as of yet.