A Haskell programozási nyelv

Bevezetés

Kezdetek

"Az első programozási nyelvek kifejlesztését egyetlen cél vezérelte: szükség volt egy módszerre, amivel a számítógépeket vezérelni lehetett. Így aztán nem meglepő, hogy a működtetett hardver felépítése jelentősen rányomta bélyegét ezekre a nyelvekre." Hudak: Conception, Evolution and Application of Functional Programming Languages
Hamar le kellett mondani erről a koncepcióról, hiszen egyrészt szinte lehetetlen volt karbantartani a programokat, másrészt az alacsony absztrakciós szint miatt a kód egyáltalán nem vagy csak alig volt hordozható. Nemsokára felmerült az igény a magasabb szintű programozási nyelvekre.
Az első "fecskék" az imperatív nyelvek közül kerültek ki. Utasítások sorozatával definiálták a programokat, az utasítások pedig szabadon változtathatták a gép belső állapotát. Tulajdonképpen egyfajta okos assemblernek is tekinthetjük őket. Legnagyobb előnyük az volt, hogy olyan magasabb rendű műveleteket tartalmaztak, mint például print utasítás, amivel a programozók megkímélhették magukat a memória bitjeinek közvetlen állítgatásától. A C és az Ada nyelvek fontos példái ennek a paradigmának. A C-t elsősorban operációs rendszerek írására, míg az Adát valósidejű rendszerek fejlesztésére használják azóta is.
Egy másik megközelítést alkalmaznak az objektum orientált nyelvek, például a Java és a C++. Ezek többek között a már meglévő komponensek egyszerű bővíthetőségét (osztályok) és a modularizációt nyújtják a programozónak. Rengeteg hasznos és érdekes design patternt fejlesztettek ki rájuk, de valami mégis hiányzik: a kifejezőerő. A programozó szándéka elveszik az interfészek és osztályok erdejében, a nyelv megköti a kezét, és sokszor több száz sort kénytelen írni még akkor is, ha a probléma matematikailag egyszerűen megfogalmazható.
Itt lépnek be a képbe a funkcionális programnyelvek. Ezek kifejezések értékének meghatározására fókuszálnak, a mögöttük húzódó számítási modell pedig a függvény. Segítségükkel a problémák a megfelelő absztrakciós szinten, matematikai eszközökkel kezelhetők és soha nem látott közelségbe hozzák a feladatot az azt megoldó algoritmushoz. Legtöbbjük továbbá (Haskell is) szigorú statikus típusossággal is felvértezett, így mindörökre búcsút mondhatunk a hibás castolásból eredő futásidejű hibáknak is.
1960-ban McCarthy találta fel az első funkcionális programnyelvet, amit LISP-nek nevezett el. A LISP eredetileg List Processinget (lista feldolgozás) jelent, bár egyesek szerint az elnevezés valójában a 'Lots of Incomprehensive Stupid Parentheses' illetve a 'Lost In a Sea of Parentheses' kifejezések kezdőbetűiből származik. Ezek a nevek a nyelv 'kissé' furcsa zárójelekkel tarkított szintaxisát parodizálják. A LISP sikerét főleg bővíthetőségének köszönheti (Steele: Growing a Language). Az évek során több különböző dialektusa terjedt el, például a Common LISP és a Scheme. Sokhelyütt használják azóta is, elsősorban mesterséges intelligencia alkalmazásokban illetve makró nyelvként.
A 70-es évek végén Backus vezette be az első magasabb rendű, tisztán funkcionális nyelvet, az FP-t, ami komoly befolyással volt a később tervezett funkcionális nyelvekre. Fontos megemlíteni a magasabb rendű függvények ötletét, ezek olyan függvények, amik függvényeket kapnak paraméterül vagy függvény a visszatérési értékük (lásd currying).
Ugyanebben az időben az edinburghi egyetem kutatói kifejlesztették az ML-t (Meta Language) automatikus tételbizonyításra. Hamar rájöttek azonban, hogy az ML általános célú funkcionális nyelvként is megállja a helyét, így kutatásokat kezdtek ebbe az irányba is. Amellett, hogy az FP-hez hasonlóan az ML is támogatja a magasabb rendű függvények használatát, gazdagabb a szintaxisa (az FP szintaxisa a kombinátor logikán alapszik) és támogatja a típus levezetést is. Dióhéjban itt arról van szó, hogy a program minden részéhez (minden kifejezéshez) levezethető annak típusa anélkül, hogy explicit deklarálva lenne. A LISPhez hasonlóan az ML-nek is több változata terjedt el, más nyelvek, mint például a Haskell, sokat merítettek belőle. A két legfontosabb ML dialektus a Standard ML (SML) és a CAML.
Egy másik ML-szerű nyelv az 1985-86-ban kifejlesztett Miranda. Ez az egyik első lusta kiértékelésű funkcionális nyelv. A lustaságnak köszönhetően lehetővé válik potenciálisan végtelen adatstruktúrák kezelése, ami azon alapszik, hogy a lusta kiértékelés a kifejezések értékének meghatározását a lehető legkésőbbre halasztja (hogy ne dolgozzon hiába). A Haskell fejlesztéséhez a Mirandát akarták kiindulópontként felhasználni, de a végül nem sikerült szerződést kötniük a tulajdonossal.
Az iparban valószínűleg az Erlang érte el a legnagyobb sikert, a nyelv a konkurens folyamatok támogatásával tűnik ki társai közül. Az Ericsson fejlesztette ki a nyolcvanas évek végén, elsősorban távközlési alkalmazásokra, de valójában általános célú programnyelv.
A funkcionális nyelvek kiértékelésének jó párhuzamosíthatósága miatt előszeretettel használják őket tudományos számítások során is. Két fontos képviselő ebből a családból a Sisal és az Id Nouveau. A gondolat lényege itt az, hogy a párhuzamosítás ellensúlyozza a funkcionális számítási folyamat bonyolultságából eredő számítási többletköltséget.
Nem csoda, hogy ez a változatosság valamifajta konklúzióban összegződött: 1987 szeptemberében, az Oregon állambeli Portlandban, egy funkcionális nyelvekről szóló konferencián az a döntés született, hogy megalapítanak egy bizottságot, amely megtervezi majd a nyelvet, ami átveheti a helyét az akkoriban megjelent számos, nagyjából azonos kifejezőerejű funkcionális nyelvnek, ezzel egyesítve a szétszakadozó funkcionális nyelvekkel foglalkozó közösséget. A nyelvet a logista Haskell B. Curry után nevezték el, akinek eredményei adják hozzá a logikai alapot. A projekt elsődleges céljai a következők voltak:

A funkcionális nyelvekről

A comp.lang.functional newsgroup GYÍKja és a TheFreeDictionary.Com egyes cikkei alapján. Mit nevezünk funkcionális programnyelvnek?
A funkcionális programnyelvek használói között is megoszlanak a vélemények arról, mi is az a funkcionális nyelv. A funkcionális programozás tulajdonképpen egy programozási stílus. Egy stílus, ami utasítások futtatása helyett inkább kifejezések kiértékelésére helyezi a hangsúlyt. A funkcionális nyelvekben minden függvény. A kifejezések függvények formájában épülnek fel az alapértékekből, amik egyébként maguk is paraméter nélküli függvények más szóval konstansok. Ha egy programnyelv ennek a stílusnak használatára serkent, joggal nevezhető funkcionálisnak.
A funkcionális programozási stílus szemléltetésére tegyük fel például, hogy listák elemeit összegző függvényt akarunk készíteni. Imperatív nyelvekben (pl. Java) ez a következőképpen valósítható meg:

int Sum(int[] vec) { int total = 0; for (int i=0; i<=vec.Length(); ++i) total += i; return total; }

Haskellben ugyanezt a programot így írhatnánk meg:

sum :: [Int] -> Int sum [] = 0 sum (x:xs) = x + sum xs

A definíció valahogy így olvasható: sum egy függvény, egész számokból álló listákról egész számokra képez. Értéke az üres listára 0, míg egy olyan listára aminek első eleme x a többi eleme pedig xs az értéket úgy kapjuk, hogy x-hez hozzáadjuk sum xs-hez rendelt értékét. Figyeljük meg, hogy a ciklus helyett rekurziót alkalmaztunk, és mindkét segédváltozó eltűnt. Ez a szemlélet általánosan jellemző a funkcionális stílusra.
Sokszor más szempontból egyébként imperatívnak nevezett nyelvekben is lehet funkcionális stílusban programozni vagy fordítva egy funkcionális nyelvben imperatív eszközöket lehet használni. A határok tehát elmosódnak, a nyelveket gyakran nem lehet csak az egyik vagy a másik kategóriába sorolni.
Mi egy "tisztán funkcionális" programozási nyelv? A tisztán funkcionális nyelvek definíciójáról hosszú viták folytak a funkcionális nyelveken programozók között. Széles körben elfogadott az a vélemény, miszerint a Haskell és a Miranda tisztán funkcionálisak, míg például az SML és a Scheme nem. Ugyanakkor a technikai részletekben eltérnek az álláspontok. Egy lehetséges definíció a következő:
A "tisztán funkcionális" jelzőt akkor használják egy nyelvre, ha az összes számítás függvények kiértékelésén keresztül történik benne. Ezzel ellentétben más nyelvek (például a Scheme és az SML) túlnyomórészt funkcionálisak, de támogatnak úgynevezett mellékhatásokat okozó műveleteket is (ezek olyan változások amik egy-egy kifejezés kiértékelése során lépnek fel, és megmaradnak a kifejezés kiértékelése után is - jelesül például globális változók és értékadás).
Szokás a fogalmat tágabb értelemben akkor is használni, ha a nyelv ugyan megengedi a mellékhatásokat, de ez jól elkülöníthető a függvények kiértékelésétől és nem befolyásolja annak alapvető tulajdonságait. Például egy kifejezés kiértékelése közben létrejöhet egy taszk, ami aztán párhuzamosan fut a kiértékeléssel és attól elszeparálva okozhat mellékhatásokat. Hogy messzire ne menjünk: a Haskell I/O mechanizmusa is így működik...
Mi a lusta és a mohó kiértékelés?
Egy függvény mohó kiértékelése azt jelenti, hogy a függvényérték meghatározása előtt először az argumentumok értékét határozzuk meg. Ha ez valamilyen oknál fogva meghiúsul (pl. végtelen ciklus vagy futás idejű hiba), akkor a függvényértéket nem tudjuk meghatározni. A funkcionális nyelvek közül az ML és a Scheme mohó kiértékelésű, de ide sorolhatjuk az imperatív nyelveket (C, C++, Java...) is.
Ezzel ellentétben, a lusta nyelveknél a függvényargumentumok egészen addig nem értékelődnek ki, amíg nincs rájuk szükség. Például abban a szélsőséges esetben ha egy függvény nem használ egy argumentumot, ez az argumentum soha nem is értékelődik ki. A Miranda és a Haskell tipikus példák ilyen nyelvekre.
A lustaság ráadásul több, mint a paraméterek kiértékelésének elhalasztása. Elképzelhető, hogy a függvényérték meghatározásához elég az argumentumokat csak részlegesen meghatározni, így bizonyos esetekben rengeteget spórolhatunk. Például tegyük fel, hogy van egy függvényünk, ami egy nem üres lista első elemét adja vissza. Az implementáció pofon egyszerű, hiszen csak vesszük az első elemet és visszatérünk vele. Ez még akkor is tökéletesen működik, ha mondjuk a lista elemeit a világ túlsó végéből kell letöltenünk, vagy egy-egy elem kiszámítása órákig tart, de képzeljünk el egy végtelen listát! A mohó kiértékelés ezzel már egyáltalán nem boldogul, így mindenképpen változtatnunk kell a definíción, hogy a függvény gyorsan (vagy egyáltalán) kiértékelhető legyen. Ugyanakkor lusta kiértékelés esetén a lista első elemének meghatározása után a rendszer azonnal képes a függvényérték meghatározására.
Ez a lustaság egy nyilvánvaló előnye, de más esetekben a mohó kiértékelés a jobb. Például lusta kiértékelés esetén sosem lehetünk biztosak benne, mikor értékelődik ki egy argumentum, amire gyakran szívesen támaszkodunk, vagy egy másik ellenérv: mivel a hardver architektúrák mohó végrehajtásra optimalizáltak, így a 'mohó' fordítóprogramok gyakran hatékonyabb kódot eredményeznek mint a legjobb 'lusta' társaik.
Szerencsére a két megközelítés valamilyen szinten kombinálható, amit például a Hope bizonyos verzióiban és a Cleanben valósítottak meg.
Megjegyzés: A lusta kiértékelést az angol terminológia nem szigorúnak (non-strict) is nevezi, a mohóra pedig a strict (szigorú) kifejezést is használják.
Mi a "currying" és honnan ered a fogalom?
A currying gyökerei a függvények matematikai tulajdonságainak vizsgálatához nyúlnak vissza. Fredge 1893-ban felfedezte, hogy több paraméteres függvények reprezentálhatók egy paraméteres függvényekkel segítségével. Például egy tetszőleges f(x,y) kétparaméteres függvényhez hozzárendelhetünk egy f'(x) egyparaméteres függvényt úgy, hogy ez minden x-hez (ahol az eredeti f értelmezve volt) egy másik egyparaméteres függvényt rendel. Ezt a függvényt y-ra alkalmazva megkapjuk az eredeti f(x,y) értéket. Formálisan tehát (f'(x))(y) = f(x,y). Még konkrétabb példával élve az egész számok összeadás művelete (+) egy kétparaméteres függvény, rögzítve az első paramétert (x), legyen (x +) az a függvény, ami minden egész számhoz x-et ad hozzá. Ekkor x + y egyenlő a következővel: (x +)(y).
Legyenek A, B és C halmazok, x a direktszorzat művelete, egy H halmazról P halmazra képező függvények halmazát pedig jelölje H -> P. A currying fogalom abból a matematikai tényből ered, hogy ekkor az (A x B) -> C és az A -> (B -> C) halmazok izomorfak.
Frege nem gondolta tovább az ötletet, így azt tőle függetlenül Schönfinkel 1924-ben újra felfedezte, miközben kitalálta a kombinátorokat, amiről sikerült megmutatni, hogy kifejezőerőben ekvivalensek a lambda kalkulussal, és mivel Turing belátta, hogy a lambda kalkulusban kiszámítható függvények ugyanazok mint a Turing géppel kiszámíthatóak, így ezzel a kiszámítható függvények egy új modelljét, a kombinátor logikát, alapozta meg. Ezt azonban csak Haskell Curry fedezte fel mintegy tíz évvel később. A currying fogalmat róla nevezték el, és a fenti f' függvényt az f curry formájának hívják..

Statikus típusosság

A statikus típusosság azt jelenti, hogy a típusilleszkedéseket fordítási időben ellenőrzi. Ugyanakkor viszont a legtöbb esetben nincs szükség a típusok explicit megadására, sőt, a függvényeket gyakran típustól függetlenül, sablonként - vagy Haskell terminológiával élve polimorf típussal - definiáljuk. Ezt a szabadságot az adja, hogy (pl. a C-vel vagy a Java-val ellentétben) itt a típusilleszkedés nem típusdeklarációk, hanem típuskövetkeztetés alapján történik, azaz a fordító a függvény típusszignatúráját a típusszignatúrával rendelkező alfüggvényekből következteti ki. Például nézzük meg a Haskell length függvényét:

length [] = 0 length (first : rest) = 1 + length rest

Ebből látszik, hogy a függvény bemenetként listát kér, és az is, hogy a visszatérési értéke egész szám (Haskell Int). Így tehát megállapítottuk, hogy a függvény típusa:

length :: [a] -> Int

Rövid bemutatás:

A Haskell egy lusta kiértékelésű, tisztán funkcionális, statikusan típusos programnyelv; fejlesztői átvették a legfontosabb ötleteket a többi nyelvből, és bevezették a típus osztályokat. (A típus osztályok az objektum orientált nyelveknél megismert overloading funkcionális megfelelői.) A Haskell első verzióját 1990-ben definiálták, 1998-ig öt verzió is napvilágot látott. A jelenlegi legújabb az 1.4-es verzió - a Haskell 98 - ami az eredeti nyelv egyetlen alapkönyvtárán, már lehet saját kivételeket definiálni,a Prelude-on kívül még számos más könyvtárt is tartalmaz, mint pl. bemenet/kimenet kezelést és egyéb, az operációs rendszerrel való kommunikációhoz szükséges eszköztárakat. A Haskell fordítók (Hugs, GHC, NHC) azóta is erre a nyelvre építenek, és egészítik ki egyre újabb és újabb eszközökkel és szolgáltatásokkal. A nyelv hátránya, hogy az implementációk - egyelőre - kevés szolgáltatást nyújtanak a hibajavításhoz, viszont más nyelvekhez képest aránylag kevés a hibalehetőség. Komolyabb probléma, hogy az eddig megjelent fordítóprogramok által generált kód sebességben messze elmarad más nyelvben írt programok mögött. Ugyanakkor van lehetőség "idegen nyelvű" programrészletek beillesztésére, ami sok esetben megoldást adhat erre.
A Haskell volt az a nyelv, ahol a tisztaságot zászlajukra tűző tervezők összetalálkoztak a valós idő és állapot kezelésének imperatív jellegű problémájával. A lusta kiértékelés miatt a Haskell programban szereplő két sorról soha nem lehetne tudni milyen sorrendben fognak lefutni. Ez mindenféle, a külső világ felé irányuló mellékhatás keltésének lehetőségét erősen korlátozná, mivel a külvilág szempontjából a mellékhatások sorrendje korántsem lényegtelen. Az egyik, szemléletes probléma a Haskellben a bevitel-kivitel (input-output, IO) kérdése, ahol egyértelmű, hogy pl. a kiírt dolgokat a kiírás sorrendjében szeretnénk viszontlátni a képernyőn, különben még az is előfordulhat hogy kezdetleges „Szia világ!” -programunk a „világ !Szia” kiírással kezdené meg pályafutását. A Haskell tervezőinek tehát fel volt adva a lecke, hogyan oldják meg a mellékhatások sorrendben tartását tiszta és lusta nyelvükben. A megoldást a matematikából kölcsönzött monád konstrukció használata jelentette.

Ingyenes fordítók

Három jól ismert Haskell rendszer van: a Hugs, a GHC és az NHC. A Hugs csak interpreter, de kitűnően alkalmas tesztelésre vagy hibajavításra. A GHC (Glasgow Haskell Compiler) tartalmaz interpretert és fordítót is; az NHC-ben csak fordító van, viszont kisebb és gyakran gyorsabb kódot generál, mint a GHC.