Typ-Inferenz
Übersicht: Typ-Inferenz
Typbestimmung
Der parametrische Typ wird bei Benutzung (laut Spezifikation) wie folgt bestimmt:
Der kleinste gemeinsame Typ für einen legalen Methodenaufruf wird als Typparameter genommen. Man nennt diese Typbestimmung lokal, da sie unabhängig von dem weiteren Kontext, insbesondere einem erwarteten Rückgabetyp ist.
Da ich mehrfach darauf Bezug nehme, hier nochmal das Codebeispiel:
01 class Test {
02 public static void main(String[] args){
03 LinkedList<Byte> xs = new LinkedList<Byte>();
04 xs.add(new Byte(0)); xs.add(new Byte(0));
05 Byte x = Collections.max(xs, new ByteComparator());
06
07 LinkedList<String> ys = new LinkedList<String>();
08 ys.add("zero"); ys.add("one");
09 // naechste Zeile fuehrt jetzt zu einem compile-error:
10 String y = Collections.max(ys, new ByteComparator());
11 }
12 }
|
Bsp/Bsp10.txt |
Codebeispiel 12
Der Typ von A wird in dem Beispiel aus den beiden Parametern abgeleitet. Im Gegensatz zu der Aussage während des Vortrages, scheint der Compiler auch Code zu akzeptieren, bei dem Object die einzige Gemeinsamkeit ist (sowohl bei Interfaces als auch bei Klassen). Dies aber nur, wenn der Typ direkt als Argumenttyp verwendet wird und nicht in anderen "verpackt" wird wie in dem Beispielcode. Die Spezifikation ist in diesem Punkt nicht eindeutig verständlich und ich kann nicht sagen, ob das Verhalten des Compilers nun korrekt ist. Man kann leicht Code produzieren, der den Compiler zu nicht nachvollziehbaren Fehlermeldungen bringt. Tatsache ist aber: im letzten Codebeispiel, in der letzten Zeile, wird eine Fehlermeldung ausgegeben. Hier versucht der Compiler einen gemeinsamen Typ von String (aus dem ersten Parameter abgeleitet) und Byte (aus dem zweiten Parameter) zu bestimmen. Das schlägt (hier) scheinbar fehl. Der Typ-Inferenz-Algorithmus muß wohl noch mal gründlich überarbeitet werden.
Null-Typ
Wenn der Compiler keinen Typ für eine parametrisierte Methode bestimmen kann, weil sie z.B. keine Argumente hat, dann wird der parametrisierte Typ durch einen besonderen Typ "*" ersetzt. Er wird im folgenden als null-Typ bezeichnet, da die Konstante null auch diesen Typ hat ([
Gosling00] §4.1). Dieser Typ darf nicht im Javaquellcode auftauchen (er hat auch keinen Bezeichner). Seine Eigenschaften sind sehr einfach: er ist ein Subtyp von allen Referenz-Typen. Darüber hinaus ist jeder Typ, der den null-Typ enthält, ein Subtyp jedes Typen, der entsteht, wenn man den null-Typ durch einen anderen Typen ersetzt. Das klingt kompliziert, ist aber ganz einfach.
Beispiele:
LinkedList<*> ist ein Subtyp von LinkedList<String> und Pair<Byte,*> ist ein Subtyp von Pair<Byte, Byte>.
Ein Codebeispiel in dem dieser Typ vom Compiler verwendet wird:
01 class Test {
02 public static <A> LinkedList<A> empty () {
03 return new LinkedList<A>();
04 }
05
06 public static <A> LinkedList<A> singleton (A x) {
07 LinkedList<A> xs = new LinkedList<A>();
08 xs.add(x);
09 return xs;
10 }
11
12 public static void main (String[] args) {
13 LinkedList<Byte> xs = empty();
14 LinkedList<String> ys = singleton(null);
15 }
16 }
|
Bsp/Bsp21.txt |
Codebeispiel 13
Hier gibt die Methode empty() einen parametrisierten Typ zurück. Da sie keine Parameter hat, wird für A der null-Typ genommen. Da LinkedList <*> ein Subtyp von LinkedList<String> ist, sind beide Zuweisungen in main(..) korrekt. Der aktuelle Argument-Typ ist immer ein Sub-Typ des formalen Parameters an der entsprechenden Position.
Umgehung des Typsystems
Es gibt jedoch eine Möglichkeit das Typsystem zu umgehen, weshalb eine weitere Einschränkung gemacht wird: der Methodenaufruf ist nur dann gültig, wenn der null-Typ nicht mehr als einmal im Rückgabetyp auftaucht. Dies ist eine so genannte Linearitätsbeschränkung. Auch hierzu ein kleines Beispiel:
01 class Cell<A> {
02 public A value;
03 public Cell (A v) { value = v; }
04 public static <B> Cell<B> allocate (B x) {
05 return new Cell<B>(x);
06 }
07 }
08
09 class Pair<A,B> {
10 public A fst;
11 public B snd;
12 public Pair (A x, B y) { fst = x; snd = y; }
13 public static <C> Pair<C,C> duplicate (C x) {
14 return new Pair<C,C>(x,x);
15 }
16 }
17
18 class Loophole {
19 public static String loophole (Byte y) {
20 Pair<Cell<String>,Cell<Byte>> p =
21 Pair.duplicate(Cell.allocate(null)); // compile-time error
22 p.snd.value = y; return p.fst.value;
23 }
24 public static String permitted (String x) {
25 Pair<Cell<String>,Cell<String>> p =
26 Pair.duplicate(Cell.allocate((String)null));
27 p.fst.value = x; return p.snd.value;
28 }
29 }
|
Bsp/Bsp22.txt |
Codebeispiel 14
Der Aufruf in loophole ist nicht erlaubt, da die Methode duplicate einen Typ zurück gibt, der vom Compiler zu Pair<Cell<*>, Cell<*>> auswertet wird. Hier könnte ein Byte zugewiesen werden, dass dann als String ausgelesen wird. Beide Felder der Klasse Pair zeigen nämlich auf das gleiche Objekt - schon ist das Typsystem nicht mehr intakt.
Dagegen ist der zweite Aufruf erlaubt, da hier der Typ Pair<Cell<String>, String<String>> entspricht und keine Verletzung des Typsystems auftritt.
Covariance kann leicht zu einer Verletzung des Typsystems führen. Deshalb werden in der Spezifikation die möglichen Fälle diskutiert. Die Argumentation beginnt damit, dass kein Typ T<...*...> explizit deklariert werden kann. Alles, was mit einem Wert von diesem Typ gemacht werden kann, ist eine Zuweisung an eine Variable bzw. einen Methodenparameter von einem anderen Typ. Es gibt dann drei Möglichkeiten:
- der Variablentyp ist ein unparametrisierter Supertyp von dem Rawtype T. Diese Zuweisung lässt das Typsystem intakt.
- der Variablentyp ist T´<....U...>, d.h. an der Position von * steht ein konkreter Referenztyp. T´ ist ein Supertyp von T. Da nur die Konstante null den null-Typ hat, und diese auch an jeden Referenztypen zugewiesen werden kann, ist die Zuweisung ebenfalls in Ordnung.
- die Variable ist ein Parameter p, dessen Typ eine Typvariable ist. Code der p im Methodenrumpf benutzt, ist unabhängig vom aktuellen Typ. Durch die Linearitätsbeschränkung wird der Methodenrückgabetyp maximal einmal den Typparameter enthalten, so dass dieser wieder in der Form T<....*...> ist.
Noch ein Beispiel:
01 interface I {}
02 interface J {}
03 interface K extends I {}
04 interface L extends I, J {}
05
06 class X {
07 static <A> A choose(A x, A y){
08 return (x.hash() < y.hash()) ? x : y;
09 }
10 static void test(K k, L l){
11 I i = choose(k,l); // ok
12 }
13 }
|
Bsp/Bsp30.txt |
Codebeispiel 15
Hier kann der Inferenz-Algorithmus den Typ von A beim Aufruf von choose(k,l) eindeutig bestimmen: es ist der Interface-Typ I. Wenn aber die Definition von K nachträglich geändert wird zu
Codebeispiel 16
dann wird der Aufruf zweideutig und ... funktioniert trotzdem! Jedenfalls akzeptiert der Prototypcompiler derartigen Code. Das Ergebnis wird in I gecastet. Ob das so korrekt ist: ich kann es wieder nicht sagen.
In [
Bracha98] findet man auch einen kurzen Vergleich von diesem Typ-Inferenz-Algorithmus zu dem Hindley-Milner-Typsystem auf dem u.a. Haskell basiert.
In C++ ist ein Methodenaufruf illegal, wenn z.B. der Typparameter als Rückgabewert, aber nicht als Argument auftaucht - also nicht bestimmt werden kann. In solchen Fällen kann man in C++ beim Funktionsaufruf die Typparameter explizit angeben ([
Schader95] Kap.18). In GJ war so etwas mal angedacht, in der letzten Spezifikation ist davon keine Rede.
Code generated with AusarbeitungGenerator Version 1.1, weblink