Interfaces für Arithmetik


#1

In einem pet-project verbrenne ich gerade gelegentlich etwas Zeit mit recht elementaren Fragen - nicht wirklich mit einem konkreten Ziel (außer vielleicht: Wie weit kann man gehen, bevor es unbenutzbar wird :wink: )

Im Zuge dessen wollte ich ein interface erstellen, mit dem man “allgemeine arithmetische Operationen” durchführen kann. So weit, so einfach:

interface Arithmetic<T> {
    BiFunction<T, T, T> addition();
    BiFunction<T, T, T> subtraction();
    ...
}

Man kann sich eine triviale Implementierung davon vorstellen, mit T=Double oder irgendeinem anderen numerischen Datentyp.

Hey.

Numerisch.

Neee. Ich würde auch gerne sowas machen:

OffsetDateTime t0 = ...;
OffsetDateTime t1 = ...;
Duration duration = arithmetic.difference().apply(t0, t1);

Und schwuppdiwupp wird’s kompliziert. Das Problem ist, dass OffsetDateTime nicht numerisch ist, oder spezieller: Die Differenz von zwei OffsetDateTime-Objekten ist eine Duration. (Oder eine Period, aber lassen wir das jetzt erstmal außen vor :roll_eyes: )

Man muss also bei dieser Arithmetik zwischen dem eigentlichen Datentyp und dem Differenztyp unterscheiden. Das ist auch noch handhabbar:

public interface Arithmetic<T, D>
{
    BiFunction<T, D, T> addition();
    BiFunction<T, D, T> subtraction();
    BiFunction<T, T, D> difference();
    ...
}

Jetzt gibt es aber Datentypen, die man miteinander multiplizieren kann, und das passt in dieses Interface schlicht nicht rein. Man will einerseits sowas

BiFunction<D, D, Double> scalarDivision();
BiFunction<D, Double, D> scalarMultiplication();

als auch sowas

BiFunction<T, T, T> division();
BiFunction<T, T, T> multiplication();

Man könnte da sicher einiges mit den passenden algebraischen Strukturen abbilden. Also Group (additiv und multiplikativ) mit den passenden inversen Elementen, Ring, und Field. Einige sind da schon recht weit gegangen, z.B. in JScience: http://www.jscience.org/api/org/jscience/mathematics/structure/GroupAdditive.html

Aber auch dort können affine Räume nicht abgebildet werden: Zwei OffsetDateTime-Objekte kann man nicht addieren. Ein OffsetDateTime und ein Duration-Objekt schon. Zwei Duration-Objekte eigentlich auch. Hm.

Hat jemand ein paar Gedanken dazu?


#2

Das erinnert mich an die Operatorenüberladung von C++ was du da machst und da ist das schon kritisiert. Warum möchtest du sowas in Java und dann auch noch in viel schlechter übersetzen? :smiley:


#3

Wäre es nicht einfacher den Datentyp Number um die abstrakten Methoden add, multiply und isInteger zu erweitern und dann in einer Math ähnlichen Klasse all die Arithmetik, die sich auf add und multiply reduzieren lässt, implementiert? Ich versuche zumindest gerade etwas Derartiges und brauche dazu nicht einmal zwischen BigInteger und BigDecimal zu unterscheiden. Probleme bekomme ich nun aber mit Registern (mutables) und Konstanten (nonmutables).

Mit nicht numerischen Werten gibt es btw. immer das Problem, dass sie “irgendwie” formatiert sind. Mathematische Arithmetik lässt sich da ohnehin nur sinnvoll auf solche anwenden, die in numerische Werte gewandelt werden können, wie z.B. Time, Date und Ähnliches.


#4

Das hat mit Operatorüberladung nicht viel zu tun. Es geht eher darum, dass für gegebene Klassen/Objekte die mathematischen Operationen angeboten werden sollen.

Das ist auch der Grund, warum ein eigener Datentyp nicht die Lösung ist.

Ein Beispiel. Das ist nicht (genau) das, worum es eigentlich geht, reicht aber hoffentlich, um den Anwendungsfall zu verdeutlichen (in Wirklichkeit ist alles komplizierter).

Es soll sinngemäß Methoden geben wie

List<T> apply(List<T> list0, List<T> list1, Arithmetic<T> arithmetic) { ... }

Und die berechnen für Elemente e0 und e1 aus den jeweiligen Listen z.B.

e = (e0 + e1) * e0 / e1;

oder irgendeinen anderen Ausdruck - eben “Irgendwas mit Arithmetik”. Und jetzt ist die Frage, wie man das vernünftig abbildet. Ursprünglich hatte ich gedacht, dass man das mit so einem Interface einigermaßen sauber abbilden könnte. Aber inzwischen glaube ich, dass man die Arithmetic-Klasse zerbrechen muss, und an jede dieser apply-Methoden spezifisch für das sein muss, was sie genau macht. Man bringt das einfach nicht unter einen Hut. (Dass man in vielen Fällen als letztes eine BiFunction übergeben kann, ist klar, aber manchmal reicht eine eben nicht…)


#5

OK, es gibt jetzt einen Commit mit dem lapidaten Kommentar: “Removed Arithmetics”. Aber trotzdem wären (über “was machst’n du da fürn Dreck?” hinaus gehende) Kommentare ggf. interessant. Tatsächlich ist das einer der Punkte, wo das Typsystem von Java an seine Grenzen stößt, aber das ist jetzt vielleicht zu allgemein…


#6

Da bräuchte man wohl eine Art Liste von möglichen Datentypen bei der Definition der Methode, um skalare und normale Multiplikation unter einen Hut zu bringen.

Das bietet Java natürlich nicht und ich weiß auch nicht, ob sowas wirklich wünschenswert wäre.

Ich finde deine Überlegungen aber durchaus interessant.

Und wenn du es einfach bei zwei verschieden benannten Methoden zur Multiplikation und Division belässt?


#7

Multiplikation und Division sind ja schon verschieden benannt. Ein paar (etwas unsortierte) Gedanken:

  • Manche Datentypen kann man miteinander multiplizieren. Z.B. double * double. Aber eben nicht OffsetDateTime * OffsetDateTime oder Duration * Duration.

  • Manche Datentypen kann man mit einem Skalar multiplizieren. Klar, double * double, oder Duration * double, aber nicht OffsetDateTime * double

  • Bei manchen Datentypen kann man die Differenz berechnen, oder ~“etwas addieren”. Und die Datentypen da werden etwas diffizil:

    double - double = double
    double + double = double
    OffsetDateTime - OffsetDateTime = Duration
    OffsetDateTime + Duration = OffsetDateTime
    Duration + Duration = Duration
    

Mit ist einerseits klar, dass das alles im Rahmen von Programmiersprachen schon abgefrühstückt wurde. Z.B. ist in Java eben double + double = double, aber double + String = String. Am anderen Ende, ganz theoretisch-formal, kann man auch schon vieles beschreiben. Z.B. ist (Duration, +) eben eine Gruppe, mit neutralem Element, und was die Skalare angeht kann man wohl mit einem https://en.wikipedia.org/wiki/Affine_space was machen. Aber das irgendwie einheitlich und sauber runterzudefinieren und in der Programmiersprache abzubilden erscheint mir recht schwierig…


#8

Dafür ist Number ungeeignet, das ginge nur mit Self-Types:

interface Num<N extends Num<N>> {
      N add(N n); 
      N subtract(N n); 
      ...
}

#9

Oder mit einer Implementation, die automatisch einen geeigneten Berechnungs- und Rückgabetyp ermittelt (schwierig) oder diese per MathContext (z.B. Mantissen- und Exponent-Bits) festlegen lässt.


#10

Irgendwie scheint eines der Hauptprobleme nicht so klar rübergekommen zu sein. Sicher weil ich auch etwas unstrukturiert gefragt habe. Aber bei einer Berechnungsfolge wie

OffsetDateTime t0 = ...;
OffsetDateTime t1 = ...;
Duration d0 = subtract(t0, t1);
Duration d1 = multiply(d0, 3.0);
OffsetDateTime t2 = add(t0, d1);

ist das Hauptproblem die Typmischung. Wenn man sowas nun generisch in eine tripleTheDistance-Methode einbauen wollte, wäre man bei

T tripleTheDistance(T t0, T t1) {
    D d0 = subtract(t0, t1);
    D d1 = multiply(d0, 3.0);
    T t2 = add(t0, d1);
    return t2;
}

Und wo sind nun welche Methoden auf welchen Typen festgelegt? Hm…


#11

Ich hab erst gegrübelt, wie du das mit dem affine space meinst. Nach dem Lesen von

ist mir aber klarer, was du meinst.

Allerdings wird da ja jedem Tupel von zwei Elementen ein “Vektor” (hier wohl eine Berechnungsvorschrift) zugewiesen. Du hast ja aber schon klar gestellt, dass man gar nicht alle Tupel sinnvoll verrechnen kann (etwa Duration * Duration).

Oder schwebt dir da eine “Berechnung” vor, die eine Ausnahme wirft? Dann könnte man damit vielleicht tatsächlich arbeiten.

Ich glaube aber das ist dann letztlich eher theoretisch wissenschaftlich interessant (und der Aspekt weckt gerade meine Neugier), und weniger für eine wirkliche Umsetzung auf der Ebene einer Programmiersprache.

Aber wer weiß. Mittlerweile gibt es auch für die ehemals vertrocknetsten, rein theoretischen mathematischen Fachgebiete praktische Anwendungen.

Edit: Um etwas klarer zu machen, was ich verstanden habe, dass es dir vorschweben könnte:

Wir haben die Menge A = { double, Duration, OffseteDateTime } und erzeugen einen affinen Raum, welcher jedem Tupel (a, b) ∈ AxA eine Rechenvorschrift R(a,b) zuweist.

Da müssen dann aber die beiden Gesetze von der Wikiseite gelten und man muss sich überlegen, wie dieser Vektorraum aussieht (und der muss den Gesetzen eines Vektorraumes genügen).


#12

Nun, um da sicherer argumentieren zu können, müßte ich an einigen Punkten bei der Theorie noch etwas auffrischen oder tiefer bohren. Darum jetzt mal alles mit Vorbehalt:

Es ist meinem (etwas schwammigen) Verständnis nach nicht so, dass “der affine Raum den Tupeln Berechnungsvorschriften zuweist”. Stattdessen ist es so, dass z.B. (OffsetDateTime, Duration, +) ein affiner Raum sind: Die “Punkte” sind OffsetDateTime und die “Vektoren” sind die Duration. Bildlich gesprochen kann man mit solchen geometrischen Punkten und Vektoren ja rechnen:

  • Punkt + Vektor = Punkt
  • Vektor + Vektor = Vektor
  • Vektor * Skalar = Vektor
  • Punkt + Punkt = Geht nicht
  • Vektor * Vektor = Geht nicht (außer Skalarprodukt, euklidisch, Spezialfall)

und das “passt” eigentlich alles, wenn man dort OffsetDateTime und Duration einsetzt.

(Mit double geht das trivialerweise auch. Da geht auch Punkt+Punkt oder Punkt*Vektor oder alles andere. Wenn die Arithmetik für so einen affinen Raum schon reichen würde, um “alles notwendige” abzubilden, wäre es ja nicht schlimm, wenn in einem Fall noch mehr ginge. Aber das dann irgendwie zu benennen wäre auch wünschenswert: Das ist etwas, was über einen “affinen Raum” hinausgeht - und wie heißt das? Eigentlich wäre das dann einfach ein Körper… :confused: )

Exceptions will ich übrigens nicht werfen. Ich hatte zwar für den angedeuteten Fall mit Punkt * Punkt gedacht, dass das für Double OK wäre, und für OffsetDateTime eine UnsupportedOperationException werfen könnte, aber die UnsupportedOperationException wirkt immer wie eine Krücke, wenn man Sachen nicht sauber ausmodellieren wollte oder konnte.

Ich finde übrigens, dass das nicht nur theoretisch interessant ist. Ein bißchen theoretisch ist es vielleicht, ja, und in der Praxis könnte man an einigen Punkten “pragmatischer” sein. Aber der Anwendungsfall ist (wie oben schonmal angedeutet) GROB sowas:

Man hat eine List<T>. Und man will überprüfen, ob alle Elemente dieser Liste den gleichen Abstand haben. Das heißt: Man muss zwischen zwei aufeinanderfolgenden Elementen dieser Liste eine Differenz berechnen können. Etwa so:

boolean allHaveSameDifference(List<T> list) {
    D firstDifference = null;
    for (int i=0; i<list.size()-1; i++) {
        T t0 = list.get(i);
        T t1 = list.get(i+1);
        D difference = computeDifference(t0, t1);
        if (firstDifference == null) firstDifference = difference;
        else if (!difference.equals(firstDifference)) return false;
    }
    return true;
}

So weit ist das ja noch recht einfach: Das computeDifference könnte irgendwie pragmatisch über eine BiFunction<T, T, D> abgebildet werden, die notfalls als Parameter übergeben wird. Was T und vor allem D dann sind, muss der Aufrufer entscheiden.

Nächster Schritt: Man hat eine List<T> und will (dummy-Beispiel) ein weiteres Element extrapolieren. Das neue Element soll den gleichen Abstand haben, wie die letzten beiden. D.h. die Liste endet mit den Elementen (..., x, y), und man will ein weiteres Element z anfügen, mit z-y == y-x

void extrapolate(List<T> list) {
    T tx = list.get(list.size()-2);
    T ty = list.get(list.size()-1);
    D d = computeDifference(ty, tx);
    T tz = add(ty, d);
    list.add(tz);
}

Da wird’s dann schwierig. Addition und Subtraktion auf unterschiedlichen Typen (das ist dann das affine…).

Eine weitere Operation könnte z.B. sein, den Abstand zwischen jeweils zwei aufeinanderfolgenden Elementen zu verdoppeln, d.h. mit dem skalaren (double) Faktor 2.0 zu multiplizieren.

Ich denke, dass man mit einer gewissenhaften Ausmodellierung von Klassen/Interfaces wie Group, Ring, Field, VectorSpace, AffineSpace & Co, da sehr weit gehen könnte (nochmal der Verweis auf http://jscience.org/api/org/jscience/mathematics/structure/Field.html - die sind da schon recht weit gegangen). Aber es könnte recht aufwändig werden, und am Ende kompliziert (und auch kompliziert zu benutzen).

Da vielleicht doch nochmal der Querverweis zur Operatorüberladung von C++, die @TMII angesprochen hat: Dort ist es ja so, dass man in template-Methoden einfach irgendwelchen Kram hinschreiben kann. Grob sowas wie

 template <T> 
 void extrapolate(vector<T> v) {
    T tx = v[v.size()-2];
    T ty = v[v.size()-1];
    T tz = ty + (ty - tx);
    list.push_back(tz);
}

Der Compiler macht dann eine “Textersetzung”, und fügt praktisch den kompletten Code (!) für jeden Datentyp ein, mit dem das ganze aufgerufen wird. Und wenn dieser Datentyp dann keinen + oder --Operator hat, erscheint ein kryptischer Compilerfehler…


#13

Ah dann hatte ich da viel zu kompliziert gedacht.

Wenn man es hinbekommen würde, dass es leicht zu benutzen ist, könnte es gekapselt und gut getestet unter der Haube ja ruhig komplex sein.

Mein C++ ist schon etwas eingerostet, aber war es nicht dort so, dass man selbst für seine Klasse ausprogrammieren konnte, was +, - und so weiter veranstalten, und dass das Opertorenüberladung bedeutete?


#14

Sicher. Der letzte Punkt bezog sich darauf, dass man, wenn man so einen Typ als das T im Template verwendet, der Compiler eben “ad hoc” prüft, ob das passt - d.h. ob es die Operatoren gibt, die im Templatecode verwendet werden. Wenn man in das Beispiel also z.B. einen Vector3D reinsteckt, der + und - kennt, dann compiliert es. Wenn man dort ein MyString reinsteckt, das nur + (aber nicht -) kennt, dann kracht es.

Der Punkt ist also etwas spezifischer, dass man bei C++ bisher nicht ein interface definieren muss, das alle relevanten Funktionen definiert, und dann an die Methode nur Objekte übergeben werden können, die das Interface implementieren, sondern dass durch “Textersetzung” für jeden Typ erkannt wird, ob er da reinpasst oder nicht.

Dass das nicht immer der Weisheit letzter Schluss ist, haben die C++ler inzwischen auch gemerkt. Ein auf einen Sprachen-Flamewar ausgerichteter Mittelfinger in Richtung C++ wäre der etwas polemische und natürlich ‘falsche’ Hinweis: "concepts == interfaces, willkommen im 21. Jahrhundert :sunglasses: "

Sowas wie der Datentyp auto x = y-z; in C++ hilft aber schon, generischen Code zu schreiben…

Aber hier soll es vorrangig um Java gehen, und eben die Frage, wie man solche Konzepte (sic) vernünftig in interfaces abbildet.