search

typelevel / algebra

Experimental project to lay out basic algebra type classes
https://typelevel.org/algebra/
Other
378 stars 69 forks source link

Having non/algebra depends on non/cats #142

Closed denisrosset closed 8 years ago

denisrosset commented 8 years ago

If non/cats removes the non/algebra dependency, how should the non/algebra be continued ? Should non/algebra depend on non/cats, or a subset thereof ?

The original vision of non/algebra was to be free of dependencies. Should we introduce a dependency of cats, and then on cats dependencies such as simulacrum, type-projector and so on ?

What binary compatibility guarantees would then be offered ?

rklaehn commented 8 years ago

I think/hope the idea would be to depend on just a small subset of the cats typeclasses. See https://github.com/non/cats/issues/777 . The main additional dependency is simulacrum and type-projector. I agree that this needs to be sorted out ASAP.

denisrosset commented 8 years ago

Thinking of it, I guess both these dependencies are fine.

simulacrum does provide syntax in the companion object, but you are free to ignore it. type-projector is a syntax plugin which does not affect non/algebra that much anyways.

Everything is provided at compile-time, and does not require runtime dependencies.

But this should be checked with the algebird people, and the vision of non/algebra should be updated.

denisrosset commented 8 years ago

Still, I would require a statement from all dependencies of non/algebra that they provide trivial binary compatibility, i.e. libraries depending on different versions of them can be mixed freely, and that the projects that depend on non/algebra do not need to include these dependencies as well (only indirectly).

This would then remove roadblocks on the adoption of non/algebra in other projects, like algebird or breeze.

non commented 8 years ago

So, I'm not totally sure. I think we will need to see what Cats ends up doing and then decide independently.

If there is a small kernel of Cats that contains the overlap, then it's easy to imagine depending on Cats. Otherwise, I'm less certain. We had been talking about an algebra-kernel (to ease Cats' dependency woes) so I could also imagine the reverse.

One interesting question is the appetite of Twitter to make Algebird depend on Algebra and/or Cats. If they would be fine depending on a small subset of Cats, then that makes a dependency easier. (And if they aren't going to create an Algebra dependency either way it also makes things easier.)

denisrosset commented 8 years ago

Great, thank you.

rklaehn commented 8 years ago

I guess the idea of algebra-kernel is no longer necessary. What about the other modularization of algebra (core/lattice/ring)? Is that still necessary? At least spire is going to use all of it anyway.

The version that is currently on maven is still monolithic, right?

johnynek commented 8 years ago

Is there a link to the discussion to remove the algebra dependency? My reaction is that this is a bad idea or at least bad for the concept of the algebra project being a shared set of traits.

Algebird depending on cats is probably not going to happen (as algebird is depended on by a large number of things at Twitter and we'd be asking to increase all their dependencies by one more).

johnynek commented 8 years ago

Sorry, I see the link above.

It does not seem to have a motivation included. What is the motivation here?

It seems to me that cats might just want to depend on algebra-core (as that split has already happened).

denisrosset commented 8 years ago

@johnynek I would prefer personally that cats keep its dependency on algebra --- but I'm not active with cats at all. I opened this issue so that the position of non/algebra can be decided.

rklaehn commented 8 years ago

Here is the PR from @milessabin https://github.com/non/cats/pull/762 . @non gave his OK. I really don't care about who depends on what, as long as we have no duplication of typeclasses between cats and algebra. In any case, this needs to be sorted out if scala wants to be a viable platform for typeclass-based FP.

johnynek commented 8 years ago

I'm super bummed it by this: https://github.com/non/cats/pull/762 because how can we really expect this to be a useful common when not even cats wants to take a dependency.

I think it is very likely to harm adoption of the project. For instance, probably algebird should just copy what we want there since the mission of a common dependency looks to be failing and for people in large code bases, any dependency is already a cost and risk of future breakage (via diamonds, etc...)

milessabin commented 8 years ago

It's not that Cats won't take a dependency, it's that it's the wrong dependency ... Cats is the general purpose library, Algebra, at least in it's current form, is more than somewhat specialized. We'll do our best to ensure that there is a minimal stable Cats kernel module that you'll be able to depend on.

denisrosset commented 8 years ago

@milessabin : I disagree. Cats has many dependencies (simulacrum, kind-projector, machinist), while algebra has none.

milessabin commented 8 years ago

Exactly my point: Cats isn't resistant to appropriate dependencies. Algebra's resistance to dependencies on simulacrum, kind-projector and machinist is a problem because it means that the style of code for eg. Monoid in Algebra, and MonoidK in Cats, is very very different.

denisrosset commented 8 years ago

... as it should for a common library of typeclasses. Algebra has minimal "code style" to perform its mission, i.e. traits with methods corresponding to operations provided by the typeclasses.

Anything more is a reason for external libraries to "do their own thing", as @johnynek is hinting.

(Actually, that's not exactly true. There is a machinery in the companion objects of non/algebra to summon instances and methods. My opinion is that they should be removed.)

milessabin commented 8 years ago

Yes, I agree that Algebra is suited to factoring out commonality between Algebird and Spire. That doesn't mean that it's suited to being part of a more general purpose library like Cats.

Please read my rationale on the PR and the comments in the followup.

johnynek commented 8 years ago

If what you want is something even smaller than the current algebra-core, why not propose that we make that and share that? I didn't know about this until this morning or I would have proposed the same.

I agree that MonoidK and SemigroupK should be in cats.

I don't see why manually writing code that is generated by simulacrum is reason enough to not depend on a core library for I guess 6 traits (Eq, Order, PartialOrder, Semigroup, Monoid, Group).

Lastly I doubt the notion that it makes it hard for newbies that we are not using simulacrum or machinist (both of which are not obvious to me and I'm not such a newbie). If you are new to category theory, the above six traits should be mastered before you try to grok, for instance, how one might use Alternative in a parser combinator library. Put another way, there are only a few properties in algebra (associativity, commutivity, inverses, identities, idempotency, and a few more in the -ring, -lattice packages). Nothing is higher kinded (except MonoidK which I think does not belong here/is not here?). So, I really doubt that this new person is going to stumble over going to a separate library to see Semigroup but then go on to immediately see how they can apply Applicative in their work.

Speaking from experience, at Twitter, Semigroup and Monoid got a ton of adoption, Monad almost none. It was just far more common to define a new data type that had some well defined Monoid but almost never did people create new type M[_] that had Monad[M]. I mention this only to emphasize my doubt that algebra will be a barrier to using Cats.

On Monday, January 4, 2016, Miles Sabin notifications@github.com wrote:

Yes, I agree that Algebra is suited to factoring out commonality between Algebird and Spire. That doesn't mean that it's suited to being part of a more general purpose library like Cats.

Please read my rationale on the PR and the comments in the followup.

— Reply to this email directly or view it on GitHub https://github.com/non/algebra/issues/142#issuecomment-168715229.

P. Oscar Boykin, Ph.D. | http://twitter.com/posco | http://pobox.com/~boykin

milessabin commented 8 years ago

I suppose that I am proposing that with the rider that it should be cats-kernel. The key point here is what I said on the Cats issue,

We are promoting Cats as the entry point into the Typelevel world, and have gone to considerable lengths to make the type classes that we provide consistent, accessible and well documented. Unfortunately several of the type classes we can expect newcomers to turn to first (Eq, Order, Monoid) are not part of Cats, they're part of Algebra. So having been introduced to Cats people are almost immediately bounced over to Algebra where they will find code written in a noticeably different style and surrounded by specialized artefacts like lattices and Heyting algebras which are most likely quite distant from their immediate interests. I don't think that this provides a good initial experience for people new to Cats.

Nb. I fully appreciate the reasons for the stylistic differences, nor do I mean to imply that Algebra isn't consistent and well documented. This isn't a criticism of Algebra, merely an observation that it's goals pull it in a somewhat different direction.

If Eq, Order, Monoid etc. were to stay in Algebra, then we'd simply be wrong to promote Cats as the entry point to the Typelevel universe, we should be pointing them at Algebra instead. But I don't think that's feasible ... we've invested a lot of time and effort into creating introductory resources around Cats and I think it would confusing in the extreme to switch horses now.

I think that the general shape of Algebra as it is now works pretty well for sharing between Algebird and Spire and I think you should be free to expand on that independently of what happens in Cats.

denisrosset commented 8 years ago

@milessabin: "switching horses" means removing Algebra support in Cats, not the other way around.

Quoting Cats' README:

Cats will be designed to use modern best practices:

-    simulacrum for minimizing type class boilerplate
-    machinist for optimizing implicit operators
-    scalacheck for property-based testing
-    discipline for encoding and testing laws
-    kind-projector for type lambda syntax
-    algebra for shared algebraic structures
denisrosset commented 8 years ago

BTW, it's very easy to hide the dependency on Algebra in Cats for newcomers by using type aliases. There is the slight complexity of having simulacrum generate boilerplate for the aliases, but nothing insurmountable.

If cats wants to do things on its own to have more freedom, good. But to have interoperability, you need to play with others.

rklaehn commented 8 years ago

The vision of having common basic typeclasses used by many major libraries (spire, algebird, cats) is what originally attracted me to spire in the first place.

How exactly can you expect an ecosystem of typeclass-based libraries to develop, when you have to decide which Eq or Monoid instance you want to support, and whatever you decide, you make life hard for most of your potential users?

So either this can be done in a way that is acceptable for algebra/algebird/spire, or it should not happen at all.

milessabin commented 8 years ago

I'm hopeful that a minimal cats-kernel will work for Algebra.

denisrosset commented 8 years ago

@milessabin The original vision for the cats project, as I read on its main Github page, was to use the best practices, including common typeclasses in Algebra.

Now, you are asking Algebra to abandon one of its goals (having no dependency) by introducing not only the cats-kernel dependency, but also simulacrum and machinist. In the process, risking Twitter's support, as I guess they also made compromises to merge Algebird's typeclasses with Spire's.

Is this change only a question of newcomer approachability and code style, or a more profound divergence between Cats and Algebra?

johnynek commented 8 years ago

@milessabin what would it take for us to maintain the vision of a shared core of concepts? Is it a deal breaker that it not be in cats? Is the deal breaker using the machinist/simulacrum plugins?

It seems to me what we are talking about is algebra-core without the commutative options and the lattice/band stuff (which still seems useful to me, but anyway).

Is that right?

On Monday, January 4, 2016, Denis Rosset notifications@github.com wrote:

@milessabin https://github.com/milessabin The original vision for the cats project, as I read on its main Github page, was to use the best practices, including common typeclasses in Algebra.

Now, you are asking Algebra to abandon one of its goals (having no dependency) by introducing not only the cats-kernel dependency, but also simulacrum and machinist. In the process, risking Twitter's support, as I guess they also made compromises to merge Algebird's typeclasses with Spire's.

Is the change only a question of newcomer approachability and code style, or a more profound divergence between Cats and Algebra?

— Reply to this email directly or view it on GitHub https://github.com/non/algebra/issues/142#issuecomment-168744617.

P. Oscar Boykin, Ph.D. | http://twitter.com/posco | http://pobox.com/~boykin

milessabin commented 8 years ago

Not being in the Cats repo isn't a dealbreaker for me, although that would be my preference. On the other hand, I think it being in the same repo as the rest of Algebra would be a problem. Is there any mileage in an independent repo which could be included as a git submodule of either or both?

I would argue very strongly in favour of Typeclassic (a proposed merger of simulacrum, machinist, imp and export-hook) being used consistently throughout Cats and a Cats/Algebra kernel.

In terms of content, I think that the components that I pulled out of Algebra in that PR are about right. I quite agree that the parts I left out are useful, but I think they belong in a more specialized library (ie. in Algebra, but not the kernel).

The most important thing for me is that I must be able to point people who are new to Typelevel-style projects at Cats as their entry point and expect them to be able to have a consistent learning and participation experience. In particular I think that means that they should be able to find the primary documentation for core type classes at https://non.github.io/cats/, that documentation should be verified using Tut, that there is a common forum for discussion (ie. the Cats gitter), that code should be written in substantially the same style, that law checking should be done in the same way, and that the path for them to raise issues and make contributions should be the same.

johnynek commented 8 years ago

@milessabin Which of the items you mention are deal not being done currently? For instance, gitter is there, law checking is done with discipline, issues and contributions are done the same way, I believe.

rklaehn commented 8 years ago

Let's see if we can find at least some common ground here.

@johnynek I think it would be good to figure out

1) the reasons why cats wants to "own" the basic typeclasses and 2) what would be acceptable from the algebra/algebird side

You already asked @milessabin about 1). So about 2). Is your concern with a) the dependency of algebra on cats-kernel or whatever it will be called b) the typeclass encoding chosen by cats c) the additional syntax that is provided via machinist d) the additional dependencies to simulacrum and machinist

Would a library that encodes typeclasses manually with a similar scheme to what is used by simulacrum, but has no dependency on simulacrum, be acceptable? Maybe a library that has neither cats nor algebra in its name would be best.

@milessabin I agree very much with the vision of typeclassic. But you are asking @johnynek and all the people that are using algebra, algebird, spire, spark etc. in production to depend on a library (typeclassic) that _does not even exist yet_. Maybe the best way forward would be to produce a library (typelevel-kernel or whatever) with a single dependency on typeclassic, that is beautifully documented using tut and provides strong binary guarantees using mima, and only then move over cats and algebra to the new kernel, preferably at the same time?

milessabin commented 8 years ago

I very much hope we can find common ground.

To be completely clear, my motivation here is that I believe that it is of critical importance that we be able to point people who are new to Typelevel-style projects at Cats as their entry point to that world and be confident that they will have a consistent and good learning and participation experience.

There's a huge and growing population of Scala developers who have barely come into contact with FP or, worse, have come into contact with it and been scared off by a combination of unapproachability and bad behaviour. Cats exists in very large part precisely to counter that. This is in no way a criticism of Algebra, but its goals are somewhat orthogonal.

So please try and read my comments in that light ...

@johnynek wrt the issues I raised in earlier, I think you agree that a unified documentation site for Cats and use of Tut is something that a Cats/Algebra kernel would need to support?

You pushed back on three of the issues I raised,

milessabin commented 8 years ago

@rklaehn yes, Typeclassic doesn't exist yet. simulacrum, machinist, imp and export-hook do and are used in Cats. This contributes to quite a significant difference in code style between Cats and Algebra. I would want to see the basic type classes in a Cats/Algebra kernel use these tools now and be prepared to upgrade to Typeclassic as and when.

johnynek commented 8 years ago

Thanks @rklaehn for bringing some additional focus to the discussion.

@milessabin I'm a little confused still the mission and purpose of Cats. I could interpret you as meaning that is not ready to start depending on and expect stability and instead it is more important to serve as a teaching and community building tool as well as a model for best practices. Is that right? If that is the first goal, and if the main committers prefer that goal, it is hard to advocate for industrial use. For instance, Twitter has several millions of lines of scala code. Would you advocate for them to adopt a particular version of cats knowing that that since it is a low level library it will be involved in many diamond dependencies and commitment to binary compatibility may not be a high goal?

In my view algebra is not orthogonal to Cats, but perhaps in conflict with your view. While it is nice to have one repo to look at to see Eq and Functor and Monad, I don't think this approach is actually scalable, and does a disservice ultimately. It means that we either deal with multiple instances of Eq (currently scala.math.Equiv, spire's Eq, algebra Eq, scalaz Eq and a proposed cats Eq), or we privilege the Cats repo above others in that it should be 100% self contained while other libraries (such as spire, algebra would be expected to point their users at Cats).

My goal has always been a standard and reusable version of these common typeclasses that people can use in scalding, summingbird, spark and more. If they have to deal with the pain of planning to deal with several different Eqs, Orders, etc... even within the typelevel project, this seems like a bad experience to me.

So, I want to emphasize this goal: a shared set of typeclasses.

Now, I'm personally somewhat flexible about some details. The gitter channel, duplicating docs, etc... Are not a big deal. Also, I don't expect that Eq, Order, PartialOrder, Semigroup, Monoid and Group will change much at all. I'm also somewhat flexible on some of the details of the typeclass encoding.

However, I'm more rigid when it comes to binary compatibility. Many industrial users operate mono-repos. In those mono-repos, diamond dependencies can cause a lot of pain. Frequent binary breaks result in those users getting stuck on old versions (and thus not contributing to the most recent version). This fractures the community and costs us available effort. I want to minimize that. I'm concerned that using some of these plugins in the algebra core/minimal/whatever we call it, is somewhat gratuitous, but brings with it binary risks. If these plugins only run at compile time and introduce no runtime dependency (do not show up in the .pom, etc...) I'm fine with them, however. I just don't know enough about how that works.

rklaehn commented 8 years ago

I can only speak for myself, but I think that algebra would be more inclined to go ahead with this if a small kernel with serious guarantees WRT binary compatibility (documented and enforced by mima) would already exist. For me personally, it would not be a problem if this kernel would be in cats, if that's what everybody agrees on. Even though I find the current arrangement (cats depends on algebra, most stuff that is of no interest for cats is in algebra-lattice and algebra-ring) pretty logical.

Is the idea of typeclassic just to merge the code of the existing libraries, or do you expect namespace changes? I guess most of these dependencies are only relevant at compile time, but nevertheless I find it hard to believe that e.g. merging simulacrum, machinist, imp and export-hook to typeclassic can be done without breaking binary compatibility.

johnynek commented 8 years ago

I am also fine with a kernel to be housed in cats if that makes eliminating duplication possible.

Big +1 to mima with a goal of minimizing breaks (and a willingness to put off cosmetic changes in the interest of binary stability, e.g. a goal to keep binary breaks to less than N per year, where N is perhaps 2 or 3).

milessabin commented 8 years ago

I think that if the kernel is limited to just what was in my PR then we should be able to provide the binary compatibility guarantees that you want.

milessabin commented 8 years ago

@johnynek when you say "I am also fine with a kernel to be housed in cats" ... do you mean in the Cats repo? I'm completely fine with your binary compatibility goals.

I think it looks suspiciously like we're close to agreement here?

johnynek commented 8 years ago

Yes, I'm fine with the cat's repo with the binary/runtime dependency goals met.

rklaehn commented 8 years ago

Great :clap: @milessabin So I guess the next step is the creation of a cats-kernel in cats?

milessabin commented 8 years ago

Yup .... I'll rework my PR as a PoC for that :-)

erik-stripe commented 8 years ago

:+1: I think a kernel is the way to go here. Thanks everyone!

milessabin commented 8 years ago

Yup ... to repeat what I said on the Cats issue: thanks everyone for engaging so constructively on an an important issue which could have been quite divisive :-)

denisrosset commented 8 years ago

Thanks @milessabin

johnynek commented 8 years ago

:+1: Thank you @milessabin

milessabin commented 8 years ago

New PR here: https://github.com/non/cats/pull/786.

johnynek commented 8 years ago

This is closed by #152 Thanks for the discussion, all.