České vysoké učení technické v Praze Fakulta elektrotechnická
Bakalářská práce
Návrh a implementace výukového programovacího jazyka založeného na jazyku Karel Jakub Šenkýř
Vedoucí práce: Ing. Ladislav Vagner
Studijní program: Elektrotechnika a informatika strukturovaný bakalářský Obor: Informatika a výpočetní technika srpen 2007
ii
Prohlášení Prohlašuji, že jsem svou bakalářskou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).
V Trutnově dne 20.8. 2007
….................................................................
iii
iv
Abstract The work deals with a design and implementation of programming language for learning based on the Karel language. It adds an ability of aritmetical and logical computations and parallel work of several virtual robots. New language empowers education of parallel programming principles and introduces synchronisation problems by game. The work covers the implementation of language translater, interpreter and basic input / output subsystem. It focuses in capability of easy language customization and modular solution of visualization part.
Abstrakt Práce se zabývá návrhem a implementací výukového jazyka založeného na jazyku Karel. Rozšiřuje ho o schopnost aritmetických a logických výpočtů a paralelní práci více nezávislých virtuálních robotů. Nový jazyk umožňuje výuku principů paralelního programování a seznámení se s problémy synchronizace formou hry. Práce pokrývá implementaci překladače, interpretu a základního vstupně / výstupního podsystému. Důraz je kladen na snadnou přizpůsobitelnost jazyka a modulární řešení vizualizační částí aplikace.
v
vi
Obsah 1 2
Úvod.................................................................................................................................... ............1 Jazyky pro výuku...................................................................................................................... .......2
2.1 Plnohodnotné jazyky navržené pro výuku...........................................................................2 2.1.1 Pascal......................................................................................................................... ....2 2.1.2 BASIC........................................................................................................... ................3 2.2 Plnohodnotné jazyky neurčené pro výuku...........................................................................4 2.2.1 C a C++..................................................................................................... ....................4 2.2.2 Java....................................................................................................................... .........5 2.3 Skriptovací jazyky...................................................................................... ..........................6 2.4 Jazyky specializované pro výuku dětí ve školním věku......................................................6 2.4.1 Logo................................................................................................... ...........................6 2.4.2 Karel................................................................................................................ ..............8 2.4.3 Baltík............................................................................................................ .................9 2.4.4 Petr.................................................................................................... ............................9 3
Vymezení cílů........................................................................................................................... .....11
3.1 Aritmetické a logické výpočty...................................................................................... ......12 3.2 Paralelní provádění programů............................................................... .............................12 3.3 Rozšířené vnímání okolí...................................................................................... ...............13 3.4 Bližší pohled na práci procesoru při běhu programu.........................................................13 3.5 Lokalizace na úrovni klíčových slov jazyka......................................................................13 3.6 Modulární uživatelské rozhraní........................................................................... ...............14 4
Analýza a návrh................................................................................................................. .............15
4.1 Analýza nových prvků jazyka A-MOR.................................................................... ..........15 4.1.1 Práce s proměnnými, výpočty................................................................................... ..15 4.1.2 Synchronizace........................................................................................... ..................16 4.1.3 Multitasking robotů................................................................................................ .....16 4.1.4 Programy vracející hodnotu.................................................................................. ......16 4.1.5 Programy volatelné s parametry................................................................ .................16 4.2 Terminály a neterminály........................................................................................... ..........18 4.2 Přepisovací pravidla....................................................................................................... .....22 4.3 Instrukce zásobníkového počítače......................................................................... .............29 4.4 Dodatečné výstupní operace................................................................................. ..............31 4.5 Překladová gramatika.............................................................................. ...........................32 4.6 Návrh aplikace.............................................................................................. ......................36 4.6.1 Překladač....................................................................................................... ..............36 4.6.2 Interpret........................................................................................................ ...............36 4.6.3 Práce se soubory.......................................................................................................... 37 4.6.4 Uživatelské rozhraní........................................................................... ........................37 4.6.5 Datová část..................................................................................................... .............37 5
Popis implementace.......................................................................................................... .............38 vii
5.1 Pomocné třídy.................................................................................................. ...................38 5.2 Globální prvky............................................................................................... .....................39 5.3 Činnost aplikace po spuštění.................................................................... ..........................40 5.4 Uživatelské rozhraní...................................................................................... .....................41 5.4 Podsystém pro práci se soubory................................................................. ........................42 5.5 Lexikální analyzátor a překladač............................................................................. ...........43 5.6 Robot a interpret...................................................................................... ...........................45 5.7 Chybová hlášení.......................................................................................................... ........46 6 7
Testování................................................................................................................... ....................48 Závěr............................................................................................................................................. .50
7.1 Zhodnocení naplnění cílů práce..................................................................................... .....50 7.2 Další možný vývoj.............................................................................................. ................50 8 Seznam literatury.................................................................................................................. ..........51 A Obsah přiloženého CD......................................................................................................... .........54 B Pokyny ke kompilaci a spuštění.................................................................................... ................56
B.1 Požadavky............................................................................................... ...........................56 B.2 Kompilace............................................................................................... ...........................56 B.3 Spuštění........................................................................................................ ......................57 C
Uživatelská příručka........................................................................................... ..........................58
viii
Seznam obrázků Ilustrace 1: Mikropočítač Altair 8800..................................................................... ........................3 Ilustrace 2: Želva jazyka Logo ze stavebnice LEGO.............................................................. ........7 Ilustrace 3: Programování pomocí ikonek v Baltie 4.............................................................. ........9 Ilustrace 4: Editor jazyka Petr........................................................................... ............................10
ix
x
Seznam tabulek Tabulka 1: Pascal – výhody a nevýhody.......................................................................... ...............2 Tabulka 2: BASIC - výhody a nevýhody...................................................................... ..................4 Tabulka 3: C - výhody a nevýhody........................................................................ .........................5 Tabulka 4: Java - výhody a nevýhody................................................................................... ..........5 Tabulka 5: Skriptovací jazyky - výhody a nevýhody..................................................................... .6 Tabulka 6: Logo - výhody a nevýhody.............................................................. .............................7 Tabulka 7: Karel - výhody a nevýhody........................................................................... ................8 Tabulka 8: Baltík - výhody a nevýhody....................................................................... ...................9 Tabulka 9: Petr - výhody a nevýhody............................................................................................ 10 Tabulka 10: Terminály a neterminály jazyka A-MOR.................................................................18 Tabulka 11: Přepisovací pravidla jazyka A-MOR........................................................................22 Tabulka 12: Abeceda zásobníkového počítače.............................................................................29 Tabulka 13: Dodatečné výstupní operace.....................................................................................31 Tabulka 14: Překladová gramatika jazyka A-MOR.............................................................. ........32
xi
xii
KAPITOLA 1
ÚVOD
1
1 Úvod Historie moderních programovacích jazyků započatá návrhem jazyka FORTRAN v roce 1954 [1] čítá do dnešních dnů více než tisíc různých jazyků, jejich vzájemných derivátů a kombinací. Pouze mizivé procento z tohoto počtu představují jazyky určené pro výuku programování, ať už je tím míněna algoritmizace, nebo návrh a tvorba aplikací v moderním pojetí. S nástupem multimédií a internetu v posledních patnácti letech se těžiště „výuky počítačů“ přesunulo z tvorby programů na práci s aplikacemi [2] a webem. „Výpočetní techniku“ nahradila „informatika“ a nutnost porozumět technice vystřídala schopnost využít ji k získávání informací. Vymizela vrstva základního seznámení s programováním na základních školách a pozici jazyků pro výuku na středních a vysokých školách převzaly profesionální jazyky určené původně k efektivnímu vývoji aplikací. Boom objektového programování v 90. letech zahájil odsun žáků a studentů od psaní příkazů a řešení algoritmických problémů směrem k vyšší abstrakci. Současný trend „Design Patterns First“ [3] upřednostňuje ještě větší odstínění budoucího programátora od konkrétního algoritmu a klade důraz především na pečlivé modelování řešeného systému. Systém tak nahradil problém řešený při programování v 80. letech. Rostoucí míra složitosti aplikací si tento vývoj vynucuje. Algoritmy jsou nyní součástí základních knihoven a těžiště vývoje aplikací leží v modifikovatelnosti a znovupoužitelnosti vyvíjeného kódu [3]. Prací programátora se z původního „jak to vyřešit“ stalo „co a jak poskládat“. Tím se zároveň z jeho práce vytratila radost z vymýšlení nového a nahradila ji všední rutina. Programování je dnes daleko „sušší“, než bylo v dřívějších dobách [29]. Původní jazyky a nástroje pro výuku programování zůstaly stát na prahu 90. let minulého století a pouze zpovzdálí sledují vývoj situace. Spolu s nimi opustilo výuku programování i nadšení ze správně vyřešeného problému, onen pravý „programátorský zápal“, který děti ve školním věku motivoval při prozkoumávání výpočetní techniky. Objevilo se sice několik pokusů o moderní „naskládej si, co potřebuješ, a kód vygeneruji já“ výukových řešení, ale ta postrádají právě radost a zadostiučinění z pokoření problému. Rutina se propracovala už i do výukových nástrojů Polozapomenuté, leč neopuštěné [4], dokáží „neužitečné“ (protože neprodukční) jazyky jako Karel a Logo tu radost vyvolat i dnes. Logo je díky svému funkcionálnímu přístupu v jistém smyslu nadčasové, neboť matematické principy a způsoby abstraktního myšlení se v porovnání s raketovým rozvojem techniky nemění. Jazyk Karel, operující s virtuálním robotem ve virtuálním prostoru, daleko lépe ilustroval skutečnou práci počítače při provádění programu. Jako takový však zároveň rychleji zastaral. Trend víceúlohových systémů na domácích počítačích podpořený v nedávné době rozvojem hardwarového paralelismu při zpracování programů se příliš vzdálil od původní analogie jednoduchého počítače vykonávajícího jediný program, kterou Karel představoval. Nové implementace přinesly až na pár drobných vylepšení pouze novou, méně přívětivou syntaxi. Cílem této práce je navrhnout jazyk, který by oprášil zapomenutého robota na jeho dvorku a obohaceného o nové schopnosti ho znovu představil těm, kdo netouží hned programovat webové stránky a vytvářet informační systémy, ale zajímá je, jak počítače uvnitř pracují.
KAPITOLA 2
2
JAZYKY PRO VÝUKU
2 Jazyky pro výuku V průběhu historie vzniklo několik jazyků určených čistě pro výuku programování a nic jiného, ale pozoruhodně často se v pozici prvního jazyka, se kterým se uživatelé na počítači setkali a ve kterém se učili programovat, ocitl jazyk naprosto odlišný, někdy i pro výuku zcela nevhodný. Tato kapitola je tedy přehledem jazyků, které se v pozici „pro výuku“ ocitly, ať už k tomu měly dispozice či ne, a zhodnocení, jakým způsobem se této role zhostily.
2.1
Plnohodnotné jazyky navržené pro výuku
2.1.1 Pascal Mezi jazyky přímo určené pro výuku patří zejména Pascal vyvinutý Niklausem Wirthem v roce 1970. Pascal od prvotního návrhu podporuje strukturované programování - inspirací mu byl jazyk ALGOL, který v roce 1960 zavedl pojem procedury [5], a Wirth navrhl svůj jazyk přímo za účelem výuky tohoto druhu programování. Zajímavostí je, že původně měl Pascal přijít na svět o rok dříve, ale Wirthovi se nepodařilo napsat pro něj ve FORTRANU kompilátor. Teprve v roce 1970 tedy Pascal vznikl - s kompilátorem napsaným v Pascalu samotném [6]. V univerzitním prostředí se Pascalu dařilo přes 30 let a teprve v poslední době ho vytlačily jiné jazyky. Jeho dědictví však stále přetrvává na některých středních školách [7] a v publikacích zabývajících se programováním, neboť mnoho tzv. pseudo-jazyků užívaných k popisu algoritmů je Pascalu podobných [1]. Přes své původní určení se Pascal přenesl i do praxe, jednak společně s programátory, kteří na něm vyrostli, a jednak přičiněním firmy Borland, která začala prodávat svoje vývojové prostředí Delphi [8] založené na objektovém rozšíření jazyka pojmenovaném Object Pascal. Ačkoli jsou zápisy v Pascalu často označované za příliš rozvleklé, jazyk vydržel živý a postupem času se objevilo několik modifikací, které mu pomohly udržet krok s dobou [6]. V letech 1983 a 1990 byly Pascal a jeho rozšířená podoba standardizovány jako ISO/IEC 7185, resp. ISO/IEC 10206 [6].
výhody
nevýhody
navržený přímo pro výuku
staticky kompilovaný
podporuje strukturované programování
delší zápis kódu
moderní implementace v Delphi podporuje objektové programování a vícevláknové zpracování Tabulka 1: Pascal – výhody a nevýhody
KAPITOLA 2
JAZYKY PRO VÝUKU
3
2.1.2 BASIC Přestože dosti kontroverzně, dal by se do této kategorie zahrnout i původní BASIC. O polovinu dekády starší než Pascal, byl tento Beginners All Purpose Instruction Code původně zamýšlen k usnadnění programování začátečníkům. Původní návrh z roku 1964 ovšem neobsahoval struktury, nebyl a není tedy pro výuku programování vhodný. Jeho přínosem bylo nicméně zjednodušení syntaxe a přiblížení klíčových slov mluvené angličtině, díky čemuž se stal mezi počítačovými amatéry velmi populární [5]. Svou spanilou jízdu (do té doby jeho rozšíření limitovaly sálové počítače a minipočítače) zahájil BASIC v roce 1975, když firma Micro-Soft (později přejmenovaná na Microsoft) vyvinula jeho interpretovanou verzi pro první mikropočítač Altair firmy MITS. Protože Micro-Soft měl ve smlouvě povoleno re-licencovat svůj BASIC další zákazníkům, stal se tento jazyk obsažený v pamětech ROM na mnoho let součástí každého domácího počítače [5].
Ilustrace 1: Mikropočítač Altair 8800 Nechvalně známým se BASIC stal pro svou tendenci podporovat tvorbu tzv. spaghetti code, dlouhých nestrukturovaných nudlí obtížně udržovatelného kódu, které vytvářeli domácí uživatelé a příležitostně přenášeli tento zlozvyk i do komerční sféry. I přes tento neduh zůstal BASIC velice oblíben, protože umožňoval rychle psát programy, které „něco dělaly“, aniž by se programátor musel starat o nějakou režii. Interpretovaný BASIC se posléze stal téměř povinnou výbavou domácích mikropočítačů a sloužil jako základní uživatelské rozhraní např. pro nahrávání aplikací z magnetických pásek do paměti počítače. Když v roce 1981 firma IBM uvedla na trh své IBM PC, Microsoft k němu začal kromě operačního systému v krátké době dodávat i Quick BASIC kompilátor, čímž se z BASICu (nyní označovaného Microsoft Basic) opět stal kompilovaný jazyk, kterým byl původně. V devadesátých letech se pro platformu MS-DOS a posléze Windows objevil Visual Basic, vývojové prostředí pro RAD (Rapid Application Development – rychlý vývoj aplikací) postavené na Quick BASICu. Na rozdíl od nastupujícího trendu objektového programování byl Visual Basic komponentově orientovaný (component-oriented) a řízený událostmi (event-driven) [9].
KAPITOLA 2
4
JAZYKY PRO VÝUKU
Neobsahoval vlastní podporu pro práci s vlákny, ale dovedl využít Windows API, které mu tuto funkčnost dodávaly externě. Dobrá srozumitelnost kódu (podobná lidské řeči ve srovnání s ostatními jazyky) u něj přetrvala stejně jako nízká přehlednost delších programů. I přesto se Visual Basic stal v druhé polovině devadesátých let oblíbeným ze stejného důvodu jako BASIC před ním – snadno lze pomocí něj sestavovat (nyní již grafické) aplikace bez zdržování s návrhem tříd apod. V rámci své technologie .NET se v současné verzi vývojových prostředí Microsoftu Visual Basic vyskytuje jen jako jedna ze syntaktických variant JIT (Just In Time) kompilovaného jazyka MS IL (Microsoft Intermediate Language).
výhody
nevýhody
snadná tvorba programů
v původním návrhu neexistence struktur, v moderní verzi neexistence klasických objektů (změna až v .NET)
od Visual Basic kompletní vývojové prostředí
ve velkých projektech málo čitelný kód
od Visual Basic .NET JIT kompilace
kromě Visual Basic .NET nepodporuje vlákna platformně závislý
Tabulka 2: BASIC - výhody a nevýhody
2.2
Plnohodnotné jazyky neurčené pro výuku
2.2.1 C a C++ Ačkoli je jazyk C široce populární mezi systémovými programátory a jeho objektový pokračovatel C++ se stal tak úspěšným, že pronikl i do oblastí, kde z bezpečnostních hledisek nemá co dělat, nebylo C nikdy zamýšleno jako jazyk pro výuku programování. Nízkoúrovňový přístup k hardwaru a potenciální nepřehlednost kódu (závislá zejména na dovednosti programátora) ho dělají pro tyto účely dokonale nevhodným. Přesto se mnoho zejména středoškolských studentů učí nejprve programovat právě v C/C++. Znalost C/C++ je viděna jako velká výhoda pro uplatnění v praxi (v poslední době ji nicméně nahrazují požadavky na znalost Javy, databází a tvorby webových aplikací). Pohříchu ovšem jen málo studentů, kteří se začnou učit programovat v C/C++, je ve výsledku dobrými programátory. Vstřebávání všech vlastností a pravidel jazyka spotřebovává čas, který by měl být věnován výuce algoritmů a umění analýzy. Programování v C se tak pro začátečníka (a nejen pro něj) často zvrtne v zápas s jazykem samým místo řešení daného problému. Protože je jazyk C původně určený k systémovému programování (vznikl kvůli přenositelnosti Unixu [10] ), podporuje vícevláknové programování. Na druhou stranu je staticky typovaný i kompilovaný, což je dnes vnímáno spíše jako nevýhoda. Změnu přináší jeho odvozenina C# od Microsoftu, která využívá syntaxe oblíbené mezi programátory k vývoji aplikací kompilovaných
KAPITOLA 2
JAZYKY PRO VÝUKU
5
způsobem JIT pomocí prostředí .NET. K výuce programování se však ani tato varianta nehodí, neboť zavádí režii s prací v objektovém prostředí.
výhody
nevýhody
silný programovací jazyk
neurčen pro výuku, potenciálně velmi nepřehledný
nepřekonaný v systémovém programování
staticky kompilovaný
podporuje vícevláknové zpracování
ani C++ není plně objektový
Tabulka 3: C - výhody a nevýhody
2.2.2 Java Jazyk Java uvedený na trh firmou Sun Microsystems v roce 1995 jako nový, plně objektový jazyk (ačkoli to není tak úplně pravda) vznikl původně jako čistě produkční. Nastupující trend objektového programování spojený s dosluhujícím Pascalem v pozici výukového jazyka na univerzitách však určil Javu jako následníka Pascalu. Přestože tak nebyla zamýšlena, stala se Java „Pascalem jednadvacátého století“. Její mateřská firma tuto generační výměnu podporuje, neboť je pro ni výhodné, aby se budoucí programátoři učili právě její jazyk. Java je založena na interpretaci tzv. bytekódu virtuálním strojem (virtual machine). Díky tomu jsou programy psané v Javě volně přenositelné na každou platformu, pro kterou existuje implementace virtuálního stroje. V posledních verzích začala Java podporovat i JIT kompilaci, aby mohla lépe soupeřit s konkurenčním řešením .NET od Microsoftu. Java podporuje vlákna, její silnou stránkou jsou bohaté knihovny umožňující vyvíjet aplikace beze ztrát času stráveného řešením algoritmických problémů. Další zbraní Javy je její podpora webových aplikací a databází a tudíž velké uplatnění v praxi. Problémem Javy z hlediska jazyka pro výuku je několik. Jednak produkční výhoda knihoven obsahujících již „vše důležité“ devalvuje snahu učit v Javě algoritmizaci. Také vysoká režie při psaní jednoduchých programů, které jsou při výuce nejčastější, je nevýhodná. I k nejzákladnější odezvě je potřeba vytvářet třídy a zabývat se pokročilým objektovým paradigmatem. Rovněž zatím nedošlo k „usazení“ principů výuky, takže často nejde o kýžené nahrazení Pascalu, ale pouze o pascalovské programování v objektovém prostředí [1].
výhody
nevýhody
objektová
nenavržená pro výuku
podpora webových aplikací, databází a vícevláknového zpracování
vysoká režie u jednoduchých programů
JIT kompilace (volitelná) Tabulka 4: Java - výhody a nevýhody
KAPITOLA 2
6
2.3
JAZYKY PRO VÝUKU
Skriptovací jazyky
Absence krátkých výukových programů, jejichž jednoduchost počítačoví amatéři tak oceňovali u BASICu a Visual Basicu, vede k tomu, že se na některých školách prosazují pro výuku programování skriptovací jazyky jako Perl, Python apod. [6] namísto jazyků „plnohodnotných“ (Pascal, Java, C++). Pro tuto volbu mluví dynamické provádění kódu, které dovoluje získat při chybě alespoň částečně funkční program místo dlouhého ladění všech chybových hlášení, které v C nebo Javě podstoupí každý student začínající programovat právě v těchto jazycích. Vyskytují se ovšem i hlasy proti, které těmto jazykům vytýkají netypové proměnné a obecně menší podobnost s produkčními jazyky, která vede k tomu, že se studenti musí učit ještě další jazyk kvůli praktickému uplatnění [6]. Rostoucí poptávka po vývojářích webových aplikací nicméně této námitce odporuje. Diskuse kolem uplatnění skriptovacích jazyků při výuce programování dosud trvá a často přechází v diskusi o tom, jak a co by se vlastně mělo v předmětu „programování“ učit. Podle preferencí jednotlivých škol se pak jejich hlas přiklání na tu či onu stranu.
výhody
nevýhody
dynamičnost
beztypovost
malá režie kódu
menší uplatnění v praxi (netýká se vývoje pro web)
Tabulka 5: Skriptovací jazyky - výhody a nevýhody
2.4
Jazyky specializované pro výuku dětí ve školním věku
2.4.1 Logo Logo je zvláštní programovací jazyk, který vznikl v roce 1967, tedy v období mezi BASICem a Pascalem. Za jeho vznikem stojí Seymour Papert [11], který Logo (tehdy ještě pojmenované „ghost“) nekoncipoval jako nástroj pro výuku programování, ale pro výuku samotného konstruktivního myšlení. Původní implementace jazyka vznikla ve funkcionálním LISPu a z něj také Logo částečně vychází. Většího rozšíření se jazyk dočkal až s nástupem osmibitových domácích počítačů (v USA především Apple II) [11], které dovolily naplno se projevit základnímu prvku atraktivity Loga, kterým je tzv. želví grafika. V praxi jde o značku (obvykle trojúhelníček) na obrazovce, která za sebou při pohybu zanechává stopu jako želva na písčité pláži. Pomocí jednoduchých příkazů jako forward, left, right apod. lze se „želvou“ manipulovat a kreslit tak různě složité obrázky.
KAPITOLA 2
JAZYKY PRO VÝUKU
7
Ilustrace 2: Želva jazyka Logo ze stavebnice LEGO Přestože je to právě grafická atraktivita, která dětské adepty programování k Logu přitáhla, neměli bychom opomenout další důležité vlastnosti jazyka, mezi které patří používání rekurze namísto smyček, podpora dynamických seznamů a návrh programu „zdola nahoru“, kdy se želva učí novým příkazům kombinací již známých. Základní rysy převzalo Logo z jazyka LISP, ale zjednodušilo jeho mnohdy příliš abstraktní syntaxi (vyznačující se mnoha závorkami a prefixovou notací operací) a přiblížilo tím dětem programovací paradigma odlišné od všech ostatních zde uváděných jazyků. Za čtyřicet let vzniklo mnoho komerčních [12] i volně dostupných [13] implementací Loga. Objevily se i verze přidávající více „želv“ kreslících různými barvami, ale jejich vzájemná interakce spočívala jen ve výsledném mnohabarevném obrázku, nelze tedy mluvit o paralelním programování, kde na sebe musí vlákna nějakým způsobem reagovat.
výhody
nevýhody
atraktivní grafický výstup
funkcionální přístup je těžko použitelný v praxi ovládané imperativními jazyky
podpora dynamických seznamů
chybí analogie vícevláknového zpracování programu
přiblížení funkcionálního paradigmatu návrhu Tabulka 6: Logo - výhody a nevýhody
KAPITOLA 2
8
JAZYKY PRO VÝUKU
2.4.2 Karel Jazyk Karel vzešel z hlavy Richarda Pattise v roce 1981 [14]. Zavedl tehdy virtuálního robota pohybujícího se ve virtuálním městě tvořeném sítí vodorovných (streets) a svislých (avenues) ulic. Robot stál vždy na křižovatce, byl schopen otočky o čtvrt kruhu a přesunu na další křižovatku. Kromě toho disponoval pípáky (beepers), které slyšel na vzdálenost jednoho bloku a mohl je rovněž umisťovat a sbírat. Rozpoznal také, jestli ulici před ním přehrazuje zeď a jestli je natočen k severu. Jazyk podporoval podmíněný příkaz a cyklus a základem při programování bylo naučit robota novým kouskům za pomoci kombinace již známých příkazů. V Česku se myšlenka virtuálního robota zalíbila a Tomáš Bartovský, autor první do češtiny lokalizované implementace, provedl v jazyce i další změny. Robot se nyní pohyboval na šachovnici přezdívané dvorek, místo severu poznal, zda je otočen na východ, a namísto pípáků měl u sebe značky, kterých mohl na každé políčko položit větší počet [4]. Následovaly další implementace, které rozšiřovaly sadu základních robotových pohybů nebo rozpoznatelných vjemů z prostředí. Různé verze Robota Karla existovaly pro osmibitové i šestnáctibitové domácí počítače a jazyk je dodnes diskutován jako varianta pro výuku na základních školách [4]. Na Slovensku vznikla varianta Robot Karol++ [15], která udělala z Karla objektově orientovaný jazyk syntakticky podobný Javě (na míle vzdálený jeho původnímu lehce pascalovskému duchu [17] ). Z moderních českých implementací uveďme jazyk xKarel, který původně vznikl jako semestrální práce a poté uvolněn k veřejnému užívání [16]. Velice pěkná je také implementace ve Visual Basicu [24], která zavádí nové prvky jako speciální políčko označené „domov“ nebo programování formou přetahování příkazů myší. Nevýhodou je omezení pro platformu Windows. Zatímco západní svět přestal poměrně brzy jevit o Karla zájem, v Česku šlo o jeden z nejpopulárnějších jazyků pro výuku po dlouhá léta, vznikaly různé výukové materiály a publikace. Součástí jedné [18] byla i papírová verze Karla, kde se po slepování příkazů mohl na plánku Karlova dvorku simulovat robotův pohyb a další akce. Zároveň kniha obsahovala zdrojový kód pro osmibitovou implementaci programu, po jejímž přepsání do počítače si mohl čtenář vyzkoušet totéž co hlavní hrdinka knihy. Postupně ale zájem o Karla vymizel i u nás. Nové implementace přinášely vesměs pouze zesložitění ve formě objektového přístupu, případně syntaxi méně odpovídající přirozené řeči, kterou původní Karel tolik zaujal. Množina řešitelných problémů se přestala zvětšovat a s ústupem výuky programování obecně Karel zapadl. výhody
nevýhody
výuka programování formou hry
omezená množina řešitelných úloh
dostupné české implementace
nové implementace jdoucí proti původní snaze o jednoduchost
Tabulka 7: Karel - výhody a nevýhody
KAPITOLA 2
JAZYKY PRO VÝUKU
9
2.4.3 Baltík Baltík je výukový „jazyk“ (respektive nástroj pro výuku) vzniklý v České republice (za jeho zrodem stojí firma SGP Systems [19] ) roku 1996. Na rozdíl od dvou výše zmíněných se tu neprogramuje klasickým psaním příkazů, ale skládáním ikon představujících příkazy. Tento systém převzal Baltík od jazyka Baltazar vyvinutého stejnou firmou o tři roky dříve [20]. Stejně jako u Loga a Karla je program personifikován, tentokrát v postavě čaroděje, který kouzlí ikony a tím vytváří scénu. Jazyk obsahuje podporu podmínek, cyklů, procedur (nikoli ale funkcí), práce se souřadnicemi, klávesnicí, zvuky atd. Jazyk umí i pracovat s proměnnými. Od verze Baltie 4 C# je možné program i klasicky psát, využívá se při tom syntaxe jazyka C#. Celkově jde o zajímavý nástroj pro výuku, abstrakce od skutečných programovacích jazyků je však už docela velká.
Ilustrace 3: Programování pomocí ikonek v Baltie 4 výhody
nevýhody
grafické programování
velká abstrakce od kódu
česká komunita
neobsahuje analogii paralelního programování
Tabulka 8: Baltík - výhody a nevýhody
2.4.4 Petr Programovací „jazyk“ Petr [21] jde podobnou cestou jako Baltík. I zde se programuje formou manipulace s grafickými ekvivalenty příkazů, proměnných, podmínek atd. Nástroj umožňuje tvorbu pokročilých aplikací s multimediálními prvky. Jde už vlastně více o specializované vývojové prostředí než o jazyk, podobá se například softwaru pro tvorbu počítačových her GameMaker [22]. Proti jeho volbě jako nástroje k výuce programování mluví jednak upřednostnění paradigmatu RAD ve stylu Visual Basicu a také komerční povaha aplikace.
KAPITOLA 2
10
JAZYKY PRO VÝUKU
Ilustrace 4: Editor jazyka Petr výhody
nevýhody
grafické programování
velká abstrakce od kódu
český interface
komerční produkt
Tabulka 9: Petr - výhody a nevýhody
KAPITOLA 3
VYMEZENÍ CÍLŮ
11
3 Vymezení cílů Cílem této práce je navrhnout a implementovat jazyk pro výuku programování založený na v Česku dříve velice populárním jazyce Karel. Jazyk by měl představovat skutečné vylepšení ve smyslu nabídnutí nových algoritmických problémů k řešení při zachování co největší jednoduchosti jazyka a maximální přístupnosti pro žáky základních, popřípadě středních škol. Měl by proto být co nejvíce zpětně kompatibilní, aby noví uživatelé mohli začínat na příkladech, kterými se s programováním seznamovali jejich předchůdci v dobách osmibitových implementací. Naopak ti s Karlem již seznámení mohou využít pokročilejších možností k řešení problémů dříve jazykem nepostižitelných. Jako výchozí bod jsem zvolil českou modifikaci jazyka Karel, která opouští původní návrh robota v městské síti ulic a přenáší ho na šachovnicový dvorek (podle nejednotného úzu nadále nazývaný město). Rovněž schopnost pokládat více značek na jedno políčko namísto jediného pípáku je z hlediska množiny řešitelných problémů vítaná. Základní body rozšíření jazyka sledují tyto cíle: •
naučit Karla počítat, tj. zavést schopnost aritmetických a logických výpočtů a možnost ukládat si výsledné údaje do paměti (podpora proměnných)
•
umožnit analogii paralelního provádění programů, tj. přidat Karlovi na dvorek několik robotích přátel, se kterými může řešit úlohy, na které by samotný nestačil, nebo naopak soupeřit o co nejlepší zvládnutí problému za použití rozdílných programů
•
rozšířit Karlovu schopnost vnímání prostředí o nové prvky, například rozměry města nebo přesnou vlastní pozici
•
nabídnout zájemcům o hlubší proniknutí do problematiky výpočetní techniky pohled do vykonávání programu na nižší úrovni, tak jak ho vnímá procesor počítače
Návrh samotného jazyka i základního uživatelského rozhraní by měl být řešen s důrazem na možnost: •
implementovat rozšíření tak, aby dovolovala další vývoj
•
implementovat lexikální elementy jazyka tak, aby nebyly závislé na mateřštině programátora a mohly být snadno editovatelné (např. z české verze zpět do angličtiny, kde má Karel svůj původ)
•
implementovat uživatelské rozhraní tak, aby nebylo na samotném jazyku závislé a mohlo být nahrazeno jiným, lépe ergonomicky zvládnutým nebo například jinak principielně řešeným (zaměnit plně grafické rozhraní za pouhé ukládání výstupů do souboru a podobně)
•
implementovat celé řešení s ohledem na snadnou platformní přenositelnost, tj. nepoužívat k implementaci prostředky dostupné jen pro jedinou platformu
KAPITOLA 3
12
3.1
VYMEZENÍ CÍLŮ
Aritmetické a logické výpočty
Jednou z nevýhod původního Karla bylo, že dokázal pracovat pouze s aktuálním stavem svého prostředí, nemohl si nic poznamenat a bez schopnosti pamatovat si byly jeho možnosti značně omezené. Přidání vnitřních proměnných robota je tedy logickým krokem a operace nad těmito proměnnými krokem logicky navazujícím. V souladu s prostředím, které obsahuje údaje celočíselného (rozměry města, počet značek na jednom políčku) a logického (značka je, nebo není, zeď je, nebo není) charakteru , bude tedy robot schopen zpracovávat proměnné těchto typů. Reálná čísla jsou pro jeho potřeby nadbytečná. Vzhledem k povaze jazyka zaměřeného na výuku a tedy i budování určitých programátorských návyků se zdá vhodnější, aby číselné a logické hodnoty nešly spolu míchat a zaměňovat. Rovněž výpočetní operace by měly pracovat jen s tím typem hodnot, pro které se jejich použití předpokládá (žádá implicitní konverze). V úvahu připadá statická nebo dynamická kontrola typů. Pro dynamickou mluví funkčnost alespoň části programu, než k chybě dojde, na druhou stranu odchycení potenciálních chyb ještě před spuštěním dovolí vychutnat si vykonávání programu bez obav, že se ještě vyskytne nějaký problém (a když se vyskytne, pak ne v kódu samotném, ale v kontextu situace, která je při vizualizované interpretaci jasně patrná). Vzhledem k přístupu diskutovanému dále v bodě 3.4 je volena statická kontrola za cenu menší uživatelské přívětivosti do začátku. Určitě je dobré na to myslet a navrhnout implementaci tak, aby případnou budoucí dynamickou kontrolu neznemožňovala. Další, z hlediska původních možností jazyka už dosti pokročilou možností, je implementace příkazů vracejících hodnotu (případně přebírajících parametry). V souladu s výše uvedeným tedy aritmetických a logických funkcí (se zachováním původních příkazů bez návratové hodnoty). Ideální začlenění je takové, které by doplnilo vyjadřovací možnosti jazyka, ale zároveň nepůsobilo komplikace začátečníkům, kteří je nebudou chtít používat.
3.2
Paralelní provádění programů
Umožnění vzájemné kooperace dalších robotů je základním vylepšením, které se zatím v žádné implementaci jazyka Karel neobjevilo. Přitom právě jazyk tohoto typu je ideální pro ilustraci paralelního provádění programů a pro osvojení si základů synchronizační problematiky formou hry. Návrh by tedy měl počítat s nějakou analogií mechanismů, které se při řešení problematiky paralelismu a synchronizace skutečně používají. Ideální by bylo umožnit robotům si navzájem zamykat / odemykat provádění kódu a dát jim schopnost vzájemného zasílání zpráv. Pro simulaci sdílení prostředků by měli být roboti vybaveni mechanismem „rezervace“ určité části města, neboť město je jediným prostředkem, který tu lze sdílet. Při simulaci paralelního programování je důležité zvolit správně míru realističnosti a abstrakce. Stále jde o jazyk určený pro výuku a pro mladší uživatele, neměl by tedy obsahovat tolik synchronizačních problémů, kolik jich v reálu při provádění vícevláknového programu procesorem skutečně může nastat. Minimálně základní činnosti robota musí být atomické, čehož lze dosáhnout buď variací na kooperativní multitasking [27], nebo skrytím složitosti do implementace (nebo kombinací obojího).
KAPITOLA 3
3.3
VYMEZENÍ CÍLŮ
13
Rozšířené vnímání okolí
Zatímco původní americký Karel se uměl rozhlížet do všech směrů bez nutnosti otáčení, ale zato rozpoznal jen jedinou světovou stranu, pozdější implementace dovolovaly rozeznávat čtyři směry, naproti tomu zeď už robot vnímal pouze tehdy, pokud k ní byl natočen čelem, a značku viděl, pouze pokud stál přímo nad ní. Nová implementace bude vycházet z pozdějších úprav, ale zároveň by měla umožňovat i nové způsoby vnímání robotova okolí. V součinnosti s bodem 3.1 toho může být dosaženo tak, že robot bude mít určitou sadu proměnných, nazývaných proměnné prostředí, které budou sloužit jako senzory vnějších jevů a nebude je možné programově měnit. Zároveň to umožňuje „zeptat se“ jiného robota na hodnotu některé z jeho proměnných prostředí a tím rozšířit své senzorické schopnosti mimo bezprostřední vlastní okolí. Není ale vhodné, aby si roboti viděli do karet příliš, protože pak by spousta pěkných algoritmických problémů pozbyla smyslu. Kompromisem může být několik proměnných prostředí přístupných i ostatním robotům, zatímco většina zůstane v soukromém vlastnictví každého z nich. Veřejné proměnné prostředí mohou sloužit např. k synchronizaci (viz bod 3.2). Výhodou by byla implementace, ve které by se dalo zveřejňování těch kterých proměnných prostředí snadno konfigurovat bez zásahu do zdrojových kódů. Některé proměnné prostředí mohou být i sdílené, typicky všechny vlastnosti města a také jevy, které se týkají všech robotů naráz.
3.4
Bližší pohled na práci procesoru při běhu programu
Jestliže původní návrh Karla zpřístupňoval paradigma strukturovaného programování a některé implementace dovolily nahlédnout do programování objektového, lze jistě jít i druhým směrem a ukázat zájemcům o bližší porozumění výpočetní technice, co se stane s napsaným programem, aby ho mohl počítač provádět. Umožnit zvídavějším nahlédnout do struktury jazyka symbolických instrukcí. Jazyk typu Karel je pro to ideální, protože jeho příkazy lze snadno převést do přechodové formy, sledu jednoduchých „instrukcí“ vykonávaných „procesorem“ (jednoduchým zásobníkovým počítačem) obsaženým v každém z robotů. Na interpretaci nebude mít toto oddělení překladače a interpretu vliv. Přechodová forma může zůstat před začátečníky skryta a ocení ji pouze ti, kdo budou chtít vidět, co překladač udělá s jejich strukturovaným kódem. Daní za tuto dvoufázovou interpretaci je nutnost rozhodnout, které typy potenciálních chyb budou odchyceny ještě ve fázi překladu, a které až při finálním provádění kódu. Zde upřednostňuji variantu „najít chybu co nejdříve“ a interpretační části ponechat pouze ty chyby, které nelze při překladu odhalit.
3.5
Lokalizace na úrovni klíčových slov jazyka
Zejména pro začátečníky je při výuce programování bariérou i samotné pojmenování klíčových slov jiným jazykem, než je jejich mateřština. Dokonce i subjektivní neintuitivnost klíčového slova může být překážkou. První věcí, která je provedena v každé nové implementaci jazyka Karel, jsou drobné změny v klíčových slovech, popřípadě celková lokalizace.
KAPITOLA 3
14
VYMEZENÍ CÍLŮ
Velkou výhodou by byla možnost si znění jednotlivých klíčových slov (a například i operátorů reprezentovaných slovy namísto znaků) přímo nastavit podle potřeb každého uživatele. U jazyka určeného pro praktické nasazení by to znamenalo drasticky snížit přenositelnost kódu, ale u jazyka pro výuku je to užitečná pomůcka.
3.6
Modulární uživatelské rozhraní
Ideální by bylo oddělit vizualizační část od zbytku programu a definovat pouze rozhraní, které musí případná náhrada vizualizačního modulu obsahovat. Protože ale vizualizaci nelze implementačně jednoduchým způsobem oddělit od vstupní části uživatelského rozhraní [26] a oboje splývá s celkovým řízením aplikace, rozhodl jsem se naopak celý blok pracující s jazykem pojmout jako modul zasaditelný do libovolného uživatelského rozhraní. Výhodou takového řešení je možnost nezávislého řízení různých částí překladače a interpretu i pro potřeby původně nezamýšlené. Možnosti přizpůsobení uživatelského rozhraní se tím dále rozšiřují, aniž by kladly zvýšené nároky na složitost implementace.
KAPITOLA 4
ANALÝZA A NÁVRH
15
4 Analýza a návrh
4.1
Analýza nových prvků jazyka AMOR
Jazyk pro výuku programování založený na jazyce Karel, který splňuje cíle popsané v kapitole 3, můžeme nazvat například A-MOR (což je rekurzivní akronym znamenající A-MOR – More than One Robot). Při jeho analýze je třeba vyjít z mateřského jazyka Karel a všechny nové prvky zapracovat tak, aby byly v co největší shodě s jeho původními syntaktickými rysy. Zatímco klasické imperativní programovací jazyky jsou založené na pojmu výraz a algoritmus vykonávají pomocí sekvencí přiřazení mezi proměnnými [23], základním elementem jazyka typu Karel je příkaz, tedy činnost, kterou virtuální robot provede. Příkazy lze rozdělit takto: •
primitivní příkazy (primitiva) – nejjednodušší typ činností, kterých je robot schopen, jako udělat krok nebo se otočit o čtvrt kruhu doleva
•
složené příkazy – sem patří podmíněný příkaz, podmíněný a počítaný cyklus a případné další konstrukce
•
uživatelské příkazy – uživatelem definované příkazy sestavené z jiných, již známých příkazů (jde tedy o podprogram, případně hlavní program, protože primitiva obvykle nelze provádět samostatně)
Co největší množství nových prvků je tedy vhodné navrhnout jako nové primitivní příkazy, či se jejich filozofii alespoň blížit syntaxí. Znění jednotlivých klíčových slov a jejich navazování by mělo při čtení programu vzbuzovat dojem přirozeného textu. Část tohoto úkolu řeší možnost přizpůsobení klíčových slov, „slovosled“ je především úkolem syntaxe. Jazyky sledující tyto cíle (Basic i původní Karel) se vyznačují „nadbytečným“ používáním klíčových slov i v situacích, kdy nejsou z hlediska syntaktické analýzy potřeba a slouží pouze ke zvýšení čitelnosti programu pro laika (na druhou stranu tím snižují přehlednost, ale to obvykle u krátkých programů nevadí).
4.1.1 Práce s proměnnými, výpočty Mezi požadavky na nový jazyk patří práce s proměnnými - jejich deklarace a výpočty. Kvůli striktnímu oddělení aritmetických a logických výrazů volím pro výpočty s každým typem proměnné jinak pojmenovaný primitivní příkaz (např. Recount pro číselné výpočty a Redecide pro logické). Při deklaraci je možno rozlišit typ klasickým způsobem, tj. identifikátorem typu (např. Memorize Number, Memorize Logic). Různé označení zjednodušuje syntaktickou analýzu a může sloužit i větší intuitivnosti při čtení programu. Pro porovnání číselných výrazů představujících ve výsledku logickou hodnotu jsem zvolil jinou cestu než primitivní příkaz – tyto konstrukce jsou uzavírány do hranatých závorek (např. [ x > y ] ). Tím jsou číselné proměnné oddělené od logických a přitom umožňují vzájemnou interakci během logických výpočtů. Vzhledem k obvyklému použití porovnání následujícím způsobem jsem navíc umožnil porovnání zřetězovat ( [ x > y <= z ] ).
16
KAPITOLA 4
ANALÝZA A NÁVRH
Otázkou je doba platnosti proměnných. Vnášet do jazyka pro začátečníky platnost proměnné omezenou na blok, ve kterém byla deklarována, jako je to obvyklé u plnohodnotných jazyků, není šťastné řešení, protože v jazyce bohatém na klíčová slova existence proměnné opticky zaniká. Ani dynamická deklarace není nejlepší z hlediska přehlednosti a u začátečníků vytváří nedobré návyky. Rozhodl jsem se proto pro platnost proměnné v celém podprogramu, ve kterém byla deklarována. Přenos proměnných mezi podprogramy řeší parametry rozebírané v bodě 4.1.5.
4.1.2 Synchronizace Mechanismus synchronizace při paralelním provádění programů více robotů si žádá další primitivní příkazy, které způsobí, že robot zastaví provádění programu (Sleep) a po signálu od jiného robota (Awake) opět naváže tam, kde přestal. Tím lze simulovat blokující čekání. Pro neblokující verzi stačí klasický podmíněný příkaz doplněný o „prázdnou instrukci“, tedy činnost, během které robot neprovede žádnou změnu u sebe ani okolí a která přesto trvá určitý čas (Wait). Zasílání zpráv mezi roboty lze zařídit například tak, že robot „zamává“ (Wave), přičemž ostatní buď na tuto akci aktivně čekají, nebo si potřebný příznak „robot již zamával“ přečtou ze sdílené proměnné prostředí. Jako analogii ke sdílení a uzamykání prostředků lze použít například atomickou operaci, která označí políčko města na určitých souřadnicích jako majetek daného robota (Annex) a pokus o vstup na něj vyvolá u ostatních robotů běhovou chybu. Párovým příkazem je možnost zabrané políčko znovu uvolnit (Release).
4.1.3 Multitasking robotů Ke střídání programů jednotlivých robotů stačí postupně přepínat mezi jejich interprety. Důležité ovšem je určit atomičnost prováděného kódu, která zabrání přepnutí na jiného robota během provádění kritické sekce. Jako atomická jsem zvolil všechna primitiva, neboť většina z nich podněcuje robota k nějaké akci a pro zachování konzistence prostředí je potřeba, aby ji robot mohl vždy dokončit.
4.1.4 Programy vracející hodnotu Pro podporu programů vracejících hodnotu stačí zavést další primitivní příkaz (Return), který předčasně ukončí prováděný podprogram, když předtím uloží na zásobník interpretu požadovanou návratovou hodnotu. Výjimečnou situací je případ, kdy by měl vracet hodnotu hlavní program obalující ostatní podprogramy. V takovém případě je třeba přeposlat výsledek ven z interpretu k čekajícímu uživateli.
4.1.5 Programy volatelné s parametry Největší zásah do syntaxe původního jazyka znamená předávání parametrů, protože vyhrazovat na to speciální primitivní příkazy by vnášelo do kódu nepřehlednost (assemblerovský model „naskládat na zásobník parametry a provést skok“) a implementační obtíže (parametry na zásobníku by byly v obráceném pořadí). K předávání parametrů proto používám syntaxi podobnou
KAPITOLA 4
ANALÝZA A NÁVRH
17
C nebo Javě. Předání i příjem parametrů je z důvodu sblížení se zbytkem syntaxe uvozeno „nadbytečným“ klíčovým slovem.
KAPITOLA 4
18
4.2
ANALÝZA A NÁVRH
Terminály a neterminály
Než bude popsána gramatika jazyka A-MOR, je třeba se seznámit s použitými terminálními a neterminálními symboly jazyka. Terminály tvoří lexikální elementy jazyka, neterminály slouží k řízení překladu. Tabulka 10: Terminály a neterminály jazyka A-MOR Symbol
N/T
Význam
SubProgram
N
TakenPars
N
TPar1
N
TPar2
N
Block
N
blok příkazů
Command1
N
Command2
N
sled primitiv, složených příkazů nebo volání uživatelsky definovaných příkazů
IfPart
N
ElsePart
N
Atomic
N
Declare1
N
Declare2
N
Count1
N
Count2
N
Decide1
N
Decide2
N
Robot
N
přístup k veřejným proměnným jiného robota
Result
N
primitivní příkaz pro vrácení hodnoty podprogramem
Action
N
volání uživatelsky definovaného příkazu, který nemá návratovou hodnotu
GivenPars
N
GPar1
N
GPar2
N
NumExp1
N
NumExp2
N
NumTerm1
N
NumTerm2
N
NumFakt
N
LogExp1
N
generovaný program (hlavička uživatelsky definovaného příkazu) přijímané parametry podprogramu
podmíněný příkaz některý z primitivních příkazů robota primitivní příkaz pro deklaraci proměnných primitivní příkaz pro celočíselné výpočty primitivní příkaz pro logické výpočty
předávané parametry podprogramu
celočíselné výpočty
logické výpočty
KAPITOLA 4
ANALÝZA A NÁVRH
19
Symbol
N/T
Význam
LogExp2
N
LogTerm1
N
LogTerm2
N
LogFakt
N
Comparison1
N
Comparison2
N
Comparison3
N
kwAction
T
klíčové slovo hlavičky uživatelsky definovaného příkazu deklarující žádnou návratovou hodnotu
kwFunction
T
klíčové slovo hlavičky uživatelsky definovaného příkazu deklarující celočíselnou návratovou hodnotu
kwPredicate
T
klíčové slovo hlavičky uživatelsky definovaného příkazu deklarující logickou návratovou hodnotu
kwEnd
T
klíčové slovo označující konec bloku příkazů nebo složeného příkazu
kwAwaits
T
klíčové slovo uvozující přijímané parametry
kwSends
T
klíčové slovo uvozující předávané parametry
kwRepeat
T
kwTimes
T
kwWhile
T
kwDo
T
kwIf
T
kwThen
T
kwElse
T
kwStep
T
kwLeft
T
kwRight
T
kwPut
T
kwGet
T
kwMemorize
T
kwRecount
T
kwRedecide
T
kwWave
T
kwWait
T
kwAnnex
T
kwRelease
T
řetězové porovnání celočíselných výrazů
klíčová slova počítaného cyklu klíčová slova podmíněného cyklu
klíčová slova podmíněného příkazu
klíčová slova primitivních příkazů robota
KAPITOLA 4
20
ANALÝZA A NÁVRH
Symbol
N/T
Význam
kwSleep
T
kwAwake
T
kwReturn
T
kwNumber
T
klíčové slovo uvozující celočíselný výraz
kwLogical
T
klíčové slovo uvozující logický výraz
kwCity
T
klíčové slovo uvozující použití proměnné prostředí města
kwAnnexed
T
kwFree
T
kwRobot
T
klíčové slovo uvozující použití proměnné prostředí jiného robota
kwRandom
T
klíčové slovo pro náhodnou hodnotu
kwTrue
T
klíčové slovo pro logickou pravdu
kwFalse
T
klíčové slovo pro logickou nepravdu
ident
T
identifikátor
number
T
celé číslo
opAs
T
operátor přiřazení
opAdd
T
opSub
T
opMul
T
opDiv
T
opMod
T
opOr
T
opXor
T
opNot
T
opAnd
T
opEq
T
opNeq
T
opGt
T
opLt
T
opGte
T
opLte
T
(
T
)
T
[
T
]
T
,
T
klíčová slova uvozující čtení příznaku zabraného políčka města
operátory aritmetických výpočtů
operátory logických výpočtů
operátory porovnání celočíselných výrazů
závorky řídící prioritu operátorů / uvozující parametry závorky ohraničující porovnání celočíselných výrazů oddělovač parametrů a vícečetných deklarací / výpočtů v jednom příkazu
KAPITOLA 4
ANALÝZA A NÁVRH
21
Symbol
N/T
Význam
\n
T
konec řádku ukončuje příkazy (na prázdných řádcích se chová jako whitespace [23])
ε
T
prázdný symbol
KAPITOLA 4
22
4.2
ANALÝZA A NÁVRH
Přepisovací pravidla
Jazyk A-MOR je generován LL(1) gramatikou [23], kterou lze zapsat jako seznam přepisovacích pravidel. Ta určují činnost překladače v závislosti na terminálu na vstupu a právě zpracovávaném pravidle. Výsledkem je rozkladová tabulka, která je pro svou velikost umístěna pouze na přiloženém CD. Tabulka 11: Přepisovací pravidla jazyka A-MOR Číslo Levá strana →
Pravá strana
FIRST
1)
SubProgram →
kwAction ident TakenPars Block kwAction
2)
SubProgram →
kwFunction ident TakenPars Block kwFunction
kwFunction
3)
SubProgram →
kwPredicate ident TakenPars Block kwPredicate
kwPredicat e
4)
TakenPars
→ ( kwAwaits Tpar1 Tpar2 )
(
5)
TakenPars
→ε
ε
6)
TPar1
→ kwNumber ident
kwNumber
7)
TPar1
→ kwLogical ident
kwLogical
8)
Tpar2
→ , Tpar1 TPar2
,
9)
TPar2
→ε
ε
→ \n Command1 Command2 kwEnd
\n
10) Block
11) Command1
→ Atomic \n
FOLLOW
kwAction
kwStep kwLeft kwRight kwPut kwGet kwMemoriz e kwRecount kwRedecid e kwWave kwWait kwAnnex kwRelease kwSleep kwAwake kwReturn
\n
)
KAPITOLA 4
ANALÝZA A NÁVRH
Číslo Levá strana →
Pravá strana
23
FIRST
12) Command1
→ Action \n
13) Command1
→
kwRepeat NumExp1 kwTimes Block kwRepeat \n
kwRepeat
14) Command1
→
kwWhile LogExp1 kwDo Block kwWhile \n
kwWhile
15) Command1
→
kwIf LogExp1 kwThen IfPart ElsePart kwIf \n
FOLLOW
ident
kwIf kwStep kwLeft kwRight kwPut kwGet kwMemoriz e kwRecount kwRedecid e kwWave kwWait kwAnnex kwRelease kwSleep kwAwake kwReturn ident kwRepeat kwWhile kwIf
16) Command2
→ Command1 Command2
17) Command2
→ ε
ε
18) IfPart
→ \n Command1 Command2
\n
19) ElsePart
→ kwElse Block
kwElse
20) ElsePart
→ kwEnd
kwEnd
21) Atomic
→ kwStep
kwStep
22) Atomic
→ kwLeft
kwLeft
23) Atomic
→ kwRight
kwRight
24) Atomic
→ kwPut
kwPut
25) Atomic
→ kwGet
kwGet
kwEnd kwElse
KAPITOLA 4
24
Číslo Levá strana →
Pravá strana
ANALÝZA A NÁVRH FIRST
26) Atomic
→ kwMemorize Declare1
kwMemoriz e
27) Atomic
→ kwRecount Count1
kwRecount
28) Atomic
→ kwRedecide Decide1
kwRedecid e
29) Atomic
→ kwWave
kwWave
30) Atomic
→ kwWait
kwWait
31) Atomic
→ kwAnnex NumExp1 , NumExp1
kwAnnex
32) Atomic
→ kwRelease NumExp1 , NumExp1
kwRelease
33) Atomic
→ kwSleep
34) Atomic
→ kwAwake Robot
kwAwake
35) Atomic
→ kwReturn Result
kwReturn
36) Declare1
→
kwNumber ident opAs NumExp1 Declare2
kwNumber
37) Declare1
→
kwLogical ident opAs LogExp1 Declare2
kwLogical
38) Declare2
→ , Declare1 Declare2
,
39) Declare2
→ε
ε
40) Count1
→ ident opAs NumExp1 Count2
41) Count2
→ , Count1 Count2
,
42) Count2
→ε
ε
43) Decide1
→ ident opAs LogExp1 Decide2
44) Decide2
→ , Decide1 Decide2
,
45) Decide2
→ε
ε
46) Robot
→ number
47) Robot
→ ident
48) Result
→ kwNumber NumExp1
kwNumber
49) Result
→ kwLogical LogExp1
kwLogical
50) Action
→ ident GivenPars
51) GivenPars
→ ( kwSends Gpar1 Gpar2 )
(
52) GivenPars
→ε
ε
53) GPar1
→ kwNumber NumExp1
kwNumber
54) GPar1
→ kwLogical LogExp1
kwLogical
55) GPar2
→ , Gpar1 GPar2
,
56) GPar2
→ε
ε
FOLLOW
kwSleep
\n
ident \n
ident \n
number ident
ident \n
)
KAPITOLA 4
ANALÝZA A NÁVRH
Číslo Levá strana →
Pravá strana
25
FIRST ( number kwRandom ident kwCity kwRobot kwFunction
57) NumExp1
→ NumTerm1 NumExp2
58) NumExp1
→ opSub NumTerm1 NumExp2
opSub
59) NumExp2
→ opAdd NumTerm1 NumExp2
opAdd
60) NumExp2
→ opSub NumTerm1 NumExp2
opSub
61) NumExp2
→ ε
FOLLOW
ε
kwTimes kwThen , \n ) opEq opNeq opGt opLt opGte opLte ]
( number kwRandom ident kwCity kwRobot kwFunction
62) NumTerm1
→ NumFakt NumTerm2
63) NumTerm2
→ opMul NumFakt NumTerm2
opMul
64) NumTerm2
→ opDiv NumFakt NumTerm2
opDiv
65) NumTerm2
→ opMod NumFakt NumTerm2
opMod
66) NumTerm2
→ ε
ε
opAdd opSub kwTimes kwThen , \n )
KAPITOLA 4
26
Číslo Levá strana →
Pravá strana
ANALÝZA A NÁVRH FIRST
FOLLOW opEq opNeq opGt opLt opGte opLte ]
67) NumFakt
→ ( NumExp1 )
68) NumFakt
→ number
69) NumFakt
→ kwRandom
70) NumFakt
→ ident
71) NumFakt
→ kwCity ident
72) NumFakt
→ kwRobot Robot ident
73) NumFakt
→ kwFunction ident GivenPars
kwFunction
74) LogExp1
→ LogTerm1 LogExp2
( kwTrue kwFalse kwRandom ident kwCity kwAnnexed kwFree kwRobot kwPredicat e [ opNot
75) LogExp2
→ opOr LogTerm1 LogExp2
opOr
76) LogExp2
→ opXor LogTerm1 LogExp2
opXor
77) LogExp2
→ε
78) LogTerm1
→ LogFakt LogTerm2
( number kwRandom ident kwCity kwRobot
ε
( kwTrue kwFalse kwRandom
kwDo kwThen , \n )
KAPITOLA 4
ANALÝZA A NÁVRH
Číslo Levá strana →
Pravá strana
27
FIRST
FOLLOW
ident kwCity kwAnnexed kwFree kwRobot kwPredicat e [ 79) LogTerm1
→ opNot LogFakt LogTerm2
opNot
80) LogTerm2
→ opAnd LogTerm1 LogTerm2
opAnd
81) LogTerm2
→ ε
ε
82) LogFakt
→ ( LogExp1 )
(
83) LogFakt
→ kwTrue
kwTrue
84) LogFakt
→ kwFalse
kwFalse
85) LogFakt
→ kwRandom
86) LogFakt
→ ident
87) LogFakt
→ kwCity ident
88) LogFakt
→ kwAnnexed NumExp1 , NumExp1
89) LogFakt
→ kwFree NumExp1 , NumExp1
90) LogFakt
→ kwRobot Robot ident
91) LogFakt
→ kwPredicate ident GivenPars
92) LogFakt
→ [ Comparison1 ]
93) Comparison1 → NumExp1 Comparison2
94) Comparison2 → opEq NumExp1 Comparison3
kwRandom ident kwCity kwAnnexed kwFree kwRobot kwPredicat e [ ( number kwRandom ident kwCity kwRobot kwFunction opSub opEq
opOr opXor kwDo kwThen , \n )
28
Číslo Levá strana →
KAPITOLA 4 Pravá strana
95) Comparison2 → opNeq NumExp1 Comparison3
ANALÝZA A NÁVRH FIRST opNeq
96) Comparison2 → opGt NumExp1 Comparison3
opGt
97) Comparison2 → opLt NumExp1 Comparison3
opLt
98) Comparison2 → opGte NumExp1 Comparison3
opGte
99) Comparison2 → opLte NumExp1 Comparison3
opLte
100) Comparison3 → Comparison2 Comparison3
opEq opNeq opGt opLt opGte opLte
101) Comparison3 → ε
FOLLOW
ε
]
KAPITOLA 4
4.3
ANALÝZA A NÁVRH
29
Instrukce zásobníkového počítače
Výsledkem překladu jsou v tomto případě instrukce zásobníkového počítače [23], které jsou v druhé fázi interpretovány virtuálním procesorem uvnitř robota. Tyto instrukce tvoří výstupní abecedu překladové gramatiky jazyka A-MOR. Podrobný popis jejich činnosti je uveden v uživatelské příručce, zde pouze stručný výpis. Tabulka 12: Abeceda zásobníkového počítače Kód
Operandy
Význam Aritmetické operace
(ADD)
(zásobník)
Add
(SUB)
(zásobník)
Subtract
(UNM)
(zásobník)
Unary Minus
(MUL)
(zásobník)
Multiple
(DIV)
(zásobník)
Divide
(MOD)
(zásobník)
Modulo
(INC)
(zásobník)
Increment
(DEC)
(zásobník)
Decrement Logické operace
(AND)
(zásobník)
And
(OR)
(zásobník)
Or
(XOR)
(zásobník)
Exclusive Or
(NOT)
(zásobník)
Not
Operace řetězového porovnávání (EQU)
(zásobník)
Equal
(NEQ)
(zásobník)
Not Equal
(GTT)
(zásobník)
Greater than
(LST)
(zásobník)
Lesser than
(GTE)
(zásobník)
Greater than or Equal
(LTE)
(zásobník)
Lesser than oq Equal
Práce s přímými hodnotami (LIN op)
číslo
Load Immediate Number
(LIL op)
log. hodnota
Load Immediate Logical
(TIN op)
identifikátor
Translate Identificator to Number
(LRN)
-
Load Random Number
(LRL)
-
Load Random Logical Práce s proměnnými
KAPITOLA 4
30
ANALÝZA A NÁVRH
Kód
Operandy
Význam
(LCV op)
identifikátor
Load City Variable
(LRV op)
identifikátor (+ zásobník)
Load Robot Variable
(LDV op)
identifikátor
Load Variable
(STV op)
identifikátor (+ zásobník)
Store Variable
(LAF)
(zásobník)
Load Annexed Flag Práce s parametry
(STP)
(zásobník)
Store Parameter
(LDP)
(zásobník)
Load Parameter Skoky
(IFJ op)
absolutní adresa
If False Jump
(ITJ op)
absolutní adresa
If True Jump
(IZJ op)
absolutní adresa
If Zero Jump
(JPA op)
absolutní adresa
Jump to Absolute Address
(JPR op)
relativní adresa
Jump to Relative Address
(GSB op)
absolutní adresa
Go to Subprogram
(RET)
-
Return from Subprogram Instrukce robota
(STE)
-
Step
(LFT)
-
Turn Left
(RGH)
-
Turn Right
(PUT)
-
Put Mark
(GET)
-
Get Mark
(WAV)
-
Wave
(WAT)
-
Wait
(SLE)
-
Sleep
(AWK)
(zásobník)
Awake
(ANX)
(zásobník)
Annex Coordinate
(RLS)
(zásobník)
Release Coordinate Ostatní operace
(TCL)
-
Timer Clock
(SWP)
(zásobník)
Swap
(POP)
(zásobník)
Pop
(NOP)
-
No Operation
KAPITOLA 4
4.4
ANALÝZA A NÁVRH
31
Dodatečné výstupní operace
Kromě skutečně generovaných instrukcí jsou při překladu vykonávány ještě další operace, které slouží k odhalení všech chyb zjistitelných během překladu a ke správě postupně vznikajícího seznamu uživatelských příkazů, které budou při interpretaci prováděny. Žádná z těchto operací se v generovaném kódu neobjeví jako instrukce. Tabulka 13: Dodatečné výstupní operace Pseudokód (DSP op)
(DCV op)
(CVT op)
Operand
Význam
Činnost
identifikátor
Declare Subprogram
nový záznam do tabulky podprogramů (typ podprogramu se určuje podle právě zpracovávaného pravidla)
Declare Variable
nový záznam do tabulky proměnných / duplicitní chyba (typ proměnné se určuje podle zpracovávaného pravidla)
Check Variable Type
kontrola typu proměnné (číselné a logické hodnoty nelze konvertovat) daného zpracovávaným pravidlem + kontrola existence
identifikátor
identifikátor
kontrola typu předávaného parametru před Check Parameter jeho převedením na proměnnou + kontrola Type prázdné předávací fronty (odpovídá kontrole počtu parametrů)
(CPT)
(fronta parametrů)
(CRT)
(zásobník)
Check Result Type
kontrola typu návratové hodnoty
(NPT op)
identifikátor (+ pomocný zásobník)
New Parameter Target
změna cíle deklarovaných parametrů (volání podprogramu s parametry)
(RPT)
(pomocný zásobník)
Restore Parameter Target
obnova cíle deklarovaných parametrů (volání podprogramu s parametry)
(SPT)
(fronta parametrů)
Store Parameter Type
uložení typu předávaného parametru do fronty (pro kontrolu parametrů v době překladu)
(FAD)
(aktuální adresa)
Fill Address
doplnění aktuální adresy do tabulky příkazů
Label
označuje adresu umístění pseudonávěští (dosazuje operand do instrukcí (IFJ), (ITJ), (IZJ))
(LAB op)
adresa
KAPITOLA 4
32
4.5
ANALÝZA A NÁVRH
Překladová gramatika
Překladová gramatika dává do souvislosti průchod překladačem a generování výstupních symbolů (zde instrukcí interpretu robota). Tabulka 14: Překladová gramatika jazyka A-MOR 1)
SubProgram → kwAction ident (FAD) TakenPars Block kwAction (RET)
2)
SubProgram → kwFunction ident (FAD) TakenPars Block kwFunction (RET)
3)
SubProgram → kwPredicate ident (FAD) TakenPars Block kwPredicate (RET)
4)
TakenPars
→ ( kwAwaits Tpar1 Tpar2 )
5)
TakenPars
→ ε (CPT)
6)
TPar1
→ kwNumber (CPT) ident (DCV ident) (LDP) (STV ident)
7)
TPar1
→ kwLogical (CPT) ident (DCV ident) (LDP) (STV ident)
8)
Tpar2
→ , Tpar1 TPar2
9)
TPar2
→ ε
10) Block
→ \n Command1 Command2 kwEnd
11) Command1
→ Atomic \n
12) Command1
→ Action \n
13) Command1
→
kwRepeat NumExp1 kwTimes (LAB lb1) (IZJ [lb2]) Block (DEC) (JPA [lb1]) (LAB lb2) kwRepeat \n
14) Command1
→
kwWhile (LAB lb1) LogExp1 kwDo (IFJ [lb2]) Block (JPA [lb1]) (LAB lb2) kwWhile \n
15) Command1
→
kwIf LogExp1 kwThen (IFJ [lb1]) IfPart (JPA [lb2]) (LAB lb1) ElsePart (LAB lb2) kwIf \n
16) Command2
→ Command1 Command2
17) Command2
→ ε
18) IfPart
→ \n Command1 Command2
19) ElsePart
→ kwElse Block
20) ElsePart
→ kwEnd
21) Atomic
→ kwStep (STE) (TCL)
22) Atomic
→ kwLeft (LFT) (TCL)
23) Atomic
→ kwRight (RGH) (TCL)
24) Atomic
→ kwPut (PUT) (TCL)
25) Atomic
→ kwGet (GET) (TCL)
26) Atomic
→ kwMemorize Declare1 (TCL)
27) Atomic
→ kwRecount Count1 (TCL)
28) Atomic
→ kwRedecide Decide1 (TCL)
KAPITOLA 4
ANALÝZA A NÁVRH
29) Atomic
→ kwWave (WAV) (TCL)
30) Atomic
→ kwWait (WAT) (TCL)
31) Atomic
→ kwAnnex NumExp1 , NumExp1 (ANX) (TCL)
32) Atomic
→ kwRelease NumExp1 , NumExp1 (RLS) (TCL)
33) Atomic
→ kwSleep (SLE) (TCL)
34) Atomic
→ kwAwake Robot (AWK) (TCL)
35) Atomic
→ kwReturn Result (SWP) (TCL) (RET)
36) Declare1
→
kwNumber ident (DCV ident) opAs NumExp1 (STV ident) Declare2
37) Declare1
→
kwLogical ident (DCV ident) opAs LogExp1 (STV ident) Declare2
38) Declare2
→ , Declare1 Declare2
39) Declare2
→ ε
40) Count1
→ ident opAs NumExp1 (CVT ident) (STV ident) Count2
41) Count2
→ , Count1 Count2
42) Count2
→ ε
43) Decide1
→ ident opAs LogExp1 (CVT ident) (STV ident) Decide2
44) Decide2
→ , Decide1 Decide2
45) Decide2
→ ε
46) Robot
→ number (LIN number)
47) Robot
→ ident (TIN ident)
48) Result
→ kwNumber (CRT) NumExp1
49) Result
→ kwLogical (CRT) LogExp1
50) Action
→ ident (DSP ident) (NPT ident) GivenPars (RPT) (GSB [ident])
51) GivenPars
→ ( kwSends Gpar1 Gpar2 )
52) GivenPars
→ ε
53) GPar1
→ kwNumber NumExp1 (SPT) (STP)
54) GPar1
→ kwLogical LogExp1 (SPT) (STP)
55) GPar2
→ , Gpar1 GPar2
56) GPar2
→ ε
57) NumExp1
→ NumTerm1 NumExp2
58) NumExp1
→ opSub NumTerm1 (UNM) NumExp2
59) NumExp2
→ opAdd NumTerm1 (ADD) NumExp2
60) NumExp2
→ opSub NumTerm1 (SUB) NumExp2
61) NumExp2
→ ε
62) NumTerm1
→ NumFakt NumTerm2
33
KAPITOLA 4
34
ANALÝZA A NÁVRH
63) NumTerm2
→ opMul NumFakt (MUL) NumTerm2
64) NumTerm2
→ opDiv NumFakt (DIV) NumTerm2
65) NumTerm2
→ opMod NumFakt (MOD) NumTerm2
66) NumTerm2
→ ε
67) NumFakt
→ ( NumExp1 )
68) NumFakt
→ number (LIN number)
69) NumFakt
→ kwRandom (LRN)
70) NumFakt
→ ident (CVT ident) (LDV ident)
71) NumFakt
→ kwCity ident (CVT ident) (LCV ident)
72) NumFakt
→ kwRobot Robot ident (CVT ident) (LRV ident)
73) NumFakt
→
74) LogExp1
→ LogTerm1 LogExp2
75) LogExp2
→ opOr LogTerm1 (OR) LogExp2
76) LogExp2
→ opXor LogTerm1 (XOR) LogExp2
77) LogExp2
→ ε
78) LogTerm1
→ LogFakt LogTerm2
79) LogTerm1
→ opNot LogFakt (NOT) LogTerm2
80) LogTerm2
→ opAnd LogTerm1 (AND) LogTerm2
81) LogTerm2
→ ε
82) LogFakt
→ ( LogExp1 )
83) LogFakt
→ kwTrue (LIL true)
84) LogFakt
→ kwFalse (LIL false)
85) LogFakt
→ kwRandom (LRL)
86) LogFakt
→ ident (CVT ident) (LDV ident)
87) LogFakt
→ kwCity ident (CVT ident) (LCV ident)
88) LogFakt
→ kwAnnexed NumExp1 , NumExp1 (LAF)
89) LogFakt
→ kwFree NumExp1 , NumExp1 (LAF) (NOT)
90) LogFakt
→ kwRobot Robot ident (CVT ident) (LRV ident)
91) LogFakt
→
92) LogFakt
→ [ (LIL true) Comparison1 (POP) ]
kwFunction ident (DSP ident) (NPT ident) GivenPars (RPT) (GSB [ident])
kwPredicate ident (DSP ident) (NPT ident) GivenPars (RPT) (GSB [ident])
93) Comparison1 → NumExp1 Comparison2 94) Comparison2 → opEq NumExp1 (EQU) Comparison3 95) Comparison2 → opNeq NumExp1 (NEQ) Comparison3 96) Comparison2 → opGt NumExp1 (GTT) Comparison3
KAPITOLA 4
ANALÝZA A NÁVRH
97) Comparison2 → opLt NumExp1 (LST) Comparison3 98) Comparison2 → opGte NumExp1 (GTE) Comparison3 99) Comparison2 → opLte NumExp1 (LTE) Comparison3 100) Comparison3 → Comparison2 Comparison3 101) Comparison3 → ε
35
KAPITOLA 4
36
ANALÝZA A NÁVRH
4.6 Návrh aplikace Aplikace umožňující práci s jazykem A-MOR musí zahrnovat překladač, interpret, vstupně/výstupní část zajišťující práci se soubory a komunikaci s uživatelem a také vizualizační část zobrazující činnost virtuálních robotů. Součástí pokynů je i modulární řešení umožňující snadnou výměnu této vizualizační části tak, aby mohlo být základní textové rozhraní v budoucnu nahrazeno atraktivnějším grafickým.
4.6.1 Překladač Součástí překladače obvykle bývá [23] • •
frontend zajišťující lexikální analýzu a překlad do vnitřní formy backend provádějící optimalizace a výslednou kompilaci do strojového kódu nebo interpretaci programu ve vnitřní formě
Protože A-MOR je jazyk interpretovaný ve smyslu provádění instrukcí zásobníkového počítače, je jeho interpret oddělený od překladače. Protože jde navíc o jazyk určený pro výuku a porozumění vnitřnímu fungování počítače, není prioritou optimalizovaný chod, ale naopak co největší čitelnost přeloženého programu i v podobě sledu instrukcí. Funkce překladače tedy odpovídá pouze frontendu. Lexikální analyzátor je třeba navrhnout tak, aby umožňoval editaci klíčových slov jazyka. To znamená, že klíčová slova budou rozpoznávána jako speciální případ identifikátoru. Z konfiguračních souborů se nahraje při startu programu do paměti tabulka představující podoby jednotlivých klíčových slov a lexikální analyzátor každý nalezený identifikátor porovná napřed s jejím obsahem. Omezí se tím množina identifikátorů použitelných k pojmenování proměnných, ale celkový dopad je zanedbatelný. Překladač využívá klasického rekurzivního sestupu, překladu řízeného syntaxí [23]. Protože nebude výsledný kód interpretovat, není tu potřeba atributová gramatika. Naproti tomu je kladen důraz na schopnost překladače rozpoznat co nejvíce sémantických chyb. K tomu slouží dodatečné výstupní operace jazyka popsané v bodě 4.4.
4.6.2 Interpret Interpret je klasickým zásobníkovým počítačem s drobným vylepšením umožňujícím jednodušší předávání parametrů. Protože velká část instrukcí odpovídá přímo primitivním příkazům robota a protože smyslem jazyka A-MOR je umožnit paralelní běh více robotů, je interpret součástí robota a doplňuje tak jeho jinak datovou podstatu. Každý z robotů bude mít vlastní paměť programu i dat a v patřičné analogii bude představovat svého druhu virtuální program s přidělenou pamětí. Toto zapouzdření vynucuje další entitu (centrální časovač), která by řídila přepínání mezi interprety jednotlivých robotů. Z pohledu analogie by šlo o procesor přepínající mezi jednotlivými programy. Toto přepínání musí dodržovat určitou stanovenou atomičnost robotových operací. Využito je zde principu podobného kooperativnímu multitaskingu [27], kdy každý robot provádí svůj program, dokud nenarazí na speciální instrukci určenou k návratu řízení časovači. Přítomnost
KAPITOLA 4
ANALÝZA A NÁVRH
37
této instrukce na patřičných místech robotova programu vynucuje překladová gramatika, která tuto instrukci umisťuje za každý primitivní příkaz. Časovač řídící přepínání mezi interprety robotů by měl obsahovat nedeterministický prvek, který přiměje programátora robotů k využití synchronizačních nástrojů. Implementace to může řešit např. funkcí která zpřehází pořadí robotů při čekání na procesorový čas. Tato funkce může být buď čistě náhodná, nebo například upřednostňovat některé roboty.
4.6.3 Práce se soubory Část aplikace vyhrazená pro souborové operace musí umožnit zejména načítání konfiguračních souborů a zdrojových textů pro lexikální analyzátor zabudovaný v překladači. Rovněž je jejím úkolem zapisovat vygenerovaný kód do souborů, odkud je bude následně načítat pro jednotlivé interprety. Čtení zdrojových textů je vhodné zařídit tak, aby se minimalizoval počet přístupů na disk.
4.6.4 Uživatelské rozhraní Vzhledem k tomu, jak úzce je v návrhu aplikací svázána část pro prezentaci a pro komunikaci s uživatelem [26], je nepraktické řešit jako vyměnitelnou pouze vizualizaci práce robotů. Řešením by bylo spojit vizualizaci a komunikaci do jednoho modulu a oddělit je od zbytku aplikace, která by měla vstupní bod v „jádře“ zprostředkovávajícím pouze komunikaci mezi jednotlivými částmi. Ve skutečnosti je ale právě uživatelské rozhraní obvyklým vstupním bodem aplikace a přenesení této úlohy na abstraktní „jádro“ vytvořené jen za tímto účelem postrádá smysl. Je tedy uživatelské rozhraní včetně části určené pro vizualizaci „základem“ aplikace, do které je teprve modulárně dodáno vše ostatní, ale zároveň je třeba udržet toto rozhraní co nejjednodušší, aby bylo snadno vyměnitelné. Funkcionalita musí být proto obsažena především v již popsaných částech a uživatelské rozhraní ji v maximální míře využívat.
4.6.5 Datová část Právě popsané moduly tvoří řídící část aplikace. Její datovou částí jsou především roboti (pomineme-li, že jejich součástí je interpret spadající do řízení) a město. Doplňuje je konfigurace, která musí pojmout nastavení samotné aplikace (umístění zdrojů, omezení vstupů) a nastavitelné vlastnosti jazyka (konkrétní podoba klíčových slov, znění chybových hlášení). Každý robot si musí udržovat informace o svém stavu a obsahuje i datové položky interpretu, které zahrnují paměť programu a dat, tabulku s uživatelskými příkazy, které robot momentálně zná, a tabulky k příkazům příslušejících proměnných. Město zahrnuje zejména data tvořící jeho strukturu, tj. velikost a informace o poloze zdí, značek a robotů. Udržuje rovněž informace týkající se společně všech jeho obyvatel, které roboti jednotlivě nést nemohou.
KAPITOLA 5
38
POPIS IMPLEMENTACE
5 Popis implementace Aplikace pokrývající překladač, interpret, nezbytné rozhraní a datovou část byla implementována v jazyce C++. Na přiloženém CD je k dispozici základní verze aplikace, která k implementaci uživatelského rozhraní využívá knihovnu ncurses; dále testovací verze přizpůsobená rozhraním pro využití testovacích skriptů a experimentální verze s grafickým rozhraním implementovaným za použití knihovny Qt. Účelem více verzí je demonstrovat snadnou výměnu uživatelského rozhraní. Každá z verzí obsahuje implementační zdrojové soubory v adresáři src/ členěném následovně: •
•
•
•
control/ (adresář se zdrojovými soubory odpovědnými za běh aplikace) •
fileIo.cpp (souborový vstupně / výstupní podsystém)
•
timer.cpp (centrální časovač řídící běh interpretů jednotlivých robotů)
•
translator.cpp (lexikální analyzátor a překladač do jazyka zásobníkového počítače)
•
UserIo.cpp (třída implementující uživatelské rozhraní)
data/ (adresář se zdrojovými soubory tvořícími datovou část aplikace) •
City.cpp (třída reprezentující město)
•
Robot.cpp (třída reprezentující robota + vnořená třída reprezentující interpret)
•
common.cpp (globální proměnné zastupující město a roboty)
•
config.cpp (konfigurace programu načítaná z hlavního konfiguračního souboru)
•
language.cpp (pomocné struktury jazyka využívané překladačem a interpretem)
support/ (adresář s pomocnými třídami použitými při implementaci) •
Array.h* (generické pole proměnné délky)
•
Queue.h* (generická fronty)
•
Stack.h* (generický zásobník)
•
String.cpp (třída pro práci s řetězci)
main.cpp (vstupní bod programu, inicializuje uživatelské rozhraní nebo s ním může splývat)
Hlavičkové soubory jsou umístěny v adresáři include/ členěném stejným způsobem. Soubory označené ve výčtu hvězdičkou jsou šablony implementované v rámci hlavičkových souborů, nacházejí se tedy v adresáři include/. Jednotlivé verze aplikace se odlišují pouze v souborech UserIo.cpp (a odpovídajícím hlavičkovém souboru) a main.cpp a pouze tyto soubory je třeba nově implementovat pro změnu uživatelského rozhraní.
5.1 Pomocné třídy Pro usnadnění implementace jsou součástí zdrojových souborů tyto třídy:
KAPITOLA 5 •
•
•
implementuje generické rozšiřitelné pole
•
obsahuje metodu add( ), která umožňuje postupné přidávání prvků na konec pole
•
obsahuje metodu clr( ), která vymaže celý obsah pole a připraví ho tím k novému použití
•
přetěžuje operátor [ ], čímž umožňuje přístup ke svému obsahu pomocí indexování
•
používá se především k uchování zdrojového textu a jeho snadnému zpracování a dále při načítání konfiguračních souborů k uchování předem neznámého počtu položek
Queue
implementuje generickou frontu
•
obsahuje metody push( ), pop( ) a top( ) pro přidávání, odebírání a čtení elementů
•
obsahuje metodu rotate( ), která přesune elementy ve směru ode dna fronty k jejímu čelu a první element přesune na konec
• •
přetěžuje operátory == a !=, čímž umožňuje snadné porovnávání svých instancí používá se především jako rozšiřitelná tabulka k uložení sekvenčně přístupného obsahu
Stack •
•
39
Array
•
•
POPIS IMPLEMENTACE
implementuje generický zásobník
•
obsahuje metody push( ), pop( ) a top( ) pro přidávání, odebírání a čtení elementů
•
používá se především jako paměť dat zásobníkového počítače a k přepínání kontextu při přechodu do podprogramu a zpět
String •
implementuje znakové řetězce
•
mimo jiné přetěžuje operátory +, +=, ==, !=, [ ], << a přiřazení pro typ char*
•
i když není výkonná jako třídy ve standardní knihovně, lépe vyhovuje požadavkům kladeným v této aplikaci
5.2 Globální prvky Implementace není přísně objektová, pro její účely to ani není potřebné. Objekty jsou použity jenom tam, kde mají odůvodnění, a zbytek aplikace je tvořen klasicky procedurálně. Tam, kde to má smysl, jsou použity i globální prvky, zahrnující zejména definice struktur používaných napříč všemi částmi aplikace. Ty jsou sdružovány podle svého určení do příslušných modulů a pro přehlednost obvykle „zapouzdřeny“ do speciálního jmenného prostoru totožného se jménem modulu.
KAPITOLA 5
40
POPIS IMPLEMENTACE
Společným prvkem celé aplikace je práce s množinou robotů a městem, ve kterém se pohybují. Proto modul common.h zavádí ukazatel na typ City (city) a generickou frontu ukazatelů na typ Robot (robots). Instance pro tyto ukazatele jsou vytvořeny při nahrávání úlohy. specifikuje výčtový typ LexSymb s lexikálními elementy vstupní abecedy (konkrétní podoba je získána z konfiguračních souborů a LexSymb slouží k přístupu k ní pomocí indexování), výčtové typy pro klasifikaci typů proměnných (VarType) a jejich přístupových práv (VarAccess). Dále jsou zavedeny struktury pro snadnou manipulaci s proměnnými (Variable, VariableTable), příkazy (Command, CommandTable) a generovanými instrukcemi (Instr). Součástí jsou i generická pole pro konfigurovatelné lexikální elementy jazyka, názvy proměnných prostředí a znění chybových hlášení. Modul language.h
Modul config.h vyváží cesty k jednotlivým adresářům s datovými a konfiguračními soubory, obsahuje značku používaného lokalizačního setu a platná omezení pro města a roboty.
5.3 Činnost aplikace po spuštění Vstupním bodem aplikace je metoda main( ) v souboru main.cpp. Jejím úkolem je nahrání konfigurace a inicializace uživatelského rozhraní. Hlavní
konfigurace
fileIo::loadConfig( ).
je čtena Obsahuje:
z
textového
souboru
•
cestu k adresáři s úlohami
•
cestu k adresáři s městy
•
cestu k adresáři se zdrojovými texty příkazů
•
cestu k adresáři, kam se má ukládat vygenerovaný kód
•
cestu k souboru s konfiguracemi klíčových slov jazyka
•
cestu k souboru s konfiguracemi proměnných prostředí města
•
cestu k souboru s konfiguracemi proměnných prostředí robota
•
cestu k souboru s konfiguracemi chybových hlášení
•
a-mor.conf
použitou lokalizační značku (určuje, které části výše popsaných konfiguračních souborů budou využity)
•
maximální rozměr města v ose x (implementace podporuje max. 99)
•
maximální rozměr města v ose y (implementace podporuje max. 99)
•
funkcí
maximální rozměr města v ose z (implementace podporuje max. 99, ale momentálně podporuje pouze zdi jako převýšení 2 a více)
•
maximální počet robotů ve městě (implementace podporuje max. 8)
•
maximální počet značek na jednom políčku města (implementace podporuje max. 99)
•
maximální zanoření při rekurzi
KAPITOLA 5
POPIS IMPLEMENTACE
41
Tyto informace se ukládají do proměnných typu char* a int deklarovaných souborem Jakmile program zná cestu k dalším konfiguračním souborům a používanou lokalizační značku, pokračuje zpracováním: config.h.
•
souboru s definicí chybových hlášení
•
souboru s proměnnými prostředí města
•
souboru s proměnnými prostředí robota
•
souboru s definicí klíčových slov jazyka
Poté je inicializováno uživatelské rozhraní. Ve všech verzích implementace je napřed deklarována instance třídy UserIo a následně zavolána její metoda initialize( ), která v závislosti na konkrétním typu rozhraní provede úkony nezbytné k další práci modulu. Metodě lze předat char* - převzatý z příkazového řádku při spouštění aplikace - který obsahuje jméno spouštěné úlohy. Součástí metody initialize( ) je obvykle i přebrání řízení aplikace, úloha funkce main( ) tím končí.
5.4 Uživatelské rozhraní Uživatelské rozhraní je implementováno dvojicí souborů UserIo.h a UserIo.cpp. Jejich úkolem je zavést třídu UserIo, která poskytuje metody: •
initialize ( )
•
loadTask( )
•
•
- základní inicializace
- nahrání úlohy ze zdrojového souboru
proceedTask( ) - spuštění překladu do jazyka zásobníkového počítače pro všechny programy všech robotů resetTask( )
- uvedení všech robotů a jejich interpretů do základního nastavení
•
- pokyn ústřednímu časovači ke spuštění interpretu jednoho z robotů po dobu trvání jednoho primitivního příkazu
•
- pokyn ústřednímu časovači k automatickému střídavému chodu interpretů až do stavu, kdy všichni roboti dokončí své programy, nebo některý z nich způsobí interpretační chybu / informativní hlášení (po jeho zobrazení je úloha pouze pozastavena, v případě chyby už není možné v interpretaci pokračovat)
stepTask( )
runTask(
)
V závislosti na konkrétní implementaci uživatelského rozhraní je možné se tohoto schématu držet, nebo použít vlastní řešení. Výše uvedené funkce jsou použity ve všech verzích aplikace implementovaných touto prací. Uživatelské rozhraní (nebo v případě jeho minimalizace nadřazená část aplikace) postupně spouští: •
•
metodu loadTask( ) - s parametrem předaným při inicializaci nebo získaným interakcí s uživatelem metodu proceedTask( ) - automaticky nebo na pokyn uživatele
KAPITOLA 5
42
POPIS IMPLEMENTACE
Po vykonání prvního bodu je nahrána úloha včetně podoby města a počátečního nastavení robotů, je tedy možné provést první vykreslení. Po zavolání druhé z metod jsou přeloženy zdrojové texty programů každého z robotů a je možno zahájit interpretaci. To se může dít: •
spuštěním runTask( ) - automaticky nebo na pokyn uživatele
•
spuštěním stepTask( ) - na pokyn uživatele
V případě, že není spuštěna automatická interpretace až do skončení všech programů, lze do ní v libovolném bodě zasáhnout metodou resetTask( ), která vrátí úlohu do její původní podoby po nahrání, případně novým voláním loadTask( ) pro nahrání úlohy nové. Implementovaná verze s textovým rozhraním se chová podle výše uvedeného schématu a po dokončení práce všech interpretů skončí. Experimentální verze s grafickým rozhraním umožňuje navíc v libovolném okamžiku, kdy interpretace neběží, nahrát úlohu jinou. Verze určená pro testování neobsahuje interaktivní rozhraní – nadřazená metoda main( ) spouští initialize( ) a vzápětí runTask( ).
5.4 Podsystém pro práci se soubory Funkce a datové struktury pro práci se soubory jsou obsaženy v hlavičkovém souboru fileIo.h a implementačním souboru fileIo.cpp. Pro zpracování konfiguračních souborů je použita funkce proceedLine( ifstream* ), která zpracuje jeden řádek textového souboru zakončený escape znakem [28] \n (znaky \r jsou ignorovány stejně jako řádky začínající #). Na řádku jsou rozeznávány: •
klíče, tj. řetězce začínající písmenem, číslicí nebo podtržítkem a tvořené týmiž druhy znaků nebo dvojtečkou (kvůli správnému čtení návěští ve vygenerovaných souborech s kódem pro interpret)
•
volby, tj. řetězce tvořené písmeny, číslicemi a znaky _ : . / \ , ( ) [ ] + - ; < > a mezerou uzavřené do uvozovek
•
čísla, tj. řetězce tvořené číslicemi, případně uvozené pomlčkou, uzavřené do špičatých závorek
Výsledek po zpracování řádku je uložen v generických polích keys, options a integers. Před zpracováním každého řádku jsou obsahy těchto polí smazány, je tedy potřeba načtené hodnoty dále zpracovat před dalším čtením. Čtení konfiguračních souborů probíhá opakovaným voláním proceedLine( ). Ke správné funkci je třeba, aby soubory obsahovaly požadované údaje na očekávaných místech – aplikace nemá implementovány prostředky, které by prováděly kontrolu nebo umožňovaly zotavení po načtení neočekávaných dat. Při jakémkoli problému během načítání konfigurace program končí chybou. Po pokynu uživatelského rozhraní je načten soubor s úlohou pomocí funkce loadTask( ) (jméno je shodou okolností totožné s metodou v UserIo). I zde je využita funkce proceedLine( ) k postupnému získávání informací o úloze. Očekávány jsou: •
jméno města
KAPITOLA 5
POPIS IMPLEMENTACE
43
•
počet využitých robotů (soubor s městem obsahuje mapu jejich rozmístění, ale nemusí být využiti všichni)
•
seznam robotů obsahující jejich identifikační číslo v plánku města, jméno, zpracovávaný příkaz a pozici políčka, které je robotovým domovem
Bezprostředně po načtení jména města je zpracován i soubor s městem, aby mohly být informace z něj využity při zbytku zpracování úlohy. Soubor města obsahuje: •
rozměr města v ose x
•
rozměr města v ose y
•
mapu města obsahující výškové informace o jednotlivých políčkách
•
mapu města obsahující počet značek na jednotlivých políčkách
•
mapu města obsahující rozmístění robotů
Protože proměnné prostředí města a robotů se načítají ve fázi konfigurace aplikace a konkrétní hodnoty parametrů jsou známy až po načtení konkrétní úlohy, zavádí souborový podsystém několik generických polí, která v mezičase přechovávají potřebné informace o proměnných prostředí. Soubory se zdrojovými texty jsou načítány znak po znaku do generického pole pomocí funkce loadFileToArray( ). Poté je zpracovává lexikální analyzátor a překladač. Vygenerovaný kód je umístěn do generického pole a ukládán do souboru odpovídajícího jménem hlavnímu programu robota funkcí saveCodeToFile( ). Interpret si ho pak zpětně načítá (okamžiky uložení a načtení od sebe může dělit překlad dalších souborů, proto k předání nedochází přímo) funkcí loadCodeFromFile( ). Protože má výsledný kód podobu sekvence řádků s několika řetězci, je při jeho čtení opět využita funkce proceedLine( ).
5.5 Lexikální analyzátor a překladač Obě tyto součásti jsou implementovány v souboru translator.cpp a specifikovány příslušném hlavičkovém souboru translator.h. Pro překlad jsou používány datové typy a struktury popsané v bodě 5.2. Datová část překladače obsahuje pomocnou tabulku příkazů (CommandTable) a generický zásobník na příkazy, dále tabulku a frontu proměnných pro práci s proměnnými prostředí robota a práci s předávanými parametry, rovněž paměti programu a dat tvořené generickým zásobníkem pro typ int, resp. generickým polem pro typ Instr. Činnost překladače zahajuje zavolání funkce translateAll( ). Ta v cyklu projde globální frontu robotů a po inicializaci pomocných struktur spustí funkcí runTransl( ). Do tabulky proměnných předtím vloží první prvek, kterým je program se jménem určeným v souboru úlohy a adresou první instrukce v paměti programu rovné -1 (odpovídající stavu „nepřeložený příkaz“). Z pohledu funkce runTransl( ) jde vždy o překlad kolekce programů pro jediného robota. Její činnost spočívá v překládání prvního příkazu s počáteční adresou -1, na který v tabulce příkazů narazí, a to opakovaně až do doby, kdy tabulka žádný takový obsahovat nebude (nové příkazy jsou do tabulky přidávány během rekurzivního sestupu při prvním objevení neznámého identifikátoru).
44
KAPITOLA 5
POPIS IMPLEMENTACE
Překlad příkazu je vždy zahájen inicializací lexikálního analyzátoru funkcí initLexan( ). Jako parametr je předáno jméno příkazu doplněné o implicitní koncovku .txt. Lexikální analyzátor pak požádá souborový podsystém o načtení zdrojového souboru stejného jména. Následuje přečtení prvního lexikálního elementu funkcí readToken( ) a rekurzivní sestup podle pravidel definovaných v kapitole 4. Funkce readToken( ) rozpoznává operátory, čísla a řetězce. Každý řetězec je porovnán s tabulkou lexikálních elementů načtenou během zpracování konfigurace. Pokud není v tabulce nalezen, je klasifikován jako identifikátor, v opačném případě jako klíčové slovo, případně operátor. Klasické operátory tvořené znaky jsou rozpoznávány rovněž, a to podle pravidel zakotvených přímo ve zdrojovém souboru překladače. Lexikálním elementem je i konec řádku (escape znak \n), ale analyzátor ho jako takový rozpoznává pouze tehdy, pokud už řádek obsahuje užitečný obsah (není plný mezer apod.). K tomu slouží příznak whiteLine, který je implicitně nastaven jako true a do false ho shazuje výskyt lexikálního elementu na daném řádku. Nestane-li se to, je konec řádku opomíjen jako whitespace společně s mezerami a escape znaky \t a \r. Na úrovni lexikální analýzy je rovněž detekováno překročení podporovaného rozsahu při práci s celočíselnými hodnotami – cifry delší než devět znaků jsou hlášeny jako chyba. Tento způsob dovoluje mylné chybové hlášení pro čísla typu 0000000001, ale protože se nepředpokládá takový způsob zápisu, není tato výjimka ošetřena. Lexikální analyzátor podporuje i jednořádkové komentáře – po nalezení znaku # je zbytek řádku ignorován. Doplnění podpory blokových komentářů by nebylo obtížné, ale pro zvýšení přehlednosti a vzhledem k cílové skupině uživatelů se jejich použití nepředpokládá. V rámci syntaxí řízeného překladu je zajímavá práce s proměnnými, parametry a s podprogramy vracejícími hodnotu. Informace o proměnných a parametrech jsou udržovány zvlášť pro každý příkaz v tabulce příkazů. Při deklaraci proměnné je do tabulky proměnných daného příkazu přidán nový záznam. Při jejím dalším použití je kontrolován typ v závislosti na právě zpracovávaném pravidle (celočíselné a logické výpočty jsou odděleny na úrovni syntaxe). Je-li jméno deklarované proměnné v konfliktu s některou proměnnou prostředí města nebo robota, je vyvolána chyba. Proměnné se mohou jmenovat stejně jako existující uživatelské příkazy – záměna není možná vzhledem k syntaktickým pravidlům. Při volání podprogramu společně s předáním parametrů je nejdříve deklarován nový podprogram a parametry jsou uloženy do jeho fronty parametrů, kde zůstanou, dokud se postupně pracující překladač nedostane k překladu volaného podprogramu. Během zpracování jeho hlavičky pak zkontroluje, zda souhlasí počet a typ předávaných parametrů, a převede je na odpovídající proměnné. Je-li již dříve volaný podprogram volán znovu a nebyl dosud přeložen, je třeba zkontrolovat, zda parametry při prvním volání souhlasí s parametry předávanými nyní (přetěžování podprogramů není podporováno). Protože je předávání parametrů realizováno v rekurzivním sestupu níže než volání podprogramu, musí překladač dočasně uložit již existující frontu parametrů, nechat proběhnout vytvoření nové fronty a obě verze porovnat. Situaci činí složitější ještě možnost, že předávaný parametr tvoří podprogram, který má rovněž parametry a může u něj
KAPITOLA 5
POPIS IMPLEMENTACE
45
proběhnout stejná kontrola. Překladač proto nepracuje s frontou parametrů přímo, ale přes ukazatel paramQueue, který je po zkopírování stávající fronty uložen na zásobník paramQueueStack, odkud je později znovu vyzvednut, a umožňuje tak libovolnou hloubku vnoření. Kontrola počtu a typu parametrů selže pouze tehdy, pokud parametrem volaného podprogramu je podprogram sám s případnými dalšími parametry. Protože kontrola probíhá postupně a ne až po načtení všech parametrů, nemůže být jejich počet správně rozpoznán. Tento typ rekurze proto implementace nepodporuje. Podprogramy mohou vracet celočíselnou, logickou nebo žádnou hodnotu. Překladač tyto typy podprogramů rozlišuje podobně jako typy proměnných na syntaktické úrovni. Ta ale nemůže postihnout, jaký výsledek daný podprogram vrací a zda návratový typ souhlasí. Při deklaraci každého podprogramu je proto do struktury popisující příkaz zaznamenán i jeho typ, který se následně kontroluje při nalezení návratového výrazu. Aby se zabránilo podprogramu vracejícímu hodnotu skončit bez specifikace návratové hodnoty, obsahuje pomocná proměnná returnOccured příznak nastavovaný při nalezení návratového výrazu. Bez něj vyvolá konec podprogramu chybu.
5.6 Robot a interpret Třída Robot implementovaná v rámci souborů Robot.cpp a Robot.h realizuje virtuálního robota. Obsahuje datové položky udržující informace o robotově stavu (jméno, počáteční příkaz, orientace ke světové straně, příznak mávání, spánku atd.) a metody, které představují zásah robota do okolního prostředí (přesun na jiné políčko ve městě, položení značky, probuzení jiného robota, …). Tyto metody volají veřejné metody třídy City a jiných instancí třídy Robot. Třída Interpreter je vnořená do třídy Robot. Obsahuje funkce odpovídající jednotlivým instrukcím zásobníkového počítače, tabulku příkazů, frontu pro předávání parametrů, paměť programu, zásobníkovou paměť dat, ukazatel do paměti programu instrPtr a zásobník na ukazatele na příkazy, který umožňuje přepínání kontextu při volání podprogramů. Součástí interpretu jsou rovněž příznaky pozastaveného a skončeného provádění programu a indikace výskytu chyby, kterým jsou odlišena informativní a fatální hlášení interpretu. Interpret je propojen se „svým“ robotem pomocí ukazatele superior. Se třídou Interpreter pracuje modul timer implementovaný soubory timer.cpp a timer.h. Obsahuje funkce reset( ) a step( ), kterými uvádí interprety všech robotů do základního stavu, resp. vybere robota a spustí jeho interpret až do objevení některého z příznaků rozebraných dále. Vždy, když se mu vrátí zpět kontrola nad aplikací, zkontroluje počet dosud aktivních robotů, a v případě nulového počtu nastaví vlastní příznak done, který znamená, že interpretace skončila. Tento příznak musí být kontrolován uživatelským rozhraním. Nedeterministické pořadí, ve kterém se roboti při přidělování času střídají, zajišťuje funkce jumble( ), která pootočí frontu robotů funkcí rotate( ) o náhodný počet míst a potom ještě zajistí, aby v čele fronty stál robot, který je aktivní. Interpret robota pracuje po jednotlivých instrukcích, provede vždy jednu po zavolání metody nextInstr( ). Při provedení instrukce TCL nastaví příznak timerClocked, který je přístupný přes metodu clocked( ). Analogicky při provedení instrukce SLE přejde do režimu spánku tím, že nastaví příznak programStopped čitelný metodou stopped( ). V případě výskytu běhové
KAPITOLA 5
46
POPIS IMPLEMENTACE
chyby je nahozen příznak programError přístupný metodou error( ) a je vyhozena číselná výjimka odpovídající číslu chybového hlášení, které situaci odpovídá. Konec provádění programu nastane, pokud při vykonávání instrukce RET zbývá v zásobníku příkazů pouze jediná položka (návrat z hlavního programu). Odpovídající příznak je programDone a čtecí metoda ended( ). Pokud v okamžiku skončení programu zůstává v paměti dat nevyzvednutá položka, je tato vrácena pomocí vyvolání výjimky se záporným číslem. Instrukce představující základní schopnosti robota pouze volají příslušné metody „nadřízeného“. Instrukce skoků mění ukazatel do paměti programu instrPtr, instrukce pro aritmetickologické výpočty pracují klasickým způsobem s pamětí dat, tj. vyzvednou příslušný počet operandů, provedou s nimi výpočet a výsledek uloží zpět do paměti dat. Většina instrukcí pracuje se dvěma operandy, několik s jedním a porovnávací operace se třemi. Porovnávací operace jsou zvláštní v tom, že ukládají na zásobník dva výsledky. Jsou implementovány tak, aby umožňovaly zřetězené porovnávání, a k tomu musí být před provedením na zásobníku uložena dvě porovnávaná čísla a výsledek předchozí operace porovnání, po skončení je třeba uložit nejen výsledek logicky znásobený s předchozím výsledkem, ale zachovat i druhý z operandů pro další porovnání. Například instrukce „rovno“ je implementována takto: void Robot::Interpreter::EQU( ) { int
op2 = dataMem.pop( );
int
op1 = dataMem.pop( );
int
pre = dataMem.pop( );
int
res = ( op1 == op2 ) & pre;
dataMem.push( res ); dataMem.push( op2 ); }
Překladová gramatika řeší vložení první logické hodnoty true, která nemá původ v porovnávání, a v závěru odstranění přebytečného číselného údaje, který „stíní“ výslednou logickou hodnotu operace.
5.7 Chybová hlášení Chybová hlášení generují moduly fileIo, translator a timer. V posledním případě jde o chyby generované ve skutečnosti třídou Interpreter, které mohou mít podobu chybového nebo informativního hlášení. Typ je určen tím, zda má Interpreter nastavený příznak programError. Chyba je vyvolána vždy vyhozením výjimky typu int, přičemž číslo odpovídá číslu hlášení, které má být zobrazeno. Texty hlášení jsou editovatelné a načítají se při nahrávání konfigurace. Jeli číselná výjimka zachycena, je z generického pole language::errorSet načten řetězec s offsetem odpovídajícím číslu výjimky a ten vyhozen novou výjimkou. Je na implementaci uživatelského rozhraní, aby tuto výjimku typu String zachytila a zpracovala, obvykle jejím zobrazením uživateli.
KAPITOLA 5
POPIS IMPLEMENTACE
47
Protože se chyby mohou vyskytnout ještě dříve, než je tabulka s texty chybových hlášení nahrána, obsahuje modul fileIo v patřičných místech samostatné zachycení číselné výjimky a výpis programově stanoveného hlášení doplněného číslem chyby. Uživatel pak může vyhledat v konfiguračním souboru error.conf, co se mu aplikace pokouší sdělit. Pomocné třídy použité při implementaci vyvolávají při chybě ve své funkčnosti (pokusy o přístup mimo přidělenou paměť apod.) výjimky typu char*. Je vhodné, aby byl celý obsah main( ) v main.cpp připraven zachytit a vypsat tyto výjimky, protože i přes provedená testování se mohou v implementaci stále vyskytovat chyby.
KAPITOLA 6
48
TESTOVÁNÍ
6 Testování Vzhledem k povaze práce, kterou je implementace jazyka, není možné otestovat všechny potenciální vstupy (jde o nekonečnou množinu). Rovněž kvůli funkční provázanosti jednotlivých součástí aplikace je tvorba unit testů obtížná. S ohledem na bohaté možnosti konfigurace jednotlivých částí aplikace a zdrojových souborů s úlohami, městy a příkazy je jisté, že mnoho potenciálních chyb zůstalo neošetřeno. K testování překladače a interpretu byla využita sada zdrojových textů s konstrukcemi pokrývajícími postupně všechny prvky jazyka A-MOR. Snahou bylo projít všemi větvemi lexikálního i syntaktického analyzátoru, ačkoli jak je uvedeno výše, není možné sadou testů postihnout všechny kombinace a konstrukce, které lze v jazyce vytvořit. Testován byl jednak správný překlad zdrojových textů (syntaxe odpovídající návrhu jazyka) a jednak schopnost překladače rozpoznat během překladu co největší množství syntaktických a sémantických chyb. Menší sada testovacích příkladů je zaměřena i na schopnost interpretu reagovat na problémy, které nejsou při překladu zachytitelné (interakce robotů, postupné výpočty s přenesenou chybou apod.). Za účelem testování překladače a interpretu je součástí práce verze aplikace se zjednodušeným uživatelským rozhraním, které přijímá zdrojový soubor jako parametr programu a neposkytuje žádný výstup kromě případných chybových a informativních hlášení. Umožňuje tím snadné hromadné testování. Výsledky testů se ukládají do souboru pro pozdější analýzu. Testovací soubory jsou uloženy v adresáři bin/data/ každé verze aplikace a skládají se ze: •
souboru úlohy (podadresář tasks/)
•
souboru města (podadresář cities/)
•
souboru zdrojového textu (podadresář dictionary/)
Pro testování je třeba zadat aplikaci pouze jméno úlohy – příslušné město a zdrojové texty jsou nastaveny v jejím souboru. V testovací verzi aplikace je v adresáři bin/test/ připraven testovací skript test_script, který postupně spouští aplikaci s jednotlivými testy. Pro snazší analýzu výsledků je připraven rovněž skript runtest, který znovu sestaví aplikaci ze zdrojových souborů a následně spustí test_script, jehož výstup přesměruje do souboru test_results.txt. Jednotlivé sady testů pro ověření syntaxe a detekci chyb jsou skriptem ve výsledném souboru odděleny nadpisy. Testy syntaxe jsou vytvořeny tak, aby robot v případě správné činnosti vrátil hodnotu 1 (tato hodnota je někdy číselná a jindy logická, ale na úrovni interpretu, který výsledek vrací, se typy nerozlišují). Testy detekce chyb vracejí příslušné chybové hlášení. Jména testovacích souborů jsou vždy uvozeny sekvencí test_ a následuje buď testovaným prvkem jazyka popsaným přímo přepisovacím pravidlem (Step, Left, If, …, začíná velkým písmenem), nebo komplexnější konstrukcí (synchro, param, compar, …, začíná malým písmenem), případně číslem chyby, která má být zachycena (err101, err209, err305, …, chyby v rozsahu 100199 příslušejí chybám při překladu, 200299 chybám při interpretaci, 300399 chybám vstupního podsystému). Zda vrácené hlášení skutečně odpovídá očekávanému, lze zkontrolovat v
KAPITOLA 6
TESTOVÁNÍ
49
souboru bin/conf/error.conf, kde jsou podoby hlášení pro jednotlivá čísla chyb specifikovány. Přímé vracení čísla chyby místo konkrétního hlášení nebylo použito proto, že k překladu z čísla na hlášení dochází už na úrovni překladače / interpretu a tyto zůstávají nezměněny v rámci všech verzí aplikace.
KAPITOLA 7
50
ZÁVĚR
7 Závěr
7.1
Zhodnocení naplnění cílů práce
Cílem práce bylo navrhnout a implementovat jazyk pro výuku programování založený na jazyce Karel, obohatit tuto předlohu o celočíselné a logické výpočty a přidat mechanismy, které by umožnily paralelní kooperaci nebo soupeření více virtuálních robotů. Tohoto cíle bylo implementací jazyka A-MOR dosaženo za cenu mírného nárůstu složitosti syntaxe. Základ jazyka je nicméně svému předchůdci velmi podobný a umožňuje odstínění začínajícího uživatele od pokročilejších vlastností. Požadavek na implementaci uživatelského rozhraní v textovém režimu byl rovněž splněn, jako potvrzení jeho snadné náhrady jinou implementací obsahuje práce experimentální verzi grafického rozhraní založenou na knihovně Qt a textové rozhraní pro snadné testování aplikace za použití skriptů.
7.2
Další možný vývoj
Současná podoba jazyka A-MOR stojí před zatěžkávací zkouškou v podobě uživatelské odezvy od těch, kterým je určena – mladým zájemcům o nahlédnutí do programování v jeho původní algoritmické podobě. Teprve po důkladném otestování z hlediska intuitivnosti a ergonomie, které přesahuje možnosti této práce, bude možné říci, zda jazyk A-MOR splnil cíl, který si vytyčil, a najde uplatnění. Potenciál k dalšímu vývoji jazyka i zastřešující aplikace je značný. S plnohodnotným grafickým rozhraním umožňujícím trojrozměrné zobrazení robotího města by bylo například možné využít dosud pouze částečně implementované možnosti mít na každém políčku města jinou nadmořskou výšku, což spojeno s chápáním zdi teprve jako převýšení 2 úrovně a větší vytváří prostor pro skutečně trojrozměrné prostředí, možnost šplhat na zdi po méně příkrých srázech a podobně. V každé výškové úrovni by se totéž město jevilo jinak a nabízelo tak bohatší interakci. Rovněž by bylo možné po vzoru jazyka Logo jednotlivé roboty obarvit a začít rozlišovat mezi vlastníky jednotlivých značek, stanovovat pro jednotlivé roboty individuální oblasti přístupnosti atd. S většími úpravami implementace je šance zavést i město jako vykonavatele určitého programu, čímž by se prostředí robotů stalo dynamické. Dvoufázová interpretace dovoluje také smělý plán nahradit virtuální roboty skutečnou hardwarovou reprezentací, jakou měla například první implementace Loga. V současnosti jazyku A-MOR schází především atraktivní grafické rozhraní, které by zastřešilo všechny části aplikace, uživatelsky přívětivým způsobem ji dovolilo ovládat a odstranilo nutnost editovat zdrojové a konfigurační soubory v externích editorech. Snadné provázání nového rozhraní s překladačem a interpretem je myslím touto prací dostatečně demonstrováno. A-MOR je připraven. Jeho osud ukáže čas.
KAPITOLA 8
SEZNAM LITERATURY
8 Seznam literatury [1]
Wikipedie: Fortran http://en.wikipedia.org/wiki/Fortran
[2]
Výuka programování na základní a střední škole http://www.fi.muni.cz/~tomp/semuc/text_pitner.html
[3]
Rudolf Pecinovský: Současné trendy v metodice výuky programování http://vyuka.pecinovsky.cz/
[4]
Rudolf Pecinovský: Jazyky pro výuku programování – Karel a Logo http://www.ceskaskola.cz/ICTveskole/AR.asp?ARI=2948&CAI=2129
[5]
Michal Rybka: Kolik jazyků znáš, tolikrát jsi počítačem, Level 11/2001
[6]
Wikipedie: Pascal (programming language) http://en.wikipedia.org/wiki/Pascal_%28programming_language%29
[7]
Jan Wagner: Jaký programovací jazyk ve výuce? Další neverending story... http://www.ceskaskola.cz/ICTveskole/Ar.asp?ARI=102364
[8]
Borland Delphi http://www.borland.cz/products/delphi/index.html
[9]
Wikipedie: Visual Basic http://en.wikipedia.org/wiki/Visual_basic
[10] Wikipedie: C (programming language) http://en.wikipedia.org/wiki/C_%28programming_language%29 [11] Pavel Tišnovský: Logo – dětská hračka nebo programovací jazyk? http://www.root.cz/clanky/logo-ndash-detska-hracka-nebo-programovaci-jazyk/
51
KAPITOLA 8
52
SEZNAM LITERATURY
[12] Pavel Tišnovský: Komerční implamentace Loga http://www.root.cz/clanky/komercni-implementace-loga/ [13] Pavel Tišnovský: Volně šiřitelné implementace Loga http://www.root.cz/clanky/volne-siritelne-implementace-programovaciho-jazyka-logo/ [14] Wikipedie: Karel (programming language) http://en.wikipedia.org/wiki/Karel_%28programming_language%29 [15] Karel++ http://csis.pace.edu/~bergin/karel.html [16] xKarel http://xkarel.sourceforge.net/cz/ [17] Karel programming language documentation http://mormegil.wz.cz/prog/karel/prog_doc.htm [18] M. Syncová: Martina si hraje s počítačem, Albatros 1989 [19] SGP Systems: Výukové programovací nástroje pro děti, mládež i dospělé http://www.sgpsys.com/cz/ [20] Wikipedie: Baltík http://cs.wikipedia.org/wiki/Balt%C3%ADk [21] Pavel Nygrýn: Programátor Petr http://www.ceskaskola.cz/ICTveskole/AR.asp?ARI=2780&CAI=2129 [22] GameMaker http://www.mindtools.tased.edu.au/gamemaker/default.htm [23] Doc. Ing. Karel Müller, Csc.: Programovací jazyky, nakladatelství ČVUT 2005 [24] http://www.sweb.cz/oldium.pro/oldium.pro.html
KAPITOLA 8
SEZNAM LITERATURY
[25] Dokumentace toolkitu Qt 4.0 http://doc.trolltech.com/4.0/index.html [26] Materiály pro výuku předmětu Rozhraní operačních systémů http://moon.felk.cvut.cz/~xballner/vyuka/x36api/lectures/API_8.pdf [27] Wikipedie: Multitasking http://en.wikipedia.org/wiki/Computer_multitasking [28] Wikipedie: Escape character http://en.wikipedia.org/wiki/Escape_character [29] Real Programmers Dont't Use PASCAL http://www.ee.ryerson.ca:8080/%7Eelf/hack/realmen.html
53
PŘÍLOHA A
OBSAH PŘILOŽENÉHO CD1
54
A Obsah přiloženého CD 1 Na přiloženém CD se nachází: •
v adresáři text/ elektronická verze tohoto textu ve formátech PDF a ODF (standard ISO/IEC 26300)
•
v adresáři text/ elektronická verze rozkladové tabulky ve formátech PDF a ODF (z důvodu její velikosti není obsažena v tištěné podobě)
• •
v adresáři html/ uživatelská příručka ve formátu HTML (více viz příloha C) v adresáři prog/ zdrojové, konfigurační a datové soubory implementovaného programu v tomto uspořádání: •
(verze pro operační systém Linux)
linux/ •
cli/ •
•
•
(základní verze programu s textovým rozhraním)
bin/
(adresář s programem)
•
conf/
(textové konfigurační soubory programu)
•
data/
(textové soubory se vstupními a výstupními daty programu)
•
a-mor.conf
•
a-mor
•
include/
•
src/
•
Makefile
(hlavní konfigurační soubor programu)
(spustitelný soubor generovaný při kompilaci) (hlavičkové soubory implementace)
(zdrojové soubory implementace, více viz kapitola 5) (specifický Makefile pro snadnou kompilaci programu)
(experimentální verze programu s grafickým rozhraním, obsah adresáře obdobný jako u cli/) gui/
test/
(verze určená pro testování pomocí skriptů, obsah adresáře obdobný jako
u cli/) •
bin/test/
(dodatečný adresář pro snadné testování implementace)
•
(skript spouštějící Makefile - kvůli případným změnám ve zdrojových souborech - a následně test_script)
•
(skript spouštějící postupně program s testovacími datovými soubory na vstupu a zapisující výsledky do test_results.txt)
•
test_results.txt (textový soubor s výstupy programu při zpracovávání testovacích souborů)
runtest
test_script
1 Tato příloha je obsažena na přiloženém CD v souboru readme.txt
PŘÍLOHA A •
•
OBSAH PŘILOŽENÉHO CD1
55
sync (synchronizační skript umožňující změny provedené v testovací verzi převést do zbývajících dvou se zachováním odlišností v implementaci uživatelského rozhraní)
solaris/
(verze pro operační systém Solaris, neobsahuje verzi gui)
•
soubor index.html, který zastřešuje obsah CD a poskytuje odkazy k jeho jednotlivým částem
•
soubor readme.txt, který obsahuje přílohy A a B v podobě jednoduchého textového souboru bez diakritiky
PŘÍLOHA B
POKYNY KE KOMPILACI A SPUŠTĚNÍ2
56
B Pokyny ke kompilaci a spuštění 2 Přiložené CD obsahuje zdrojové soubory a kompilační skripty pro platformy Linux a Solaris. Program byl úspěšně zkompilován a odzkoušen na platformách SUSE Linux 10.1 (kernel 2.6.16.27) na procesorech x86 a SunOS 5.10 na procesorech Sparc. V jiných operačních systémech se může postup při kompilaci lišit a nevylučuje ani zásah do zdrojových souborů nebo kompilačních skriptů.
B.1 Požadavky Pro úspěšnou kompilaci je doporučen kompilátor gcc včetně jeho rozšíření g++ ve verzi 4.1.0 a vyšší (Linux) nebo 3.4.6 a vyšší (Solaris). Starší verze mohou být funkční, ale nejsou garantovány. Implementace programu obsahuje C++ šablony (implementované v rámci hlavičkových souborů) a vyžaduje po kompilátoru schopnost s nimi správně pracovat. V systému musí být dále obsažen nástroj make a standardní knihovny C++. Pro kompilaci a chod verze programu s textovým uživatelským rozhraním je vyžadována přítomnost knihovny ncurses (curses v Solarisu) a jejích hlavičkových souborů. Pro kompilaci verze s experimentálním grafickým rozhraním (pouze Linux) knihovna Qt verze 4.0 a vyšší, její hlavičkové soubory a vývojové nástroje (Makefile této verze byl generován pomocí qmake).
B.2 Kompilace Každá verze programu obsažená na přiloženém CD má svůj Makefile. K úspěšné instalaci zkopírujte celý adresář prog/ nebo jeho požadovanou část (přehled viz příloha A) na pevný disk. Přechodem do adresáře příslušné verze programu a spuštěním příkazu make se do podadresáře bin/ vygeneruje spustitelný soubor a-mor. Adresář bin/ již obsahuje konfigurační a datové soubory programu. Jejich relativní umístění vůči pozici souboru a-mor lze nastavit v okomentovaném textovém konfiguračním souboru amor.conf. Tento soubor je po spuštění programu očekáván ve stejném adresáři, kde se nachází spouštěný program. V případě jeho nenalezení bude nahlášena chyba a program skončí.
B.3 Spuštění Program se spouští z příkazové řádky přechodem do adresáře bin/ a příkazem ./a-mor. Program ve verzi s textovým uživatelským rozhraním a v testovací verzi lze spouštět s parametrem, který tvoří jméno zpracovávané úlohy. Bez tohoto parametru se textová verze interaktivně dotáže na jméno úlohy, která se má nahrát, testovací verze skončí. Jméno úlohy je třeba zadávat včetně přípony. Cesta, ve které bude soubor vyhledán, je specifikována v hlavním konfiguračním souboru a-mor.conf. Pro bližší seznámení s konfigurací, editováním úloh a zdrojových souborů viz uživatelskou příručku. Pro základní demonstraci funkčnosti je připravena
2 Tato příloha je obsažena na přiloženém CD v souboru readme.txt
PŘÍLOHA B
POKYNY KE KOMPILACI A SPUŠTĚNÍ2
57
úloha sample.task. Všechny verze programu mají rovněž mezi datovými soubory připravené testovací úlohy, o nich blíže viz kapitola 6.
PŘÍLOHA C
UŽIVATELSKÁ PŘÍRUČKA
58
C Uživatelská příručka Uživatelská příručka se nachází na přiloženém CD v adresáři html/. Je přístupná přes html/index.html nebo odkazem z index.html v kořenovém adresáři média. Příručka obsahuje: •
shrnutí kompilace a spuštění programu
•
seznámení se základní konfigurací programu
•
seznámení s editací úloh, měst a zdrojových textů
•
seznámení s filozofií programování v jazyce AMOR odvozeného z jazyka Karel
•
přehled instrukcí generovaných během překladu do jazyka zásobníkového počítače
