Joy: radost z programování

Obsah

1. Joy – radost z programování
2. Paradigma programovacího jazyka Joy
3. Joy v porovnání s Lispem (Scheme) a Forthem
4. Postfixová notace a RPN
5. Zásobníkové manipulátory
6. Definice nových funkcí
7. Odkazy na Internetu
8. Obsah druhé části článku

1. Joy – radost z programování

Programovací jazyk Joy byl před několika 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 či Scheme. 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 interpreteru – spustitelný soubor s interpreterem 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 nutné říci, ž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ů.

V mnoha ohledech je Joy čistě funkcionální jazyk, protože neobsahuje přiřazovací příkaz a dokonce ani běžné proměnné. V imperativních jazycích běžné konstrukce jako smyčky či podmínky jsou zde nahrazeny kombinátory a rekurzí, popř. takzvanými rekurzivními manipulátory, které samy o sobě představují snad nejzajímavější část tohoto netradičního jazyka, který na první pohled zaujme svojí neobvyklou syntaxí a sevřeným způsobem zápisu programů.

Ptáte se, jak je možné v takovém jazyce vůbec programovat? Po pochopení základů je to docela jednoduché a přitom zábavné, zvláště když si člověk uvědomí, na jak jednoduchých pravidlech může být programovací jazyk postaven. Základy programování si spolu s demonstračními příklady ukážeme v následujících kapitolách a druhé i třetí části tohoto článku.

2. Paradigma programovacího jazyka Joy

Z předchozí kapitoly již víme, že Joy spadá do kategorie funkcionálních programovacích jazyků, což je poměrně velká rodina jazyků, mezi jejíž členy patří především známý Lisp, od něj odvozené Scheme, dále pak jazyk ML nebo poměrně populární Haskell. Všechny čtyři zmíněné jazyky jsou ve svých základech založeny na lambda kalkulu. Ovšem Joy je v tomto ohledu odlišný, protože je postaven na kompozici funkcí a citaci programů. Nejprve si vysvětleme význam kompozice funkcí. Z teorie vyčíslitelnosti je známé, že vyčíslitelné (spočitatelné) funkce je možné získat z takzvaných počátečních funkcí, což je nulová funkce (zero function), funkce následníka (successor function) a projekce (projection), ze kterých jsou vytvářeny funkce složitější.

Mezi základní způsoby tvorby složitějších funkcí patří kombinace funkcí, kompozice funkcí a primitivní rekurze. V jazyce Joy se používá především kompozice funkcí, která bývá v matematice zapisována speciálním symbolem kolečka ° v infixové notaci, tj. symbol kolečka se umisťuje mezi názvy dvou funkcí, na které je aplikován (už z podstaty se totiž jedná o binární operaci). Ovšem Joy, přesněji řečeno jeho syntaxe, je založena na notaci postfixové, to znamená, že nejprve je zapsán operand (operandy) a teprve po něm jednotlivé funkce, které se na operand (operandy) aplikují. Díky tomuto způsobu zápisu se zcela eliminuje nutnost zápisu ° do programů, protože již z pozice jmen jednotlivých funkcí je zřejmé, jaké je pořadí operací – je určeno přesně tím pořadím, jakým program čteme, tj. zleva doprava, neboli opačně, než je tomu u funkcionálních programovacích jazyků založených na lambda kalkulu.

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"
.
[1 4 9 16] 

Druhým základem, na kterém je Joy založený, je citace programů, což 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í/o­perátorů, tj. ve skutečnosti za data, která je možné ve vhodném okamžiku „spustit“, tj. předat je funkci typu eval. Stejný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 

Pro srovnání si uveďme obdobný lispovský kód se speciální formou if:

(if (> x 1000) (/ x 2) (* x 3)) 

Sám autor tohoto jazyka jej označuje názvem concatenative language, čímž je myšlen fakt, že je kompozice funkcí zapisována v postfixové notaci, tj. jednotlivé funkce jsou za sebou zřetězeny.

3. Joy v porovnání s Lispem (Scheme) a Forthem

Svými možnostmi a celkovým dojmem je možné Joy považovat za jakýsi hybrid, který přebírá většinu dobrých vlastností z programovacích jazyků Lisp a Forth. To však v žádném případě neznamená, že by byl Joy vytvořen ve stylu „jak pejsek s kočičkou vařili dort“. Právě naopak – Joy je postaven na velmi jednoduchých funkcionálních základech a minimalistické syntaxi, podobně jako Lisp, přičemž samotný výpočet (vyčíslení funkcí) je založen na manipulaci se zásobníky, což je naopak doména Forthu.

Joy není jediný programovací jazyk, který se vydal tímto směrem, protože na podobných principech je postaven i programovací jazyk Factor autora Slavy Pestova (známý je především jeho multiplatformní programátorský editor JEdit), o kterém se později také zmíníme (ve skutečnosti je vývoj Factoru do velké míry ovlivněn právě Joyem a už zde je nutné říci, že zatímco Joy je především „akademický“ programovací jazyk, je naopak Factor ve větší míře zaměřený na praktické programování). Dalším podobným jazykem je Cat, který má dokonce vlastní GUI.

Prostředí programovacího jazyka Cat

Ve stručnosti je možné říci, že programování v Joyovi je založené na provádění operací nad položkami uloženými na zásobníku, podobně jako Forth, ovšem s tím rozdílem, že je rozšířen repertoár datových typů a především v tom, že na zásobníku mohou být uloženy také takzvané citované programy, s nimiž je možné manipulovat stejným způsobem, jako je tomu v Lispu. Bez podrobnějšího vysvětlování, na které bude čas dále, se podívejme na ukázku několika jednoduchých algoritmů zapsaných v programovacím jazyce Joy, aby byla vidět syntaktická podoba s programovacími jazyky založenými na postfixové notaci a současně i sémantická podoba s jazyky funkcionálními (funkce resp. operátor „tečka“ provede výpis položky obsažené na vrcholu zásobníku):

aplikace základních aritmetických operací
s tiskem výsledku pomocí operátoru tečky
20  3  4  +  *  6  -  100  rem .

definice nové funkce
square   ==   dup  *

aplikace funkce na numerické hodnoty uložené v seznamu
(výsledkem bude seznam s druhými mocninami původních hodnot)
[1 2 3 4]  [dup *]  map 

4. Postfixová notace a RPN

If you're a frequent calculator user, you owe it to yourself to investigate the advantages of RPN. RPN stands for Reverse Polish Notation. Reverse Polish Notation was developed in 1920 by Jan Lukasiewicz as a way to write a mathematical expression without using parentheses and brackets. Hewlett-Packard Co., realizing that Lukasiewicz's met­hod was superior to standard algebraic expressions when using calculators and computers, adapted RPN for its first hand-held scientific calculator, the HP35, in 1972.
Hewlett-Packard Development Company The RPN Method: An Overview and History 

Zápis veškerých operací, tj. způsob řazení operandů a operátorů či parametrů funkcí, je v programovacím jazyce Joy založený na takzvané postfixové notaci, známé také pod názvem obrácená Polská notace (RPN – Reverse Polish Notation). Název Polská notace byl zvolen na počest polského matematika Jana Lukasiewicze, který už v roce 1920 navrhl dvě možnosti psaní matematických výrazů bez nutnosti explicitní 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; druhou notací zavedenou Lukasiewiczem je prefixová notace, která v určitém ohledu připomíná zápis použitý v programovacím jazyce Lisp či Scheme.

Slavný kalkulátor HP-35 s RPN
(35 v názvu značí počet tlačítek)

Už na základní škole se však každý člověk učí takzvanou infixovou notaci zápisu, ve které se nejčastěji používané matematické operátory, jakými jsou sčítání, odčítání, násobení a dělení, zapisují mezi své operandy. Vzhledem k různé prioritě operátorů (například operátor násobení má definitoricky větší prioritu než sčítání) je však nutné v infixové notaci při zápisu složitějších výrazů velmi často používat závorky. Rozdíl mezi následujícími dvěma výrazy uvedenými v infixové notaci je zřejmý (znakem × je zapsán operátor násobení):

a+b×c
(a+b)×c 

Infixová notace se používá i při zápisu dalších operací, například operací logických (konjunkce, disjunkce) či množinových (sjednocení množin, průnik množin, doplněk množiny atd.). I u takových výrazů se mnohdy nevyhneme závorkám. Při použití postfixové notace však nejsou závorky ve výrazech nikdy zapotřebí, protože se priorita operací vyjadřuje přímo posloupností operátorů. Výše uvedené dva výrazy lze tedy do postfixové notace přepsat následovně:

a b c * +   nebo též   b c * a +
a b + c *   nebo též   c a b + * 

Všimněte si, že u výše uvedených RPN výrazů  proměnnými a, b a c napsaných na levé straně se oproti infixové notaci nemění pořadí operátorů. Toho se velmi často využívá při algoritmickém převodu mezi infixovou a postfixovou notací a také při ručním zápisu RPN výrazů. Tento převod provádí vlastně každý překladač či interpreter programovacího jazyka, a to buď přímo (mimochodem většinou opět s využitím zásobníku, do kterého jsou ukládány kódy požadovaných matematických operací a pozice závorek), nebo takzvaným rekurzivním sestupem podle gramatických pravidel daného jazyka. V případě použití programovacího jazyka Joy se jeho interpreter tímto převodem nemusí zabývat, protože na vstupu má již dopředu zpracovaný postfixový kód, který je možné bez dalšího složitého zpracování přímo interpretovat, což si můžeme ukázat na praktickém příkladu v jazyce Joy:

2 3 4 * + .
14

2 3 * 4 + .
10

2 3 4 + * .
14 

Kalkulátor HP-65 taktéž s RPN

Jaké jsou však výhody postfixového zápisu výrazů oproti zápisu infixovému? Mezi základní přednost patří už zmíněná absence závorek, pomocí nichž se v infixové notaci mění priority operací. Priorita je totiž v postfixové notaci velmi intuitivně určena přímo pozicí operátoru či funkce ve výrazu. Toho využívaly i kalkulačky HP, které žádné klávesy se závorkami neobsahovaly. Původní klávesnice byly vybaveny pouze tlačítky s číslicemi, čtyřmi klávesami pro základní matematické operace (ty se zadávaly za operandy) a klávesou [Enter], která prováděla uložení právě zobrazené hodnoty na displeji do zásobníku operandů (konkrétně na jeho vrchol označovaný symboly TOP, TOS či SP).

Mezi druhou výhodu postfixové notace patří – pro mnohé možná poněkud překvapivě – konzistence zápisu. Ve skutečnosti se totiž v běžně používané infixové notaci zapisují pouze některé základní matematické operace, jako je sčítání, násobení nebo dělení. Další operace se zapisují pomocí funkcí v prefixové notaci (například sinus, odmocnina, logaritmus, minimum) a některé dokonce v notaci postfixové (pravděpodobně nejznámější „postfixovou funkcí“ je faktoriál, který se zapisuje znakem vykřičníku umístěného za operand). Podobné je to i u programovacích jazyků, které pro některé operace mají rezervovány příslušná klíčová slova či znaky (+, -, *, %, ! atd.) s pevně danou syntaxí i prioritou a všechny další operace je nutné zapisovat formou funkcí.

Kalkulátory s RPN se vyráběly i v SSSR

Pomocí postfixové notace je možné zapisovat všechny operace i funkce, dokonce ani nezáleží na počtu operandů (stírá se tím rozdíl mezi unárními, binárními, ternárními apod. operacemi). Ve skutečnosti není v postfixové notaci prakticky žádný rozdíl mezi operacemi a funkcemi, takže pro ně není nutné zavádět nějaká zvláštní syntaktická pravidla. Mezi běžně používané funkce, které mají dva operandy, patří logaritmus o libovolném základu, exponenciální funkce a například také (spíše programátorská avšak velmi praktická) funkce atan2.

Rarita: RPN kalkulačka firmy Sinclair (Spectristům netřeba představovat)

Důsledkem výše uvedených skutečností je fakt, že znaky běžně používané pro aritmetické operátory je možné v programovacím jazyce Joy použít i pro jiné účely, podobně jako například v jazyce Lisp nebo Scheme, což jsou, jak jsme se dozvěděli v úvodu této kapitoly, jazyky používající prefixovou notaci, tou se však v dalším textu nebudeme zabývat.

5. Zásobníkové manipulátory

V předchozí kapitole jsme si řekli, že postfixová notace je založena na zápisu operátorů až za všechny operandy či parametrů funkcí před vlastní volání funkce. Veškeré výpočty jsou přitom prováděny na zásobníku (stack), což je datová struktura typu LIFO (Last In – First Out). To ovšem znamená, že je zapotřebí operandy nějakým způsobem umístit na zásobník, ze kterého budou následně při provádění operace opět vyjmuty, přičemž se na zásobník vrátí výsledek operace. Umístění operandů je velmi jednoduché – samotný zápis operandu, například čísla či pravdivostní hodnoty, je považován za operaci typu push, tj. vložení hodnoty operandu na aktuální vrchol zásobníku. Zcela stejný způsob zápisu je podporován v programovacím jazyku Forth, grafickém metaformátu PostScript nebo tradiční Unixové utilitě dc (Desk Calculator). Programovací jazyk Joy sice na zásobník umožňuje ukládat i složitější datové či programové struktury, ovšem princip zůstává stále stejný.

Základní operace se zásobníkem

Ovšem vzhledem k tomu, že programovací jazyk Joy neobsahuje explicitní přiřazovací příkaz a tím pádem ani pojmenované proměnné, je v některých případech nutné změnit způsob řazení operandů/parametrů na zásobníku, některé operandy odstranit či je naopak zkopírovat (duplikovat). K tomuto účelu jsou v jazyce Joy určeny takzvané zásobníkové manipulátory. Ve své podstatě se jedná o funkce, které rozšiřují čistě zásobníkový automat (nazývaný také push-pull automata) o další úroveň zpracování. Vzhledem k tomu, že je Joy navržen minimalisticky, obsahuje pouze tři základní zásobníkové manipulátory, které jsou vypsány v následující tabulce.

Kromě těchto tří základních zásobníkových manipulátorů je možné ve standardní knihovně najít i operátor nazvaný dip, který na zásobníku očekává dvě položky: citovaný program (viz další část tohoto seriálu) a libovolnou další hodnotu. Tato hodnota je po „spuštění“ operátoru dip uložena mimo zásobník, citovaný program, který je typicky zapsaný mezi závorky [ a ], je spuštěn a následně je původní, mimo zásobník uložená hodnota, opět obnovena. Pomocí všech čtyř popsaných zásobníkových manipulátorů lze vytvořit i manipulátory další, například:

Podobným způsobem je možné aplikovat i složitější zásobníkové operace, které zasahují do stále níže umístěných datových či programových položek umístěných na zásobníku. Poznámka: na zásobník nemusí být ukládány pouze číselné hodnoty, ale například i seznamy, řetězce či množiny.

Operace push a pop znázorněné na mechanické analogii zásobníku

6. Definice nových 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 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, znaky == oddělující název funkce od jejího těla a poté vlastní tělo funkce. Jednotlivé definice jsou od sebe odděleny znakem středníku, což 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 jedné zajímavosti, která dosti podstatným způsobem odlišuje „zásobníkové“ programovací jazyky od zbytku světa: 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 

Následuje klasický příklad funkce vracející maximální hodnotu z dvojice čísel uložených na zásobník. Příklad jsem upravil tak, aby využívat výše zmíněné zásobníkové manipulátory dup, dupd, pop, popd a swapd. Nejprve jsou duplikovány obě hodnoty umístěné na zásobníku, poté jsou porovnány (přičemž se původní hodnoty zahodí, proto je nutná duplikace) a posléze se na základě vyhodnocení porovnání ze zásobníku odstraní menší hodnota a výsledek, tj. hodnota větší, zůstane umístěná na nejvyšším místě zásobníku, protože ten slouží jako odkládací místo pro výsledky funkcí:

definice funkce max
(přepíšeme tím sice původní funkci, to však v této chvíli není na škodu)
DEFINE
    max == [dup swapd dupd >] [pop] [popd] ifte
warning: overwriting inbuilt 'max'
.

test funkce max:
10 20 max .
20
20 10 max .
20
10 10 max .
10
3 1 2 max max .
3
-1 -3 -2 -4 -5 max max max max .
-1 

Ve skutečnosti však lze funkci max napsat i jiným způsobem bez explicitního použití ifte, například následovně:

DEFINE
    max == dup swapd dupd > rotate choice
. 

7. 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 dalšími programovacími jazyky založenými na zásobníkovém kódu

HP 49g+ – kalkulačka pracující „pod obojí“, tedy jak v režimu RPN, tak i v algebraic­kém režimu

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

Ve druhé části celkem trojdílného článku o programovacím jazyce Joy si ukážeme ty nejzajímavější vlastnosti tohoto netradičního jazyka. Především se bude jednat o způsob citace programů, který představuje základ pokročilejšího funkcionálního programování a současně i metodu pro tvorbu maker, dále o použití kombinátorů a především náhrady klasicky pojaté rekurze pomocí takzvaných rekurzivních kombinátorů. Jako návnadu pro přečtení druhé části ukážu způsob zápisu programu pro výpočet faktoriálu a zobrazení výsledku výpočtu:

číslo [1] [*] primrec . 

Docela krátký zápis, že?

Přejete si něco složitějšího, například algoritmus QuickSort aplikovaný na seznam?

qsort  ==
    [ small ]
    [ ]
    [ uncons [>] split ]
    [ swap23 cons concat ]
    binrec