Scala online olvasnivalók

Néhány angol nyelvű online olvasnivaló Scala-val kapcsolatban, hogy ne Neked kelljen összevadásznod:

• Az alap 15 oldalas Scala tutorial for Java programmers, amit a Google elsőre kihoz és a letöltött disztribúcióban is megtalálható. Gyors áttekintésnek jó, de csak a felszínt karcolja.
• A Scala By Example nekem kezdésnek bejött. Az interpreteres megközelítéstől indul, azaz amikor utasításokat írunk konzolra és a Scala válaszol rájuk. Ez már mélyebben belemegy a dolgokba 145 oldalon keresztül, de még mindig hiányoznak belőle részletek. (Névtelen függvények kompakt változata, XML kezelés, kivételek, ...) Egy eléggé friss változata szintén megtalálható a disztribúcióban.
• A harmadik pdf ami lejön a scala-install.jar -ral, a Scala Language Specification, amiben viszont természetesen minden benne van, csak nem földi halandók számára érthető módon. Mindenesetre annak kiderítésére alkalmas hogy milyen funkciók vannak a nyelvben, amikkel aztán valami könnyebben emészthető forrásból meg lehet ismerkedni.
• A letöltött Scala disztróban a doc/scala-devel-doc könyvtárban akadnak példakódok és API doc is. Az API doc-ban vannak linkek a forrásra is, ami egy online SVN repóra mutat.
  
• A HUP fórumban találtam linket egy ingyenes online OReilly könyvre: Dean Wampler, Programming Scala. Sokminden benne van, de az a tapasztalatom, hogy néha (ritkán!) nincsenek teljesen kifejtve a bonyolultabb témák, főleg a különböző funkciók kombinálása terén. Érdemes letölteni lokálisra, mert eléggé lassan jönnek be az oldalai. Olvasói kommentek is vannak az online anyagban. Talán ez a legjobb a felsoroltak közül.
  
• First steps to Scala az Artimánál a kályhától indulva, valamint sok más egyéb komoly írás a Scalazine-ban.
  
• James Strachan blogbejegyzése, ami magát a nyelvet nem részletezi, de tartalmaz néhány érvet és hasznos linket.
• A Tour of Scala nem lineáris online olvasmányt is James linkjei között találtam, ami a scala-lang.org -on, a hivatalos Scala oldalon van. Ez átfutja a nyelv jellemzőit.
  
• Szintén a scala-lang.org -on található a Reference Manuals oldal, ahonnan már az előzőekben is említettem egy-két írást. Ugyanitt papírkönyvek is fel vannak tüntetve.
• Írások az IBM-nél elfoglalt java programozóknak.
• CodeCommit: Scala java-soknak, ami egész jó. Valamint Java Scala együttműködés ugyanitt.

• Topik a jhacks-on, ami egyelőre még eléggé csonk. -Ez magyar.

Más magyar nyelvű bővebb írásokkal nem találkoztam még, halott fa formátumú angol anyagokat pedig még nem vettem a kezembe eddig.

Megoldás

Szóval ott tartottam hogy Scala és Java programkódokat hasonlítgatok össze, ami egy tömbben egy adott karakter előfordulásait számolja meg. Egy szerény 30 millió karakteres tömbön próbálgattam a négyféle programkódot, amit az előző post-ban fabrikáltam össze tegnapelőtt: Volt sima for ciklusos és rekurzív algoritmus Java-ban és Scala-ban is.

Nézzük hogyan muzsikáltak:

Az első sima Java megoldás (1.) kb 160 ezredmásodperc alatt birkózik meg a feladattal. A Scala program, amibe a Java imperativizmusát másoltam le (2.), 1200 ezredmásodpercig dolgozik ugyanezen. Ez egyáltalán nem elhanyagolható különbség, de mégegyszer hangsúlyoznám, hogy ész nélkül írtam át a Java kódot Scala-ba: Egyszer talán majd pörgök egy post-ot ezen a különbségen is, de alapvetően "nem érdekel ez most engem".

Következőnek a (4.) Java programkódot tárgyalom ki, amit kvázi funkcionálisan írtam meg, rekurziót használva, viccből. Na ez már hatezer karakteres bemeneti karaktertömbnél is csúnyán elcsattan StackOverflowError-ral. Ha ismerjük a rekurzió működését, -azaz hogy a program minden egyes függvényhívásnál felépít egy stack frame-et- ez nem is túl meglepő. Ahány karakter, annyi stackframe: a verem hamar felzabálja a memóriát.

Végül jöjjön a (3.) funkcionális Scala program, ami a 4.-eshez hasonlóan rekurziót használ. Ez viszont nem száll el StackOverFlowError-ral, sőt egész jó időt hoz, kb. 160 ezredmásodpercet. Csak kicsivel lassabb mint a legelső kód. Hogyan lehet ez?

A megoldás kulcsa a farokrekurzió és annak kioptimalizálása. A dolog lényege, hogy a rekurzív függvény legutolsó művelete saját magának a meghívása. Még általánosabban, ha egy függvény utolsó művelete egy másik függvény meghívása (Tail Call). Ilyenkor levezethető, hogy a legutolsó stackframe újrafelhasználható, vagy legalábbis eldobható a következő függvény meghívása előtt. A jelenlegi Java-t futtató JVM implementáció nem támogatja ezt a feature-t. Vannak rá törekvések, ami talán új bájtkód prefixet is szükségessé tenne, de ez nem a közeljövőben fog megvalósulni. Biztonsági kérdések is felmerülnek, mert a Java nem optimalizálhatja ki csak úgy a stack frame-eket. Kivétel dobásánál vagy hozzáférési jogosultság ellenőrzésnél nem szerencsés ha hiányoznak frame-ek. A ScalaByExample.pdf -ami külön fejezetet szán ennek a magyarázatára- megemlíti hogy a Scala esetében farokrekurzió optimalizására lehet építeni, de a stackoverflow-n találtam még két kitételt ezen felül: Csak lokális vagy final függvények esetében.

Aki arra is kíváncsi hogy a Scala (valószínűleg) hogyan oldja meg, illetve hogyan oldható ez meg magas szinten egy nyelv meglévő elemeivel a program átírásával de az algoritmus jellegének megtartásával, az itt találhat egy kimerítő leírást róla. Elég messziről indul és körmönfont példát hoz, de egyébként nem egy bonyolult dolog. Hasonlít a Command Pattern-re.

Egyébként ezzel az egésszel csak arra akartam megnyugtató választ kapni, hogy a Scala-ban előszeretettel használt tail rekurzió megállja-e a helyét gyári környezetben. A válasz: igen.

Scala fejtvény

Ahogy beleolvasgattam egy-két Scala ismertetőbe az volt az érzésem, hogy folyton túl kézreálló példákat próbálnak hozni a nyelvhez. Arra gondoltam, csinálok egy olyan példát, ami nem annyira kézreálló. Számoljuk meg egy karakter tömbben a paraméterben megadott karaktereket. Sokkal kreténebb példákat is lehetne kitalálni, de én most megelégszem ezzel. Java-ban elég kézenfekvő a megoldás (1.):

public int count(char a, char[] array) {
  int ctr = 0;
  for(char ch : array) if(ch==a) ctr++;
  return ctr;
}

Ezt tükörfordításban ész nélkül kb. így lehet átírni Scala-ba (2.):

def count(a: Char, array: Array[Char]) : Int = {
  var ctr = 0;
  for(ch <- array) if(ch==a) ctr = ctr + 1;
  ctr;
}

Viszont a Scala funkcionális nyelv és ha ezt a paradigmát kihasználva szeretnénk megírni a programot, nem tehetjük meg, hogy ezt mondjuk: ctr = ctr + 1. Ez az a dolog, ami miatt ezt én "nem kézreálló példának" tartom. Ehelyett valami olyasmit kell elkövetnünk, mintha fél lábon állva a bal fülünket a jobb kezünkkel a fejünk mögött átnyúlva vakarnánk meg (3.):

def count(a: Char, array: Array[Char]) = {
def count_(i : Int, ctr : Int) : Int =
  if(i == array.length) ctr else
    count_(i+1, if(array(i)==a) ctr+1 else ctr)
  count_(0, 0)
}

Bár nem tartozik szorosan a témához, azért néhány Scala jellegzetességet gyorsan kiemelek: A külső függvénynek nincs meghatározva visszatérési értéke, mert kikövetkeztethető. Nem írtam pontosvesszőket a sor végére, mert a fordító így is érti miről van szó. Ja és ezek egymásba ágyazott függvények, ráadásul a belső függvény látja a külső bemenő paramétereit.

Csak a vicc kedvéért, ezt az utóbbit visszaírom java-ba, úgyhogy ha az előző megoldás nem volt érthető, talán ez tisztába teszi a dolgokat némileg a Java-s emberek számára is. Itt viszont már két függvényre van szükségem (4.):

public int count(char a, char[] array) {
  return count_(a, array, 0, 0);
}
    
private int count_(char a, char[] array, int i, int ctr) {
  return i==array.length ? ctr :
    count_(a, array, i+1,
      a==array[i] ? ctr+1 : ctr);
}

Namost a kérdés a következő: Szerintetek a négy megoldás mennyire gyors és mi történik (és miért - főleg ez a lényeges) ha egy jó nagy -de még nem akkora nagy hogy azonnal OutOfMemoryErrort okozzon- karaktertömböt adok meg bemeneti paraméterként? A megoldást megírom pénteken. Ha addig valaki bekommenteli a megfejtést, kap tőlem egy sört vagy ezzel egyenértékű élvezeti cikket a következő JUM-on.