typelevel/algebra

Integrating cats.kernel.Semigroup and friends

Opened this issue · 30 comments

LukaJCB commented

Right now, there's AdditiveSemigroup and MultiplicativeSemigroup which are then combined into Semiring. This is all well and good, but unfortunately there's a huge amount of code out there written on the basis of cats.kernel.Semigroup and it's a bit of a shame we can't reuse those.
Especially in Spire where the various numeric types don't have Monoid instances and therefore can't be foldMaped.

Since in the Cats ecosystem numeric types usually come with an Additive Monoid as default, I would personally love to see that convention being expanded in this project, but I also understand there are some good reasons not to do that.
Here is some code I came up with that demonstrates how I'd personally like to have it:

trait Semiring[A] extends CommutativeMonoid[A] {
  def times[A](x: A, y: A): A

  def plus[A](x: A, y: A): A = combine(x, y)
  def zero[A] = empty[A]
}

trait Rig[A] extends Semiring[A] {
  def one[A]: A
}
johnynek commented

I think we can look at merging algebra into cats now that cats has reached 1.0

algebra has been stable for quite some time, and the main mission was a common set of classes between algebird and spire.

I think a cats-algebra module would make a lot of sense and core could eventually depend on it.

LukaJCB commented

I would very much like to see that as well: typelevel/cats#2041

denisrosset commented

Regarding the default monoid/group: the meaning really depends.

Say you have a Map[Monomial, Scalar] that represents a polynomial. You want the additive group there.

However, if you use permutation matrices to represent permutation group elements, you want the multiplicative group notation.

(And you'll want to avoid AnyVal wrappers in numerical/symbolical code to avoid wrapping with Array)
I like the distinction that is currently made. However, we could provide optional implicit conversions.

Regarding cats-algebra, I'm all for it. The only distinction between spire and algebra is spire.algebra.Field, which includes gcd/lcm/euclidean ring structure.

LukaJCB commented

Regarding the default monoid/group: the meaning really depends.
Say you have a Map[Monomial, Scalar] that represents a polynomial. You want the additive group there.
However, if you use permutation matrices to represent permutation group elements, you want the multiplicative group notation.

I completely agree with this notion. I'd just like to see consistency in the ecosystem.
Furthermore I'm not a huge fan of the duplication of having e.g. Semigroup, AdditiveSemigroup and MultiplicativeSemigroup.
Algebird also has its own Ring which extends cats.kernel.CommutativeGroup and can therefore be used with most of Cats' existing functionality which makes quite a bit nicer to use IMO.

(And you'll want to avoid AnyVal wrappers in numerical/symbolical code to avoid wrapping with Array)
I like the distinction that is currently made. However, we could provide optional implicit conversions.

Instead of using AnyVal wrappers, we could use something like scala-newtype which we're also going to be [using soon in cats]. (typelevel/cats#1800) and even if the extra dependency is something we don't want we could manually encode them as has already been done successfully multiple times in Cats and cats-effect.

Regarding cats-algebra, I'm all for it. The only distinction between spire and algebra is spire.algebra.Field, which includes gcd/lcm/euclidean ring structure.

Should we just add those ring structures (along with DivisionRing) to algebra? Sounds like a good idea to me :)

johnynek commented

I couldn’t see almost any code that we wanted that is generic on the Field stuff and Field also has the ugly aspect that inverse/div is not total (it can throw).

I think the marginal win of the Field/DivisionRing stuff isn’t worth including (also I don’t know of any interesting instances other than numbers).

LukaJCB commented

I couldn’t see almost any code that we wanted that is generic on the Field stuff and Field also has the ugly aspect that inverse/div is not total (it can throw).

This makes me uncomfortable as well. If scala had predicate/refinement types we could define it as

trait DivisionRing[A] {
  def div(x: A)(y: {A => y != zero}): A
}

but alas we do not, maybe in Scala 4. 😄

@johnynek what do you suggest we do about Field then, just stop the hierarchy at CommutativeRing and leave the rest to Spire?

johnynek commented

Yes. That’s precisely what I support. Spire is great and not going anywhere. If you are doing interesting numerical work, you should use it. It is fine if they keep the Field related classes.

denisrosset commented

Would be great to stop the hierarchy in algebra at CommutativeRing, so that we avoid the duplicate Field classes. And the rest of the ring tower is not exactly set in stone (we put UniqueFactorizationDomain outside the tower to let people pick their integer factoring algorithm, for example).

But I'm very adamant against merging Group and AdditiveGroup. Sure, add an implicit conversion, but typeclasses are about laws and syntax, and I've always admired that cats/algebra/spire has distinct method names and operators for e.g. permutation groups vs. addition and multiplication of integers.

denisrosset commented

Note: the precision of the commutative ring tower starts to be important when dealing with polynomials in a generic way. But the polynomial code in Spire is still a bit shaky.

LukaJCB commented

But I'm very adamant against merging Group and AdditiveGroup. Sure, add an implicit conversion, but typeclasses are about laws and syntax, and I've always admired that cats/algebra/spire has distinct method names and operators for e.g. permutation groups vs. addition and multiplication of integers.

How about going the PureScript route then? Remove AdditiveGroup and MultiplicativeGroup and their friends and start the ring hierarchy at Semiring. Then add newtypes to get either mutliplicative or additive Monoid. I think having to duplicate the 6 Semigroup -> CommutativeGroup typeclasses a full 3 times all with the exact same laws is really suboptimal and I think we can do better :)

Edit: For reference the PureScript prelude Semiring: https://pursuit.purescript.org/packages/purescript-prelude/4.1.0/docs/Data.Semiring

johnynek commented

I’m -1 on additive group but I didn’t insist since @non liked it so much.

I don’t like having a different type just to get syntax (which I’m not an enourmous fan of).

Algebird has always done what @LukaJCB suggests and uses types (case classes sadly) to dispatch. This means we get weird stuff like Max(1) + Max(3) == Max(3) but having one trait is a big win.

When writing generic code, I don’t care if I have an additive or multiplicative group. So at those points either and implicit or manual conversion is done. Since I’m most interested in generic programming and not syntax hacks, this seems like a bad trade.

  • 👍1
LukaJCB commented

Another argument is that the |+| syntax on cats.kernel.Semigroup (as well as the |-| syntax on cats.kernel.Group) already sort of implies that combine usually refers to addition.

We're probably going to integrate scala.newtype (which will compile down to opaque types in 2.13) into cats-core for the various newtypes defined there as well, so that problem would be solved as well.

When writing generic code, I don’t care if I have an additive or multiplicative group. So at those points either and implicit or manual conversion is done. Since I’m most interested in generic programming and not syntax hacks, this seems like a bad trade.

I agree with this and a function

def foo[A: AdditiveMonoid](...) = ...

is completely the same as

def foo[A: Monoid](...) = ...

or

def foo[A: MultiplicativeMonoid](...) = ...

The laws are the same and they are fundamentally equivalent. IMO, generic code shouldn't care about multiplicative or additive at that level of abstraction.

The fact that we could remove 12 type classes from Algebra without losing any functionality is a pretty strong argument to me personally :)

  • 👍1
denisrosset commented

I see the force is strong on this one. Before I present my case, let's acknowledge that there is no optimal solution there, just sets of different trade-offs.

The ambition of Spire is to go beyond arithmetic, and support generic algebraic structures: for example polynomials have more or less structure depending on what the underlying scalar supports. So precision is definitely a requirement.

On the other hand, PureScript made the choice of having a compact prelude, acknowledging platform limitations: for example, none of the Rig, Rng, semiring business, and the EuclideanRing function is limited to 32-bits integers.

I'll now give use cases of the structures that are proposed for elimination. My own experience concerns the use of Scala in quantum information, where the concepts below are central (complex arithmetic in particular).

  1. MultiplicativeMonoid instances are used when multiplying monomials in polynomial arithmetic. There are linear algebra operations that do not require more than that, for example the Kronecker product (or tensor product) of matrices, the outer product of vectors. The notation here is explicitly multiplicative. In particular, this genericity comes handy when performing global optimization over polynomials (see Lasserre hierarchy).

  2. On the same topic, complex conjugation is a involution on a multiplicative monoid, and there is a rich structure of *-rings, *-algebras, etc..., which concretely describe complex matrix multiplications. However, you want to define that involution on the multiplicative monoid of a ring, not the additive one. This becomes relevant when defining (complex) inner product spaces in linear algebra.

  3. Additive groups have a particular relationship with total orders. In particular, the % operation on the JVM has laws based on an additive monoid compatible with a total order ("how many integer times does the right operand fit in the left?"). To express this % operation, which is distinct from Euclidean division Spire defined a TruncatedDivision typeclass. However, it makes sense relative to additive groups, and not others. I'm skipping over laws related to signs and the absolute value.

  4. Most of the notation used for monoids/groups in mathematics is multiplicative, not additive. For example, multiplying permutations is commonly understood as semigroup composition (by analogy with the multiplication of permutation matrices), whereas permutation addition is seldom seen (but sometimes corresponds to the direct sum operation).

johnynek commented

@denisrosset can you speak to why the newtype approach does not solve the problems?

Is it just that you don't want to pick a privileged monoid from a ring?

denisrosset commented

I haven't seen the newtype approach implemented in other symbolic computation systems.

For example, both GAP and SAGE duplicate the structure into additive and multiplicative variants (note: both use multiplicative notation for monoids/groups by default).

The newtype approach is fine when you are just using a generic monoid. In the context of linear algebra, the full precision is precious + the coherence of the whole is precious. See for example https://github.com/denisrosset/scalin/blob/master/core/src/main/scala/scalin/Mat.scala where different operations become available on a matrix depending precisely on the scalar type (the Mat type is mostly a syntax placeholder).

For example, trace requires only an additive monoid. The operation kron a multiplicative semigroup, while the conjugate transpose requires an involution: but Spire's involution is defined so that it is obeys laws with respect to a multiplicative monoid if present, so that in the linear algebra library, additional laws hold for the Kronecker product.

In the end, maybe cats/algebra does not require per se such a fine grained distinction. But the possibility of making such distinctions downstream is precious.

LukaJCB commented

I see the force is strong on this one. Before I present my case, let's acknowledge that there is no optimal solution there, just sets of different trade-offs.

Fully agreed, and thanks for putting in the effort to fully explain your position and bearing with me 😄

For example, both GAP and SAGE duplicate the structure into additive and multiplicative variants (note: both use multiplicative notation for monoids/groups by default).

That SAGE link doesn't appear to be working.

For example, trace requires only an additive monoid. The operation kron a multiplicative semigroup, while the conjugate transpose requires an involution: but Spire's involution is defined so that it is obeys laws with respect to a multiplicative monoid if present, so that in the linear algebra library, additional laws hold for the Kronecker product.

This is interesting and seems sensible to me, however I'm still a bit unclear as to why you definitely need an AdditiveMonoid. To me, the terms additive and multiplicative only make sense in the context of Rings, but I concede that that may be a misconception on my part. Are there any data types that support only additive or only multiplicative semigroups?
My point is that if you want to disambiguate between addition and multiplication, it only makes sense to apply it to a structure that know the difference, i.e. a Semiring.
If you want to apply the principle of least power, then the least power you need to implement trace isn't AdditiveMonoid but just Monoid.

I think I have more to say on this, but I'm out of time right now and will continue this soon :) Thanks again for your time!

  • 👍1
denisrosset commented

Corrected the SAGE link, thanks for the comment!

Before replying to your points, let's mention that I've been bitten by the Scala typesystem when trying to encode mathematical structures using categorical concepts. It's simply not powerful enough to encoding structures that e.g. SAGE or Magma (another CAS) implement. So trade-offs are needed. Spire does not aim at providing an abstract framework for all math, but basically "undergraduate mathematics", i.e. the default context you get when running Mathematica or Maple.

To answers your points.

There are data types that support only multiplicative semigroups. As a concrete example, the monomial part of polynomials (e.g. x^2, x*y) form a monoid, and when performing global optimization over polynomials, you'd want to take the outer product of two vectors (v * v.transpose), with those vectors containing monomials. So I'm glad my matrix library lets me do that without pushing towards enlarging that type to full-blown polynomials (because that would be type unsafe).

As for additive groups, vector spaces form an additive group without a corresponding multiplicative group.

Now, to clarify my position:

  1. The distinction between additive groups and multiplicative groups has to stay. There is simply now way to write a usable generic linear algebra library without them (happy to walk you through a concrete example implementing global polynomial optimization to see what's required, for example, but I'd prefer to do that live).

  2. If we merge Semigroup/Monoid/... with one of the additive/multiplicative variants, for mathematical uses it should be the multiplicative variant. The only cases where I've seen additive notation being used in maths was for commutative/abelian groups. Using e.g. additive notation for permutations in mathematical code is a no go for usability (note that the current Monoid.empty, Monoid.isEmpty is not satisfactory compared to the previous Monoid.id, Monoid.isId, but at least it is not misleading). Note that this suggestion contradicts what cats users would expect when merging Map[String, Int].

  3. While at the cats level, the generic, additive and multiplicative variants are interchangeable outside of a ring combining them, there are interpreted in different ways when combined with other typeclasses in Spire.

  • On (commutative) additive groups, we have extra structure in the presence of an order, see https://en.wikipedia.org/wiki/Linearly_ordered_group . This provides the laws for the sign/absolute value business.

  • Additive groups are at the basis of modules/vector spaces.

  • Multiplicative semigroups have extra structure in the presence of complex conjugation.

  1. Thus I'd recommend: keep the 3 group variants, and the additive/multiplicative variants only in algebra. Don't have cats-core depend on algebra (cats has a different outlook on group genericity). Have generic monoids/groups instances for primitive types in cats-core. In algebra, we can add an implicit conversion from additive structures to generic structures, so that merging Map[String, Polynomial[BigInt]] is possible with the additive structure.
johnynek commented

Denis. I have a PhD in quantum information and computation and an undergrad degree in math.

I mention that because it feels like the argument in this thread is being made from a position of authority: “I am doing some fancy stuff and I assure you it is only possible if the abstraction works exactly this way”.

I think this is not a way to argue for something and I think if we can’t make a concrete case for many cars users these abstractions don’t belong in cats.

What I think we need to see some stronger arguments for cats to include these types for any reason other than we like you and @non and y’all just really like them, which I guess can be okay in some limited cases.

Cats largely is about lawful abstractions.

Can you clarify any law an additive monoid has to follow that a multiplicative does not or vice versa?

I am aware of no such law in algebra. As far as I can see they exist in order to distinguish the two structures in rings. Rings have laws but independently these additive and multiplicative structures don’t have separate laws.

Can you show some actual code you can’t see how to generalize which you can do lawfully using additive/multiplicative?

We need to be more concrete.

The default position is non-inclusion. So I think the include case needs to be made and more concretely in my view.

denisrosset commented

@johnynek

Please point me where I made an argument of authority. I think I provided quite a few examples, and I'm sincerely curious about how the same algebraic structures could be encoded with a newtype approach, or with the simplified hierarchy inspired by PureScript.

I'm not adamant for the inclusion of algebra into cats, if that's the sticking point. (Actually, I'm curious about the use of ring structures in Algebird; can you point me to relevant examples?)

I'm adamant on preserving the syntactic distinction between additive and multiplicative structures in Spire, as is standard in other computer algebra systems (see links above).

Finally, great that you were active in quantum information! I did not expect that at all.
If that interests you, you can have a look at a recent preprint regarding the use of Scala in NC polynomial optimization. The use of semidefinite programming in quantum info took off between 2004 and 2010. I'm coming late to the party (would have loved to be in the field ~10 years earlier).
Comparing similar implementations done by colleagues in Python/Mathematica/Matlab, the use of Scala/Spire has been a boon: I've encountered exactly zero bugs when writing the pure functional part of the code.

LukaJCB commented

For me personally, I'm going to list a few reasons why I think having ring structures in cats would be great:

  1. We already have a ring-like typeclass in cats.Alternative complete with distibutivity and absorption laws. IMO it's a glaring inconsistency that'd we have a higher kinded version, but no "regular" one. You can do some pretty cool things, like e.g. alternative validation as seen in PureScript, that you can't really do in Cats right now.

  2. Both algebra and Cats-core have fine-grained imports only by instance type and both extend the cats-kernel instances. This means you can easily get highly annoying implicit ambiguities simply by importing from both cats.instances.* and algebra.instances.*. Right now there's no good way around that to my knowledge and it makes working with both pretty cumbersome. E.g. https://scastie.scala-lang.org/2qlrVMllTQC3t1yb9BOC3Q

import cats.implicits._
import algebra.instances.all._

1 |+| 1 // value |+| is not a member of Int
  1. The lack of finer grained numeric typeclasses in cats makes defining abstract programs with numerics much more difficult, many people I know opting instead for the stdlib Numeric type, which I think is a fairly bad sign. One example of this is newts which offers a Mult newtype for any N: Numeric and there are many others out there. This could be much nicer IMO.
benhutchison commented
denisrosset commented

The main problem imho is that the Scala type system is not powerful enough to declare distinct instances of the same typeclass on a given object and combinations thereof (barring newtypes, but I wonder how one would write arithmetic or boolean operations with that syntax).

(In textbooks, you can summon as many instances as you wish by defining new notation, and God knows how many LaTeX symbols are out there.)

As an additional example: JoinSemilattice and MeetSemilattice are duplicate instances of Semilattice, which are then combined in Lattice. And all those instances are semigroups/monoids distinct from the generic semigroup hierarchy.

Now, to move forwards. We don't wish to duplicate all the Semigroup/Monoid convenience methods in cats for the additive/multiplicative/join semilattice/meet semilattice variants. But we could define newtype wrappers Additive(x), Multiplicative(x), Join(x), Meet(x) such that the resulting object gets implicitly the corresponding Semigroup/Monoid variant.

LukaJCB commented

Quick addendum to the Alternative Validation, I coded up a quick example of what we could do if Semiring were available in Cats-core :)

case class MatChain[A](value: Chain[Chain[A]])

sealed trait AltValidation[+E, +A]
case class Valid[A](a: A) extends AltValidation[Nothing, A]
case class Invalid[E](e: E) extends AltValidation[E, Nothing]
  
type ValidatedMat[E, A] = AltValidation[MatChain[E], A]


def validateInt(s: String): ValidatedMat[String, Int] = 
  try(Valid(s.toInt)) catch { 
    case e: Throwable => Invalid(MatChain.one("No number"))
  }
  
def validateBoolean(s: String): ValidatedMat[String, Boolean] =
  if (s.toLowerCase == "true") Valid(true)
  else if (s.toLowerCase == "false") Valid(false)
  else Invalid(MatChain.one("Not a bool"))
  
  
def validateIntOrBoolean(s: String): ValidatedMat[String, Either[Int, Boolean]] =
  validateBoolean(s).map(_.asRight[Int]) <+>
    validateInt(s).map(_.asLeft)
    

val validInt = "42"
val validBool = "True"
val invalid = "Nope"

println(validateIntOrBoolean(validInt)) // Valid(Left(42))
println(validateIntOrBoolean(validBool)) // Valid(Right(true))
println(validateIntOrBoolean(invalid)) // Invalid(MatChain(Chain(Chain(Not a bool), Chain(No number))))

https://scalafiddle.io/sf/EfMFoe6/3

denisrosset commented

What is AltValidation? Anything I can read?

LukaJCB commented

It's just a newtype over Validation/Either, it's all in the fiddle I linked :)

LukaJCB commented

As for other things to read, the only thing I've got is the inspiration from PureScript: https://pursuit.purescript.org/packages/purescript-validation/3.0.0/docs/Data.Validation.Semiring

denisrosset commented

@johnynek I've just met with people in Siegen working on a formal approach to the description of algebraic structures. Right now, they are working on top of a dynamically typed language (GAP), but assured me that their approach solves a lot of ambiguities. Their system is here: http://homalg-project.github.io/CAP_project/CAP/doc/chap0.html , but I haven't taken the time yet to investigate (they have examples and tutorials, but you have to look for them).

It would be interesting to see if our Scala instances can benefit from their principled approach.

LukaJCB commented

This is really cool, thanks for sharing!

denisrosset commented

@johnynek Thanks a lot for the insightful comments and the debate. It led to a talk at the Lausanne Typelevel summit, and many discussions with people in the industry.

Especially

I mention that because it feels like the argument in this thread is being made from a position of authority: “I am doing some fancy stuff and I assure you it is only possible if the abstraction works exactly this way”.

Sometimes it is worth losing a bit of performance / expressiveness if it means getting community traction.

johnynek commented

I'd love to watch the talk and view the slides. Please post them if possible!