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

Obsah

1. Základy práce s řetězci
2. Vytvoření a inicializace řetězce
3. Výpis jednoho znaku
4. Výpis celého řetězce
5. Další slova určená pro manipulaci s řetězci
6. Obsah dalšího pokračování

1. Základy práce s řetězci

From the standpoint of programming methodology, the advantage to the Forth approach is that new words and new syntaxes can easily be added. Forth cannot be said to be „looking“ for words – it finds words and executes them. If you add new words Forth will find and execute them as well. There's no difference between existing words and words that you add.
What's more, this „extensibility“ applies to all types of words, not just action-type functions. For instance, Forth allows you to add new compiling words „like“ IF and THEN that provide structured control flow. You can easily add a case statement or a multiple-exit loop if you need them, or, just as importantly, take them out if you don't need them.
Leo Brodie, Thinking Forth

Práce s řetězci znaků je ve Forthu poněkud těžkopádnější než v jiných programovacích jazycích, protože programátor musí ve své režii zajistit veškeré alokace paměti, inicializace řetězců, kontrolu délky řetězců při jejich naplňování i čtení apod. V tomto aspektu se Forth do jisté míry podobá C-čku, které také žádnou výraznější podporu pro práci s řetězci neobsahuje (samozřejmě kromě možnosti inicializace pole bytů konstantním řetězcem a používání konstantních řetězců ve výrazech a příkazech). Pomocí vhodně naprogramovaných slov je však možné s řetězci pracovat i ve Forthu poměrně rozumným a přehledným způsobem.

Nejprve si řekněme, jakým způsobem jsou řetězce ve Forthu reprezentovány, tj. jaký je jejich obraz v operační paměti počítače. Nejedná se o nic jiného než o pole znaků, kde je každý znak uložen na jednom byte. Vzhledem k tomu, že u řetězce je při mnoha manipulacích zapotřebí znát i jeho délku, je první byte v poli rezervován právě pro uložení délky řetězce. Z toho mimo jiné vyplývá, že maximální počet znaků v řetězci je roven 255 (2⁸-1). Tento způsob úschovy řetězce v operační paměti, který je mimo jiné použit i u standardního programovacího jazyka Pascal, je nevýhodný především nemožností úschovy delších textů. Na druhou stranu je možné explicitní znalost délky řetězce použít v různých smyčkách, které manipulují s jednotlivými zna­ky.

Je však samozřejmě možné vytvořit nová slova, pomocí kterých se s řetězci pracuje podobně jako v C-čku, tj. jednalo by se o nulou ukončené řetězce (ve starší literatuře označované také jako ASCIIZ). Také je možné provést rozšíření z původní osmibitové znakové sady na znaky reprezentované v Unicode apod. Zde se projevuje významná vlastnost Forthu: přidání těchto nových jazykových konstrukcí není spojeno se změnou v samotném jazyku (viz motto na začátku této kapitoly). To v jiných jazycích není možné – i když se například v C-čku vytvoří funkce pro práci s jinak ukládanými řetězci, není pro takto vytvořené řetězce možné použít stávající jazykové konstrukce, například konstantní řetězce.

V dalším textu se budu zabývat především prací s původními forthovskými řetězci, tj. poli o maximálně 256 bytech, kde v prvním byte je uložena velikost pole (délka řetězce).

2. Vytvoření a inicializace řetězce

An artist's paintbrush doesn't notify the artist of a mistake; the painter will be the judge of that. The chef's skillet and the composer's piano remain simple and yielding. Why let a programming language try to out think you?
Leo Brodie, Thinking Forth 

Prvním úkolem před jakoukoli další manipulací s řetězci je alokace paměti, do které se bude řetězec ukládat. Pro alokaci paměti už známe potřebná slova: CREATE a ALLOT. Při alokaci paměti je nutné udat počet alokovaných byte. Výpočet paměti, kterou je nutné alokovat pro jeden znak, zajistí slovo CHARS, které tvoří analogii s již dříve popsaným slovem CELLS. Ve většině případů toto slovo neprovádí žádnou činnost (tj. ponechá na zásobníku původní hodnotu), protože znak je uložen na jednom byte. Z tohoto důvodu může definice slovaCHARS vypadat velmi triviálně:

: chars ;

Vytvoření slova pro alokaci paměti pro řetězec se tedy provede pomocí následující sekvence, která kopíruje známou sekvenci slov pro vytvoření pole:

create jméno_řetězce délka_řetězce chars allot

například:

create pozdrav 10 chars allot

Jak je z výše uvedeného kódu patrné, je vytvoření řetězce a pole prováděno naprosto stejným způsobem, pouze se liší slova pro výpočet alokovaného místa (původní slovo CELLS je nahrazeno slovem CHARS).

Inicializace řetězce, tj. vlastní zápis textu do řetězce, je poněkud obtížnější, protože některé implementace Forthu pro tuto činnost neposkytují potřebné slovo. Dokonce ani ANS-Forth (tj. prakticky oficiální standard Forthu) žádným podobným slovem neoplývá. Toto slovo, které se již tradičně a výstižně nazývá PLACE, je možné vytvořit například následujícím způsobem (pokud již slovo se stejným jménem existuje, bude novou definicí „překryto“, to vyplývá ze způsobu procházení slovníkem, který jsme si taktéž uvedli v předchozích částech tohoto seriálu):

: place over over >r >r char+ swap chars cmove r> r> c! ;

Za zmínku stojí použité slovo CMOVE, pomocí kterého je možné přenášet bloky paměti. S tímto užitečným slovem se několikrát setkáme i v dalším textu. Prozatím se tedy nebudeme ani podrobněji zabývat parametry, které toto slovo vyžaduje; ty lze ostatně z výše uvedeného kódu velmi přesně odhadnout, připomenu jen, že pomocí slov >r a r> lze přesouvat hodnoty mezi zásobníkem operandů a zásobníkem návratových adres.

Pokud tedy máme ve slovníku uložené slovo PLACE, je možné řetězec inicializovat řetězcovou konstantou (ta začíná slovem S", které na zásobník operandů uloží počáteční adresu řetězcové konstanty), což neznačí nic jiného než kopii konstantního řetězce na adresu reprezentující začátek námi vytvořeného řetězce:

create pozdrav 10 chars allot
s" Hello! " pozdrav place

Při inicializaci řetězce se neprovádí žádné kontroly na překročení mezí předem alokovaného pole. Pokud by se například řetězec pozdrav inicializoval hodnotou „Hello world!“, došlo by k přemazání další oblasti paměti, která již do řetězce nepatří. Ve většině situací tato chyba nekončí přepsáním kódu (ten je uložen na relativně bezpečném místě – ve slovníku), ale modifikací nějakého jiného řetězce, popř. jiného pole.

3. Výpis jednoho znaku

Ještě předtím, než si ukážeme slovo pro výpis řetězce, se musím krátce zmínit o velmi důležitém slovu EMIT. Toto slovo, které tvoří základ prakticky všech výstupních operací, je používáno pro výpis jednoho znaku, jeho účinek tedy odpovídá C-čkovským funkcím putc() a putchar(). Při vyvolání slova EMIT se musí na zásobníku operandů nacházet číselný kód znaku – prakticky vždy jde o ASCII kód, avšak při použití nějaké značně specifické architektury se kódy znaků mohou lišit.

Použití slova EMIT v programech je velmi jednoduché. Ukažme si výpis znaku ‚A‘, který má v ASCII znakové sadě číselný kód 65:

65 emit

Již v předchozích částech tohoto seriálu jsme používali slovo CR, které provádí odřádkování, tj. přesun textového kurzoru na nový řádek. Toto slovo může být – a mnohdy také je – definováno následovně (v ASCII sadě je pozice 10 rezervována pro znak konce řádku):

: cr 10 emit ;

Ve Forthu dále existuje konstanta (resp. slovo ukládající na zásobník operandů konstantu) BL, kterou je reprezentován prázdný znak (blank), mezera je totiž jiným způsobem (například řetězcovou konstantou) složitě zapisovatelná. Toto slovo může být vytvořeno například následujícím způsobem:

: bl 32 ;

protože kód mezery je v ASCII roven právě třiceti dvěma. S pomocí tohoto slova lze vytvořit nové slovo SPACE, které mezeru vytiskne:

: space bl emit ;

Z tohoto slova lze dále odvodit slovo SPACES, které vytiskne několik mezer. Počet mezer je uložen na vrcholu zásobníku operandů. Pokud toto slovo není v původním slovníku Forthu obsaženo, je možné ho velmi jednoduše doplnit:

: spaces 0 do space loop ;

Toto slovo předpokládá, že počet opakování pro smyčku DO-LOOP je zadán na vrcholu zásobníku operandů (před začátkem smyčky je ještě vhodné otestovat uložené číslo, aby byla zaručena jeho kladná hodnota, případnou úpravu slova ponechám na čtenáři). Použití slova SPACES je triviální:

10 spaces

Nyní již máme dostatek informací k tomu, abychom se mohli zabývat způsobem tisku celých řetězců na obrazovku nebo na jiné výstupní zařízení.

4. Výpis celého řetězce

Forth has often been characterized as offbeat, totally unlike any other popular language in structure or in philosophy, On the contrary, Forth incorporates many principles now boasted by the most contemporary languages. Structured design, modularity, and information-hiding are among the buzzwords of the day.
Leo Brodie, Thinking Forth 

Výpis řetězce se dá provést například následujícím způsobem: řetězec se postupně ve smyčce prochází, přičemž se každý znak řetězce (resp. jeho ASCII kód) uloží na zásobník operandů a zavolá se slovo EMIT, které daný znak vytiskne. Před procházením se musí zjistit délka řetězce, to zajišťuje slovo COUNT, které je součástí ANS-Forthu. Toto slovo má jedinou nevýhodu – ponechává na zásobníku operandů délku řetězce. Proto si nadefinujeme slovo LENGTH$ (návrat k Basicu :-), ale označování slov pro práci s řetězci dolarem je běžné i ve Forthu), které po zavolání ponechá na zásobníku pouze jedno číslo odpovídající délce řetězce:

: length$ count swap drop ;

Pro ladění si ještě vytvoříme slovo PRINTLEN$ pro přímý výpis délky řetězce:

: printlen$ length$ . cr ;

S využitím výše uvedených slov již můžeme vytvořit nové slovo, které řetězec vytiskne na obrazovku. Toto slovo, které se ve Forthu nazývá TYPE, můžeme zapsat například následujícím způsobem:

: type
    ?dup
    if over + swap
        do
            i
            c@
            emit
        loop
    else
        drop
    then
;

Před zavoláním slova TYPE musí být ve druhé buňce zásobníku operandů umístěna adresa počátku řetězce a na vrcholu zásobníku musí být uložen počet znaků, který se má vypsat. Jediné neznámé slovo je c@, které slouží k přečtení jednoho znaku z paměti (adresa paměťového místa je získána pomocí slova I) a uložení přečtené hodnoty na zásobník (s případnou konverzí kódu znaku na celé číslo). Na tomto slovu je také názorně vidět, že jako hodnoty počitadla smyčky DO-LOOP mohou bez problémů vystupovat adresy. Slovo TYPE si můžeme ihned odzkoušet na jednoduchém prográmku:

s" Hello world!"
type

Pro jistotu ještě uvedu celý program, který nejprve vytvoří řetězec, uloží do něj text, a tento text posléze vypíše. Uvedený program by měl pracovat prakticky ve všech implementacích Forthu, tedy i v těch, které neobsahují žádná slova pro práci s řetězci (kromě CMOVE a EMIT):

: chars ;          ( některé Forthy toto slovo neznají )
: place over over >r >r char+ swap chars cmove r> r> c! ;
: type ?dup if over + swap do i c@ emit loop else drop then ;
: cr 10 emit ;     ( pro ne-ASCII platformy nutno změnit )

create pozdrav 20 chars allot
s" Hello world! " pozdrav place
pozdrav count type cr

5. Další slova určená pro manipulaci s řetězci

Software development in Forth seeks first to find the simplest solution to a given problem. This is done by implementing selected parts of the problem separately and by ignoring as many constraints as possible. Then one or a few constraints are imposed and the program is modified.
Kim Harris, The Forth Philosophy, Dr. Dobb's Journal. 

Pro kopii řetězců (a nejenom jich) se používá velmi důležité slovo CMOVE. Toto slovo provádí přesun bloku paměti, a vzhledem k tomu, že se jedná o činnost, která má trvat co nejkratší dobu, je toto slovo většinou vytvořeno v inline assembleru s optimalizací na použitý procesor. Slovo CMOVE vyžaduje před svým zavoláním následující strukturu uloženou na zásobníku operandů: (zdroj cíl počet_znaků), přičemž počet znaků většinou odpovídá počtu bytů.

Toto slovo je sice možné přímo použít pro kopie celých řetězců, ale problém nastává se správným umístěním všech hodnot na zásobník, zejména s výpočtem počtu kopírovaných znaků a s posunem adres počátků řetězců. Z tohoto důvodu je pro provádění kopií řetězců mnohem výhodnější následující slovo COPY$, které nejprve provede přípravu a uložení všech potřebných parametrů a posléze zavolá slovo CMOVE:

: copy$
    swap dup count 1+
    swap drop rot swap
    cmove
;

Použití slova COPY$ je velmi jednoduché, jak ukazuje následující příklad:

create prvni 10 chars allot
create druhy 10 chars allot
s" Hello!" prvni place

prvni druhy copy$

prvni count type cr
druhy count type cr

Pro zopakování významu slov operujících se zásobníkem si na zásobníkovém diagramu ukážeme, jakým způsobem je slovo COPY$ interpretováno v sekvenci prvni druhy copy$:

swap    ( prvni druhy -- druhy prvni )
dup     ( druhy prvni -- druhy prvni prvni )
count   ( druhy prvni prvni -- druhy prvni prvni delka )
1+      ( druhy prvni prvni delka -- druhy prvni prvni delka+1 )
swap    ( druhy prvni prvni delka+1 -- druhy prvni delka+1 prvni )
drop    ( druhy prvni delka+1 prvni -- druhy prvni delka+1 )
rot     ( druhy prvni delka+1 -- prvni delka+1 druhy )
swap    ( prvni delka+1 druhy -- prvni druhy delka+1 )
cmove   ( prvni druhy delka+1 -- )

Ve Forthu je samozřejmě možné pracovat i s řetězci ve stylu jazyka C, tj. s poli znaků, která jsou ukončena nulou. Tyto řetězce mohou mít prakticky neomezenou délku, jejich nevýhodou je fakt, že při manipulacích s nimi se musí jejich délka zjišťovat postupným průchodem, což je mnohdy značně pomalé, zejména na moderních architekturách procesorů, které provádějí přístupy do paměti po jednotlivých bytech poměrně neefektivním způsobem.

Alokace řetězců ve stylu C-čka se provádí prakticky stejným způsobem, jako tomu bylo v případě forthovských řetězců. Jediný rozdíl nastane při inicializaci řetězce, kdy je zapotřebí vytvořit nové slovo PLACE$, které řetězec správně ukončí nulou. Jako příklad práce s řetězci ukončenými nulou si uvedeme slovo STRLEN, které vrací délku řetězce, podobně jako C-čkovská funkce strlen():

: strlen ( adresa -- délka )
    0
    begin
        over c@ 0= dup not if
            -rot 1+ swap 1+ swap rot
        then
    until
    nip
;

(u některých verzí Forthu je nutné dodefinovat slova NIP a-ROT – jejich význam při práci se zásobníkem operandů jsme si uvedli v předchozí části tohoto seriálu).

Jak je z předchozích kapitol patrné, nepatří práce s řetězci (a s texty obecně) ve Forthu k příjemným a jednoduchým činnostem. To je zčásti způsobeno jak syntaktickou odlišností samotného Forthu, tak i neexistencí potřebných slov v normě ANS-Forth. Uživatel je v mnoha případech nucen vytvořit si vlastní sadu potřebných slov (typicky PLACE, TYPE, SLICE, APPEND atd.) nebo použít některou z četných knihoven, které pro práci s řetězci ve Forthu existují (v kForthu je to například knihovna strings.4th).

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

V dalším pokračování tohoto seriálu si uvedeme funkce pro přístup k informacím, které jsou uloženy v externích souborech. Řeč tedy bude o klasických vstupně-výstupních operacích, které však jsou ve Forthu implementovány poněkud odlišným způsobem, než je tomu v jiných programovacích jazycích.