Hlavní navigace

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

Pavel Tišnovský 22. 2. 2005

Dnešní část seriálu pojednávajícího o programovacím jazyku Forth je věnována popisu nejčastěji prováděných matematických operací, manipulaci se zásobníkem návratových adres (return stackem) a v neposlední řadě také způsobu práce s konstantními hodnotami a poli.

Obsah

1. Matematické operace
2. Manipulace se zásobníkem návratových adres
3. Rozšiřující funkce pro práci se zásobníkem operandů
4. Číselné konstanty
5. Pole konstantních hodnot
6. Pole celočíselných hodnot
7. Práce s řetězci
8. Obsah dalšího pokračování

1. Matematické operace

Již v předchozích částech tohoto seriálu jsme si popsali některé matematické operace, které lze provádět s hodnotami uloženými na zásobníku operandů. Dnes si uvedeme soupis nejpoužívanějších matematických operací spolu s jejich zásobníkovými diagramy. Připomínám, že v zásobníkovém diagramu se na jeho levé straně zobrazuje obsah zásobníku operandů před provedením operace a za dvojicí znaků obsah zásobníku operandůpo provedení popisované operace. Pro jednoduchost budu mezi matematické operace zahrnovat i některé komparativní operace. V následujícím seznamu budou názvy operací (tj. slov) uvedeny tučně, zásobníkový diagram bude vypsán neproporcionálním textem.

  1. 0<   (N1 – FLAG)
    pokud je na vrcholu zásobníku uloženo záporné číslo, vrací se na zásobník hodnota TRUE (-1), jinak FALSE (0). Původní hodnota je ze zásobníku odstraněna.
  2. 0=   (N1 – FLAG)
    pokud je na vrcholu zásobníku uložena nula, vrací se na zásobník hodnota TRUE (-1), jinak FALSE (0). Původní hodnota je ze zásobníku opět odstraněna, podobně jako při zavolání předchozího slova.
  3. 0>   (N1 – FLAG)
    pokud je na vrcholu zásobníku uloženo kladné nenulové číslo, vrací se na zásobník operandů hodnota TRUE, jinak FALSE.
  4. 0BRANCH   (N1 –)
    pokud je na vrcholu zásobníku uložena nula, provede se skok (získaný z hodnoty uvedené ihned za touto instrukcí/slovem). Tato operace je interně provedena mnohem efektivněji než porovnání a následný skok.
  5. 1+   (N1 – N2)
    přičtení jedničky k hodnotě uložené na vrcholu zásobníku. Nahrazuje slova 1 +, je však interně implementováno efektivněji, mnohdy pomocí jediné instrukce procesoru.
  6. 1-   (N1 – N2)
    odečtení jedničky od hodnoty uložené na vrcholu zásobníku. Nahrazuje slova 1 -, ale opět s efektivnější implementací.
  7. 2+   (N1 – N2)
    přičtení dvojky k hodnotě uložené na vrcholu zásobníku. Toto slovo lze použít zejména ve smyčkách pro přístup do paměti či k indexování polí.
  8. 4+   (N1 – N2)
    přičtení čtyřky k hodnotě uložené na vrcholu zásobníku. Nejčastější použití tohoto slova spočívá opět ve vytváření smyček.
  9. 2*   (N1 – N2)
    vynásobení hodnoty uložené na vrcholu zásobníku dvěma. Interně se většinou provádí pomocí bitového posuvu.
  10. 2/   (N1 – N2)
    vydělení hodnoty uložené na vrcholu zásobníku dvěma. Interně se provádí pomocí bitového či aritmetického posuvu.
  11. ?DUP   (N1 – N1 N1) nebo (N1 – N1)
    pokud je na vrcholu zásobníku uložena nenulová hodnota, provede se operace DUP. Toto slovo je velmi často používané, protože může mnohdy nahradit podmíněný příkaz.
  12. ABS   (N1 – N2)
    výpočet absolutní hodnoty čísla uloženého na vrcholu zásobníku.
  13. /MOD   (N1 N2 – N3 N4)
    současné provedení dělení a výpočtu zbytku po dělení. Po provedení operace je na vrcholu zásobníku operandů uložen výsledek dělení a na druhé pozici zbytek po dělení. Jedná se o jednu z operací, kterou lze například na procesorech Intel provést jedinou instrukcí, a je škoda, že další programovací jazyky podobnou jazykovou konstrukci neobsahují.
  14. */MOD   (N1 N2 N3 – N4 N5)
    toto je jedno z mých nejoblíbenějších slov :-). Nejprve se provede vynásobení hodnot N1 a N2 s tím, že výsledek je uložen ve dvojitém rozsahu, takže nedochází k přetečení výsledků. Posléze je hodnota vzniklá násobením vydělena hodnotou N3 a výsledek dělení je spolu se zbytkem po dělení zapsán zpět na zásobník. Tuto instrukci lze velmi jednoduše a efektivně použít například pro provádění operací s čísly reprezentovanými ve formátu pevné řádové tečky (FX-fixed point).
  15. U<   (U1 U2 – FLAG)
    porovnání dvou celých kladných čísel, která v tomto případě nejsou vyjádřena ve dvojkovém doplňku, a vrácení výsledku operace „je menší“ zpět na zásobník operandů.
  16. U>   (U1 U2 – FLAG)
    porovnání dvou celých kladných čísel, která opět nejsou vyjádřena ve dvojkovém doplňku, a vrácení výsledku operace „je větší“.
  17. U*   (N1 N2 – D3)
    vynásobení dvou celých kladných čísel a uložení výsledku na dvě pozice v zásobníku (výsledek má dvojitý rozsah, typicky 0..232-1).
  18. U/MOD   (D1 N2 – N3 N4)
    celočíselné dělení s vrácením výsledku dělení v N3 a zbytku v N4. Dělenec je uložen na dvou pozicích zásobníku ve dvojitém rozsahu, dělitel má jednoduchý rozsah.
  19. WITHIN   (N1 N2 N3 – FLAG)
    další z mých oblíbených slov. Provede se porovnání, zda hodnota N3 leží mezi hodnotami N1 a N2, tj. zda platí nerovnost N1<N3<N2. Podle výsledku porovnání se na zásobník operandů uloží buď hodnota TRUE, neboFALSE. Pokud toto slovo není v nějaké implementaci Forthu přítomno, může se jednoduše dodefinovat:
    : WITHIN OVER – >R – R> U< ;

2. Manipulace se zásobníkem návratových adres

Doposud jsme si ukazovali operace, které lze provádět se zásobníkem operandů. Druhý forthovský zásobník, tj. zásobník návratových adres, jsme poněkud opomíjeli. To mělo své důvody, protože tento zásobník je používán zejména pro uložení návratových adres slov (jak již naznačuje jeho název) a jakákoli „nerovnováha“ zde uložených hodnot může mít pro běžící program fatální následky.

Na druhou stranu se však často vyskytují situace, kdy je zapotřebí nějakou hodnotu odložit ze zásobníku operandů pro pozdější použití. K tomu účelu je možné použít buď proměnné (což je neefektivní a ve Forthu prakticky nepoužívané řešení) nebo právě zásobník návratových adres (viz předchozí deklaraci slova WITHIN). Pro práci s hodnotami uloženými na zásobníku návratových adres jsou určena následující slova:

  1. >R   (N – )
    přenesení hodnoty ze zásobníku operandů na zásobník návratových adres.
  2. R>   ( – N)
    přenesení hodnoty ze zásobníku návratových adres na zásobník operandů.
  3. R@   ( – N)
    kopie hodnoty ze zásobníku návratových adres na zásobník operandů.
  4. 2>R   (D – )
    přenesení hodnot ze dvou pozic zásobníku operandů na dvě pozice v zásobníku návratových adres.
  5. 2R>   ( – D)
    přenesení hodnot ze dvou pozic na zásobníku návratových adres na zásobník operandů.
  6. 2R@   ( – D)
    kopie dvou hodnot ze zásobníku návratových adres.

Je samozřejmě možné přímo ze zásobníku návratových adres vyčíst návratovou adresu volajícího slova a dále ji různým způsobem upravovat, či na něj naopak vložit nějakou adresu, na kterou program při návratu z aktuálně prováděného slova skočí. Tento způsob programování však již vyžaduje pokročilé znalosti interních struktur Forthu, zejména implementace slovníku a adresové aritmetiky.

3. Rozšiřující funkce pro práci se zásobníkem operandů

Ve většině implementací Forthu jsou k dispozici následující operace (slova), které pracují s hodnotami uloženými na zásobníku operandů. Tato slova jsou určena zejména pro práci s celočíselnými hodnotami s rozsahem dvojitým oproti rozsahu základních celočíselných hodnot. Z toho důvodu je každá hodnota s dvojitým rozsahem rozložena na zásobníku do dvou položek. Tradiční Forthy pracují s šestnáctibitovými hodnotami, to znamená, že čísla s dvojitým rozsahem mají délku 32 bitů (včetně znaménka, protože formát uložení je ve dvojkovém doplňku). Pro tato čísla jsou k dispozici následující operace:

  1. 2DROP (někdy také označeno jako DDROP) – tato operace odstraní ze zásobníku operandů jednu hodnotu uloženou ve dvojitém rozsahu. Ve skutečnosti se tedy dvakrát provede slovo DROP. Zásobníkový diagram této operace je (D1 – ), kde D1 značí hodnotu ve dvojitém rozsahu.
  2. 2DUP (někdy také DDUP) – tato operace duplikuje na zásobníku operandů hodnotu uloženou ve dvojitém rozsahu. Tuto operaci lze naprogramovat s využitím slov OVER. Její zásobníkový diagram lze zapsat následovně: (D1 – D1 D1).
  3. 2NEGATE (někdy také DNEGATE) – pomocí této operace se vyčíslí dvojkový doplněk hodnoty uložené na vrcholu zásobníku ve dvojitém rozsahu. Zásobníkový diagram: (D1 – D2).
  4. 2SWAP (někdy také DSWAP) – prohození dvou hodnot uložených ve dvojitém rozsahu. Zásobníkový diagram tohoto slova lze zapsat: (D1 D2 – D2 D1). Toto slovo lze samozřejmě využít i při práci s čísly v jednoduchém rozsahu:
    1 2 3 4 2SWAP . . . . cr
  5. D+ – součet dvou hodnot uložených ve dvojitém rozsahu a uložení výsledku operace zpět na zásobník. Tuto operaci lze popsat zásobníkovým diagramem (D1 D2 – D3).
  6. D! – uložení číselné hodnoty ve dvojité přesnosti ze zásobníku operandů do paměti. Zásobníkový diagram: (D1 ADDR – ).
  7. D@ – načtení číselné hodnoty ve dvojité přesnosti z paměti do zásobníku operandů. Zásobníkový diagram: (ADDR – D1).
  8. D< – porovnání dvou čísel uložených ve dvojité přesnosti.
  9. D> – porovnání dvou čísel uložených ve dvojité přesnosti.
  10. D>S – převod čísla uloženého ve formátu dvojité přesnosti na číslo uložené v jednoduché přesnosti.
  11. DMIN – vyjme ze zásobníku dvě čísla ve dvojitém rozsahu a uloží zpět na zásobník číslo s menší hodnotou. Toto slovo lze naprogramovat následovně:
    : DMIN ( d1 d2 – d1 | d2) 2OVER 2OVER D< NOT IF 2SWAP THEN 2DROP ;
  12. DMAX – opak předchozího slova: vyjme ze zásobníku dvě čísla ve dvojitém rozsahu a uloží zpět na zásobník číslo s větší hodnotou. Vytvoření tohoto slova je opět jednoduché:
    : DMAX ( d1 d2 – d1 | d2) 2OVER 2OVER D< IF 2SWAP THEN 2DROP ;

Dále jsou k dispozici slova TUCK se zásobníkovým diagramem (N1 N2 – N2 N1 N2), NIP s diagramem (N1 N2 – N2) a -ROT s diagramem (N1 N2 N3 – N3 N1 N2), která doplňují repertoár slov pro manipulaci s obsahem zásobníku operandů po jednotlivých položkách: celkově je tedy možné používat slovaDUP, SWAP, OVER, ROT, -ROT, DROP, TUCK a NIP (to se krásně rýmuje).

4. Číselné konstanty

Číselné konstanty (tj. neměnné hodnoty jednoduchého rozsahu) se vytvářejí velmi jednoduše pomocí slova constant následující konstrukcí:

hodnota constant jméno_konstanty

například:

1048576 constant megabyte

Hodnota však nemusí být nutně vyjádřena pouze číslem, je možné použít i složitější výraz:

1024 1024 * constant megabyte

Podobně jako ve všech programovacích jazycích zvyšuje použití konstant čitelnost i modifikovatelnost vytvářených programů. Podle platformy, na které Forth běží, mohou mít číselné konstanty rozsah 16 bitů nebo 32 bitů (viz předchozí příklad). V každém případě je však konstanta uložena v jedné buňce (cell).

5. Pole konstantních hodnot

V mnoha případech je nutné pracovat s konstantami, které jsou uloženy do pole. Může se jednat například o pole, v němž jsou uloženy kódy barev, počty dnů v jednotlivých měsících apod. Pro tyto účely Forth umožňuje vytváření polí konstantních hodnot, jejichž položky se velmi snadno zapisují pomocí slova CREATE a , (čárka). Vytvoření pole s konstantami vypadá následovně:

create název_pole hodnota1 , hodnota2 , hodnota3 ,

Při zápisu si musíme uvědomit, že , (čárka) je slovo, nemá tedy žádný jiný význam. Z toho důvodu je nutné mezi čárku a hodnotu vložit alespoň jeden bílý znak, typicky mezeru. Vytvoření pole konstant může v praxi vypadat například následovně:

create pole 10 , 20 , 30 , 35 , 100 ,

Prvky se z pole konstant čtou pomocí následující konstrukce:

název_pole index cells + @

Vysvětlení této konstrukce bude uvedeno v následující kapitole.

6. Pole celočíselných hodnot

Pole celočíselných hodnot je velmi často používaná datová struktura. Forth se od ostatních programovacích jazyků odlišuje zejména způsobem přístupu k jednotlivým prvkům pole. Ostatní jazyky používají indexaci, kdy je v kulatých či hranatých závorkách zapsána hodnota specifikující pořadí čteného či zapisovaného prvku. Forth se chová podobně jako C-čko, protože povoluje přístup k jednotlivým prvkům přes jejich adresu, která je získána součtem počáteční adresy pole a indexu prvku pole.

Pole lze ve Forthu vytvořit následujícím způsobem:

create název_pole počet_prvků cells allot

Slovo CELLS převádí číselnou hodnotu uloženou na zásobníku na hodnotu reprezentující počet adresovatelných buněk paměti (bytů), což typicky znamená vynásobení uložené hodnoty dvěma nebo čtyřmi, podle použité architektury počítače. Pomocí tohoto slova lze obejít závislost vytvářeného programu na použitém procesoru, v mnohém se tedy podobá C-čkovské konstrukci sizeof(int) nebo sizeof(void *). Slovo ALLOT provede alokaci požadovaného počtu buněk, jde tedy o obdobu funkcemalloc().

Zápis hodnoty do pole je možné provést následujícím příkazem:

hodnota název_pole index cells + !

Uvedený zápis sice na první pohled vypadá složitě, jeho stavba je však naprosto logická. Nejprve se na zásobník uloží hodnota, která se má posléze zapsat do pole. Potom se na zásobník uloží adresa počátku pole a index prvku, na který se má provést zápis. Tento index je převeden na počet bytů a sečten s adresou začátku pole. Nyní je tedy na zásobníku uložena pouze hodnota a adresa. Vlastní zápis se provede pomocí nám již známého slova ! (store). Toť vše, kromě odlišného zápisu se provádí naprosto stejná operace jako v jiných programovacích jazycích, ovšem s tím rozdílem, že ve Forthu je nutné násobit index velikostí adresovatelné buň­ky.

Čtení hodnoty z pole se provádí obdobným způsobem jako zápis:

název_pole index cells + @

Po provedení výše uvedeného kódu se na zásobník operandů uloží hodnota z vybraného prvku pole.

Pro ilustraci si můžeme uvést konkrétní příklad:

create pole 20 cells allot
10 pole 5 cells + !
pole 5 cells + @
. cr

7. Práce s řetězci

Manipulace s řetězci dnes patří mezi základní operace, které by měl každý programovací jazyk zvládat. Forth samozřejmě není výjimkou, je však nutné přiznat, že podpora práce s řetězci je ve Forthu dosti těžkopádná a v žádném případě nesnese srovnání například s Basicem či dokonce Perlem. Řetězce jsou ve Forthu používány podobně jako v klasickém Pascalu – jedná se o pole jednobytových položek, kde první položka obsahuje délku řetězce. Z toho také vyplývá, že maximální počet znaků, které lze do jednoho řetězce uložit, je 255 (28-1=255), toto pole má tedy maximální velikost 256 bytů.

To sice může z dnešního hlediska vypadat naprosto nedostatečně, Forth však nikdy nebyl určen pro aplikace, ve kterých se hromadně pracuje s texty – to ostatně cílové platformy (jednočipy, řídicí systémy apod.) ani neumožňují. Samozřejmě existují rozšíření, kde se s textem (resp. s řetězci) dá pracovat podobně jako v C-čku, ve Forthu přidání takového rozšíření znamená pouze vytvoření několika vhodně naprogramovaných slov. Více informací o práci s textem si uvedeme až v navazujícím pokračování tohoto seriálu.

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

V následující části tohoto seriálu si probereme nejčastěji prováděné operace s řetězci a také se začneme zabývat vstupně-výstupními operacemi.

Našli jste v článku chybu?

12. 9. 2008 21:38

MikRom (neregistrovaný)
Niekde som nasiel imformaciu, ze
WITHIN ( u1 u2 u3 −− flag ) je True ak u3 − u2 > u1 − u2, inac je False

12. 9. 2008 17:45

MikRom (neregistrovaný)
Ten WITHIN mi nejak neleze do hlavy:
3 6 5 WITHIN
dava vysledok -1 (t.j. True, pretoze plati 3 < 5 < 6. To je ok. Ale preco
5 3 6 WITHIN
dava takisto vysledok -1 (t.j. True), ked by to malo byt 0 (t.j. False), pretoze predsa neplati 5 < 6 < 3 ?! Takze
a b x WITHIN
zrejme dava nieco ineho, nie len pravdivostnu hodnotu a < x < b. Aby sa to spravalo jak ma, mala by definicia vyzerat asi takto:
: WITHIN?
( a b x -- f )
\ f je pravdivostna hodnota nerovnosti a < x &…
Lupa.cz: Levný tarif pro Brno nebude. Radní: je to kartel

Levný tarif pro Brno nebude. Radní: je to kartel

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Měšec.cz: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?