Programovací jazyk Forth a zásobníkové procesory (12)

Obsah

1. Význam jazyků založených na Forthu
2. PostScript
3. Zajímavé programy v PostScriptu
4. Funkcionální jazyk Joy
5. OpenBoot a Open Firmware
6. Virtuální stroj jazyka Java
7. Obsah dalšího pokračování

1. Význam jazyků založených na Forthu

Forth v sobě spojuje jak jednoduchou syntaxi a sémantiku samotného jazyka, tak i důraz na vytváření krátkých slov, která je možné ihned při jejich vytvoření otestovat (to ve své podstatě odpovídá dnes módnímu extrémnímu programování). Další význačnou vlastností Forthu je velmi malá náročnost na systémové zdroje, takže se Forth používal a stále používá v různých vestavěných zařízeních, a jak uvidíme dále, i v tiskárnách a osvitových jednotkách. Jazyky, které jsou na Forthu založeny, tyto vlastnosti v menší či větší míře zdědily, proto jsou velmi jednoduché jak na implementaci, tak i pro psaní aplikací.

2. PostScript

A page description language (PDL) developed by Adobe Systems. PostScript is primarily a language for printing documents on laser printers, but it can be adapted to produce images on other types of devices. PostScript is the standard for desktop publishing because it is supported by imagesetters, the very high-resolution printers used by service bureaus to produce camera-ready copy.
Webopedia

Patrně nejrozšířenější a současně nejznámější jazyk, který je založený na Forthu a abstraktním zásobníkovém procesoru, se jmenuje PostScript. Jedná se o specializovaný jazyk primárně určený pro popis stránky, která se má vytisknout na postscriptové tiskárně, převést na bitmapový obrázek pro „hloupější“ tiskárny nebo zobrazit na obrazovce počítače vhodným prohlížečem (například programem GhostView spolu s GhostScriptem).

Na rozdíl od ostatních jazyků pro popis stránky (jmenujme například často používaný PCL, HP-GL pro plottery atd.) je však PostScript plnohodnotný programovací jazyk s proměnnými, řídicími strukturami, možností definice nových slov a proměnných apod. Program napsaný v PostScriptu existuje v čitelné podobě ve formě (skoro)textového souboru, který má příponu .ps nebo .eps (zapouzdřený PostScript). V tomto souboru mohou být uložena i binární data fontů, bitmap apod., proto mohou nastat problémy při ruční editaci souboru v těch textových editorech, které do souboru některé znaky přidávají nebo z něj naopak ubírají.

Program pro popis stránky může být v PostScriptu napsán velmi čitelně, nicméně prakticky všechny aplikace, které PostScriptový soubor generují, produkují pro člověka nečitelný kód – prohlédněte si například PostScriptový výstup z TeXu nebo Wordu (obdobou prakticky nečitelného výstupu jsou i mnohé WYSIWYG editory HTML, které také neprodukují zrovna čistý a čitelný HTML kód). Snad jedinou světlou výjimkou je AutoCAD, jehož PostScriptový výstup je docela dobře čitelný a je také ukázkou, jak vytvářet nová slova pro zmenšení celkové velikosti PostScriptového souboru.

Na PostScriptu je založeno mnoho dalších aplikací. Kromě již zmíněných programových prohlížečů jsou to tiskové programy (poněkud nesprávně nazývané RIPy), které mohou provádět konverzi PostScriptového souboru na bitmapy, jež se mají zobrazit. Tyto konverzní programy nejsou vlastně nic jiného než interpretery programovacího jazyka PostScript, které postupně zadaný program vykonávají a podle volaných funkcí mění barvu jednotlivých pixelů výsledné bitmapy.

PostScriptové tiskárny také obsahují interpreter PostScriptu, který skládá jednotlivé stránky a postupně je tiskne. Na některých tiskárnách jde také ovládat zabudovaný displej a klávesničku a psát pomocí příkazů PostScriptu humorné hlášky obsluze.

PostScriptový program pracuje následovně: při inicializaci každé stránky je nejprve tato stránka vymazána, tj. všechny pixely odpovídající bitmapy jsou nastaveny na bílou barvu (barvu pozadí). Programátor či aplikace, která vytváří PostScriptový program, však nemusí pracovat až na nejnižší úrovni, tj. na úrovni bitmapy složené z jednotlivých pixelů, ale může celou stránku seskládat ze základních grafických primitiv, kterými jsou v PostScriptu cesty a znaky.

Naproti tomu jednoduché rastrové tiskárny (zejména takzvané Windows GDI tiskárny) přijímají pouze bitmapy ve svém nativním rozlišení. Veškeré rastrování tedy provádí samotný počítač a tiskárna pouze tiskne výslednou bitmapu. Nevýhoda programového rastrování nemusí být na první pohled zřejmá, zejména při výpočetním výkonu moderních počítačů, ale zkusme se zamyslet nad tím, jak se poměrně veliká bitmapa přenáší například po počítačové síti (ve skutečnosti jsou prakticky všechny síťové tiskárny PostScriptové).

Patrně nejmocnější je na PostScriptu vytváření cest – ty byly později převzaty i do dalších formátů, například SVG – Scalable Vector Graphics, na jejichž vývoji se taktéž podílela firma Adobe (vlastník licence PostScriptu). Každá cesta se skládá z křivek, dokonce je možné převádět jednotlivé znaky na křivky. Křivka má zadané základní vlastnosti, jako je typ čáry, výplňový vzorek, způsob zakončení a barva (ta pouze u novějších verzí PostScriptu). Pomocí uzavřených cest lze také ořezávat část obrázku. Parametry jednotlivých křivek, ze kterých je cesta složena, se ukládají na zásobník. Vlastní vykreslení (tisk) se provádí pomocí slovaSHOWPAGE.

Vzhledem k tomu, že je PostScript založený na Forthu, má zabudovány i základní operátory pro práci se zásobníkem. Jedná se o následující operátory (resp. v terminologii Forthu slova): DUP, DROP, SWAP, OVER a ROT. Jednotlivá slova se tvoří poněkud odlišným způsobem: pomocí DEF, nikoli dvojtečky a středníku. Kromě toho lze vytvářet i další rozšiřující slova, která ve Forthu chybí, a používat rozhodovací a iterační konstrukce (smyčky). Syntaxe se poněkud odlišuje od standardního Forthu, nicméně smysl zůstává stejný.

Jednoduchý prográmek v PostScriptu i s nutnou hlavičkou může vypadat například následovně (jsou použita slova LINETO a CURVETO pro vykreslení polyčáry/cesty se zaoblenými hranami tvořenými Bézierovými křivkami):

400 72 translate/L{lineto}def/C{curveto}def
0 0 moveto 0 24 L 9 24 10 0 5 0 C
18 14 L 21 -6 23 0 27 16 C 32 0 L
37 0 45 12 45 24 C 45 0 L 45 24 L
54 22 50 20 46 10 C 59 9 51 6 49 0 C
58 10 66 -4 78 4 C 87 20 L
93 0 99 3 104 6 C 108 0 L
1 setlinejoin stroke showpage
(David Brooks, Open Software Foundation) pop

3. Zajímavé programy v PostScriptu

V této kapitole uvedu některé zajímavé prográmky vytvořené v PostScriptu. Jedná se o takzvané signatury, tj. programy, které lidé ve zdrojovém kódu přidávají na konce svých e-mailů. Dobrá signatura musí být co nejkratší (a tím pádem prakticky nečitelná ;-). Níže uvedené programy je možné zobrazit například pomocí aplikací GhostScript a GhostView, nebo je lze poslat na PostScriptovou tiskárnu (to ovšem například u generátorů fraktálů nedoporučuji, zejména u síťových školních či podnikových tiskáren :-). Převod na program v PostScriptu je jednoduchý – copy and paste do souboru s koncovkou .ps.

Duhová číslice 42 s texturou (mimochodem, 42 je odpověď na velmi zásadní otázku, která zní… …ale ne, implementujte si svou Hlubinu myšlení):

%!ps Bertrand Petit
550 0 translate 90 rotate /NewCenturySchlbk-Bold findfont 690 scalefont setfont
-5 15 moveto (42) true charpath clip /Helvetica-Bold findfont 8 scalefont
setfont 0 9 800 { dup 360 mod 360 div 1 1 sethsbcolor /y exch def rand 10 mod
neg 11 800 { y moveto (42) show }for }for clippath 4 setlinewidth 0 setgray
stroke showpage

Dynamický systém (fraktál – nespouštět na síťových tiskárnách):

/d{def}def/a{add}d/s{sub}d/u{usertime}d % Alun Jones, IBS, UW Aberystwyth
/x 0 d/y 0 d 9 9 scale 35 47 translate/b u d .1 setlinewidth{u b s 6e4 gt
{exit}if/x x 4 a d/v 1 x s d/x y 2 x mul 3 s abs sqrt x 0 lt{neg}if a d/y
v d x y moveto .1 0 rlineto stroke}loop showpage% You may need %!PS-Adobe

Fraktální keř vytvořený pomocí L-systému (opět raději netrapte svou tiskárnu, GhostScript je méně drastické řešení):

%!  -Markku Rossi
/d{def}def/t{translate}d /r{rotate}d /F{0 0 moveto 0 10 rlineto stroke 0 10
t }d/P{22 r}d/M{-22 r}d/S{gsave}d/R{grestore}d 240 90 t/E{dup 1 eq{F}{dup 1
sub E E M S M E P E P E R P S P E M E M E R pop} ifelse} d 5 E pop showpage

Mandelbrotova množina v 294 bytech zdrojového kódu – můj favorit:

/D{def}def /d{.00017 add D}D /C{2 copy dup mul exch dup mul}D /g 150 string
D /y .29 D 150 150 8[.4 0 0 .4 -45 -90]{/x -1.2 D 0 1 149{x y /n 300 D{/n n
5 sub D C exch sub x add 3 1 roll 2 mul mul y add C add 4 gt n 5 eq or{exit
}if}loop pop pop g exch n put /x x d}for /y y d g}image showpage

4. Funkcionální jazyk Joy

The language Joy is a purely functional programming language. Whereas all other functional programming languages are based on the application of functions to arguments, Joy is based on the composition of functions. All such functions take a stack as argument and produce a stack as value. Consequently much of Joy looks like ordinary postfix notation. However, in Joy a function can consume any number of parameters from the stack and leave any number of results on the stack. The concatenation of appropriate programs denotes the composition of the functions which the programs denote.

Joy je velmi zajímavý funkcionální programovací jazyk, který svým zaměřením vychází jak z Forthu, tak i z LISPu. Funkcionální jazyky jsou již tradičně založeny na aplikaci funkcí (aplikaci ve smyslu Lambda kalkulu), v programovacím jazyce Joy je však zvolena odlišná možnost: kompozice funkcí, která vede k postfixovému zápisu funkcí (operátorů) a operandů.

Odlišnost aplikace funkcí od jejich kompozice uvedu na porovnání dvou malých programů. První program je vytvořený v LISPu:

(* (+ 1 2) (- 3 4))

Výše uvedený program je sestaven ze tří funkcí. Funkce * (násobení) očekává minimálně dva argumenty, jejichž hodnoty mezi sebou vynásobí a vrátí výsledek. Argumenty jsou opět tvořeny funkcemi, v našem případě jsou to funkce + a -, které provádějí výpočet součtu resp. rozdílu hodnot svých argumentů.

V programovacím jazyce Joy by se místo předávání výsledků funkcí jiným funkcím použila jejich kompozice. Využívá se toho, že parametry jsou uloženy na zásobníku, stejně jako výsledky funkcí. Výsledků může být i více, podobně jako ve Forthu:

1 2 + 3 4 - *

Výše uvedený kód značí, že se na zásobník nejprve uloží hodnoty 1 a 2, protože číselné hodnoty jsou ve své podstatě atomy, které se vyhodnotí na sebe sama. Posléze se zavolá funkce +, která sečte dvě hodnoty, které najde na zásobníku a posléze na zásobník uloží výsledek operace. Podobná činnost se opakuje s hodnotami 3 a 4, na které je aplikována funkce -. Nakonec se zavolá funkce *, která provede vynásobení dvou hodnot, které nalezne na zásobníku. Vzhledem k tomu, že program touto funkcí skončil, vytiskne se automaticky hodnota (či hodnoty) ze zásobníku, podobně jako v LISPu, kde se vypíše návratová hodnota poslední zpracovávané funkce.

Je vidět, že až do této chvíle se Joy choval podobně jako Forth. Oba jazyky jsou však odlišné zejména v podporovaných datových typech a v tom, že v Joyovi je možné funkce skládat přímo na zásobníku a posléze je také vyvolat (spustit).

Joy podporuje následující datové typy:

1. celá čísla (integer)
2. čísla uložená ve formátu pohyblivé řádové tečky (float number)
3. logické hodnoty (boolean)
4. znaky (char)
5. řetězce (string) – konstruktor: „pokus“
6. množiny (set) – konstruktor: {1 2 3}
7. seznamy (list) – konstruktor: [a b c]
8. soubory (file)

Celá čísla, čísla v pohyblivé řádové čárce, znaky a logické hodnoty patří mezi primitivní datové typy, nad kterými jsou vytvořeny všechny základní (tj. očekávatelné) aritmetické, logické aj. funkce, podobně jako v jiných programovacích jazycích. Řetězce, množiny, seznamy a soubory jsou naproti tomu určeny pro tvorbu strukturovaných typů a zejména u seznamů je vidět velká inspirace v LISPu. Určitým zklamáním jsou množiny, které mohou jako své prvky obsahovat pouze celá čísla, takže operace s množinami není tak flexibilní, jak by se mohlo na první pohled zdát.

Důležité přitom je, že všechny výše zmíněné datové typy (resp. návratové hodnoty z funkcí) jsou mezi funkcemi předávány na zásobníku. Následující příklad provede spojení dvou seznamů:

[1 2 3] [4 5 6] concat

Postup při provádění programu je zřejmý: nejprve se vytvoří oba seznamy přímo pomocí svých konstruktorů a posléze se zavolá funkce concat, která tyto seznamy spojí a na zásobník uloží výsledný seznam [1 2 3 4 5 6].

Vedle toho zavádí Joy takzvané kombinátory (opět inspirované LISPem), které jsou podobné operátorům, ale s tím rozdílem, že se provádí přímo kód uložený na vrcholu zásobníku. Jednoduchý příklad na kombinátory:

[1 2 3 4] [dup *] map

Vrátí na vrcholu zásobníku výsledek:

[1 4 9 16]

Samotný zápis sekvence příkazů v seznamu lze „spustit“ zadáním středníku:

[10 20 30 + * ] ;

Nakonec si ještě uveďme, jak se v Joyovi vytváří nové funkce. Syntaxe je poněkud odlišná od Forthu, ale význam je prakticky stejný. Kód:

square == dup *

je možné ve Forthu zapsat následovně:

: square dup * ;

Nelze samozřejmě očekávat, že by se Joy vyvíjel až do té podoby, že by byl používaný v komerčních aplikacích; nicméně se jedná o velmi zajímavý funkcionální jazyk, který v sobě spojuje výhody postfixové notace (a virtuálních zásobníkových procesorů) a funkcionálních jazyků (zejména seznamů a rovnosti dat a kódu). Zdrojové kódy jsou na výše uvedené stránce k dispozici, proto je možné Joy běžným způsobem přeložit a vytvořit v něm nějaké jednodušší prográmky.

5. OpenBoot a Open Firmware

Open Firmware provides a novel capability, virtually unheard of before its invention in 1988 at Sun. This new capability is writing hardware independent boot code, firmware and device drivers.
Sabaki Engineering

Technologie OpenBoot a Open Firmware byly vytvořeny firmou Sun Microsystems pro tvorbu firmware (zjednodušeně řečeno systému základních ovladačů) nezávislého na použitém výpočetním systému. Idea je taková, že napsaný firmware, který například u počítačů zajišťuje načtení a start operačního systému (u dalších zařízení i jinou činnost), by měl být přenositelný mezi různými platformami. Další důležitou vlastností OpenBootu a OpenFirmware je možnost programování a interaktivního ovládání celého procesu bootování i konfigurace počítače přes shell, který je založen na Forthu (ostatně celý OpenFirmware je naprogramován ve Forthu a přeložen do forthského bytekódu).

V současné době je OpenFirmware provozován na stanicích SPARC, počítačích firmy Apple a na některých serverech od IBM. Do budoucna se plánuje i vývoj BIOSu pro počítače PC, který by byl také založený na OpenFirmware – to by ostatně znamenalo po dlouhé době zase velký skok PCček směrem k opravdu profesionálním výpočetním systémům ;-)

6. Virtuální stroj jazyka Java

JVM – Java Virtual Machine představuje v dnešní době patrně nejznámější prostředí pro běh programů zapsaných v instrukcích abstraktního zásobníkového procesoru. Samotný programovací jazyk Java se sice v prakticky žádném svém aspektu nepodobá Forthu nebo jiným jazykům určeným pro programování zásobníkových procesorů (spíše naopak), ale po překladu javovského zdrojového kódu nevznikne strojový kód přímo pro daný procesor, ale takzvaný bytekód, který je možné interpretovat právě pomocí JVM (Javu je samozřejmě možné překládat přímo do strojového kódu nějakého mikroprocesoru, většinou se však používá překlad právě do bytekódu).

Javovský bytekód používá zásobník především pro vyčíslení aritmetických a logických výrazů. V bytekódu jsou definovány instrukce pro práci s čísly reprezentovanými jak celočíselnou aritmetikou, tak i čísly typu IEEE float a IEEE double. To je významný krok vpřed oproti jiným virtuálním zásobníkovým počítačům, které většinou obsahují instrukce pouze pro práci s celočíselnými hodnotami, a reálná aritmetika tak u nich musí být řešena voláním knihovních funkcí.

V minulosti, kdy situace pro Javu – a firmu Sun Microsystems obecně – vypadala velice příznivě, byly vyvinuty procesory určené pro efektivní běh javovského bytekódu. Jednalo se o procesory UltraJava, MicroJava a PicoJava, které se lišily jak počtem přímo prováděných instrukcí bytekódu (některé složitější instrukce bylo zapotřebí emulovat), tak i svou taktovací frekvencí. Tyto procesory se však z více důvodů neprosadily, takže v současné době jsou programy v Javě provozovány na klasických procesorech typu RISC a CISC.

První verze Javy, která se označovala číslem 1.0, používala klasickou interpretaci javovského bytekódu. Zjednodušeně řečeno to znamená, že pro každou instrukci bytekódu byla vytvořena kratší či delší sekvence instrukcí pro daný procesor (například pro Intel Pentium). Interpretace pak vypadala tak, že se postupně načítaly jednotlivé instrukce z bytekódu a volaly se pro ně tyto vytvořené sekvence. Je jasné, že rychlost běhu programů v Javě byla menší než u přeloženého programu (napsaného například v C-čku).

Druhá generace překladačů se vyznačovala použitím JIT (Just In Time) překladačů, které pracovaly nad již vytvořeným bytekódem aplikace. Překlad byl prováděn pro celou aplikaci (či pro jednotlivé načítané moduly) před spuštěním, proto nemohla být optimalizace při překladu dokonalá – to by znamenalo příliš velké zdržení při načítání.

Z tohoto důvodu je ve třetí generaci JVM použita hot spot optimalizace, kdy se přímo za běhu programu vyhledávají místa, která je možné optimalizovat. Přitom se uvažuje, že platí známá zásada, že 80 % času běhu programu je obsaženo pouze ve 20 % kódu (v některých případech je to dokonce 90 % a 10 %). Kvalitní optimalizace je tedy vhodné provádět pouze pro oněch 20 % kódu, zbylou část je možné pouze interpretovat. Zde se opět ukazuje výhoda použití zásobníkového kódu, protože ten je poměrně jednoduché analyzovat a následně optimalizovat.

7. Obsah dalšího pokračování

V dalším pokračování tohoto seriálu se již začneme podrobněji zabývat zásobníkovými procesory, jejich vlastnostmi, parametry a způsobem využití.