Übersetzung


... [ Seminar "Java und Werkzeuge für das Web" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ...

Übersicht: Übersetzung


Grundsätzliches

Die Semantik der Übersetzung wird im folgenden dadurch beschrieben, dass die Übersetzung wieder als Javacode dargestellt wird. Natürlich übersetzt der Compiler direkt in Bytecode, aber diese Darstellung ist anschaulicher als Bytecode.

Bei der Übersetzung wird der Typparameter aus der Klassendefinition gelöscht. Wurde kein einschränkender Typ angegeben, so wird Object genommen. Ansonsten werden Typparameter innerhalb der Klasse durch ihren einschränkenden Typ, also den Typ, der direkt nach "extends" steht, ersetzt. Wenn der Compiler die Typparameter umformt, ersetzt er also beschränkte Typparameter durch den beschränkenden Typ.

01 public static <A extends Comparable<A>> A max(Collection<A> xs){...
02 
03 // wird uebersetzt zu
04 
05 public static Comparable max(Collection xs){...
Bsp/Bsp43.txt

Codebeispiel 21


Der Fall mit mehreren Einschränkungen wird später behandelt. Alle anderen Typen bleiben unverändert.

Ein vollständiges Beispiel für die Übersetzung:
01 interface Collection<A> {
02   public void add(A x);
03   public Iterator iterator();
04 }
05 
06 interface Iterator<A> {
07   public A next();
08   public boolean hasNext();
09 }
10 
11 class NoSuchElementException extends RuntimeException {}
12 
13 class LinkedList<A> implements Collection<A> {
14   protected class Node {
15     A elt;
16     Node next = null;
17     Node(A elt){ this.elt = elt; }
18   }
19 
20   protected Node head = null, tail = null;
21   public LinkedList(){}
22   public void add(A elt){
23     if(head==null){ head = new Node(elt); tail = head; }
24     else { tail.next = new Node(elt); tail = tail.next; }
25   }
26 
27   public Iterator<A> iterator(){
28     return new Iterator<A>(){
29       protected Node prt = head;
30       public boolean hasNext(){ return ptr!=null; }
31       public A next(){
32         if(ptr!=null){
33           A elt=ptr.elt; ptr=ptr.next; return elt;
34         } else
35           throw new NoSuchElementException();
36       }
37     };
38   }
39 }
Bsp/Bsp05.txt

Codebeispiel 22

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 = xs.iterator().next();
06 
07     LinkedList<String> ys = new LinkedList<String>();
08     ys.add("zero"); ys.add("one");
09     String y = ys.iterator().next();
10 
11     LinkedList<LinkedList<String>> zss = new LinkedList<LinkedList<String>>();
12     zss.add(ys);
13     String z = zss.iterator().next().iterator().next();
14   }
15 }
Bsp/Bsp45.txt

Codebeispiel 23

Im Beispiel wird also "Iterator<A>" durch "Iterator" ersetzt. Alle Vorkommen von "A" werden durch "Object" ersetzt. Für Methoden die einen Typparameter zurückgeben, wird in der benutzenden Klasse ein Cast eingefügt (in den korrekten Typ). Das gleiche gilt für einen Zugriff auf ein Datenfeld, dass von einem parametrisierten Typ ist. Alle Casts die der Compiler einfügt, sind garantiert sicher. Sollte der Compiler keine Sicherheit garantieren können (das passiert wenn generischer Code mit nichtgenerischem vermischt wird), so wird er eine Warnmeldung ausgeben, aber trotzdem compilieren. Dies ist notwendig um die Zusammenarbeit mit altem Code zu gewährleisten. Wird alter Code mit der neuen parametrisierten Collection-Bibliothek compiliert, wird an mehreren Stellen eine unchecked-Warnung ausgegeben werden, aber der Code wird wie bisher funktionieren.

Das entstehende Programm ist vollständig identisch mit dem Programm das ohne Generizität entwickelt wurde:
01 interface Collection {
02   public void add(Object x);
03   public Iterator iterator();
04 }
05 
06 interface Iterator {
07   public Object next();
08   public boolean hasNext();
09 }
10 
11 class NoSuchElementException extends RuntimeException {}
12 
13 class LinkedList implements Collection {
14   protected class Node {
15     Object elt;
16     Node next = null;
17     Node(Object elt){ this.elt = elt; }
18   }
19 
20   protected Node head = null, tail = null;
21   public LinkedList(){}
22   public void add(Object elt){
23     if(head==null){ head = new Node(elt); tail = head; }
24     else { tail.next = new Node(elt); tail = tail.next; }
25   }
26 
27   public Iterator iterator(){
28     return new Iterator(){
29       protected Node prt = head;
30       public boolean hasNext(){ return ptr!=null; }
31       public Object next(){
32         if(ptr!=null){
33           Object elt=ptr.elt; ptr=ptr.next; return elt;
34         } else
35           throw new NoSuchElementException();
36       }
37     };
38   }
39 }
Bsp/Bsp03.txt

Codebeispiel 24

01 class Test {
02   public static void main(String[] args){
03     LinkedList xs = new LinkedList();
04     xs.add(new Byte(0)); xs.add(new Byte(0));
05     Byte x = (Byte) xs.iterator().next();
06 
07     LinkedList ys = new LinkedList();
08     ys.add("zero"); ys.add("one");
09     String y = (String) ys.iterator().next();
10 
11     LinkedList zss = new LinkedList();
12     zss.add(ys);
13     String z = (String)((LinkedList)zss.iterator().next()).iterator().next();
14   }
15 }
Bsp/Bsp44.txt

Codebeispiel 25

Daraus kann man bereits einige (vorläufige) Eigenschaften ableiten:
Durch das beschriebene Übersetzungsschema geht die Typinformation verloren und steht zur Laufzeit nicht mehr zur Verfügung. Als Begründung für diese Entscheidung wird Effizienz und Kompatibilität angegeben. Es sei nicht klar, welchen Einfluss generische Typen zur Laufzeit auf die Performanz haben. Man geht davon aus, dass die JVM deutlich komplexer werden müsste und dies ist für Java insbesondere im Embeded Systems Bereich (Handys etc.) zur Zeit nicht akzeptabel. Microsoft hat vor kurzem eine Spezifikation veröffentlicht, die Generizität in der CLR vorsieht. Dies wird am Beispiel von C# besprochen [Kennedy02]. C# hat zur Zeit auch keine Generizität. Der Entwurf sieht vor, die Typinformation zur Laufzeit beizubehalten. Wie in C++ ist es auch hier möglich, primitive Typen als Parameter einzusetzen. Die Performance soll bei dem beschriebenen Entwurf ähnlich zu "handoptimiertem" Code sein. Zur Umsetzung wird die Zwischensprache (entsprechend dem ByteCode bei Java) erweitert. Sun will den ByteCode bisher nicht ändern.

Das Übersetzungsschema von GJ nennt man auch homogene Übersetzung. Allgemein ist eine homogene Übersetzung eine Umformung, die zwei Klassen, welche mit unterschiedlichen Typen parametrisiert wurden, in eine Klasse abbildet. Vorteilhaft ist dabei der nicht anwachsende Code (insb. Speicherverbrauch). Nachteil sind die eingefügten Casts [Eisenecker98].

C++ verwendet dagegen eine heterogene Übersetzung. Für jede Typausprägung wird der Code sozusagen verdoppelt ([Stroustrup91], S. 342). Im Prinzip ist das C++ Konzept nur eine Art erweiterter Präprozessor. Dies ist einer der Hauptkritikpunkte an dem Template-Konzept von C++. Wird der gleiche Code mit vielen unterschiedlichen Typen parametrisiert, so wird für jeden Typ die gesamte Klasse dupliziert. Der Speicherbedarf steigt entsprechend.

Vorteil hierbei ist allerdings, dass die Laufzeit besser ist und auch primitive Typen als Parameter erlaubt sind. Dies ist in der Javalösung nicht möglich (auch nicht in NextGen)! Ein weiterer Nachteil, neben dem erhöhtem Speicherverbrauch in der C++ Implementierung, ist die Tatsache, dass Typkonflikte evtl. erst beim Binden und nicht beim Compilieren aufgelöst werden können ([Stroustrup91], S.343). Die Typdeklarationen (nicht "Typdefinitionen"!) werden bei C++ im Gegensatz zum Javaentwurf nicht typgeprüft. Insofern erlaubt die Javalösung eine frühere Fehlererkennung. In [Bracha98] wird auch angegeben, dass eine heterogene Übersetzung Probleme mit dem Java Sicherheitsmodell bereiten könnte.

Alle parametrisierten Typen haben zur Laufzeit die gleiche Klasse bzw. das gleiche Interface wie dieses Beispiel zeigt:

01 Vector<String> x = new Vector<String>();
02 Vector<Integer> y = new Vector<Integer>();
03 return x.getClass() == y.getClass();
Bsp/Bsp33.txt

Codebeispiel 26


Die letzte Zeile liefert "true".

Und noch eine Unstimmigkeit zwischen Compiler und Spezifikation: Wenn die Beschränkung nur aus Interfaces besteht, so wird nach der Spezifikation ([Bracha01_1] S. 14) das Interface genommen, dass nach der Typauslöschung den kleinsten lexikographischen Namen hat. Diese merkwürdige Regel ist aber im Prototypcompiler nicht implementiert. Dort wird die Typvariable immer durch den ersten beschränkenden Typ ersetzt. Dazu ein Beispiel

01 interface IA { public void testA(); }
02 interface IB { public void testB(); }
03 interface IC { public void testC(); }
04 
05 class Test<A extends IB & IC & IA>{
06   public A value; // wird den Typ IB bekommen!
07   public void testIt(){ value.testA(); }
08 }
Bsp/Bsp37.txt

Codebeispiel 27


Dieser Code wird vom Prototypcompiler in Bytecode übersetzt, bei dem das Feld value den Typen IB bekommt. Der Aufruf von testA() funktioniert, da der Compiler einen Cast einfügt, wie folgender Bytecode zeigt:

01 Method void testIt()
02   0 aload_0
03   1 getfield #2 <Field IB value>
04   4 checkcast #3 <Class IA>
05   7 invokeinterface (args 1) #4 <InterfaceMethod void testA()>
06  12 return
Bsp/Bsp39.txt

Codebeispiel 28


Dieses Verhalten ist korrekt, die Spezifikation falsch [BrachaMail].


[ nach oben ]

RawTypes

Einen parametrisierter Typ ohne seine Parameter nennt man Raw-Type. So ist z.B. LinkedList der Raw-Type von LinkedList<A>. Methoden, die auf einem Raw-Type aufgerufen werden, entsprechen Methoden bei denen die Typinformation gelöscht wurde. Ein Aufruf einer Methode, die auf einem parametrisierten Typ ein "A" als Rückgabetyp liefert, würde bei einem Raw-Type Object liefern.

Eine Zuweisung von einem parametrisierten Typ an den entsprechenden Raw-Type ist immer möglich. Das bedeutet also auch, dass z.B. Collection<A> an eine Methode übergeben werden kann, die eigentlich nur Collection erwartet. Anders herum geht die Zuweisung auch, aber hier wird eine Unchecked-Warnung zur Compilezeit ausgegeben. Auch einige Methodenaufrufe können auf einem Raw-Type eine Unchecked-Warning auslösen. Dazu ein Beispiel:

01 class Loophole {
02   public static String loophole (Byte y) {
03     LinkedList<String> xs = new LinkedList<String>();
04     LinkedList ys = xs;
05     ys.add(y); // unchecked warning
06     return xs.iterator().next();
07   }
08 }
Bsp/Bsp27.txt

Codebeispiel 29


Hier wird bei Aufruf der add-Methode eine unchecked-Warning angezeigt. Zur Compilezeit kann nicht geprüft werden, ob hier der richtige Typ eingefügt wurde. Der übersetzte Code:

01 class Loophole {
02   public static String loophole (Byte y) {
03     LinkedList xs = new LinkedList();
04     LinkedList ys = xs;
05     ys.add(y);
06     return (String)xs.iterator().next(); // run-time exception
07   }
08 }
Bsp/Bsp28.txt

Codebeispiel 30


Hier wird bei Zugriff auf den Container in der letzten Zeile eine ClassCastException zur Laufzeit ausgelöst. Der Compiler hatte den Programmierer gewarnt!

Eine uncheckedWarnung wird bei einem RawType allgemein in zwei Fällen ausgelöst:

01 /* Code in der Datei Test03.java */
02 class Testit<A>{
03   public A v;
04   public void set(A v){ this.v=v; }
05 }
06 
07 public class Test03{
08   public static void main(String[] args){
09     Testit t = new Testit(); // oder auch new Testit<Boolean>()
10     t.v = Boolean.TRUE;
11     t.set(Boolean.TRUE);
12   }
13 }
14 
15 /* Ausgabe des Compilers:
16  * Test03.java:9: warning: unchecked assignment to variable v of raw type
17  * class Testit
18  *     t.v = Boolean.TRUE;
19  *      ^
20  * Test03.java:10: warning: unchecked call to set(A) as a member of the raw
21  * type Testit
22  *     t.set(Boolean.TRUE);
23  *      ^
24  * 2 warnings
25  */
Bsp/Bsp41.txt

Codebeispiel 31


Keine Warnung wird bei Typ-Änderung des Rückgabewertes, bei lesenden Zugriffen oder bei Konstruktor Aufrufen auf RawTypes ausgegeben. Beim Vermischen von GJ-Code mit altem Code werden eine ganze Reihe von unchecked-Warnungen ausgegeben. Diese sind in vielen Fällen unbegründet. Wenn die aktuelle Version von jtap [jtap02] mit dem GJ Compiler übersetzt wird, werden z.B. 102 unchecked-warnungen ausgegeben.

Das nächste Beispiel zeigt, wie RawTypes mit parametrisierten Typen interagieren:

01 class Cell<A>
02   A value;
03   Cell(A v){ value = v; }
04   A get(){ return v; }
05   void set(A v){ value = v; }
06 }
07 
08 Cell x = new Cell<String>("abc");
09 x.value;      // ok, hat Typ Object
10 x.get();      // ok, hat Typ Object
11 x.set("def"); // warnung: unchecked call
Bsp/Bsp35.txt

Codebeispiel 32



[ nach oben ]

Brückenmethoden

Wie wird dieses Codebeispiel übersetzt?
01 interface Comparator<A> {
02   public int compare(A x, A y);
03 }
04 
05 class ByteComparator implements Comparator<Byte> {
06   public int compare(Byte x, Byte y){
07     return x.byteValue() - y.byteValue();
08   }
09 }
10 
11 class Collections {
12   public static <A> A max(Collection<A> xs, Comparator<A> c){
13     Iterator<A> xi = xs.iterator();
14     A w = xi.next();
15     while(xi.hasNext()){
16       A x = xi.next();
17       if(c.compare(w,x) < 0) w = x;
18     }
19     return w;
20   }
21 }
Bsp/Bsp09.txt

Codebeispiel 33

Der Code kann mit den bisher beschrieben Verfahren nicht umgesetzt werden, da die Methode compare dann nicht mehr überschrieben werden könnte.
Hier kommt eine weitere Besonderheit ins Spiel. Eine so genannte Brückenmethode wird in der Klasse ByteComparator eingefügt:

01 class ByteComparator implements Comparator {
02   public int compare(Byte x, Byte y){
03     return x.byteValue() - y.byteValue();
04   }
05 
06   public int compare(Object x, Object y){
07     return this.compare((Byte) x, (Byte) y);
08   }
09 }
Bsp/Bsp11.txt

Codebeispiel 34


Die zweite Methode ist eine Brückenmethode, die die Argumente in den bisherigen Typ castet und dann die speziellere Methode aufruft. Eine Brückenmethode ist nicht anderes, als eine Überladung der Methode mit Änderung der Argumenttypen. Die Brückenmethode hat als Argumenttypen Object. Dies ist notwendig, weil eine Methode, die parametrische Typen enthält, auch überschrieben werden darf. Konkret darf die compare Methode aus der Klasse ByteComparator überschrieben werden. Nun gibt die JLS [Gosling00] aber vor, dass eine Methode nur dann überschrieben wird, wenn die Signatur exakt gleich bleibt. Aus diesem Grund muss die Brückenmethode eingefügt werden. Ganz allgemein wird eine Brückenmethode eingefügt, wenn eine Klasse ein parametrisiertes Interface implementiert oder von einer parametrisierten Klasse abgeleitet ist und den Parameter dabei mit einem konkreten Typ festlegt. (in diesem Beispiel Byte für A). Etwas formaler: es gebe eine Klasse oder ein Interface C von dem D abgeleitet wird. Eine Brückenmethode wird in D eingefügt, wenn ([Bracha01_1], S.14-15):

Da der zweite Punkt etwas unklar ist, wollte ich dies mit dem Dissassembler "javap -c" prüfen. Der stützt aber leider ab, wenn der Code Brückenmethoden enthält. Dieser Punkt muss daher offen bleiben.

Damit die Übersetzung nicht zu Mehrdeutigkeiten führt, gibt es drei weitere Regeln: ([Bracha01_1], S.16)

Die Regeln wollte ich wieder mit einem Beispiel beweisen. Leider verhält sich der Compiler bei der zweiten und dritte Regel mal wieder nicht entsprechend der Spezifikation. Diesmal liegt der Fehler aber im Compiler [BrachaMail]. Nachfolgend der kommentierte Beispielcode:

01 class D<A> { A id(A x){...} }
02 interface I<A> { A id(A x); }
03 
04 class C extends D<String> {
05   Object id(Object x){...}
06   // liefert wie erwartet einen Compilerfehler
07   /** Fehlerausgabe wg. zweiter Regel:
08    *  name clash: id(java.lang.Object) in C and id(A) in 
09    *  D<java.lang.String> have the same erasure, yet none
10    *  overrides the other
11    *  class C extends D<String>{
12    *  ^
13    */
14 }
15 
16 class E extends D<String> implements I<Integer> {
17   String id(String x){...} 
18   Integer id(Integer x){...}
19   /** Diese Klasse wird OHNE Fehlermeldung
20    *  compiliert! Das widerspricht der dritten Regel
21    *  (S.16 Example 20) der Spezifikation
22    *  Gilad Bracha hat dies als Compilerfehler bestaetigt
23    */
24 }
Bsp/Bsp38.txt

Codebeispiel 35



[ nach oben ]

Brücken gleicher Signatur

Ein Problem tritt auf, wenn eine Klasse ein parametrisiertes Interface oder eine parametrisierte Klasse implementiert bzw. erweitert und den Parameter als Rückgabetyp einer Methode ohne Argumente verwendet. Hier muss der Compiler wieder eine Brückenmethode einfügen, die den Typparameter durch den beschränkenden Typ oder Object ersetzt. Jetzt sind aber in der Klasse zwei Methoden mit identischer Signatur enthalten! Sie unterscheiden sich nur noch in den Rückgabetypen. Ein Beispiel:

01 inteface Iterator<A> {
02   public boolean hasNext();
03   public A next();
04 }
05 
06 class Interval implements Iterator<Integer> {
07   private int i;
08   private int n;
09   public Interval(int l, int u) { i = l; n = u; }
10   public boolean hasNext() { return (i <= n); }
11   public Integer next() { return new Integer(i++); }
12 }
Bsp/Bsp16.txt

Codebeispiel 36


Für die "next()" Methode muss eine Brückenmethode eingesetzt werden. Der erzeugte Code sieht als Javaquellcode so aus:

01 interface Iterator {
02   public boolean hasNext();
03   public Object next();
04 }
05 
06 class Interval implements Iterator {
07   private int i;
08   private int n;
09   public Interval(int l, int u) { i = l; n = u; }
10   public boolean hasNext() { return (i <= n); }
11   public Integer next/*1*/() { return new Integer(i++); }
12   // bridge
13   public Object next/*2*/() { return next/*1*/(); }
14 }
Bsp/Bsp17.txt

Codebeispiel 37


Nun ist dies aber kein legaler Javaquellcode mehr. Eine Klasse darf keine zwei Methoden mit identischer Signatur haben (der Rückgabetyp zählt nicht zur Signatur) [Gosling00] §8.4.2.
Allerdings lässt sich dieser Code in legalen ByteCode übersetzen. Die JVM erlaubt zwei Methoden mit gleicher Signatur aber unterschiedlichen Returntype in einer Klasse. Die Identifizierung einer Methode in der JVM erfolgt über den Namen der Methode und ihren "method descriptor" [Lindholm99] §4.3.3. und dieser enthält neben den Parameterbeschreibungen auch den Rückgabewert.

Mit anderen Worten: der vom Compiler erzeugte Code lässt sich nicht mehr als legaler Javaquellcode darstellen bzw. compilieren, ist aber legaler JVM-Code. Um die Übersetzung trotzdem als Javacode darzustellen, wird in den Beispiel der Methodenaufruf mit einem Kommentar versehen (/*1*/), der klar macht, welche Methode hier gemeint ist und im JVM-Code aufgerufen wird.


[ nach oben ]

Covariante Rückgabetypen

Die GJ Spezifikation erlaubt covariante Rückgabetypen. Man bezeichnet Methodenüberschreibung als covariant, wenn die Parametertypen und der Rückgabetyp durch speziellere Typen ersetzt werden können. Java hat bisher eine "novariant" Regelung: weder Rückgabetyp noch Parametertypen dürfen in überschriebenen Methoden geändert werden [Gosling00], §8.4.6.3. Covarianz kann tatsächlich in Zusammenhang mit Polymorphie zu einer Umgehung des Typsystems führen (siehe auch [Meyer98], in Eiffel wird Polymorphie in diesem Fall nicht erlaubt). Die Änderung des Rückgabetypen in einen spezielleren, ohne dabei die Parametertypen zu ändern ist aber ungefährlich für das Typsystem. Die Java Sprachdefinition wird dahingehend geändert werden. Covariante Rückgabetypen haben den Vorteil, dass weniger Cast nötig sind. Ein Beispiel:

01 class C implements Cloneable {
02   public C copy () { return (C)this.clone(); }
03 }
04 
05 class D extends C implements Cloneable {
06   public D copy () { return (D)this.clone(); }
07 }
Bsp/Bsp18.txt

Codebeispiel 38


Dies wäre in Java 1.4.1 illegaler Code, aber ist in GJ (und Java 1.5) erlaubt. Die Übersetzung erfolgt wieder mit einer Brückenmethode:

01 class D extends C implements Cloneable {
02   public D copy/*1*/ () { return (D)this.clone(); }
03 
04   // bridge
05   public C copy/*2*/ () { return this.copy/*1*/(); }
06 }
Bsp/Bsp19.txt

Codebeispiel 39


Es muss daher keine Änderung am Bytecode vorgenommen werden. Covariante Rückgabetypen stehen übrigens auf der RFE Liste zur Zeit auf Platz 3 [SunRFE]. Damit schlägt Sun zwei Fliegen mit einer Klappe.


[ nach oben ]

Sicherheit

Ein Beispiel wie mit generischen Klassen ein Sicherheitsloch entstehen kann:

01 class SecureChannel extends Channel {
02   public String read();
03 }
04 class C {
05   public LinkedList<SecureChannel> cs;
06   ...
07 }
Bsp/Bsp31.txt

Codebeispiel 40


Der Typ von LinkedList<SecureChannel> wird beim Compilieren durch den Rawtype LinkedList ersetzt. Jetzt wäre es möglich einen unsicheren Kanal in die Liste einzufügen - z.B. durch Code der mit einem älteren Compiler compiliert wird, oder durch Programmierung direkt im Bytecode. Die Typverletzung würde nicht bemerkt werden. Über diese Art von Problemen muss sich der Programmierer bewusst sein, denn er muss dieses Problem umgehen. Die Lösung ist eine spezielle Klasse die von der parametrisierten Klasse abgeleitet wird:

01 class SecureChannelList extends LinkedList<SecureChannel>{
02   SecureChannelList(){ super(); }
03 }
04 
05 class C {
06   SecureChannelList cs;
07   ...
08 }
Bsp/Bsp32.txt

Codebeispiel 41


Jetzt kann in der Liste kein anderer Typ mehr eingefügt werden als SecureChannel. Der Compiler wird bei der Übersetzung von SecureChannelList für alle Methoden einen Cast in SecureChannel einfügen, der die Sicherheit garantiert. Dies gilt jedoch nicht für den Zugriff auf Datenfelder.


... [ Seminar "Java und Werkzeuge für das Web" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ... [ nach oben ] ...

valid html4 logo Code generated with AusarbeitungGenerator Version 1.1, weblink