Obsah
1. Programovací technika nazvaná tacit programming
3. Tacit programming a reálné programovací jazyky
4. Programovací jazyky založené na zásobníku operandů a RPN
5. Operace nad daty uloženými na zásobníku operandů
7. Definice nových funkcí v jazyku Joy, volání funkcí
8. Rekurzivní kombinátory v jazyce Joy
9. Lineární rekurze zapsaná formou tacit programmingu
10. Primární rekurze zapsaná formou tacit programmingu
12. Známé algoritmy přepsané do formy tacit programmingu
13. Tacit programming v programovacím jazyku J
15. Výpočet průměru výrazem +/ % #
1. Programovací technika nazvaná tacit programming
V dnešním článku se seznámíme se zajímavou programovací technikou, která je nazývána point-free style, popř. v některých programovacích jazycích tacit programming. Přesný a přitom dostatečně jednoznačný český ekvivalent tohoto označení mě nenapadá, proto raději zůstanu u termínu anglického, který se ostatně snadněji vyhledává. Co se ovšem pod názvy tacit programming nebo point-free style skrývá? Jedná se o styl zápisu bloků programů (typicky jednotlivých výrazů, ale i uživatelských funkcí, popř. sekvencí funkcí, někdy o zápis dekorátorů), ve kterých se nachází volání jiných funkcí, ovšem bez explicitního udání jmen jejich argumentů (parametrů). A nejenom to – většinou není naznačen ani počet argumentů. Proč by se však tacit programming měl používat, resp. jaká je jeho přednost? Základní idea spočívá v tom, že se seskupením funkcí,, popř. operátorů vytvoří abstraktnější funkce nebo operátor, takže je možné v programovacím jazyce vybaveném relativně základními operacemi vytvářet vyšší úrovně abstrakce podle potřeb programátora, a to za použití snadno pochopitelných a testovatelných prostředků a idiomů.
S tacit programmingem se můžeme setkat v mnoha navzájem odlišných prostředích a v různých programovacích jazycích. Asi nejznámějším příkladem jsou dobře známé kolony v shellu, dále technika vytváření nových slov v jazycích založených na RPN (což jsou jazyky jako Forth, Joy, Factor, PostScript, …), technika operátorů použitá v programovacích jazycích APL a J (zde se pravděpodobně poprvé objevuje označení train) a zapomenout nesmíme ani na jazyk Haskell, popř. na Clojure (s threading makry a takzvanými transducery).
2. Kolony (roury) v shellu
Lze předpokládat, že naprostá většina čtenářů Roota se s programovací technikou, kterou budeme v tomto článku označovat termínem tacit programming již setkala, a to přímo v shellu. Konkrétně se jedná o použití klasických kolon, protože každý příkaz uvnitř kolony čte data z předchozího příkazu, transformuje či nějakým způsobem agreguje tato data a posílá výsledky příkazu dalšímu (a pro propojení dvou zpracovávajících entit v koloně se používá roura). Výjimkou je první popř. poslední příkaz, který je ke koloně připojen jen zleva či zprava. Na následujícím demonstračním příkladu je ukázána velmi jednoduchá kolona, přičemž ta část, kterou bychom mohli označit termínem tacit programming nebo point-free style, je zvýrazněna tučným písmem:
cat foobar | tr ',' '\n' | sort | uniq | rev | head -n 10
Koncept kolon (a tím pádem i rour) je již poměrně starý, neboť byl popsán již na začátku sedmdesátých let minulého století Douglasem McIlroyem a implementován byl Kenem Thompsonem v roce 1973. I přes toto stáří se dodnes jedná o velmi mocný koncept, který je používán dodnes, a to jak v klasické verzi (tedy s daty reprezentovanými jako sekvence textových řádků), tak i například ve formě Relational pipes. Díky jednoduše pochopitelnému a přitom efektivnímu konceptu se z rour stal návrhový vzor „roura“ a „filtr“.
3. Tacit programming a reálné programovací jazyky
Prozatím jsme si ukázali jeden sice velmi úspěšný, ale možná poněkud specifický příklad tacit programmingu. Ovšem s tímto stylem programování jsme se již mohli ve stručnosti seznámit ve starších miniseriálech o programovacích jazycích Forth, Joy a Factor (viz dvacátou kapitolu s příslušnými odkazy na tyto seriály). V těchto jazycích se využívalo toho, že všechny argumenty funkcí (operátorů) se nacházely na nejvyšších místech takzvaného zásobníku operandů, přičemž všechny operátory s těmito operandy pracovaly implicitně, opět bez nutnosti explicitně uvádět jejich jména (příklady si pochopitelně ukážeme v navazujících kapitolách). Ve všech třech zmíněných programovacích jazycích, tedy ve Forthu, jazyce Joy i ve Factoru, se striktně používá obrácená polská notace (RPN – Reverse Polish Notation), která tacit programming umožňuje používat efektivně pro libovolný počet argumentů funkcí popř. operandů nějakých operátorů (unární, binární, ternární atd. operátory).
Název „polská notace“ byl zvolen na počest polského matematika Jana Lukasiewicze, který v roce 1920 navrhl dvě možnosti psaní matematických výrazů bez nutnosti definice priorit operací a také bez použití závorek, kterým se při použití dnes nejpoužívanější infixové notace v mnoha případech nevyhneme. Notace, při které se operátory píšou až za operandy (tedy „obráceně“), se nazývá RPN či postfixová notace. A právě tato notace, která je interně založena na použití zásobníku operandů, je spojovacím článkem mezi výše zmíněnými programovacími jazyky.
Ve skutečnosti však není tacit programming v žádném případě vázán pouze na použití RPN. Typickým příkladem programovacího jazyka, v němž se tacit programming začal používat, je jazyk APL, s jehož padesáti pětiletou historií jsme se nedávno seznámili zde na Rootu. A APL je jazykem založeným na klasické infixové notaci. Myšlenka tacit programmingu ovšem nebyla v původním jazyku APL plně rozvinuta; ke zobecnění této techniky došlo v jazyce J, který je od APL odvozen. A konečně se můžeme s tacit programmingem setkat v Haskellu (dokonce v několika variantách) a taktéž v programovacím jazyku Clojure, který tento koncept nabízí taktéž v několika variantách. Ani to však není zdaleka vše, protože podobný koncept je realizován v jazyku ML (poněkud neprávem opomíjenému) a taktéž v Mirandě popř. v jazyku FP a FL.
S jednotlivými variantami, které jsou sice syntakticky velmi odlišné, ale realizují prakticky tutéž myšlenku, se seznámíme v navazujících kapitolách.
4. Programovací jazyky založené na zásobníku operandů a RPN
V úvodním textu jsme se zmínili o jazycích Forth, Joy, Factor či PostScript. I přesto, že se tyto jazyky od sebe v mnoha ohledech odlišují, mají jednu důležitou vlastnost společnou – výpočty, tj. aritmetické operace, logické operace a rozhodovací (řídicí) konstrukce jsou prováděny s hodnotami uloženými na zásobníku. Díky tomu bylo možné tyto jazyky interně značně zjednodušit, protože se o transformaci výrazů z dnes běžné infixové podoby do podoby postfixové (jinak známé pod taktéž již zmíněným názvem Převrácená Polská Notace/Reverse Polish Notation – RPN) musí postarat sám programátor. To ve skutečnosti není nijak složité, ostatně s prakticky stejným (pseudo)problémem se musí potýkat i ti uživatelé, kteří například používají kalkulačky Hewlett-Packard.
5. Operace nad daty uloženými na zásobníku operandů
Zde si jen v krátkosti připomeňme, že při použití zásobníku operandů přímo v programovacím jazyku jsou hodnoty na zásobník ukládány explicitně (zápis 42 tedy většinou znamená uložení této hodnoty na vrchol zásobníku operandů), aritmetické a logické operace používají implicitní adresování operandů (vždy se totiž jedná o hodnotu uloženou na vrcholu zásobníku či těsně pod ním) a kromě toho se většinou setkáme i s několika pomocnými operacemi určenými pro manipulaci s obsahem zásobníku. Tyto operace bývají nazývány dup (zduplikování hodnoty uložené na vrcholu zásobníku), drop (odstranění hodnoty z vrcholu zásobníku operandů), swap (prohození dvou nejvyšších prvků uložených na zásobníku) a rot (rotace tří nejvyšších prvků). Tyto názvy mají dnes již vlastně historický původ, protože byly použity v programovacím jazyku Forth; později se začaly používat například i v zásobníkových virtuálních strojích.
Nicméně se vraťme k tacit programmingu. Ve Forthu je možné napsat například následující funkci:
:foo + * ;
Tato funkce na zásobníku očekává alespoň tři číselné hodnoty, které ovšem uvnitř funkce nejsou nikde explicitně pojmenovány ani (explicitně) použity. Použití této funkce je stejně snadné jako její zápis, pochopitelně pokud si zvyknete na RPN:
3 2 1 foo . 9
Nejprve jsme na zásobník uložili tři hodnoty. Posléze se zavolala funkce foo, která tyto hodnoty nějakým způsobem zpracovala. Na nakonec byla hodnota umístěná na TOS vypsána další funkcí se jménem . (ano, toto je ve Forthu skutečně zcela legitimní jméno funkce).
Povšimněte si, že nyní těla funkce foo:
+ *
Tělo této funkce obsahuje pouze dvě tzv. slova „+“ a „*“. Každé z těchto slov očekává na zásobníku operandů dvojici hodnot, které jsou sečteny popř. vynásobeny a výsledek je uložen zpět na zásobník operandů. Nikde tedy není nutné psát, jak se operandy jmenují a už vůbec ne, jak se jmenuje výsledná hodnota. Navíc ani funkce foo tyto údaje neobsahuje.
6. Programovací jazyk Joy
Ve Forthu bylo použití zásobníku operandů (a nepřímo i tacit programmingu) omezeno na celá čísla popř. na reálné hodnoty. Ovšem samotnou myšlenku implicitního využívání parametrů/operandů je možné rozšířit na hodnoty libovolného datového typu. A právě tento koncept byl použit v programovacím jazyku Joy.
Programovací jazyk Joy byl prakticky přesně před dvaceti lety navržen Mangredem von Thunem pro účely výzkumu odlišného přístupu k funkcionálnímu programování, než nabízejí – v tomto oboru již klasické a zavedené – jazyky typu Lisp, Scheme a Haskell. Jedná se o minimalistický jazyk, který však v sobě skrývá velké možnosti, které nemusí být na první pohled zřejmé. Minimalismus je vidět i na velikosti samotného interpretru – spustitelný soubor s interpretrem a základní knihovnou funkcí má po přeložení céčkových zdrojových kódů velikost cca 110 kB a po aplikaci UPX či podobného nástroje se velikost dokonce snížila na pouhých 27 kB (zde je navíc nutné dodat, že v tomto spustitelném souboru je uložen také celý manuál o délce přes 2 kilobytů, jenž je dostupný pod příkazem manual). Zatímco ostatní funkcionální jazyky jsou založeny na aplikaci funkcí (v obecnějším pohledu tedy na teorii lambda kalkulu), je srdcem programování v Joyi kompozice funkcí spolu s takzvanou citací programů.
způsob kompozice funkcí pomocí funkce vyššího řádu "map" a citace programu [1 2 3 4] [square] map tisk výsledku pomocí operátoru "tečky" (zobecnění převzaté z Forthu) . [1 4 9 16]
Druhým základem, na kterém je programovací jazyk Joy založený, je citace programů, což ve skutečnosti není nic jiného než způsob zápisu (ale i dynamické tvorby) programového kódu bez jeho spuštění. Znalci programovacích jazyků Lisp či Scheme jistě znají speciální formy, které využívají stejného principu – programový kód je možné považovat za seznam příkazů/funkcí/operátorů, tj. ve skutečnosti za data, která je možné ve vhodném okamžiku „spustit“, tj. předat je funkci typu eval. Prakticky shodným způsobem je citace programů vyřešena i v Joyovi, ostatně je to základ takových funkcí, které se v nefunkcionálních programovacích jazycích transformují do podoby příkazů while, if-then-else atd. Ve funkcionálních jazycích se bez těchto speciálních syntaktických prvků hravě obejdeme:
funkce ifte nahrazuje "plný" větvicí příkaz typu if-then-else [1000 >] [2 /] [3 *] ifte příklad použití (tečka zajistí výpis položky na zásobníku): 10 [1000 >] [2 /] [3 *] ifte . 30 2000 [1000 >] [2 /] [3 *] ifte . 1000
7. Definice nových funkcí v jazyku Joy, volání funkcí
Způsob vytváření nových funkcí je, alespoň po syntaktické stránce, zcela zjevně inspirován programovacím jazykem Forth. Pojďme se tedy bez většího teoretizování podívat na příklad vytvoření dvou nových funkcí pojmenovaných jednoduše square a cube. Z příkladu je patrné, že vytváření nových funkcí začíná slovem DEFINE, za nímž následuje vždy název funkce, dále znaky == oddělující název funkce od jejího těla a poté již vlastní tělo funkce. Jednotlivé definice jsou od sebe odděleny znakem středníku, což opět připomíná již zmíněný jazyk Forth, konec definic všech funkcí zařídí operátor tečky:
DEFINE
square == dup * ;
cube == dup dup * * .
Všimněte si (v tomto článku již podruhé) jedné zajímavosti, která dosti podstatným způsobem odlišuje „zásobníkové“ programovací jazyky od zbytku světa a co je současně řadí do škatulky tacit programmingu: v těle funkcí ani v jejich názvu se nikde nevyskytují názvy parametrů, protože se předpokládá, že ty budou uloženy na zásobníku. Není tedy nutné nějakým složitým způsobem nahrazovat formální parametry za parametry skutečné. Má to ještě jednu výhodu – tělo funkce je možné zkopírovat, přenést na příkazový řádek a funkci přímo spustit či jinak testovat bez nutnosti měnit byť jediný znak v těle funkce. Jinými slovy: aplikace funkce přímo v programu (tj. zápis těla funkce) i její definice jsou zcela stejné, čehož lze velmi dobře využít při ladění a testování:
definice nové funkce nazvané xx:
DEFINE
xx == [1000 >] [2 /] [3 *] ifte
.
použití této funkce:
20 xx .
60
1000 xx .
3000
1001 xx .
500
přímé použití těla funkce:
20 [1000 >] [2 /] [3 *] ifte .
60
1000 [1000 >] [2 /] [3 *] ifte .
3000
1001 [1000 >] [2 /] [3 *] ifte .
500
Ukázka citace (části) programu s jeho následným spuštěním příkazem i (interpret):
[1 2 + 3 * print] i . 9
8. Rekurzivní kombinátory v jazyce Joy
Jednou z nejzajímavějších vlastností programovacího jazyka Joy je způsob náhrady rekurzivních funkcí a programových smyček s využitím takzvaných rekurzivních kombinátorů. Joy samozřejmě, ostatně jako naprostá většina programovacích jazyků (snad s výjimkou starého Fortranu a Basicu), podporuje normální rekurzi, tj. volání té samé funkce z jejího těla. Lze také použít rekurzi nepřímou, což znamená, že se z nějaké funkce A volá funkce B a v jejím těle se opět volá funkce A.
Ještě před vysvětlením konkrétních kombinátorů si vysvětleme, o jaké jazykové konstrukce se jedná. Rekurzivní kombinátor je vlastně běžný operátor, který na zásobníku očekává buď jeden nebo několik citovaných programů, popř. další parametry, například počet opakování. Jak již víme z předchozího textu, je citovaný program na zásobníku uložen ve formě seznamu, tj. v hranatých závorkách. Podle typu rekurzivního kombinátoru je citovaný program/programy opakovaně spouštěn, přičemž je specifickým způsobem (popsaným v dalších odstavcích) měněn obsah zásobníku tak, aby se simulovalo skutečné provádění rekurze. Rekurzivní kombinátory nemají žádnou specifickou syntaxi, jedná se o běžné funkce/operátory zapisované nám již známou postfixovou notací, tj. samotný programovací jazyk nemusel být kvůli jejich aplikaci žádným způsobem měněn. I tato skutečnost vypovídá o kvalitním a promyšleném návrhu tohoto jazyka.
Pravděpodobně nejjednodušším typem kombinátoru je kombinátor nahrazující klasickou počítanou smyčku typu for (mám teď na mysli podobu smyčky známou například z Pascalu, Fortranu (původní smyčka typu do) nebo Basicu, nikoli céčkovskou variantu, která má daleko širší možnosti). Tento kombinátor, který dostal přiléhavý název times, pracuje následujícím způsobem: při spuštění operátoru se předpokládá, že jsou na zásobníku uloženy dvě hodnoty: na vrcholu zásobníku seznam, jenž představuje tělo smyčky v imperativních jazycích, tj. citovaný program a pod vrcholem zásobníku je očekávána číselná hodnota udávající, kolikrát se má citovaný program provést. Použití tohoto kombinátoru je velmi jednoduché (funkce putchars zajistí tisk řetězce bez uvozovek a speciální znak \n pochopitelně slouží k odřádkování):
10 ["hello\n" putchars] times . hello hello hello hello hello hello hello hello hello hello
V mnoha programovacích jazycích se také objevuje smyčka typu for-each. Nejedná se o smyčku počítanou, jak tomu bylo v předchozím případě, ale o smyčku prováděnou nad všemi prvky nějakého datového kontejneru, typicky pole, seznamu nebo asociativního pole (počet prvků uložených v kontejnerech není v době překladu obecně známý). I za tento typ programové smyčky existuje v jazyce Joy náhrada ve formě kombinátoru nazvaného map. Použití tohoto kombinátoru je snadné – citovaný program předávaný na vrcholu zásobníku je aplikován na všechny položky seznamu či řetězce uloženého na druhém místě zásobníku. Výsledkem je nový seznam nebo řetězec:
[1 2 3 4] [dup *] map . [1 4 9 16]
Podobným způsobem pracuje i kombinátor nazvaný filter, který ovšem do nově vytvářeného seznamu či řetězce vkládá ty položky, které splňují zadané kritérium, tj. položky jsou skutečně filtrovány na základě neustále vyhodnocované podmínky:
ze seznamu získáme pouze sudá čísla (dělitelná dvěma) [0 1 2 3 4 5 6 7 8 9 10] [2 rem 0 =] filter . [0 2 4 6 8 10] opak předchozího příkladu, získání lichých čísel z předaného seznamu [0 1 2 3 4 5 6 7 8 9 10] [2 rem 0 !=] filter . [1 3 5 7 9] z řetězce se vyberou všechny znaky, jejichž pořadí v ASCII leží pod znakem 'a' (v tomto případě se odstraní malá písmena) "Hello World" ['a <] filter . "H W" z řetězce se vyberou všechny znaky, jejichž pořadí v ASCII leží nad znakem 'Z' (v tomto případě se odstraní velká písmena a mezery) "Hello World" ['Z >] filter . "elloorld" filtrace mezer (všimněte si způsobu zápisu mezery pomocí apostrofu) "Hello World" [' !=] filter . "HelloWorld" filtrace všech znaků kromě mezer "Hello World" [' =] filter . " "
Nepočítaná programová smyčka typu while známá z mnoha imperativních jazyků, je v programovacím jazyce Joy nahrazena (poněkud překvapivě, že…) kombinátorem nazvaným právě while. Před voláním tohoto kombinátoru musí být na zásobník uloženy dva citované programy. První program představuje podmínku, která je vyhodnocena před každým opakováním smyčky, druhý program představuje vlastní tělo smyčky, které je opakovaně voláno v závislosti na vyhodnocení podmínky. Učebnicovým příkladem použití tohoto kombinátoru je tvorba počítaného cyklu, přičemž nesmíme zapomenout na zásobníku vytvořit číselnou hodnotu, která se bude při opakování smyčky zvětšovat nebo naopak zmenšovat (funkce put provádí tisk čísla uloženého na vrcholu zásobníku):
podmínka tělo funkce volání kombinátoru 10 [0 <] [dup put 1 -] while . 10 9 8 7 6 5 4 3 2 1 0 jednodušší způsob využívající operátoru pred (poslední vytištěná hodnota je výsledkem operátoru tečka) 10 [0 >] [dup put pred] while . 10 9 8 7 6 5 4 3 2 1 0 zápis opačné podmínky a změna počáteční hodnoty (poslední vytištěná hodnota je opět výsledkem operátoru tečka, nikoli běhu smyčky) 0 [10 <] [dup put succ] while . 0 1 2 3 4 5 6 7 8 9 10 odstranění poslední hodnoty, která zůstává na zásobníku 0 [10 <] [dup put succ] while pop . 0 1 2 3 4 5 6 7 8 9 tisk sudých čísel 0 [10 <] [dup put succ succ] while . 0 2 4 6 8 10 tisk násobků tří 0 [10 <] [dup put 3 +] while . 0 3 6 9 12 o tom, že poslední číselná hodnota již není tělem smyčky zpracovávána, se můžeme jednoduše přesvědčit 0 [10 <] ["->" putchars dup put succ "\n" putchars] while . ->0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9 10
9. Lineární rekurze zapsaná formou tacit programmingu
Velmi často se při programování setkáváme s případy algoritmů, které se dají efektivně řešit pomocí takzvané lineární rekurze. Jedná se vlastně o takový případ rekurze, kdy funkce volá sebe samu ve svém těle pouze jednou. Nejprve si řekněme, co si pod pojmem lineární rekurze vůbec máme představit a v dalších odstavcích si ukážeme rekurzivní kombinátor, který slouží k zápisu lineárně rekurzivních algoritmů.
Nějaká naprogramovaná funkce f je nazývána lineárně rekurzivní v případě, že aktivace této funkce (tj. její zavolání) vyvolá nejvýše jednu novou aktivaci té samé funkce f. Typickým příkladem lineárně rekurzivní funkce je funkce faktoriál, v matematice označovaná postfixovým operátorem ! (vykřičník). Příkladem funkce, která není lineárně rekurzivní, je funkce pro výpočet Fibonacciho čísel – v těle této funkce (nazvěme ji například pro jednoduchost Fib) jsou vyvolány dvě aktivace té samé funkce Fib. Vraťme se však ke zmíněné typické lineárně rekurzivní funkci faktoriál, kterou lze matematicky definovat následujícím způsobem:
Fact(x)=1 pro x=0
Fact(x)=x×Fact(x-1) pro x>0
Z praktického hlediska je zajímavý především způsob výpočtu lineárně rekurzivní funkce, tj. vyjádření její hodnoty pro zadaný parametr. Vyhodnocování je možné obecně rozdělit do dvou po sobě následujících částí:
Fáze navíjení (winding phase): v této fázi jsou postupně volány, tj. aktivovány takzvané aktivace rekurzivní funkce, obecně s různými hodnotami parametrů.
Fáze odvíjení (unwinding phase): tato fáze nastane po splnění nějaké ukončující podmínky rekurze. Řízení, tj. bod, ve kterém se běžící proces nachází, se postupně vrací jednotlivým vytvořeným aktivacím.
V klasických imperativních i funkcionálních jazycích se lineárně rekurzivní funkce skutečně zapisují pomocí rekurze, tj. v těle funkce je volána (aktivována) ta samá funkce. Kromě toho je nutné zajistit, aby rekurze byla konečná, což je provedeno pomocí nějaké podmínky, jež v podstatě tvoří hranici mezi fází navíjení a fází odvíjení. Ukažme si, jakým způsobem by byla zapsána lineárně rekurzivní funkce pro výpočet faktoriálu v běžném programovacím jazyku (podobným způsobem, i když trošku jednodušším, by se výpočet provedl i ve funkcionálních jazycích, například Lispu nebo Scheme):
unsigned int fact(unsigned int n)
{
if (n==0) // podmínka pro ukončení rekurze
return 1; // => přechod mezi fází navíjení a odvíjení
else
n*fact(n-1); // rekurzivní volání funkce fact()
}
Programovací jazyk Joy se od většiny jiných funkcionálních jazyků odlišuje tím, že se lineárně rekurzivní funkce nemusí zapisovat pomocí rekurze (i to je však samozřejmě možné); místo toho nabízí speciální rekurzivní kombinátor představovaný slovem linrec. Tento kombinátor při svém zavolání požaduje, aby byly na zásobníku uloženy následující čtyři fragmenty citovaných programů:
- P – tento citovaný program, který je nazývaný if-part, je spuštěn před každým rekurzivním zanořením (nebo jeho obdobě, pokud je rekurze nahrazena jiným výpočtem). Podle výsledku vyhodnocení programu je buď spuštěn citovaný program T (P se vyhodnotí na hodnotu true), nebo je spuštěn program R1, je provedena rekurze a následně je spuštěn program R2 (spuštění tohoto programu může být časově velmi vzdálené od spuštění programu R1, v závislosti na počtu zanoření do rekurzivní funkce).
- T – tento citovaný program je nazývaný then-part podle podobnosti s funkcí podobného programu u operátoru ifte. Slouží k „úklidu“ po rekurzivním zanořování v případě, že je splněna podmínka zapsaná ve výše uvedeném programu P.
- R1 – citovaný blok programu nazývaný else-part-1 je vykonán v případě, že není splněna podmínka vyhodnocovaná citovaným programem P, ještě před vlastním provedením rekurze.
- R2 – citovaný blok programu nazývaný else-part-2 je vykonán po provedení rekurzivního zanoření do funkce.
Lineární rekurzi si můžeme ukázat na oblíbeném příkladu výpočtu faktoriálu, který lze zapsat buď klasicky rekurzivně:
DEFINE factorial == [0 =] [pop 1] [dup 1 - factorial *] ifte .
Nebo s využitím rekurzivního kombinátoru:
DEFINE factorial2 == [dup 0 =] [1 +] [dup 1 -] [*] linrec .
Popř. po náhradě některých aritmetických výrazů za funkce vykonávající stejnou činnost:
DEFINE factorial3 == [null] [succ] [dup pred] [*] linrec .
A můžeme si vše otestovat:
[1 2 3 4 5 6] [factorial3] map . [1 2 6 24 120 720]
nebo lze číselnou řadu vytvořit ještě lépe a radostněji:
0 [10 <] [dup factorial3 put succ] while pop . 1 1 2 6 24 120 720 5040 40320 362880
10. Primární rekurze zapsaná formou tacit programmingu
Programovací jazyk Joy podporuje kromě kombinátoru umožňujícího provádění lineární rekurze i kombinátor, který slouží pro zápis takzvané primitivní rekurze. V podstatě se jedná o zredukovanou verzi kombinátoru linrec, ovšem s tím rozdílem, že citovaný blok nazvaný if-part a else-part-1 je automaticky doplněn o kód zajišťující automatické zjištění, kdy má být rekurze ukončena. Vzhledem k tomu, že je blok else-part-1 doplněn automaticky, nelze nic provádět ve chvíli rekurzivního zanořování/navíjení (tím se například zamezí vzniku nekonečné rekurze), ale průběh vynořování/odvíjení z rekurze je již řízen blokem else-part-2, který je přítomen.
Následují velmi jednoduché příklady použití primitivní rekurze:
nejprve se zásobník naplní sekvencí 5 4 3 2 1 a poté je tato sekvence v opačném pořadí vypsána pomocí funkce put 5 [] [put] primrec . 1 2 3 4 5 fáze navíjení je stejná jako v předchozím případě ovšem ve fázi odvíjení je proveden výpočet (0-hodnota) a teprve výsledek tohoto výpočtu je vypsán 5 [] [0 swap - put] primrec . -1 -2 -3 -4 -5 obdobný případ, akorát se ve fázi odvíjení každá hodnota na zásobníku vynásobí dvěma 5 [] [2 * put] primrec . 2 4 6 8 10 opět se jedná o obdobný příklad s tím rozdílem, že se vypočítá druhá mocnina hodnot uložených na zásobníku 5 [] [dup * put] primrec . 1 4 9 16 25 můžeme ovlivnit také počáteční podmínku 5 ['A] [put] primrec . 'A 1 2 3 4 5
11. Binární rekurze
V praxi se také někdy setkáme s algoritmem, který vede na tvorbu funkce, jež není lineárně rekurzivní, tj. v jejím těle se ta samá funkce volá minimálně dvakrát. Jednou z takových funkcí je i známá rekurzivně zadaná matematická funkce sloužící k výpočtu jedné hodnoty ležící na Fibonacciho řadě. Pro každé číslo Fibonacciho řady platí vztah:
xn=xn-1+xn-2
Přičemž je definitoricky nastaveno x1=x2=1
Při použití rekurzivního kombinátoru binrec je výpočet n-té hodnoty Fibonacciho řady velmi jednoduchý, i když pomalý, protože se nepamatují předchozí vypočtené hodnoty. První blok citovaného programu slouží pro test, zda je hodnota uložená na zásobníku rovna nule nebo jedné (docela příjemná funkce ne?). Pokud je podmínka splněna, je spuštěn druhý blok, který neprovádí žádnou činnost a tudíž na zásobníku ponechá původní hodnotu. Třetí blok programu je zavolán před provedením rekurze, přičemž by se zde typicky měl zvýšit počet položek uložených na zásobníku, protože pro dvě nejvyšší položky je provedena rekurze. Poslední blok programu je proveden ve fázi odvíjení a slouží ke zpětnému zkombinování dvou položek umístěných na vrcholu zásobníku. Výsledkem je následující program:
[small] [] [pred dup pred] [+] binrec
výpočet prvních deseti hodnot Fibonacciho řady 1 [12 <] [dup [small] [] [pred dup pred] [+] binrec put succ] while pop. 1 1 2 3 5 8 13 21 34 55 89
12. Známé algoritmy přepsané do formy tacit programmingu
V této kapitole si ukážeme, jakým způsobem je možné použít výše popsané rekurzivní kombinátory k úpravě původně rekurzivních algoritmů na jejich nerekurzivní variantu, tj. na variantu, ve které se explicitně nevyskytuje přímá či nepřímá rekurze. Nerekurzivní úpravu je samozřejmě možné použít v téměř jakémkoli programovacím jazyce, ovšem většinou za cenu explicitního vytvoření zásobníku nebo podobné netriviální úpravy (v některých případech pomůže tail rekurze, ovšem pouze jako optimalizace primitivní a lineární rekurze). V programovacím jazyce Joy je vytvoření nerekurzivních algoritmů s využitím rekurzivních kombinátorů poměrně snadné.
nejjednodušší forma výpočtu faktoriálu pomocí primitivní rekurze [1] [*] primrec . ukázka zanořování bloků kódu při výpočtu faktoriálu [0 1 2 3 4 5 6] [[1] [*] primrec] map . [1 1 2 6 24 120 720] vytvoření seznamu obsahujícího sekvenci hodnot 10 [[]] [cons] primrec . [10 9 8 7 6 5 4 3 2 1] vytvoření rekurzivně vkládaných podseznamů 6 [[]] [[] cons cons] primrec . [6 [5 [4 [3 [2 [1 []]]]]]] algoritmus QuickSort [small] [] [uncons [>] split] [[swap] dip cons concat] binrec
13. Tacit programming v programovacím jazyku J
Podobným způsobem je možné vytvářet funkce i v programovacím jazyku J. Typickým příkladem je funkce pro výpočet průměru číselných hodnot uložených v nějakém vektoru. Průměr se vypočítá snadno: nejprve zjistíme součet (sumu) všech prvků (funkce + zkombinovaná s operátorem /) a následně tento součet vydělíme jejich počtem (funkce # zjistí délku vektoru). Při těchto výpočtech není nutné nikde explicitně pojmenovávat parametry – ty se použijí až při aplikaci (použití) vytvořené kombinace funkcí v další části programu:
NB. mean=suma(a1..an)/n mean =: +/ % #
Aby ovšem bylo možné tento program plně pochopit, musíme si říci, jak pracuje operátor +/ a primitivní funkce % a #.
Aritmetické a logické výrazy, které tvoří nejdůležitější součást všech programů zapisovaných v jazyku J, se vyhodnocují stejným způsobem, jako v již zmíněném programovacím jazyku APL, tj. zprava doleva bez toho, aby některé funkce měly vyšší prioritu než funkce jiné. Funkce se zapisují stejným způsobem jako v jiných jazycích prefixové a infixové operátory, tj. buď mezi oba argumenty (operandy) při volání dyadických funkcí nebo před jediný argument v případě, že se volá funkce monadická. Pokud je zapotřebí změnit pořadí volání funkcí, lze k tomuto účelu použít obligátní kulaté závorky. V jazyku J je k dispozici pět základních aritmetických funkcí, které jsou vypsány v tabulce pod odstavcem (povšimněte si především odlišného způsobu zápisu funkce podílu dvou hodnot). Způsob použití těchto funkcí i způsob úpravy priority (pořadí volání) je patrný z demonstračních příkladů uvedených pod tabulkou.
| Znak funkce | Monadická funkce | Dyadická funkce |
|---|---|---|
| + | negace imaginární složky komplexního čísla | součet (skalárů, vektorů, matic…) |
| – | negace | rozdíl |
| * | vrací znaménko | součin |
| % | převrácená hodnota | podíl |
| | | absolutní hodnota | zbytek |
| ^ | umocnění xy | |
| *: | druhá mocnina x2 | |
| %: | druhá odmocnina x1/2 | |
| ! | faktoriál |
Programovací jazyk J je, podobně jako jeho ideový předchůdce APL, určen především pro tvorbu aplikací, v nichž se zpracovávají data uložená ve vektorech, maticích či polích s větším počtem dimenzí (může se jednat například o hierarchické mřížky atd.). Z tohoto důvodu je jazyk J vybaven jak jednoduchou syntaxí určenou pro zápis vektorů a matic, tak i sadou primitivních (základních) funkcí, pomocí nichž lze nad vektory i maticemi provádět různé operace:
| Symbol funkce | Forma funkce | Popis funkce (význam) |
|---|---|---|
| + – * % | dyadická | základní aritmetické operace prováděné nad dvojicí vektorů na korespondujících prvcích (též prováděné nad skalárem a vektorem) |
| < <: > >: = ~: | dyadická | porovnání korespondujících prvků dvou vektorů |
| # | monadická | vrací délku vektoru |
| # | dyadická | kopie prvků vektoru představovaného druhým parametrem |
| { | dyadická | výběr prvku či více prvků z vektoru na základě indexů vybíraných prvků |
| {. | dyadická | výběr prvních n prvků z vektoru |
| }. | dyadická | výběr posledních délka-n prvků vektoru (= odstranění prvních n prvků) |
| , | dyadická | spojení dvou vektorů či vektoru se skalárem |
| /: | monadická | setřídění prvků vektoru sestupně (funkce vrací indexy prvků, ne jejich hodnoty) |
| \: | monadická | setřídění prvků vektoru vzestupně (funkce též vrací indexy prvků, ne jejich hodnoty) |
| i. | monadická | vytváří seznam (vektor) obsahující řadu čísel začínající nulou, popř. prázdný vektor |
| i: | monadická | vytváří seznam (vektor) obsahující čísla on -n do n, kde n je parametr funkce |
| p. | monadická | výpočet kořenů polynomu reprezentovaného vektorem obsahujícím koeficienty ai |
Jedním z nejdůležitějších operátorů jazyka J je operátor /, který jsme si již v jednodušší podobě představili při popisu jazyka APL. Tento operátor, který se zapisuje za identifikátor primitivní či uživatelské funkce, postupně danou funkci aplikuje na první dva prvky argumentu, dále ji aplikuje na průběžný výsledek a třetí prvek atd., do doby, než jsou všechny prvky argumentu zpracovány (jinými slovy – daná dyadická funkce je jakoby zapsána mezi všechny prvky předané datové struktury, počet operací je roven n-1 v případě, že předaný vektor má počet prvků n):
NB. Součet všech čísel v řadě od 1 do 10. + / 1 2 3 4 5 6 7 8 9 10 55
14. Jazyk J a „vláčky“
Známe tedy význam posledního dvojznaku +/. Zbývá nám zjistit, jak je možné, že kombinace operátoru +/ a dvojice funkcí % a # můžeme spojit do výpočtu průměru vektoru +/ % #. V tomto zápisu nám totiž zcela chybí uvedení parametrů obou funkcí a operátoru.
Podívejme se nejdříve na dvojici funkcí sum a square. Ty lze zapsat následujícím způsobem:
sum =: +/ square =: *:
V jazyce J platí, že následující výraz pro libovolné funkce f, g a pro parametr y:
(f @: g) y
je ve skutečnosti vyhodnocen jako:
f (g y)
To tedy znamená, že pokud napíšeme:
sumsq =: sum @: square
Můžeme vypočítat součet (sumu) druhých mocnin hodnot prvků 3 a 4:
sumsq 3 4 25
Dále v programovacím jazyce J platí pravidla i pro další typy vláčků:
(f g) y se vyhodnotí jako y f (g y) (f g h) y se vyhodnotí jako (f y) g (h y)
15. Výpočet průměru výrazem +/ % #
Nyní se konečně vraťme k funkci pro výpočet průměru ze sekvence hodnot:
mean =: +/ % #
Nejprve si pro jednoduchost výpočet rozdělíme na části – sumu a výpočet průměru:
sum =: +/ mean =: sum % #
Pro druhý ze zápisů, tedy pro sum % # nahradíme jednotlivé konkrétní symboly za obecnější symboly f, g a h. Doplníme symbol y představující vstupní data (zapisovaný zcela doprava):
| Obecný symbol | Symbol z výrazu |
|---|---|
| f | sum |
| g | % |
| h | # |
| y | y |
Dále již z předchozí kapitoly známe následující pravidlo pro přepis „vláčku“:
(f g h) y se vyhodnotí jako (f y) g (h y)
Což při zpětném dosazení za symboly f, g, h znamená:
| Zápis | Ekvivalentní se zápisem |
|---|---|
| (f g h) y | (f y) g (h y) |
| (sum % #) y | (sum y) % (# y) |
A právě (sum y) % (# y) je našim cílem – nyní se vstupní hodnoty použijí dvakrát: nejdříve pro výpočet sumy, podruhé pro získání počtu prvků vstupního vektoru. Následně se tyto dvě hodnoty podělí a výsledkem je logicky průměr.
Nyní se podívejme na konkrétní vstupní hodnoty i na to, jak bude výpočet probíhat:
y =: 1 2 3 4
Postupné počítání mezivýsledků:
| Výraz | Vyhodnoceno na |
|---|---|
| y | 1 2 3 4 |
| sum y | 10 |
| # y | 4 |
| (sum y) % (# y) | 2.5 |
| mean y | 2.5 |
Pokud namísto sum použijeme původní operátor +/, bude výsledek totožný:
| Obecný symbol | Symbol z výrazu |
|---|---|
| f | +/ |
| g | % |
| h | # |
| y | y |
Rozpis „vláčku“:
| Zápis | Ekvivalentní se zápisem |
|---|---|
| (f g h) y | (f y) g (h y) |
| (+/ % #) y | (+/ y) % (# y) |
Postupné počítání mezivýsledků:
| Výraz | Vyhodnoceno na |
|---|---|
| y | 1 2 3 4 |
| +/ y | 10 |
| # y | 4 |
| (+/ y) % (# y) | 2.5 |
| mean y | 2.5 |
16. Obsah druhé části článku
Jak jsme se již řekli v úvodních kapitolách, není tacit programming ani náhodou výsadou pouze některých nemainstreamových programovacích jazyků.Ve skutečnosti byl tento (nutno dodat, že někdy nečitelný) styl převzat i do mainstreamu, o čemž se přesvědčíme příště.
17. Odkazy na Internetu
- Tacit programming (APL Wiki)
https://aplwiki.com/wiki/Tacit_programming - Function trains
https://mlochbaum.github.io/BQN/doc/train.html - Tacit programming (Wikipedia)
https://en.wikipedia.org/wiki/Tacit_programming - Beyond Functional Programming: Manipulate Functions with the J Language
https://www.adamtornhill.com/articles/jlang/beyondfunctional.html - Real World Uses of Tacit Programming: Part 1 of 2
https://medium.com/@jesterxl/real-world-uses-of-tacit-programming-part-1-of-2-f2a0c3f9e00c - Programovací jazyk Forth a zásobníkové procesory
http://www.root.cz/clanky/programovaci-jazyk-forth-a-zasobnikove-procesory/ - Seriál Programovací jazyk Forth
http://www.root.cz/serialy/programovaci-jazyk-forth/ - Programovací jazyk Factor
http://www.root.cz/clanky/programovaci-jazyk-factor/ - Grafický metaformát PostScript
http://www.root.cz/clanky/graficky-metaformat-postscript/ - Programovací jazyk Factor
https://www.root.cz/clanky/programovaci-jazyk-factor/ - Factor: revoluce v programování nebo propadák?
https://www.root.cz/clanky/factor-revoluce-v-programovani-nebo-propadak/ - Integrované vývojové prostředí Factoru
https://www.root.cz/clanky/integrovane-vyvojove-prostredi-factoru/ - Programujeme ve Factoru
https://www.root.cz/clanky/programujeme-ve-factoru/ - Joy: radost z programování
https://www.root.cz/clanky/joy-radost-z-programovani/ - Joy: programovací jazyk od protinožců
https://www.root.cz/clanky/joy-programovaci-jazyk-od-protinozcu/ - Jazyk Joy a rekurzivní kombinátory
https://www.root.cz/clanky/jazyk-joy-a-rekurzivni-kombinatory/ - Point-Free or Die: Tacit Programming in Haskell and Beyond
https://www.thestrangeloop.com/2016/point-free-or-die-tacit-programming-in-haskell-and-beyond.html - Threading macro (dokumentace k jazyku Clojure)
https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/-> - Understanding the Clojure → macro
http://blog.fogus.me/2009/09/04/understanding-the-clojure-macro/ - Transducers
https://clojure.org/reference/transducers - dc (computer program)
https://en.wikipedia.org/wiki/Dc_%28computer_program%29 - dc (na Esolang)
http://esolangs.org/wiki/Dc - Relational pipes
https://relational-pipes.globalcode.info/v0/ - Roura (Unix)
https://cs.wikipedia.org/wiki/Roura_(Unix) - Roura (software)
https://cs.wikipedia.org/wiki/Roura_(software) - APL Wiki
https://aplwiki.com/wiki/ - The Array Cast
https://www.arraycast.com/episodes/episode-03-what-is-an-array - EnthusiastiCon 2019 – An Introduction to APL
https://www.youtube.com/watch?v=UltnvW83_CQ - Dyalog
https://www.dyalog.com/ - Try APL!
https://tryapl.org/ - APL na replit
https://replit.com/languages/apl - Advent of Code 2020 in APL!
https://www.youtube.com/watch?v=0RQFW6P1Tt0 - Python vs APL (1 Problem)
https://www.youtube.com/watch?v=APdKFJkmBbM - APL Wins (vs C++, Java & Python)
https://www.youtube.com/watch?v=59vAjBS3yZM - A Tour de Force of APL in 16 Expressions by Roger Hui
https://www.youtube.com/watch?v=e0rywC7-i0U - Conway's Game Of Life in APL
https://www.youtube.com/watch?v=a9×AKttWgP4 - A List of companies that use Array Languages (J, K, APL, q)
https://github.com/interregna/arraylanguage-companies - APL – one of the greatest programming languages ever
http://www.vaxman.de/publications/apl_slides.pdf - „The J Programming Language“ by Tracy Harms (2013)
https://www.youtube.com/watch?v=RWYkx6-L04Q - Dyalog Modern Programming Language, Morten Kromberg, Talks at Google
https://www.youtube.com/watch?v=PlM9BXfu7UY - The J Language: Consistency, Adjacency, and Solution-Oriented Programming – Tracy Harms
https://www.youtube.com/watch?v=gLULrFY2-fI - Un-directed programming
https://www.sacrideo.us/un-structured-programming/ - Concatenative programming language
https://en.wikipedia.org/wiki/Concatenative_programming_language - Repositáře s jazykem Joy
https://github.com/joy-language - J language: Chapter 8: Composing Verbs
https://www.jsoftware.com/help/learning/08.htm - J language: Chapter 9: Trains of Verbs
https://www.jsoftware.com/help/learning/09.htm
