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

Obsah

1. Paradigma programování ve Forthu
2. Základní operace s obsahem zásobníku operandů
3. Vytváření nových slov
4. Podmínky
5. Počítané cykly
6. Poznámky
7. Obsah dalšího pokračování

1. Paradigma programování ve Forthu

Programovací jazyk Forth přímo podporuje strukturované a modulární programování, i když ponechává na každém vývojáři, zda bude, či nebude tyto dva mechanismy používat (podobně se chová Pascal, Céčko, Python apod.). Tento styl programování vychází z následujících principů (viz například známé články od Dijkstry):

1. Každý program je popsán jako lineární sekvence modulů.
2. Každý modul má jeden vstupní bod a jeden bod výstupní. Modul by měl vykonávat pouze jednu přesně specifikovanou funkci s jasně specifikovanou množinou vstupních a výstupních hodnot.
3. Každý modul může obsahovat pouze následující jazykové struktury: odkazy (volání) jiných modulů, smyčky (pouze uvnitř modulů) a rozhodovací struktury typu IF-THEN, IF-THEN-ELSE, popř. SWITCH-CASE.

Forth již z principu své práce neobsahuje příkaz goto ani žádnou jeho alternativu – všechny příkazy pracují přísně lokálně. Pomocí několika nových slov lze do Forthu zavést i principy OOP, tj. objektově orientovaného programování.

V následujících kapitolách si popíšeme operace prováděné s datovými položkami uloženými na zásobníku, princip tvorby nových slov a vestavěná slova pro programování podmínek a cyklů.

2. Základní operace s obsahem zásobníku operandů

V předchozích dílech tohoto seriálu jsme si vysvětlili několik operací, kterými lze ovládat obsah zásobníku operandů. Umíme již na zásobník ukládat číselné hodnoty pouhým zadáním číselné konstanty, provádět základní matematické operace a nakonec vytisknout hodnotu uloženou na vrcholu zásobníku operandů pomocí interního slova . (tečka).

Vzhledem k tomu, že zásobník operandů tvoří ve Forthu ústřední místo veškerého dění, je zapotřebí mít k dispozici i další operace, které mohou manipulovat s datovými položkami na zásobníku uloženými. V některých případech nám totiž nemusí vyhovovat pořadí položek uložených na zásobníku, položky je nutné duplikovat, mazat apod. Z tohoto důvodu má jazyk Forth implementovány následující základní operace (slova) nad zásobníkem, resp. nad jeho obsahem:

2.1 Slovo „swap“

Pomocí tohoto slova se provede prohození nejvyšší a druhé nejvyšší datové položky uložené na zásobníku. Pokud byla na zásobníku uložena čísla 1 a 2, je po provedení tohoto slova na nejvyšších dvou pozicích zásobníku uložena posloupnost 2 1. Následuje jednoduchý příklad použití:

Uložení dvou čísel na zásobník a jejich následný výpis na obrazovku spolu s odřádkováním pomocí slova cr:

1 2 . . cr

Uložení dvou čísel na zásobník, provedení slova swap a následný výpis čísel na obrazovku:

1 2 swap . . cr

2.2 Slovo „dup“

Pomocí vestavěného slova dup se provede kopie (duplikace) hodnoty uložené na vrcholu zásobníku. Velikost zásobníku se tedy o jednotku zvětší. Toto slovo se využívá v mnoha případech, například pro přípravu na matematickou operaci násobení dvěma, umocnění, předání parametru na zásobník návratových adres apod. Ilustrační příklad použití této operace:

1 dup . . cr

V následující kapitole bude ukázáno, jakým způsobem se slovo dup použije při výpočtu druhé mocniny.

2.3 Slovo „drop“

Opakem interního slova dup je slovo drop, pomocí něhož se odstraní položka z vrcholu zásobníku. Toto slovo, jež se často používá při „úklidu“ po nějaké složitější operaci, je podobné slovu. (tečka), avšak s tím rozdílem, že neprovádí výpis hodnoty odstraňované položky. Příklad použití:

1 2 drop . cr

2.4 Slovo „over“

Slovo over se podobá výše popsanému slovudup, tj. provádí se kopie hodnoty uložené v zásobníku. V tomto případě se však jedná o hodnotu uloženou pod vrcholem zásobníku, nikoli o hodnotu uloženou přímo na vrcholu zásobníku. Chování této funkce se nejlépe předvede na jednoduchém příkladu, který porovná význam operací over a dup:

1 2 dup . . . cr
1 2 over . . . cr

2.5 Slovo „rot“

Slovo rot manipuluje hned se třemi položkami uloženými na zásobníku. Jak již název tohoto slova napovídá, provádí se rotace položek, a to tak, že datová položka na třetí nejvyšší pozici v zásobníku operandů je vyjmuta a uložena na jeho vrchol. Opět je vhodné si vyzkoušet jednoduchý příklad, nejprve výpis tří položek bez rotace:

1 2 3 . . . cr

A následně s rotací:

1 2 3 rot . . . cr

2.6 Manipulace s položkami uloženými na nižších úrovních v zásobníku

Pro manipulaci s datovými položkami, které jsou na zásobníku uloženy ve větší hloubce než tři je možné ve většině implementací Forthu použít slova pick a roll. Jedná se ve své podstatě o selektory podobné indexům do polí u jiných programovacích jazyků – pokud se ovšem na zásobník díváme jako na dynamicky alokované pole s proměnnou velikostí.

V reálných programech se však tato slova nevyskytují a jejich použití ani není doporučováno, protože neodpovídá programovacímu stylu používanému ve Forthu.

Pokud je zapotřebí získat informace z dalších míst zásobníku, nebo je tam uložit, je možné využít zásobník návratových adres (return stack) nebo použít proměnných pro uložení dočasných hodnot. Většinou však potřeba zásahu do hloubky zásobníku vychází ze špatného návrhu programu.

3. Vytváření nových slov

Forth místo funkcí, operací a řídicích struktur používá pouze slova. Slova se zadávají z klávesnice nebo ze vstupního souboru a jsou určena svým jménem. Jméno je ve Forthu libovolný řetězec znaků, který je oddělen (ukončen) mezerou nebo v novějších verzích libovolným „bílým znakem“. Každé volání funkce je ve forthovském programu nahrazeno jejím jménem bez dalších znaků (závorek apod.), protože veškeré parametry funkce i její návratová hodnota jsou uloženy na zásobníku.

Ve Forthu jsou rozeznávány tři typy slov: definovaná slova, nedefinovaná slova a číselné konstanty. Základní slova, například operace se zásobníkem popsané v předcházející kapitole, jsou většinou vytvořena přímo pomocí operací napsaných v assembleru.

Definovaná slova jsou ukládána do slovníku (dictionary), který je většinou implementován jako lineární seznam nebo jako zásobník. V multiuživatel­ských systémech má každý uživatel k dispozici svůj slovník, přičemž existuje ještě slovník společný.

První krok, který se před spuštěním Forthovských aplikací provádí, je rozklad řetězců, které jsou zadány uživatelem nebo načteny z datového zařízení (pevného disku, paměti EPROM apod.), do jednotlivých slov, což je operace triviální (na rozdíl od prakticky všech ostatních programovacích jazyků, které mají složitější syntaxi), protože za slova je považován souvislý řetězec oddělený bílými znaky. Tomu, kdo psal lexikální analyzátory pro jazyky podobné C-čku či Pascalu, je zřejmé, že napsání základní lexikální analýzy pro Forth je otázka několika řádků kódu.

Každé slovo v řetězcové podobě je následně vyhledáno ve slovníku. Pokud je nalezeno, je proveden jeho kód (slovo je v paměti uloženo jako seznam ukazatelů na další slova nebo primitivní operace). Pokud slovo ve slovníku nalezeno není, je považováno za číslo, které je po převodu do binární podoby uloženo na zásobník. Pokud převod na číselnou konstantu z nějakého důvodu selže, znamená to, že jde o neznámé slovo, proto interpreter nahlásí chybu. Zde je opět vidět syntaktická jednoduchost jazyka, který rozeznává pouze slova a numerické hodnoty (operandy a řídicí struktury jsou také slova).

Pro vytváření nových slov se používají pouze dvě zabudovaná slova. Prvním slovem je : (dvojtečka) a druhým slovem je ;(středník). Po zadání dvojtečky se interpretr Forthu přepne z režimu Execute (přímého vykonávání zadávaných příkazů) do režimu Compile (překlad nového slova). Naopak, po zadání středníku se interpretr přepne z režimu Compile do režimu Execute (samotný středník se přitom překládá jako return). Za slovem dvojtečka musí následovat jméno nového slova.

Nově vytvořená slova se chovají stejným způsobem jako slova zabudovaná, tj. jejich parametry se vybírají ze zásobníku a výsledek je taktéž uložen na zásobník. V tom spočívá jedna z krásných vlastností Forthu, kdy je vytváření a volání slov velmi jednoduché a rychlé. Ukažme si vytvoření nového slova print, které vytiskne hodnotu uloženou na vrcholu zásobníku a potom kurzor přesune na nový řádek:

: print
  .
  cr
;

Slovo print, které musí být od slova dvojtečky odděleno bílým znakem, tedy vytiskne hodnotu uloženou na vrcholu zásobníku (to zajistí volání zabudovaného slova tečka) a potom provede odřádkování pomocí interního slova cr. Středník ukončí kompilaci nového slova a vrátí řízení zpátky do režimu Execute. Můžeme ihned provést několik interaktivních testů s nově vytvořeným slovem:

10 print
1 2 + print
1 2 3 * - print

Vzhledem k tomu, že je tělo slova print velmi krátké, můžeme ho zapsat i na jeden řádek:

: print . cr ;

Příkladem složitějšího slova může být například mocnina. Toto slovo vezme ze zásobníku hodnotu a na zásobník vrátí její druhou mocninu. Slovo může vypadat následovně:

: mocnina dup * ;

Nejdříve se tedy provede duplikace hodnoty na vrcholu zásobníku. Poté se obě (shodné) hodnoty ze zásobníku vyjmou, vynásobí a na zásobník se uloží výsledek operace násobení. Použití tohoto slova je opět velmi jednoduché:

2 mocnina . cr
10 mocnina print

(na druhém programovém řádku používáme dříve vytvořené slovo print)

4. Podmínky

Nedílnou součástí všech imperativních programovacích jazyků je i jazyková konstrukce pro podmínky. Forth se k této problematice staví poněkud odlišným způsobem: pro zápis podmínek používá tři slova, nejedná se tedy o speciální jazykovou konstrukci, ale o mimořádně flexibilní mechanismus, který umožňuje přidávat i další „strukturované“ konstrukce bez zásahu do překladače.

Tři slova pro zápis podmínky jsou if, else a then. Jejich použití (zejména umístění) se však již na první pohled liší od jiných programovacích jazyků. Schematicky lze celou konstrukci zapsat následovně:

logický_výraz
if
  příkazy_1_větve
else
  příkazy_2_větve
then

To znamená, že slovo then se zde spíš používá ve významu endif. Výsledek logického výrazu musí být uložen na zásobník operandů, odkud je při zavolání slova if vyjmut a je zjištěna jeho hodnota. Při nenulové hodnotě (true) je vykonána první větev, při nulové hodnotě větev druhá. Po vykonání jedné z obou větví běh programu pokračuje slovem, které se nachází za then.

Zkrácená podoba podmínky bez druhé větve má tvar:

logický_výraz
if
  příkazy_1_větve
then

Příklady použití podmínek budou uvedeny v následujících částech tohoto seriálu.

5. Počítané cykly

Forth patří mezi jazyky nižší úrovně; tyto jazyky jsou mimo jiné charakteristické častým používáním počítaných a nepočítaných cyklů. U jazyků vyšší úrovně, zejména jazyků funkcionálních, se spíše setkáváme s použitím rekurze a konstrukcí typu foreach (tj. skrytých smyček).

Jedním ze základních typů cyklů ve Forthu je smyčka typu do-loop. Jedná se o počítanou smyčku, která zhruba odpovídá smyčce for z Pascalu, Fortranu či Basicu. Podobnost klíčových slov pro smyčku do-loop ve Forthu a C-čku svádí k jejich záměně, v C-čku se ale jedná o nepočítanou smyčku s podmínkou, která se hodí pro poněkud jiné operace než její forthovská příbuzná.

Inicializace smyčky do-loop je jednoduchá – na zásobník operandů se nejprve uloží dvě hodnoty. První hodnotou se specifikuje počet opakování smyčky, druhou (tj. tou, která je uloženou na vrcholu zásobníku) pak počáteční hodnota.

Příkazy, které se mají ve smyčce opakovat, jsou umístěny uvnitř „příkazových závorek“ specifikovaných slovy do a loop. Smyčka probíhá tak, že se aktuální hodnota počitadla ukládá na zásobník návratových adres (return stack), na konci smyčky je pak tato hodnota přesunuta na zásobník operandů, kde je počitadlo porovnáno s koncovou hodnotou. Z toho vyplývá, že smyčka proběhne alespoň jednou, podobně jako smyčka typu do-while v céčku nebo repeat-until v Pascalu.

Nejjednodušší forma smyčky do-loop, která se má opakovat desetkrát, vypadá následovně:

10 1 do loop

Jak je z předchozího úryvku kódu patrné, bude se smyčka provádět desetkrát, přičemž první hodnota počitadla bude rovna jednotce.

Uvnitř smyčky je možné používat speciální klíčové slovo i, pomocí kterého se na zásobník operandů uloží aktuální hodnota počitadla smyčky. Pokud by tedy měla smyčka proběhnout desetkrát a postupně vypisovat hodnotu počitadla, může celý kód vypadat následovně:

: smycka1
    10 1 do
        i . cr
    loop
;

Jak je z předchozího programu patrné, vytvořili jsme nové slovo smycka1, po jehož zavolání se smyčka desetkrát provede a vypíše všechny hodnoty počitadla. Připomínám, že slovo . (tečka) slouží k vypsání hodnoty uložené na vrcholu zásobníku a slovo cr provede přechod na nový řádek.

Výše vytvořené slovo smycka1 však není příliš flexibilní, výhodnější by bylo vytvořit slovo, které provede smyčku n-krát s různou počáteční hodnotou. To je možné provést jednoduchou úpravou kódu:

: smycka2
    do
        i . cr
    loop
;

Před provedením nově vytvořeného slova smycka2 je nutné na zásobník vložit počet opakování smyčky a počáteční hodnotu. Celé volání může vypadat například takto:

10 1 smycka2

Všimněte si velké jednoduchosti vytvoření nového slova a způsobu „předávání parametrů“ přes zásobník. Nikde není zapotřebí pojmenovávat parametry, vytvářet lokální proměnné ani používat závorky. Tento způsob předávání parametrů pracuje samozřejmě pouze v případě, že se využívají čísla typu integer. V případě použití jiných datových typů (například reálných čísel) je nutné pracovat se zásobníkem nepřímo pomocí slov pro zpracování dalších datových typů.

Místo slova do je možné použít i slovo ?do, při jehož vyvolání se nejprve provede test, zda se nerovná hodnota indexu a počáteční hodnoty. Pokud dojte k rovnosti, smyčka se neprovede a běh programu pokračuje až za slovem loop. Následující dva řádky tedy budou mít zcela odlišný efekt:

10 10 do i . cr loop
10 10 ?do i . cr loop

Poznámka: některé interpretery Forthu (například Atlast) nepovolí výše uvedené smyčky použít v příkazu zapsaném na příkazovou řádku mimo definici slova. V takovém případě je nutné smyčky uzavřít do jednoduchých slov a tato slova následně vyvolat, např.:

: test1 10 10 do i . cr loop ;
: test2 10 10 ?do i . cr loop ;
test1 \ nutno ukončit například klávesou
      \ Ctrl+D, Ctrl+C, Ctrl+Break
      \ - podle zvyklostí OS
test2

6. Poznámky

Poznámky lze vytvářet pomocí dvou slov. Prvním slovem je \ (zpětné lomítko), od jehož výskytu až do konce řádku je text ignorován. Toto slovo je tedy určeno pro vytváření jednořádkových poznámek:

1 2 + \ nyní sečteme dvě čísla

Druhý typ poznámek začíná slovem ( (levá závorka). Text, který je za závorkou zapsán (včetně znaků pro nový řádek), je ignorován až do výskytu pravé závorky. Příklad:

2 dup *    ( provedeme výpočet
             druhé mocniny čísla)

Vzhledem k tomu, že oba typy poznámek jsou uvozeny slovy, musí být za těmito slovy vždy alespoň jedna mezera nebo jiný bílý znak.

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

Následující část tohoto seriálu bude věnována práci s proměnnými, základním matematickým a logickým operacím, rozšířeným funkcím pro manipulaci se zásobníkem a samozřejmě bude uvedeno větší množství demonstračních příkladů.