A Pizza nyelv

Sablonok

A Java nyelvhez nem terveztek genericet, template-et (a C++-tól eltérően), mivel arra gyakorlatilag csak hatékonysági okokból van szükség. De ügyeltek arra, hogy szimulálni lehessen a generic-et. A változó típusokat az osztályhierarchia csúcsával helyettesíthetjük; megtehetjük, hogy az Object osztályt használjuk, ami az összes osztály közös őse, és azon a helyen emiatt bármely osztálytípus használható. A standard Java könyvtárakban végig ezt az módszert használták a generic reprezentálására, ide értve a vektorokat, a hash táblákat és az enumerációkat. Ahogy a JDK fejlődött, a generic egyre több szerepet kapott. A JDK 1.1-ben bevezettek egy observer mintát (design pattern; lásd a Gamma könyvet) ami a generikusságon alapszik ugyanúgy, mint a kollekció osztályok az 1.2-ben. Generic eszközök sok nyelvben léteznek (Ada, Eiffel, Modula3). Ha egy adott nyelvben nincsenek meg, a generic eszközök megtervezése ma már rutinmunka. A Java-ban már a Commumity Process része a generic hozzáadása a nyelvhez, és a Pizza az első megoldások között volt. A szerzők azóta a Generic Java-val (GJ) továbbléptek kifejezetten a generic irányába.

A fenti bekezdésben leírtak időközben érvényüket vesztették. A Sun Java implementációja 2004 óta, a J2SE 5.0 -val kezdve támogatja a genericeket. A Pizza utolsó verziója 2002-ben került kiadásra.

Nézzük most bővebben, miért van szükség genericre:

A Pizza lehetővé teszi, hogy paraméterezett osztályokat és interfészeket írjunk. A paraméter bármilyen Java/Pizza típus lehet (Java osztályok, Pizza osztályok, beleértve a generikus Pizza osztályokat, felhasználói típusok, és elemi típusok (például az int). Van azonban néhány megkötés, ezekről lásd később (homogén átírás). Alprogramok is lehetnek a generic paraméterei, ezeket függvényparaméterekként lehet átadni. A generic formális típus paraméterére adhatunk megszorításokat (megkövetelhetjük, hogy a paraméter osztály bizonyos interfészt implementáljon). A példányosítás fordítási időben történik, és a fordító elvégzi a megfelelő típusellenőrzéseket. Nem azt csinálja, mint C++-ban, hogy előbb generálja a példánynak a kódját és utána ellenőriz. Így értelmes hibaüzeneteket kapunk.

Paraméterezett osztályok

Az osztály/interfész paramétere bármilyen Java/Pizza típus lehet. A típusparamétereket az osztály/interfész név után soroljuk fel < és > jelek között. Érdekesség: a Pizzában a < és > jelek határoló jelként viselkednek típusparaméter részben, így nyugodtan írhatjuk őket egybe, szemben a C++-al ahol a >>-t operátornak tekinti.

Paraméteres polimorfizmus (parametric polymorphism)

Nézzünk egy egyszerű példát egy olyan osztályra, ami egy meghatározott típusú elemet tárol. Az tárolt elem típusa az A típusparaméterben példányosításkor megadott típus lesz.

class StoreSomething<A> { A something; StoreSomething( A something ) { this.something = something; } void set( A something ) { this.something = something; } A get() { return something; } }

A generic átfordítása című fejezetben két módszert is láthatunk amivel szimulálni tudjuk Java-ban a paraméterezett osztályokat. Mennyivel szebb a Pizza megoldása.

A példányosítás úgy történik, hogy a típus neve után < és > jelek között felsoroljuk az aktuális típusparamétereket. Vegyük észre, hogy amikor allokálunk egy paraméterezett osztálybeli objektumot, akkor nem kell kiírni a típusparamétereket. Ezt a fordító a konstruktor argumentumainak típusából kideríti. Eltérően a Sun Java szabványba bevezetett genericektől, új objektumpéldány létrehozásakor a Pizza fordító hibát jelez, ha típus paramétert próbálunk megadni.

StoreSomething<String> a = new StoreSomething("I'm a string!"); StoreSomething<int> b = new StoreSomething(17+4); StoreSomething<StoreSomething<char>> c = new StoreSomething(new StoreSomething('c')); c.get().set('d'); b.set(9); int i = b.get(); String s = a.get();

Lehetőségünk van polimorf osztályból örököltetni is:

class StoreSomething2<A> extends StoreSomething<A> { StoreSomething2( A something ) { super(something); } void print() { System.out.println(""+something); } }

Megszorított polimorfizmus (bounded polymorphism)

Néha szükségünk van arra, hogy csak bizonyos feltételeket kielégítő típusokkal lehessen paraméterezni egy polimorf osztályt. Ez Pizza-ban úgy jelenik meg, hogy a típusparaméterre előírhatjuk, hogy milyen interfészt (sajnos csak egyet) implementáljon (ill. milyen osztálynak legyen a leszármazottja). A paraméter típusunkat a következő interfészhez kötjük:

interface Comparable { boolean equals(Object x); boolean less(Object x); }

Ezek után a halmazunk elemeit erre korlátozzuk:

interface Set<A implements Comparable> { boolean contains(A x); Set<A> include(A x); }

Ez a deklaráció azt jelenti, hogy a Set típusparamétere csak olyan típus lehet, ami implementálja a Comparable interfészt. Ezután írhatunk például ilyesmit:

abstract class BoundSet<A implements Comparable> implements Set<A> { public abstract boolean contains(A x); public abstract BoundSet<A> insert (A x); public Set<A> include(A x) { return insert(x); } }

De ezt csak olyan osztállyal példányosíthatjuk, ami implementálja a Comparable-t. Ha nincs ilyen, akkor nekünk kell ilyet írni:

class ComparableString implements Comparable { private String s; ComparableString( String s ) { this.s = s; } public boolean less( Object other ) { if ( other instanceof ComparableString ) return s.compareTo(((ComparableString)other).s) < 0; else throw new Error("can't compare to non-strings"); } } public class TestForDuplicates { public static void main( String[] args ) { Set<ComparableString> set = new MyEmptySet(); for ( int i = 1; i < args.length; i++ ) set.include(new ComparableString(args[i])); System.out.println( set.contains(new ComparableString(args[0]))); } }

F-megszorított polimorfizmus (F-bounded polymorphism)

Mint láthattuk a ComparableString-ben van néhány ronda típusellenőrzés. Ezt elkerülhetnénk, ha tudnánk paraméterezni a Comparable interfészt. És valóban, a kötött változó előfordulhat a megszorító kifejezésben. A típusra vonatkozó megszorítás tehát rekurzív is lehet. Például:

interface Comparable<A> { boolean less(A x); } interface Set<A implements Comparable<A>> { boolean contains(A x); Set<A> include(A x); }

Most a ComparableString osztályt definiálhatjuk az alábbi módon:

class ComparableString implements Comparable<ComparableString> { private String s; ComparableString( String s ) { this.s = s; } public boolean less( ComparableString other ) { return s.compareTo(other.s) < 0; } }

Az F-kötött polimorfizmust ritkán használják a gyakorlatban.

Polimorf függvények

A típusváltozókat csak dinamikus függvényekhez, blokkokhoz és inicializálókhoz használhatjuk. Statikushoz azért nem, mert ott nincs aktuális példány. Néha szükséges azonban a polimorf statikus függvények használata is. Például ha olyan dinamikus függvényt szeretnénk, ami az aktuális példánytól függetlenül polimorf. Ezt úgy érhetjük el, hogy a függvény visszatérési típusa elé beírjuk a típusváltozókat:

class TreeUtils { static <A implements Comparable<A>> Tree<A> insertArray(Tree<A> tree, A[] elems) { for (int i = 0; i < elems.length; i++) tree = tree.insert(elems[i]); return tree; } }

Megkötések a paraméteres típusokra

A paraméteres típusokat kétféleképpen lehet implementálni:

Sajnos a homogén átfordításnál felmerültek bizonyos problémák. A generikus tömböknél gondot okozna, ha primitív típussal próbálnánk példányosítani. Wrapper osztályt kellene létrehozni ilyen esetekben, viszont ekkor a castolások válnak lehetetlenné konstans időben, ezért a Pizza tervezői elvetették ezt a lehetőséget. Tehát generikus tömböt nem lehet létrehozni.

class Queue<A> { A queue[]; Queue(int n) { queue = new A[n]; } ... }

Ez nem működik. Továbbá castolni se lehet parametrikus típusra. Azaz (Tree<long>)intTree-t nem lehet használni.

Generic átfordítása

A Pizza tervezői eredetileg közvetlenül a JVM-re akartak fordítani, de mivel a JVM és a Java szorosan kapcsolódik egymáshoz, ezért úgy döntöttek, hogy inkább első lépésben Java kódra átfordítják a Pizza kódot, majd onnan tovább a JVM-re. Ezzel ugyan vesztettek a kód hatékonyságából, de sokat nyertek az érthetőség terén. Két módja is van az átfordításnak: a heterogén és a homogén. Heterogén átfordítás esetén minden típushoz (paraméterezett) külön kódot generál a fordító. Így nagy, de hatékony kódot kapunk. Homogén átfordítás esetén egyetlen kód felel az általános reprezentációért, éppen ezért kicsi, de kevésbé hatékony kód lesz az eredmény. A két módszer keverése lehetséges, így a programozó egyensúlyozni tud a méret és a hatékonyság között. A legjobb választás, ha a heterogén átfordítást választjuk a primitív típusokra (int, char, ...), és a homogént a referencia típusokra. Persze csak a fordító paraméterezésével lehet választani a két módszer között.

Parametrikus polimorfizmus átfordítása

Alappélda: A Pair osztálynak van egy típusparamétere, az elem. Ez az osztály tartalmaz két elem típusú tagot, x és y. A konstruktora két paraméterével inicializálja őket. A swap() függvény megcseréli a két értéket. A példa végén található egy kis teszt programrészlet, amely példányosítja a Pair osztályt egy String és egy int típussal. Az eredmény:

Hello, world!
42

class Pair<elem> { elem x, elem y; Pair( elem x, elem y ) { this.x = x; this.y = y; } void swap() { elem t = x; x = y; y = t; } } //test Pair p = new Pair("world!", "Hello, "); p.swap(); System.out.println(p.x + p.y); Pair q = new Pair( 22, 64 ); q.swap(); System.out.println( q.x - q.y );

Most lássuk milyen kódot kapunk a két módszerrel:

Heterogén átfordítás

A Pair osztály minden példánynak generálunk egy új osztályt. A Pair<String> és a Pair<int> példányosításból a Pair_String és a Pair_int osztályok keletkeznek. Valójában nem így generálódnak a példányosított nevek, de hasonlóan. Ha nem használunk $ jelet, akkor nem fordul elő névütközés saját osztály és egy példány között. Az új osztályok törzsében az elem típusváltozókat lecseréljük az aktuális paraméterre, vagyis String-re és int-re. A forráskódban a példányosításokat pedig az új osztálynevekre.

class Pair_String { String x; String y; Pair_String( String x, String y ) { this.x = x; this.y = y; } void swap() { String t = x; x = y; y = t; } } class Pair_int { int x; int y; Pair_int( int x, int y ) { this.x = x; this.y = y; } void swap() { int t = x; x = y; y = t; } } Pair_String p = new Pair_String("world!", "Hello,"); p.swap(); System.out.println(p.x + p.y); Pair_int q = new Pair_int(22, 64); q.swap(); System.out.println(q.x - q.y);
Homogén átfordítás

Ennél a módszernél csak egy osztályt hozunk létre egy parametrikus osztályhoz, ez fogja az összes példányosítást kezelni. Az egésznek a kulcsa az, hogy minden típus konvertálható Object-re és vissza. A típus paraméterek előfordulásait a generic osztály kódrészében lecseréljük Object-re és a törzsében minden paraméterezett típusú változót Object-re konvertálunk. A konkrét példányoknál meg a megfelelő típusra konvertálnunk vissza. Referencia típus esetén a konvertálás egy egyszerű cast. Primitív típus esetén egy kis trükköt kell alkalmazni. Ha például a v változó int típusú, akkor Object-re (Object)(new Integer(v))-vel lehet konvertálni, visszafele pedig ((Integer)o).intValue-val.

class Pair { Object x; Object y; Pair( Object x, Object y ) { this.x = x; this.y = y; } void swap() { Object t = x; x = y; y = t; } } Pair p = new Pair((Object)"world!", (Object)"Hello,"); p.swap(); System.out.println((String)p.x + (String)p.y); Pair q = new Pair((Object)new Integer(22), (Object)new Integer(64)); q.swap(); System.out.println(((Integer)(q.x)).intValue() - ((Integer)(q.y)).intValue());

Megszorított parametrikus polimorfizmus átfordítása

Kicsit módosítjuk az előző példánkat. Meg akarjuk találni egy pár elem közül a kisebbiket. Az Ord interfésznek van egy típus paramétere elem és definiál egy less műveletet. A Pair osztályunknak szintén van egy típusparamétere (elem), de itt meg van szorítva olyan típusokra amik implementálják az Ord<elem> interfészt. Mint látjuk ez egy F-megszorított polimorfizmus.

interface Ord<elem> { boolean less(elem o); } class Pair<elem implements Ord<elem>> { elem x; elem y; Pair ( elem x, elem y ) { this.x = x; this.y = y; } elem min() { if ( x.less( y ) ) return x; else return y; } } class OrdInt implements Ord<OrdInt> { int i; OrdInt ( int i ) { this.i = i; } int intValue() { return i; } public boolean less( OrdInt o ) { return i < o.intValue(); } } //test Pair<OrdInt> p = new Pair( new OrdInt(22), new OrdInt(64) ); System.out.println( p.min().intValue() );
Heterogén átfordítás

Láthatjuk a példában, hogy a Pair<OrdInt> és az Ord<OrdInt> példányosítás fordul elő, ezért létrehozunk nekik egy új osztályt Pair_OrdInt, illetve egy interfészt Ord_OrdInt. Az új példányokat hasonlóan generáljuk, mint a parametrikus polimorfizmus heterogén átfordításánál. Mint látjuk az Ord_OrdInt interfésznek semmi különleges szerepe nincs az új kódban, így azt eltávolíthatjuk a hivatkozásaival együtt.

interface Ord_OrdInt { boolean less(OrdInt o); } class Pair_OrdInt { OrdInt x; OrdInt y; Pair_OrdInt ( OrdInt x, OrdInt y ) { this.x = x; this.y = y; } OrdInt min() { if ( x.less( y ) ) return x; else return y; } } class OrdInt implements Ord_OrdInt { int i; OrdInt ( int i ) { this.i = i; } int intValue() { return i; } boolean less( OrdInt o ) { return i < o.intValue(); } } Pair_OrdInt p = new Pair_OrdInt( new OrdInt(22), new OrdInt(64) ); System.out.println( p.min().intValue() );
Homogén átfordítás

Az Ord interfészben a megszorítatlan típusparaméter Object-re cserélődik. A Pair osztályban a megszorított típusparaméter a megszorításra cserélődik, Ord-ra. Az Ord interfészben a less függvény Object típusú argumentumot vár, míg az OrdInt osztályban OrdInt-et. Ezt úgy kerüljük el, hogy az Ord interfészben a less függvényt átnevezzük less_Ord-ra, az OrdInt osztályban pedig felvesszük a less_Ord függvényt.

interface Ord { boolean less_Ord(Object o); } class Pair { Ord x; Ord y; Pair ( Ord x, Ord y ) { this.x = x; this.y = y; } Ord min() { if ( x.less_Ord( y ) ) return x; else return y; } } class OrdInt implements Ord { int i; OrdInt ( int i ) { this.i = i; } int intValue() { return i; } boolean less( OrdInt o ) { return i < o.intValue(); } boolean less_Ord( Object o ) { return this.less( (OrdInt)o ); } } Pair p = new Pair( new OrdInt(22), new OrdInt(64) ); System.out.println(( (OrdInt)(p.min())).intValue() );