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 |
|
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 |
|
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 |
|
Note: ha használjuk az idea automatikus kiegészítését, és mikor felajánlja a tailrec
et,
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:
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 |
|
Válasz mutatása
A fenti kód vajon 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:
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:
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árTest 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, hogypackage week02
. - Ez ugyanaz a csomag, mint a
main/scala/week02
által mutatottweek02
csomag, így az ottaniGyakorlat
objektumfib
függvényét fogja keresni; mivel ugyanaz a csomag, ezért ezt külön nem kell beimportálnunk, nem kellweek02.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:
Tehát,
- a tesztesetek fordulnak, mert a
Gyakorlat
objektumon belül tényleg van egyfib
függvény, ami ténylegInt
et vár és azt is ad vissza, ahogy a tesztekassert
jein 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, mertNothing
típusú, ami minden más típusnak leszármazottja és nem csinál mást, csak dob egyUnimplementedMethod
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 egyassert
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,
assert
ek használatával, ezt atest/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:
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:
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:
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?
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?
Válasz mutatása
Írjunk ilyet! Ha nem sikerül elsőre, nézzük meg a hintet.
Hint mutatása
1 2 3 4 5 6 7 8 9 10 |
|
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?
Válasz mutatása
Implementáljuk ezt a tailrec függvényt!
1 2 3 4 |
|
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 |
|
Válasz mutatása
Mielőtt egyszerűsíteni próbálnánk, tesztelni érdemes:
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!
1 2 3 4 5 6 7 8 9 |
|
Válasz mutatása
Futtassuk persze újra a teszteket, de ez így jó is lesz.