Obsah
1. Co je to zásobník?
2. Praktická implementace zásobníku
3. Základní operace nad zásobníkem
4. Abstraktní dvouzásobníkový procesor
5. Zápis matematických operací v postfixové notaci
6. Výpis hodnoty uložené na vrcholu zásobníku
7. Obsah dalšího pokračování
1. Co je to zásobník?
Zásobník (anglicky stack) je z hlediska programování a programovacích technik dynamická datová struktura, pomocí které lze podobně jako u jednosměrně či obousměrně vázaného seznamu ukládat a zpětně získávat data. Zásobník se od seznamu a dalších dynamických datových struktur, jako je fronta, strom či graf, liší především množinou základních operací určenou pro práci s touto datovou strukturou.
Datová struktura zásobník nebo její hardwarová implementace se někdy označuje akronymem LIFO, který pochází z anglického výrazu Last In – First Out. Tento výraz docela přesně vystihuje základní vlastnost zásobníku: data, která byla do zásobníku vložena nejpozději, lze nejdříve přečíst. Naopak to platí samozřejmě také: data nejdříve vložená do zásobníku lze přečíst až po vyjmutí později vložených dat. Čistě implementovaný zásobník totiž neumožňuje přímo manipulovat s daty uloženými pod jeho vrcholem.
Zásobník si můžeme znázornit i graficky spolu se dvěma základními operacemi: vložení prvku (operace push) a vyjmutí prvku spolu s navrácením jeho hodnoty (operace pop):
Princip práce s daty u zásobníku je tedy přesně opačný než u další lineární dynamické datové struktury – fronty (anglicky queue) – ze které je možné data číst pouze v tom pořadí, v jakém byla zapsána. Fronta se proto označuje akronymem FIFO, tj. First In – First Out.
Také frontu je možné znázornit graficky. Všimněte si rozdílných míst, ve kterých do fronty data vstupují pomocí operace push a vystupují z ní pomocí operace pop.
2. Praktická implementace zásobníku
Při implementaci je většinou zásobník interně v operační paměti či externí paměti uložen jako kontinuální blok hodnot. Hodnoty tak mezi sebou nejsou nijak provázány, protože už podle jejich uspořádání v paměti je jasná struktura zásobníku. Kromě toho musí existovat ještě dva ukazatele, které se používají při veškerých operacích nad zásobníkem:
- První ukazatel, který se označuje zkratkou SB (stack base). Tento ukazatel je v rámci jednoho procesu nebo vlákna konstantní a ukazuje na dno zásobníku. U mnoha mikroprocesorů a operačních systémů je vrchol zásobníku pro každý proces nastaven na maximální dostupnou adresu. Například při práci v šestnáctibitovém režimu (tj. většinou reálném režimu) mikroprocesorů Intel x86 je vrchol zásobníku umístěn na adrese 0×fffe v segmentu SS(stack segment).
- Druhý ukazatel se označuje zkratkou SP (stack pointer). Tento ukazatel ukazuje buď na první volnou pozici v zásobníku, nebo na vrchol zásobníku – konkrétní chování závisí také na konkrétní implementaci a z hlediska práce se zásobníkem není důležité. Na mnoha mikroprocesorech se hodnota vrcholu zásobníku se zaplňováním snižuje, tj. zásobník roste v paměti shora dolů (ve smyslu adres). Programátor je však od konkrétní implementace zásobníku dostatečně odstíněn programovacím jazykem, takže směr růstu zásobníku je pro něj ve většině případů nezajímavý.
Se zásobníkem lze provádět několik základních operací, které jsou popsány v následující kapitole.
3. Základní operace nad zásobníkem
V první kapitole jsem uvedl obrázek, kde je nakreslen zásobník, do nějž lze vkládat prvky pomocí operace push a tyto prvky následně vybírat pomocí operace pop. Tyto operace však nejsou pro plně definovanou abstraktní datovou strukturu dostačující, protože je nutné přidat operace, které zajišťují inicializaci zásobníku, a test, zda není zásobník prázdný (ideální zásobník nemůže být nikdy „zaplněn“, proto také příslušná testovací funkce chybí).
Také se ukazuje, že operace pop vlastně provádí dva kroky, které lze popsat dvěma jednoduššími operacemi. Nad abstraktním datovým typem zásobník je z tohoto důvodu definováno pět základních operací:
- Init – inicializace zásobníku. Po provedení této operace se zásobník vyprázdní, tj. nebude obsahovat žádná data. Při implementaci této operace bude ukazatel vrcholu zásobníku SP ukazovat na jeho dno – SB.
- Push – vložení jedné položky do zásobníku. Pokud je zásobník prázdný (tj. při implementaci platí SP=SB), vloží se nová položka na jeho dno. Pokud již zásobník obsahuje nějaké položky, vloží se nová položka na vrchol zásobníku.
- Top – tato operace vrátí hodnotu položky, která se nachází na vrcholu zásobníku. Jedná se o poslední položku vloženou operací Push. Tato operace skončí chybou v případě, že je zásobník prázdný, tj. není v něm uložena žádná hodnota.
- Drop – odstranění položky z vrcholu zásobníku. Po provedení této operace je položka, která byla naposledy vložena do zásobníku pomocí operace Push, ze zásobníku odstraněna. Tato operace skončí s chybou v případě, že je zásobník prázdný. Jak uvidíme v dalším textu (a jak jsme viděli i na prvním obrázku), operace Push aDrop se při praktické implementaci většinou slučují do jedné operace Pop, která vyjme a současně vrátí poslední položku ze zásobníku.
- Empty – dotaz, zda je zásobník prázdný, tj. zda obsahuje nějaké datové položky. Výsledkem této operace je pravdivostní hodnota true, pokud je zásobník prázdný, a false, pokud obsahuje alespoň jednu datovou položku (prvek). Při implementaci se jednoduše provádí porovnání obsahu ukazatelů SP a SB.
4. Abstraktní dvouzásobníkový procesor
Programovací jazyk Forth byl určen zejména pro implementaci na zásobníkových procesorech, přesněji řečeno na procesorech s minimálně dvěma zásobníky – zásobníkem operandů (operand stack nebo pouzestack) a zásobníkem návratových adres (return stack). Tyto procesory se od dnes nejpoužívanějších registrových procesorů liší především způsobem provádění aritmetických a logických operací.
Před popisem zásobníkových procesorů si nejprve stručně řekněme, jakým způsobem můžeme provádět aritmetické a logické operace, tj. operace, které pracují s jednou až třemi hodnotami na vstupu a s jednou hodnotou na výstupu. Jedním ze základních bloků každého procesoru je aritmeticko-logická jednotka (ALU), která vykonává veškeré aritmetické, logické a bitové operace. Na vstup této jednotky se přivádí vstupní hodnoty (vyčíslené operandy) a kód operace, která se má provést. Jednotka ALU žádanou operaci provede a její výsledek pošle na svůj výstup.
Až do této chvíle není žádný podstatný rozdíl mezi jednotlivými druhy procesorů, protože všechny ALU nabízejí v podstatě stejnou funkcionalitu, liší se pouze svým vnitřním uspořádáním, repertoárem funkcí, bitovou šířkou operandů apod. Rozdíl však nastává ve způsobu, jakým ALU získává hodnoty, se kterými má aritmetické a logické operace provádět (získávání hodnot operandů však pochopitelně není věcí ALU, ale dalších bloků procesoru).
Principiálně je možné využít dvou strategií, z čehož vycházejí i dva typy procesorů.
Registrové procesory
Registrové procesory ukládají všechny hodnoty pro provádění operací do registrů, proto musí být v každé instrukci obsažena informace, se kterými registry se má žádaná funkce provést. Tato informace je buď v instrukci obsažena implicitně (tj. instrukce se provádí vždy nad stejným registrem či registry), nebo explicitně, tj. přímo v operačním kódu instrukce.
Příkladem instrukce s implicitním určením registru je například instrukce pro součet ada dostupná u procesorů Intel 8080 či Zilog Z80. Instrukce s podobným významem má však u procesorů řady Motorola 68×xx, Intel x86 aj. explicitní určení registrů (prvně uvedený registr je současně i registrem pro uložení výsledků):
add ax, bx add cx, 10 add dx, [bp+10]
Zjednodušením registrových procesorů vznikne procesor s akumulátorem. Zjednodušení spočívá v odstranění určení prvního zdrojového a cílového operandu z kódu instrukcí s tím, že tímto operandem je vždy speciální registr nazvaný akumulátor. Příkladem takového typu procesoru je například Intel 8048.
Zásobníkové procesory
U zásobníkového procesoru je situace odlišná, protože u něj je vždy zaručeno, že se hodnoty pro provádění operací nacházejí na vrcholu zásobníku. Proto jsou operační kódy instrukcí velmi jednoduché, například:
add
Při provádění této operace je zřejmé, že se hodnoty operandů získají ze zásobníku a výsledek se taktéž uloží na zásobník. Proto je také zakódování operačního kódu této instrukce přímočaré, neboť se v něm nemusí vytvářet pole pro specifikaci operandů.
Podrobnější popis rozdílů mezi zásobníkovými procesory a registrovými procesory je uveden v knize Stack Computers: the new wave. Tato kniha je psána velmi podrobně a čtivě (samozřejmě, že v angličtině).
5. Zápis matematických operací v postfixové notaci
Forth je mezi programátory znám především jako jazyk, ve kterém se aritmetické a logické výrazy zapisují pomocí RPN – Reverse Polish Notation (obrácené polské notace) označované také jako postfixová notace. Při tomto způsobu zápisu se nejdříve uvádějí operandy a teprve poté operace, která se s těmito operandy může provádět – viz také RPN, An introduction to Reverse Polish Notation.
Už na základní škole se však každý člověk učí infixovou notaci zápisu, ve které se operátory píšou mezi operandy. Vzhledem k prioritě operátorů je však nutné v infixové notaci používat závorky. Rozdíl mezi následujícími dvěma výrazy uvedenými v infixové notaci je snad zřejmý:
a+b*c (a+b)*c
Při použití postfixové notace nejsou závorky zapotřebí, protože se priorita operací vyjadřuje přímo posloupností operátorů. Výše uvedené výrazy lze tedy do postfixové notace přepsat následovně:
a b c * + nebo též b c * a + a b + c * nebo též c a b + *
Všimněte si, že u výrazů napsaných na levé straně se oproti infixové notaci nemění pořadí operátorů.
Jaké jsou však výhody postfixového zápisu výrazů oproti zápisu infixovému? Mezi základní přednost patří absence závorek, pomocí nichž se v infixové notaci mění priority operací. Priorita je totiž v postfixové notaci velmi intuitivně určena pozicí operátoru či funkce ve výrazu.
Mezi druhou výhodu patří, možná poněkud překvapivě, konzistence zápisu. Ve skutečnosti se v běžně používané infixové notaci zapisují pouze některé základní matematické operace, jako je sčítání, násobení nebo dělení. Další operace se zapisují pomocí funkcí v prefixové notaci (například sinus, odmocnina, logaritmus, minimum) a některé dokonce v notaci postfixové (například faktoriál).
Pomocí postfixové notace je možné zapisovat všechny operace i funkce, dokonce ani nezáleží na počtu operandů (stírá se rozdíl mezi unárními. binárními, ternárními apod. operacemi). Ve skutečnosti není v postfixové notaci prakticky žádný rozdíl mezi operacemi a funkcemi, takže pro ně není nutné zavádět nějaká zvláštní syntaktická pravidla.
Důsledkem výše uvedených skutečností je fakt, že znaky běžně používané pro operátory je možné použít pro jiné účely, podobně jako například v jazyce Lisp nebo Scheme (což jsou mimochodem jazyky používající prefixovou notaci).
Aritmetické operace se ve Forthu zapisují přesně podle infixové notace s tou podmínkou, že jednotlivé operátory od sebe musí být odděleny mezerou, znakem tabelátoru či znakem pro konec řádku. Příklad zápisu některých aritmetických operací a jejich kombinací:
10 20 + 10 20 * 10 20 - 10 20 + 30 * 5 4 3 2 1 * / + -
Význam výše uvedených operací ve Forthu je následující: samotný zápis čísla znamená, že se toto číslo uloží do zásobníku. Zápis operátoru způsobí, že se operandy vyberou ze zásobníku, provede se s nimi operace a výsledek se uloží zpět na zásobník. Vzhledem k tomu, že všechny zmíněné operace jsou binární, vyberou se ze zásobníku dvě hodnoty a zpět se zapíše pouze jediná hodnota, tj. počet položek na zásobníku se o jednu sníží. (Cvičení – jaký je výsledek poslední sekvence operací?).
To si můžeme ilustrovat na následujícím diagramu, kde jsou na levé straně od pomlček naznačeny významné položky na vrcholu zásobníku před provedením operace a na pravé straně od pomlček je uveden stav zásobníku po provedení operace. Tento diagram se nazývá stack diagram a hojně se vyskytuje ve zdrojových textech programů psaných ve Forthu:
(x y -- x+y)
6. Výpis hodnoty uložené na vrcholu zásobníku
Po spuštění některého interpretru Forthu je možné ihned (podobně jako u kalkulaček HP) zapisovat aritmetické operace v postfixové notaci s využitím známých operátorů + - * a /. Pouze potřebujeme znát příkaz, kterým je možné vypsat hodnotu na vrcholu zásobníku. Tento příkaz je velmi jednoduchý – jedná se o prostou tečku: ., kterou je však nutné od ostatních příkazů oddělit alespoň jednou mezerou nebo jiným „bílým“ znakem.
Stack diagram tohoto příkazu je velmi jednoduchý, protože dochází k vyjmutí prvku uloženého na vrcholu zásobníku:
(n -- )
Po zadání příkazu tečka se přečte hodnota uložená na vrcholu zásobníku a zapíše se na standardní výstup. Současně je hodnota ze zásobníku odebrána, takže se počet uložených položek o jednotku sníží. Pokud je tento příkaz zavolán na prázdný zásobník, znamená to chybu, kterou by měl interpretr ohlásit. Příklady použití:
10 . 10 20 + . 10 20 30 * + . 10 20 * 30 + .
Všimněte si, že všechny výše zmíněné operace pracují se zásobníkem korektně, tj. po jejich provedení je zásobník zcela vyprázdněn. Při programování ve Forthu je důležité, aby na zásobníku nezůstala žádná zbytečná data, neboť to ve většině případů značí nesprávně napsanou operaci či funkci. Kód je možné upravit libovolným způsobem, vždy se však musí dodržet podmínka, že operandy a operátory musí být odděleny „bílým“ znakem:
10 20 + . 10 20 + . 10 20 + . 10 20 + .
7. Obsah dalšího pokračování
V další části tohoto seriálu se již budeme nekompromisně věnovat Forthu. Popíšeme si zejména způsob vytváření nových slov (funkcí) a dále slova pro tvorbu smyček a rozhodovacích příkazů.
