Hlavní navigace

Programovací technika nazvaná tacit programming

23. 11. 2021
Doba čtení: 29 minut

Sdílet

 Autor: Depositphotos
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.

Obsah

1. Programovací technika nazvaná tacit programming

2. Kolony (roury) v shellu

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ů

6. Programovací jazyk Joy

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

11. Binární rekurze

12. Známé algoritmy přepsané do formy tacit programmingu

13. Tacit programming v programovacím jazyku J

14. Jazyk J a „vláčky“

15. Výpočet průměru výrazem +/ % #

16. Obsah druhé části článku

17. Odkazy na Internetu

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ů.

Poznámka: poměrně často používám v článcích pojem „idiom“ pro ustálenou strukturu/notaci v daném obvyklou programovacím jazyce. Důsledné používání idiomů vede ke kódu, který je srozumitelný i pro další programátory. A nejenom to – v takovém kódu se obecně nachází menší množství logických chyb. Naopak nepoužití idiomu programátory zbytečně zmate.

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
Poznámka: povšimněte si, že se skutečně nikde uvnitř kolony neuvádí žádná jména proměnných ani souborů, s nimiž se má pracovat. U příkazu tr můžeme vidět ještě jednu techniku – díky použití parametrů jsme vlastně z původního obecného příkazu tr vytvořili nový (anonymní – tedy nepojmenovaný) příkaz, který by ovšem klidně mohl být pojmenován, například commas2endlines apod. Mimochodem – podobnou techniku nalezneme i v některých dále popsaných „plnohodnotných“ programovacích jazycích, kde se v tomto kontextu většinou hovoří o uzávěrech (closures) nebo transducerech.

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.

Poznámka: mimochodem – podle názoru některých vývojářů se všechny čtyři výše zmíněné programovací jazyky už nachází na hranici mezi „civilizovanými“ programovacími jazyky a jazyky esoterickými, i když autor článku je velkým fandou zásobníkových jazyků, takže tento názor nesdílí :-).

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.

Poznámka: vrchol zásobníku se označuje zkratkou TOS neboli Top Of Stack.

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.

Poznámka: a právě zápis :foo + * ; ukazuje typické znaky tacit programmingu. Na jednu stranu je tento zápis velmi úsporný a v mnoha případech i idiomatický. Na stranu druhou může být tento zápis těžko rozluštitelný, a to právě díky jeho úspornosti – všechny nepodstatné detaily byly vynechány, takže kód prakticky postrádá redundanci (která je například v hovorovém jazyce užitečná, neboť usnadňuje porozumění zprávě i při jejím „zašumění“ či nedokonalé znalosti jazyka).

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.

Poznámka: jazyky „Forthovského stylu“ se někdy označují termínem „concatenative languages“.

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
Poznámka: v tomto případě jsou jednotlivá slova, z nichž se program skládá, uložena do seznamu. Žádné další operace se s tímto seznamem neprovádí až do chvíle, kdy je zavoláno slovo i, které obsah seznamu „spustí“.

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
.
Poznámka: povšimněte si, že se v tomto zápisu nevyskytuje ani jediné jméno parametru, pomocné proměnné či rekurzivně volané funkce (to je uvedeno jen na levé straně definice).

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
Poznámka: ještě by bylo vhodné doplnit obdobu generátoru range z Pythonu nebo operátoru iota z jazyka APL.

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  
Poznámka: nyní již tedy známe funkci dyadické funkce % – jedná se o podí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
Poznámka: ve výpočtu byla použita funkce #, kterou již tedy taktéž známe – jde o zjištění délky vektoru.

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 =: *:
Poznámka: dvojznakem *: se označuje druhá mocnina.

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
Poznámka: tomuto řazení operátorů a funkcí se říká „vláček“ neboli train.

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)
Poznámka: povšimněte si, že v levém sloupci se hodnoty (parametry) y vyskytují pouze na jediném místě, a to konkrétně zcela vpravo. Při vyhodnocování jsou však „rozesety“ i dovnitř výrazů (pravý sloupec). A právě tato pravidla nám umožňují zápis funkce výpočtu průměru ve stylu tacit programmingu.

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“:

Root školení Elk

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
Poznámka: závorky jsou zbytečné – byly uváděny pouze pro zvýraznění, které operandy a jakým způsobem jsou vyhodnocovány.

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

  1. Tacit programming (APL Wiki)
    https://aplwiki.com/wiki/Ta­cit_programming
  2. Function trains
    https://mlochbaum.github.i­o/BQN/doc/train.html
  3. Tacit programming (Wikipedia)
    https://en.wikipedia.org/wi­ki/Tacit_programming
  4. Beyond Functional Programming: Manipulate Functions with the J Language
    https://www.adamtornhill.com/ar­ticles/jlang/beyondfuncti­onal.html
  5. 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
  6. Programovací jazyk Forth a zásobníkové procesory
    http://www.root.cz/clanky/programovaci-jazyk-forth-a-zasobnikove-procesory/
  7. Seriál Programovací jazyk Forth
    http://www.root.cz/serialy/pro­gramovaci-jazyk-forth/
  8. Programovací jazyk Factor
    http://www.root.cz/clanky/programovaci-jazyk-factor/
  9. Grafický metaformát PostScript
    http://www.root.cz/clanky/graficky-metaformat-postscript/
  10. Programovací jazyk Factor
    https://www.root.cz/clanky/pro­gramovaci-jazyk-factor/
  11. Factor: revoluce v programování nebo propadák?
    https://www.root.cz/clanky/factor-revoluce-v-programovani-nebo-propadak/
  12. Integrované vývojové prostředí Factoru
    https://www.root.cz/clanky/integrovane-vyvojove-prostredi-factoru/
  13. Programujeme ve Factoru
    https://www.root.cz/clanky/pro­gramujeme-ve-factoru/
  14. Joy: radost z programování
    https://www.root.cz/clanky/joy-radost-z-programovani/
  15. Joy: programovací jazyk od protinožců
    https://www.root.cz/clanky/joy-programovaci-jazyk-od-protinozcu/
  16. Jazyk Joy a rekurzivní kombinátory
    https://www.root.cz/clanky/jazyk-joy-a-rekurzivni-kombinatory/
  17. 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
  18. Threading macro (dokumentace k jazyku Clojure)
    https://clojure.github.io/clo­jure/clojure.core-api.html#clojure.core/->
  19. Understanding the Clojure → macro
    http://blog.fogus.me/2009/09/04/un­derstanding-the-clojure-macro/
  20. Transducers
    https://clojure.org/referen­ce/transducers
  21. dc (computer program)
    https://en.wikipedia.org/wi­ki/Dc_%28computer_program%29
  22. dc (na Esolang)
    http://esolangs.org/wiki/Dc
  23. Relational pipes
    https://relational-pipes.globalcode.info/v0/
  24. Roura (Unix)
    https://cs.wikipedia.org/wi­ki/Roura_(Unix)
  25. Roura (software)
    https://cs.wikipedia.org/wi­ki/Roura_(software)
  26. APL Wiki
    https://aplwiki.com/wiki/
  27. The Array Cast
    https://www.arraycast.com/e­pisodes/episode-03-what-is-an-array
  28. EnthusiastiCon 2019 – An Introduction to APL
    https://www.youtube.com/wat­ch?v=UltnvW83_CQ
  29. Dyalog
    https://www.dyalog.com/
  30. Try APL!
    https://tryapl.org/
  31. APL na replit
    https://replit.com/languages/apl
  32. Advent of Code 2020 in APL!
    https://www.youtube.com/wat­ch?v=0RQFW6P1Tt0
  33. Python vs APL (1 Problem)
    https://www.youtube.com/wat­ch?v=APdKFJkmBbM
  34. APL Wins (vs C++, Java & Python)
    https://www.youtube.com/wat­ch?v=59vAjBS3yZM
  35. A Tour de Force of APL in 16 Expressions by Roger Hui
    https://www.youtube.com/wat­ch?v=e0rywC7-i0U
  36. Conway's Game Of Life in APL
    https://www.youtube.com/wat­ch?v=a9×AKttWgP4
  37. A List of companies that use Array Languages (J, K, APL, q)
    https://github.com/interreg­na/arraylanguage-companies
  38. APL – one of the greatest programming languages ever
    http://www.vaxman.de/publi­cations/apl_slides.pdf
  39. „The J Programming Language“ by Tracy Harms (2013)
    https://www.youtube.com/watch?v=RWYkx6-L04Q
  40. Dyalog Modern Programming Language, Morten Kromberg, Talks at Google
    https://www.youtube.com/wat­ch?v=PlM9BXfu7UY
  41. The J Language: Consistency, Adjacency, and Solution-Oriented Programming – Tracy Harms
    https://www.youtube.com/wat­ch?v=gLULrFY2-fI
  42. Un-directed programming
    https://www.sacrideo.us/un-structured-programming/
  43. Concatenative programming language
    https://en.wikipedia.org/wi­ki/Concatenative_programmin­g_language
  44. Repositáře s jazykem Joy
    https://github.com/joy-language
  45. J language: Chapter 8: Composing Verbs
    https://www.jsoftware.com/hel­p/learning/08.htm
  46. J language: Chapter 9: Trains of Verbs
    https://www.jsoftware.com/hel­p/learning/09.htm

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.