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
trait IntList {
  def sum: Int
}
case object Empty extends IntList {
  override val sum = 0  
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = head + tail.sum
}

Szokás a "nemüres listát" 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!

A kérés miatt ezt is tail rekurzív belső függvénnyel implementáljuk. A szokásos if-else konstrukció helyett most a mintamegoldásban mintaillesztést használunk Intre, csak hogy lássuk, lehet ilyet is:

1
2
3
4
5
6
7
def createList( n: Int ): IntList = {
  def createTail( i: Int, list: IntList ): IntList = i match {
    case 0 => list
    case _ => createTail( i-1, Cons(i,list) )
  }
  createTail( n, Empty )
}

Figyeljük meg a sorrendet! Mivel a listát ,,a végéről kezdve'' építjük, először az n elemet kell beszúrjuk fejnek, majd az n-1-et stb - ezért a belső függvény egy fentről lefelé számoló ,,for ciklusnak'' felel meg.

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
trait IntList {
  def sum: Int
  def sum( n: Int ): Int
}
case object Empty extends IntList {
  override val sum = 0
  override def sum( n: Int ) = n
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  override def sum( n: Int ) = tail.sum( n + head )
}

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?

Mert a Scala fordító csak akkor optimalizálja a tail callokat függvényhívás helyett ,,goto''ra, ha *ténylegesen ugyanazt a függvényt hívjuk rekurzívan*. Itt **nem ez történik**! A `Cons.sum( n: Int )` függvényben a `tail.sum( n: Int )` hívás az nem a `Cons`-beli, hanem az `IntList`-beli `sum` függvényt hívja, ami majd csak **futásidőben** dől el, hogy éppen az `Empty` vagy a `Cons` overrideját hívja meg. Erre a Scala fordító nem képes. 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
trait IntList {
  def sum: Int
  def sum( n: Int ): Int
}
case object Empty extends IntList {
  override val sum = 0
  override def sum( n: Int ) = n
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  override def sum( n: Int ) = tail match {  //tail _típusától_ függően kezeljük:
    case Empty => n + head                   //ha üres, akkor az összeg head, plusz n
    case t : Cons => t.sum( n + head )       //ha nemüres, akkor az előző rekurzió
  }
}

Figyeljük meg: a Cons.sum( Int ) függvényben a mintaillesztés második esetében azt ellenőrizzük, hogy a tail-ben egy Cons van-e, és ha igen, akkor azt elnevezzük t-vel, így a match case jobb oldalán a kifejezésben a t az ugyanúgy a tail, mint amire az eredeti kódban is hívtuk a sum( Int ) függvényt, de már ismerten Cons típusú és ezért a Scala fordító (és az idea is) tail rekurzívnak ismeri fel:

tailrec sum method

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:

hát nem

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:

tailrec annotáció 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 Consnak, 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:

final jó lesz

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?

Azt, hogy a metódus maga final legyen, és (pl. mintaillesztéssel) garantáljuk azt is, hogy a rekurzív hívás ténylegesen ennek az osztálynak ezt a metódusát hívja, nem pedig polimorf módon valamelyik felmenő-belit. 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
trait IntList {
  def sum: Int
}
case object Empty extends IntList {
  override val sum = 0
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  @tailrec
  final def sum( n: Int ): Int = tail match {  //ki kell írnunk most már a return typeot
    case Empty => n + head
    case t : Cons => t.sum( n + head )
  }
}

Persze érdemes tesztelni is, hogy még mindig kioptimalizálja-e a tail callt a fordító, mondjuk az jó jel, hogy a @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álynak sum( n: Int ) metódusa, így ha ilyen típusú értékünk van, annak már csak a sum metódusát tudjuk meghívni explicit.
  • Viszont ha Consunk van, azon még elérjük ezt a helper metódust: Cons(7,Empty).sum(4) fordul és kiértékeli 11-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
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  @tailrec
  private final def sum( n: Int ): Int = tail match {
    case Empty => n + head
    case t : Cons => t.sum( n + head )
  }
}

Így már nem fog fordulni ,,kint'' a 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?

Csak a protectednek van értelme. A traitben deklarált sum metódusunk absztrakt, ami azt jelenti, nincs implementálva - ha priváttá tennénk, akkor nem tudjuk overrideolni sem az Empty, sem a Cons osztályokban, mert nem is látnak rá, így nem tudják implementálni sem.

Ezért a fordító nem is engedi absztrakt metódus priváttá tételét, hiszen azzal elérnénk, hogy abból a típusból egyetlen példányt se tudnánk soha létrehozni.

A protected viszont rendben van: ha az IntList-ben a sum fejléce protected def sum: Int lenne, akkor

  • az Empty és a Cons osztályok mivel extendelik az IntListet, látnák, tudják overrideolni, ugyanúgy, ahogy most,
  • mások viszont nem látnák ezt a metódust és nem hívhatnák meg.

Persze ennek konkrétan az összegző függvényben nincs értelme, mert azt azért készítjük, hogy mások meghívják, de helper/implementációfüggő függvényeket rejtsünk el, a protected jellemzően jó választás lesz erre, ha azt szeretnénk, hogy a leszármazott osztályokban is tudjuk hívni és esetleg overrideolni a metódust (ha utóbbit nem akarjuk, lehet kombinálni és protected finallá tenni a metódust, that's fine).

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
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  @tailrec
  private def sum( n: Int ): Int = tail match {
    case Empty => n + head
    case t : Cons => t.sum( n + head )
  }
}

Így se dob stacktracet a 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?

Ha úgy építünk egy Cons( head, tail ) elemet, hogy ez a tail az a bizonyos harmadik, kezeletlen új típus, akkor ezen az objektumon a sum függvény egy MatchErrort fog dobni. A jelenlegi implementáció arra számít, hogy a lista az vagy Empty, vagy Cons, más nem lehet. 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 IntListet?

Egy harmadik ,,joker'' case bevezetésével igen: ott jobb híján meghívjuk a tail összegzőjét és hozzáadjuk a fejet, mint amit amúgy is csináltunk:

1
2
3
4
5
6
7
8
9
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum = sum(0)
  @tailrec
  private def sum( n: Int ): Int = tail match {
    case Empty => n + head
    case t : Cons => t.sum( n + head )
    case _ => n + tail.sum  //tail ismeretlen IntList, csak azt tudjuk, hogy van sum függvénye
  }
}

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
sealed trait IntList {  //sealed
  def sum: Int
}
case object Empty extends IntList {
  override val sum = 0
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def sum: Int = sum(0)
  @tailrec
  private def sum( n: Int ): Int = tail match {
    case Empty => n + head
    case t : Cons => t.sum( n + head )
  }
}

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.


Utolsó frissítés: 2021-02-07 23:06:47