Az arrow struktúra. Patai Gergely április 1

Az arrow struktúra Patai Gergely 2008. április 1.

1.

Kiinduló motiváció

A funkcionális nyelvek alapvető építőeleme a függvény. Egyszerű függvényekből különböző kombinátorok segítségével bonyolultabb függvények építhetők fel anélkül, hogy expliciten meg kellene említeni az általuk feldolgozott adatokat. A point-free style olyan programozási stílus, amely ezt a megközelítést emeli ki. A point szó a topológia területéről származik, és az adatokra utal, amelyek között a függvények (vagy általánosabban morfizmusok) átjárást biztosítanak. A gyakorlatban arról van szó, hogy a függvényeket próbáljuk úgy definiálni, hogy az argumentumok implicitek legyenek. A legalapvetőbb kombinátor a függvénykompozíció. Például definiáljunk egy függvényt, amely megszámolja egy sztringben egy adott szó előfordulásait: countw1 w s = length (filter (≡ w ) (words s)) Kompozíció használatával ez a művelet sokkal intuitívabban fejezhető ki, mivel a fenti definíció alapján jól láthatóan egymás után következő fázisokra bontható: countw2 w s = (length ◦ filter (≡ w ) ◦ words) s Az s argumentumot implicitté téve ezzel ekvivalens definíciót kapunk: countw3 w = length ◦ filter (≡ w ) ◦ words Ez persze még nem teljesen point-free, hiszen a számlálandó szó továbbra is megjelenik a definícióban. Ezen is lehet változtatni1 , viszont az így kapott kifejezés már sokkal nehezebben értelmezhető: countw4 = (length◦) ◦ (◦words) ◦ filter ◦ (≡) Egyértelmű, hogy az első transzformáció javítja az olvashatóságot, a második viszont nagy mértékben rontja. Ez nem feltétlenül a megközelítés hibája, sokkal inkább a függvénykompozíció kifejezőkészségének a korlátja – ebben a konkrét esetben az a baj, hogy a w argumentumot egy műveletsor közepére kell bejuttatni. „Okosabb” kombinátorok használatával könnyen elképzelhető valami más, jobban olvasható definíció. Más probléma is akad. Tegyük fel, hogy a függvényünket perifériákon szeretnénk értelmezni, azaz a szöveget file-ból venni és az eredményt kiírni: countwio w = print ◦ length ◦ filter (≡ w ) ◦ words ◦ readFile Csakhogy ezt nem engedi meg a Haskell típusellenőrzője! Az a baj, hogy a readFile és a print is mellékhatással jár, és a típusukban megtalálható az IO monád: readFile :: String → IO String print :: Show a → a → IO () Természetesen ez a típusellenőrzés előnye, hiszen így meg tudjuk különböztetni a tiszta függvényeket a mellékhatásosoktól. A baj az (ahogy már a monádoknál is láthattuk), hogy az ilyen függvények közvetlenül nem komponálhatók a többivel. A közvetlen megoldás egyszerű, csak az adott monád bind (> >=) műveletét kell segítségül hívni és a tiszta műveleteket monadikussá alakítani: countwio1 w = (> >=print ) ◦ liftM (length ◦ filter (≡ w ) ◦ words) ◦ readFile Ez azonban megint nehezebben olvasható, mint az eredeti változat. Az arrow struktúra olyan tervezési minta, amely a fent említett problémákra elegáns megoldást ad. 1 Thomas

Jäger pointfree programjának segítségével

1

2.

A kompozíció általánosítása

Először a monádok és a függvények egységesítésével foglalkozunk. Mint emlékszünk, a monadikus függvények típusa α → µ β. Ahhoz, hogy ezzel kényelmesen dolgozhassunk, érdemes egy típusszinonimát deklarálni: type Kleisli m a b = a → m b Ezután a readFile és a print típusát a következő módon is leírhatjuk: readFile :: Kleisli IO String String print :: Show a → Kleisli IO a () A Kleisli név a kategóriaelméletből ered, amivel itt nem foglalkozunk. A lényeg, hogy ez a típus tetszőleges monádot takarhat. Mivel ez a típus leképzést jelöl (ellentétben a monáddal, amely csak egy „statikus” absztrakciónak felel meg), így tulajdonképpen ez már egy Kleisli arrow. Ha van két ilyen függvényünk – egy α-ból β-ba, valamint egy β-ból γ-ba –, akkor a „kompozíciójuk” egy α-ból γ-ba képző arrow -t ad, amely a mellékhatásaikat is sorbarendezi. A következőkben ezt a műveletet definiáljuk. A függvénykompozícióhoz képest fordított sorrendben vesszük az argumentumokat, hogy a jelölésünkben az arrow -k sorrendje megfeleljen a mellékhatásaik sorrendjének: (> > >) :: Monad m ⇒ Kleisli m a b → Kleisli m b c → Kleisli m a c (f > > > g) a = do b ← f a gb Az így kapott kompozíciós operátort felhasználva már a mellékhatásos függvények esetén is könnyen visszatérhetünk a point-free jelölésre: printFile = readFile > > > print Viszont az eredeti példánkat még nem fejezhetjük ki ezzel az operátorral, mert mellékhatásmentes függvényeket is tartalmaz a kompozíció, amelyeknek pont ezért nem megfelelő a típusa. Szerencsére ezek a függvények könnyen mellékhatás nélküli Kleisli arrow -vá alakíthatók egy újabb kombinátorral: arr :: Monad m ⇒ (a → b) → Kleisli m a b arr f = return ◦ f Ezt felhasználva már felírható a függvény új alakja: countwio2 w = readFile > > > arr words > > > arr (filter (≡ w )) > > > arr length > > > print

3.

Az Arrow osztály

Mivel már kétféle point-free jelölésünk van (egy függvényekre és egy arrow -kra épülő), érdemes ezeket közös nevezőre hozni. A Haskell típusosztályai erre jól használható eszközt nyújtanak, mivel a segítségükkel lehetőség nyílik az arrow operátorok túlterhelésére. Első lépésként definiáljuk az ehhez szükséges osztályt: class Arrow arr where arr :: (a → b) → arr a b (> > >) :: arr a b → arr b c → arr a c Ennek az osztálynak az egyik példánya a közönséges függvények típusa: instance Arrow (→) where arr = id (> > >) = flip (◦)

2

Ha a tiszta függvények körében maradunk, akkor ez csupán egy alternatív jelölés a kompozícióra. Ahhoz, hogy a Kleisli arrow -kat is példánnyá tegyük, típusszinonima helyett új típusként kell őket deklarálni, hogy kapjunk egy típuskonstruktort: newtype Kleisli m a b = Kleisli {runKleisli :: a → m b } instance Monad m ⇒ Arrow (Kleisli m) where arr f = Kleisli $ return ◦ f Kleisli f > > > Kleisli g = Kleisli $ (> >=g) ◦ f Ha ez megvan, felírhatjuk a szószámláló függvény újabb definícióját: countwio3 w = Kleisli readFile > > > arr words > > > arr (filter (≡ w )) > > > arr length > > > Kleisli print Ennek futtatása a következőképpen történik: runKleisli (countwio3 w ) filename Láthatóan az új konstruktor kicsit felhígítja a jelölést, de legalább lehetővé teszi, hogy a monádokat és a függvényeket immár egyformán kezeljük egy absztrakciós lépést (az arr illetve Kleisli „csomagoló” műveleteket) követően. Ezt a jelölést bármely Haskell programban használhatjuk a Control .Arrow könyvtár importálása után, amely többek között az Arrow és a Kleisli definícióját is tartalmazza.

4.

Az arrow értelmezése

Eddig kétféle példányosítását ismertük meg az arrow mintának, de mielőtt újabbakat keresnénk, érdemes belegondolni, mit is várunk általánosságban ettől a struktúrától. A monádok bevezetésekor a kiindulópont az volt, hogy az absztrakciók mögé rejtett adatok helyes kezelését akartuk kikényszeríteni. Ennek megfelelően a monádot egyfajta csomagként – fekete dobozként – tekinthetjük, amelyről csak azt tudjuk, hogy milyen típusú adatot tartalmaz. Az adott csomagtípushoz tartozó return és > >= műveletek lehetővé teszik, hogy a csomag megbontása és szerkezetének ismerete nélkül dolgozhassunk a benne tárolt adatokkal. Láttuk, hogy ez a két művelet elég is minden monádhoz (emellett természetesen több monádtípus még definiál pluszban specifikus műveleteket, pl. az állapotmonád esetén az állapot explicit kezelésére szolgáló get és set függvényeket). A „csomag” persze akár mellékhatásos számítás is lehet, ekkor az említett műveletek biztosítják a mellékhatások helyes menedzselését. Ezzel szemben az arrow általánosságban olyan folyamatnak tekinthető, amelyet a be- és kimenetének típusa jellemez. Azaz míg a monád valamilyen adatot rejt absztrakció mögé, addig az arrow egy transzformációt. Ez látszik is a konstruktorukon, hiszen a return tetszőleges típust elfogad, az arr viszont kötelezően függvényt vár. Természetesen a monádba is csomagolhatunk függvényt, mert a funkcionális programozás alapelve szerint az is csak adat, de lényeges különbség, hogy maga a monád nem tud különbséget tenni konstansok és függvények között, míg az arrow eleve arra épít, hogy a becsomagolt adat függvény, így alkalmazható a megfelelő típusú argumentumra. Tehát a monádba csomagolt függvény passzív marad, míg az arrow egyfajta „keretrendszert” biztosít a futtatásához.

5.

Az egységesítés haszna

Sem a monádok, sem az arrow -k nem kapcsolódnak szorosan egy alkalmazásukhoz sem. A monádok például sokszor előjönnek, ha imperatív nyelvek viselkedését szeretnénk modellezni, de ettől függetlenül használhatók funkcionálisan tiszta kód strukturálására is. Végeredményben a monádstruktúra (és az arrow is) olyan interfészt definiál, amelyet nagyon sokféle kombinátorkönyvtár képes implementálni. A közös interfész mindenképpen előnyös: • sok olyan hasznos művelet van, amely a közös monádműveleteken alapszik; ezeket mind ingyen megkapjuk, ha a könyvtárunkat monádként definiáljuk

3

• transzformerek használatával szisztematikusan kombinálhatunk különböző könyvtárakat, ezzel pedig nagyon sok munka takarítható meg • ha egy interfész ennyire általánosan használható, akár közvetlen nyelvi támogatás adható rá (a Haskell esetében például a do-szintaktika); ez szépen beleillik abba az általános tendenciába, hogy a különböző tervezési minták egy nemzedékkel később nyelvi primitívként jelennek meg • a könyvtárakat használó programozónak is egyszerűbb a dolga, hiszen ismerős műveletekkel dolgozik

6.

A teljes Arrow osztály

Van egy hatalmas különbség a monádok és az arrow -k interfésze között, amely nagyban befolyásolja ezeknek a mintáknak az alkalmazási módját. Vessünk egy pillantást a kompozíciós operátoraik típusára: (> >=) :: m a → (a → m b) → m b (> > >) :: a b c → a c d → a b d A monádok esetén a > >= második argumentuma Haskell függvény, így a nyelv teljes kifejezőereje rendelkezésünkre áll, hogy a bejövő csomagból előállítsuk a kimenő csomagot. Mikor két monádszámítást sorbaállítunk, közöttük tetszőleges Haskell kódot futtathatunk. Ezzel szemben az arrow -k esetén a > > > második argumentuma szintén arrow, azaz absztrakt adattípus, így csak olyan műveleteket végezhetünk rajta, amelyet az ahhoz tartozó interfész definiál. Ugyan az arr művelettel beemelhetünk egy függvényt az absztrakció mögé, viszont ez csak tiszta függvény lehet az arrow szempontjából, tehát az egyéb hatásai nem érvényesülhetnek. Ha azt szeretnénk, hogy a második arrow hatásai az első hatásaitól függjenek, akkor az arr és > > > mellett valami újabb műveletet is be kell vezetnünk. Tegyük fel, hogy szeretnénk két egész számot visszaadó számítást egymás után lefuttatni, majd az eredményeiket összeadni. Monádokkal ez nagyon egyszerű: addM :: (Num a, Monad m) ⇒ m a → m a → m a addM ma mb = do x ← ma y ← mb return (x + y) De az eddig látott arrow interfész még ezt sem képes kifejezni! Ha viszont lenne egy olyan műveletünk, amely képes párba állítani két arrow (f és g) kimenetét, akkor ezt a párt már át lehetne adni az arr (uncurry (+)) kifejezéssel felépített arrow -nak. Ezt viszont nem definiálhatjuk a már ismert műveletekkel, mert az . . .> > >f > > >. . . alakú kompozíció értelemszerűen eldob mindent f kimenetén kívül. A megoldás egy új operátor bevezetése: (& & &) :: a b c → a b d → a b (c, d ) Visszatérve a Haskell megvalósításra az osztály és a két már ismert példány definíciója így bővül: class Arrow arr where ... (& & &) :: arr a b → arr a c → arr a (b, c) instance Arrow (→) where ... (f & & & g) a = (f a, g a) instance Monad m ⇒ Arrow (Kleisli m) where ... Kleisli f & & & Kleisli g = Kleisli $ λa → do b ← f a c←g a return (b, c) Ennek segítségével már definiálható az addA: addA :: (Arrow arr , Num c) ⇒ arr a c → arr a c → arr a c addA f g = f & & &g > > > arr (uncurry (+)) 4

Ugyan a & & & operátor kényelmesen használható, de sajnos elég bonyolult is. Figyelembe kell venni, hogy az arrow -k gyakorlati használatához sok műveletet kell bevezetnünk, és ezeket nehézkes egyenként implementálni. Mivel a Haskell lehetővé teszi alapértelmezett kód futtatását, célszerű olyan egyszerű operátorokat keresni, amelyekből a többi kifejezhető. A& & & többek között megduplázza a bemenetét, hogy mindkét argumentumának átadhassa. Mivel a duplázás arrow -sított tiszta függvénnyel megoldható (arr (λx → (x , x ))), ezért ezt a funkciót kivehetjük, és & & &-t kifejezhetjük az egyszerűbb ∗∗∗ segítségével, amely két arrow -t párhuzamosít úgy, hogy a be- és kimeneteiket párba állítja: (∗∗∗) :: a b c → a d e → a (b, d ) (c, e) Azaz a Haskell definícióban: class Arrow arr where ... (∗∗∗) :: arr a b → arr c d → arr (a, c) (b, d ) f & & & g = arr (λx → (x , x )) > > > f ∗∗∗ g De ne is foglalkozzunk a ∗∗∗ közvetlen megvalósításával, mert van egyszerűbb kombinátor is, amellyel kifejezhető. A ∗∗∗ két arrow -ból csinál egy párokon működő arrow -t, ami visszavezethető arra a speciális esetre, ahol az egyik az azonosság, amely mellékhatás nélkül továbbadja a bemenetét. Vezessük be tehát a first műveletet, amely egy tetszőleges arrow -t párbaállít az azonossággal: class Arrow arr where ... first :: arr a b → arr (a, c) (b, c) instance Arrow (→) where ... first f (a, c) = (f a, c) instance Monad m ⇒ Arrow (Kleisli m) where ... first (Kleisli f ) = Kleisli $ λ(a, c) → do b ← f a return (b, c) Ha a ∗∗∗ operátort vettük volna primitívnek, akkor a first definíciója a következő lehetett volna: first f = f ∗∗∗ arr id Ehelyett a first-re építkezünk. Először definiáljuk a párját second néven, amely a pár második tagját vezeti át az arrow -n: class Arrow arr where ... second :: arr a b → arr (c, a) (c, b) second f = arr swap > > > first f > > > arr swap where swap (x , y) = (y, x ) Ezután a ∗∗∗ megadható alapértelmezett műveletként: class Arrow arr where ... f ∗∗∗ g = first f > > > second g Ez a definíció egyben azt is tisztázza, hogy az f mellékhatásai megelőzik a g-éit. Természetesen tetszőleges mennyiségű hasonló operátort lehetne definiálni, azonban ezek alapvetően mind kifejezhetők az arr , > > > és a first segítségével, valamint tiszta műveletek (pl. a & & & esetén a bemenet megduplázása) felhasználásával. Az itt bemutatott operátorok vizuális értelmezését az 1. ábra mutatja. A Control .Arrow könyvtárban található Arrow osztály tartalmazza ezeket az operátorokat az említett alapértelmezett megvalósítással, így új arrow példányosításakor elég az arr , > > > és first függvényeket megírni. Hatékonysági okokból általában a többit is célszerű közvetlenül implementálni a későbbiekben, de ahhoz nem kellenek, hogy az új adatstruktúránkat működésre bírjuk. 5

arr f

first f

f > > >g

f

f ∗∗∗ g

second f f

f

g

f

f & & &g

f

f

g

g

1. ábra. Az arrow -kombinátorok

7.

Visszacsatolás

Ha az arrow -kat adatfolyamgráfok építőelemeinek tekintjük, adja magát a kérdés, hogy hogyan lehetne köröket alkotni, hiszen a funkcionális világban természetes a rekurzió használata. Az itt definiált kombinátorok ezt nem teszik lehetővé, ezért be kell vezetnünk egy újabbat. Ez azonban már plusz szolgáltatást jelent az alapfunkciókon felül, így semmi esetre sem bővíthetjük az új kombinátorral az Arrow osztályt. Ehelyett egy alosztályt kell definiálni, amely egy új elemmel egészíti ki az interfészt: class Arrow arr ⇒ ArrowLoop arr where loop :: arr (a, c) (b, c) → arr a b A loop kombinátor egy arrow második kimenetét a második bemenetére csatolja vissza. A közönséges függvények esetén ez rekurzív definícióhoz vezet: instance ArrowLoop (→) where loop f a = let (b, c) = f (a, c) in b A furcsán ható definíció gyakorlatilag arra jó, hogy kiváltsa a rekurziót a függvény fixpontjának kiszámításával. Például a szokásos faktoriális a következő függvény fixpontjaként adódik: facloop (x , f ) = (f x , fn) where fn 0 = 1 fn n = n ∗ f (n − 1) Használatára példa: loop facloop 7 Könnyen ellenőrizhető, hogy ez a kifejezés tényleg 5040-re redukálható. Ami a másik példányt illeti, csak a MonadFix osztályba tartozó monádokon értelmezett Kleisli-arrow struktúrák esetén implementálható loop, amivel most nem foglalkozunk.

8.

Adatfolyamok

Bár az ArrowLoop bevezetése jó ötletnek látszik, sem a függvények, sem a monádok esetén nincs igazi haszna, hiszen csak egy alternatív, a szokásosnál bonyolultabb módot ad a rekurzió leírására. A valódi adatfolyamok esetén viszont tényleg van értelme a hurkoknak, így érdemes megvizsgálni, hogy alkalmas-e az arrow struktúra ezek leírására. Legyen a kiindulópont a folyamokon értelmezett függvény, ahol a folyamokat listákkal modellezzük: newtype SF a b = SF {runSF :: [a ] → [b ]} Ezután hozzuk létre az ilyen függvényeken értelmezett arrow példányt: 6

instance Arrow arr f SF f > > > SF g first (SF f )

SF where = SF $ map f = SF $ f > > >g = SF $ unzip > > > first f > > > uncurry zip

Az implementációban kihasználjuk azt, hogy a tiszta függvények is arrow -k, így jól olvasható egységes jelölést kapunk. Ezután megpróbálkozhatunk a loop-pal is: instance ArrowLoop SF where loop (SF f ) = SF $ λas → let (bs, cs) = unzip (f (zip as cs)) in bs Ezzel azonban gond van: ha például vesszük a loop (arr id ) kifejezéssel felépített arrow -t, akkor azt várnánk, hogy úgy viselkedjen, mint a sima azonosság. A probléma gyökere az, hogy mind a zip, mind az unzip szigorú kiértékelésű, azaz muszáj kiértékelniük az argumentumaikat, mielőtt bármit is visszaadhatnának. Emiatt a rekurzió holtponthoz vezet. A megoldás a lusta minták használata: instance ArrowLoop SF where loop (SF f ) = SF $ λas → let (bs, cs) = unzip (f (zip as (stream cs))) in bs where stream ˜(x : xs) = x : stream xs A lusta minta mindenképpen illeszkedik, viszont ha később kiderül, hogy az átadott struktúra nem megfelelő, akkor hiba keletkezik. Ebben az esetben ez nem történik meg, hanem keletkezik egy végtelen lista, amelynek az elemei nem definiáltak. A zip ezeket az elemeket olyan párokkal tölti ki, amelyeknek első tagja az as listából jön, a második pedig még mindig definiálatlan. Viszont a holtpontot feloldottuk, és a függvényekhez hasonló módon működik a loop új változata. Érdemes végiggondolni a runSF (loop (arr swap)) [1, 2, 3] kifejezés kiértékelésének menetét, amely a következő kifejezéssel ekvivalens: loopExample = bs where (bs, cs) = unzip (map swap (zip [1, 2, 3] (stream cs))) swap (x , y) = (y, x ) stream ˜(x : xs) = x : stream xs Ahhoz, hogy a hurok tényleg használható legyen, definiálni kell egy olyan műveletet, amely csak a folyamokon értelmezhető, a függvényeken és a monádokon nem: az egyszerű késleltetést. Ezzel olyan bővítményt kapunk, amellyel tetszőleges szinkron hálózatot le tudunk írni, így ehhez is érdemes egy szűkebb arrow -osztályt is definiálni: class ArrowLoop arr ⇒ ArrowCircuit arr where delay :: a → arr a a instance ArrowCircuit SF where delay x = SF (x :) A delay egy óraütéssel késlelteti a rajta átmenő adatforgalmat, az első értéket pedig az argumentumában megadott érték előzi meg a kimeneten. A hurokba helyezett késleltetésre a stabilitás miatt van szükség. Így pontosan tudjuk szabályozni, hogy a kimenet mely korábbi értékeit szeretnénk felhasználni a következő iterációban. Próbáljunk akkor az eddig definiált műveletekkel egy újabb faktoriálisfüggvényt írni! Az adatfolyamhálót a 2. ábra mutatja. Először kell egy szorzóelem, amelynek két bemenete és egy kimenete van: mul :: (Num n, Arrow arr ) ⇒ arr (n, n) n mul = arr (uncurry (∗)) Ha a kimenetének a másolatát visszacsatoljuk egy késleltetésen keresztül, akkor egy egyszerű akkumuláló struktúrát kapunk: 7

mulAcc mul delay 1

2. ábra. Szorzó-akkumulátor struktúra mulAcc1 :: (ArrowCircuit arr , Num n) ⇒ arr n n mulAcc1 = loop (mul > > > (arr id & & & delay 1)) Ezt megfelelően felparaméterezve már meg is oldottuk a feladatot: fac1 :: (Num a, Enum a) ⇒ a → a fac1 n = last $ runSF mulAcc1 [1 . . n ]

9.

A do-szintaktika kibővítése

Bár az arrow -kombinátorok viszonylagos gazdagsága miatt sokkal egyszerűbb velük a munka, mint a monádok egyetlen > >= műveletével, nagyobb programokat nehézkes ilyen formában leírni. A monádoknál már látott megoldás itt is működik: a point-free megközelítést elvetjük, és újra explicitté tesszük az adatokat, azaz az egyes arrow -k be- és kimeneteit. Egy arrow -t a proc kulcsszóval vezetünk be, amelyet a bemenetre illeszkedő minta, majd egy jobbra mutató nyíl (→, azaz egy kötőjel és egy kacsacsőr kombinációja: ->) követ. A nyíl másik végén egy arrow -kifejezésnek kell állnia. Ez a legegyszerűbb esetben az arr −≺ input alakot ölti, ahol arr maga a használt arrow, input pedig egy tiszta Haskell kifejezés, amelynek az eredményét szeretnénk az arrow bemenetére kötni. A −≺ is egy kötőjelet követő, de ellenkező irányú kacsacsőr: -<. A kimenet arr kimenete lesz, ezért nem kell explicit nevet kapnia. Például egy egyszerű összeadó definíciója lehetne a következő: adder = proc (x , y) → arr id −≺ x + y Látható, hogy tiszta kifejezés nem állhat csupaszon, hanem be kell csomagolni az identitás-arrow felhasználásával. Ez analóg a monadikus return művelettel, ezért is definiálták a returnA arrow -t: returnA = arr id Természetesen általában több arrow -t szeretnénk kombinálni egy definícióban, így a köztes értékeket is meg kell jeleníteni a forrásban. Ez a monádokéhoz nagyon hasonló do-jelöléssel lehetséges. A különbség lényegében csak annyi, hogy a szokásos „kicsomagoló nyilak” (←) jobb oldalán most monádok helyett arrow -k állnak, azaz arr −≺ input alakú kifejezések. Például próbáljuk definiálni a & & & kombinátort ezzel a szintaxissal! f & & & g = proc x → do y1 ← f −≺ x y2 ← g −≺ x returnA −≺ (y1 , y2 ) Az operátorok nem véletlenül formálják egy nyíl fejét és farkát. Adja magát az interpretáció, hogy a jobb oldalon látható kifejezést a középen megadott arrow -n keresztülküldve a bal oldali értéket kapjuk. Csak azt kell észben tartani, hogy nem egyszerűen argumentumként adjuk át az értékeket, hanem a −≺ operátor (amely szintaktikai elem, nem infix jelölésű Haskell függvény!) felhasználásával. Ez azért van, mert az arrow -k általánosságban nem függvények, így nem függvényalkalmazásról van szó. Ezután már csak a hurkok leírása hiányzik. Mint említettük, a loop kombinátor gyakorlatilag a rekurzió átfogalmazása, így nincs is másról szó, mint az azonosítók kölcsönösen rekurzív deklarációjáról. Elvileg ennyi 8

counter

reset

out

if reset then 0 else next next

out + 1

delay 0

inc

3. ábra. Resetelhető számláló elég is lenne, viszont implementációs okokból az ilyen jellegű felhasználást a rec kulcsszóval kell jelezni, és az ilyen blokkokat célszerű csak azokra az arrow -kra korlátozni, amelyeknél tényleg szükség van erre. Az így kapott do-jelölést felhasználva az előbb látott faktoriális például a következő módon definiálható: mulAcc2 :: (ArrowCircuit arr , Num n) ⇒ arr n n mulAcc2 = proc x → do rec prod ← mul −≺ (x , prec) prec ← delay 1 −≺ prod returnA −≺ prod fac2 :: (Num a, Enum a) ⇒ a → a fac2 n = last $ runSF mulAcc2 [1 . . n ] Vegyünk egy kicsit bonyolultabb példát. Hozzunk létre egy resetelhető számlálót, amelynek csak egy boolean bemenete van, a kimenete pedig egész számok folyama. A hálózatot a 3. ábra mutatja. counter1 :: ArrowCircuit a ⇒ a Bool Int counter1 = proc reset → do rec next ← delay 0 −≺ out + 1 out ← returnA −≺ if reset then 0 else next returnA −≺ out Például a következő módon tudjuk futtatni: runSF counter1 $ map (≡ ’r’) "....r.rrr.....r...r." Próbáljuk most ugyanezt leírni az ismert kombinátorokkal: counter2 :: ArrowCircuit a ⇒ a Bool Int counter2 = loop $ cond > > > returnA & & & (inc > > > delay 0) where cond = arr (λ(reset , next) → if reset then 0 else next) inc = arr (+1) Jól látható, hogy az átírás bonyolult, és semmi esetre sem oldható meg olyan egyszerű szabálygyűjteménnyel, ami a monádok do-szintaxisánál működik. Az például egyértelmű, hogy a jobb oldalon található tiszta kifejezéseket arrow -ba kell csomagolni, hogy beilleszthessük őket a struktúrába, de a különböző értékeket már egyáltalán nem egyszerű eljuttatni a megfelelő pontokba. Ebben az esetben azért is könnyű a dolgunk, mert nincs olyan kifejezés, amely kettőnél több paramétert vár, így a beágyazása egyszerűen leírható a már definiált kombinátorokkal. Ha mondjuk a számláló induló értékét is kívülről vennénk egy másik adatfolyamból, a cond komponensnek máris három bemenete lenne, amely újabb kombinátor híján csak egymásba ágyazott párokkal írható le. Ez természetesen még távolabb viszi egymástól a do-jelölést és a kombinátorost. Mindezt figyelembe véve megállapíthatjuk, hogy ez a transzformáció már összetett fordítási lépés, hacsak nem akarunk teljesen lemondani az optimális megvalósításról. A hatékonyság növeléséhez minél több kombinátort kéne bevezetni (pl. az említett hárombemenetű esetre), ám ezzel több probléma is van. A legkisebb gond az, hogy ezeket mind meg is kell valósítani az arrow definiálásakor, mert az alapértelmezett implementáció csak arra jó, hogy rossz hatékonysággal ugyan, de legalább működjön a program (ez ekvivalens azzal, hogy nem is bontjuk meg az absztrakciót). Az első nehéz kérdés inkább az, hogy milyen kombinátorokat is definiáljunk, hiszen a lehetséges struktúrák száma robbanásszerűen nő még kevés be- és kimenet esetén is. Ha ezt valahogy sikerült eldöntenünk, rögtön azzal szembesülünk, hogy a fordító nagyon gyorsan elbonyolódik, ha ezeket ki is akarjuk használni az átírásnál. Nem véletlen, hogy a jelenlegi preprocesszor csak az említett operátorokból dolgozik, és a végeredmény messze nem optimális. 9

10.

További érdekes bővítések

10.1.

Feltételes kifejezések

Alapötlet: feltételhez kötjük egy arrow létezését. Ehhez bevezetünk egy if-then-else kombinátort: ifte :: Arrow arr ⇒ arr a Bool → arr a b → arr a b → arr a b Azaz ifte p f g a p folyam aktuális értékétől függően f -ként vagy g-ként viselkedik. Viszont ez is visszavezethető egyszerűbb elemekre. Első lépés: p-t kiemeljük előre, hiszen mindenképpen ki kell értékelni f vagy g előtt. Bevezetünk helyette egy olyan kombinátort, amely az eredeti bemenetet és a p kimenetét várja: ifte p f g = p & & & arr id > > > f ||| g A ||| az első (boolean típusú) bemenetétől függően a másodig bemenetét vagy az f , vagy a g arrow -n keresztül küldi tovább. Ennél még jobb, ha egy (Bool , a) típusú bemenet helyett Either a b-t használunk, így az is lehetséges, hogy a két esetben két különböző típusú adatunk legyen. A szokásos módon származtatunk egy újabb típusosztályt: class Arrow arr ⇒ ArrowChoice arr where (|||) :: arr a c → arr b c → arr (Either a b) c Erre azért is van szükség, mert nem feltétlenül tudja minden arrow -típus biztosítani ezt a műveletet. Például ezzel definiálhatjuk a MapA-t: mapA :: ArrowChoice arr ⇒ arr a b → arr [a ] [b ] mapA f = arr listcase > > > arr (const [ ]) ||| (f ∗∗∗ mapA f > > > arr (uncurry (:))) where listcase [ ] = Left () listcase (x : xs) = Right (x , xs) Az előzőleg bevezetett do-jelölést használva így is felírhatjuk: mapA f = proc xs → case xs of [] → returnA −≺ [ ] z : zs → do y ← f −≺ z ys ← mapA f −≺ zs returnA −≺ y : ys Az ||| olyan arrow -kat vár, amelyeknek azonos típusú a kimenete. Viszont Either használatával ez a kényszer is feloldható: class Arrow arr ⇒ ArrowChoice arr where ... (+++) :: arr a b → arr c d → arr (Either a c) (Either b d ) A +++ gyakorlatilag úgy viszonyul a |||-hoz, mint a ∗∗∗ a & & &-hoz, és gyakorlatilag ezek duálisainak is tekinthetők, ha az arrow -k irányát megfordítjuk, és az Either típusokat párokra cseréljük. ||| új definíciója tehát: f ||| g = f +++ g > > > arr join where join (Left b) = b join (Right b) = b És az analógia tovább is vihető: definiálhatunk a first mintájára egy left kombinátort, amely csak a Left -be csomagolt értékeket küldi át a paraméterül kapott arrow -n, a többit változatlanul továbbadja: class Arrow arr ⇒ ArrowChoice arr where ... left :: arr a b → arr (Either a c) (Either b c) 10

Ezzel definiálható a second -nak megfelelő right is: right f = arr mirror > > > left f > > > arr mirror where mirror (Left a) = Right a mirror (Right a) = Left a És ezek után +++ egyszerűen kifejezhető: f +++ g = left f > > > right g Az Control .Arrow -ban található ArrowChoice osztály ezeket az operátorokat definiálja az ifte kivételével. Látható, hogy a left implementálásával a többit rögtön meg is kaphatjuk. Mind a függvények, mind a Kleisli arrow -k példányai ennek az osztálynak is: instance ArrowChoice (→) where left f (Left a) = Left (f a) left f (Right b) = Right b instance Monad m ⇒ ArrowChoice (Kleisli m) where left (Kleisli f ) = Kleisli $ λx → case x of Left a → do b ← f a return $ Left b Right b → return $ Right b Így látszik, hogy a fent definiált mapA a map és a mapM közös általánosítása, például a következő két kifejezés kiértékelésekor: mapA (arr (+1)) [1 . . 5] runKleisli (mapA (Kleisli print) > > > Kleisli print) [1 . . 5] Az adatfolyamoknál viszont nem ilyen egyszerű a helyzet. Kiszűrhetjük a Left -be csomagolt értékeket, és átadhatjuk az f arrow -nak, de nem tudjuk az eredményt értelmesen összefésülni a Right csomagokkal! Csak úgy oldható meg a probléma, ha szűkítjük a lehetséges függvények körét. Az egyik lehetőség az, hogy csak a szinkron függvényekkel foglalkozunk, amelyek minden bemenetre egy kimenetet produkálnak, azaz hossztartók. Így már magától értetődő a megvalósítás: instance ArrowChoice SF where left (SF f ) = SF $ λxs → combine xs $ f [y | Left y ← xs ] where combine (Left y : xs) (z : zs) = Left z : combine xs zs combine (Right y : xs) zs = Right y : combine xs zs combine [ ] zs = [] A hossztartás nem csak a left definiálása miatt fontos. Ez a tulajdonság a first működését is megregulázza, ugyanis az általános esetben nem teljesíti (az itt nem említett) arrow -törvényeket, így meglepően viselkedhet. Sajnos az is nyilvánvaló, hogy a delay nem hossztartó, ám ezen könnyű segíteni a lista utolsó elemét elhagyó init függvénnyel: delay x = SF $ init ◦ (x :) Példafutás: runSF (mapA $ delay 0) [[1 . . 3], [4 . . 6], [7 . . 9]] ⇒ [[0, 0, 0], [1, 2, 3], [4, 5, 6]]

10.2.

Magasabbrendű arrow -k

Próbáljuk meg bevezetni a $ operátor arrow -alapú megfelelőjét! Mivel a meglevő kombinátorokkal ez lehetetlen, származtassunk le egy újabb osztályt: class Arrow arr ⇒ ArrowApply arr where app :: arr (arr a b, a) b 11

Ezt könnyű példányosítani függvényekre és Kleisli arrow -kra: instance ArrowApply (→) where app (f , x ) = f x instance Monad m ⇒ ArrowApply (Kleisli m) where app = Kleisli (λ(Kleisli f , x ) → f x ) Viszont az adatfolyamok már nem tudják ezt a műveletet biztosítani! A probléma gyökere az, hogy maguk a folyamokon továbbított adatok már nem folyamok – pontosabban lehetnek azok, de ezek teljesen függetlenek a továbbító közegüktől (ha esetleg a folyamon cseles módon saját magára mutató referenciákat akarnánk továbbítani, végtelen típust kapnánk, így le sem fordulhatna a programunk). Mivel az arrow -k ezeken az adatokon dolgoznak, magukra a folyamokra nincs rálátásuk (azaz a teljes folyamhoz nem férnek hozzá), így nincs értelmes megvalósítása az app műveletnek. Természetesen lehet olyan műveletet definiálni, amelynek megfelelő a típusa, csak sok hasznunk nem származik belőle. Egy példa: instance ArrowApply SF where app = SF $ concat ◦ (map (λ(SF f , x ) → f [x ])) Látszik, hogy némi trükközésre van szükség, hogy egyáltalán futtatható kódot kapjunk. A bejövő adatokat formálisan folyammá kell alakítani, ami ebben az esetben csak abból áll, hogy egyelemű listaként kötjük be őket a szintén a bemeneten kapott arrow -ba. Ezzel viszont pont az állapottal rendelkező arrow -k vesztik értelmüket, hiszen csak az első időpillanatuk jöhet létre. Másszóval csak a tiszta függvényekből arr -ral létrehozott arrow -k fognak a tőlük elvárható módon működni ebben a környezetben. Be lehet látni, hogy az app segítségével a first és a left is kifejezhető, így ezeknél nagyobb a kifejezőereje: first f = arr (λ(a, b) → (f > > > arr (λx → (x , b)), a)) > > > app → (arr (λ(Left x ) → x ) > > >f > > > arr Left , ab) left f = arr (λab → case ab of Left Right → (arr (λ(Right x ) → Right x ), ab)) > > > app Az app kombinátor annyira sokoldalú, hogy az őt támogató arrow -k monádokká is alakíthatók! A számításokat „bemenet nélküli” arrow -val modellezzük: newtype ArrowMonad arr a = ArrowMonad (arr () a) Ezután a return és a > >= implementációjára van szükség: instance ArrowApply a ⇒ Monad (ArrowMonad a) where return x = ArrowMonad $ arr (const x ) ArrowMonad m > >= f = ArrowMonad $ m > > > arr (λx → let ArrowMonad h = f x in (h, ())) > > > app Az alapelv egyszerű: f egy arrow -t ad vissza, amelyet kicsomagolunk és egy () kíséretében az app-nak átadunk. Ebből is látszik, hogy azok az arrow -k az érdekesek, amelyek nem támogatják az app műveletet, mivel ellenkező esetben célszerű közvetlenül monádokat használni.

Felhasznált források 1. John Hughes: Programming with Arrows, in 5th International Summer School on Advanced Functional Programming, LNCS 3622, pp 73-129, Springer, 2005 2. Ross Paterson: A New Notation for Arrows, in ICFP 2001, Firenze, Italy, pp 229-240. 3. My Evolution as a Haskell Programmer: Factorial with Arrows http://onthebalcony.wordpress.com/2007/02/19/my-evolution-as-a-haskell-programmer/ 4. Arrows in Haskell: bumpy first steps http://www.blurty.com/talkread.bml?journal=claudiusmaximus&itemid=105502 5. ArrowLoop http://d.hatena.ne.jp/propella/20070904/p1

12