Kihagyás

05 - tailrec és tesztek

Láttuk előadáson, hogy ha rekurzív függvényt írunk, preferáljuk, ha tail rekurzív.

Első feladatként írjuk meg a faktoriális függvényt is tail rekurzívan, mondjuk az előadás összegző függvénye alapján!

1
2
3
4
def fakt( n: Int, acc: Int ): Int = 
  if ( n <= 1 ) acc else fakt( n-1, n*acc )

def fakt( n: Int ): Int = fakt( n, 1 )
Válasz mutatása

Scalában lehetőség van arra, hogy függvényen belül függvényt deklaráljunk, olyankor, amikor alapvetően egy ,,helper'' függvényt ,,kintről'' nem szeretnénk, hogy bárki meghívjon, ez egy jó módja az elrejtésének. Tegyük meg!

1
2
3
4
5
def fakt( n: Int ): Int = {
  def fakt( n: Int, acc: Int ): Int = 
    if ( n <= 1 ) acc else fakt( n-1, n*acc )
  fakt( n, 1 )
}
Válasz mutatása

Jól látható, hogy a fakt függvényen belül eredetileg egy kifejezés volt: fakt(n,1), így pedig már két részből áll a függvény törzse: először a belső függvény deklarációja, majd maga a kifejezés áll. Ezért kapcsosba kell rakjuk a függvény törzsét.

annotáció

A kód működését érdemben nem változtatja meg, csak a fordító számára ad ki újabb feladatokat egy úgynevezett annotáció, aminek a fogalmát egy példán keresztül érthetjük meg jobban: most például van a belső fakt( n: Int, acc: Int ) függvényünk, ami szándékunk szerint tail rekurzív. Ilyenkor jó programozási gyakorlat ezt jelezni is, azzal, hogy a metódus elé írjuk, hogy @tailrec (az annotációk ismertetőjele általánosságban az, hogy @-tel kezdődnek). Mivel maguk az annotációk is Scala elemek (a tailrec épp egy ,,osztály''), így ők is valahol szerepelnek a package hierarchiában. A tailrec esetében ez a hely a scala.annotation.tailrec: mivel nem ugyanebben a csomagban dolgozunk, ezért őt vagy be kell importoljuk, vagy mindig ezen a teljes nevén kell emlegetnünk. Jó gyakorlat beimportolni a standard osztályok közül azokat, melyeket használunk a forrásfileunkban, olvashatóbb kódot eredményez:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
package week01

import scala.annotation.tailrec

object Gyakorlat extends App {
  def fakt( n: Int ): Int = {
    @tailrec
    def fakt( n: Int, acc: Int ): Int = 
      if ( n <= 1 ) acc else fakt( n-1, n*acc )
    fakt( n, 1 )
  }  
}

Note: ha használjuk az idea automatikus kiegészítését, és mikor felajánlja a tailrecet, elfogadjuk, akkor automatikusan behúzza az import sort is a forrásfile elejére.

A @tailrec beírásával azt érjük el, hogy a fordító ellenőrzi is nekünk, hogy a függvény, ami előtt ez az annotáció szerepel, valóban tail rekurzív-e. Ha az, akkor minden rendben; ha nem (akár azért, mert nem is rekurzív, akár azért, mert nem minden rekurzív hívás van végpozícióban), akkor fordítási hibával tér vissza, ahogy az alábbi képen látjuk, ha ráhoverelünk a pirossal aláhúzott rekurzív hívásra:

nem is tailrec

Az annotáció nélkül ez a kód persze nem dob hibát.

A fenti képen a 28. és 33. sor margóján a két bekarikázott ,,loop'' logó azt mutatja, hogy (ha ideát használunk) a fejlesztőkörnyezet maga is megjeleníti nekünk, ha tail rekurzív (28. sor melletti piktogram) vagy ,,általános'' rekurzív (33. sor melletti piktogram) egy-egy függvényünk, ezzel is segít. A rajzon is látszik, hogy az általános rekurzió egy becsavarodósabb loop, ha ilyet írunk (fogunk), akkor azt mindenképp biztosítsuk, hogy ezzel ne lehessen több tízezres mélységbe menni, mert akkor kapunk egy stacktracet és le fog állni a programunk.

fibonacci

Következő feladatként implementáljuk a Fibonacci sorozatot: f(0)=f(1)=1 és minden további n-re f(n)=f(n-1)+f(n-2)!

Ha nem tail rekurzióban gondolkodunk, akkor mi a kézenfekvő implementáció?

1
2
def f( n: Int ): Int = 
  if( n <= 1 ) 1 else f(n-1) + f(n-2)
Válasz mutatása

A fenti kód vajon tail rekurzív?

Nem az: pl. az `f(n-1)` hívás eredménye nem a kifejezés értéke lesz, hanem még tovább dolgozunk rajta (konkrétan hozzáadjuk `f(n-2)` értékét - hogy ez az utóbbi is rekurzív hívás, az nem számít ebből a szempontból, ha `1+f(n-1)` lenne a kifejezésünk, az se lenne tail rekurzív). Válasz mutatása

De honnan tudjuk egy komplikáltabb feladatnál, hogy a kódunk helyes?

tesztesetek

A letölthető gyakorlati zipben tesztesetek segítik annak ellenőrzését, hogy implementációnk helyes-e. Nem minden esetben teljes körű, és később az is része lesz a feladatban, hogy mi magunk írjunk tesztesetet a kódunkhoz. A Fibonacci feladathoz vannak teszteseteink, ezeknek a standard helye a test.scala. könyvtáron belül van; ha az ajánlott módon hoztuk létre a projektet, akkor a projektstruktúrában az idea zölddel jelzi, hogy az ebben a könyvtárban szereplő forrásfileokban tesztesetek vannak:

a forrás kék, a teszt zöld

Ha belekattintunk az aktuális csomaghoz tartozó teszt fileba, akkor láthatjuk, hogy tesztesetek megadása Scalában nem nagy ördöngösség (több mindennek köszönhetően ilyen kényelmes a szintaxis): miután megvan a teszt osztályunknak a kerete, egyszerűen csak listáznunk kell

  • a tesztelt feature nevét, azt adunk neki, amit szeretnénk, ez egy String,
  • a should szót (később látni fogjuk, hogy ez egy metódusnak a neve a teszt osztályban),
  • magának az egyedi tesztesetnek a nevét, ez is egy String ízlés szerint,
  • az in szót (ez is egy metódusnak lesz a neve),
  • és végül egy kifejezést, amit a teszteset kiértékel, ha futtatjuk:

teszteset

Például fentebb a 24. sorban a "fibonacci" should "be 0 -> 1" in assert( Gyakorlat.fib(0) == 1 ) egy teszteset; a feature, amit tesztelünk, a "fibonacci", ez a konkrét teszteset pedig azt ellenőrzi, hogy fib(0) == 1 teljesül-e, ezt a szöveges leírás is megadja.

assert it

Ebből a kódból ami számunkra ismeretlen lehet még, az az assert függvény; ez futásidőben kiértékeli a paraméterként kapott Boolean kifejezést (most azt, hogy fib(0)==1), ha igaz, akkor minden rendben van, ha viszont hamis, akkor ez a teszteset failni fog.

Amit még láthatunk, a 25-28. sorban az it: ez egy shorthand arra, hogy még mindig ugyanazt a featuret teszteljük, mint amit a korábbi tesztesetben tettünk.

futtatás

A tesztek futtatása hasonlóan megy, mint mikor az Appot futtajuk: létrehozhatunk neki kézzel egy run configurationt, de van rá kényelmesebb mód: jobb klikk a teszteset file nevére a projektstruktúrában, ajd a "Run" menüpont választása (fenti shoton bekarikázott rész).

miért fordul: ???

Először is, hol van a hivatkozott Gyakorlat.fib függvény?

  • A tesztesetet tartalmazó scala file maga a test/scala/week02 könyvtáron belül van.
  • Ebből a részből a test/scala könyvtár Test sources-nek van megjelölve a build pathon.
  • Így ez a file a week02 package-ben lesz, egyébként ennek megfelelően első sora az is, hogy package week02.
  • Ez ugyanaz a csomag, mint a main/scala/week02 által mutatott week02 csomag, így az ottani Gyakorlat objektum fib függvényét fogja keresni; mivel ugyanaz a csomag, ezért ezt külön nem kell beimportálnunk, nem kell week02.Gyakorlat.fib-ként hivatkozunk a függvényre.

Ha belenézünk a main/scala/week02/Gyakorlat.scala forrásfile-ba, ezt látjuk:

the what

Tehát,

  • a tesztesetek fordulnak, mert a Gyakorlat objektumon belül tényleg van egy fib függvény, ami tényleg Intet vár és azt is ad vissza, ahogy a tesztek assertjein belül szerepel is.
  • maga a függvény azért fordul, mert a ??? Scalában egy előre definiált függvény, ami minden típusnak megfelel és ha ráfut a vezérlés, akkor hibát dob. (Később, az osztályhierarchiáknál látni fogjuk, hogy ez azért van, mert Nothing típusú, ami minden más típusnak leszármazottja és nem csinál mást, csak dob egy UnimplementedMethod kivételt.)

Emiatt egy jó fejlesztési metodika lehet a következő:

  • létrehozzuk a main/scala sources folderben az objektumot, amit éppen készítünk, vagy annak a feature-jeit, egyelőre csak olyan módon, hogy megírjuk a ,,kintről'', ,,mások számára'' látható függvényeinek a fejlécét,
  • minden függvény után az = ??? ,,törzset'' írjuk, így a függvények maguk már létezni fognak, de ha bárki bármikor meghívja őket, hibát fognak jelezni error formájában (amit pl egy assert le fog jelenteni, hogy ez a függvény nincs még implementálva),
  • ezután megírjuk a teszteseteket, amikbe a fentinek megfelelő módon írunk elvárt viselkedést, assertek használatával, ezt a test/scala test sources folderen belül,
  • ezután implementáljuk a featuret, majd teszteljük.

fibonacci tesztelés

Ha tehát futtatjuk a teszteseteket, ezt látjuk:

failelt minden

A kép bal felső sarokban látható két (bekarikázott) gombot érdemes megnézni, mindkettő be van-e nyomva, alapból a pipás vélhetően nem lesz; ha a pipa be van nyomva, akkor mutatja azokat a teszteseteket is, melyek átmentek, ha a várakoznitilos be van nyomva, akkor a failelt teszteseteket is mutatja.

Azt látjuk tehát, hogy a "Fibonacci" nevű feature teszt alatt volt öt tesztesetünk, mindegyiknek van egy saját neve, ami egybecseng azzal, amit megírtunk fentebb, piros felkiáltójel jelzi, hogy a teszteset failelt, és ha rákattintunk, a konzol ablakban látszik is, hogy miért: mert nincs is implementálva a függvény, melyet tesztelnénk.

Írjuk meg úgy, ahogy fentebb láttuk:

első próba

Az idea jelzi nekünk a függvény fejléc margóján, hogy egy nem-tail rekurzív kódot írtunk. Futtatva megint a teszteket ezt kapjuk:

tailrec error

Azt látjuk tehát, hogy az első néhány teszt alapján a függvény kis számokra helyes választ ad, nagyobbakra viszont kicsúszik a call stack méretéből (ilyenkor egyébként a test suite most úgy van megírva, hogy a további teszteket nem is fogja futtatni).

Mi lehet a probléma és mi a megoldás?

Ez az implementáció nem tail rekurzív; azzá kell tennünk. Válasz mutatása

fibonacci tail rekurzívan

Hogy hogyan teszünk tail rekurzívvá egy alapból nem tailrec függvényt, arra nincs általánosan alkalmazható módszer, kreatívnak kell lennünk; egy módszer az, amit az előadáson láthattunk.

Mi annak a megközelítésnek az első lépése?

Ha imperatívan könnyen tudnánk rá **for ciklusos** megoldást adni, írjunk egyet. Válasz mutatása

Írjunk ilyet! Ha nem sikerül elsőre, nézzük meg a hintet.

A for ciklusban tároljuk el az előző **két** elemét a sorozatnak és aktualizáljuk mindkettőt. Hint mutatása
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int fib( int n ) {
  int prev = 1;
  int last = 1;
  for( int i = 2; i <= n; i++ ) {
    int tmp = prev; //meg kell jegyeznünk, mert használjuk
    prev = last;
    last = last + tmp;
  }
  return last;
}
Válasz mutatása

Miből lesz most itt egy tail rekurzív függvény, és annak milyen paraméterei lesznek? Mi lesz a kimenet típusa és értéke?

A `for` ciklusból: * az imperatív ciklusban használjuk az `i`, `n`, `prev` és `last` változókat, melyeket ciklusiterációról iterációra viszünk magunkkal, ezek első körben lehetnek paraméterek; * a `tmp` nem kell paraméter legyen, hiszen lokális változó, minden iterációban újra inicializáljuk, ezért belőle **a tailrec függvényünkben lesz egy val**; * mivel a végén az eredeti imperatív függvényünk a `last`ot adja vissza, ami egy `Int`, a tailrec függvény is csinálja ezt: értéke majd a `last` legyen, típusa pedig `Int`. Válasz mutatása

Implementáljuk ezt a tailrec függvényt!

1
2
3
4
@tailrec
def fibTail( i: Int, n: Int, prev: Int, last: Int ): Int =
  if( i > n ) last                         //a ciklus kilépési feltétele és a visszatérési érték
  else fibTail( i+1, n, last, prev+last )  //a változók aktualizálása az új iterációhoz
Láthatjuk, hogy explicit nem kellett létrehoznunk a `tmp` változót, tudtuk nélküle aktualizálni az összes értéket: `i`-t növelni kell eggyel, `n` nem változik, az eddigi `prev` ,,új értéke'' az eddigi `last` lesz, a `last` ,,új értéke'' pedig az eddigi `prev` és `last` értékek összege. Válasz mutatása

Használva ezt a tailrec függvényt belső függvényként, implementáljuk a fenti C fib függvény Scala megfelelőjét!

1
2
3
4
5
6
7
8
9
def fib( n: Int ): Int = {

  @tailrec
  def fibTail( i: Int, n: Int, prev: Int, last: Int ): Int =
    if( i > n ) last                         
    else fibTail( i+1, n, last, prev+last )  

  fibTail( 2, n, 1, 1 )
}
A függvény első részében a for ciklusnak egy az egyben megfelelő tailrec függvény szerepel; eztán jön maga a hívás a változók C kódnak megfelelő beállításaival: `i` értéke `2`, `n` értéke amit kaptunk, `prev` és `last` pedig mindketten `1`. Válasz mutatása

Mielőtt egyszerűsíteni próbálnánk, tesztelni érdemes:

minden okés

Nagyszerű. Most, hogy működik a függvényünk, tegyük egyszerűbbé, ha lehet. Meg tudunk szabadulni például valamelyik paramétertől? Ha igen, tegyük meg!

Igen, az `n` argumentum értéke a belső függvényben mindig ugyanaz az `n` lesz (látszik, hogy a rekurzív hívásnál `n` helyére mindig ugyanúgy `n` kerül), amivel a külső `fib` függvényt hívták meg - és amit a belső függvény ,,lát'' is! Ezért ez a paraméter törölhető:
1
2
3
4
5
6
7
8
9
def fib( n: Int ): Int = {

  @tailrec
  def fibTail( i: Int, prev: Int, last: Int ): Int =
    if( i > n ) last                         
    else fibTail( i+1, last, prev+last )  

  fibTail( 2, 1, 1 )
}
Válasz mutatása

Futtassuk persze újra a teszteket, de ez így jó is lesz.


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