Selles peatükis võrdleme normaaljärjekorras- ja aplikatiivjärjekorras redutseerimist. Kumba eelistada ja mis on eelised ja puudused. Meenutuseks: normaaljärjekord redutseerib alati välimise vasakpoolse alamtermi ja aplikatiivjärjekord redutseerib alati sisemise vasakpoolse alamtermi.
Normaaljärjekorras redutseerimise eeliseks on, et ei redutseerita argumente mida ei kasutata. Näiteks term (λx. 0) (fact 100) väärtustub nulliks ühe sammuga, kuigi fact 100 väärtustamiseks võib minna väga palju samme. Seega võime funktsiooni argumendina kasutada ka terme, millel endal pole normaalkuju.
Vaatame makrodefinitsiooni from := Y (λf n. cons n (f (add 1 n))), mis seab igale täisarvule vastavusse lõpmatu listi alates sellest arvust. Vaata termi from 1 reduktsiooni ja pane tähele, et sellel puudub normaalkuju.
|
Aplikatiivjärjekorras redutseerimisel ei saa sellist definitsiooni kasutada, kuna sellist alamtermi sisaldav termi redutseerimine ei termineeru kunagi. Normaaljärjekorras redutseerimisel saame aga võtta selle lõpmatu listi peas oleva väärtuse. See tähendab, et argumenti from 1 väärtustatakse vaid niikaua, kuni selle peasse tekib cons — siis läheb redutseerimisele välimine δ-reedeks.
|
Lisaks, saame defineerida funktsiooni, mis võtab lõpmatu listi algusest etteantud arvu elemente. Vaata järgnevalt defineeritud funktsiooni take. Sellise funktsiooni kasutamine töötab samuti vaid eeldusel, et argumenti ei redutseeritaks oluliselt rohkem kui seda vaja läheb.
Vaata järgnevat normaaljärjekorras reduktsiooni. Paneme tähele, et reduktsioonijada on üsna pikk (tegelikult 34 sammu) isegi kui võtame lõpmatust listist vaid kaks elementi. Lisaks on näha, et mingid reduktsioonid korduvad: sub 2 1 redutseetitakse esimese take rakenduse juures väärtuseks 1 aga hiljem tuleb see uuesti teha sub (sub 2 1) 1 juures. Samamoodi tuleb arvutada tl (from 1) ja siis hiljem jälle otsast peale tl (tl (from 1)).
|
Reduktsioonisamme tuleks vähem (kokku 24), kui alamterm from 1 redutseerida esmalt termiks cons 1 (cons 2 (from 3)). Aga ka see pole kaugeltgi optimaalne.
Reduktsioonisammude arvu vähendamiseks on mitu erinevat strateegiat. Üks viis oleks analüüsida kasutatud funktsioone, et teada saada, kas mõnda argumenti, mida kasutatakse funktsiooni kehas mitmes kohas ja on igal juhul vaja välja arvutada. Meie näites on selline argument take-i esimene argument n. Sellisel juhul on mõistlik argument väärtustada enne funktsioonikutset. Mida aga teha take-i teise argumendiga xs? Seda on kasutatud vaid cond-i teises harus — kuid seal kaks korda. Seega ei tohi me püüda seda enne funktsioonikutset väärtustada, kuna väärtustamine ei pruugi termineeruda samas kui selle väärtust tegelikut vaja ei lähe.
Vahemärkusena, kindlasti vajamineva argumendi väljaarvutamine enne funktsioonikutset võib olla ka praktiliselt otstarbekas. Laisk keel Haskell ei väärtusta üldjuhul foldl funktsiooni argumente enne funktsioonikutset. Sellel on aga jõudluses tagajärjed. Seetõttu on Haskelli standardteegis funktioon foldl', mis väärtustab teise argumendi enne funktsioonikutset. Vaata järgnevaid näiteid, kus vastavad fold-i kasutades liidetakse listi [10,20,30] elemendid.
|
Näeme, et tulemus ei muutu ja tehtud sammude arv on sama. Seetõttu võib olla üllatav, et agar funktsioon foldl' on palju kiirem. Vaata Haskelli REPL-is testimist, kus kümne miljoni arvu liitmisel tuleb kümnekordne vahe jõudluses.
| *Main> time $ print $ foldl (+) 0 [0..10000000] 50000005000000 2.895953s *Main> time $ print $ foldl' (+) 0 [0..10000000] 50000005000000 0.268244s |
Haskelli kompilaator GHC sisaldab palju optimeeringuid ja tehnikaid, et lõpmatuid vahestruktuure sisaldav kood võimalikult kiiresti jookseks.Haskellis on kasutatud n.n. graafireduktsiooni, mis tähendab, ühe monoliitse termi asemel on meil definitsioonid ja term, mille sees võivad olla viidad. Kui viida kaudu üht alamtermi väärtustad, siis sama viita kasutav term lõikab sellelt automaatselt kasu. Öeldakse ka, et need alamtermid on jagatud. Tekstuaalsel kujul on tavaks sellist graafi kirjeldada where-dega, mis tuleb mängu siis kui sama parameetrit kasutatakse mitmes kohas ja argument ei ole juba normaalkujul. Näiteks võib see välja näha järgnevalt. Erinevalt Idrisest ei pea Haskellis tüüpe kirjutama. Mittetühja listi konstruktoriks on üks koolon.
Laisk väärtustamine laiemas mõttes ongi funktsiooni argumentide väärtustamie edasilükkamine (näiteks kasutades normaaljärjekorda) kasutades jagamist. Väärtustamine kitsamas mõttes on üks konkreetne viis kuidas normaalkujuni jõuda ilma termi reduktsioonisammudga teisendamata — seda vaatame peatükiks 13.
Kokkuvõtteks, normaaljärjekorras väärtustamine võib leida normaalkuju ka siis kui aplikatiivjärjekorras seda leida ei õnnestu. Sellisel juhul ei pea programmeerija muretsema lõpmatutest definitsioonidest hoidumisest. Samas ei pruugi normaaljärjekorras väärtustamine olla kiirem aplikatiivjärjekorras väärtustamisest. Praktikas kasutatakse reduktsiooni kiiruse tõstmiseks funktsiooni argumentide kasutuse analüüsi ja jagamist/graafireduktsiooni.
Laisa väärtusamise miinuseks on väiksem jõudlus, suurem mälukasutus ja tööaja hindamise suurem keerukus. Seetõttu on populaarsed ka agarad funktsionaalsed keeled nagu Swift, Lisp, OCaml, Erlang jne. Ka kompileeritud Idrise programmid väärtustatakse aplikatiivjärjekorras. Lisaks on peaaegu kõik multi-paradigma keeli, kus saab FP stiilis programmeerida, agarad.
Samas on ka vaikimisi agarates keeltes võimalik kasutada laiskust ja lõpmatuid struktuure. Näiteks Idrises on tüübikonstruktorid Lazy ja Inf ning funktsioonid Delay ja Force. Esmalt vaatame andmetüüpi Stream, mis on standardteegis defineeritud järgnevalt.
| 1data Stream a = (::) a (Inf (Stream A)) |
Defineeritud on vaid üks konstruktor (::) : a -> Inf (Stream a) -> Stream a, kuna tühja striimi olemas ei ole.
Konstruktori esimene argument on striimi pea ja teine argument on saba, mis on pandud Inf kontruktsiooni sisse. Enamasti saab Idris ise hakkama tüüpide A ja Inf A vahel teisendamisega. Harva on ise vaja panna mõni Delay või Force.
| Main> the (Inf Int) (5+5) Delay (5 + 5) Main> Force (the (Inf Int) (5+5)) 10 |
Ehk, kui tahame listi ühest seitsmeni, saame kirjutada [1..7] ja selle väärtustamine annab [1, 2, 3, 4, 5, 6, 7]. Kui tahame striimi ühest lõpmatuseni, kirjutame [1..]. Pane tähele, et seda ei arvutata välja kaugemale kui üheni. Aga kui võtame esimesed seitse elementi sellest lõpmatust listist, siis saame jälle sama tulemuse nagu [1..7].
| Main> [1..7] [1, 2, 3, 4, 5, 6, 7] Main> [1..] 1 :: Delay (countFrom 2 (\arg => prim__add_Integer 1 arg)) Main> take 7 [1..] [1, 2, 3, 4, 5, 6, 7] |
Lõpmatute andmestruktuuride kasutamise motivatsiooniks on võimaldada eraldada vahestruktuuri loomist tarbimisest. Näiteks kirjeldas vanakreeka matemaatik Eratosthenes viisi kuidas leida algarvude tabelit, viisil, kus lõpmatust arvude jadast 2, 3, 4, 5, 6 jne. filtreeritakse välja kõigepealt kahest suuremad kahekordsed, siis kolmest suuremad kolmekordsed, siis neljast suuremad neljakordsed jne. Alles jäävad algarvud. Järgnev kood implementeerib Eratosthenese algoritmi Idrises. Seejärel saab kuus esimest algarvu välja arvutada avaldisega take 6 primes mis tagastab listi [2, 3, 5, 7, 11, 13]
| 1filter : (a -> Bool) -> Stream a -> Stream a 2filter p (x :: xs) = 3 if p x then 4 x :: filter p xs 5 else 6 filter p xs 7 8iterate : (a -> a) -> a -> Stream a 9iterate f x = x :: iterate f (f x) 10 11sieve : Stream Int -> Stream Int 12sieve (p::xs) = filter (\x => x `mod` p /= 0) xs 13 14primes : Stream Int 15primes = map head (iterate sieve [2..]) |
See kood on Idrises natuke kohmakas (ja aeglane). Laisusele optimeetirud keeles Haskell saame kasutada standardteegi funktioone filter ja iterate ning ei pea kirjutama sieve tüüpi. Haskelli versioon Eratosthenese algoritmist on järgnev.