Strukturované datové typy v Logu

Obsah

1. Implementace zásobníků, front, polí a seznamů vlastností pomocí seznamů
2. Zásobník (stack)
3. Fronta (queue)
4. Seznamy a datová struktura pole (array)
5. Seznamy vlastností (property list)
6. Odkazy na další informační zdroje
7. Obsah následující části tohoto seriálu

1. Implementace zásobníků, front, polí a seznamů vlastností pomocí seznamů

Seznamy (lists) sice tvoří základní strukturovaný datový typ, který se v Logu, podobně jako v jeho ideovém předchůdci LISPu a Scheme, používá ve velkém množství algoritmů, ale existují programy, ve kterých může být výhodnější využít jiné datové typy, například zásobníky, fronty, klasická pole či asociativní pole. Z tohoto důvodu jsou v mnoha verzích Loga dostupné procedury a funkce, které tyto datové typy podporují.

Ve skutečnosti se vždy jedná o datové typy, které interně používají pro ukládání dat seznamy, což jenom ukazuje na jejich univerzálnost. Kromě toho je mnoho úloh zaměřena na práci s textovými řetězci, které v Logu mají také mnoho společných vlastností se seznamy. Pojďme si nyní říci, jak lze v Logu pracovat se zásobníky (druhá kapitola) a frontami (kapitola třetí). Ve čtvrté kapitole si ukážeme práci s poli a v kapitole páté použití takzvaných seznamů vlastností.

2. Zásobník (stack)

Zásobník (anglicky nazývaný stack), je z hlediska programování a programovacích technik dynamická datová struktura, pomocí které je možné, podobně jako u implementačně příbuzného jednosměrně či obousměrně vázaného seznamu, ukládat a zpětně získávat data. Ovšem od seznamu a dalších dynamických datových struktur jako je fronta, strom či graf se zásobníky liší především množinou základních operací, určenou pro práci s touto datovou strukturou.

Mezi typické použití zásobníků patří zpracování aritmetických výrazů zapsaných v postfixové notaci, převod aritmetických výrazů z infixové („lidské“) notace do notace postfixové (RPN – Reverse Polish Notation), procházení binárními stromy, volání podprogramů, předávání parametrů funkcím, uložení stavu programu při zpracování přerušení apod. Zásobníky také tvoří základ programovacího jazyka Forth, grafického metaformátu PostScript a tradičního unixovského kalkulátoru dc.

Datová struktura zásobník nebo jeho 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é: nejdříve vložená data do zásobníku lze přečíst až po vyjmutí všech 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.

V případě Loga to však neplatí, protože zásobník je zde implementován pomocí seznamů, takže je možné „mixovat“ operace se zásobníkem s operacemi prováděnými nad seznamem, což může v některých případech vést k jednoduššímu programu. 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):

Obrázek 1: Dynamická datová struktura zásobník společně s dvojicí základních operací

V Logu jsou pro práci se zásobníky určeny dvě procedury (resp. jedna procedura a jedna funkce), které se jmenují push a pop, tj. stejně jako základní operace prováděné nad abstraktním zásobníkem. Proceduře push se předávají dva parametry. Prvním parametrem je proměnná, která reprezentuje zásobník, druhým parametrem je objekt, který se má do zásobníku uložit na jeho vrchol. Funkci pop se předává pouze proměnná reprezentující zásobník. Výsledkem volání této funkce je navrácení hodnoty (objektu) uložené na vrcholu zásobníku, přičemž je tato hodnota (objekt) ze zásobníku odstraněna.

To znamená, že funkce pop není čistě matematickou funkcí, protože má vedlejší efekt – změnu struktury zásobníku. Vzhledem k tomu, že v Logu je zásobník vytvořen nad seznamem, je také proměnná reprezentující zásobník typu seznam. Inicializace zásobníku je provedena jednoduše: vytvořením prázdného seznamu pomocí dvojice hranatých závorek (náhrada Lispovského nil).

Ukažme si jednoduchý příklad, ve kterém je využit zásobník. Následující obrázek ukazuje, jak se do zásobníku postupně naskládají čtyři číselné hodnoty (v Logu se však může jednat i o další objekty, například řetězce či podseznamy) a poté se tyto hodnoty opět vyjímají:

Obrázek 2: Stav zásobníku při vkládání a vyjímání číselných hodnot

V Logu by celý program mohl vypadat například takto (příkazy zadané uživatelem jsou zvýrazněny tučným písmem, odpovědi počítače písmem normálním, poznámky kurzivou):

; nejprve vytvoříme proměnnou, která bude "bází"
; pro vznikající zásobník
make "zasobnik []

; přesvědčíme se, že jde opravdu o prázdný seznam
show :zasobnik
[]

; vložíme do zásobníku čtyři čísla
push "zasobnik 42
push "zasobnik 23
push "zasobnik 2
push "zasobnik 9

; jak nyní vypadá stav zásobníku?
show :zasobnik
[9 2 23 42]

; odstranění čísla z vrcholu zásobníku (TOS)
show pop "zasobnik
9

; došlo skutečně ke změně zásobníku?
show :zasobnik
[2 23 42]

; odstraníme i další objekty ze zásobníku (z TOS)
show pop "zasobnik
2
show pop "zasobnik
23
show pop "zasobnik
42

; nyní je zásobník prázdný, ale zkusíme ještě jeden "pop"
show pop "zasobnik
first doesn't like [] as input in pop
; na tomto hlášení je patrné, jak je operace "pop" implementována 

3. Fronta (queue)

Princip práce s daty u zásobníku je přesně opačný než u další lineární dynamické datové struktury, která je velmi často v praktických aplikacích používána – 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.

Použití front je všestranné, typicky jsou však fronty implementovány (ať již programově, či přímo v hardware) v různých vyrovnávacích pamětech, například bufferech tiskáren, tiskových spoolerech, sériových portech, sběrnicích apod. Nejjednodušší hardwarovou implementací fronty je posuvný registr. Také frontu si můžeme znázornit graficky. Všimněte si rozdílných míst, ve kterých do fronty data vstupují pomocí operace push a vystupují pomocí operace pop. Pod abstraktními názvy základních operací jsou napsány i odpovídající jména procedur Loga.

Obrázek 3: Dynamická datová struktura fronta společně s dvojicí základních operací

V Logu se pro ukládání či vybírání dat z fronty nepoužívají operace pojmenované push a pop, protože ty jsou rezervované pro práci se zásobníky. Místo toho zde můžeme nalézt proceduru queue sloužící pro uložení objektu na začátek fronty (korektnější by však bylo označení enqueue) a dále proceduru dequeue pro výběr objektu na konci fronty. Pokud potřebujeme získat informaci o tom, zda je fronta prázdná, můžeme využít faktu, že je fronta interně reprezentována zásobníkem, pro který existuje predikátová funkce emptyp. Pokud tedy zavoláme tuto funkci na proměnnou obsahující frontu, získáme pravdivostní hodnotu false v případě, že fronta není prázdná a naopak hodnotu true tehdy, pokud se ve frontě nenachází žádný objekt. Práci s frontou si můžeme ukázat na podobné sekvenci čtyř číselných objektů, jaká byla použita při vysvětlování funkce zásobníku, tj. na sekvenci 42, 23, 2 a 9:

Obrázek 4: Stav fronty při vkládání a vyjímání číselných hodnot

; nejprve vytvoříme proměnnou, která bude "bází"
; pro vznikající frontu
make "fronta []

; přesvědčíme se, že jde opravdu o prázdný seznam
show :fronta
[]

; vložíme do fronty čtyři čísla
queue "fronta 42
queue "fronta 23
queue "fronta 2
queue "fronta 9

; jak nyní vypadá stav fronty?
show :fronta
[42 23 2 9]
; všimněte si odlišnosti od stavu zásobníku v předchozím příkladu

; odstranění čísla z konce fronty
show dequeue "fronta
42
; i zde došlo k odstranění jiného prvku, než v případě zásobníku

; došlo však skutečně ke změně fronty?
show :fronta
[23 2 9]

; odstraníme i další objekty z fronty
show dequeue "fronta
23
show dequeue "fronta
2
show dequeue "fronta
9

; nyní je fronta prázdná, ale zkusíme ještě jeden "dequeue"
show dequeue "fronta
first doesn't like [] as input in dequeue
; na tomto hlášení je patrné, jak je operace "dequeue" implementována 

Vzhledem k tomu, že jak fronta, tak i zásobník jsou implementovány nad seznamem, je možné kombinovat všechny čtyři procedury push, pop, queue a dequeue a vytvořit tak například další poměrně často používaný datový typ – oboustrannou frontu, do které je možné data zapisovat i číst z obou stran, tj. jak z jejího začátku, tak i konce.

4. Seznamy a datová struktura pole (array)

Dalším strukturovaným datovým typem, který je možné v Logu použít, je pole (array). Jedná se o v praxi velmi často používaný datový typ, zejména v těch programovacích jazycích, u nichž lze seznamy, fronty, zásobníky či stromy implementovat nesnadným způsobem (Fortran, Basic, Pascal). Pole se od striktně pojatých seznamů odlišuje především v tom, že má pevnou délku (položky do něj nelze přidávat ani ubírat), každá položka je dostupná pod svým celočíselným indexem a existují funkce pro zápis libovolné položky popř. pro její čtení, přičemž jsou tyto funkce vytvořeny efektivně tak, aby jejich složitost byla O(1), tj. nezávislá na celkové délce pole.

V Logu se pole chovají více dynamicky, než je na první pohled zřejmé – jejich délka je vyhodnocována až v době běhu programu, tj. může být určena i nějakým výrazem, je možné převádět data z polí do seznamů a naopak a není nutné, aby každá položka pole měla stejný datový typ (z tohoto hlediska tedy nejsou pole v Logu homogenním datovým typem, to nás však nemusí trápit).

Pole lze v Logu vytvořit pomocí funkce array, které se předá délka pole, tj. celkový počet položek (ten nemusí být konstantní, lze použít libovolný celočíselný výraz). První položka má index nastavený na jedničku, což je pro začátečníky přirozenější, než indexování od nuly známé například z C, C++ či Javy. Pokud by bylo zapotřebí pole indexovat od jiné hodnoty, je možné funkci array volat ve formátu (array velikost index_první_po­ložky).

Při obou způsobech vytvoření pole jsou všechny jeho položky inicializovány na prázdné seznamy, tj. na hodnoty []. Druhou možností vytvoření pole je použití funkce listtoarray, pomocí níž lze libovolný seznam převést na pole. Počet položek tohoto pole je roven počtu položek seznamu. Také tuto funkci je možné volat s přídavným parametrem, kterým se udává index jeho první položky: (listtoarray seznam index_první_po­ložky). Opačnou funkcí je arraytolist, která slouží k převodu pole na seznam.

Pro čtení obsahu položek obsažených v poli slouží především funkce item index, je však také možné použít dvě „seznamové“ funkce first a last (platí pouze pro novější verze Loga). Některou položku pole je možné měnit pomocí funkce setitem index pole hodnota. Vzhledem k tomu, že proměnné jsou v Logu typovány dynamicky, je v některých případech nutné zjistit, zda je nějaká hodnota opravdu typu pole. To se zajistí zavoláním predikátu arrayp, který vrátí pravdivostní hodnotu true pouze v případě, že se skutečně jedná o pole. Následuje jednoduchý příklad použití pole:

; vytvoření pole s pěti položkami
make "pole array 5

; vypíšeme si obsah tohoto pole
show :pole
{[] [] [] [] []}
; skutečně se jedná o pět prázdných seznamů

; zapíšeme položku s indexem 1
setitem 1 :pole 42

; a znovu vypíšeme obsah pole
show :pole
{42 [] [] [] []}
; místo prvního prázdného seznamu je uloženo číslo

; získáme pouze první položku pole
show item 1 :pole
42

; druhá položka je inicializována na prázdný seznam
show item 2 :pole
[] 

5. Seznamy vlastností (property list)

Zajímavým datovým typem, který je v Logu pomocí několika procedur a funkcí podporován, je takzvaný seznam vlastností (property list). Ve skutečnosti se interně jedná o prostý seznam, na jehož lichých položkách jsou uloženy názvy vlastností a na sudých položkách jejich hodnoty. Vzhledem ke způsobu, jakým je možné se seznamy vlastností pracovat, je možné tyto seznamy použít i jako jednoduchá asociativní pole či hešovací pole. Pro práci se seznamy vlastností jsou určeny pouhé čtyři procedury.

Pomocí procedury pprop se do vybraného seznamu vlastností vloží vlastnost zadaná svým jménem a hodnotou. Opakem je procedura remprop, jež slouží k odstranění zadané vlastnosti a samozřejmě i její hodnoty ze seznamu vlastností. Pro zjištění hodnoty nějaké vlastnosti se používá funkce gprop, která v případě, že zadaná vlastnost nebyla v seznamu uložena, vrátí prázdný seznam, tj. hodnotu []. Poslední funkcí je plist, která seznam vlastností vrátí ve formě běžného seznamu (liché indexy=názvy vlastností, sudé indexy=hodnoty vlastností).

Práci se seznamy vlastností si ukážeme na velmi jednoduchém příkladu, ve kterém se do seznamu nazvaného jednoduše konfigurace vloží vlastnost nazvaná computer s hodnotou PC, dále vlastnost nazvaná system s hodnotou Linux a konečně vlastnost memory s hodnotou 256. Jména vlastností jsou chápaná jako řetězce (což je u asociativních polí běžné), proto před nimi musí být uveden znak ". Stejné pravidlo platí i pro jméno vlastního seznamu vlastností:

; nejprve do seznamu vlastností vložíme tři nové vlastnosti
pprop "konfigurace "computer "PC
pprop "konfigurace "os       "Linux
pprop "konfigurace "memory   256

; převod na "běžný" lineární seznam
show plist "konfigurace
[memory 256 os Linux computer PC]

; funkcí gprop lze získat hodnotu jednotlivých vlastností
show gprop "konfigurace "computer
PC
show gprop "konfigurace "os
Linux
show gprop "konfigurace "memory
256

; co se stane, pokud budeme chtít získat neinicializovanou vlastnost?
show gprop "konfigurace "neco_jineho
[] 

6. Odkazy na další informační zdroje

1. Wikipedia EN: List
   http://en.wiki­pedia.org/wiki/Lis­t_(computing)
2. Wikipedia EN: Stack
   http://en.wiki­pedia.org/wiki/Stac­k_(data_struc­ture)
3. Wikipedia EN: Queue
   http://en.wiki­pedia.org/wiki/Qu­eue_(data_struc­ture)
4. Wikipedia EN: Deque
   http://en.wiki­pedia.org/wiki/De­que
5. Wikipedia CS: Zásobník
   http://cs.wiki­pedia.org/wiki/Zá­sobník_(datová_struk­tura)
6. Wikipedia CS: Fronta
   http://cs.wiki­pedia.org/wiki/Fron­ta_(datová_struk­tura)
7. Friendly M.:
   Advanced LOGO a Language for learning
   New Jersey, Hillsdale, 1988
8. Goldenberg E. Paul, a Wallace Feurzeig:
   Exploring Language with Logo
   MIT Press
9. Young People's Logo Association:
   The Logo Library
10. StarLogo Pages at MIT,
    http://el.www­.media.mit.edu/grou­ps/el/Projects/star­logo/
11. StarLogo Pages at Northwestern University,
    http://ccl.nor­thwestern.edu/cm/star­logoT/
12. NETLogo Pages,
    http://ccl.nor­thwestern.edu/ne­tlogo/
13. MSWLogo,
    http://www.sof­tronix.com/lo­go.html

7. Obsah následující části tohoto seriálu

V další části seriálu o programovacím jazyce Logo si popíšeme pokročilejší operace, které jsou některými interpretery tohoto programovacího jazyka nabízeny. Jedná se například o komunikaci po síti, podpora více vláken, multitasking atd. Kromě toho dokončíme téma řetězců – popíšeme si funkce, které se k řetězcům vztahují.