Jazyk Joy a rekurzivní kombinátory

Obsah

1. Náhrada rekurze pomocí rekurzivních kombinátorů
2. Kombinátor nahrazující počítanou smyčku typu for
3. Kombinátor nahrazující nepočítanou smyčku typu foreach
4. Kombinátor nahrazující smyčku typu while
5. Lineární rekurze
6. Primitivní rekurze
7. Binární rekurze
8. Nerekurzivní verze známých algoritmů
9. Odkazy na Internetu

1. Náhrada rekurze pomocí rekurzivních kombinátorů

Jednou z nejzajímavějších vlastností programovacího jazyka Joy je způsob náhrady rekurzivních funkcí a programových smyček pomocí 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 opět funkce A.

Volání je samozřejmě možné provádět i přes větší počet funkcí, například formou A->B->C->A. V dalších kapitolách si způsob provádění rekurze vysvětlíme jak teoreticky, tak i na několika praktických příkladech. Uvidíme, že některé formy rekurze lze nahradit lineárním kódem poměrně snadno, u dalších je to již těžší a ve speciálních případech (matematici by spíše řekli v obecných případech) je to dokonce nemožné.

Mnoho funkcionálních programovacích jazyků, mezi jinými i Lisp (přesněji řečeno pouze některé implementace Lispu) a Scheme, obsahuje techniku zvanou tail recursion. Ta je bez zásahu programátora do jím vytvářeného programu použita pro náhradu rekurze za smyčku v době překladu či běhu programu. Pokud však programátor chce použít tail rekurzi, musí dodržet jistá pravidla zápisu funkce; především se to týká vlastního rekurzivního volání.

Jedná se vlastně o optimalizační techniku, která v mnoha případech vede jak ke snížení množství alokované operační paměti, tak i ke zrychlení běhu programu, protože skutečné provedení rekurze, tj. volání funkce, je implementačně i časově složitější, než použití programové smyčky. Tail rekurze je však většinou omezena především na lineární rekurzi popsanou ve čtvrté kapitole a samozřejmě je použitelná i pro rekurzi primitivní popsanou v kapitole páté. Pro vyšší formy rekurze už se tato optimalizační technika neuplatňuje.

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í části tohoto článku, 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 kapitolá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.

Aplikace gcalculator přepnutá do režimu RPN

2. Kombinátor nahrazující počítanou smyčku typu for

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 slouží k odřádkování):

10 ["hello\n" putchars] times .
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello 

3. Kombinátor nahrazující nepočítanou smyčku typu foreach

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 smyčky existuje v jazyce Joy náhrada ve formě kombinátoru 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 .
" " 

Do podobné kategorie patří i kombinátor step, pomocí kterého je možné zpracovávat seznamy, řetězce nebo množiny, ovšem s tím rozdílem, že se výsledek nevrací do stejné datové struktury (seznamu atd.), ale na nové místo v zásobníku. Jedno z možných použití tohoto kombinátoru je rozklad seznamu na sekvenci jeho prvků:

rozklad seznamu na sekvenci prvků
[1 2 3 4 5] [nop] step .....
5
4
3
2
1

ukázka rozdílu mezi kombinátory step a map
[1 2 3 4 5] [nop] map .....
[1 2 3 4 5]

na zpracovávané prvky lze samozřejmě aplikovat různé operace
[1 2 3 4 5] [succ] step .....
6
5
4
3
2

výsledek je opět odlišný od kombinátoru map
[1 2 3 4 5] [succ] map .....
[2 3 4 5 6]

složitější operace - vytvoření převráceného seznamu
(postupně se provádí operace '[] 1 swap cons')
[] [1 2 3 4 5] [swap cons] step .....
[5 4 3 2 1] 

RPN kalkulačka určená pro PDA
(nahoře vlevo je vidět prozatím prázdná část zásobníku)

4. Kombinátor nahrazující smyčku typu while

Nepočítaná smyčka typu while známá z mnoha imperativních jazyků, je v programovacím jazyce Joy nahrazena (poněkud překvapivě…) 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 

Podpora drag and drop v RPN kalkulačce určené pro PDA
(numerické klávesy v tomto případě slouží jako deset nezávislých pamětí!)

5. Lineární rekurze

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 čás­tí:

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 

RPN kalkulačky určené pro PDA jsou evidentně oblíbené – aplikace MathU Pro
(proč vůbec mají telefony klávesnici otočenou oproti kalkulačkám nebo počítačovým klávesnicím?)

6. Primitivní rekurze

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 

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

x_n=x_n-1+x_n-2

Přičemž je definitoricky nastaveno x₁=x₂=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 

8. Nerekurzivní verze známých algoritmů

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 

9. Odkazy na Internetu

• http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y.html
  – Joy Programming Language, stránka s rozcestníkem informací o programovacím jazyku Joy
• http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/j01tut.html
  – Tutorial on Joy
• http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/j06prg.html
  – Programming in Joy
• http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/synops.html
  – Synopsis of the language Joy
• http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/faq.html
  – Frequently Asked Questions about Joy, obsahuje i částečné porovnání s některými dalšími programovacími jazyky založenými na zásobníkovém kódu
• http://en.wiki­pedia.org/wiki/Fac­tor_(programmin­g_language)
  – Factor Programming Language, programovací jazyk značně inspirovaný Joyem
• http://www.fig-uk.org/
  – stránka sdružení FIG UK – The United Kingdom Forth Interest Group. Jedná se o jedno z prvních sdružení FIG, které se zaměřuje na vydávání časopisu ForthWrite (v minulosti 6 čísel za rok) a také údržbě a rozšiřování rozsáhlé knihovny zaměřené na Forth. Členové tohoto sdružení pochází zejména z Velké Británie, někteří členové jsou však i z USA, Ruska, Japonska apod.
• http://www.co­lorforth.com/
  – domácí stránka Chucka Moorea, vynálezce Forthu. Na této stránce jsou k dispozici některé technické detaily o zásobníkových procesorech a zejména popis systému ColorForth spolu s jeho zdrojovými texty (bootstrap code) napsanými v assembleru x86.
• http://zforth­.com/
  – takzvaný The Forth Programming Webring, počátek řetězce stránek věnovaných Forthu a příbuzným tématům. Zajímavé a možná i příznačné je, že tento server je vytvořen pomocí systému zHTTP, který je napsaný v dialektu programovacího jazyka Forth nazvaného zForth.
• http://www.hp­.com/calculator­s/articles/rpn­.html
  – stránka firmy HP, na které je velmi podrobně popsána obrácená Polská notace (RPN – Reverse Polish Notation), která je použitá jak u kalkulátorů této firmy, tak i při zápisu výrazů v programovacích jazycích Forth, PostScript i Joy.
• http://en.wiki­pedia.org/wiki/For­th_programmin­g_language
  – stránka Wikipedie o programovacím jazyku Forth.
• http://en.wiki­pedia.org/wiki/Chuc­k_Moore
  – stránka Wikipedie o Chucku Moorovi, vynálezci Forthu.
• http://en.wiki­pedia.org/wiki/Jo­y_(programmin­g_language)
  – Wikipedia EN: Joy (programming language)
• http://en.wiki­pedia.org/wiki/Pri­mitive_recursi­ve_function
  – Wikipedia EN: Primitive recursive function
• http://en.wiki­pedia.org/wiki/Mu-recursive_function
  – Wikipedia EN: µ-recursive function
• http://cs.wiki­pedia.org/wiki/Pri­mitivně_rekur­zivní_funkce
  – Wikipedia CS: Primitivně rekurzivní funkce
• http://cs.wiki­pedia.org/wiki/Čás­tečně_rekurziv­ní_funkce
  – Wikipedia CS: Částečně rekurzivní funkce
• http://home.e­arthlink.net/~mrob/p­ub/lang_srom.html
  – porovnání programovacích jazyků podle názoru programátorů.
• http://www.for­th.com/resources/e­volution/index­.html
  – The Evolution of Forth – velmi dobře zpracovaná historie Forthu.
• Wikipedia EN: Primitive recursive function:
  http://en.wiki­pedia.org/wiki/Pri­mitive_recursi­ve_function
• Wikipedia EN: µ-recursive function:
  http://en.wiki­pedia.org/wiki/Mu-recursive_function
• Wikipedia CS: Primitivně rekurzivní funkce:
  http://cs.wiki­pedia.org/wiki/Pri­mitivně_rekur­zivní_funkce
• Wikipedia CS: Částečně rekurzivní funkce:
  http://cs.wiki­pedia.org/wiki/Čás­tečně_rekurziv­ní_funkce
• Simulátor kultovní kalkulačky HP-35 vytvořený v JavaScriptu:
  http://www.mac-net.com/host/pa­ges/hp35/calc­.html