Místo cyklu rekurze
Oblíbenou datovou strukturou deklarativních programovacích jazyků jsou seznamy. Po minulém dílu jistě dobře porozumíte definici typu seznam:
:- type list(T) ---> []; [ T | list(T) ].
Seznam prvků typu T je buď prázdný seznam (označován jako []), nebo dvojice prvek typu T a seznam typu T, tradičně označované jako hlava a ocas a zapisované jako [ Hlava | Ocas ].
Chcete-li sečíst čísla v seznamu, připravíte si rekurzivní predikát:
:- pred secti(list(int)::in, int::out) is det. secti([], 0). secti([Cislo|Ocas], Soucet) :- secti(Ocas, SoucetOcasu), Soucet = Cislo+SoucetOcasu.
Implementace secti/2 má dvě „klauze“, každá klauze je jedna větvička switche (viz minulý díl) popisující právě jednu ze dvou možností hodnot vstupního seznamu. První klauze se použije pro prázdný seznam a ve výstupním parametru vrátí 0 (jinak nedělá nic, nemá tedy žádné tělíčko za nabodeníčkem :-). Druhá klauze se použije pro neprázdný seznam, napřed rekurzivním voláním zjistí součet ocasu a pak jej sečte s číslem v hlavě.
Právě jsme úkol, který tradičně řešíte pomocí for-cyklu, vyřešili pomocí rekurzivního volání. Protože mluvíme o Mercury, sluší se poznamenat, že kompilátor dokáže identifikovat a cíleně podporuje tzv. tail-rekurzi. Pokud predikát něco počítá a nakonec buď uspěje a vrátí výsledek, nebo zavolá sám sebe, aby výsledek vrátilo vnořené volání, může Mercury implementovat takový predikát tradičním for cyklem. Výhoda for cyklu je v tom, že není třeba uchovávat v paměti starší hodnoty proměnných, tj. zásobník rekurzivních volání. Mercury o deklarativním programu umí dokázat tuto vlastnost a implementovat ho úsporně procedurálně. (Naše implementace secti/2 není tail-rekurzivní, níže se však k takové implementaci snadno dopracujeme.)
Programování vyššího řádu: abstrakce nad algoritmy
Při programování člověka často napadne, že např. takové operace na seznamu, jako je sečtení všech prvků, součin všech prvků či výběr nejmenšího prvku, jsou si něčím nápadně podobné a že nechce stále dokola psát podobné programovací konstrukce. Pozorováním dospějete k tomu, že abstraktní algoritmus pro všechny popsané úkoly zní:
- pro prázdný seznam vrať danou počáteční hodnotu (pro součet 0, pro součin 1, pro minimum maxint)
- pro neprázdný seznam zjisti souhrnnou hodnotu ocasu a pomocí dané operace (součet, součin, minimum dvou čísel) vypočti souhrnnou hodnotu celého výsledku: součet/součin/minimum hlavy a ocasu.
Tradičně se tento abstraktní algoritmus na seznamu nazývá složení (fold) a v Mercury jsou k dispozici dvě varianty: složení zleva (foldl) a zprava (foldr). Předvedeme si pro srovnání implementace obou:
:- pred foldl(pred(T, Aku, Aku), list(T), Aku, Aku).
:- mode foldl(pred(in, in, out) is det, in, in, out) is det.
foldl(Operace, [], PocatecniHodnota, PocatecniHodnota).
foldl(Operace, [Hlava|Ocas], PocatecniHodnota, VystupniHodnota) :-
Operace(Hlava, PocatecniHodnota, PracovniHodnota),
% Zavolali jsme předaný predikát Operace s danými parametry
foldl(Operace, PracovniHodnota, VystupniHodnota).
:- pred foldr(pred(T, Aku, Aku), list(T), Aku, Aku).
:- mode foldr(pred(in, in, out) is det, in, in, out) is det.
foldr(Operace, [], PocatecniHodnota, PocatecniHodnota).
foldr(Operace, [Hlava|Ocas], PocatecniHodnota, VystupniHodnota) :-
foldr(Operace, PocatecniHodnota, PracovniHodnota),
Operace(Hlava, PracovniHodnota, VystupniHodnota). Signatura obou predikátů foldl/4 a foldr/4 je stejná: v prvním argumentu předáváme „skládací predikát“. Něco, co umí vzít prvek seznamu a dosavadní mezivýsledek a vrátit nový mezivýsledek (tedy predikát (in, in, out), kde mezivýsledek vstupní i výstupní musí mít identický typ Aku, ale připojovaný prvek se může typem lišit). Za skládacím predikátem musíme dodat seznam, který chceme projít a poskládat. Seznam musí mít samozřejmě správný typ, list(T), aby skládací predikát uměl s prvky seznamu pracovat. Dále nesmí chybět počáteční hodnota, a ve čtvrtém parametru dostaneme výsledek složení. Opět je zde vyžadován typ Aku, libovolný, ale stejný jako ten, který umí skládat skládací predikát.
Příklad použití foldl:
:- pred plus(int::in, int::in, int::out) is det. :- pred times(int::in, int::in, int::out) is det. :- pred min(int::in, int::in, int::out) is det. :- pred test is det. test :- Seznam = [1, 2, 3, 4], foldl(plus, Seznam, 0, SoucetSeznamu), foldl(times, Seznam, 1, SoucinSeznamu), foldl(min, Seznam, int__max_int, MinimumSeznamu).
Představte si postupné volání predikátů foldl. V prvním kroku je utržena hlava 1 a složena s počáteční hodnotou (např. sečtena s 0 nebo násobena 1). Pracovní výsledek je použit jako počáteční hodnota do rekurzivního volání. Hlava 2 je tedy složena s 1. Nakonec se použije první klauze predikátu: v prázdném seznamu není co s čím skládat a vstupní hodnota (dosavadní součet/součin/minimum) je rovnou vrácena na výstup. Náš příklad nevyužívá možnosti jiného typu pro akumulovanou hodnotu a pro prvky seznamu, Aku=T=int.
Rozdíl mezi foldl a foldr je v tom, že foldl napřed skládá a pak se noří hlouběji do seznamu, kdežto foldr se napřed noří, nechá poskládat celý ocas, a pak teprve výsledek složí s hlavou. Foldl tedy je tail-rekurzivní, protože napřed pracuje a pak se zavolá. Foldr není tail-rekurzivní, protože napřed volá sám sebe, a pak teprve pracuje.
Věřím, že se vám popsanou abstrakci for-cyklu podařilo vstřebat. Každý for-cyklus přes seznam lze totiž popsat pomocí této abstrakce: řekni, jak vypadá stav „akumulované proměnné“ na začátku, a řekni, jak se odvodí nový stav z dalšího prvku seznamu a dosavadní hodnoty akumulátoru.
Funkcionální programování
Abychom výše představený abstraktní for-cyklus implementovali „funkcionálně“, stačí místo predikátů hovořit o funkcích. Mezi predikátem a funkcí je ostatně rozdíl pouze syntaktický: funkce je predikát s jedním argumentem „navíc“, pro výstup.
:- func foldl(func(T, Aku) = Aku, list(T), Aku) = Aku.
:- mode foldl(func(in, in) = out is det, in, in) = out is det. Někdy je šikovnější pracovat s funkcemi, někdy s predikáty. Např. pro sečtení prvků v seznamu je určitě šikovnější práce s funkcemi, protože funkci (+) nalezneme přímo ve standardní knihovně a nemusíme implementovat predikát plus/3. Použití vypadá takto:
test :- SoucetSeznamu = foldl((+), [1,2,3], 0).
Výhoda funkcionálního způsobu vynikne, když si uvědomíme pohodlnost skládání funkcí.
Chtějme nyní vypočítat součet druhých mocnin prvků v seznamu. Budeme k tomu potřebovat funkci druhé mocniny a abstrakci operace „vypočti po prvcích“, která se tradičně nazývá map a najdete ji implementovanou v modulu list. Pro úplnost ji však vypíšeme i zde.
:- func sqr(int::in) = (int::out) is det.
sqr(X) = X*X.
:- func map(func(T)=S, list(T)) = list(S).
% :- mode map(func(in)=out is det, in) = out is det.
% Pro funkce je tento mód implicitní, netřeba zapisovat.
map(Operace, []) = [].
map(Operace, [Hlava|Ocas]) = [Operace(Hlava) | map(Operace, Ocas)].
% map prázdný seznam rovnou vrátí.
% u neprázdného seznamu převede hlavu na jinou hodnotu
% pomocí dodané funkce Operace. Celkově tedy aplikuje
% Operaci na všechny prvky seznamu. Slíbený součet druhých mocnin dostaneme takto:
test :- SoucetCtvercu = foldl((+), map(sqr, [1,2,3]), 0).
Perl jsem v perexu uvedl proto, abych k pochopení podstatných konceptů z programování nalákal i ty z vás, kteří rádi rychle „bušíte“ bez přílišného rozhlížení se. Nuže, v Perlu je také map, a používá se takto:
@seznam = (1, 2, 3);
@ctverce = map { $_ * $_ } @seznam;
# nyní stačí sečíst seznam @ctverce, což každé
# perlové čuňátko může napsat také pomocí mapu
# (fold v Perlu není)
$soucet_ctvercu = 0;
map { $soucet_ctvercu += $_ } @ctverce;
Pravé perlové čuňátko ovšem umí každý program napsat na jeden řádek:
$s = 0; map { $s += $_**2 } (1, 2, 3);
O čuňátcích mluvím záměrně, protože vnořený blok modifikuje proměnnou soucet_ctvercu jen jako postranní efekt. V Perlu stejně jako ve všech procedurálních jazycích je to sice legitimní postup, ale programátor se ve svých postranních efektech nezřídka utopí. V Mercury jsou postranní efekty zakázány (program nezkompilujete a dozvíte se čísla řádků, kde se o modifikaci vnějších proměnných pokoušíte), takže se utopit nemůžete.
Všechna řešení a curryování
Skalní zastánci Prologu (kdyby takoví měli důvod k bytí a byli) by se zlobili, že Mercury nenabízí predikát bagof nebo setof. Pro získání všech řešení nedeterministického predikátu má Mercury predikát s mnohem jasnějším významem:
:- pred solutions(pred(T), list(T)). :- pred solutions(pred(out) is nondet, out) is det.
Predikát solutions/2 přijímá v prvním parametru „generovátko“ a ve druhém parametru vrací seznam toho, co všechno generovátko vygenerovalo. Protože generovátko může výsledky vracet v náhodném pořadí, predikát solutions získané výsledky napřed setřídí a vrátí uspořádaný seznam. Tím je zaručen plný determinismus predikátu solutions/2, výsledný souhrn výsledků generovátka je jednoznačně určen právě jen tím generovátkem (a nikoli jeho různými implementacemi).
Upřímně řečeno, už jste viděli nějakou užitečnou funkci/predikát, který nic nepřijímá na vstupu a jen generuje výstup? Takových moc není, snad jen generátor náhodných čísel, ale kdo by chtěl získat uspořádaný seznam všech generovatelných čísel… Abychom ukázali použití predikátu solutions/2, musíme generovátko připravit důmyslněji a užitečněji.
Minule jsme se seznámili s abstraktním datovým typem map(K, V) reprezentujícím tabulku, kde jednomu klíči typu K odpovídá nejvýše jedna hodnota typu V, opačně však jedné hodnotě může odpovídat více klíčů. Není tedy překvapením, že inverzní vyhledávání je nedeterministické:
:- pred map__inverse_search(map(K, V)::in, V::in, K::out) is det.
:- pred vsechny_klice_ktere_maji_danou_hodnotu(map(K, V)::in, V::in,
list(K)::out) is det.
vsechny_klice_ktere_maji_danou_hodnotu(Map, Hodnota, NalezeneKlice) :-
solutions(map__inverse_search(Map, Hodnota), NalezeneKlice). Příklad výše ilustruje nejen použití predikátu solutions/2, ale též tzv. curryování, currying (podle pana Howarda Curryho, autora lambda kalkulu). Jak víte, v prvním parametru jsme predikátu solutions měli předat nedeterministický predikát s jediným a současně výstupním parametrem. My jsme v tomto parametru napsali map__inverse_search(Map, Hodnota). Víme, že inverse_search/3 z modulu map má tři parametry, když tedy první dva vyplníme proměnnými Map a Hodnota, zbude nám predikátmap__inverse_search(Map, Hodnota)/1 o jediném výstupním parametru. A to je právě to, co potřebuje predikát solutions. Curryování je „automatické vyrábění funkcí či predikátů tím, že několik prvních parametrů vyplníte“.
Vyrábění funkcí na místě, lambda výrazy, bezejmenné funkce
Už jsme se naučili pracovat s predikáty, kterým jako parametr předáváme funkci. A nebylo pro nás obtížné předat funkci, když už taková byla někde implementována a měla jméno. Pomocí curryování jsme se naučili použít pojmenovanou funkci a vyrobit z ní jinou tím, že jsme část parametrů fixovali (vyplnili). Často však potřebujete použít funkci „jen mírně upravenou“ (třeba prohozením pořadí parametrů), nebo „naprosto specifickou“ a není vhodné si pro takové funkce či predikáty vymýšlet jména.
K tomu účelu slouží lambda výrazy, lambda slouží jako označení „tady není žádné jméno funkce“ a pochází tradičně z LISPu. V Mercury se místo klíčového slova lambda užívá klíčové slovo pred, pokud vyrábíme bezejmenný predikát, nebo func, pokud vyrábíme bezejmennou funkci.
Vraťme se k příkladu sčítání seznamu pomocí predikátu list__foldl. Potřebovali jsme predikát na sečtení dvou čísel a zbytečně jsme ho explicitně pojmenovávali plus/2, když by nám dobře posloužila běžná funkce (+), kdyby jen byla predikátem.
Následující příklad potřebný predikát z funkce (+) vyrobí a uloží ho do lokální proměnné Plus:
test :-
Plus = (pred(X::in, Y::in, S::out) is det :- S = X+Y),
list__foldl(Plus, [1,2,3], 0, Soucet). Proměnná Plus byla jaksi nadbytečná, mohli jsme také rovnou predikát vyrobit na místě prvního parametru list__foldl/2:
test :-
list__foldl((pred(X::in, Y::in, S::out) is det :- S = X+Y),
[1,2,3], 0, Soucet). Shrnutí a co příště
Dnes jsme si udělali pořádek v předávání funkcí parametrem a vysvětlili si základy funkcionálního programování. Mercury proti jiným vyšším programovacím jazykům, kde je také možné předat pointr na funkci jako parametr, dokáže díky přesnému typovému systému prověřit, že předávaná funkce bude mít správný počet parametrů správného typu, takže volání určitě nehavaruje.
V příštím dílu uvedu na začátku ještě jeden či dva příklady programování vyššího řádu. Pak se ponoříme do typových tříd. (Pokud v diskusi vyjádříte zájem o ještě více ilustrací užití a užitečnosti programování vyššího řádu, odložím typové třídy o týden a příště budou jen příklady.)
ČLÁNKY DO MAILU