Programujeme v PostScriptu

Obsah

1. Programujeme v PostScriptu
2. Zásobníky
3. Obrácená polská notace (postfixový zápis matematických výrazů)
4. Operátory pro ovládání zásobníku
5. Aritmetické operátory
6. Relační a booleovské operátory
7. Odkazy na další informační zdroje
8. Obsah dalšího pokračování tohoto seriálu

1. Programujeme v PostScriptu

Ve všech předchozích částech tohoto seriálu jsme si popisovali rastrové i vektorové grafické formáty (či metaformáty), ve kterých byly informace o grafických objektech uložené v pevně zadaných a předem popsaných datových strukturách, tj. bez možnosti uložení jakéhokoli (procedurálního) programového kódu. Jedinou výjimkou byly v tomto ohledu skoky v animovaných GIFech, ty však není možné chápat jako plnohodnotný programovací jazyk. PostScript se od těchto grafických formátů v mnoha ohledech odlišuje, protože je to patrně nejrozšířenější a současně i nejznámější turingovsky kompletní programovací jazyk, který je založený na principu abstraktního vícezásobníkového procesoru, podobně jako programovací jazyk Forth, kterým jsem se již před dvěma lety na Rootu podrobně zabýval v samostatném seriálu.

Přitom je zajímavé, že následník PostScriptu, tj. formát PDF (Portable Document Format), je v tomto ohledu spíše chudý příbuzný. I to svědčí o způsobu vývoje „moderního“ softwaru, kdy je naprogramovaná funkcionalita nahrazována popisnými daty. Pravděpodobně nejdále v tomto směru došla některá schémata XML, ve kterých se i podmínky či cykly zapisují pomocí značek XML a ne programovým kódem. V následujících kapitolách si ukážeme základy programování v jazyku PostScript. Výklad začneme popisem zásobníků a obrácené polské notace (RPN). Posléze si popíšeme základní operátory, zejména aritmetické operátory, operátory pro ovládání zásobníku operandů, relační i booleovské operátory a operátory pro konverzi mezi různými datovými typy.

2. Zásobníky

Like all programming languages, the PostScript language builds on elements and ideas from several of the great programming languages. The syntax most closely resembles that of the programming language FORTH. It incorporates a postfix notation in which operators are preceded by their operands. The number of special characters is small and there are no reserved words.
PostScript ® LANGUAGE REFERENCE, third edition
(Adobe Systems Incorporated)

Programovací jazyk PostScript je, podobně jako programovací jazyk Forth či tradiční unixovská utilita dc, postaven nad abstraktním několikazásob­níkovým procesorem. Proto se při programování PostScriptu nevyhneme častým manipulacím se zásobníky, zejména se zásobníkem operandů. Tyto manipulace se buď provádí pomocí explicitně zadaných příkazů (například duplikace hodnoty uložené na zásobníku pomocí operátoru dup) nebo implicitními operacemi (například při provádění matematických výpočtů nebo při volání vestavěných funkcí). Mezi příkazy, které se zásobníkem manipulují, implicitně patří již dříve popsané funkce, jakou je moveto, která ze zásobníku přečte a posléze odstraní dva číselné parametry představující pozici bodu v rovině.

Zásobníky jsou v PostScriptu použity z několika důvodů. Asi nejvýznamnějším důvodem je, že se „zásobníkový kód“ velmi jednoduše a přitom rychle interpretuje. Ostatně mnoho abstraktních (virtuálních) procesorů je právě z tohoto důvodu postaveno na zásobnících; typickým příkladem je virtuální zdroj jazyka Java (JVM) či Pythonu. Nenechte se zmást paměťovou náročností Javy – příčina jejích obrovských paměťových nároků netkví v zásobníkovém kódu (právě naopak), ale v tom, že se pro každý i sebemenší javovský program načítá prakticky celé běhové prostředí Javy s několika tisíci třídami a rozhraními. Ale například Java Kilobyte Machine resp.  KVM běží, kromě PDA a mobilních telefonů, i na stařičkém ZX Spectru!

Další příčinou použití zásobníků v PostScriptu je unifikace všech operací. Zatímco se v běžné matematice vyskytují všechny tři zápisy matematických výrazů (prefixový, infixový i postfixový) a je definitoricky stanovena priorita některých operátorů, PostScript používá všude pouze postfixový zápis. Nepřímo s tím souvisí i způsob ukládání parametrů na zásobník před voláním funkcí a možnost návratu více hodnot z funkce (například minule zmiňovaný příkaz transform na zásobník vrací dvě hodnoty, což je v jiných programovacích jazycích většinou těžko dosažitelná operace). Třetí příčinou použití zásobníků je poměrně značná obliba Forthu v době navrhování PostScriptu. Ostatně volba programovacího jazyka na základě jeho oblíbenosti také není ničím novým – stačí se podívat na historii Cobolu či Javy.

3. Obrácená polská notace (postfixový zápis matematických výrazů)

V této kapitole si vysvětlíme princip postfixového zápisu matematických výrazů, který je také nazýván obrácená polská notace (RPN – Reverse Polish Notation), včetně způsobu práce RPN na zásobníkových procesorech. 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 (ostatně i v samotném názvu PostScriptu je postfixová notace skryta). Poznámka: následující text vznikl úpravou textu uvedeného ve článku Utilita DC vydaného dne 14.2.2006.

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

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

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 č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).

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.

Důsledkem výše uvedených skutečností je fakt, že znaky běžně používané pro aritmetické operátory je možné použít i pro jiné účely, podobně jako například v jazyce Lisp nebo Scheme (což jsou mimochodem jazyky používající prefixovou notaci, tou se zde však nebudeme zabývat).

4. Operátory pro ovládání zásobníku

Zásobník (anglicky stack), jenž je použit při zpracování aritmetických výrazů zapsaných v postfixové notaci, je z hlediska programování a programovacích technik dynamická datová struktura, pomocí které lze, podobně jako u implementačně příbuzného jednosměrně či obousměrně vázaného seznamu, ukládat a zpětně získávat data. Zásobník se od seznamu a dalších dynamických datových struktur, jako je fronta, strom či graf, liší především množinou základních operací, určenou pro práci s touto datovou strukturou.

Datová struktura zásobník nebo jeho hardwarová implementace se někdy označuje akronymem LIFO, který pochází z anglického výrazu Last In – First Out. Tento výraz docela přesně vystihuje základní vlastnost zásobníku: data, která byla do zásobníku vložena nejpozději, lze nejdříve přečíst. Naopak to platí samozřejmě také: nejdříve vložená data do zásobníku lze přečíst až po vyjmutí všech později vložených dat. Čistě implementovaný zásobník totiž neumožňuje přímo manipulovat s daty uloženými pod jeho vrcholem (to však není případ PostScriptu, který obsahuje operátory typu index, jež mohou zasahovat i hluboko do zásobníku).

Zásobník si můžeme znázornit i graficky spolu se dvěma základními operacemi: vložení prvku (operace push) a vyjmutí prvku spolu s navrácením jeho hodnoty (operace pop):

V PostScriptu je pro ovládání zásobníku operandů (to je zásobník používaný pro výpočty) určeno několik operátorů, z nichž ty nejdůležitější jsou vypsány v následující tabulce:

Použití těchto operátorů je jednoduché. Stačí si uvědomit, že zápis čísla automaticky znamená jeho uložení na vrchol zásobníku:

1 2 3 4 count clear
1 dup clear
1 2 exch clear
1 2 mark 3 4 cleartomark 

5. Aritmetické operátory

Aritmetické operátory pracují s jednou či dvěma číselnými položkami uloženými na zásobníku. Tyto položky jsou ze zásobníku odebrány, je s nimi provedena požadovaná operace a výsledek operace (vždy jedno číslo) je uložen zpět na zásobník. PostScript rozeznává několik typů číselných údajů, nejčastěji se setkáme s celými čísly (integer) a čísly reálnými (real). O převod mezi těmito dvěma datovými typy se starají operátory zaokrouhlení.

Příklad použití:

1 2 add
1 2 3 add mul
1 2 3 mul add % rozdíl od předchozího!
0.5 1 atan 

6. Relační a booleovské operátory

PostScript rozpoznává i pravdivostní (logický) datový typ boolean. Hodnoty tohoto typu jsou výsledkem dále uvedených operací. Tyto operace očekávají, že budou mít své operandy uloženy na zásobníku a výsledek opět vrací na zásobník. Všimněte si, že některé operace se chovají různě podle toho, jaké typy hodnot jsou uloženy na zásobníku (zásobník si tedy musí „pamatovat“ i typy hodnot, což je rozdíl oproti Forthu). Jedná se vlastně o formu přetěžování operátorů, a co je důležité – stejnou funkcionalitu je možné zajistit i pro uživatelské příkazy.

Příklad použití:

true false and clear
1 42 eq clear 

7. Odkazy na další informační zdroje

1. Adobe Systems: PostScript Language Reference Manual, The Red Book,
   Adobe Systems Incorporated, 2nd ed., Addison Wesley 1990.
2. PostScript Language Program Design,
   Addison-Wesley 1990, ISBN 0–201–14396–8
3. PostScript Language Reference Manual,
   Addison-Wesley 1990, ISBN 0–201–18127–4
4. PostScript Language Tutorial and Cookbook,
   Addison-Wesley 1990, ISBN 0–201–10179–3
5. Wikipedia: PostScript,
   http://en.wiki­pedia.org/wiki/Pos­tScript
6. Paul Bourke: PostScript Tutorial,
   http://local.was­p.uwa.edu.au/~pbou­rke/dataformat­s/postscript/
7. A First Guide to PostScript,
   http://www.ta­ilrecursive.or­g/postscript/pos­tscript.html

8. Obsah dalšího pokračování tohoto seriálu

V následují části seriálu o grafických formátech si ukážeme tvorbu nových příkazů (operátorů, funkcí, maker), použití podmíněných příkazů a také vytváření programových smyček.