09 - tailrec method, private, protec, seal¶
Ahogy előadáson láttuk, tudunk implementálni egy immutable láncolt
Int
listát egy traittel, egy case objecttel és egy case classal, induljunk ki az
itteni állapotból:
1 2 3 4 5 6 7 8 9 |
|
Cons
-nak nevezni, ezért tartsuk mi is ezt a jó szokást.
Most ezzel az osztállyal fogunk dolgozni, egyre jobban kibővítjük és gyakoroljuk a
mintaillesztést is.
tail rekurzív implementációk¶
Hogy tesztelni tudjuk a következő feladatok megoldásainak a stackkel kapcsolatos viselkedését,
először is implementáljunk egy függvényt, mely paraméterben kap egy n
számot és
visszaadja az (1,2,3,...,n)
listát! Úgy oldjuk meg a feladatot, hogy pl. egy
20.000 hosszú lista létrehozására is képesek legyünk. Figyeljünk a sorrendre.
Itt is és a többi feladatban is, ellenőrizzük a tesztesetek segítségével, hogy
implementációnk helyes-e!
1 2 3 4 5 6 7 |
|
Válasz mutatása
Ha most generálunk egy 20.000 hosszú listát és kiszámítattjuk az összegét, akkor
szintén betelik a call stack. Alapvetően az idea terminológiájában nem ,,rekurzív''
így a sum
függvény, de persze ugyanúgy telik a stack, mint mikor előadáson
tapasztaltuk a sum
függvénynél, ahogy tölti a stacket. Nevezzük ,,tail rekurzívnak''
akkor is egy osztály tagfüggvényét, ha egy másik példánynak hívja az ugyanolyan nevű
tagfüggvényét, tail rekurzív módon, azaz ha a függvényhívás után nem végez semmi további
műveletet, hanem maga a kiértékelt függvény értéke lesz a visszatérési érték!
Próbáljunk meg egy olyan ,,tail rekurzív'' sum
implementációt készíteni, mely
nem dob stacktracet hosszú listán sem.
Az első ötlet lehetne a következő: adjunk az IntList
traitnek egy sum( n: Int )
metódust,
mely visszaadja a lista összegét plusz n
-t! Próbáljuk követni a ,,tail rekurzív'' módszert.
Hogy implementáljuk ezt a metódust?
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Válasz mutatása
Szemre nagyon hasonlít egy tail rekurzív kódhoz: a sum függvény ,,kapott még egy paramétert'', melybe gyűjti az összeget. Ha egy 20 méretű listára futtatjuk le, ki is számítja a lista összeget, de hosszú listára továbbra is stacktracet dob!
Miért lehet ez?
Válasz mutatása
Viszont ha a fordító látja, hogy a Cons.sum
-ban a Cons.sum
-ot hívjuk, nem pedig az
IntList.sum
-ot, akkor azt talán ki tudja optimalizálni! Ezt mintaillesztéssel el tudjuk érni.
Hogyan?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Válasz mutatása
Ígéretes, hogy az idea tailrecnek jelöli a függvényt, más függvényhívás pedig nincs benne, így joggal feltételezhetjük, hogy minden rendben lesz, ha ezt hívjuk egy 20.000-es listán, igaz? Puding próbája az evés:
A tanulság, hogy ne higgyünk mindig az ideának és teszteljük is, hogy amiket úgy gondolunk, hogy a fordító elvégez optimalizálást, azt teszteljük. Ez egyben egy másik jó érv a tailrec annotáció használatóra is, ugyanis ha azt is beírjuk, azt látjuk, hogy nem fordul:
final metódusok¶
Amiért a fordító nem tudja elvégezni ezt a tail call optimalizálást, az a következő:
ugyan azt biztosítottuk, hogy a sum
hívás már nem lehet Empty.sum
, hanem egy
Cons
típusú objektum sum
metódusát fogjuk hívni. Csakhogy ugyanúgy, ahogy az
IntList
trait sum
függvényét overrideolhatjuk, akkor is, ha van neki default
implementációja, az egy elvileg elképzelhető forgatókönyv, hogy a Cons
típusnak
egyszer valamikor létrehozzuk egy altípusát és azon belül tovább overrideoljuk a
sum
metódust! Ilyenkor ez a tail rekurzívnak látszó hívás nem ezt a Cons.sum
metódust hívná tovább, hanem az altípusban implementált sum
metódust (pontosan úgy,
ahogy eredetileg a tail.sum
híváskor tail
formailag ugyan IntList
, de nem az ottani
- amúgy nem is implementált - metódus fog futni, hanem a leszármazott osztályban, az
altípusban, a tényleges típusban implementált metódus, jelen állás szerint vagy az
Empty.sum
, vagy a Cons.sum
). Mivel pedig a fordító nem tudja kizárni azt a lehetőséget,
hogy valahol egyszer lesz egy ilyen altípusa a Cons
nak, ahol overrideolni tudjuk,
ezért nem tudja tail call opimalizálni.
De a hover üzenetben olvashatjuk is a megoldást: a metódus elé írt final
kulcsszó
pontosan azt jelenti, hogy az adott metódus nem lesz overrideolható leszármazott típusokban.
Lehet, hogy erre van szükségünk:
Ha lefuttatjuk az összegző függvényt egy húszezres elemű listára, azt kapjuk, hogy ez így szépen összegzi is a listát, nem dob stacktracet.
Tehát ha egy osztályban implementált metódust szeretnénk, hogy tail call optimalizáljon a fordító, akkor mit kell pl. biztosítsunk?
Válasz mutatása
hide and protect your private parts¶
Van ennek az implementációnak még legalább
egy szépséghibája: az, hogy most már az osztályunk felhasználói kaptak egy sum( Int )
függvényt,
amit csak helper függvénynek szántunk, és alapvetően nincs értelme megmutatnunk nekik.
Korábban azzal védtük ki, hogy lássák, hogy beraktuk a helper függvényt egy másik függvény
belsejébe, úgy nem látszott - de ezt most nem tudjuk megtenni, mert a t.sum
híváshoz
szükség van arra, hogy a másik példánynak mi meg tudjuk hívni a függvényét.
Észrevehetjük azt is, hogy valójában nincs szükség arra, hogy a traitben vagy az Emptyben
legyen ilyen függvényünk: ez a helper függvény csak a Cons
osztályon belül szükséges.
Első lépésben ki is törölhetjük onnan, ahol nem kell, persze így már nem lesz overrideolt
metódus:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
@tailrec
annotáció is rendben van. Ha teszteljük hosszú
listán az összegzést, azt látjuk, hogy ez így rendben van.
Amit elértünk és amit nem:
- Most már nincs az
IntList
osztálynaksum( n: Int )
metódusa, így ha ilyen típusú értékünk van, annak már csak asum
metódusát tudjuk meghívni explicit. - Viszont ha
Cons
unk van, azon még elérjük ezt a helper metódust:Cons(7,Empty).sum(4)
fordul és kiértékeli11
-re. Ezt nem szeretnénk, mert ez a függvény nem kéne része legyen az osztály interface-ének, csak a belső implementációhoz kell nekünk, aki a lista osztályt fejlesztjük.
Van rá mód, hogy ezt elérjük: a private
kulcsszót egy metódus elé írva pontosan
azt érjük el, hogy az adott metódust kizárólag az adott osztály kódjából érhetjük
el:
1 2 3 4 5 6 7 8 |
|
println( Cons(4,Empty).sum(7) )
hívás, mert a privát
metódust nem látjuk máshonnan, csak az adott osztály belsejéből.
Egy hasonló másik láthatósági módosító a protected
: ha egy metódust ezzel látunk el,
akkor azt érjük el, hogy azt csak az adott osztály és leszármazott osztályainak a kódjából
érjük el.
A kettő közül ha azt szeretnénk, hogy külső felhasználó ne érje el a sum
metódust,
melyiket használnánk az IntList
traitben?
Válasz mutatása
A fentiekből logikusnak tűnik feltételezni, hogy privát metódust is tud tail call optimalizálni a Scala fordító és tényleg tud:
1 2 3 4 5 6 7 8 |
|
sum
metódus, ha hosszú listára hívjuk, ebből a szempontból
rájön, hogy ha privát, akkor nem fogjuk overrideolni leszármazott osztályban, hiszen
ott nem is látszik. (Ha protected
lenne final
nélkül a metódus, akkor nem fordulna
le a @tailrec
annotációnál a függvény, anélkül pedig dobja a stacktracet hosszú listára.)
seal the trait¶
Még egy pont van, ahol ez a kódunk elpusztulhat: ha valaki szintén kiterjeszti valahol máshol
az IntList
traitet és pl jóhiszeműen (rekurzívan vagy sem) implementálja benne ő is a sum
függvényt.
Sejtjük, hogy mi lesz ekkor a probléma?
Válasz mutatása
Meg tudjuk oldani, hogy az implementációnk akkor is működjön, ha valaki más is kiterjeszti
az IntList
et?
1 2 3 4 5 6 7 8 9 |
|
Válasz mutatása
Van egy másik opció is: ha úgy gondoljuk, hogy a traitünket senki másnak nem kéne kiterjeszteni,
akkor erre való a sealed
módosító, melyet traitek elé írhatunk: sealed traitet csak abban
a forrásfile-ban lehet extendelni, melyben ő szerepel.
Tehát ha biztosak vagyunk abban, hogy ez a trait csak a mienk kell legyen és megcsináljuk az összes leszármazott típusát, akkor lezárhatjuk:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Ilyen esetekben a sealed
kulcsszó használata azért is előnyös, mert a Scala fordító
egyszerűbb mintaillesztéseknél rájöhet, ha egy IntListre matchelünk és nem kezelünk minden esetet
és ilyenkor dob egy warningot. Nem teljeskörű ez a vizsgálata: ha pl. van typecast egy caseben
(mint most a case t : Cons
), akkor nem fogja tudni megvizsgálni, hogy minden eshetőségre
fel vagyunk-e készülve, ahogy az if
guardok is kikapcsolják ezt a képességét.