List und default methods

Byte-Welt - Projekte / Projects neco4j
41

********[QUOTE=cmrudolph]Hast du schon Ergebnisse?[/quote]

Nichts wirklich hübsches. Aber ich poste es trotzdem mal.

Zum grundsätzlichen Design mit den ganzen default-Methods habe ich heute einen Blogbeitrag gelesen, in dem auf diese Mail von Brian Goetz verlinkt war.

Nachdem ich mich ein wenig mehr mit default-Methods und den Auswirkungen bei deren intensiven Nutzung beschäftigt habe, bin ich für mich zu dem Ergebnis gekommen, dass es vielleicht sinnvoll wäre, einen klassischeren Ansatz zu verwenden und eine Kombination aus Interface + abstrakte Klasse zu entwerfen.
Wie das konkret aussieht ist natürlich auch stark davon abhängig, was deine Abstraktionsansätze bisher ergeben haben bzw. inwiefern wir gemeinsam eine schöne Abstraktion finden.

Welches konkrete Problem würden abstrakte Klassen anstatt default-Methoden lösen? Herrn Goetz’ Meinung in Ehren, aber wir haben jetzt nun einmal „poor man’s traits“ zur Verfügung.

Benefit: how would having this feature enable me to write code that is
better than what I can write today.

Cost: how would having this feature enable other people to write WORSE
code than they might write today.

Ich weiß, dass diese Sichtweise in der Java-Welt weit verbreitet ist, aber leider ist sie schlicht fehlgeleitet. Die Wahrheit ist: Man kann nichts „idiotensicher“ machen, und es ist ein Fehler, es überhaupt zu versuchen. Hat sich Herr Goetz einmal angeschaut, was gewisse Leute schon vorher mit Java veranstaltet haben? Als Beispiel: Wieviele falsche equals-Implementierungen hast du schon gesehen? Ist den Leuten, die den equals-Kontrakt nicht einhalten, irgendwie damit geholfen, wenn sie das in Interfaces nicht auch noch falsch machen können? Und ist von Leuten, die equals implementieren können, zu erwarten, dass sie ein korrektes equals in Interfaces auf einmal geistig überfordert?

Es ist eine Sache, Dinge ergonomisch und bei normalen Gebrauch sicher zu gestalten, aber es wird immer Missbrauch in der einen oder anderen Form geben. Andersherum betrachtet: Wie gut kann ein Pistole sein, die nicht einmal genügend Bums oder so viel Sicherheitsvorkehrungen hat, um sich damit in den Fuß zu schießen? Wenn ich damit in den Fuß meines Gegners schießen kann (was ja Sinn und Zweck eines solchen Geräts ist), wie soll dann verhindert werden, in den eigenen zu schießen? Wie nützlich kann ein entsprechend „sicheres“ Sprach-Feature sein?

42

Ich wollte mir für diese Antwort ein wenig Zeit nehmen, weil das Thema recht diffizil ist. Bei all meinen Äußerungen ist zu beachten, dass ich noch nicht viel Designerfahrung habe (du programmierst wahrscheinlich schon doppelt so lange wie ich) und noch auf der Suche bin (die wahrscheinlich auch nie enden wird).

Interface und Implementierung würden entkoppelt. Abgesehen davon gehören in ein Interface eigentlich keine statischen Methoden (genau wie dort keine magischen Konstanten reingehören). Die Erzeugung eines Objektes sollte außer in einfachen Fällen von der Klasse des Objektes unabhängig sein und von einer Factory übernommen werden, der Konstruktor sollte höchstens die Constraints prüfen (notNull der Einträge), um die Logik der Klasse möglichst aufgabenorientiert zu halten.
Das Ergebnis wäre eine klarere Trennung der Aufgaben.

Diese Ansicht hatte ich auch mal (weshalb ich vielleicht auch irgendwann bei Java gelandet bin), allerdings zu Zeiten als ich PHP programmiert habe (das war äußerst unbefriedigend :wink: ). Davon bin ich mittlerweile aber auch weit weg und versuche einen sinnvollen Kompromiss aus Nutzbarkeit und Sicherheit zu finden.

An dieser Stelle geht es dann darum, die richtige Abstraktionsebene zu finden: genügend Flexibilität zu bieten und ausreichend sicher zu sein, sodass die Klasse ohne groß darüber nachzudenken nutzbar ist. Das gilt es gegeneinander abzuwägen (und dabei muss ich jetzt an Kent Becks wedelnde Armbewegungen in den von dir verlinkten Videos denken :wink: ).

43

Das Problem mit Abstraktion ist in unserem Fall vor allem, dass Java keinen “Selbst-Typ” besitzt: Wenn man ein allgemeines List-Interface mit wenigen Methoden hat und eine Klasse mit weitergehenden Methoden zwingt man den Nutzer entweder, mit dem Typ der konkreten Klasse zu hantieren, oder Upcasts durchzuführen. Das kann man auch in den “offiziellen” Collections-Klassen u.s.w. sehen: Die Hierarchie ist (zu) flach, und es werden Methoden angeboten, die nicht überall implementiert sind (etwa add für unmodifizierbare Listen, oder auch remove in Iterator). Das CRTP wie in der Klasse Enum<E extends Enum<E>> hilft uns hier leider auch nicht, weil damit Methoden wie map nicht abgebildet werden können.

44

OK, mal ganz grob ein mögliches Super-Interface, das in etwa spiegelbildlich zu List wäre:

package org.neco4j.collect;

import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;

public interface Seq<A> extends Iterable<A> {

    Seq<A> plus(A a);

    Seq<A> append(Seq<A> that);

    Optional<A> headOpt();

    default A head() throws NoSuchElementException {
        return headOpt().orElseThrow(NoSuchElementException::new);
    }

    Optional<? extends Seq<A>> tailOpt();

    default Seq<A> tail() throws NoSuchElementException {
        return tailOpt().orElseThrow(NoSuchElementException::new);
    }

    Optional<? extends Seq<A>> initOpt();

    default Seq<A> init() throws NoSuchElementException {
        return initOpt().orElseThrow(NoSuchElementException::new);
    }

    Optional<A> lastOpt();

    default A last() throws NoSuchElementException {
        return lastOpt().orElseThrow(NoSuchElementException::new);
    }

    default Optional<A> getOpt(int index) {
        int i = 0;
        for(A a : this) {
            if (i++ == index) {
                return Optional.of(a); 
            }
        }
        return Optional.empty();
    }

    default A get(int index) throws IndexOutOfBoundsException {
        return getOpt(index).orElseThrow(IndexOutOfBoundsException::new);
    }

    default int size() {
        return foldLeft(0, (n, a) -> n + 1);
    }

    default boolean isEmpty() {
        return !headOpt().isPresent();
    }

    Seq<A> reverse();

    <B> Seq<B> map(Function<? super A, ? extends B> fn);

    <B> Seq<B> flatMap(Function<? super A, ? extends Iterable<B>> fn);

    Seq<A> filter(Predicate<? super A> predicate);

    default boolean all(Predicate<? super A> predicate) {
        for (A a : this) {
            if (!predicate.test(a)) {
                return false;
            }
        }
        return true;
    }

    default boolean any(Predicate<? super A> predicate) {
        for (A a : this) {
            if (predicate.test(a)) {
                return true;
            }
        }
        return false;
    }

    default <B> B foldLeft(B start, BiFunction<? super B, ? super A, ? extends B> fn) {
        B value = start;
        for (A a : this) {
            value = fn.apply(value, a);
        }
        return value;
    }

    default <B> B foldRight(BiFunction<? super A, ? super B, ? extends B> fn, B start) {
        B value = start;
        for (A a : this.reverse()) {
            value = fn.apply(a, value);
        }
        return value;
    }

}
  • Es wird angenommen, dass die Länge der Sequenz nicht fest ist, also Operationen wie plus() und tail() Sequenzen anderer Länge zurückliefern
  • Es macht keine Annahmen über die konkrete Implementierung, insbesondere nicht darüber, ob die Sequenz lazy oder strict ist
  • Es enthält keinerlei Methoden zur Konstruktion
  • Default-Methoden werden nur da eingesetzt, wo es nur eine vernünftige Implementierung gibt (man sich z.B. nicht zwischen lazy und strict unterscheiden muss)
  • Es wird direkt von Iterable geerbt. Es fragt sich, ob wir ein Gegenstück zu Collection brauchen, denn ein Set (und sogar eine Map) könnte auch Seq implementieren (wobei reverse() nicht besonders sinnvoll und get() nicht besonders performant wäre). Allerdings würde dann plus() keine bestimmte Einfügeordnung garantieren.

Was meint ihr?

45

Schnelle Gedanken:

  • plus() hört sich für mich etwas irreführend an. Warum nicht add()?
  • zu einer Sequenz passt eine Methode size() nicht so gut. length() wäre besser. Bei den Implementierungen in Form einer Liste wäre size() dann wahrscheinlich wieder angebrachter. Bei einem Set erst recht.
  • auf die getOpt() Implementierung würde ich in Seq noch verzichten, weil sie annimmt, dass ein wahlfreier Zugriff nicht möglich ist (siehe #32: „Random Access List (von Okasaki)“)
  • auch die size() Implementierung würde ich weglassen, weil vorausgesetzt wird, dass die Größe nicht in einem Feld gespeichert wird
    (- die isEmpty() Implementierung würde ich ebenfalls weglassen, weil sie bei einer „ReverseList“ die worst-Case-Implementierung darstellt)*

Ansonsten sieht das Interface so schön aufgeräumt aus.

Diese Heuristik hatte ich auch verwendet, ohne deinen Beitrag zuende gelesen zu haben, als ich mir den Code angesehen habe. Ich halte sie für sinnvoll, gerade weil die IDE einen ansonsten zu einer schlechten Implementierung verführt, weil es bereits eine (in diesem Fall schlechte) Implementierung gibt (z. B. isEmpty() mit einer „ReverseList“).
*Falls wir die Annahme machen wollen, dass auf das erste Element in konstanter Zeit zugegriffen werden kann (was wahrscheinlich gar nicht verkehrt ist, weil die Implementierungen ja iterierbar sind), könnten wir die isEmpty()-Implementierung drin lassen und eine headOpt()-Implementierung einfügen:

    return getOpt(0);
}```
Falls die getOpt()-Implementierung drin bleiben sollte, würde ich die headOpt()-Implementierung auf jeden Fall dazu nehmen.

[QUOTE=Landei;97764]Es fragt sich, ob wir ein Gegenstück zu Collection brauchen, denn ein Set (und sogar eine Map) könnte auch Seq implementieren (wobei reverse() nicht besonders sinnvoll und get() nicht besonders performant wäre). Allerdings würde dann plus() keine bestimmte Einfügeordnung garantieren.[/QUOTE]
Wie meinst du das?

*** Edit ***

Gut finde ich auch, dass du die `public` alle weggelassen hast. Das war mir beim NecoList-Interface auch schon aufgefallen, da hatte ich das aber nicht geändert.
46

[QUOTE=cmrudolph]Schnelle Gedanken:

  • plus() hört sich für mich etwas irreführend an. Warum nicht add()?
    [/quote]
    Wir sind von Collections her so gewöhnt, list.add(x) zu schreiben, dass ich es besser fand, mit einem anderen Namen auf den Unterschied hinzuweisen. Bei einem plus in der Mathematik verändert sich der Summand dagegen auch nicht.
  • zu einer Sequenz passt eine Methode size() nicht so gut. length() wäre besser. Bei den Implementierungen in Form einer Liste wäre size() dann wahrscheinlich wieder angebrachter. Bei einem Set erst recht.

Da habe ich mich an Collections orientiert. Sicher ist size ein dummer Name, aber bei etwas collection-artigen wird er wohl erwartet.

  • auf die getOpt() Implementierung würde ich in Seq noch verzichten, weil sie annimmt, dass ein wahlfreier Zugriff nicht möglich ist (siehe #32: „Random Access List (von Okasaki)“)
  • auch die size() Implementierung würde ich weglassen, weil vorausgesetzt wird, dass die Größe nicht in einem Feld gespeichert wird
    (- die isEmpty() Implementierung würde ich ebenfalls weglassen, weil sie bei einer „ReverseList“ die worst-Case-Implementierung darstellt)*
    [/quote]
    Muss ich nochmal drüber überlegen. Unsere Klassen sind Iterables, so dass man zumindest von einem halbwegs effektiven Iterator ausgehen kann, was die Implementierungen jedenfalls nicht grauenhaft macht. Überschreiben kann man sie ja jederzeit.

Diese Heuristik hatte ich auch verwendet, ohne deinen Beitrag zuende gelesen zu haben, als ich mir den Code angesehen habe. Ich halte sie für sinnvoll, gerade weil die IDE einen ansonsten zu einer schlechten Implementierung verführt, weil es bereits eine (in diesem Fall schlechte) Implementierung gibt (z. B. isEmpty() mit einer „ReverseList“).
*Falls wir die Annahme machen wollen, dass auf das erste Element in konstanter Zeit zugegriffen werden kann (was wahrscheinlich gar nicht verkehrt ist, weil die Implementierungen ja iterierbar sind), könnten wir die isEmpty()-Implementierung drin lassen und eine headOpt()-Implementierung einfügen:

    return getOpt(0);
}```
Falls die getOpt()-Implementierung drin bleiben sollte, würde ich die headOpt()-Implementierung auf jeden Fall dazu nehmen.

Vielleicht ist selbst head schon zu implementations-spezifisch. Wir könnten auch einfach zwei Methoden einführen, die das „erste“ Element und den Rest liefern, ohne damit eine bestimmte Ordnung zu implizieren. Auch plus wäre dann unspezifisch, es macht einfach die Seq eins größer. Damit würde z.B. etwas analoges zu Hashset oder Treeset ein Seq sein können. Ich arbeite das mal aus.

*** Edit ***

package org.neco4j.collect;

import org.neco4j.tuple.Pair;

import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;

public interface Seq<A> extends Iterable<A> {

    //vergrößert die Seq um ein Element
    Seq<A> plus(A a);

    //verkleinert die Seq um ein Element
    Seq<A> minus();

    //gibt das Element zurück, das bei minus in der Seq fehlen würde
    A peek();

    default Pair<A, Seq<A>> chop() {
       return Pair.of(peek(), minus());
    }

    Seq<A> append(Seq<A> that);

    int size();

    boolean isEmpty();

    Seq<A> reverse();

    <B> Seq<B> map(Function<? super A, ? extends B> fn);

    <B> Seq<B> flatMap(Function<? super A, ? extends Iterable<B>> fn);

    Seq<A> filter(Predicate<? super A> predicate);

    default boolean all(Predicate<? super A> predicate) {
        for (A a : this) {
            if (!predicate.test(a)) {
                return false;
            }
        }
        return true;
    }

    default boolean any(Predicate<? super A> predicate) {
        for (A a : this) {
            if (predicate.test(a)) {
                return true;
            }
        }
        return false;
    }

    default <B> B foldLeft(B start, BiFunction<? super B, ? super A, ? extends B> fn) {
        B value = start;
        for (A a : this) {
            value = fn.apply(value, a);
        }
        return value;
    }

    default <B> B foldRight(BiFunction<? super A, ? super B, ? extends B> fn, B start) {
        B value = start;
        for (A a : this.reverse()) {
            value = fn.apply(a, value);
        }
        return value;
    }

}
47

Das war auch der Grund, weshalb ich die *-Passage eingeführt hatte. Eine „ReverseList“ macht als Implementierung daher keinen Sinn.
Die Idee, weiter zu verallgemeinern gefällt mir eigentlich ganz gut. Man kann damit auch FiFo- und LiFo-Queues abbilden. Allerdings besteht die Gefahr, dass der Code in dem eine Implementierung genutzt wird sich dann etwas merkwürdig liest, weil die Semantik des Interfaces zu unspezifisch ist. Erst bei der konkreten Implementierung wird die Semantik klar (es sei denn, wir fügen wie im Collections-Framework noch Zwischenschichten ein).