Scheme aneb programujeme funkcionálně

2008-01-01 21:09 napsal Lukáš Havrlant

Tenhle článek se bude zabývat především programovacím jazykem Scheme, jakožto jednoho ze zástupců funkcionálního programování.

Představení imperativního paradigma

Předpokládám, že každý zná alespoň nějaké střípky z imperativního paradigma. Že ne? Ale jo, určitě jste už něco programovali v nějakém procedurálním jazyku (C, PHP, Pascal, …), což je právě imperativní paradigma. Nejprve bych stručně charakterizoval procedurální jazyky a na základě této charakteristiky bych vysvětlil jaký je rozdíl mezi funkcionálním a imperativním paradigmatem.

Klasický procedurální jazyk staví na efektu postupného provádění částí kódu a na efektu přiřazení. Efekt přiřazení je asi nejtypičtější rys procedurálního jazyka, je to ono magické prom=funkce(); (prom:=funkce(); v Pascalu) nebo prostější a=10; b=a; apod. Každou chvíli něco do něčeho ukládáme a následně s tím pracujeme. Dalším typickým rysem je použití cyklů. Chceme-li něco provádět vícekrát, obvykle použijeme nějaký vestavěný cyklus; klasicky for nebo while. Procedurální jazyky mají obvykle složitou syntax a mají také přísnější pojmenování identifikátorů funkcí a proměnných.

Scheme

Teď se vrhneme na funkcionální programování, tedy na Scheme. Scheme není čistě funkcionální jazyk, protože obsahuje procedury vyvolávající vedlejší efekty (například zde existuje příkaz přiřazení, typický rys z imperativního paradigma). Scheme má ve své podstatě strašně jednoduchou syntax, ale o to složitější sémantiku. Zapsat syntakticky správně program je téměř triviální, ovšem zapsat ho tak, aby dával smysl je již horší.

Nyní by se slušelo upozornit na to, že funkcionální programování je naprosto, ale opravdu naprosto, odlišné od „běžného“ programování v jazycích typu C (procedurální jazyky). Je to asi jako byste se pár let učili anglicky a německy a pak přešli na čínštinu. Prostě je to úplně jiná dimenze. Zapomeňte na efekt přiřazení. Zapomeňte na cykly. Zapomeňte na všechno na co jste byli zvyklí…

Prefixová notace

Jak v běžném jazyku zapíšete součet tři plus pět? Asi takhle, že jo? 3+5. Tak se to rychle odnaučte, jestli chcete Schemovat, protože Scheme používá tzv. prefixovou notaci, což znamená, že na prvním místě je operace a na dalších pozicích jsou operandy. Takže tři plus pět byste ve Schemu zapsali jako (+ 3 5). Ze začátku to bude dělat trochu guláš, ale postupem času si na to zvyknete a přijdete na výhody tohoto zápisu. Třeba když chcete sečíst vícero čísel, stačí vám stále jen jedno plus: (+ 1 2 3 4 5 6). Výsledek tohoto výrazu by byl 21. Další výhoda je v jednoznačnosti. V Céčku závorky ve výrazech můžete psát, ale nemusíte, takže z toho místy může vzniknout trochu nepořádek. Ve Schemu prostě ty závorky napsat musíte, jinak se ten výraz vůbec nevyhodnotí. Třeba 2+3*4 ve Schemu s prefixovou notací zapíšeme takto: (+ 2 (* 3 4)).

Trochu blbé je, že prefixové je všechno, takže třeba zápis if(a>b) by ve Schemu vypadal takhle: (if(> a b)), což je dost nepřehledné a pořádně jsem si na to nezvykl doteď.

Symbolický výraz – všechno je vším

Tohle je asi úplně nejšílenější. Všechno může být vším, což částečně plyne z předchozí prefixové notace. Nejen že operátory píšeme na začátek seznamu (seznam je jednoduše řečeno několik symbolů oddělených mezerami a ohraničeny závorkami – třeba předchozí zápis se sčítáním (+ 1 2 3 4 5 6) je seznam.), ale i jakékoliv jiné procedury píšeme na začátek seznamu a další výrazy jsou argumenty procedury. Nové vazby vytváříme pomocí speciální formy define. Třeba tenhle výraz (define cislo 10) vytvoří vazbu ze smybolu cislo na číslo deset. Nic nečekaného. Když si necháme v interpretu vyhodnotit cislo, vrátí nám to 10. Novou proceduru můžeme vytvořit podobně:

(define proc
  (lambda(a b)
    (+ (* a a) (* b b))))

Tahle procedura vrací součet druhých mocnin předaných argumentů. A teď přijde ten hardcore. Tuhle proceduru můžeme předat jako argument úplně jiné procedury. Interpret Schemu totiž postupuje tak, že prochází seznamy a hledá vazby jednotlivých symbolů a následně je provede, přičemž je mu úplně šumafuk, jakou vazbu ten symbol má. Pokud provedeme třeba tohle: (define plus +), můžeme používat symbol plus úplně stejně jako normální symbol sčítání. Interpretu je jedno co se jak jmenuje (téměř) a co se kde aplikuje. Zkrátka jen suše vyhodnotí vazbu a provede co chceme.

Příklad: mějme tuhle proceduru:

(define porovnej
  (lambda(procedura a b c)
    (if(> (* c c) (procedura a b))
    #t
    #f)))

Tahle procedura bere čtyři argumenty – proceduru a tři čísla. Samozřejmě nikde není explicitně definované, jaké typy argumentů musíme předat, ale předáme-li špatné typy argumentů, program prostě dále při aplikaci vyhodí chybu. Procedura porovnej porovnává, jestli je větší druhá mocnina c nebo výsledek aplikace předané procedury na argumenty a a b. Příklad aplikace procedury porovnej:

(porovnej proc 2 3 4)

Proceduru proc jsme sepsali výše. Takže nejprve se provede umocnění čtyřky na druhou a poté se provede součet druhých mocnic 2 a 3. 16>13, výraz nám vrátí #t.

Otázka pro bystřé kluky a holky – jaký bude výsledek posledního řádku?

(define plus +)
(define + -)
(define - plus)
(+ 10 5)

Kdo si tipl pět, má bod; kdo tipl patnáct, nemá pro funkcionální programování vlohy; kdo tipl něco jiného, nemá vůbec pro programování vlohy ;o).

Filtrování prvků

Předchozí příklad s procedou jako argumentem nebyl úplně vhodný, protože byl více méně nesmyslný. Ale co třeba tohle? Představme si proceduru, která bere jako argument predikát (proceduru vracející buď #t nebo #f) a následně odstraní ze seznamu všechny prvky, které neodpovídají danému predikátu. Proceduru napíšeme snadno:

(define filter
  (lambda(pred? sez)
    (foldr (lambda(x y) (if (pred? x)
                            (cons x y)
                            y)) '() sez)))

Nebudeme teď moc rozebírat jak to funguje, na to by bylo třeba pár lekcí Schemu. Jen zdůrazním, že procedura filtr bere jako první argument predikát a jako druhý argument seznam. Možné příklady aplikace:

> (define seznam '(1 2 3 4 5 6 7 8 9 10))
> (filter even? seznam)
(2 4 6 8 10)

Predikát even? (mimochodem si všimněte, že ve Schemu bývá zvykem predikáty, vracející jen pravdivostní hodnoty, zakončovat otazníkem; příjemná konvence.) zjišťuje, zda je číslo sudé. Procedura vyfiltrovala všechna čísla, která nejsou sudá.

Další příklad:

> (filter (lambda(x) (> x 5)) seznam)
(6 7 8 9 10)

Tentokrát jsme si již vytvořili vlastní predikát, který zjišťoval, zda je číslo větší než pět. Čísla menší nebo rovna pěti procedura vyfiltrovala.

> (filter (lambda(x) (and (even? x) (> x 5))) seznam)
(6 8 10)

Teď jsme ponechali jen ta čísla, která jsou sudá a zároveň jsou větší než pět. Podobných příkladů najdeme plno…

Mapujeme…

Další užitečná procedura je map, která provádí mapování seznamu – na každý prvek seznamu aplikuje námi předanou proceduru. Opět si to ukážeme na příkladech:

> (map - seznam)
(-1 -2 -3 -4 -5 -6 -7 -8 -9 -10)

Zde jsme aplikovali operátor odčítání na předchozí seznam, takže všechna čísla nyní mají opačnou hodnotu. Další příklad:

> (map (lambda(x) (* x x)) seznam)
(1 4 9 16 25 36 49 64 81 100)

Zde jsme umocnili všechny prvky seznamu na druhou.

> (map (lambda(x) (>= x 6)) seznam)
(#f #f #f #f #f #t #t #t #t #t)

A nakonec jsme si zjistili, která čísla jsou větší nebo rovna šesti.

Něco takového lze pravděpodobně udělat třeba pomocí pointerů v Céčku, nejsem si tím každý. Každopádně to nebude tak elegantní jako ve Schemu, kde se to prostě používá naprosto běžně.

Cykly? E-e…

Zapomeňte na cykly, to jsem myslel vážně. Ve Schemu nejsou nebo se přinejmenším nepoužívají (tuším, že tam snad i nějaký cyklus je – on by v podstatě měl jít naprogramovat, ale zkrátka se nepoužívá). Všechno se řeší pomocí rekurze a iterace, což je místy docela šílenost. Třeba faktoriál vypadá ve schemu takhle:

(define fak
  (lambda(n)
    (if (<= n 1)
        1
        (* n (fak (- n 1))))))

A Fibonacciho posloupnost takto:

(define fib-iter
  (lambda(n)
    (let fib((a 0)
             (b 1)
             (n n))
      (if(< n 1)
         a
         (fib b (+ a b) (- n 1))))))

A to jsem ještě nepředstavil tzv. y-kombinator. To je hezká věcička. Myslíte si, že je možné provést rekurzi bez toho, aniž bychom tu proceduru nadefinovali? Tedy bez použití define? Do normálního jazyka bych tu otázku převedl takto: Je možné zacyklit funkci, kterou deklarujeme takhle…

function mojeFunkce(a, b, c…)
{
  //tělo funkce
}

…bez toho, aniž bychom v těle této funkce zavolali mojeFunkce()? Ve Schemu to jde docela jednoduše. Ještě předtím si ale musíme uvědomit jednu milou skutečnost. A sice, že tohle (lambda(x) (* x x)) se vyhodnotí na proceduru. Interpret vám po aplikaci toho kódu zobrazí #<procedure>. A na tuto proceduru můžete dále aplikovat argumenty. Takže třeba tohle: ((lambda(x) (* x x)) 5) se již vyhodnotí na 25. Lambda se opět vyhodnotí na proceduru a tahle procedura bere jediný argument – a my jí hned předáme pětku, takže interpret hodí do té procedury pětku a vrátí nám dvacet pětku. A teď ten y-kombinator:

((lambda(y) (y y 5))
 (lambda(fac n) (if(= n 0)
               1
               (* n (fac fac (- n 1))))))

Takže jak to teď proběhne: První lambda se vyhodnotí na proceduru beroucí jeden argument y. Tu okamžitě aplikujeme a jako argument jí předáme další – jinou – proceduru. Teď zpět k první lambdě. Vidíte tam tu magickou formuli y y 5? To znamená jen jediné. Zavolej proceduru, kterou jsme předali v argumentu a jako argument této volané procedury předáme tu samou proceduru. Poté předáme číslo, ze kterého chceme ten faktoriál počítat. Vidíte už trochu tu rekurzi? Vzhledem k tomu, že můžeme směle proceduru předat jako argument, můžete také pomocí argumentů provádět rekurze – stačí, když zavoláme tuto proceduru z argumentu a jako argument jí dáme zase tu proceduru z argumentu. Krása, ne? :-) Ještě bych rád upozornil na to, že to je spíše perlička, tak se hned nelekněte (u nás to málokdo pochopil na přednáškách a cvičeních, takže když jste princip y-kombinatoru nepochopili, neděste se).

Efekt přiřazení? E-e…

Zapomeňte na to, že si budete ve výpočtech ukládat nějaké hodnoty. Takhle to ve funkcionálním programování nefunguje. Ani dost dobře nemůže, protože ve funkcionálním programování jde především o postupném aplikování procedur, kde jako argumenty jsou předávány výsledky aplikace jiných procedur. Žádné zbytečné ukládání. Jedinou výjimku tvoří tzv. let-bloky, pomoci kterých můžeme ukládat hodnoty a poté pouze v těle tohoto let-bloku s nimi můžeme pracovat. V praxi to slouže jen pro ukládání hodnot, které bychom jinak museli počítat vícekrát. Například pokud v některé části kódu potřebujeme znát délku seznamu více než jednou, nebudeme při každém použití délky seznamu tu délku znova počítat, ale navážeme si tu délku na nějaký symbol. Jinak let-bloky prakticky nepoužíváme.

Závěrem…

…bych měl pár slov a odkazů pro ty, kterým se Scheme zalíbil. Ještě bych měl ale upozornit na to, že Scheme je v praxi více méně nepoužitelný jazyk a neznám obor, kde by se Scheme uplatnil. I když jsem slyšel o tom, že se Scheme používá při programování pluginů do Gimpu ;-). Nicméně je to dobrý odrazový můstek třeba pro LISP, který už by měl být použitelnější. Scheme je více méně klasický jazyk na učení, něco jako Pascal.

Jako interpret Schemu používám DrScheme (s jazykem „Pretty Big“, ostatní neznám – Language → Choose language → PLT → Pretty Big) a jestliže se chcete do Schemu ponořit naplno, stáhněte si PDF od dua Vychodil-Konečný. Nic lepšího v češtině nejspíše nenajdete.

Proč se mi Scheme líbí?

Scheme je krásný jazyk, obecně mě to funkcionální programování docela vzalo. Když něco programuju procedurálně, ať dělám co dělám, vždycky z toho vyjde prasárna. Neumím programovat v nějakém normálním jazyku tak, aby to bylo tak hezké, jako bych to napsal ve Schemu. Jako příklad na zkoušku ze Schemu jsem měl naprogramovaný determinant matice a inverzní matice. A když se teď na ten kód kouknu, je mi více méně jasný a na každém řádku vím co dělám.

(define determinant
  (lambda(matice)
    (if (ctvercova? matice)
        (let det((matrix (vynuluj-sloupec matice))
                 (nasobek 1))
          (if matrix
              (if(= (length matrix) 1)
                 (* nasobek (reditel matrix))
                 (det (vynuluj-sloupec (zbytek matrix)) (* nasobek (reditel matrix))))
              0))
        #f)))

I teď po měsící zkrátka vím o co jde. Jo a tohle samozřejmě není celý kód, je to jen ta hlavní procedura. Kdybych to napsal v céčku, vzejde z toho strašná prasárna…

Linkuj.cz!

Komentáře

Komentáře jsou uzavřeny