Někteří (snad i většina) z vás už někdy viděli program. Programy jsou napsány v
něčem co se nazývá programovací jazyk. Žijeme v (relativně) svobodném světě a
tak není divu, že programovacích jazyků existuje celá řada. BASIC, Pascal, C,
C++, Java, Perl - něco z toho jste už určitě viděli. Ti, kteří znají některý z
těchto nebo jiných běžných jazyků, mi jistě dají za pravdu, že tyto jazyky se
liší jen velmi málo. Některé jsou interpretované, některé kompilované (z
principu, může být každý \"slušný\", tj. neautomodifikující se program to i to),
některé umí navíc to (perl má regexy), některé zas ono (Java běží v VM). Ale
když se na ně podíváte trošku důkladněji tak zjistíte, že jsou vlastně totožné
(semanticky). Jsou to totiž imperativní jazyky. Jazyky založené na imperativním
(přikazovacím?) paradigmatu (světonázoru). Toto paradigma se dá popsat asi
takto:
Každý program se skládá ze tří základních konstrukcí: přiřazení (destruktivní
aktualizace), větvení a cyklu (explicitní iterace). Proces je vyjádřen
implicitním stavem (aktuální místo vykonání v programu + obsah proměnných). V
zdrojovém kódu explicitně vyjadřujeme JAK se má co vykonat, pořadí vykonávání
je explicitně dáno. Toto paradigma je \"přirozené\" pro dnešní počítače (díki
destruktivní aktualizaci) a proto rychlé (pouze z hlediska běhu!!) a proto je
96% dnes používaných jazyků pojmuto tímto paradigmatem.
Rychlost běhu programu je sice hezká věc, jenže nežijeme v 50. letech minulého
století a tak nás dnes zajímají i jiné věci. Z těch nejméně důležitých bych
jmenoval např. formální ověřitelnost programu, rychlost naprogramování
aplikace, maintainability apod. Ve všech těchto ukazatelích imperativní
programování těžce pokulhává. Objasním jen formální ověřitelnost (na ukázku).
Každý formální zápis v nějakém formálním (vnitřně nesporném) systému musí,
proto aby byl dokazatelný, splňovat mimojiné požadavek na tzv. referenční
transparentnost. Tj. aby ten samý výraz vždy representoval stejnou hodnotu. Tj.
aby x=x. Toto v imperativních jazycích principielne dodrženo není. (x=2*x
např.), díki destruktivní aktualizaci (přiřazení). Program tedy principielně
není možno dokázat.
No, nevím jak vás, ale mne představa toho, že se nezbavím debugovaní dost
*censored*. Naštěstí existují i jiná paradigmata než imperativní (fuj fuj
Jedním z nich je i tzv. funkcionální. Abych vás nalákal tak uvedu výhody tohoto
paradigma (toto jsem obšlehl ze skript VUT Brno):
S programy se lépe matematicky pracuje - to znamená nejen dokazatelnost (tam
kde to jde principielně, ne všude!) ale i možnost různých optimalizací
Existuje lepší mechanismus abstrakce - programy (zdrojáky) jsou kratší(výrazně!)
Nové algoritmické přístupy - např. lazy evaluation (o tom nemá cenu mluvit to
se musí vidět!!)
Obecně nový přístup k programování - např. transformace apod.
Možnost brutálního paralelismu - nezáleží na pořadí vhodnocování a tak lze
vyhodnocovat paralelně - to brutálně tam vážně patří
Bystří to mozek a rozšiřuje obzory :
Toto paradigma se dá ve zkratce (která vám stejně nic neřekne) popsat asi takto:
Program NEMÁ implicitně daný stav. To například znamená, že nemá proměnné.
V programu vyjadřujeme CO se má dělat, aniž bysme nějak specifikovaly JAK. V
efektu to znamená, že program nemá příkazy (a tím i jejich explicitně dané
pořadí).
Nabízí se otázka: \"co v tom zdrojáku teda je?\". Funkcionální jazyk chápe jako
všechno jako funkci (obecně n proměnných). Funkci ve smyslu Lambda kalkulu (tj.
jako posloupnost výpočetních pravidel) ne jako v diskrétní matematice popř.
matematické analýze. Tedy, že funkce je \"černá skříňka\" do které data nasypete
a ona vám je vysype. Programy se tvoří jako kompozice funkcí, které mohou být
zase další kompozicí až k atomickým funkcím.
příklad:
add a b = a + b
program = add (read-from-keyboard) (read-from-keyboard)
kde read-from-keyboard je primitivum na čtení z klávesnice. Jak vidno v
programu nikde není řečeno JAK se co má vykonat, pouze je zde deklarováno, že
program je tvořen aplikací funkce add na dva argumenty, ktere jsou aplikací
funkce read-from-keyboard. Také je vidět, že zde nejsou žádné proměnné (a a b
nejsou proměnné ale argumenty funkce)
Zatím ovšem také nic zajímavého. Zajímavé se funkcionální programování stane,
když uvedu, že funkcionální jazyky přirozeně operují nad seznamy (množinamy).
příklad:
qsort [] = [] (1)
qsort (a:as) = qsort [ x | x<-as, x<=a ] ++ [a] ++ qsort [ x | x<-as, x>a ] (2
alias quick-sort na dva řádky. První řádek říká, že seřazením prázdného seznamu
dostaneme prázdný seznam. Druhý řádek definuje funkci qsort neprázdného seznamu
ve kterém je první prvek pojmenovan a a zbytek seznamu as takto: aplikuj
rekurzivně funkci qsort na seznam všech x z množiny as takových, že jsou menší
nebo rovna a, spoj takto získaný seznam s a a dále ho spoj se seznamem, který
je výsledkem aplikace funkce qsort na seznam všech x z množiny as takových, že
jsou větší než a.
Nevím jak vám, ale mně se to líbí.
Nyní k oné proklamované dokazatelnosti:
Zkusíme dokázat, že námi definovaný qsort opravdu třídí (tento důkaz je made by
neologism, takže pokud je to blbost, tak to berte jakože zkouším jestli si toho
všimnete :-) )
1) dokážeme, že qsort [] dá setříděný seznam. dle (1) qsort [] = [], takže asi
ano (protože vzestupně setříděný seznam je definovaný jako seznam [a0,a1,a2..an]
, kde pro všechna m (0<=m<=n) platí am<=a(m+1), což zde evidentně platí )
2) za předpokladu, že platí, že (qsort list) je vzestupně setříděný seznam (3)
dokažme, že (qsort (a:list)) je také vzestupně setříděný.
dle (2) (a díki referenční transparentnosti!) je
qsort (a:list) = qsort [ x | x<-list, x<=a ] + [a] ++ qsort [ x | x<-list, x>a ]
qsort [ x | x<-list, x<=a ] je dle (3) setříděný seznam l1=[a0,a1,a2..a(n-1)]
kde a(n-1)<=a, stejně tak qsort [ x | x<-as, x>a ], je dle (3) setříděný seznam
l3=[a(n+1),a1(n+2),a2(n+3)..am], kde a<=a(n+1), položka a tvoří seznam l2.
spojením těchto tří seznamů (l1,l2,l3) dostaneme vzestupně setříděný seznam.
Důkaz je u konce.
Další příjemnou věcí funkcionálních jazyku (přinejmenším některých) je tzv.
líné vyhodnocování (lazy evaluation).
Toto znamená, že výsledky jsou vypočítány až ve chvíli, kdy jsou doopravdy
potřeba. tj. např. při kompozici funkcí f.g, je g volána tak, jak to požaduje
funkce f, tj. může se stát, že funkce g se nezavolá ani jednou. Toto umožňuje
jednu krásnou věc - nekonečné seznamy. Pokud se ťukáte do hlavy a odvracíte
zrak s poznámkou o omezenosti paměti, pak radím prostudovat tento odstavec
ještě jednou.
příklad:
primes = r [2..]
r (l:list) = [l] ++ r (filter (not.(== 0).(`mod` l)) list
takto jsou definována VŠECHNA prvočísla (podotýkám že prvočísel je neomezeně
mnoho), v programu potom tedy můžete použít tuto funkci jako zdroj nekonečně
mnoha prvočísel. Jistě dokážete vymyslet i další příklady.
Jak vidno, tak funkcionální jazyky svým inovativním přístupem odstraňují
většinu nevýhod imperativních jazyků. Programy jsou dokazatelné, rychleji
napsané, reusability v pojetí funkcionálních jazyků je doopravdy NĚCO. (které
funkce z Cčka používéte doslova pořád? a nemyslím věci jako printf apod.) Cenou
za toto je ovšem jistá neefektivnost na dnešních počítačích (což je dáno jejich
Von Neumannovou podstatou - tj. nijak lehce odstranitelné). Ovšem díki daleko
vyššímu stupni abstrakce poskytují funcionální jazyky větší prostor pro
optimalizaci což neefektivitu do jisté míry eliminuje. Ovšem pravdou zůstává,
že \"kapku\" pomalé to je. (což ale neznamená nic jiného než, že je potřeba dále
zkoumat!
Ani omylem jsem nevyčerpal vše co funkcionální jazyky nabízí (např. v LISPu
mají data i kód stejnou strukturu apod., Haskell umi pattern matching, higher
order functions apod.), ale doufám, že jsem aspoň trošku ukázal, že tyto jazyky
stojí zato a jsou mnohdy daleko lepší a vhodnější pro daný úkol než konvenční
imperativní jazyky.
Tento článek si neklade za cíl někoho naučit programovat ve funkcionálním
programovacím jazyce, chce jen upozornit na existenci jiných (a imho daleko
zajímavějších a lepších) způsobů jak \"dělat do počítačů\". Berte prosím tento
článek tedy tak a nevytýkejte mi needukativnost/nesystémovost apod..
Jo a doufám, že diskuse pod článekem bude k tématu a ne o tom, že jsem idiot,
neumím českou gramatiku atak vubec. Děkuju.
neologism (aktuálně šíleně zamilován do Haskellu ;)
Technické info:
příklady jsou psány v programovacím jazyce Haskell (www.haskell.org), za
použití interpretu hugs (www.haskell.org/hugs)
další jazyky: Lisp, Scheme, Miranda, Erlang, Concurrent Clean apod., ale
doporucuju Haskell
zajímavé čtivo:
hysteria.sk/~neologism/whyfp.ps,hysteria.sk/~neologism/haskell-98-tutorial.ps,
pokud vás funkcionální programování zajímá pak můžu jen doporučit knihu \"The
Craft Of Functional Programming - Haskell\" (a vyhněte se čemukoliv z JZD
Slušovice apod. - tam je předpokládána VELMI slušná znalost matematiky okolo ->
nepoužitelné, zajímavý je taky ACM Journal, ale zase je to příšerně složité ;( )neologism
