Lekce 4: Tečkové páry, symbolická data a kvotování
Obsah lekce: V této lekci se budeme zabývat vytvářením abstrakcí pomocí dat. Představíme tečkové páry pomocínichž budeme vytvářet hierarchické datové struktury. Ukážeme rovněž, že tečkové páry bychom mohli plně definovat pouze pomocí procedur vyšších řádů. Dále se budeme zabývat kvotováním a jeho zkrácenou notací jenž nám umožníchápat symboly jako data. Jako příklad datové abstrakce uvedeme implementaci racionální aritmetiky.
Klíčová slova: ##datová_abstrakce, ##konstruktory, ##kvotování, ##selektory, ##symbolická_data, ##tečkové_páry.
s4_1
4.1 Vytváření abstrakcí pomocí dat
Doteď jsme vytvářeli abstrakce pomocí procedur: používali jsme procedury k vytvářenísložitějších procedur,
přitom jsme se nemuseli zabývat tím, jak jsou jednodušší procedury vytvořeny (pokud fungujísprávně).
Teď provedeme totéž s daty: budeme pracovat se složenými (hierarchickými) daty a budeme konstruovat procedury,
které je budou zpracovávat – budou je brát jako argumenty nebo vracet jako výsledek své aplikace.
Přitom to opět budeme provádět tak,
aby bylo procedurám de facto jedno, jak jsou složená data konstruována z jednodušších.
Nejprve si ukážeme několik motivačních příkladů, z nichž pak vyplyne potřeba vytvářet a zpracovávat složená data.
Příklad 4.1 kvadratická rovnice
Uvažujme, že bych chtěli napsat proceduru,
která má nalézt kořeny kvadratické rovnice \(ax^2 + bx + c = 0\)
na základě jejich koeficientů podle důvěrně známého vzorce
\((b \pm \sqrt D ) \over 2a\), kde \(D = b^2 − 4ac\).
Takové kořeny jsou v oboru komplexních čísel dva: \(x_1\) a \(x_2\) (popřípadě jeden dvojitý).
Proceduru pro výpočet kořenů, která má tři argumenty reprezentující koeficienty kvadratické rovnice,
bychom mohli napsat například následujícím způsobem.
Kód je ponechán neúplný, protože nám zatím schází prostředek, jak vrátit oba kořeny současně:
(define koreny
(lambda (a b c)
(let* ((diskr (- (* b b) (* 4 a c)))
(koren1 (/ (+ (- b) (sqrt diskr)) (* 2 a)))
(koren2 (/ (- (- b) (sqrt diskr)) (* 2 a))))
;teď bychom chtěli vrátit dvě hodnoty současně
)))
V tuto chvíli se samozřejmě nabízí celá řada „hloupých řešení“, jak obejít problém vracení dvou hodnot.
Mohli bychom například proceduru rozšířit o další parametr, který by určoval, který kořen máme vrátit.
Kód by pak vypadal následovně:
(define koreny
(lambda (a b c p)
(let ((diskr ((- (* b b) (* 4 a c)))))
(/ ((if p + -) (- b) (sqrt diskr)) 2 a))))
Předchozí řešení problému není šťastné, kdybychom totiž dále chtěli pracovat s oběma kořeny,
museli bychom proceduru aplikovat dvakrát
a pokaždé by docházelo k vyhodnocování téhož kódu se stejnými argumenty (jedná se třeba o výpočet diskriminantu).
Jiným takovým řešením je namísto jedné procedury koreny mít dvě procedury koren1 a r+, která bere jako parametry dvě racionálníčísla a vrací jejích součet.
Z pohledu primitivních dat uvažujeme racionální číslo jako dvě celá čísla – čitatele a jmenovatele.
S touto dvojicí potřebujeme zacházet jako s jednou hodnotou.
Pro bližší ilustraci uvedeme neúplnou definici procedury r+ s vloženým textem poukazujícím na potřebu používat hierarchická data:
(define r+
(lambda (cit1 jmen1 cit2 jmen2)
;proceduře bychom chtěli předávat jen dva argumenty = dvě racionální čísla
(let* (
(cit (+ (* cit1 jmen2) (* cit2 jmen1)))
(jmen (* jmen1 jmen2))
(delit (gcd cit jmen))))
;teď bychom chtěli vrátit dvě hodnoty současně: cit a jmen
)))
Obdobně jako v předchozím příkladě bychom mohli mít zvlášť proceduru na výpočet čitatele
a zvlášť proceduru na výpočet jmenovatele, nebo pomocí dalšího argumentu určovat,
kterou složku racionálního čísla (čitatele nebo jmenovatele) má procedura vrátit.
Ve většině výpočtů ale budeme potřebovat i čitatele i jmenovatele.
Navíc kdybychom neustále pracovali se dvěma hodnotami namísto jedné
a pro každou operaci bychom museli mít dvě procedury (vracejí cíčitatele a jmenovatele z výsledné hodnoty).
Program by se stal velmi brzy nepřehledným.
Tato podvojnost procedur a čísel by také velice znesnadňovala udržování kódu a stala by se potenciálním zdrojem chyb.
Příklad 4.3 geometrické útvary
V dalším příkladě se snažíme navrhnout program pracujícís geometrickými útvary,
ve kterém bychom chtěli pracovat s pojmy jako bod, úsečka, kružnice a tak dále.
Bod v rovině je z pohledu primitivních dat dvojice ré alných čísel; úsečku můžeme reprezentovat (třeba) jako dvojici bodů;
kružnici (třeba) jako bod (střed) a ré alné číslo (poloměr).
Rozumným požadavkem na takový geometrický program by bylo mít v něm například k dispozici procedury pro výpočet různých průsečíků:
třeba procedura na výpočet průsečíku dvou úseček bude vracet bod.
Při vytváření programu bychom záhy narazili na potřebu „slepit“ dvě souřadnice dohromady, abychom je mohli považovat za bod;
„slepit“ dva body dohromady a vytvořit tak reprezentaci úsečky a podobně.
Z pohledu tohoto příkladu je tady patrné, že jako programátoři bychom měli mít k dispozici prostředky,
které nám umožní reprezentovat abstraktnější data než jen „numerické hodnoty“.
Konec konců, prakticky všechny soudobé programy pracujís mnohem složitějšími daty než jsou jen čísla.
Pokus <idxref Priklad #4.3>
Z těchto tří motivačních příkladů vyplývázřejmý požadavek:
Obdobně jako jsme v lekci 2 vytvářeli nové procedury, potřebujeme teď vytvářet větší datovécelky z primitivních dat
a pracovat s nimi jako by se jednalo o jeden element.
Potřebujeme tedy vytvářet abstrakce pomocí dat.
Jakmile to budeme moci udělat, můžeme například přestat uvažovat racionálníčíslo jako dvě čísla – čitatele
a jmenovatele – a můžeme začít s ním pracovat na vyšší úrovni abstrakce jako s celkem,
to jest s elementem reprezentujícím „racionálníčíslo“.
Stejně tak v ostatních motivačních příkladech můžeme pracovat s elementy reprezentující „dvojice kořenů
kvadratické rovnice“, „bod“, „úsečka“, „kružnice“, a tak dále.
Abychom docílili datové abstrakce, musíme odpovědět na dvě otázky:
1. Jak implementovat abstraktní data pomocí konkrétní (fyzické) datové reprezentace?
Neboli potřebujeme prostředek, který nám umožní z primitivních dat vytvářet složená data.
2. Jak odstínit program od této konkrétní datové reprezentace?
Když budeme pracovat se složenými daty, budeme s nimi chtít zacházet jako s pojmem, který reprezentují.
Nebude nás zajímat jak a kde jsou data konkrétně uložena.
Například v případě kořenů kvadratických rovnic chceme mít k dispozici procedury jako „vytvoř řešení “,
„vraťprvní kořen z ře-šení “, „vrať druhý kořen z řešení “, a další procedury, které pracujís kořeny.
Z pohledu uživatelů těchto procedur nás už ale nebude zajímat jakým způsobem a kde jsou hodnoty uloženy.
str98
Kvůli odstínění programu od konkrétní datové reprezentace proto pro každá složená data vytváříme:
1/konstruktory – procedury sloužící k vytvářenísložených dat z jednodušších,
s vytvořenými daty dále pracujeme jako s jednotlivými elementy;
1/selektory – procedury umožňují přistupovat k jednotlivým složkám složených dat.
cons konstruktor páru (vytváří pár z jednoduchých dat)
a car a cdr jsou selektory (umožňují přistupovat k prvkům párů).
Viz následující upřesňující definici.
Definice 4.4 Procedura cons
Procedura cons se používá se dvěma argumenty
(cons první-prvek druhý-prvek)
a vrací pár obsahující tyto dva argumenty první prvek a druhý prvek jako svoje prvky.
Máme-li pár pár, můžeme extrahovat tyto části pomocí primitivních procedur car a cdr.
Procedury car a cdr se používají s jedním argumentem
(car pár )
,
(cdr pár )
.
Procedura car jako výsledek své aplikace vrací první prvek předaného páru.
Procedura cdr jako výsledek své aplikace vrací druhý prvek předaného páru.
V případě, že by car nebo cdr byly aplikovány s elementem, který není pár,
pak dojde k chybě „CHYBA: Argument předaný proceduře musí být pár“.
Poznamka_4.5 Původ jmen cons, car a cdr: Jméno procedury cons znamená „construct“ (vytvoř).
Jména car a cdr pocházejíz původní implementace LISPu na počítači IBM 704.
Tento stroj měl adresovacíschéma, které povolovalo odkazovat se na místa v paměti nazvané „address“ a „decrement“.
Zkratka „car“ znamená „Contents of Address part of Register“
a zkratka „cdr“ (čteno „kudr“) znamená „Contents of Decrement part of Register,“ pro detaily viz například [SICP].
Příklad 4.6 cons
Uvažujme, že na symboly par1 a par2 navážeme dva páry následujícím způsobem:
(define par1 (cons 1 2))
(define par2 (cons par1 3))
(a) Výraz (car par1) se vyhodnotína číslo 1, protože na symbol par1 je navázán pár, který má první
prvek číslo 1 (a jeho druhým prvkem je číslo 2). Aplikací procedury car dostaneme toto číslo.
(b) Výsledkem vyhodnocení výrazu (cdr par2) bude číslo 3.
Na symbol par2 je navázán pár, jehož druhý prvek je číslo 3, kterézískáme aplikací procedury cdr.
Výsledkem vyhodnocení výrazu (car par2) bude pár obsahující jako svůj první prvek jedničku a jako druhý prvek dvojku.
Z příkladu je myslím jasné, že prvky párů mohou být obecně jakékoliv elementy, tedy i další páry.
© Vyhodnocení výrazu (car (car par2)) bude vypadat následovně:
Jelikož je na symbol car navázána procedura, vyhodnotíme předanýargument – tedy seznam (car par3).
Vyhodnocením tohoto seznamu dostaneme pár,
který má první prvek číslo 1 a druhý prvek je číslo 2 – vyhodnocení tohoto podvýrazu bylo již popsáno v bodě (b).
Aplikací procedury car na tento pár dostaneme číslo 1.
Obdobně číslo 2 dostaneme jako výsledek vyhodnocení (cdr (car par2)).
(d) Při vyhodnocení výrazu (cdr (cdr par2)) dostaneme chybu „CHYBA: Argument není pár“,
protože výsledek vyhodnocení výrazu (cdr par2) je číslo 3,
tedy druhá (vnější) aplikace cdr selže, viz komentář v definici 4.4.
Při složitějších strukturách párů se může stát, že sekvence volání car a cdr budou dlouhé a nepřehledné,
proto jsou ve Scheme k disposici složeniny.
Například místo (car (cdr p)) můžeme psát jen (cadr p).
str99
Ve Scheme jsou složeniny až do hloubky čtyři.
Například na symboly caaaar, cadadr a cddaar budou ještě navázány složené selektory, ale na třeba na cddadar již ne.
Složenin je tedy celkem 28.
Před tím než uvedeme další příklad podotkněme, že složeniny bychom mohli vytvářet sami:
(define caar (lambda (p) (car (car p))))
(define cadr (lambda (p) (car (cdr p))))
(define cdar (lambda (p) (cdr (car p))))
(define cddr (lambda (p) (cdr (cdr p))))
(define caaar (lambda (p) (car (caar p))))
...
5/Příklad 4.7 Uvažujme pár, který navážeme na symbol par vyhodnocením následujícího výrazu:
(define par (cons (cons 10 (cons 20 30)) 40))
(a) Výraz (caar par) se vyhodnotína číslo deset. Jde o totéž jako bychom psali (car (car par)).
(b) Výraz (cdar par) se vyhodnotína číslo 2.
© Vyhodnocení výrazu (caaar par) skončíchybou „CHYBA: Argument není pár“.
(d) V předchozích příkladech jsme vždy používali selektory na páry, které jsme předtím navázali na symboly pomocíspeciální formy define. Samozřejmě, že define se samotnými páry nic společného nemá a selektory bychom mohli použít přímo na páry vytvořené konstruktorem cons bez provádění jakýchkoliv vazeb, například:
(caar (cons (cons 10 20) (cons 30 40))) ;=> 10
(cdar (cons (cons 10 20) (cons 30 40))) ;⇒ 20
(cadr (cons (cons 10 20) (cons 30 40))) ;⇒ 30
(cddr (cons (cons 10 20) (cons 30 40))) ;⇒ 40
Než si ukážeme několik příkladů na použití tečkových párů, popíšeme, jak vypadaéxterní reprezentace tečkových párů, a také si ukážeme, jak se páry znázorňují graficky, pomocí tak zvané boxovénotace.
Externí reprezentace páru majícího první prvek A a druhý prvek B je následující: ( A . B ).
Z této notace pro externí reprezentaci tečkových párů je asi jasné, proč se o nich říká, že jsou „tečkové“.
Viz příklad:
(cons 1 2)) ;⇒ (1 . 2)
V případě, že druhý prvek páru je zase pár, se používázkrácenýzápis.
V tomto zkráceném zápisu se vynechávajízávorky náležející tomu vnitřnímu páru a tečka náležející vnějšímu.
Třeba pár ( A . ( B . C )) můžeme zkráceně zapsat jako pár ( A B . C ).
5/Příklad 4.8 V tomto příkladu vidíme externí reprezentace párů:
(cons 10 20) ;⇒ (10 . 20)
(cons (cons 10 20) 30) ;⇒ ((10 . 20) . 30)
(cons 10 (cons 20 30)) ;⇒ (10 . (20 . 30)) = (10 20 . 30)
(cons (cons 10 (cons 20 30)) 40) ;⇒ ((10 . (20 . 30)) . 40) = ((10 20 . 30) . 40)
(cons 10 (cons (cons 20 30) 40)) ;⇒ (10 . ((20 . 30) . 40)) = (10 (20 . 30) . 40)
(cons (cons 10 20) (cons 30 40)) ;⇒ ((10 . 20) . (30 . 40)) = ((10 . 20) 30 . 40)
Naopak následující výrazy nejsou externí reprezentace tečkových párů: (10 . ), ( . 20), (10 . 20 . 30) a (10 . 20 30).
Nyní si ukážeme grafickéznázornění tečkových párů – boxovou notaci.
Pár je zobrazen jako obdélníček (box) rozdělenýna dvě části.
Do levéčásti boxu se zakresluje první prvek páru a do pravé druhý prvek páru.
Tedy pár ( A . B ) vypadá v boxovénotaci tak, jak je znázorněno na obrázku 4.1.
100
Obrázek 4.1. Boxová notace tečkového páru.
A
B
Obrázek 4.2. Tečkové páry z příkladu 4.8 v boxovénotaci (10 . 20)
10
20
1)
