KATEDRA INFORMATIKY ˇ´IRODOVEDECK ˇ ´ FAKULTA PR A ´ UNIVERZITA PALACKEHO PARADIGMATA OBJEKTOVÉHO PROGRAMOVÁNÍ I MICHAL KRUPKA ´ ˇ ´IHO TEXTU JE SPOLUFINANCOVAN ´ VYVOJ TOHOTO UCEBN ´ SOCIALN ´ ´IM FONDEM A STATN ´ ´IM ROZPOCTEM ˇ ˇ ´ REPUBLIKY EVROPSKYM CESK E Olomouc 2008 Abstrakt Obsahem textu jsou základy objektově orientovaného programování. C´ılov´ a skupina První část textu je určena studentům všech bakalářských oborů vyučovaných na katedře informatiky Přírodovědecké fakulty UP Olomouc. Chystaná druhá část textu je určena především studentům bakalářského oboru Informatika. Obsah 1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Od Scheme ke Common Lispu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Pozadí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Logické hodnoty a prázdný seznam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Vyhodnocovací proces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Common Lisp: základní výbava . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Řízení běhu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Proměnné a vazby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Místa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.5 Logické operace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6 Porovnávání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.7 Čísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.8 Páry a seznamy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.9 Chyby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.10 Textový výstup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.11 Typy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.12 Prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Třídy a objekty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.1 Třídy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Třídy a instance v Common Lispu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Inicializace slotů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Zapouzdření . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1 Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Princip zapouzdření . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.3 Úprava tříd point a circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.4 Třída picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Polymorfismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.1 Kreslení pomocí knihovny micro-graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Kreslení grafických objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3 Princip polymorfismu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.4 Další příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Dědičnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.1 Dědičnost jako nástroj redukující opakování v kódu . . . . . . . . . . . . . . . . . . . . . . . . 70 7.2 Určení předka při definici třídy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3 4 5 6 7 8 7.3 Přiblížení běžným jazykům . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.4 Hierarchie tříd grafických objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7.5 Přepisování metod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.6 Volání zděděné metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.7 Inicializace instancí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.8 Příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.1 Symbolické výrazy poprvé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.2 Zápis a čtení symbolických výrazů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 8.3 Symbolické výrazy a dědičnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 8.4 Zpráva simplify a volání metody předka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.5 Posloupnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.6 Zprávy fyzické úrovně . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.7 Zprávy logické úrovně . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8.8 Jednorozměrná pole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.9 Seznamy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.10 Posloupnosti: další příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9 Události . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.1 Zpětná volání v knihovně micro-graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.2 Jednoduché využití zpětných volání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 9.3 Vlastnické vztahy, delegování, události . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 9.4 Implementace událostí u jednoduchých grafických objektů . . . . . . . . . . . . . . . . . . . . 111 9.5 Reakce na změny u jednoduchých objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 9.6 Klikání myší u jednoduchých objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.7 Reakce na změny u složených objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 9.8 Klikání myší u složených objektů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 9.9 Příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 A Slovníček . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 A.1 Základní výrazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 A.2 Odvozené výrazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 A.3 Makra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 A.4 Standardní procedury — predikáty ekvivalence . . . . . . . . . . . . . . . . . . . . . . . . . . 129 A.5 Standardní procedury — čísla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 A.6 Standardní procedury — logické typy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 A.7 Standardní procedury — páry a seznamy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 A.8 Standardní procedury — symboly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 A.9 Standardní procedury — znaky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 A.10 Standardní procedury — řetězce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 A.11 Standardní procedury — vektory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 A.12 Standardní procedury — řízení běhu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 A.13 Standardní procedury — eval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 A.14 Standardní procedury — vstup a výstup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 A.15 Standardní procedury — systémové rozhraní . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 B Knihovna micro-graphics: seznam použitelných barev . . . . . . . . . . . . . . . . . . . . . . . . 134 1. Úvod Tento text pokrývá část látky předmětu Paradigmata programování 2 (dříve Paradigmata programování 3), vyučovaného autorem na Přírodovědecké fakultě Univerzity Palackého Olomouc od roku 2005, a je určen studentům tohoto předmětu i dalším zájemcům o hlubší pochopení principů objektového programování. Chystaná druhá část tohoto textu se zabývá pokročilejšími a méně obvyklými rysy objektového programování. Kurz Paradigmata programování 2 představuje pro většinu studentů první setkání s objektovým programováním. Jeho cílem je seznámit studenty s obecnými základy objektového programování, bez úzké vazby na konkrétní programovací jazyk. Kurz tak slouží jako protiváha předmětů, v nichž je objektové programování probíráno se zřetelem k přímému uplatnění v praxi a v nichž se studenti musejí zabývat zvláštnostmi jednotlivých v současné době v praxi používaných programovacích jazyků. Text klade důraz na praktickou stránku problematiky, je proložen mnoha praktickými příklady, další příklady, které tvoří nedílnou součást textu, lze nalézt na webu autora. Výklad je ve většině případů koncipován metodou „zdola nahoru“, většina pojmů a technik je nejprve inspirována příkladem či problémem. Smysl každého pojmu by tak měl být čtenáři jasný dříve, než je pojem přesně vymezen. Objektové programování obsahuje nástroje, které pomáhají programátorům zvládat práci na složitých a rozsáhlých programech. Kvůli pochopení některých důležitých principů tohoto programovacího stylu bylo tedy nevyhnutelné sáhnout po poměrně netriviálních příkladech — na takových příkladech se teprve síla objektového programování projeví. Čtenář tak může ocenit a pochopit metody, které objektové programování poskytuje, při zvládání praktických úkolů. Není nucen řešit akademické příklady, do kterých by uměle vnášel složité principy způsobem, který by v praxi neobstál. (Toto předsevzetí nebylo z pochopitelných důvodů možno dodržet stoprocentně. Proto čtenář v textu i nějaké „akademické“ příklady najde. Celkové ladění textu by ale mělo být jiné.) Jako modelový programovací jazyk byl použit Common Lisp a jeho objektová část, Common Lisp Object System (CLOS). Použitým vývojovým prostředím je program LispWorks. Hlavní důvody této volby jsou následující: • Studenti znají z předchozího studia příbuzný jazyk Scheme. • Díky tomu, že se jedná o dynamicky typovaný jazyk s velmi jednoduchou syntaxí, se studenti nemusí zabývat podružnými problémy, které by je odváděly od pochopení podstatného (jako příklad mohu uvést, že jsem se nikdy nesetkal s tím, že by studenti při řešení úkolů z objektového programování měli jakékoliv dotazy ohledně syntaxe). Na závěr tohoto textu zjistíme, že se nám podařilo poměrně snadno a rychle napsat plně funkční jednoduchou objektovou 2D grafickou knihovnu. • Common Lisp je dynamický programovací jazyk, psaní a ladění programů je velmi pohodlné a rychlé (při opravě chyby ve vykreslování okna často není nutné okno vůbec zavírat — abychom vyléčili pacienta, není nutné ho předtím zabít). • CLOS je bohatý a současně snadno pochopitelný objektový programovací jazyk, v němž lze demonstrovat většinu běžných a mnoho neobvyklých rysů objektového programování. • Program LispWorks je moderní vývojový nástroj obsahující všechny podstatné nástroje pro tvorbu i rozsáhlejších aplikací. Je dostupný na všech hlavních platformách (Windows, Mac OS X, Linux), k dispozici je plně funkční (s nepodstatnými omezeními) verze zdarma. • Grafická knihovna LispWorks (CAPI) je přenositelná mezi platformami a obsahuje vše potřebné pro implementaci naší grafické knihovny. Na webu autora je k dispozici kód a příklady k jednotlivým částem textu, i knihovna micro-graphics. Michal Krupka 2. Od Scheme ke Common Lispu Účelem této části je poskytnout uživatelům jazyka Scheme první informace potřebné k zahájení práce s Common Lispem. Čtenář se dozví o základních rozdílech mezi těmito jazyky, zejména terminologických a rozdílech ve vyhodnocovacím procesu. Další informace o Common Lispu lze nalézt v následujících částech tohoto textu, již bez vazby na jazyk Scheme. Vždy je vhodné mít po ruce nějakou příručku o Common Lispu, jako reference může dobře sloužit webová podoba standardu, Common Lisp HyperSpec. V dodatku A je uveden slovníček, ve kterém čtenář najde ke každému symbolu definovanému ve standardu R5 RS jeho ekvivalent v Common Lispu. 2.1. Pozadí Jakkoli jsou rozdíly mezi syntaxí jazyka Scheme a Common Lispu malé, přechod od Scheme ke Common Lispu nemusí být pro programátora rutinně pracujícího ve Scheme snadný. Podstata obou jazyků, jejich účel nebo, chceme-li, duch, jsou totiž značně rozdílné. Zatímco jazyk Scheme vznikl a je dodnes vyvíjen jako samostatný programovací jazyk — byť založený na Lispu —, jehož hlavním rysem je jednoduchost a čistota, Common Lisp přímo navazuje na rozličné předchozí dialekty Lispu, počínaje původním, uvedeným koncem padesátých let. V těchto dialektech bylo napsáno mnoho rozsáhlých programů, včetně operačních systémů pro počítače přímo navržené pro práci s Lispem1 a jedná se tedy o jazyk robustní, obsahující desetiletí vyvíjené a osvědčené nástroje potřebné pro tvorbu velkých projektů mnohočlennými vývojovými týmy. Poznámka 2.1. Common Lisp lze ztěží označit za čistý jazyk vysoké úrovně. Rozšířené tvrzení, že se jedná o „jazyk umělé inteligence,“ nepoužitelný pro praktickou práci, je zcela mylné. Ve většině implementací i ve standardu samotném je tradičně k dispozici mnoho nízkoúrovňových nástrojů, z nichž některé bychom dokonce v implementacích jiných jazyků těžko hledali — bitové operace, instrukce skoku lokálního i nelokálního, práce s ukazateli, inline assembler, přímé napojení na služby operačního systému, možnost prohlížet jednotlivě u každé funkce její zkompilovaný tvar v assembleru, lokálně v libovolné části kódu (i uvnitř funkce) nastavovat různé varianty optimalizace přeloženého kódu, dokonce i do určité míry programovat kompilátor. Z uvedených důvodů se Common Lisp těžko mohl vyhnout jisté komplexnosti a mírné vnitřní nekonzistentnosti. Začínající programátor v Common Lispu se pohybuje rozsáhlým a nepřehledným terénem, ve kterém se z počátku nesnadno orientuje. Má k dispozici mnoho složitých, leckdy těžko srozumitelných nástrojů a jen pomalu se dobírá pochopení jejich podstaty a vzájemné souvislosti. Důvody, proč stojí za to úsilí do studia Common Lispu vložit, již byly vysvětleny. Tento text se snaží využívat poměrně značně omezenou část Common Lispu, která je popsána v této a následujících dvou částech, a stavět na čtenářových znalostech jazyka Scheme. 2.2. Terminologie Některé základní rysy jazyků Scheme a Common Lisp jsou označovány rozdílnými termíny. Na tomto místě shrneme základní rozdíly. Poznámka 2.2. Nepřesnost ve vyjadřování vede k nepřesnosti sdělení. Nepřesné pochopení základů mívá v programování jasný důsledek: špatně napsaný program. 1 Tzv. Lisp Machines, vyráběné koncem sedmdesátých a v osmdesátých letech, které významně ovlivnily vývoj výpočetní techniky. Objektům, které se ve Scheme nazývají procedury, se v Common Lispu říká funkce. Ve standardu se dočteme, že funkce je objekt, který může být volán s žádným nebo více argumenty a který vytváří (vrací) nula nebo více hodnot. Je to tedy objekt, na jaké jsme zvyklí z většiny programovacích jazyků, i když s možností vracení více než jedné hodnoty se obvykle nesetkáváme (nemluvě ovšem vůbec o základním rysu funkcionálního programování, že funkce je objekt prvního řádu, tj. objekt, se kterým lze manipulovat stejně jako s ostatními objekty). K pojmu funkce je třeba dodat, že kromě vracení výsledku může funkce také vykonat vedlejší efekt — tato okolnost je v oblasti funkcionálního programování nepříjemnou a nevítanou nutností, objektové programování ji naopak používá jako základní pracovní nástroj. Víme, že v Lispu je zdrojový kód programu složen ze seznamů a dalších objektů (zejména čísel, symbolů, textových řetězců). Libovolnému objektu, který je částí zdrojového kódu programu, říkáme výraz. Termín forma má v Common Lispu jiný význam než ve Scheme (kde se používá hlavně ve spojení speciální forma2 ): Podle standardu je forma libovolný objekt, který je určen k vyhodnocení. Jak víme (a to je v Scheme i Common Lispu stejné), vyhodnocovat můžeme objekty jednoduché, jako jsou čísla a symboly (tzv. atomy), a objekty složené, neprázdné seznamy (prázdný seznam je atom). Vyhodnocování seznamů probíhá v Common Lispu poněkud jinak než ve Scheme; popíšeme je později. U složených forem se první položka nazývá operátor. Podle operátoru rozlišujeme tři typy složených forem: funkční formy, makro formy a speciální formy (tento pojem tedy znamená něco jiného než stejný pojem ve Scheme). Funkční formy odlišíme od makro forem podle toho, jestli je jejich operátor jménem funkce nebo jménem makra. Posledně jmenované speciální formy jsou formy, jejichž operátor je jedním z 25 symbolů definovaných standardem. Tyto symboly se nazývají speciální operátory. 2.3. Logické hodnoty a prázdný seznam V jazyce Scheme slouží k reprezentaci logických hodnot objekty #t (pravda) a #f (nepravda). V Common Lispu tuto úlohu hrají hodnoty t a nil. Narozdíl od Scheme se nejedná o hodnoty speciálního typu, ale o symboly. Zvláštností těchto symbolů je, že je pro ně stanoveno, že se vyhodnocují samy na sebe, podobně jako například čísla: > nil nil > t t (později se setkáme s mnoha dalšími takovými symboly). Poznámka 2.3. Na tomto místě je samozřejmě vhodné vědět, co je to symbol. Pokud to nevíte, zopakujte si příslušné části kurzu jazyka Scheme. Poznámka 2.4. Zařídit, aby hodnotou symbolu byl dotyčný symbol samotný je ovšem snadné; ve Scheme by se dalo napsat například (define a 'a), v Common Lispu například (defvar a 'a). V Common Lispu se stejně jako ve Scheme používají zobecněné logické hodnoty: hodnotu pravda (true) může reprezentovat libovolný objekt kromě symbolu nil, hodnotu nepravda (false) pak jedině symbol nil. V literatuře o Common Lispu i v tomto textu je zvykem psát slovo pravda místo konkrétnější hodnoty v případě, že je tato hodnota 2 Tento termín není ve standardu R5 RS nikde definován ani použit (kromě jedné historické zmínky), jedná se ale o mezi uživateli Scheme obecně rozšířený pojem a čtenář se s ním setkal. podstatná pouze jako pravdivostní hodnota. V tomto kontextu se také používá slovo nepravda jako synonymum pro symbol nil. Jako argumenty logických operací je tedy možno používat jakékoliv objekty a samotné logické operace mohou jako hodnotu pravda místo symbolu t vracet jiný, v dané situaci užitečnější objekt. Příklad 2.5. Výraz (and a b c) vrací pravdu, pokud hodnoty a, b i c jsou pravda. Díky použití zobecněných logických hodnot je možno, aby proměnné a, b, c nabývaly i jiných hodnot než jenom t nebo nil, a hodnotou celého výrazu může být i něco jiného, než jen symboly t a nil. Makro and je například definováno tak, že pokud jsou všechny jeho argumenty pravda (rozumějme: různé od nil), vrací hodnotu posledního z nich. Výraz, který vrátí číslo 3, pokud je x rovno 1 a y rovno 2, a jinak vrátí nil, se tedy dá jednoduše napsat takto: (and (= x 1) (= y 2) 3). Pokud bychom navíc třeba chtěli, aby v případě negativního výsledku výraz nevracel nil, ale nulu, můžeme použít makro or, které také pracuje se zobecněnými logickými hodnotami, a napsat jej takto: (or (and (= x 1) (= y 2) 3) 0). V Common Lispu není žádná zvláštní hodnota reprezentující prázdný seznam; roli prázdného seznamu hraje symbol nil: > '() nil > '(1 . nil) (1) Poznámka 2.6. Symbol nil tak zastává funkce, na které jsou v jazyce Scheme vyčleněny tři různé objekty: logická hodnota #f, prázdný seznam a symbol nil. Poznámka 2.7. Používání symbolu nil v Common Lispu ke třem různým účelům bývá často uživateli zvyklými na jazyk Scheme kritizováno. Z praktického hlediska se ale tato okolnost ukazuje být častěji spíše předností než nedostatkem. V Common Lispu je běžné, a my se s tímto přístupem budeme často setkávat, užívání symbolu nil jako univerzální negativní či prázdné hodnoty. To je pochopitelně umožněno tím, že může vystupovat současně jako prázný seznam i pravdivostní hodnota nepravda — v jazyce Scheme se s žádnou podobně univerzální hodnotou nesetkáme. Poznámka 2.8. Nevýhoda pojetí zvoleného v Common Lispu se může projevit například v momentě, kdy hledáme nějaký seznam a za pozitivní výsledek považujeme i seznam prázdný. V Common Lispu pak hodnota niluž nemůže signalizovat neúspěch. Jako příklad lze uvést třeba funkci, která by měla vrátit cestu mezi dvěma vrcholy grafu ve formě seznamu hran, nebo hodnotu nepravda, když taková cesta neexistuje (prázdná cesta spojující vrchol s ním samým je tedy prázdný seznam a pozitivní výsledek současně), či funkci, která má nalézt daný prvek v daném seznamu, v případě úspěchu vrátit podseznam začínající prvkem následujícím a v případě neúspěchu hodnotu nepravda (zde dojde k potížím, pokud je nalezený prvek na konci seznamu). Podobné problémy se ale nevyskytují příliš často a v Common Lispu je lze vždy snadno obejít. Koneckonců, oddělení hodnoty #f a prázdného seznamu ve Scheme stejně neřeší například problém prohledávání množiny, která může obsahovat i hodnotu #f. Poznámka 2.9. Za zmínku snad ještě stojí, že v některých jazycích je definováno více hodnot reprezentujících logickou hodnotu nepravda. Například v Pythonu to je (mimo jiné) hodnota none, prázdný seznam, nebo číslo 0 libovolného typu. Další nepravdivé hodnoty lze dodefinovat. Stejně jako v jazyce Scheme se funkcím, které vrací hodnotu pravda nebo nepravda, říká predikáty. V jazyce Scheme je obvyklé ukončovat názvy predikátů otazníkem, v Common Lispu písmeny „p“ nebo „-p“. Varianta bez pomlčky se používá v případě, že koncovku přidáváme k jednoslovnému názvu (například u symbolů equalp, stringp a podobně), jinak se používá varianta s pomlčkou (upper-case-p). 2.4. Vyhodnocovací proces V Common Lispu může symbol sloužit současně jako název funkce i jako název proměnné. Tyto dvě role symbolů spolu nijak nekolidují. Proto je možno napsat: > (defvar list 1) ;definice proměnné list s hodnotou 1 1 > list ;v proměnné list je hodnota 1: 1 > (list 2 3) ;funkci list to však neovlivnilo: (2 3) V terminologii Common Lispu se říká, že každý symbol má dvě vazby: hodnotovou a funkční . Pomocí každé z těchto vazeb může být symbol svázán s nějakou hodnotou. V případě vazby hodnotové s libovolnou hodnotou, v případě vazby funkční s funkcí. Poznámka 2.10. Záměrně nezmiňujeme případ, kdy symbol neoznačuje funkci, ale makro, nebo kdy je speciálním operátorem. Tato informace je uložena stejně jako u funkcí pomocí funkční vazby symbolu (symbol nemůže například současně označovat funkci a makro). Podle standardu je přitom hodnota svázaná funkční vazbou se symbolem označujícím makro nebo speciální operátor implementačně závislá; standard neříká, jakého typu tato hodnota je. Je-li symbol svázán funkční vazbou s nějakou funkcí, říkáme, že je názvem této funkce. V případě hodnoty svázané se symbolem hodnotovou vazbou hovoříme prostě o hodnotě symbolu (či, volněji, hodnotě proměnné). Příklad 2.11. Dvojí role symbolů tedy umožňuje používat stejné názvy pro proměnné a funkce. Proto například můžeme napsat: (defun comp (list) (list (car list))) (pomocí makra defun se v Common Lispu definují funkce; viz níže uvedený doslovný překlad do Scheme). Funkce encap-car vrací jednoprvkový seznam obsahující první prvek seznamu list: (encap-car '(1 2)) => (1) Ve Scheme by doslovná analogie definice této funkce vypadala takto: (define encap-car (lambda (list) (list (car list)))) Scheme nesprávně (define (encap-car list) (list (car list))) Scheme nesprávně neboli a volání (encap-car '(1 2)) by skončilo chybou (proč?). Poznámka 2.12. V Common Lispu je tedy možné vybírat pro proměnné názvy bez ohledu na to, jestli současně označují nějakou funkci — tak, jak jsme to viděli v případě funkce encap-car; u této funkce jistě neexistuje přirozenější název pro její parametr, než je symbol list (snad jedině symbol cons, který je ale rovněž názvem funkce) — není nutno sahat po náhradních názvech, jako například lst nebo clist. Poznámka 2.13. Této možnosti se v Common Lispu poměrně často využívá; jakmile si na ni uživatel zvykne, začne přijímat nabízenou volnost spíše jako výhodu a bez obav z nedorozumění. Ve zdrojovém kódu je totiž podle pozice symbolu vždy jasně poznat, kterou z jeho dvou možných hodnot právě uvažujeme. Poznámka 2.14. V základních implementacích Common Lispu bývá k dispozici možnost zjistit snadno ke kterékoliv funkci její dokumentaci a seznam parametrů. Například v LispWorks můžeme umístit kurzor na symbol encap-car a z nabídky vyvolat Expression→Arguments. Pokud jsme funkci encap-car definovali stejně jako zde, dozvíme se, že seznam parametrů této funkce je (list). Ve vývojovém prostředí SLIME se nám podobná informace zobrazí automaticky během psaní volání funkce: (encap-car...). Názvy parametrů funkcí nejsou tedy pouze interní věcí autora, ale slouží i jako jednoduchá dokumentace pro uživatele. Proto je vhodné volit názvy parametrů funkce srozumitelně, s ohledem na případného uživatele. Dvoje vazby symbolů v Common Lispu umožňují pojmenovávat parametry funkcí co nejpopisnějším způsobem. Existence dvojí vazby symbolů, kterou jsme zatím prezentovali jako jednoznačnou výhodu, nutně vede i k několika komplikacím. Kromě složitějšího vyhodnocovacího procesu jde zejména o dva případy: když chceme zavolat funkci uloženou v proměnné a když chceme zjistit funkci podle jejího názvu. K ilustraci těchto problémů nejprve uveďme následující definici procedury na kompozici dvou procedur v jazyce Scheme: (define comp (lambda (a b) (lambda (x) (a (b x))))) Scheme (define (comp a b) (lambda (x) (a (b x)))) Scheme neboli Analogická definice v Common Lispu by vypadala takto: (defun comp (a b) (defun (x) (a (b x)))) nesprávně a vedla by k nepředvídatelným důsledkům, protože ve výrazu (a (b x)) by se nepoužily aktuální hodnoty proměnných a a b, ale došlo by k pokusu aplikovat funkce se jmény a a b, o kterých není jasné, jestli by existovaly a pokud ano, co by dělaly. Poznámka 2.15. Přečtěte si podrobně předchozí odstavec. Důvod, proč uvedený příklad v Common Lispu nefunguje, je třeba přesně pochopit. V naší definici potřebujeme volat nikoli funkce, jejichž jména jsou a a b, ale funkce, které jsou hodnotami proměnných a a b — tedy jsou se symboly a, b svázány hodnotovou, nikoliv funkční vazbou. Pro podobné situace je v Common Lispu připravena funkce funcall, která volá funkci, kterou najde ve svém prvním argumentu. Správná definice funkce comp v Common Lispu je tedy následující: (defun comp (a b) (lambda (x) (funcall a (funcall b x)))) Ke druhému problému: pomocí funkce comp a funkcí car a cdr lze snadno vyjádřit funkci, která vrací druhý prvek daného seznamu. Ve Scheme by takovou funkci (proceduru) vracel výraz (comp car cdr) Scheme V Common Lispu by vyhodnocení tohoto výrazu opět vedlo k nepředvídatelným důsledkům, protože by se v něm nepoužily funkční, ale hodnotové vazby symbolů car a cdr. Abychom získali funkce car a cdr, musíme použít speciální operátor function, který je navržen přesně k požadovanému účelu — nalezení funkce zadaného jména. Funkce car a cdr získáme vyhodnocením výrazů (function car) a (function cdr). Analogický výraz v Common Lispu by tedy správně vypadal takto: (comp (function car) (function cdr)) Pro výraz (function name) se používá zkratka #'name, takže uvedený výraz je možno napsat stručněji: (comp #'car #'cdr) Dvojí vazby symbolů představují jediný významný rozdíl mezi vyhodnocovacím procesem Scheme a Common Lispu. Pro zopakování: Chceme-li zavolat funkci uloženou v proměnné a s argumenty p1, . . . , pn, nestačí jako ve Scheme napsat (a p1 ... pn) Scheme ale (funcall a p1 ... pn) Chceme-li získat funkci s názvem f, musíme místo prostého f uvést Scheme #'f což je zkratka pro (function f) Kvůli zopakování a pro pozdější potřebu uvádíme na obrázku 1 zjednodušený popis vyhodnocovacího procesu v Common Lispu. Tento vyhodnocovací proces je stejně jako ve Scheme rekurzivní; kdekoli se v popisu na obrázku hovoří o vyhodnocení nějakého objektu, znamená to spuštění celého vyhodnocovacího procesu od začátku na tento objekt. Vyhodnocováním objektu (kterému, jak už víme, za těchto okolností říkáme také forma), rozumíme jistý přesně definovaný proces, který tomuto objektu přiřadí hodnotu3 a má případný vedlejší efekt. Seznam posledních změn 10. 3. 2008 Přidána poznámka o predikátech a způsobu jejich zápisu. 3 V předchozím textu bylo uvedeno, že výrazy v Common Lispu mohou mít více hodnot. Pro jednoduchost zde tuto vlastnost výrazu neuvažujeme. Vyhodnocení formy F Je-li F symbol, výsledkem je hodnota symbolu F , vedlejší efekt není žádný. Je-li F seznam s první položkou Op, pak je-li Op speciální operátor nebo symbol pojmenovávající makro, výsledek včetně případného vedlejšího efektu závisí na speciálním operátoru Op, případně definici makra Op a ostatních prvcích seznamu F . λ–výraz definující funkci F un nebo symbol pojmenovávající funkci F un, vyhodnotí se zleva doprava všechny prvky seznamu F počínaje druhým a zavolá se funkce F un s argumenty rovnými hodnotám těchto vyhodnocení. Hodnotou výrazu bude hodnota vrácená funkcí F un, během výkonu této funkce také může dojít k vedlejším efektům. něco jiného, dojde k chybě. Je-li F něco jiného, hodnotou je F , vedlejší efekt není žádný. Obr´ azek 1: Zjednodušený vyhodnocovací proces v Common Lispu 3. Common Lisp: základní výbava Common Lisp je jazyk s velmi jednoduchou syntaxí, kterou jsme mohli v podstatě celou vysvětlit na několika stránkách předchozí části textu. Na druhé straně ovšem je Common Lisp objemná knihovna nástrojů na tvorbu rozsáhlých programů. V jazyce je 978 jmen speciálních operátorů, maker, funkcí a dalších symbolů, z nichž některé jsou podloženy hlubokými poznatky a principy. Abychom mohli při výkladu objektového programování Common Lisp používat jako účinný pomocný nástroj, musíme si jej alespoň do určité míry osvojit. Tato kapitola se věnuje vysvětlení části Common Lispu, která postačí ke zvládnutí základů objektového programování, probíraných v tomto textu. V této kapitole představíme část ze zmíněných 978 symbolů. Některé z nich podrobně vysvětlíme, u jiných odkážeme čtenáře na definici ve standardu. U každého symbolu ze základní výbavy očekáváme, že o jeho existenci bude čtenář vědět a že jej bude schopen (s případným nahlédnutím do standardu) správně, rychle a účinně použít. 3.1. Řízení běhu Základním operátorem, který slouží k podmíněnému vyhodnocení výrazů je speciální operátor if. Jeho zjednodušená syntax je následující: (if test-form then-form else-form) => result Speciální operátor if vyhodnocuje nejprve formu test-form a podle výsledku pak buď then-form nebo else-form: je-li hodnota test-form pravda, vyhodnotí formu then-form a jako výsledek vrátí její hodnotu, je-li nepravda, vyhodnotí else-form a vrátí její hodnotu. Poznámka 3.1. V Common Lispu, narozdíl od některých jiných (zejména procedurálních) programovacích jazyků, není rozdíl mezi příkazem a výrazem. Proto lze jak k podmíněnému vykonání příkazu, tak k podmíněnému získání hodnoty výrazu použít tentýž operátor if (například v jazyce C je nutno k prvnímu použít klíčové slovo if, ke druhému ternární operátor ?:). Toto dvojí použití (které lze samozřejmě i kombinovat) ilustrujeme na jednoduchém příkladě: pokud bychom k číslu x chtěli přičíst číslo 1, nebo -1 v závislosti na tom, zda je číslo y nezáporné, nebo záporné, mohli bychom napsat (if (>= y 0) (+ x 1) (+ x -1)) což by odpovídalo podmíněnému vykonání příkazu, nebo (+ x (if (>= y 0) 1 -1)) což je podmíněné získání hodnoty. Pro úplnost uvedeme ještě jednu možnost, která se také může v některých situacích hodit: (funcall (if (>= y 0) #'+ #'-) x 1) Užitečnými variantami speciálního operátoru if jsou makra when a unless. Jejich definice a příklady použití (včetně souvislosti se speciálním operátorem if a makrem cond) lze najít ve standardu. V Common Lispu existuje mnoho maker umožňujících iterace (cykly) nejrůznějších typů. Jsou to například makra dotimes a dolist. Jejich použití je někdy pohodlnější než použití rekurze. První slouží k iteraci přes všechna čísla větší nebo rovna nule a menší než zadaná hodnota. Výraz (dotimes (x 5) (print x)) vytiskne následujících pět řádků: 0 1 2 3 4 Makro dolist vytváří cyklus, v němž je daná proměnná navázána postupně na všechny prvky daného seznamu. Výraz (dolist (x '(2 -1 3)) (print x)) vytiskne 2 -1 3 Poznámka 3.2. Makra dotimes a dolist patří jednoznačně do imperativního programovacího stylu. Je nemožné vymyslet příklad využití těchto maker v jinak čistě funkcionálním kódu (proto jsme použili funkci print, která má vedlejší efekt — vytisknutí daného objektu). Tato makra ovšem lze definovat čistě funkcionálními prostředky. Hloubavější čtenář to může zkusit. Poznámka 3.3. Funkci print vysvětlíme později. Speciální operátor quote i jeho zkratka “' “ jsou čtenáři již dostatečně známy. Symboly do základní výbavy: if, when, unless, cond, dotimes, dolist, quote 3.2. Proměnné a vazby Každý symbol může být vybaven množstvím hodnotových vazeb, které jej svazují s libovolnými hodnotami (víme už, že symboly mají i funkční vazby, ty však pro nás nyní nejsou podstatné) — těmto vazbám se podle standardu říká proměnné, symbolu, kterému vazba přísluší, se říká název (nebo také jméno) proměnné. Někdy se také pro jednoduchost ale nepřesně ztotožňuje proměnná se svým symbolem, tj. se svým názvem. Ze všech hodnotových vazeb symbolu je aktivní vždy pouze jedna; ta určuje, jakou má příslušný symbol v daný moment hodnotu. O ostatních vazbách říkáme, že jsou aktuální vazbou zastíněny. 1 b a (1 2 3) "mrkev" Obr´ azek 2: Vazby symbolu Poznámka 3.4. Hodnotové vazby symbolu si můžeme představit jako provázky spojující tento symbol s různými hodnotami. Pokud je tedy například symbol a svázán se čtyřmi hodnotami — číslem 1, symbolem b, řetězcem "mrkev" a seznamem (1 2 3), můžeme si tuto skutečnost představit tak, jak je uvedeno na Obrázku 2. Pokud je tučně vyznačená vazba právě aktivní, bude aktuální hodnotou symbolu a řetězec "mrkev". Říkáme také, že tento řetězec je hodnotou proměnné a. Kdybychom v tento moment změnili hodnotu proměnné a na něco jiného, řekněme na řetězec "salám" (což lze udělat voláním (setf a "salám"), jak uvidíme podrobněji později), vypadal by výsledek tak, jak vidíme na Obrázku 3. 1 b a (1 2 3) "salám" Obr´ azek 3: Vazby symbolu po změně aktuální vazby Hodnotové vazby mohou být dvou typů: lexikální, nebo dynamické. Tyto typy vazeb se liší okolnostmi, za kterých vazby vznikají, zanikají a za kterých jsou aktivní. Základním typem vazby v Common Lispu je vazba lexikání4 , dynamické vazby se používají pouze za určitých okolností a my se s nimi v tomto textu nesetkáme. Každá hodnotová vazba symbolu je vytvářena speciálními operátory let a let*, které popíšeme níže, a na začátku volání funkce, je-li symbol uveden jako její parametr. Každá nová vazba je vždy lexikální, vyjma případů, kdy programátor rozhodne jinak. Lexikální vazba nikdy nezaniká, ale je aktivní pouze v části programu určené blokem textu ve zdrojovém kódu — buď částí těla operátoru let nebo let*, nebo částí volané funkce. Mimo tento blok textu není možno žádným způsobem hodnotu lexikální vazby získat nebo nastavit, a to ani v rámci kódu, který je z tohoto bloku textu volán. Poznámka 3.5. Lokální proměnné ve většině programovacích jazyků jsou lexikální. Základním nástrojem pro práci s vazbami je speciální operátor let, jehož zjednodušená syntax je následující: (let ((var init-form)*) form*) => result var: symbol init-form: forma form: forma result: hodnota vrácená poslední formou form 4 I když se v literatuře občas dočteme opak. Speciální operátor let vytváří nové vazby symbolů var a inicializuje je na hodnoty, které získá postupným vyhodnocením forem init-form. Vytvořené vazby jsou obecně lexikální (výjimky zde nebudeme rozebírat). Vytvořené lexikální vazby, jak už bylo řečeno, nikdy nezanikají, ale jsou aktivní pouze v části kódu, která je označena jako form*. Výrazy form* se postupně vyhodnotí, výsledek posledního se vrátí jako výsledek celého let-výrazu. Místo seznamu (var init-form) lze napsat pouze var. Význam je stejný, jako kdybychom napsali (var nil). Příklad 3.6. Například: CL-USER 1 > (let ((a t) b) (list a b)) (T NIL) Jelikož nové vazby jsou aktivní uvnitř let-výrazu, dochází k zastínění případných vazeb vnějších: CL-USER 2 > (let ((a 1)) (cons (let ((a 2)) a) a)) (2 . 1) V tomto případě vnitřní let-výraz vytvořil vazbu symbolu a na číslo 2, která zastínila vnější vazbu tohoto symbolu na číslo 1. Poznámka 3.7. Při opakovaném vyhodnocení téhož let-výrazu se vytvářejí stále nové vazby na tytéž symboly a původní vazby zůstávají v platnosti. Tuto skutečnost ilustrujeme později, v odstavci věnovaném funkcím. Speciální operátor let* má stejnou syntax jako operátor let. Liší se od něj tím, že nové vazby symbolů var nejsou aktivní pouze v oblasti form*, ale stanou se aktivními vždy ihned poté, co je získána hodnota příslušné init-form. Jinými slovy, při vyhodnocování každé init-form už jsou aktivní vazby všech předchozích var. Příklad 3.8. Rozdíl mezi operátory let a let* demonstrujeme na příkladě: CL-USER 3 > (let ((a 1)) (let ((a 2) (b a)) b)) 1 — v momentě, kdy byla inicializována vazba symbolu b, byla aktivní vnější vazba symbolu a. CL-USER 4 > (let ((a 1)) (let* ((a 2) (b a)) b)) 2 — v momentě, kdy byla inicializována vazba symbolu b, už byla aktivní vnitřní vazba symbolu a. Poznámka 3.9. Existují další způsoby, jak vytvořit novou vazbu. Kromě navazování parametrů na konkrétní hodnoty při volání funkce, které podrobněji rozebereme později, to je například u maker dotimes a dolist, která již byla probrána; v obou příkladech, na kterých jsme práci těchto maker ilustrovali, se vytváří nová vazba symbolu x. O lexikálních vazbách souhrnně říkáme, že mají lexikální rozsah platnosti. Tento pojem můžeme použít i na jiné objekty než jsou vazby. V každém okamžiku běhu programu je u každého symbolu aktivní nejvýše jedna vazba. Souhrn aktivních lexikálních vazeb se nazývá aktuální lexikální prostředí. Poznámka 3.10. Prostředí si lze představit (a pravděpodobně tak bývá implementováno) jako tabulku se dvěma sloupci: jedním pro symbol, druhým pro jeho hodnotu. Poznámka 3.11. Chceme-li místo vytváření nové vazby symbolu změnit hodnotu aktivní vazby, můžeme použít makro setf. K němu se dostaneme později. V souvislosti s proměnnými je třeba zmínit ještě makro defvar. Jeho zjednodušená syntax je tato: (defvar name [form]) => name name: symbol form: forma Makro defvar vytvoří zvláštní druh vazby symbolu name. Tato vazba má časově neomezenou platnost — nikdy nezaniká. Navíc je viditelná ze všech míst programu. Poznámka 3.12. Proměnné definované makrem defvar mají tedy podobné vlastnosti jako tzv. globální proměnné v jiných programovacích jazycích. Proměnným definovaným makrem defvar se říká dynamické (někdy též speciální ) proměnné. Je-li uvedena forma form a proměnná name dosud nemá žádnou hodnotu, forma form bude vyhodnocena a výsledek bude nastaven jako hodnota nově vzniklé vazby symbolu name. Má-li proměnná name hodnotu, forma form se vůbec nevyhodnotí. Příklad 3.13. Demonstrace uvedené vlastnosti makra defvar: CL-USER 5 > (defvar *x* 1) *X* CL-USER 6 > *x* 1 CL-USER 7 > (defvar *x* 2) *X* CL-USER 8 > *x* 1 Tento efekt makra defvar zjevně nemusí být vždy tím, který očekáváme. Pokud například vyhodnotíme výraz (defvar *x* (fun)), pak objevíme a opravíme chybu ve funkci fun a výraz znovu vyhodnotíme, bude proměnná *x* stále obsahovat původní nechtěnou hodnotu. Proto, pokud víme dopředu, že chceme, aby se vždy při načtení souboru s touto definicí hodnota proměnné *x* aktualizovala, použijeme místo uvedeného výrazu raději dvojici výrazů (defvar *x*) (setf *x* (fun)). Makro defvar obsahuje jednu záludnost. Symboly, které jsou pomocí tohoto makra zavedeny jako dynamické proměnné, nemohou mít lexikální vazby. Pokud tyto symboly použijeme (například v let-výrazu) jako název nové proměnné, nevytvoří se lexikální, ale dynamická vazba. Abychom se vyhnuli komplikacím spojeným s používáním dynamických vazeb, zavedeme dvě pravidla pro používání dynamických proměnných: Pravidla pro používání dynamických proměnných 1. Za názvy dynamických proměnných budeme volit pouze symboly začínající a končící hvězdičkou, 2. u těchto symbolů nebudeme nikdy vytvářet nové vazby. Poznámka 3.14. Připomeňme si, jakým způsobem lze vytvářet nové vazby symbolů, abychom věděli, co všechno nám druhý bod zakazuje: k vytváření nových vazeb slouží operátory let a let*, nové vazby vznikají při volání funkcí tak, že se navážou parametry na argumenty (o tom viz níže v podkapitole o funkcích), makra dotimes a dolist také vytvářejí nové vazby. Symboly do základní výbavy: let, let*, defvar 3.3. Místa V Common Lispu se k vykonání vedlejšího efektu často používá makro setf. Například: CL-USER 28 > (defvar *a*) *A* CL-USER 29 > (setf *a* (cons 0 2)) (0 . 2) CL-USER 30 > (setf (car *a*) 1) 1 CL-USER 31 > *a* (1 . 2) Uvedená dvě volání makra setf tedy vykonávají rozdílné akce. První nastavuje hodnotu aktuální vazby symbolu *a*, druhé mění hodnotu car nějakého tečkového páru. Příklad 3.15. Je důležité dobře pochopit, co znamená, že makro setf nastavuje hodnotu aktuální vazby symbolu. Začátečníci zvyklí programovat v procedurálních jazycích se často diví výsledku následujícího pokusu: CL-USER 8 > (defvar *a*) *A* CL-USER 9 > (setf *a* 1) 1 CL-USER 10 > (defun set-a (a b) (setf a b)) SET-A CL-USER 11 > (set-a *a* 2) 2 CL-USER 12 > *a* 1 Mnoho výrazů, jejichž vyhodnocení vede k získání obsahu nějakého místa v paměti, lze v kombinaci s makrem setf současně použít k modifikaci tohoto místa. Kromě výše uvedených dvou typů výrazů (výrazu a a výrazu (car a)) jsou to zejména výrazy, které pracují s položkami strukturovaných dat různých typů (vektorů, polí, párů, posloupností). Výraz, který lze současně použít k získání hodnoty a v kombinaci s makrem setf k jejímu nastavení, se nazývá místo (place). V Common Lispu je definováno mnoho typů míst, jejich výčet může zájemce najít v části 5.1.2 standardu. Kromě toho je ve standardu vždy u každého symbolu, který lze v kombinaci s makrem setf jako místo použít, tato skutečnost uvedena. Poznámka 3.16. Zvídavější čtenáře zaujme, že Common Lisp poskytuje mechanismy, jak nové typy míst dodefinovat. Makro setf použité uvedeným způsobem vždy vrací jako svůj výsledek nastavovanou hodnotu — tedy svůj druhý parametr. Makro setf lze použít s více parametry k nastavení hodnot více míst současně. V takovém případě vrací vždy hodnotu posledního z těchto míst. Například: CL-USER 12 > (defvar *a*) *A* CL-USER 13 > (setf *a* (cons 1 2)) (1 . 2) CL-USER 14 > (setf (car *a*) 3 (cdr *a*) 4) 4 CL-USER 15 > *a* (3 . 4) Symbol do základní výbavy: setf 3.4. Funkce Základní operací prováděnou s funkcemi je volání (aplikace) funkce s nějakými daty. Těmto datům se v Common Lispu říká argumenty funkce. Příklad 3.17. Ve formě (cons 1 2) je tedy funkce cons volána s argumenty 1, 2, neboli seznam argumentů v tomto volání je (1 2). Pokud budeme dále hovořit o definici funkce, budeme používat termín parametr. Ten neoznačuje konkrétní data, se kterými je funkce volána, ale proměnnou, na kterou je v průběhu výkonu funkce některý z argumentů navázán. Poznámka 3.18. V jiných jazycích se používá jiná terminologie, například formální a aktuální parametry. Při definici nových funkcí (například pomocí operátorů defun, lambda a labels, které popíšeme za chvíli), je třeba uvést informaci o jejich parametrech. Tuto informaci uvádíme formou tzv. obyčejného λ-seznamu, kterým může v našem zjednodušeném případě být seznam symbolů, které se v nesmí opakovat. Symboly obsažené v λ-seznamu se nazývají parametry dané funkce. Pokud λ-seznam funkce obsahuje n parametrů, musí být funkce volána právě s n argumenty. Při volání funkce se vytvoří nové lexikální vazby parametrů na pořadím jim odpovídající argumenty. Rozsah platnosti těchto vazeb je podobný jako u speciálních operátorů let a let* a zahrnuje celé tělo definované funkce. Příklad 3.19. Funkce car, cdr a cons by tedy mohly mít následující λ-seznamy: (x) (x) (x y) Podívejme se nyní na to, jakými způsoby lze definovat nové funkce. Základním prostředkem je makro defun, jehož zjednodušená syntax je následující: (defun function-name lambda-list form*) => function-name function-name: symbol ordinary-lambda-list: obyčejný λ-seznam form: forma Makro defun vytváří novou funkci jménem function-name (nastavuje tedy hodnotu funkční vazby symbolu function-name na tuto funkci), jejíž seznam parametrů je specifikován obyčejným λ-seznamem lambda-list a tělo se skládá z forem form. Při volání této funkce se vytvoří nové vazby parametrů λ-seznamu tak, jak bylo specifikováno výše, a ve vzniklém prostředí se postupně vyhodnotí všechny formy form. Hodnota poslední formy form bude hodnotou celého tohoto volání. Příklad 3.20. Definice funkce na sečtení všech celých čísel od a do b: (defun sum-numbers (a b) (* (+ a b) (- b a -1) 1/2)) Po vyhodnocení této definice pak tuto funkci můžeme volat jménem sum-numbers: CL-USER 7 > (sum-numbers 1 10) 55 Poznámka 3.21. Z předchozí části již víme, že získat tuto funkci můžeme vyhodnocením výrazu (function sum-numbers), což je ve zkratce #'sum-numbers. K vytváření bezejmenných funkcí slouží operátor lambda. Zjednodušená syntax: (lambda lambda-list form*) => result ordinary-lambda-list: obyčejný λ-seznam form: forma result: výsledná funkce Operátor lambda vytváří novou funkci, jejíž seznam parametrů je specifikován obyčejným λ-seznamem lambda-list a tělo se skládá z forem form. Narozdíl od makra defun nestanovuje pro novou funkci žádné jméno, ale vrací ji jako svou hodnotu. Při volání této funkce se naváží všechny parametry λ-seznamu jak bylo specifikováno výše a pak se postupně vyhodnotí všechny formy form. Hodnota poslední formy form bude hodnotou celého tohoto volání. Poznámka 3.22. Makro defun si tedy lze zhruba představit tak, že nejprve pomocí makra lambda vytvoří novou funkci a potom tuto funkci nějak uloží jako hodnotu funkční vazby symbolu function-name. Pokročilejší programátoři v Common Lispu ale vědí, že to není všechno, co makro defun dělá. λ-výrazy stejné syntaxe lze uvést i na prvním místě vyhodnocovaného seznamu. V takovém případě se funkce definovaná tímto výrazem přímo zavolá — viz popis vyhodnocovacího procesu uvedený v předchozí části. Příklad 3.23. Například výraz ((lambda (x) (+ x (if (< x 0) -1 1))) (fun)) přičte k výsledku volání funkce fun jedničku, pokud je nezáporný, jinak od něj jedničku odečte. Speciální operátor labels lze použít k lokální definici funkcí. Tento operátor definuje funkce, které jsou platné pouze v určitém lexikálním rozsahu. Každá definice lokální funkce má stejnou syntax jako u makra defun. Vlastnosti definovaných funkcí jsou rovněž stejné jako u makra defun. Lexikální rozsah platnosti těchto definic zahrnuje celý labels-výraz. Proto se definované lokální funkce mohou vzájemně rekurzivně volat. Příklad 3.24. Možná definice iterativní verze funkce na výpočet faktoriálu: (defun fact (n) (labels ((fact-iter (n accum) (if (<= n 1) accum (fact-iter (- n 1) (* n accum))))) (fact-iter n 1))) Funkci definovanou lokálně speciálním operátorem labels lze pomocí jejího názvu získat stejně jako funkci definovanou globálně makrem defun — použitím speciálního operátoru function. Obvyklý způsob volání funkce je použitím jejího názvu nebo λ-výrazu na prvním místě vyhodnocovaného seznamu (viz popis vyhodnocovacího procesu v předchozí části textu). Další možností je použít funkci funcall nebo apply, jejichž popis lze najít ve standardu. Funkce vytvářené operátory defun, lambda a labels jsou lexikální uzávěry — veškeré volné lexikální proměnné použité v těle těchto funkcí se budou interpretovat v lexikálním prostředí, v němž byly použity, a to i v případě, že tyto funkce budou volány v jiném prostředí. Lexikální uzávěry tedy mají možnost číst a měnit hodnoty lexikálních vazeb, které byly aktivní, když byly tyto uzávěry definovány, a to i když už program výraz, který tyto vazby definoval (let nebo let*-výraz, nebo tělo volané funkce), opustil. Ještě jinak řečeno: v těle lexikálního uzávěru tyto vazby opět aktivní budou, neboť toto tělo se textově nachází uvnitř bloku kódu, ve kterém aktivní jsou — vzpomeňme si, že lexikální vazby nikdy nezanikají. Například v této definici (defun test (x) (cons (lambda () x) (lambda (val) (setf x val)))) každé volání funkce test vytváří novou lexikální vazbu symbolu x a každá z dvojic funkcí, které tímto voláním postupně vznikají, se tak prostřednictvím symbolu x odkazuje na jinou jeho vazbu: CL-USER 9 > (setf a (test 1)) (# . #) CL-USER 10 > (setf b (test 2)) (# . #) CL-USER 11 > (funcall (car a)) 1 CL-USER 12 > (funcall (car b)) 2 CL-USER 13 > (funcall (cdr a) 3) 3 CL-USER 14 > (funcall (car a)) 3 CL-USER 15 > (funcall (car b)) 2 Symboly do základní výbavy: defun, lambda, labels, function, funcall, apply 3.5. Logické operace O logických hodnotách v Common Lispu jsme se už zmínili. Ve všech operátorech, které pracují s logickými hodnotami, symbol nil reprezentuje hodnotu nepravda a všechny ostatní objekty hodnotu pravda. Tak může například výsledek logických operací kromě informace o kladném výsledku přinášet také nějakou užitečnou hodnotu. Funkce not neguje svůj argument. Mohla by být definována takto: (defun not (x) (unless x t)) Makra and a or pracují podle pravidel zkráceného vyhodnocování logických operací, tj. nevyhodnocují všechny své argumenty, ale postupují od prvního tak dlouho, dokud nenarazí na hodnotu, která rozhodne o výsledku. Tuto hodnotu ihned vrátí a ve vyhodnocování dalších argumentů už nepokračují. U makra and rozhodne o výsledku první nepravdivá hodnota, u makra or první pravdivá. Pokud makro and nebo or dojde ve vyhodnocování až na konec seznamu argumentů, vrátí hodnotu posledního z nich. Poznámka 3.25. Makra and a or lze tedy používat i jako operátory řídící běh programu. Takto by například mohla být implementována funkce find-true, která najde první prvek daného seznamu, který není roven nil: (defun find-true (list) (and list (or (car list) (find-true (cdr list))))) Poznámka 3.26. V předchozí kapitole jsme upozornili na to, že názvy predikátů, tj. funkcí, které vracejí (zobecněnou) logickou hodnotu je obvyklé psát s příponou „p“ nebo „-p“. Symboly do základní výbavy: and, or, not 3.6. Porovnávání Univerzální predikát na porovnávání dat neexistuje. Vždy záleží na účelu, ke kterému data používáme. Poznámka 3.27. Představa, že by mohl existovat jeden univerzální porovnávací predikát (tj. funkce, která rozhoduje, zda jsou objekty „stejné“ nebo ne), je scestná. Predikát na porovnávání seznamů bude jistě vypadat jinak, než predikát na porovnávání seznamů, reprezentujících množiny (tj. seznamů, u nichž nám nezáleží na pořadí prvků). Příklad 3.28. Pokud programujeme čistě funkcionálně, můžeme seznamy vytvořené dvojím voláním výrazu (list 1 2) považovat za totožné. Pokud ale pracujeme s vedlejším efektem, už to obecně nelze: CL-USER 16 > (setf a (list 1 2)) (1 2) CL-USER 17 > (setf b (list 1 2)) (1 2) CL-USER 18 > (setf (car a) 3) 3 CL-USER 19 > a (3 2) CL-USER 20 > b (1 2) Příklad 3.29. Čísla 1 a 1.0 můžeme z matematického hlediska považovat za sobě rovná, z implementačního hlediska ale sobě jistě rovná nejsou — jsou různých typů, zabírají různé místo v paměti, pro práci s nimi se používají různé instrukce procesoru atd. V Common Lispu jsou zavedeny čtyři univerzální porovnávací predikáty. My budeme využívat dva z nich: predikát eql a predikát equalp. Oba přijímají dva argumenty a oba vracejí hodnotu pravda, pokud si tyto argumenty jsou v jistém smyslu rovny. Funkce eql, zjednodušeně řečeno, zkoumá, zda jsou zadané objekty totožné podle těch nejpřísnějších pravidel, jaká mají v rámci Common Lispu smysl. U objektů shodných podle funkce eql se můžeme spolehnout na to, že zůstanou shodné, ať s nimi budeme dělat cokoli. Příklad 3.30. Například: CL-USER 21 > (eql 'a 'a) T CL-USER 22 > (eql 1 1) T CL-USER 23 > (eql (list 1 2) (list 1 2)) NIL CL-USER 24 > (eql 1 1.0) NIL Funkce equalp naopak považuje dva objekty za stejné, pokud mají, opět zhruba řečeno, stejný obsah. Nerozlišuje také malá a velká písmena v řetězcích. Pokud jsou dva objekty equalp, jsou také určitě eql. Příklad: CL-USER 25 > (equalp (list 1 2) (list 1 2)) T CL-USER 26 > (equalp "ahoj" "AHOJ") T CL-USER 27 > (equalp 'ahoj "AHOJ") NIL CL-USER 28 > (equalp 1 1.0) T Přesný popis funkcí eql a equalp je ve standardu. Symboly do základní výbavy: eql, equalp 3.7. Čísla Základní funkce pro práci s čísly jsou následující: Predikáty =, /=, <=, >= slouží k porovnávání dvou a více čísel. Funkce +, -, *, / implementují základní aritmetické operace. Akceptují jeden (v případě funkcí + a * dokonce žádný) a více argumentů. K dispozici je mnoho různých reálných funkcí, například min, max, abs, signum, sin, cos, tan, exp, expt, sqrt, log a dalších. Konstanta pi obsahuje číslo π . Celočíselné dělení a zaokrouhlování provádějí například funkce floor, ceiling, round, truncate (různé typy celočíselného dělení spojené se zaokrouhlováním — vracejí vždy dvě hodnoty, podíl a zbytek; v tomto textu se ale druhými a dalšími hodnotami funkcí nezabýváme) a mod, rem (dva typy zbytku po dělení). Symboly do základní výbavy: =, /=, <=, >=, +, -, *, /, min, max, abs, signum, sin, cos, tan, exp, expt, sqrt, log, pi, floor, ceiling, round, truncate, mod, rem 3.8. Páry a seznamy Základní funkce pracující s tečkovými páry — v Common Lispu se pro ně používá spíše název cons — čtenář i čtenářka již většinou zná: funkce cons vytváří nový pár, funkce car a cdr získávají hodnoty jeho složek. Hodnoty (car nil) a (cdr nil) jsou navíc definovány jako nil — při jejich získávání tedy nedojde k chybě. Poznámka 3.31. Funkce car a cdr tedy nepracují jen s páry, ale se všemi seznamy včetně prázdného. Dejme si na tuto okolnost pozor, někdy může vést k nepříjemným chybám. Funkce car a cdr definují místa, takže složky párů lze modifikovat pomocí makra setf. Pokus o nastavení car nebo cdr symbolu nil ovšem vede k chybě. Funkce, které zjišťují hodnoty složek zřetězených párů jsou caar, cadr, cdar, cddr, caaar, caadr, cadar, caddr, cdaar, cdadr, cddar, cdddr, caaaar, caaadr, caadar, caaddr, cadaar, cadadr, caddar, cadddr, cdaaar, cdaadr, cdadar, cdaddr, cddaar, cddadr, cdddar, cddddr. Všechny tyto funkce akceptují jako parametr i symbol nil a definují místa obdobně jako funkce car a cdr. K získávání hodnot obecných složek zřetězených párů slouží funkce nth a nthcdr. Funkce nth a nthcdr akceptují jako parametr i symbol nil. Funkce nth navíc definuje místo. Seznam je v Common Lispu libovolný pár nebo symbol nil (který reprezentuje prázdný seznam). Mezi seznamy se tedy počítají i tzv. tečkované seznamy, což jsou všechny seznamy x, pro něž některá z hodnot (nthcdr n x) není seznam. Objekt (1 2 3 4 5 . 10) je tedy tečkovaný seznam. Tečkované seznamy zde zmiňujeme pouze pro úplnost, v dalším se s nimi nesetkáme. Totéž platí i o tzv. kruhových seznamech. Funkce list vytváří nové seznamy. Funkce copy-list kopíruje daný seznam. Funkce append spojuje libovolný počet seznamů. Funkce last vrací konec daného seznamu zadané délky, funkce butlast začátek. K jednotlivým prvkům seznamu lze také přistupovat pomocí funkcí first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth, které také definují místo. Funkce null testuje, zda je daný objekt nulový seznam (je tedy ekvivalentní funkci not; volba je věcí stylu). Funkce reverse slouží k obracení seznamů. Funkce mapcar je základní funkce, která aplikuje danou funkci na všechny prvky seznamu a shromažďuje výsledky volání do nového seznamu: CL-USER 10 > (mapcar (lambda (x) (+ x 1)) '(0 1 2 3)) (1 2 3 4) Pokud zadanou funkci lze volat s více argumenty, můžeme funkci mapcar zadat více seznamů: CL-USER 12 > (mapcar #'cons '(a b c) '(1 2 3)) ((A . 1) (B . 2) (C . 3)) CL-USER 13 > (mapcar #'+ '(1 2 3) '(4 5 6) '(7 8 9)) (12 15 18) Příklad 3.32. Skalární součin vektorů u a v reprezentovaných seznamy: (apply #'+ (mapcar #'* u v)) Pokud bychom matici reprezentovali seznamem řádků, z nichž každý by byl reprezentován seznamem, vypadal by součin matice M a vektoru v takto: (mapcar (lambda (row) (apply #'+ (mapcar #'* row v))) M) Funkce find a find-if rozhodují, zda je daný prvek, nebo prvek s danou vlastností přítomen v zadaném seznamu. Zjednodušená syntax: (find element list) => result (find-if predicate list) => result element: libovolný objekt predicate: funkce list: seznam result: nalezený prvek nebo nil Funkce find vrátí element, pokud jej najde v seznamu list. Pokud ne, vrátí nil. Příklad: CL-USER 1 > (find 2 '(1 2 3)) 2 CL-USER 2 > (find 4 '(1 2 3)) NIL Funkce find používá k porovnávání prvku element a prvků seznamu list funkci eql. Proto: CL-USER 3 > (find (cons 1 2) '((1 . 2) (3 . 4))) NIL Funkce find-if vrátí první prvek seznamu list takový, že když se na něj aplikuje funkce predicate, výsledek aplikace bude pravda. Pokud takový prvek v seznamu list nenajde, vrátí nil. Příklad: CL-USER 4 > (find-if (lambda (x) (> x 4)) '(2 4 6 8)) 6 CL-USER 5 > (find-if (lambda (x) (< x 2)) '(2 4 6 8)) NIL Funkce remove a remove-if slouží k odstranění prvků ze seznamu. Příklad: (remove 2 '(1 2 3)) => (1 3) (remove-if (lambda (x) (> x 5)) '(1 4 7 10 6 2)) => (1 4 2) Funkce length zjišťuje délku seznamu. Funkce every testuje, zda všechny prvky posloupnosti vyhovují danému predikátu. Podobně jako například funkce mapcar je také schopna pracovat s predikáty, které přijímají více argumentů a více posloupnostmi. Symboly do základní výbavy: cons, car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, caddr, cdaar, cdadr, cddar, cdddr, caaaar, caaadr, caadar, caaddr, cadaar, cadadr, caddar, cadddr, cdaaar, cdaadr, cdadar, cdaddr, cddaar, cddadr, cdddar, cddddr, nth, nthcdr, list, copy-list, append, last, butlast, first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth, reverse, mapcar, find, find-if, remove, remove-if, length, every 3.9. Chyby Každý program se může dostat do situace, se kterou jeho autor dopředu nepočítal a která vyžaduje zásah uživatele (ať už jiné části programu nebo člověka). Takovýmto stavům se říká vyjímečné stavy a dochází k nim hlavně v důsledku nějaké chyby (programu, operačního systému, disku apod.). Jsou to stavy, u kterých je nevhodné, aby program bez informace z vnějšku pokračoval v práci. V našem textu budeme používat jednu funkci, která signalizuje, že k vyjímečnému stavu došlo. Je to funkce error a má následující zjednodušenou syntax: (error string) Tato funkce signalizuje chybu, jejíž popis je v řetězci string. Současně dojde k předčasnému zastavení běhu programu. Příklad 3.33. Bezpečná funkce na výpočet faktoriálu: (defun fact (n) (unless (and (typep n 'integer) (>= n 0)) (error "Factorial needs a non-negative integer as its argument.")) (labels ((fact-iter (n accum) (if (<= n 1) accum (fact-iter (- n 1) (* n accum))))) (fact-iter n 1))) (volání (typep n 'integer) zjišťuje, zda je hodnota proměnné n celé číslo; více v odstavci o typech). Test: CL-USER 1 > (fact -1) Error: Factorial needs a non-negative integer as its argument. 1 (abort) Return to level 0. 2 Return to top loop level 0. Type :b for backtrace, :c