Hlavní navigace

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

Pavel Tišnovský

V dnešní části seriálu pojednávajícího o programovacím jazyku Forth se budeme věnovat způsobům manipulace s proměnnými, logickým operátorům a operacím, relačním operátorům a v neposlední řadě také výstavbě složitějších algoritmů pomocí rekurze a programových smyček.

Obsah

1. Práce s proměnnými
    1.1 Vytvoření proměnné
    1.2 Uložení hodnoty do proměnné

    1.3 Získání hodnoty z proměnné
    1.4 Tisk hodnoty proměnné
2. Logické hodnoty a logické operace
    2.1 Unární a binární logické operace
    2.2 Pravdivostní tabulky binárních logických operací

3. Relační operátory
4. Rekurze
5. Nepočítané smyčky
    5.1 Smyčky s testem na začátku
    5.2 Smyčky s testem na konci
    5.3 Nekonečné smyčky

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

1. Práce s proměnnými

The only problem we Forthers have is that each time someone tells us he has found something new, we answer: „Oh, I know three guys, none of them has a CS degree, and each one invented this independently 10 years ago, but they had a much better approach than you“. He'll hate you for that.
Bernd Paysan

Programovací jazyk Forth podporuje, podobně jako prakticky všechny ostatní programovací jazyky, práci s proměnnými, které však mají poněkud odlišný význam od jiných programovacích jazyků. Ve Forthu se totiž proměnné používají převážně k relativně trvalému uložení výsledků výpočtů; pro vlastní výpočty, řízení výpočtů a uložení mezivýsledků se používá zásobník operandů a zásobník návratových adres. Nutnost použití proměnných pro uložení výsledků mezivýpočtů ve Forthu prakticky vždy ukazuje na špatně navržený program.

V dalších odstavcích si popíšeme všechny základní činnosti prováděné s proměnnými, tj. jejich vytvoření v operační paměti (deklaraci), uložení hodnoty do proměnné, zpětné získání uložené hodnoty a také tisk aktuální hodnoty proměnné na standardní výstup. Pro všechny tyto činnosti není zapotřebí vytvářet specializované jazykové konstrukce, vystačíme si pouze s prostředky, jakými jsou slovník (dictionary) a slova v něm uložená (words).

1.1 Vytvoření proměnné

Pro deklaraci číselné proměnné se používá slovo variable, po němž následuje jméno proměnné. Jelikož je jméno proměnné taktéž považováno za slovo, nemělo by kolidovat s žádným jiným jménem, jinak by došlo k jejich „zastínění“. Příklad deklarace dvou proměnných nazvaných one a two:

variable one
variable two

Při běhu programu se jméno proměnné vždy nahradí adresou, na které je uložena hodnota proměnné.

1.2 Uložení hodnoty do proměnné

Do proměnných se samozřejmě mohou ukládat hodnoty. Pro tento účel se používá slovo ! (vykřičník), které se nazývá store. Při použití slova ! musí být na druhém místě zásobníku operandů uložena hodnota, která se má do proměnné uložit, a na vrcholu zásobníku musí být adresa proměnné, tj. paměťového místa s uloženou hodnotou. Na následujícím kódu je ukázáno, jakým způsobem se do výše deklarovaných proměnných zapíše jejich hodnota:

1 one !
2 two !

Vzhledem k tomu, že hodnota pro uložení musí být umístěna na druhém místě v zásobníku operandů, je možné sloučit výpočet a přiřazení:

1 1 + two !

Pokud někomu nevyhovuje způsob psaní slova !, tj. nechce se ztratit ve změti „paznaků“, může si samozřejmě nadefinovat vlastní slovo se stejným významem a jiným jménem, například:

: store ! ;

které je možné použít následovně:

1 one store
1 1 + two store

1.3 Získání hodnoty z proměnné

Pro získání (přečtení) hodnoty proměnné a uložení na zásobník operandů se používá slovo @ (zavináč), které se čte jakofetch. Před použitím tohoto slova se musí na zásobník operandů uložit adresa proměnné reprezentovaná jejím jménem. Po provedení operace bude na vrcholu zásobníku uložena aktuální hodnota zvolené proměnné. Příklad výpisu hodnot obou výše zmíněných proměnných:

one @ . cr
two @ . cr

Slovo @ je možné opět nahradit „ukecanější“ variantou, například:

: fetch @ ;

a po přidání dalších slov print a multiply:

: print . cr ;
: multiply * ;

se již Forth prakticky stává zjednodušenou angličtinou:

variable acceleration
variable mass
variable force

10 mass store
3 acceleration store
mass fetch
acceleration fetch
multiply dup print
force store

1.4 Tisk hodnoty proměnné

Přímočarý způsob tisku hodnoty proměnné spočívá v uložení její hodnoty na zásobník s následným použitím slova . (tečka) pro tisk hodnoty uložené na vrcholu zásobníku – to jsme ostatně viděli už v předchozích příkladech. Sekvence slov tedy může pro proměnnou a vypadat následovně:

a @ .

Pro dvojici slov @ . existuje zkratka v podobě slova ? (otazník). Toto slovo nejprve uloží hodnotu proměnné na zásobník a poté tuto hodnotu vytiskne. Místo předchozí sekvence slov tedy můžeme psát pouze:

a ?

Nebo si přímo vytvořit specializované slovo print_a:

: print_a
    a ? cr
;

Použití výše vytvořených slov může být například následující (slovo factorial bude uvedeno dále):

10 factorial a ! print_a

2. Logické hodnoty a logické operace

Like most programmers, my choice of language is based on personal preference. I find that I think more clearly in Forth, and from past experience I estimate I'm 5 to 10 times more productive in Forth than in C. Others may not share this preference or facility. Forth may not be your preference, but it's certainly „relevant“ – now more than ever.
Brad Rodriguez 

Při práci s logickými hodnotami, které tvoří základ Booleovy algebry, rozlišuje Forth dvě slova: true a false. Při zadání slova true se na zásobník uloží desítková hodnota –1 (v binární podobě má toto číslo všechny bity jedničkové). Po zadání slova false se na vrchol zásobníku naopak uloží nulová hodnota (všechny bity jsou samozřejmě nastaveny na nulu).

Hodnoty obou výše zmíněných slov si můžeme jednoduchým způsobem vypsat pomocí již známého slova . (tečka):

true .
false .

2.1 Unární a binární logické operace

Forth přímo implementuje také základní unární i binární logické operace. Operandy těchto operací musí být před provedením operace uloženy na zásobníku operandů, kam je po provedení operace uložen i její výsledek. Mezi základní logické operace patří and, or,xor a unární operace not (někdy také označovaná invert).

Logické operace pracují s jednotlivými bity, ale vzhledem ke způsobu reprezentace logických hodnot není mezi bitovými a logickými operacemi prakticky žádný rozdíl (ten samozřejmě nastane při práci s jinými hodnotami než true a false).

Následuje ukázka použití logických operací:

true false and .
false not .
true not .
true true false and xor .

Programátoři znalí C-čka a z něj odvozených jazyků si mohou některé operace přejmenovat vytvořením nových slov, například následujícím způsobem:

: & and ;
: | or ;
: ^ xor ;

Operace not resp. invert je unární, tj. bere ze zásobníku pouze jeden operand a na stejné místo v zásobníku posléze vrací výsledek operace:

false .
false not .
false not not .
true .
true not .
true not not .

2.2 Pravdivostní tabulky binárních logických operací

Následuje ukázka slova pro výpis pravdivostní tabulky binárních logických operací:

: pravdivostni_tabulka
    ." Operace and" cr
    false false and . cr
    true false  and . cr
    false true  and . cr
    true true   and . cr

    ." Operace or" cr
    false false or . cr
    true false  or . cr
    false true  or . cr
    true true   or . cr

    ." Operace xor" cr
    false false xor . cr
    true false  xor . cr
    false true  xor . cr
    true true   xor . cr
;

3. Relační operátory

You define each word so that the computer knows what it means. The way it knows is that it executes some code as a consequence of being invoked. The computer takes an action on every word. It doesn't store the word away and keep it in mind for later.
In a philosophical sense I think this means that the computer „understands“ a word. It understands the word DUP, perhaps more profoundly than you do, because there's never any question in its mind what DUP means.
The connection between words that have meaning to you and words that have meaning to the computer is a profound one. The computer becomes the vehicle for communication between human being and concept.
Chuck Moore

S logickými operacemi úzce souvisí i relační operátory, které porovnávají dvě číselné hodnoty a jejichž výsledkem je logická hodnota true nebo false. Provedení relačního operátoru, který je ve Forthu opět zadán slovem, spočívá ve vyzvednutí dvou hodnot ze zásobníku, provedení operace a uložení výsledku operace zpět na vrchol zásobníku.

U relačních operátorů je nutné správně rozlišit jejich operandy, tj. který operand se nachází na levé straně a který na pravé. Obecně platí, že operand, který se v infixové notaci nachází na levé straně relačního operátoru, musí být uložen na druhém místě na zásobníku, kdežto pravý operand je umístěn na vrcholu zásobníku.

V následující ukázce kódu jsou vypsány všechny podporované relační operátory definované nad celočíselným datovým typem (výsledkem aplikace operátorů je hodnota true nebo false, ta je však při tisku zobrazena jako číslo 0 nebo –1):

1 2 <> .
1 2 = .
1 2 < .
1 2 <= .
1 2 > .
1 2 >= .

Relační operátory je samozřejmě možné použít současně s logickými operátory. V následující ukázce kódu je uveden jednoduchý test intervalu (v reálném příkladu by se samozřejmě místo hodnoty 5 použila proměnná):

1 5 < 5 100 < and .

Vzhledem ke způsobu reprezentace hodnoty slov true a false je zapotřebí mít na mysli, že ve Forthu platí vztah true<false (na rozdíl od Pascalu a podobných jazyků). Tuto vlastnost ilustruje následující příklad:

true false < . cr
true false > . cr
false true < . cr
false true > . cr

4. Rekurze

Programovací jazyk Forth již z podstaty své činnosti podporuje rekurzivní funkce. Vyplývá to z toho, že parametry „procedur“ a „funkcí“ (tj. slov) se nacházejí na zásobníku operandů a návratové adresy do nadřazených funkcí se ukládají do zásobníku návratových adres. Volání slov je ve Forthu mnohem jednodušší než v jiných programovacích jazycích, protože se nemusí složitě ukládat parametry na zásobník a vytvářet na něm takzvaný zásobníkový rámec (stack frame).

Jako příklad rekurzivní funkce uvedu známou funkci pro výpočet faktoriálu:

: factorial
    dup 0= if
        drop 1
    else
        dup 1- factorial *
    then
;

Ve výše uvedené funkci (slovu) se používá jediné nám neznámé slovo – 0=, které provádí test, zda je hodnota na vrcholu zásobníku nulová.

Při používání rekurzivních funkcí/slov je samozřejmě nutné řešený problém důkladně analyzovat a zvážit, zda pro nějaké vstupní hodnoty nebude docházet k přeplňování zásobníků.

5. Nepočítané smyčky

V předchozí části tohoto seriálu jsme si uvedli příklad počítané smyčky, kterou lze vytvořit pomocí vestavěných slov do a loop. Počítané smyčky jsou při implementaci velmi efektivní, protože pro jejich tvorbu většinou existují specializované instrukce procesoru, například DJNZ.

Ve Forthu je však možné použít i nepočítané smyčky, tj. smyčky, u nichž není předem známý počet opakování. V takové smyčce proto musí být při každé iteraci testována nějaká podmínka a na základě jejího výsledku musí být rozhodnuto, zda se má smyčka opakovat, či ukončit.

5.1 Smyčky s testem na začátku

Pro tvorbu prvního typu nepočítaných smyček, kdy se podmínka pro ukončení smyčky testuje ještě před první iterací, se používají slova begin, while a repeat. Způsob jejich použití ilustruje následující kód:

begin
podmínka
while
    tělo smyčky
repeat

Kde podmínka značí hodnotu uloženou na vrcholu zásobníku. Při každé iteraci se podmínka vyhodnotí a na základě výsledku vyhodnocení (tj. hodnoty true či false) se smyčka buď provede, nebo se z ní vyskočí. Následuje jednoduchý příklad použití, kdy vytvořený program vypíše čísla od 1 do 10:

: pokus
    0
    begin
        dup 10 <
    while
        1 +
        dup . cr
    repeat
    drop
;

5.2 Smyčky s testem na konci

Další formou nepočítané smyčky je smyčka, při které se test provádí až na konci. Tato smyčka se konstruuje pomocí slov begin a until. Způsob použití je následující:

begin
    tělo smyčky
    podmínka
until

Vzhledem k tomu, že se podmínka testuje až na konci smyčky, proběhne smyčka minimálně jedenkrát. Toho lze využít při tvorbě malých elegantních funkcí. Příkladem budiž funkce (slovo) lcd, která pomocí známého postupu vypočítá největší společný dělitel dvou čísel:

: lcd
    begin
        swap over mod
        dup 0=
    until
    drop
    . cr
;

Příklad použití výše vytvořeného slova:

10 15 lcd
20 21 lcd
384 1024 lcd

5.3 Nekonečné smyčky

V některých případech se hodí testovat podmínku na ukončení smyčky uvnitř jejího těla, tj. nikoli přísně na začátku a na konci. Pro tento typ problémů je možné použít nekonečné smyčky, které se tvoří pomocí slov begin a again. Způsob použití tohoto typu smyček je jednoduchý:

begin
    tělo smyčky
again

Příklad použití:

: infinite_loop
    begin
        ." looping" cr
    again
;

Smyčky je možné kdykoli opustit pomocí následujících slov: leave, exit a abort. Některá slova je možné použít na dříve popsané smyčky, tj. na smyčku, která podmínku testuje před první iterací i na smyčku s testem na konci (slovoleave se používá spolu se smyčkou obsahující počitadlo). Následující dvě slova ilustrují použití nekonečné smyčky s podmíněným ukončením. Při vyvolání prvního slova se vypíše číselná řada, druhé slovo vypíše hodnoty mocniny dvou:

: infinite_loop2
    0
    begin
        1 +
        dup . cr
        dup 10 > if
            abort
        then
    again
;

: infinite_loop3
    1
    begin
        2 *
        dup . cr
        dup 10000 > if
            abort
        then
    again
;

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

V následující části tohoto seriálu si popíšeme práci s poli a řetězci. Také si řekneme, jakým způsobem je možné ve Forthu pracovat s hodnotami uloženými ve formátu pohyblivé řádové čárky.

Našli jste v článku chybu?

13. 6. 2009 19:56

Funkce pro vypocet nejvetsiho spolecneho delitele se vetsinou nazyva GCD (greatest common divisor) a ne LCD. Take by byl vhodne doplnit, ze „pomocí známého postupu vypočítá největší společný dělitel“ je velmi nestastne napsano – jedna se o Eukliduv algoritmus.

9. 9. 2008 9:22

MikRom (neregistrovaný)
Standardne treba na rekurziu pouzit slovo RECURSE. Ale su vynimky: Napriklad pri pouziti kompilatoru 4tH funguje definicia faktorialu presne tak ako ju popisuje pan Tisnovsky.

Tu je priklad ako to funguje standardne:
( Rekurzia vo FORTHe )
: fac
dup 0= 
if
  drop 1
else
  \ dup 1- fac *     \ toto funguje s kompilatorom 4tH
  dup 1- recurse * \ standardny pristup: RECURSE
then
;

11 0 do
 i . ." ! = " i fac . cr
loop


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

Jak vymáhat výživné zadarmo?

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

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Lupa.cz: Brněnský radní chce zničit kartel operátorů. Uspěje?

Brněnský radní chce zničit kartel operátorů. Uspěje?

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

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

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

Recenze Westworld: zavraždit a...

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

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

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

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá