Warum Angst vor Abstraktionen mit komischen Namen?

[Landei]

Als Ausgangspunkt soll einmal dieses Zitat dienen:

Zitat: JavaCoda

	implicit def wrapToOps[T](x: T)(implicit monoid: AdditiveMonoid[T]): AdditiveMonoid[T]#Ops = new monoid.Ops(x) <ironie> Wow, Scala ist wahrlich ein Meilenstein für die Verständlichkeit und Nachvollziehbarkeit der Fachkonzepte aus dem Code </ironie>

Auf den Scala-Aspekt will ich hier nicht eingehen, das wurde schon im dortigen Thread gut beantwortet. Es ist aber auffallend, dass ausgerechnet ein Beispiel ausgewählt wurde, das den "furchteinflößenden" Begriff "Monoid" verwendet.

Das es gut ist, in seinem Code Strukturen zu entdecken, die sich verallgemeinern lassen, sollte eigentlich klar sein: Jede "entdeckte" Abstraktion ist eine Chance, wiederverwendbaren Code entweder zu schreiben oder zu nutzen.

Ein Monoid ist ein sehr einfaches Konzept: Wir haben eine assoziative Operation # (also a # (b # c) == (a # b) # c) ) mit einem neutralen Element e (dass bei Veknüpfung mit einem anderen Element dessen Wert nicht ändert). Monoide sind z.B. die natürlichen Zahlen bezüglich der Addition und Multiplikation, aber auch die Verkettung von Strings oder Listen(*). Hat man diese Abstraktion einmal erkannt, kann man z.B. eine List<T> zu einem einzelnen Wert T "eindampfen" (oder "falten"), egal welche Art von Monoid über T man benutzt. Eigentlich eine praktische Sache.

Also: Wieso lassen sich Programmierer so leicht von mathematisch angehauchten Namen abschrecken? Irgendwie muss man die Strukturen ja nennen, und es wäre Blödsinn, eine eigene Nomenklatur zu verwenden, wenn es schon eine allgemein akzeptierte, konsistente Benennung gibt. Wieso werden so schnell die Scheuklappen aufgesetzt, wenn ein Wort wie "Monoid", "Funktor", "Arrow" oder dreikreuzederherrseibeiuns "Monade" fällt?

(*) Mehr Beispiele: Monoid (Functional Java 3.0)

[schalentier]

Ich glaub es geht da weniger um das Wort "Monoid", als vielmehr um das Verstaendnis dieses Konstrukts. Ich hab mir das ne Weile angesehen, aber als Scala-Nicht-Kenner versteh ich ueberhaupt nicht was das sein soll und wozu es gut ist. Dieser Effekt, dass man einige Statements ohne tieferes Wissen ueber die Sprache auch nicht annaehernd verstehen kann, macht Scala in gewisser Weise einzigartig.

Und ich rede jetzt nicht von der Syntax oder der Formatierung (man kann auch Java so kryptisch schreiben, dass es niemand versteht), sondern von der Semantik.

Die andere Sache ist, dass der normale Entwickler wohl eher selten das Verlangen hat, einen neuen Monoiden zu programmieren. Meisten rechnet man mit Zahlen, iteriert ueber Listen und konkatiniert Strings. Mehr braucht man selten und damit fehlt auch das Verstaendnis, wieso man nun mit Scala ploetzlich mit Monoiden, Funktoren oder Faltungen rummachen muss.

[Landei]

Wie gesagt soll das hier keine Scala-Diskussion werden, deshalb nur soviel: Der obige Code ist ein typisches Beispiel für das Scala-Typklassen-Pattern. Hier ein praktisches Beispiel: Algorithmically challenged: Type Class pattern example

Zitat:

	...wieso man nun mit Scala ploetzlich mit Monoiden, Funktoren oder Faltungen rummachen muss.

Müssen muss niemand, auch in Scala nicht.

In Java werden sogar die einfachsten Abstraktionsmöglichkeiten verpasst: Wieso hat man List.size() , String.length() und array.length ? Wieso implementiert String nicht Iterable<Character> ? Wieso implementiert StringBuilder nicht List<Character> ? Die Liste ließe sich endlos fortführen. Das Problem ist, dass man einerseits zehn verschiedene Wege (oder Methodennamen) lernen muss, um prinzipiell das Gleiche zu tun, aber andererseits die vorhandenen Methoden deshalb nicht so flexibel sind, wie sie sein könnten. Bin ich der einzige, der das doof findet?

[Beni]

Ich möchte nicht, dass jede Klasse 20 Interfaces implementiert und 300 Methoden hat... Bei Eiffel wurde das so gemacht (ein Fenster ist ein Rectangle, und eine Liste von Componenten, und und und). Resultat: flexibel, aber so extrem unübersichtlich dass es praktisch nicht zu gebrauchen ist.

[ARadauer]

Zitat: Landei

	In Java werden sogar die einfachsten Abstraktionsmöglichkeiten verpasst: Wieso hat man List.size() , String.length() und array.length ? .... Das Problem ist, dass man einerseits zehn verschiedene Wege (oder Methodennamen) lernen muss...

size und length sind 2
Wie kommst du auf 10

[Marco13]

NEIN. Viele dieser Punkte sind mir auch schon aufgefallen. Ein Beispiel, das in die gleiche Kategorie fällt, sind StringBuilder und StringBuffer: Für ein paar 'synchronized's eine neue Klasse?!

Ich glaube auch, dass viele Leute sich lange über bestimmte Strukturen und Ansätze Gedanken machen. Dann kommen sie zu irgendeinem Ergebnis, und setzen es um. Aber ein ähnliches oder sogar besseres Ergebnis hätte man erreichen können, wenn man sich pragmatischer an die Vorgaben der rein mathematischen Beschreibung gehalten hätte. Mathematik ist eine Sprache für gute Beschreibungen, und anscheinend wird viel zu selten erkannt, dass die Algebra sie eigentliche formale Grundlage der Objektorientierten Programmierung ist.

Oder anders: Man muss vielleicht nicht die Definition von "Monoid" auswendig wissen (da könnte man gleich noch nach Gruppe, Ring und Körper fragen - darum geht es ja nicht) aber wer sich "Informatiker" schimpft, sollte schon wissen, dass das eine (einfache) algebraische Struktur ist - und wenn nicht, hat derjenige IMHO viel nachzuholen...

Ich fand z.B. sowas wie org.jscience.mathematics.structure (JScience 5.0-SNAPSHOT API) vom Ansatz her toll, aber erstens nicht konsequent und systematisch genug umgesetzt, und zweitens nicht so "mächtig", wie es sein könnte, wenn dieser Aspekt systematischer in der Standard-API berücksichtigt worden wäre.

Aber ich nehme an, dass dein Einwand sich nicht nur auf die existierenden, schon mathematisch definierten Strukturen an sich bezog, sondern, wie im Titel angedeutet, um allgemeine Abstraktionen - also die Definition eigener Algebren. Über ähnliche Aspekte hatte ich mir auch schon oft Gedanken gemacht. Und ich habe immer Angst, dass, wenn man mögliche Abstraktionen ausnutzt, der entstehende Code (primär von anderen) nicht mehr so gut nachvollzogen werden kann.

Man könnte sagen, dass ein weiterer Grundgedanke der OOP ja der ist, irgendwelchen Dingen Namen zu geben. Und wenn diese Namen wegen "zu viel Abstraktion" wegfallen, und jeder Typ nur noch eine lose Ansammlung von Mengen, Funktoren, Tupeln, Gruppen und Prädikaten ist, erleichtert das das Verständnis nicht unbedingt. Etwas pauschalisiert könnte man wohl sagen, dass es einen Trade-Off gibt, zwischen der Flexibilität und Allgemeingültigkeit, die die Mathematik an sich innehat, und der einfachen Verbindung zwischen Code und Objekten in der "realen" Welt.

Aber ich versuche zumindest eher in Richtung der allgemeineren Beschreibung zu gehen. Wenn jemand anderes das dann nicht mehr versteht... tja...

[Landei]

Zitat: ARadauer

	size und length sind 2 Wie kommst du auf 10

Das reicht auch schon. Ohne nachzuschlagen: Heißt es File.length() oder File.size() ? Heißt es javax.swing.text.Document.length() oder Document.size() ? Reingefallen, es ist Document.getLength() !

[spaghetti]

Zitat: Landei

	Das reicht auch schon. Ohne nachzuschlagen: Heißt es File.length() oder File.size() ? Heißt es javax.swing.text.Document.length() oder Document.size() ? Reingefallen, es ist Document.getLength() !

Document. + strg + space

[SlaterB]

und dann auch getSize() in ListModel

aber das ist kein rechter Angriffspunkt, das sind zum Teil separate Libraries, unabhängig von der Sprache,
oder nach Jahren von verschiedenen Programmierer-Generationen hinzugefügt,
dass dort nicht alles verregelt ist ist eine gewisse Entspannung,

es hilft nix, komplizierte Neuerungen haben es immer schwer

[Landei]

Zitat: SlaterB

	...aber das ist kein rechter Angriffspunkt, das sind zum Teil separate Libraries, unabhängig von der Sprache...

Ich finde es aber ärgerlich, wenn z.B. eine Bibliotheksklasse kein Iterable implementiert, wo das sinnvoll wäre. In Haskell würde eine Bibliothek, die Instanzen für wichtige Typklassen definieren könnte, das aber nicht tut, dafür mit Sicherheit kritisiert und u.U. nicht akzeptiert werden. Diese Einstellung fehlt mir bei den imperativen Sprachen.

Ein Grund dafür ist, ist, dass durch Implementierung bekannter Interfaces o.ä. auch leichter zu sehen ist, was eine Klasse tut. Wenn ich z.B. eine add-Methode habe, ändert sie dann das Objekt, oder liefert ein neues zurück? Und nein, das kann man nicht sofort am Rückgabewert sehen (man denke z.B. an StringBuilder.append ). Eine Abstraktion erfüllt also auch eine wichtige Dokumentations-Funktion.

[0x7F800000]

Nja, 'tschuldigung: ich wollte in dem Beispiel mit einer 0 anfangen, und alle Elemente einer Liste mit + addieren, dazu brauchte ich eben eine Struktur mit 0 und +, soll ich die jetzt "GridBagLayout" oder "Helmut" nennen, damit's vertrauter klingt?

Zitat: schalentier

	Ich glaub es geht da weniger um das Wort "Monoid", als vielmehr um das Verstaendnis dieses Konstrukts. Ich hab mir das ne Weile angesehen, aber als Scala-Nicht-Kenner versteh ich ueberhaupt nicht was das sein soll und wozu es gut ist.

Ich find's wirklich so lustig: wenn zB. bei Python fürchterliche Innereien in C/C++ geschrieben, und dann mit dem Python-Brei übergossen werden, dann sagen alle: "oooh hat das eine schöne Syntax", und kein Mensch beschwert sich über die fürchterlichen Innereien, und darüber, dass man mit der Sprache an sich eigentlich nichts anstellen kann, außer irgendwelche Altlasten aufzuhübschen.

Kaum entwirft jemand eine Sprache, wo sowohl die fürchterlichen Bibliothek-Innereien, als auch die benutzerfreundlichen DSL's implementiert werden können, geht das Geheule los, es sei doch "Alles so kompliziert!", und "Wie soll ich denn bloß nach Mallorca fliegen, ohne eine Flugzeugturbine zusammenbauen zu können?!". Scala vereint alles: es ist gut für die Benutzer der Bibliotheken, und es ist gut für die Designer der Bibliotheken. Wenn man sich als Benutzer versteht, dann sollte man sich aus dem Design der Bibliotheken einfach erstmal raushalten. Oder es einfach lernen: es ist nämlich ein riesen Spaß.

Zitat:

	Die andere Sache ist, dass der normale Entwickler wohl eher selten das Verlangen hat, einen neuen Monoiden zu programmieren. Meisten rechnet man mit Zahlen, iteriert ueber Listen und konkatiniert Strings. Mehr braucht man selten und damit fehlt auch das Verstaendnis, wieso man nun mit Scala ploetzlich mit Monoiden, Funktoren oder Faltungen rummachen muss.

"Normaler Entwickler" muss über alle Äpfel im virtuellen Einkaufskorb gehen, und den float-Preis der Äpfel aufaddieren, und ist dann glücklich. Okay. Ich mag auch online-Shops und konsumiere gerne Äpfel, und bin den "normalen Entwicklern" außerordentlich dankbar, wenn der Preis am Ende korrekt berechnet ist. Ich muss aber mit doubles, floats, rationalen Zahlen, konstruierbaren zahlen, Galois-Feldern, p-Adischen Zahlen, komplexen Zahlen, Cayley-Zahlen, Oktonionen, elliptischen Kurven, tropischen Ringen, algebraischen Körpererweiterungen, Ganzheitsringen, inversen Limiten von Idealen, Polynomen, Multivariaten Polynomen, Reihen, Multivariaten Reihen, Matrizen von dem ganzen Kram, allgemeinen Linearen Operatoren zwischen dem ganzen Kram, Computertomographie-Phantomen, Masse- oder Ladungsdichten, Zufallsvariablen, Stochastischen Prozessen, Maßen, sowie natürlich allen möglichen Datenstrukturen von all dem rechnen können, und ich will stets hingehen und

sum(seq)

hinschreiben können, und zwar OHNE hundert mal die sum(seq) -methode neuimplementieren zu müssen. Und da fängt man schon an, sich Gedanken über die richtige Abstraktionen zu machen.

Zitat: Beni

	Ich möchte nicht, dass jede Klasse 20 Interfaces implementiert und 300 Methoden hat...

Warum nicht? Das ist doch Frage der Dokumentation, nicht die Frage der zu komplexen Syntax. Ist es denn besser, die 300 methoden jedes mal neu zu implementieren?

Zitat: Marco13

	Aber ein ähnliches oder sogar besseres Ergebnis hätte man erreichen können, wenn man sich pragmatischer an die Vorgaben der rein mathematischen Beschreibung gehalten hätte. Mathematik ist eine Sprache für gute Beschreibungen, und anscheinend wird viel zu selten erkannt, dass die Algebra sie eigentliche formale Grundlage der Objektorientierten Programmierung ist. [...] Ich fand z.B. sowas wie org.jscience.mathematics.structure (JScience 5.0-SNAPSHOT API) vom Ansatz her toll

Was die Anwendung der mathematischen Definitionen bei der Programmierung angeht, ist Vorsicht geboten. Ich habe schon mehrmals versucht, eine Bibliothek (in Scala) aufzubauen, indem ich mir einfach nur ein dickes Algebra-Buch genommen habe, und einfach alle Strukturen nacheinander als Traits skolemisiert habe. Es ist sowas wie in dem Link angedeutet herausgekommen, allerdings nicht mit 8 Interfaces, sondern mit ~60 Traits. Es war nicht wirklich praktisch, aus folgenden Gründen:

1) In der Mathematik rechnet man oft mit Objekten herum, von den anfangs nicht ganz klar ist, welche Struktur sie eigentlich tragen: ist beispielsweise Z/(8220625327)Z ein Körper, oder lediglich ein Ring mit Nullteilern? Soll man elemente solchen Dings als "Ring" oder "Field" initialisieren, um damit rumzurechnen? Während man damit rumrechnet, führt man gerne (beweisbar gültige) Teilungen durch, auch wenn man im Ring ist, also müsste das Ring-interface eigentlich auch inverse beinhalten, aber wodurch unterscheiden sich dann Ringe von Körpern bei der Implementierung?

2) Um irgendwelche strukturierten Teilmengen zu erkennen, ist das Typsystem nicht mächtig genug. Beispielsweise bilden invertierbere quadratische Matrizen gleicher Größe eine wunderbare Gruppe, aber allgemeine matrizen kann man nicht mal vernünftig multiplizieren: krampfhafte Versuche, da irgendeine mathematisch korrekt definierte Struktur drüberzuziehen sehen nicht gut aus.

3) Hirnlose Skolemisierung der mathematischen Definitionen führt nicht zu brauchbaren schnittstellen. Beispiel Graphen: Mathematisch ist ein Graph G = (V, E) eine menge von Knoten blah blah blah... Es ist aber schwachsinnig, das ganze wie folgt zu einem interface zu machen:

interface Graph[V, E]{
  Collection[V] getNodes()
  Collection[E] getedges()
}

Denn Graphen (auch wenn sie im mathematischen Sinne endlich sind usw.) müssen überhaupt nicht in den Speicher reinpassen, und müssen all ihre Knoten nicht kennen: man denke an riesige backtracking-Bäume oder Webcrawler. Das Interface, welches für einen Wegsuch-algo sinn macht, sieht in diesem fall völlig anders aus, als die mathematisch einwandfreie, aber unbrauchbare Skolemisierung.

Man muss da also schon mit viel Gefühl rangehen, wie genau versuche ich herauszufinden.

[schalentier]

Zitat: 0x7F800000

	Ich muss aber mit doubles, floats, rationalen Zahlen, konstruierbaren zahlen, Galois-Feldern, p-Adischen Zahlen, komplexen Zahlen, Cayley-Zahlen, Oktonionen, elliptischen Kurven, tropischen Ringen, algebraischen Körpererweiterungen, Ganzheitsringen, inversen Limiten von Idealen, Polynomen von dem ganzen Kram, Multivariaten Polynomen von dem ganzen Kram, Reihen von den ganzen Kram, Multivariaten Reihen von dem ganzen Kram, Matrizen von dem ganzen Kram, allgemeinen Linearen Operatoren zwischen dem ganzen Kram, Computertomographie-Phantomen, Masse- oder Ladungsdichten, Zufallsvariablen, Stochastischen Prozessen, Maßen, sowie natürlich allen möglichen Datenstrukturen von all dem rechnen können, und ich will stets hingehen und sum(seq) hinschreiben können, und zwar OHNE hundert mal die sum(seq) -methode neuimplementieren zu müssen. Und da fängt man schon an, sich Gedanken über die richtige Abstraktionen zu machen.

Auch wenn mir vieles davon nix sagt, hast du schonmal versucht dein Problem mit einer Sprache ohne statisches Typsystem umzusetzen? Deine sum(seq) Methode saehe in Ruby z.B. so aus:

def sum(initial_value, seq)
  seq.inject(initial_value) do |result, s|
    result + s
  end
end

Das klappt dann fuer alle Listen, Arrays, Enumerations, etc. mit Objekten drin, die die Methode "+" implementiert haben. Nur so ne fixe Idee...

[Landei]

Geht bestimmt, ist aber für ernsthafte numerische Aufgaben zu langsam. Scala hätte als Äquivalent strukturelle Typen anzubieten ("für alle Typen, die eine Methode foo(Bar) haben, tue...", siehe Pimp my Library eSCALAtion Blog ), die aber auch nicht gerade für ihre Performance berühmt sind.

[0x7F800000]

Zitat: schalentier

	Auch wenn mir vieles davon nix sagt, hast du schonmal versucht dein Problem mit einer Sprache ohne statisches Typsystem umzusetzen? Deine sum(seq) Methode saehe in Ruby z.B. so aus: def sum(initial_value, seq) seq.inject(initial_value) do |result, s| result + s end end Das klappt dann fuer alle Listen, Arrays, Enumerations, etc. mit Objekten drin, die die Methode "+" implementiert haben. Nur so ne fixe Idee...

1) Klassisches Argument gegen Duck-Typing: man merkt erst zur Laufzeit, dass irgendwas schief gelaufen ist. In diesem konkreten Fall könnte ich mir beispielsweise vorstellen, dass schon sehr bald mehrere Benutzer sich über folgendes seltsames Verhalten wundern könnten:

sum([[1,2,3],[4,5,6],[7,8,9]]) //liefert [1,2,3,[4,5,6],[7,8,9]] statt [12,15,18]

Hier will man 3 listen in einer liste komponentenweise addieren. Eine Liste könnte nun "+" implementieren, allerdings nicht das "+" einer Additiven Gruppe, sondern ein "+" zum hinzufügen der Elemente, was dazu führen könnte, dass die nachfolgenden listen als elemente angehängt werden. Die fehlermedung würde dann vielleicht hundert zeilen später auftauchen, wenn man versucht, den mittelwert solch einer liste auszurechnen o.ä. Ich bin mir ziemlich sicher, dass Python sowas abfangen sollte, bei Ruby weiß ich es nicht. Ich kenne allerdings genug jämmerlich zusammengeschusterte Skript-Sprachen, die sich ungefähr so bescheuert benehmen würden.

2) das "klassische OOP" strebte ursprünglich danach, daten und methoden zu vereinen. Das macht aber nicht immer unbedingt Sinn. Ich möchte vielleicht mit Double-daten rumrechnen, aber einmal mit der üblichen Körperstruktur, und anderes mal wie in einem tropischen ring mit Operationen (max, +) statt (+, *). Eher denkbar: man möchte mit longs rumrechnen, allerdings nicht mit üblichen Z/(2^64)Z-Ring, sondern in einem Z/pZ-Körper. Da man nur bei statisch typisierten Sprachen so etwas wie implizite paremeter übergeben kann (bei dynamisch typisierten weiß der kompiler ja nicht, was verlangt ist), müsste man die Struktur explizit übergeben. Das mag bei so einfachen methode gehen, wird aber bei komplizierteren aufgaben mir 2-3 Strukturen auf Dauer evtl. stressig.

3) Für mich eigentlich das wichtigste: dank der statischen Typisierung kann man den scala-compiler dazu zwingen, aus einfachen Formeln komplizierte Algorithmen zur compile-zeit zusammenzubauen. Beispiel: Seien A, B, C, D... matrizen
Wenn man sowas schreibt:

val C = A * B
val Z = C * D

dann stellt man beim genauen hinschauen fest, dass man anhand der ersten zeile allein nicht feststellen kann, ob die matrix C in row-major, col-major, oder im gehashten-Assemblier-Zustand vorhanden sein muss. Man muss also Auswertung von C auf später verschieben. Nun wird in der zweiten Zeile C an (sagen wir mal dichte) matrix D dranmultipliziert, jetzt ist klar: C muss in rowMajor gespeichert werden, damit die zeilen/spalten korrekt in den Cache reinpassen und nicht umkopiert werden müssen. Doch wie wertet man das aus? Haufen if-Abfragen bei jeder Multiplikation? Könnte man machen, aber scala-compiler erledigt das schon zur Kompilezeit, und zwar indem es mithilfe von impliciten casts die zweite Zeile zu sowas wie

val Z = evalInRowMajor(C)*convertToColMajor(D)

umbaut. Der Compiler wählt mir anhand harmlos aussehenden Formeln also die passenden Algorithmen. Das gibt's imho bei gar keiner anderen Sprache, nicht mal bei C/C++ oder Java.

Das fehlen dieser Fähigkeit merkt man schon bei deinem Beispiel: bei deiner version muss man den startwert mit übergeben, weil der compiler eben die Lücken mit dem passenden Struktur nicht ausfüllen kann.

4) [EDIT] Ok, Performance habe ich hier gar nicht erwähnt: klar, um etwas bei diesen ganzen Skriptsprachen schnell zu machen, muss man es in C/C++ schreiben. Wenn ich den s***** eh in C/C++ schreiben muss, wozu brauch ich dann die blöden Skriptsprachen überhaupt?

[Marco13]

Zitat: 0x7F800000

	Was die Anwendung der mathematischen Definitionen bei der Programmierung angeht, ist Vorsicht geboten. Ich habe schon mehrmals versucht, eine Bibliothek (in Scala) aufzubauen, indem ich mir einfach nur ein dickes Algebra-Buch genommen habe, und einfach alle Strukturen nacheinander als Traits skolemisiert habe. Es ist sowas wie in dem Link angedeutet herausgekommen, allerdings nicht mit 8 Interfaces, sondern mit ~60 Traits. Es war nicht wirklich praktisch, aus folgenden Gründen: 1) In der Mathematik rechnet man oft mit Objekten herum, von den anfangs nicht ganz klar ist, welche Struktur sie eigentlich tragen: ist beispielsweise Z/(8220625327)Z ein Körper, oder lediglich ein Ring mit Nullteilern? Soll man elemente solchen Dings als "Ring" oder "Field" initialisieren, um damit rumzurechnen? Während man damit rumrechnet, führt man gerne (beweisbar gültige) Teilungen durch, auch wenn man im Ring ist, also müsste das Ring-interface eigentlich auch inverse beinhalten, aber wodurch unterscheiden sich dann Ringe von Körpern bei der Implementierung? 2) Um irgendwelche strukturierten Teilmengen zu erkennen, ist das Typsystem nicht mächtig genug. Beispielsweise bilden invertierbere quadratische Matrizen gleicher Größe eine wunderbare Gruppe, aber allgemeine matrizen kann man nicht mal vernünftig multiplizieren: krampfhafte Versuche, da irgendeine mathematisch korrekt definierte Struktur drüberzuziehen sehen nicht gut aus. 3) Hirnlose Skolemisierung der mathematischen Definitionen führt nicht zu brauchbaren schnittstellen. Beispiel Graphen: Mathematisch ist ein Graph G = (V, E) eine menge von Knoten blah blah blah... Es ist aber schwachsinnig, das ganze wie folgt zu einem interface zu machen: interface Graph[V, E]{ Collection[V] getNodes() Collection[E] getedges() } Denn Graphen (auch wenn sie im mathematischen Sinne endlich sind usw.) müssen überhaupt nicht in den Speicher reinpassen, und müssen all ihre Knoten nicht kennen: man denke an riesige backtracking-Bäume oder Webcrawler. Das Interface, welches für einen Wegsuch-algo sinn macht, sieht in diesem fall völlig anders aus, als die mathematisch einwandfreie, aber unbrauchbare Skolemisierung. Man muss da also schon mit viel Gefühl rangehen, wie genau versuche ich herauszufinden.

Ich gehe davon aus, dass es keinen Sinn machen würde, eine Programmiersprache 1:1 auf Mathematischen Strukturen auzubauen. Schon allein weil viele Konstrukte zu speziell sind, und wenig wirklich "praktische" Awendungsbereiche haben. Zugegeben, ich hatte schonmal was ähnliches in Erwägung gezogen, wie du: Hierarchie mathematischer Strukturen ? Wikipedia und los geht's Es geht ja nicht um ein Computeralgebrasystem, das genau für solche Dinge da ist, sondern nur darum, existierende Strukturen auszunutzen. Und mit Monioden, Gruppen, Ringen und Körpern hat man schon den überwiegendsten Teil davon abgedeckt - die Herausforderung würde dann nicht darin bestehen, auch ja unbedingt noch den Quasikörper und den Integritätsbereich einzubauen, oder zu Erkennen, dass diese-und-jene Struktur mit einer zusätzlichen 'null' nun zu dieser-und-jender Struktur wird, sondern darum, diese wenigen, wichtigen Strukturen konsequent und gut (d.h. "viele Vorteile bringend") umzusetzen.

Das Beispiel des Graphen ist aber schon fast klassisch, und darüber (und einige andere Aspekte, die hier im Thread diskutiert werden - deswegen ist dieser Backlink vielleicht sogar ganz praktisch) hatte ich schon philosophiert, als ich den durch immer weiter gehende (speziell auch mathematische) Abstraktion drohenden Abstraktions-Overkill mal angesprochen hatte. Ich fände, dass es durchaus einen Haufen Vorteile hätte, einen Graphen als
Tuple<Set<Object>, Set<Tuple<Object,Object>>> g;
zu beschreiben. Aber wenn das jemand sieht, der... (neutral formuliert) "eine andere Einstellung zu solchen Dingen" hat, und entweder das verwenden kann, oder stattdessen
Graph g;
schreiben kann, wird er sich tendenziell eher für letzteres entscheiden.

Leicht OT, weil ganz spezifisch darauf bezogen: Was wäre an dem angedeuteten Interface denn so "falsch" oder "unbrauchbar"? Abgesehen davon, dass man Set#size u.U. recht schwer implementieren kann, hat man durch die Interface an sich ja immernoch die Möglichkeit, dort vieles z.B. "lazy" zu implementieren, und sinngemäß einen Iterator beim Aufruf von "next" halt eine Webseite aufrufen zu lassen (rein theoretisch). Anders formuliert: "Ein Graph IST EIN Tupel aus einer Menge von Knoten und einer Menge von Kanten..." - wenn man etwas anderes implementiert, dann IST das - polemisch formuliert - eben kein Graph mehr....

[0x7F800000]

Zitat: Marco13

	Ich gehe davon aus, dass es keinen Sinn machen würde, eine Programmiersprache 1:1 auf Mathematischen Strukturen auzubauen.

Nein, denselben Satz von mathematischen Konstrukten, wie in der theoretischen Mathematik zu nehmen, und zu versuchen, das alles in API reinzuquetschen, würde keinen Sinn machen, weil Rechner einfach nicht so funktionieren, wie der unbegrenzte mathematische Kosmos. Rechner haben nun mal endlichen Speicher, endliche Geschwindigkeit, es gibt Haufenweise wohldefinierte aber unberechenbare Funktionen, Rechner können keine Instanzen aus nicht konstruktiven Existenzbeweisen herbeizaubern usw usw...

Zitat:

	... unbedingt noch den Quasikörper und den Integritätsbereich einzubauen ...

Weiß nicht... Aus Integritätsbereichen kann man eigentlich ganz gut Quotientenkörper bauen, und mit Quotientenkörpern kann man tolle LGS lösen usw. Zum Beispiel kann man aus euklidischen Polynomringen den Körper der rationalen Funktionen erzeugen, und damit ganz gut rumrechnen, auch wenn's nicht das schnellste ist... Integritätsbereiche sind gar nicht so abwegig

Zitat:

	Ich fände, dass es durchaus einen Haufen Vorteile hätte, einen Graphen als Tuple<Set<Object>, Set<Tuple<Object,Object>>> g; zu beschreiben. Aber wenn das jemand sieht, der... (neutral formuliert) "eine andere Einstellung zu solchen Dingen" hat, und entweder das verwenden kann, oder stattdessen Graph g; schreiben kann, wird er sich tendenziell eher für letzteres entscheiden.

Nja, was soll daran schlecht sein:

type Graph[V] = (Set[V], Set[(V, V)])

beides muss sich ja nicht ausschließen, vorausgesetzt die Syntax macht mit

Allgemein bei Interfaces muss man irgendwie darauf achten, dass man nicht ins unendlich abstrakte & völlig unbrauchbare abdriftet. Ich bemühe mich deshalb darum, bei Traits das richtige Gleichgewicht zwischen vorgeschriebenen Methoden und gebotener Funktionalität zu halten. Einfach nur Tausend Interfaces zu liefern, an die sich der Benutzer zu halten hat, ohne dass es ihm was nützt, ist zum Scheitern verurteilt, auch wenn diese ganzen Interfaces aus algebraischer Sicht sauber definiert sind.

Zitat:

	Leicht OT, weil ganz spezifisch darauf bezogen: Was wäre an dem angedeuteten Interface denn so "falsch" oder "unbrauchbar"?

naja, um Breitensuche, Tiefensuche (in allen Varianten), kürzeste Wege-Algos, aufzählung der Zusammenhangskomponente eines Knoten, aufzählung der d-entfernten Nachbarschaft, test ob ein anderer knoten erreichbar ist usw: diese ganzen Algorithmen funktionieren bestens mit sehr lokaler Information, sie müssen eigentlich immer nur einen einzelnen Knoten sehen, und zu seinen Nachbarn springen können. Alle Knoten und Kanten zu sehen ist nicht nötig (und oft nicht möglich, auch wenn's theoretisch endlich viele sind). Und es gibt in der Praxis eben sehr viele Fälle, wo man gerne graphenalgos einsetzen würde, ohne jemals alle Knoten aufzählen zu können:
1) tankstelle in der Nähe suchen, ohne die ganze Weltkarte runterzuladen
2) kliquen im engen Freundeskreis bei facebook suchen, ohne ganzes facebook runterzuladen
3) backtrackings aller art auf fürchterlich großen Graphen (es gibt sehr viele Graphen, die zeitlich in unsere 4D-Welt gut reinpassen, aber niemals zur selben Zeit im Speicher Platz finden können)
4) Untergruppen-zugehörigkeits probleme, Rubic's cube lösen o.ä...

bei all diesen problemen macht es keinen Sinn, die Aufzählung aller Knoten zu verlangen. Natürlich gibt es Graphen, die alle ihre Knoten kennen und Algorithmen, die das brauchen. Aber das ist dann schon ein speziellerer Unter-Trait.

Auf den Punkt gebracht:

mathematische Definition abschreiben != die algorithmisch entscheidenenden Eigenschaften erkennen

Zum schreiben der Beweise benötigt man das erstere.
Zum schreiben des Codes benötigt man das letztere.

[Marco13]

OK, zugegeben, die Frage was daran "unbrauchbar" ist, war ein bißchen rethorisch Tatsächlich braucht man die reine Aufzählung der Knoten nicht oder selten. (Auch wenn, nur weil dort "Set<V>" steht, das ja nicht heißen muss, dass die Knoten ALLE im Speicher liegen - es kann ja eine quasi-implizite Beschreibung der Knoten sein).

Aber es stimmt schon: Die ALLERmeisten Graphenalgorithmen brauchen massivst genau eine Funktion, nämlich: "Gibt mir alle Kanten, die an dem Knoten hängen" (Die Differenzierung zwischen ein- und ausgehenden Kanten, oder die darauf aufbauend in gleicher asymptotischer Zeit zu erreichender Suche nach allen Nachbarn mal außen vor gelassen). Für praktische Zwecke braucht man also IMMER noch eine Methode wie
Iterable<Edge> getEdges(Vertex v);
Sowas schreibt sich sowohl steng mathematisch als auch in einem Graph-Interface (zumindest in der naivsten Form) recht leicht hin - sei jetzt mal egal, ob mit "Edge" oder "Tuple<V,V>". Es ist aber nicht inheränter Teil der Definition eines Graphen. Es kann theoretisch auf Basis des Graphen in seiner angedeuteten, minimalistisch-abstraktesten Form leicht berechnet werden: Über alle Kanten gehen, und schauen, ob 'v' einer der Endpunkte ist - mit einer einfachen Utility-Methode. Und es müßte rein strukturell deswegen nicht Teil eines Graph-Interfaces sein, sondern wird nur aus Effizienzgründen mit dort aufgenommen. Warum? Weil der Graph eben üblicherweise sowas wie eine Map<Vertex, List<Edge>> speichert, in der diese Information leicht nachgesehen werden kann. Und das ist ... doch eigentlich nur eine Funktion, die Vertices auf Listen von Edges abbildet. Eigentlich wäre es doch schön, wenn man diese Information dann nicht als höchst-spezifische Methode in einer höchst-spezifischen Graph-Klasse beschreiben würde, sondern eben genau als
Function<V, Set<Tuple<V,V>>> edgesOfVertices;
Damit könnte man all die magischen Sachen machen, z.B. diese Funktion auf triviale Weise zu einer Funktion erweitern, die einen Knoten auf seinen Grad abbildet, oder auf die Menge seiner Nachbarknoten - alles Dinge, die oft praktisch sind, und durch so ein Konstrukt, dank der Abstraktion, "aus dem (fast) nichts heraus" von ganz alleine bekommt.

Aber das führt dann, konsequent weitergedacht, eben zum angedeuteten Overkill, wo man nur noch mit Sets, Tuples und Functions rumhantiert, und durch reines Lesen nicht mehr erkennbar ist, ob ein Programm eine rohe Breitensuche in einem Graphen durchführt oder die Bestellannahme eines Pizzaservices regelt Wie im anderen Thread (und oben) schon angedeutet geht damit ja eine der Kernideen von OOP verloren, nämlich dass Strukturen sprechende (und vereinfacht gesagt: aus der realen Welt stammende) Namen haben. Ich denke, speziell bei sowas abstrakt-mathematischem wie Graphen ist das nicht so schlimm, und die Vorteile überwiegen deutlich, zumal um die allgemeinen Strukturen ja immernoch spezifischere Business-Strukturen drumrumgewickelt werden können... aber es ging ja ursprünglich um die allgemeine Frage, wie viel Abstraktion man einem Programmierer zumuten oder abverlangen kann

Meine ersten Gehversuche in Scala waren übrigens ... der Versuch, einer Graph-Klasse weil ich dachte, dass es erstens eine tolle Übung wäre, und zweitens sowas damit ja aus den angedeuteten Gründen und in der angedeuteten Form total cool und allgemein umsetzbar sein müßte - und ich bin kläglich gescheitert ... da braucht's wohl viel, viel mehr Übung und Versiertheit, um da etwas in diesem Sinne vernünftiges machen zu können...

[0x7F800000]

Zitat: Marco13

	Aber es stimmt schon: Die ALLERmeisten Graphenalgorithmen brauchen massivst genau eine Funktion, nämlich: "Gibt mir alle Kanten, die an dem Knoten hängen"

so ist es.

Zitat:

	Es ist aber nicht inheränter Teil der Definition eines Graphen.

Doch, man kann (auch gerichteten) Graphen G als eine Funktion f: V -> 2^V definieren (rechts steht die Potenzmenge), das wird dann völlig äquivalent zu der anderen Definition, nur eben wesentlich schöner für die Implementierung.

Zitat:

	Und das ist ... doch eigentlich nur eine Funktion, die Vertices auf Listen von Edges abbildet.

jaaa...?

Zitat:

	Eigentlich wäre es doch schön, wenn man diese Information dann nicht als höchst-spezifische Methode in einer höchst-spezifischen Graph-Klasse beschreiben würde, sondern eben genau als Function<V, Set<Tuple<V,V>>> edgesOfVertices;

Was heißt "höchst spezifisch"? Eine solcher Graph-Trait hätte doch eben nur eine abstrakte methode (und dann vielleicht noch sowas wie einen "Startknoten" oder Menge von Startknoten, wo man irgendwelche Suchen anfangen kann) so irgendwie:

trait Graph[V]{
  // abstrakt
  def neighbors(x: V): Iterable[V]

  // das evtl überschreiben
  def sccRepresentants: Iterable[V] = new Set[V]()

  // alles andere lässt sich ja durch abstrakte methoden ausdrücken
  def degree(x: V) = neighbors(x).size

  // ... 150 weitere nützliche methoden, etwa:
  // search(start, predicate):X
  // aStar(heuristic, predicate):X
  // bfs(x, predicate)
  // ...
}

Wenn man sowas aus Funktion basteln möchte, bitte sehr:

implicit def functionToGraph[V](f: V => Iterable[V]) = new Graph[V]{
  def neighbors(x: V) = f(x)
}

Wenn man die neighbors Funktion aus dem graphen heraustrennen möchte, bitte sehr:

val nodes = List("Marco13", "Landei", "L-ectron-X")
val firstNeighbors = for(n <- nodes) yield g.neighbors(name).head

val separateFunction = (s: String) => g.neighbors(s)

Wo ist das Problem?

Zitat:

	Damit könnte man all die magischen Sachen machen, z.B. diese Funktion auf triviale Weise zu einer Funktion erweitern, die einen Knoten auf seinen Grad abbildet, oder auf die Menge seiner Nachbarknoten - alles Dinge, die oft praktisch sind, und durch so ein Konstrukt, dank der Abstraktion, "aus dem (fast) nichts heraus" von ganz alleine bekommt.

Nja, aber einen ziemlich fetten Graph-Trait bekommt man eben auch durch implementierung von gerade mal einer einzigen Methode, und schon kann man damit Wegsuche machen und sonst was anstellen... Wozu soll man das denn als kryptische Function[Blah, Blah]-Dinger implementieren und die funktionalität irgendwo verstreuen?

Zitat:

	Aber das führt dann, konsequent weitergedacht, eben zum angedeuteten Overkill, wo man nur noch mit Sets, Tuples und Functions rumhantiert, und durch reines Lesen nicht mehr erkennbar ist, ob ein Programm eine rohe Breitensuche in einem Graphen durchführt oder die Bestellannahme eines Pizzaservices regelt

Warum? Man bastle eben ein recht abstraktes Graph Trait, und verwende es dann in der Pizza-Service. Alles benannt, alles klar, alles toll.

Weißt Du was, irgendwie habe ich das Gefühl, als ob du durch das Fehlen der higher-order-functions und closures in Java zu irgendwelchen merkwürdigen Workarounds abdriften würdest, als ob du geistig schon in einer funktionalen Sprache denken, aber physisch noch in Java coden würdest

Vor dem Umstieg auf Scala ging es mir so: ich habe plötzlich angefangen, haufenweise Klassen wie "Tuple, Pair, Function, LazyMappedSequence, MappedFunction" usw. in java zu implementieren und sie an jeder Stelle zu benutzen, bis mir aufgefallen ist, dass ich eigentlich kein Java mehr schreibe, sondern lediglich java-syntax zur simulation einer funktionalen Sprache missbrauche

[EDIT] *im tagebuch rumblätter*
Genau habe ich damals folgende Hilfsmittel in Java implementiert:
MapFunction, MappedIterable, MultiIterable, EmptyIterator, MappedIterator, MultiIterator, Function, Identity, Inclusion, Memoization, Pair, Square, VisitorProcess, IntRange, LongRange, LongCounter...

also lauter so Sachen, die irgendwie Funktionales Programmieren imitieren sollten

[Marco13]

Dass es verschiedene äquivalente mathematische Beschreibungen geben kann, die bei "direkt-naiver" Umsetzung unterschiedlich gut implementieren lassen (oder auch abhängig von der Art des Graphen unterschiedlich effizient sind - z.B. bei "dünn besetzen" Graphen vs. vollständige Grapen) kommt zu dem ganzen noch dazu. Aber mit Interfaces und abstrakten Beschreibungen hält man sich für die Implementierung ja zum Glück gerade diese Türen so lange wie möglich offen.

Zitat: 0x7F800000

	Was heißt "höchst spezifisch"? ... Wenn man sowas aus Funktion basteln möchte, bitte sehr: ... Wenn man die neighbors Funktion aus dem graphen heraustrennen möchte, bitte sehr: ... Wo ist das Problem?

Die erste Richtung geht mit Java genauso einfach. Die zweite kann (mit Java, und wohl auch mit Scala) etwas komplizierter sein, je nachdem, wie viele weitere abstrakte Methoden jemand unüberlegterweise(?) in dieses Interface mit reingepackt hat. Natürlich hat man meistens noch diese Option des "Einwickelns". Man kann auch bei

1
2
3
4
class Graph {
    int getNumVertices() { ... }
    Vertex getVertex(int i) { ... }
}

daraus eine "List<Vertex>" machen: AbstractList erweitern, und die 1,2 abstrakten Methoden auf die beiden vorhandenen umbiegen und gut. Aber ich hätte einen Vorteil der allgemeinen Beschreibung (GROB im Sinne von

1
2
3
class Graph {
    Collection<Vertex> getVertices(){ ... }
}

oder gar das schon angedeutete Tuple<Collection<Vertex>, ...>, an dem man gar nicht mehr sieht, dass es ein Graph ist!) eben darin gesehen, dass man dieses Einwickeln und Umbiegen gar nicht mehr braucht.

Zitat:

	Weißt Du was, irgendwie habe ich das Gefühl, als ob du ... geistig schon in einer funktionalen Sprache denken, aber physisch noch in Java coden würdest

Genau das Gefühl habe ich auch Ich will und brauche mehr funktionale Aspekte, und merke selbst, dass ich tendenziell immer häufiger anonyme Implementierungen einzelner Interfaces für solche "Umbiege-Operationen" verwende. Eigentlich hatte ich gehofft, dass das bei Scala weniger notwendig sein könnte, aber deinen Ausführungen nach scheint es lediglich besser... "antizipiert" zu sein Ich finde den Einstieg in Scala trotzdem schwer... (mal schauen, was in Yes, Scala is hard so neues steht ). Hatte auch schonmal Goovy ins Auge gefasst. Dazu kommt , dass ich gerne von anfang an etwas sinnvolles machen würde, man aber vermutlich sicher sein kann, dass man von allem, was man anfangs in Scala schreibt, wenige Monate später erkennt, was für ein crap es eigentlich war Die zur Verfügung stehenden Mittel gut zu nutzen erfordert so viel Übung, dass vorher erstmal viel Zeit vermeintlich verbrannt wird...

[nillehammer]

Zitat: Marco13

	Dazu kommt , dass ich gerne von anfang an etwas sinnvolles machen würde, man aber vermutlich sicher sein kann, dass man von allem, was man anfangs in Scala schreibt, wenige Monate später erkennt, was für ein crap es eigentlich war Die zur Verfügung stehenden Mittel gut zu nutzen erfordert so viel Übung, dass vorher erstmal viel Zeit vermeintlich verbrannt wird...

Das Gefühl hab ich auch, wenn ich mir meinen Java-Code von früher anschaue... was sag ich, das Gefühl hab ich, wenn ich mir meinen Java-Code von vor ein paar Monaten anschaue! Man sollte meinen, dass ich es nach 7 Jahren endlich kann. Ist aber nicht so... Egal, ich bin trotzdem ein super Programmierer!