EDIT: Abgetrennt aus dem Java-Quiz-Thread: Eine Diskussion, die sich aus http://forum.byte-welt.net/threads/4929-Java-Quiz/page8?p=74105&viewfull=1#post74105 ergeben hat
Wie wäre es mit ein bisschen Graphentheorie? Wenn du Generics als „zusammengesetzten“ Datentyp ansiehst, dann dürfte sich das doch auflösen.
Öm… das ändert nichts daran, dass es unendlich viele supertypen gibt, und ich eine Entscheidung treffen muss, bis zu welcher “Tiefe” die angegeben werden sollen. Und das ist nicht so einfach: Wenn es einen unendlichen Typen “A<B<A<B<…>>>>” gibt, soll dann “A” ausgegeben werden, oder “A<B>” …? Und was ist bei mehreren Typparametern, wo vielleicht einer bei einer anderen Tiefe “unendlich wird” als ein anderer? :verzweifel: Wah, ich habe mich entweder zu viel oder zu wenig mit Typen beschäftigt, das ist echt mind-fucking :sick: (Eigentlich sollte das nur eine kleine Typ-Utility-Lib für ein anderes Projekt werden, aber … man beißt sich halt so fest :rolleyes: )
Das ist richtig, allerdings ist der Graph beschränkt. Und mittels Graphentheorie kannst du ja Zyklen feststellen. Allerdings kenne ich deinen Anwendungsfall ja nicht, daher kann das auch in die komplett falsche Richtung gehen.
Ich sag ja, ich kenne deinen Anwendungsfall nicht 
Die Menge wirst du schwerlich in endlicher Zeit ausgeben können :o) wenn das also dein Ziel ist…
Hm… mir ist nicht ganz klar, was du meinst… Jeder Typ ist ein Knoten, und die Kanten sind “ist supertyp von” ?! Das bringt ja nichts - das wird ja “implizit” aufgebaut. Solange (mir) nicht klar ist, welche Typen überhaupt aufgelistet werden sollen, ist ein Ansatz da ziemlich schwierig…
Mit „out of memory“?
Ich meinte eigentlich den Graphen, der direkt aus der Vererbungshierarchie hervorgeht: Knoten ist eine Klasse / Interface und von jedem Knoten geht eine Kante zum Supertyp, n-Kanten zu den implementierten Interfaces und pro Typparameter (das ist das entscheidende) eine Anzahl an Kanten zu den möglichen Kandidaten.
Da die Referenzen für die Typparameter nicht auf explizite Typen zeigen, wird der Graph nicht unendlich groß.
Hmm. Ich glaube so richtig toll kann ich das nicht ausdrücken. Vielleicht zeichne ich nachher mal kurz eine Grafik am Beispiel von Integer.
P. S.: vielleicht sollte man diese Diskussion hier vom Quizthread abtrennen?
Es war ein StackOverflowError (aber auf den oder OutOfMemory mußte es natürlich rauslaufen…)
Irgendwie müßten die Typparameter eine “besondere” Rolle einnehmen (also nicht Teil des übrigen Graphen sein). Vielleicht könnte man sich da was überlegen… Aber… wie auch immer die konkrete Implementierung dann aussehen würde: Welche supertypen würde dieses Verfahren denn z.B. für ‘Integer’ dann ausgeben…?!
Das wäre auch eine Möglichkeit, wenngleich sie dann halb explizit und halb implizit ist (explitzit das meiste, implizit die Typparameter). Das fände ich nicht so schön.
Der Zustandsraum ist unendlich, daher wird man ihn, wie man es auch dreht und wendet, nicht vollständig ausgeben können.
Sinnvoll wäre es meiner Meinung nach, die Zyklen zu detektieren und dann bei der Ausgabe eine geeignete Darstellung dafür zu wählen (wie auch immer diese dann aussehen mag).
Vielleicht wie bei sich wiederholenden Nachkommastellen gebrochener Zahlen mit Strich drüber?
Nun, es geht nicht direkt um eine “Ausgabe” - es sollte nur damit gerechnet werden können. Aber selbst DA habe ich für dieses spezielle Problem keinen konkreten Anwendungsfall. Wie gesagt, es ist nur eine kleine Lib, für “Zeug, das mit Typen zu tun hat”, und die Berechnung der Menge der Supertypen wollte ich (angelehnt an http://www.angelikalanger.com/GenericsFAQ/FAQSections/TechnicalDetails.html#Which%20super-subtype%20relationships%20exist%20among%20instantiations%20of%20parameterized%20types? ) eigentlich nur als Schmankerl einbauen. Für das Projekt, für das ich das entwickle, brauche ich in erster Linie die magische “Types.isAssignable(to, from)”-Methode, aber … selbst die ist nicht so einfach, wenn Typvariablen in den Typen vorkommen. Da entsteht dann ein übles Konglomerat aus Anforderungen (siehe auch http://forum.byte-welt.net/threads/10615-Typinferenzalgorithmus-in-Java-(ggf-auch-Java-8) ), und ich habe es bisher noch nicht geschafft, meinen Kopf da drum zu wickeln… :verzweifel:
Eine Menge von Typen fällt ja auf jeden Fall schonmal weg, weil sie erwiesenermaßen unendlich ist. Daher kommt meines Erachtens nach nur ein Graph in Frage, deren Knoten wie oben beschrieben keinen vollständigen Typen darstellen, sondern deren generische Typparameter als Kanten hinterlegt sind.
Du nimmst dir ja recht sportliche Aufgaben vor 
Aber wenn man irgendwann mal einen bestimmten Level erreicht hat, ist vieles andere wahrscheinlich unspektakulär.
Ich finde gar nicht dass man verschiedene Generics einer Klasse als eigene Typen ansehen sollte wenn man sowas zählt.
Du meinst alles nur als raw types? Naja, das ist dann ja etwas langweilig. Schon das angesprochene “Types.isAssignable(to, from)” wäre ja trivial, wenn man nur Raw Types verwenden würde - schließlich gibt es schon someClass.isAssignableFrom(someOtherClass). Das Problem dabei ist, dass er immer sagt ‘someList.isAssignableFrom(someOtherList)==true’. Ich will aber gerade, dass er mir die Assignabilitäten richtig ausgibt:
List<Number> := List<Integer> -> false (NICHT true!)
List<? extends Number> := List<Integer> -> true
List<? extends Comparable> := List<Integer> -> true
…
Nochmal: Wirklich “benötigt” wird die Berechnung der Menge aller supertypen bisher (?!) eigentlich nicht. Ich wollte diese Funktion nur “der Vollständigkeit halber” anbieten, und weil ich dachte, dass sie an manchen Stellen vielleicht ganz interessant oder praktisch sein könnte (für sowas wie “Berechne mir die Schnittmenge der Supertypen dieser beiden Typen” etc…).
BTW: Das mit der Assignability funktioniert auch so weit. Abgesehen von den Typvariablen, wo ich gerade dran bastle:
List<T> := List<Integer> -> ???
Er sollte dort weder ‘false’ noch ‘true’ ausgeben, sondern vielmehr sowas wie
“true, wenn T==Integer ist”
Entsprechend kompliziert kann das werden…
List<? extends T> := List<Integer> -> ???
“true, wenn T ein Supertyp von Integer ist”
Hinauslaufen wird das vermutlich auf eine Sammlung von Methoden, die im Umfeld von http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.12.2.7 benötigt werden…
(Ja, ich weiß, spätestens im OpenJDK (und auch im Eclipse JDT) muss all das ja schonmal irgendwo implementiert worden sein, aber ich hätte halt gerne ein kleines, praktisches “Schweizer Taschenmesser der Typberechnungen” :D)
Ich glaube, das was du vorhast ist noch eine Nummer komplexer. Ich habe die JLS (explizit auch den von dir verlinkten Abschnitt) nicht komplett gelesen. Was der Compiler aber macht, ist doch nur zu prüfen, ob ein Ausdruck gültig ist. Du möchtest die möglichen Kandidaten bestimmen. Meinem Verständnis nach verhält sich das in etwa so, wie „prüfen, ob eine gegebene Menge von Primfaktoren diejenigen einer Zahl sind“ zu „die Primfaktoren einer Zahl ermitteln“. Das eine ist leicht, das andere schwierig.
Siehe oben, die kannst du auch nicht explizit angeben. Um Schnittmengen zu bilden, brauchst du die Mengen aber gar nicht explizit, dafür reicht eine Menge an Raw Types, die um Referenzen auf ihre Typparameter angereichert sind. Ähnlich wird es sich mit anderen Anwendungsfällen dieser Menge verhalten.
Das erinnert mich ein wenig an Parser, die ja auch in der Lage sind, Vervollständigungen zu machen (bzw. Kandidaten zu listen). Vielleicht kannst du dich aus dem Bereich von irgendwelchen Algorithmen bedienen?
Muss man korrekterweise schon, zumindest wenn man nicht jegliche Typtheorie über Bord werfen will: Eine List in Java ist kein Typ, sondern ein Typkonstruktor, oder anders gesagt, sie hat den Kind * -> * statt *.
OT: Ich kann nicht richtig nachvollziehen, warum auf so etwas an den Unis kaum eingegangen wird (zumindest ist das mein Eindruck), denn im Endeffekt hilft es z.B. beim Verständnis von Generics, und ist auch nicht komplizierter als etwa Mengenlehre.
[QUOTE=cmrudolph]Ich glaube, das was du vorhast ist noch eine Nummer komplexer. Ich habe die JLS (explizit auch den von dir verlinkten Abschnitt) nicht komplett gelesen. Was der Compiler aber macht, ist doch nur zu prüfen, ob ein Ausdruck gültig ist. Du möchtest die möglichen Kandidaten bestimmen.
[/quote]
Ich habe das auch noch nicht alles gelesen und nachvollzogen. Aber die Vermutung, die du da andeutest („Prüfen, ob X passt“ vs. „Ausgeben, was alles passen würde“) hatte ich auch schon… Zuerst hatte ich (für das eigentliche Projekt) auch die Guava Type Tokens verwendet ( http://code.google.com/p/guava-libraries/wiki/ReflectionExplained ) : Die bieten schon viel von der Funktionalität, die ich brauchte: Assignability mit Typparametern, Resolven passender Typen etc. Aber die können erstmal nur zur Compilezeit erstellt werden, und hatten nicht zuletzt deswegen einige Einschränkungen, die mich dazu veranlasst haben, zumindest mal zu versuchen, das ganze selbst anzugehen. (Viel von dem, was ich bisher gemacht habe, ist ziemlich analog zu dem, was auch von den TypeTokens gemacht wird, aber … an manchen Stellen geht es schon etwas darüber hinaus, und an anderen Stellen wird es hoffentlich noch deutlich darüber hinausgehen).
Dass das ganze ziemlich komplziert ist, schwant mir auch schon eine Weile. Bezüglich der „Vervollständigung“: Sicher gibt es da Algorithmen dafür. (Ansatzweise wird das ja schon von Eclipse erledigt, z.B. wenn man eine Variable verwendet, die es nicht gibt, und man ihm dann sagt: ‚Generate local Variable‘ oder so). Aber es gibt da eben nicht nur „einen“ Algorithmus, der in 10 Zeilen Pseudocode beschrieben und in 50 Zeilen Java-Code nachimplementiert ist. Da steckt ziemlich viel Theorie dahinter. Meine „Liste, der Dokumente, die ich mal lesen müßte“ wird immer länger. Und wenn ich sowas sehe wie das schon in diesem Beitrag erwähnte, wird nochmal das offensichtlicher, was mir eigentlich schon klar ist: Da stecken 50 Jahre Forschung und wissenschaftliche Ergebnisse drin, die auf einer theoretischen Basis stehen, die ich mir in der Praxis unmöglich „mal kurz nebenbei“ erarbeiten kann.
Selbst die vergleichsweise elementarsten Papers (oder auch schon Landei’s Link) lehren mich diesbezüglich eine Form von Demut, die schon seit hunderten von Jahren nicht mehr praktiziert wurde 
(Naja, vielleicht doch: Die Zitate vom Anfang von http://www.artima.com/weblogs/viewpost.jsp?thread=222021 beruhigen mich da doch immer wieder ein bißchen 
). Es wäre sicher hilfreich, wenn man sich bei sowas schonmal mit Haskell oder so beschäftigt hätte (das wird praktisch überall für die ~„Simple Examples“ verwendet - und für mich sind es eben nur Hieroglyphen 
), aber vielleicht schaffe ich es zumindest, mich so weit da reinzufräsen, dass da eine praktische Lib rauskommt.
Wär’ ja langweilig, wenn man immer nur Sachen machen würde, die man schon kann
Ist jetzt nur ein Teilaspekt und ich schreibe hier bestimmt nichts neues.
Für Unendliche Mengen, also die Menge der natürlichen Zahlen, oder die Menge der Primzahlen ist es weit verbreitet Generatoren zu verwenden.
Angenommen Primzahlen: Ist 67 eine Primzahl?
boolean isPrime(int x)
Collection<Integer> allPrimes = calculateAllPrimes();
return allPrimes.contains(x);```
Das Problem tritt beim Berechnen der Primzahlen auf, da diese ja eigentlich kein Ende besitzen. Also nutzt man einen Generator, der könnte in Java in Form eines Iterators daherkommen. In Scala oder Clojure sieht man solche Generatoren oder Lazy Seq's an allen Ecken und Enden.
```boolean isPrime(int x)
Iterator<Integer> it = primeGenerator();
do {
int cur = it.next();
if(cur == x)
return true;
} while(cur<x);
return false;```
Die Primzahlen haben eine **natürliche Ordnung** und werden **nur soweit generiert, wie** sie auch **gebraucht** werden. Die Ordnung sorgt dafür, dass man auch ein **Abbruchkriterium** definieren kann.
Ich denke, dass sind Punkte, die man auch auf das Problem anwenden müsste.Sich mit Haskell zu beschäftigen ist ganz lustig. Ich habe das im Studium ein Semester lang sehr intensiv gemacht, auch keine andere Sprache parallel programmiert. Und als ich dann wieder Delphi programmiert habe, waren meine Algorithmen plötzlich alle rekursiv
Sehe ich auch so. Du wirst bei deinen Expeditionen wahrscheinlich recht wenig Hilfe bekommen. Bei so einem Tätigkeitsfeld ist man wahrscheinlich in einer Uni am besten aufgehoben
*** Edit ***
Hatte ich oben, zwar nicht so explizit, aber mit der Aussage gemeint, dass man die Mengen nicht explizit angeben muss und referenzen verwenden kann. Man nutzt dabei dann natürlich die topologische Ordnung (ist das überhaupt eine 
) aus, um den Suchraum zu minimieren, sobald man explizit wird.
Was ich meinte ist, dass sobald du ein hast du ja sowieso schon unendlich viele mögliche Typen hast, auch wenn du nur Klassen betrachtest die Comparable implementieren weil ich unendlich viele Klassen machen kann. Realistischer wäre es, wenn du deinem Programm eine Menge an Klassen gibst, z.B die standard JDK Klassen und von denen dann die möglichen Treffer zeigst.
An einen Iterator hatte ich auch schon gedacht, aber … das ist ja nicht das Ziel. Es sollte schon eine explizit konstruierte Menge sein. Gerade um sowas wie “Schnittmenge der Supertypen zweier Typen” berechnen zu können. Aber nochmal: Wirklich “brauchen” tut man das nicht. Ich dachte nur, dass es vielleicht ein interessantes Feature wäre, das man von so einer Lib erwarten würde.
Ich denke aber schon, dass, wenn diese Lib erstmal auf GitHub o.ä. liegt, sich Leute dafür interessieren könnten (die mehr Ahnung von der Theorie haben, als ich), und DA dann Hilfe herkommt. Deswegen könnte sowas ggf. auch nachträglich eingebaut werden.
Bezüglich des scheinen Mißverständnisse vorzuliegen: Es geht ja nicht darum, herauszufinden, wofür das ‘T’ in diesem Fall genau steht. Erstens könnten das, wie du schon sagtest, unendlich viele Klassen sein, und zweitens ist die einzig relevante Information in diesem Fall schon gegeben: T extends Comparable. Mehr kann man daraus nicht ableiten. Das Problem bei der Auflistung der Supertypen ist ja, dass dort eine unendlich lange Kette entstehen kann. Diese unendlich lange Kette besteht so gesehen nicht aus “verschiedenen Typen”. Die Menge der “raw” supertypen von Integer ist ja klar: Object, Number, Serializable, Comparable (das war’s dann glaub’ ich schon). Aber obwohl diese Menge der Supertypen hart eingeschränkt ist (und auch nicht “von außen” erweitert werden kann), können durch die Typparameter von Comparable dort unendlich viele Parameterized Types als Supertypen angegeben werden, die alle wieder nur aus ein paar “? extends X” bestehen, wobei X einer dieser 4 supertypen ist.
In den letzten Tagen habe ich da nicht konkret auf eine Lösung hingearbeitet, aber in den nächsten Tagen werde ich mal schauen, was man da machen kann (aber da es eigentlich nicht “wichtig” ist, hat es vergleichsweise geringe Priorität gegenüber der Type Inference (und gegenüber der Lib, für die ich diese Types-Lib dann eigentlich verwenden will…))