What's wrong with algebraic types in KMath? (Or is it me?)

[lounres]

I have worked a bit with KMath (but still did not even opened NDStructures nor linear algebra), and there are some moments that makes mathematician in me faint.

It has the same theme with #192 and #103, but as I understand the question is absolutely open. So I want any clear answer, what is the state of the problem right now: is it needed to do something, what meets KMath ideology and what does not, etc.

(Almost) everything depends on Double

In KMath there are usual basic algebraic types that have sensible gradation (of course, it's not linear): GroupOps, Group, RingOps, Ring, FieldOps, ... but not Field. The Field made abrupt move in implementation: besides Ring and FieldOps it implements ScaleOperations and NumericAlgebra. The first problem I see here is ScaleOperations's scale method. It makes you scale your field members with real (Double) values. It doesn't make any sense when you try to implement your own field.

At first consider rational numbers. There is sense in multiplication or addition it with integers (integer is rational, so everything is OK). But what should I do with real value? OK, Double is not real value, but some interval (precision and suchlike), so you can approximate it with rational numbers with corresponding denominator, but it's strange way. At second consider any finite field. For example, F_4. It's not ring of integers modulo 4, it's field with 4 elements (constructive example is F_2[x]/x^2+x+1). And there is hardly any sense in scaling any of the 4 members by Double to get some other one (or the same one).

The only counterargument to this I see is phrase "By documentation, the convention of the interface is that the interface just extends the usual field definition with scaling". It is strange that there is nothing about it in /docs directory (see here) but there could be reasons (like simple acquaintance with the subject) and it's not the main problem. The main problem is that I can't understand the sentence (and the sentence from docstring). What scaling does it describe (what the scaling should do)? How does it mean that there must be multiplication (and division) on any Number implementation.

What is Number? Is it everything or is it nothing at all?

"What is Number?" was one of my first questions in programming on JVM platform. And all answers I know are lame. I see it as unification of relationship between primitive numbers (int, short, long, double, float, byte and their wrappers). I don't know how is it for case of the considered types (I think it's good), but it's senseless to try implement the interface in other classes. Or try to implement any very abstract numerical logic with it. Numbers can be very different (as we already know it can be F_p, Z, Q, R or a lot of other realizations). And in a lot of cases there is no relation between two different rings or fields, so converting members of one of them to another is senseless. Number is a good way for very few rings or fields.

So when I found this interface the first time, after seeing the name Number I thought it's everything numeric (or as others say algebraic), and after reading its declaration I understood that it's nothing at all (nothing can be meaningfully converted to any number). That's why I don't see any profit in it. Why do KMath use it?

Conflicting conventions of Field interface

And the worst thing here, that the Field does not have any more or less concrete definition, because it can not. It has different meanings in different implementations. For example, in DoubleField it means honest mathematical field, in FieldND it means element-wise multiplication and division, in BigIntField it means Euclidean division. So what exactly is Field? Why not to make different interfaces and formal conventions for them? Why not say that

1. DoubleField is honest field,
2. FieldND is a vector space with Hadamard product, or an algebra (not KMath algebra, mathematical algebra) with partially working division, or just vector space, but that one exemplar has multiplication and division, and
3. BigIntField is Euclidean ring.

What's the fuss about it? It's simple. One of the main features of KMath I saw at first is that you can prevent simple logic mistakes by delegating some logic to type mechanism of Kotlin, that will check if something stupid is off. Different types can not replace each other and suchlike. But mixing a lot of logic in one object prohibits you from use of the strategy. It looks like little self-contradiction. And also the fact that using BigInt (with Euclidean division) in polynomials is allowed by KMath scares me a lot. And not because it's strange object (actually vice versa), but because there would be consequences of the operations like converting to monic polynomial, or calculating GCD (there is correct behaviour for them, but not the same as for fields).

May be it is something usual for physical calculations, but I hope KMath will be library not only for physicists, but also for mathematicians.

Summing up

I don't understand KMath usage of some details. And some of them as I understand are part of KMath ideology. So I want to understand what is wrong and with whom.

[altavir]

I think it is better to split those discussions in several threads, but I can try to all questions in separate comments.

(Almost) everything depends on Double

It is a compromise. I tried to use more general Number, but the problem is that we need to use concrete numbers in implementations. And interpreting number as double or int implicitely could lead to unexpected behavior, so it was discarded. It is possible to use additional generic type for numbers involved in scaling, but it would make API much more cumbersome without a good cause. Currently, one is free to do an alternative scale operations for any type so it is possible to bypass this limitations.

Any prototypes that solve this problem are welcome as PRs.

[altavir]

Actually, using additional generic for scale operation could be feasable. It would be used only once during algebra type actualization. But it needs to be tested.

[lounres]

Yeah, in mathematics you always consider algebra, vector space or module over some fixed (predefined) ring or field. So I mean, it makes sense to add another generic type: it helps to concentrate only on needed types to scale with.

I'll try to implement a prototype in spare time.

[altavir]

What is Number? Is it everything or is it nothing at all?

The Number class is one of the design flaws in Java. It is intended as some kind of intersection type that has behaviors of all numbers. At the same time it is extendable, adding new numbers, which it is not compatible to. In real life we would like something like an open union type, which could be actualized as an actual subtype. I am not sure it is possible to introduce such concept without breaking any compatibility with JVM ecosystem. Though we can try to prototype it. But one needs to think about performance and readability. We would need to introduce value types for primitives and overload all operations on primitives to use that wrapper types. Not sure it is feasable.

[lounres]

In real life we would like something like an open union type, which could be actualized as an actual subtype.

I cannot understand that moment. I mean, if you speak about union type for members of algebraic structure, then why do you need it? Actually, it's just Any? because any set of objects forms an algebraic structure as soon as you implement an algebraic structure on them. And if you speak about union type of algebraic structures themselves, then also why do you need it? Although KMath's Algebra is already such union type.

By that I mean that in mathematics when you work with structures you just consider some group, ting, field, etc., you don't need anything from members of the algebraic structure except that it is set used in definition of the structure and that there are some detailed elements in it (like zero and one, or standard basis, etc.). So I don't understand why do you need all numbers or all algebraic structures, when in concrete cases you need concrete numbers and concrete algebraic structures.

About realisations and performance. The obvious way (that I see) is to implement interfaces with just logic you want object to have. If you need vector space with elements of type V over field working with elements of type C create an interface that declares addition (and, maybe, subtraction) of elements of V and scaling with element of V and element of C. You don't need other types (like Double) actually; although it is better to declare multiplication or even addition with integers because they have sensible interaction with your structure (that is almost obvious for everyone). But yes, this way makes primitives to be boxed, so the only way to work it around is to reimplement such interfaces removing type arguments by substituting primitives. On the one hand, it's boring and is a bit confusing (because sometimes there will be a number of duplicates of only one interface), but on the other hand Field is actually a realisation of algebra over Double, i.e. there are Double duplicates when there is no duplicated interface itself.

[altavir]

We are both saying more or less the same thing. Number should not be used because it is disfunctional. We mostly managed to remove it. I just quick searched the code base and we have it mostly for interoperability.

[altavir]

Conflicting conventions of Field interface

Well, mathematical correctness was not the ultimate goal. Because we need a practical tool, not a correct one. We tried to follow very general definition of algebras. But we could not follow it fully of course (though, specific proposals are welcome).

There are two important features of algebras:

1. They allow to isolate operations, so operations are not fully defined on types they are used on, but instead by scopes where they are invoked.
2. Reduce code duplication by implementing operations on generic algebras instead of re-implementing it for all of them.

The first point was secondary initially, but now it is the main. And usage of context receivers, will allow to simplify the hierarchy even further (and make it more flexible).

As for the second one. Consider integration. You need only sum and division by nubmer operations to do Riemann integration. If we could abstrac away scopes that provide those operations, we could implement integration once and then apply it to any algebra that has necessary features. That way there is an example here that shows effortless integration with matrices.