použijeme include plugin

Lekce 1 Program, jeho syntax a sémantika

Lekce 2 Vytváření abstrakcí pomocí procedur

Cvičení 3

Řešení viz Reseni ke cvicenim

1. Bez použití interpretu určete výsledky vyhodnocení následujících výrazů:

(let () 10) ;⇒
 
(let () x) ;⇒
 
(let () (define x 5)) ;⇒
 
(let () (define x 5) (* x x)) ;⇒
 
(let ((x (+ 5 5))) (* x x)) ;⇒
 
(let* ((x (+ 5 5))) (* x x)) ;⇒
 
(let ((x (+ 5 5))) (* x x) (+ x x)) ;⇒
 
(let ((x 10)) (define x 5) (* x x)) ;⇒
 
(let* ((x 10)) (define x (+ x 1)) (* x x)) ;⇒
 
(let ((x 10)) (define x x) (* x x)) ;⇒
 
(let ((x 10) (y 20)) (+ x y)) ;⇒
 
(let* ((x 10) (y 20)) (+ x y)) ;⇒
 
(let ((x 10) (y x)) (* x y)) ;⇒
 
(let* ((x 10) (y x)) (* x y)) ;⇒
 
(let ((x 10) (y +)) (* x y)) ;⇒
 
(let ((x 10) (y +)) (define y x) (* x y)) ;⇒
 
(let* ((x 10) (y +)) (define y x) (* x y)) ;⇒
 
(let* ((x 10) (y x)) (define y 3) (* x y)) ;⇒
 
(let ((x 10)) (define y 3) (* x y)) ;⇒
 
(let ((x 10) (y (lambda () x))) (+ x (y))) ;⇒
 
(let* ((x 10) (y (lambda () x))) (+ x (y))) ;⇒
 
(let* ((x 10) (y (lambda (x) x))) (+ x (y x))) ;⇒
 
(let* ((x 10) (y (lambda () x)) (x 5)) (+ x (y))) ;⇒
 
(let* ((x 10) (y (lambda (x) x)) (x 5)) (+ x (y x))) ;⇒
 
(let ((x 10)) (define y (lambda () x)) (define x 5) (+ x (y))) ;⇒
 
(let ((x 10)) (define y (lambda (x) x)) (define x 5) (+ x (y x))) ;⇒
 
(let ((x 10)) (+ (let ((y (+ x 1))) (* y 2)) x)) ;⇒
 
(let ((x 10) (x 20)) (+ x x)) ;⇒
 
(let* ((x 10) (x 20)) (+ x x)) ;⇒
 
(if #f (let ((x 10) (x 20)) (+ x x)) 10) ;⇒

2. Přepište následující výrazy na ekvivalentní výrazy bez použitíspeciální forem let a let*.

(let* ((x (+ 10 y))
       (y (let ((x 20)
		(y 30))
	   (* 2 (+ x y)))))
 (/ x y z))
(let ((a 3)
      (b 4)
      (c (let* ((a 10)
		(b 20))
	  (+ a b 10))))
 (+ a b c))
 (let* ((x (let ((x 10))
	    (define x 2)
	    (+ x x)))
	(y (+ x x)))
  (+ x y))

str94 3. Napište proceduru, která vypočte, v jaké výšce dosáhne těleso vržené vzhůru počáteční rychlostí v0 rychlosti v (ve vakuu). Vstupními parametry budou v0 a v. Použijte vzorce: v0 − v 1 t = , s = v0t − gt2. g 2

Lokální vazbu pro t vytvořte jednou pomocí interní definice, podruhé pak pomocí speciální formy let.

Tíhové zrychlení g definujte globálně.

4. Napište proceduru řešící tento typ slovních úloh: Objekt se pohybuje rovnoměrně zrychleným pohy-bem, s počáteční rychlostí v0 se zrychlením a. Vypočtěte dráhu, po které dosáhne rychlosti v. Použijte vzorce: v − vo 1 t = , s = v0t + at2. a 2

Lokální vazbu pro t vytvořte jednou pomocí interní definice, podruhé pomocíspeciální formy let.

5. Předefinujte proceduru navázanou na symbol + na proceduru sčítání druhých mocnin dvou čísel.

6. Napište λ-výraz, který má ve svém těle více než jeden výraz

 a jehož přímočarý přepis na λ-výraz obsahující ve svém těle jeden výraz s požitím speciální formy and
 (viz například [[#P-Program_3_1|programy]] 3.1 a 3.2) se vyhodnotí na jinou proceduru.
 Jinou procedurou v tomto případě myslíme to, že aplikací na nějaký argument bude vracet jiný výsledek.
2014/04/24 16:04

Lekce 4: Tečkové páry, symbolická data a kvotování

Export page to Open Document format 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)

2014/04/24 16:04

Cvičení 5

1. Bez použití interpretu vyhodnoťte následující výrazy:

(cons 1 (cons (cons 2 '()) (cons 3 '()))) ;⇒
 
(cons (cons '() '()) '()) ;⇒
 
(caddr '(1 2 3)) ;⇒
 
(list '1 2 3) ;⇒
 
(list '(1 2 3)) ;⇒
 
(list list) ;⇒
 
(list (+ 1 2)) ;⇒
 
(list '+ 1 2) ;⇒
 
(list + 1 2) ;⇒
 
(list '(+ 1 2)) ;⇒
 
(reverse '(1 2 3)) ;⇒
 
(reverse '((1 2 3))) ;⇒
 
(reverse '(1 (2 3) 4)) ;⇒
 
(build-list 5 -) ;⇒
 
(build-list 3 list) ;⇒
 
(build-list 0 (lambda(x) nedef-symbol)) ;⇒
 
(build-list 1 (lambda (x) '())) ;⇒
 
(map number? '(1 (2 3) 4)) ;⇒
 
(map + '(1 2 3)) ;⇒
 
(map + '(2 4 8) '(1 3 9)) ;⇒
 
(map (lambda (x) (cons 1 x)) '(2 4 8) '(1 3 9)) ;⇒
 
(map (lambda (x) '()) '(1 2 3)) ;⇒
 
(map (lambda (x) nenavazany-symbol) '()) ;⇒
 
(append 1 2) ;⇒
 
(append 1 '(2)) ;⇒
 
(append '(1) '(2)) ;⇒
 
(append (append)) ;⇒
 
(append '(1 2)) ;⇒
 
(append) ;⇒
 
(append '()) ;⇒
 
(append '(1 2) '(3 4) (list 5)) ;⇒
 
(append '(list 5)) ;⇒
 
'(map (lambda (x) '()) 10) ;⇒
 
(quote quote) ;⇒
 
(quote (quote (1 2 3))) ;⇒
 
('quote (1 2 3)) ;⇒
 
(car ''10) ;⇒

str139

2. Naprogramujte proceduru o třech argumentech n, a, d, která vracíseznam prvních n členů aritmetické

posloupnosti {a + nd}∞ n=0

3. Naprogramujte proceduru o třech číselných argumentech n, a a q, která vracíseznam prvních n členů geometrické posloupnosti {aqn}∞ n=0.

4. Naprogramujte konstruktor diagonální čtvercové matice a pomocí něho konstruktor jednotkové matice.

5. Napište obdobu procedury map, která do mapované procedury dává nejen prvek seznamu ale i jeho index. Například:

(map cons '(a b c)) ;⇒ ((a . 0) (b . 1) (c . 2))
 
(map 2-ze-2 '(a b c)) ;⇒ (0 1 2)
2014/03/14 22:15

Lekce 6: Explicitní aplikace a vyhodnocování

Obsah lekce: V předchozích lekcích jsme popsali aplikaci procedur jakožto jednu z částí abstraktního interpretu. Část interpretu odpovědnou za aplikaci jsme označovali „Apply“. Stejně tak jsme popsali část interpretu provádějící vyhodnocování elementů a označovali jsme ji jako „Eval“. V této lekci ukážeme, že „Apply“ a „Eval“ lze bez újmy chápat jako procedury abstraktního interpretu, které mohou programátoři kdykoliv využít k přímé aplikaci procedur na seznamy hodnot a k vyhodnocování libovolných elementů v daném prostředí. Dále ukážeme, že prostředí je možnéchápat jako element prvního řádu.

Klíčová slova: aplikace procedur, procedura apply, procedura eval, prostředí, vyhodnocování elementů.

s6_1

6.1 Explicitní aplikace procedur

Nyní se budeme věnovat aplikaci procedur. V lekci 1 jsme uvedli, že aplikace procedur probíhá v momentě, kdy se první prvek seznamu vyhodnotil na proceduru. Procedura vzniklá vyhodnocením prvního prvku seznamu je aplikována s argumenty jimiž jsou elementy vzniklé vyhodnocením všech dalších prvků seznamu. Této aplikaci procedur můžeme říkat implicitní aplikace, protože je prováděna implicitně během vyhodnocování elementů (seznamů). V některých případech bychom ale mohli chtít prové st explicitní aplikaci dané procedury s argumenty, které máme k dispozici ve formě seznamu – tedy argumenty již máme k dispozici a nechceme je získávat vyhodnocením (nějakých výrazů).

Předpokládejme pro ilustraci, že na symbol s máme navázaný seznam čísel, který jsme získali jako výsledek aplikace nějakých procedur. Z nějakého důvodu bychom třeba mohli chtít prové st součet všech čísel ze seznamu (navázaného na) s. Kdybychom mohli v programu zaručit, že tento seznam bude mít vždy pevnou velikost (vždy stejný počet prvků), pak bychom mohli jeho prvky sečíst pomocí

(+ (car s) (cadr s) (caddr s) · · · ).

Co kdybychom ale délku seznamu dopředu neznali? Pak bychom zřejmě předchozí výraz nemohli přesně napsat, protože bychom neznali počet argumentů, které bychom měli předat proceduře sčítání při její aplikaci. Další problém předchozího kódu je jeho neefektivita. Pro seznam délky n potřebujeme prové st celkem n(1+n) aplikací procedur car a cdr k tomu, abychom vyjádřili všechny argumenty pomocícar, 2 cadr, caddr, a tak dále. Předchozí řešení tedy není ani univerzální ani efektivní.

Předchozí problém by bylo možné snadno vyřešit, kdybychom měli v jazyku Scheme k dispozici Apply (viz definici 2.12 na straně 50) jako primitivní proceduru vyššího řádu, které bychom mohli předat (i) proceduru E, kterou chceme aplikovat,

(i) seznam argumentů E1, . . . , En, se kterými chceme proceduru E aplikovat, a která by vrátila hodnotu aplikace Apply[E, E1, . . . , En].

V jazyku Scheme je taková primitivní procedura skutečně k dispozici. Část interpretu „Apply“, která je odpovědnáza aplikaci procedur, je tedy přístupná programátorovi pomocí primitivní procedury vyššího řádu (vyššího řádu proto, že jedním z předaných argumentů je samotná procedura, kterou chceme aplikovat).

Tato primitivní procedura je navázána na symbol apply a nynísi ji popíšeme.

Definice 6.1 (primitivní procedura apply). Primitivní procedura apply se používás argumenty ve tvaru:

(apply procedura arg1 arg2 ··· argn seznam )

přitom arg1 , . . . , argn jsou nepovinné a mohou být vynechány. Jelikož je apply procedura, je aplikována s argumenty v jejich vyhodnocené podobě. Při aplikaci procedura apply nejprve ověří, zda-li je element procedura primitivnínebo uživatelsky definovaná procedura. Pokud by tomu tak nebylo, ukončíse aplikace hlášením „CHYBA: První argument předanýapply musí být procedura. V opačném případě procedura apply sestavíseznam hodnot ze všech ostatních argumentů, takto: první prvek seznamu hodnot bude arg1 , druhý prvek seznamu hodnot bude arg2 , . . . n-tý prvek seznamu hodnot bude argn a další prvky seznamu hodnot budou tvořeny prvky ze seznamu seznam . str142 Pokud by poslední argument uvedený při aplikaci apply (to jest argument seznam ) nebyl seznam, pak se aplikace ukončí hlášením „CHYBA: Poslední argument předanýapply musí být seznam.“ Výsledkem aplikace apply je hodnota vzniklá aplikací procedury procedura s argumenty jimiž jsou elementy ze sestaveného seznamu hodnot.

Z předchozí definice je tedy jasné, že apply musí být volána alespoň se dvěma argumenty, první z nich se musí vyhodnotit na proceduru (kterou aplikujeme) a posledníz nich se musí vyhodnotit na seznam argumentů, kteréchceme při aplikaci použít (seznam může být prázdný).

Nyní ukážeme několik vysvětlujících příkladů použití apply, praktické příklady budou následovat v dalších sekcích. Nejprve se zaměříme na použití apply pouze se dvěma argumenty, tedy bez arg1 , . . . , argn , viz definici 6.1. Vyhodnocenínásledujících výrazů vede na součet čísel (všimněte si použití apply):

(+ 1 2 3 4 5) ;⇒ 15
(apply + (list 1 2 3 4 5)) ;⇒ 15
(apply + '(1 2 3 4 5)) ;⇒ 15
(apply + 1 2 3 4 5) ;⇒ „CHYBA: Poslední argument předanýapply musí být seznam.“

V posledním případě při aplikaci došlo k chybě, protože posledním argumentem předaným apply nebyl seznam (ale číslo 5). Při použití apply se seznamem hodnot si ale musíme dát pozor na to, že hodnoty v seznamu (poslední argument apply) se používají jako argumenty při aplikaci a nejsou před aplikací vyhodnoceny. Všimněte si například rozdílu v následujících dvou aplikacích:

(apply + (list 1 (+ 1 2) 5)) ;⇒ 9
(apply + '(1 (+ 1 2) 5)) ;⇒ „CHYBA: Pokus o sčítání čísla se seznamem.“

Uvědomte si, že v prvním případě v ukázce vznikl vyhodnocením výrazu (list 1 (+ 1 2) 5) tříprvkový seznam (1 3 5), takže došlo k sečtení těchto hodnot. V druhém případě byla ale procedura sčítání aplikována se seznamem (1 (+ 1 2) 5) jehož druhým prvkem neníčíslo, takže aplikace sčítánína argumenty 1 (číslo), (+ 1 2) (seznam) a 5 (číslo) selhala.

Pokud se nyní vrátíme k našemu motivačnímu příkladu, tak bychom sečtení hodnot v seznamu navázaném na s provedli následovně:

(apply + s)

Použití apply je tedy vhodné v případě, kdy máme dány argumenty (se kterými chceme prové st aplikaci nějaké procedury) v seznamu. Nemusíme přitom předávané argumenty nijak „ručně vytahovat“ ze seznamu (jak to bylo naznačeno na začátku této sekce). V případech, kdybychom neznali délku seznamu, protože by byla proměnlivá, by to stejně k uspokojivému řešenínevedlo.

Následující příklady ukazují další použití apply:

(apply +) ;⇒ „CHYBA: Chybíseznam hodnot.“
(apply + '()) ;⇒ 0
(apply append '()) ;⇒ ()
(apply append '((1 2 3) () (c d) (#t #f))) ;⇒ (1 2 3 c d #t #f)
(apply list '(1 2 3 4)) ;⇒ (1 2 3 4)
(apply cons (list 2 3)) ;⇒ (2 . 3)
(apply cons '(1 2 3 4)) ;⇒ „CHYBA: cons má mít dva argumenty.“
(apply min '(4 1 3 2)) ;⇒ 1

Doposud jsme ukazovali pouze příklady použití apply se dvěma argumenty, to jest s procedurou a seznamem hodnot. Nynísi ukážeme příklady použití apply s více argumenty (viz definici 7.1). Nepovinné argumenty, které se nacházejíza předanou procedurou a před posledním seznamem (který musí být vždy přítomen) jsou při aplikaci předávány tak, jak jsou uvedeny. Následující příklad ukazuje několik možnostísečteníčísel z daného seznamu za použitínepovinných argumentů apply:

(apply + 1 2 3 4 '()) ;⇒ 10
(apply + 1 2 3 '(4)) ;⇒ 10
(apply + 1 2 '(3 4)) ;⇒ 10
(apply + 1 '(2 3 4)) ;⇒ 10
(apply + '(1 2 3 4)) ;⇒ 10

str143 V prvním případě byly nepovinné argumenty čtyři a povinný posledníseznam byl prázdný. V druhém případě byly nepovinné argumenty tři a posledníseznam byl jednoprvkovýa tak dále. Uvědomte si, že nepovinné argumenty budou před aplikací apply, a tedy i před explicitní aplikací předané procedury, vyhodnoceny. Viz rozdíl mezi následujícími aplikacemi:

(apply + '((+ 1 2) 10)) ;⇒ „CHYBA: Pokus o sčítáníčísla se seznamem.“
(apply + (+ 1 2) '(10)) ;⇒ 13

Otázkou je, kdy použít tyto nepovinné argumenty. Používají se v případě, kdy potřebujeme aplikovat proceduru se seznamem hodnot, ale k tomuto seznamu ještě potřebujeme další hodnoty (zepředu) dodat.

Kdybychom například chtěli sečíst všechny hodnoty v seznamu navázaném na l s číslem 1, pak bychom to mohli udělat následujícími způsoby:

(define l '(10 20 30 40 50))
 
(apply + (cons 1 l)) ;⇒ 151
(+ 1 (apply + l)) ;⇒ 151
(apply + 1 l) ;⇒ 151

V prvním případě jsme ručně jedničku připojili jako nový první prvek seznamu hodnot. V druhém případě jsme přičtení jedničky provedli až po samotné aplikaci. V tomto případě to bylo možné, ale u některých procedur bychom to takto řešit nemohli (uvidíme dále). Poslední příklad byl nejkratší a nejčistší, využili jsme jeden nepovinnýargument – přidání jedničky k seznamu argumentů za nás vyřeší procedura apply.

Následující příklad je o něco složitějšína představivost, ale ukazuje praktičnost nepovinných argumentů, které lze předat proceduře apply. Uvažujme tedy aplikaci:

(apply map list '((a b c) (1 2 3))) ;⇒ ((a 1) (b 2) (c 3))

Při této aplikaci došlo k aplikování map jehož prvním argumentem byla procedura navázanána list, druhý a třetí argument byly prvky seznamu ((a b c) (1 2 3)). Předchozí aplikaci si tedy můžeme představit jako vyhodnocenínásledujícího výrazu:

(map list '(a b c) '(1 2 3)) ;⇒ ((a 1) (b 2) (c 3))

Nyní by již výsledná hodnota měla být jasná. Procedura map má první argument jiného významu než ostatní argumenty, technicky bychom tedy nemohli prové st trik jako byl v případě + proveden na třetím řádku v předchozí ukázce.

Na aplikaci procedur na seznamy argumentů se lze dívat jako na způsob agregace elementů seznamu do jediné hodnoty. Aplikaci pomocí apply používáme v případě, kdy máme vytvořený seznam hodnot, třeba nějakým předchozím výpočtem, a chceme na tento celý seznam aplikovat jednu proceduru. Při aplikaci (tímto způsobem) je potřeba pamatovat na to, že prvky v seznamu předaném apply jsou aplikované proceduře předány „jak leží a běží“, tedy bez dodatečného vyhodnocování.

s6_2

6.2 Použití explicitní aplikace procedur při práci se seznamy

V minulé lekci jsme ukázali řadu procedur pro práci se seznamy. Pro některéz těchto procedur jsme ukázali, jak bychom je mohli naprogramovat, kdybychom je v jazyku Scheme implicitně neměli. Nyní budeme v této problematice pokračovat a zaměříme se přitom na využití apply.

Prvním problémem bude stanovení délky seznamu. V předchozí lekci jsme ukázali proceduru length, která pro daný seznam vrací počet jeho prvků. Nyní ukážeme, jak tuto proceduru naprogramovat. Předpokládejme, že máme na symbol s navázaný nějaký seznam, třeba:

(define s '(a b c d e f g))
s ;⇒ (a b c d e f g)

str144 Jak napsat výraz, jehož vyhodnocením bude délka seznamu navázaného na s? Jde nám přitom o to, nalézt obecné řešení. To jest, když změníme seznam s, vyhodnocením výrazu by měla být délka modifikovaného seznamu. Délku seznamu získáme tak, když sečteme počet jeho prvků. Při výpočtu délky by tedy zřejmě mělo hrát roli sčítání. Nejde však o sčítání elementů nacházejících se v seznamu (což nemusí být ani čísla, jako v našem případě), ale o jejich „počet“. V seznamu se na každé jeho pozici nachází jeden element. Na základě seznamu s tedy můžeme vytvořit seznam stejné délky tak, že každý prvek ze seznamu s zaměníme za 1:

(map (lambda (x) 1) s) ;⇒ (1 1 1 1 1 1 1)

K záměně jsme použili mapování konstantní procedury vracející pro každýargument číslo 1. Nyní již stačí aplikovat na vzniklý seznam proceduru sčítání. Takže délku seznamu navázaného na s spočítáme pomocí:

(apply + (map (lambda (x) 1) s)) ;⇒ 7

Zopakujme si ještě jednou použitou myšlenku: klíčem k vypočtení délky seznamu bylo „sečíst tolik jedniček, kolik bylo prvků ve výchozím seznamu“. Potřebovali jsme tedy udělat jeden mezikrok, kdy jsme z daného seznamu vytvořili seznam stejné délky obsahujícísamé jedničky, pak již jen stačilo aplikovat sčítání. Uvědomte si zde dobře roli apply. Procedura sčítání je aplikována na seznam „neznámé délky“ (délku seznamu se teprve snažíme zjistit) obsahující hodnoty, se kterými chceme proceduru sčítání aplikovat; například tedy výraz:

(+ (map (lambda (x) 1) s)) ;⇒ „CHYBA: Nelze sčítat seznam.“

by tedy nebyl nic platný. Podle výše uvedeného postupu tedy můžeme naprogramovat proceduru pro výpočet délky seznamu jak je tomu v programu 6.1.

5;Program 6.1 Výpočet délky seznamu.

(define length
  (lambda (l)
    (apply + (map (lambda (x) 1) l))))

Všimněte si, že procedura funguje skutečně stejně tak jako procedura length, kterou jsme představili v předchozí lekci a to včetně mezního případu. To jest, délka prázdného seznamu je nula, viz následující příklady:

(length '(a b c d)) ;⇒ 4
(length '(a (b (c)) d)) ;⇒ 3
(length '()) ;⇒ 0

Na tomto příklady je dobře vidět, že pokud provedeme při programovánísprávný myšlenkový rozbor problému, nemusíme se zabývat ošetřování okrajových případů, což často vede ke vzniku nebezpečných chyb, které nejsou vidět.

Pokud někteří čtenáři doposud pochybovali o užitečnosti definovat procedury jako jsou sčítání a násobení „bez argumentů“, tak nyní vidíme, že je to velmi výhodné. Kdyby nebylo sčítání definováno pro prázdný seznam (to jest (+) ;⇒ 0), tak bychom v proceduře length v programu 6.1 museli ošetřovat speciální případ, kdy bude na argument l navázán prázdný seznam. Kdybychom ošetřeníneprovedli, length by počítala pouze délky neprázdny ćh seznamů. Při některých aplikacích length v programu by bylo nutné dělat dodatečné testy prázdnosti seznamu – což by vše jen komplikovalo kód.

Nyní ukážeme užitečnou a často používanou proceduru (vyššího řádu), která provádí filtraci elementů v seznamu podle jejich vlastnosti (predikát jednoho argumentu), která je dodanáspolu se seznamem formou argumentu. Pro objasnění si nejprve ukážeme několik příkladů, na kterých uvidíme, jak bychom chtěli proceduru používat:

str145

(filter even? '(1 2 3 4 5 6)) ;⇒ (2 4 6)
(filter (lambda (x) (<= x 4)) '(1 2 3 4 5 6)) ;⇒ (1 2 3 4)
(filter pair? '(1 (2 . a) 3 (4 . k))) ;⇒ ((2 . a) (4 . k))
(filter (lambda (x)
	  (not (pair? x)))
	'(1 (2 . a) 3 (4 . k))) ;⇒ (1 3)
(filter symbol? '(1 a 3 b 4 d)) ;⇒ (a b d)

V prvním případě procedura z daného seznamu čísel vyfiltrovala všechna sudáčísla, v druhém případě byla vyfiltrována čísla menšínebo rovna čtyřem, v třetím případě byly ze seznamu vyfiltrovány páry, v dalším případě vše kromě párů a v posledním případě symboly. Proceduru filter tedy chceme používat se dvěma argumenty: prvním je predikát jednoho argumentu a druhým je seznam. Chceme, aby procedura vrátila seznam, ve kterém budou právě ty prvky z výchozího seznamu, pro které je daný predikát pravdivý (přesněji: výsledek jeho aplikace je cokoliv kromě #f).

Při implementaci filtrace tedy musíme vyřešit problém, jak vynechávat prvky v seznamu. Zde bychom si mohli pomoci aplikací procedury pro spojováníseznamů, protože při spojovánínehrají roli „prázdné seznamy“, ve výsledku spojení jsou vynechány. Můžeme tedy říct, že výsledkem filtrace je spojení jedno prvkových seznamů obsahujících prvky z původního seznamu splňující danou vlastnost. V prvním kroku nám tedy z výchozího seznamu stačí vytvořit nový seznam, ve kterém budou: (i) všechny prvky splňující danou vlastnost obsaženy v jednoprvkových seznamech a (ii) místo ostatních prvků zde budou prázdné seznamy. K vytvoření tohoto seznamu můžeme použít map. Uvažujme následujícíseznam navázanýna s a vlastnosti reprezentovanou predikátem navázaným na even?:

(define s '(1 3 2 6 1 7 4 8 9 3 4))
s ;⇒ (1 3 2 6 1 7 4 8 9 3 4)

Pak následujícím mapováním získáme:

(map (lambda (x)
       (if (even? x)
	 (list x)
	 '()))
     s) ;⇒ (() () (2) (6) () () (4) (8) () () (4))

Na takto vytvořený seznam již jen stačí aplikovat append:

(apply append
       (map (lambda (x)
	      (if (even? x)
		(list x)
		'()))
	    s)) ;⇒ (2 6 4 8 4)

což je výsledek filtrace sudých čísel z výchozího seznamu. Hlavní myšlenkou filtrace tedy bylo zřetězení jednoprvkových, případně prázdných, seznamů obsahující filtrované prvky (jednoprvkové seznamy obsahovaly právě prvky splňující vlastnost). Obecnou filtrační proceduru tedy můžeme naprogramovat zobecněním předchozího principu. Viz proceduru filter v programu 6.2. Podotkněme, že stejně jako tomu bylo v případě length máme naším přístupem opět automaticky vyřešen mezní případ filtrace prvků z prázdného seznamu. Viz příklady:

(filter even? '()) ;⇒ ()
(filter (lambda (x) #f) '()) ;⇒ ()

Filtrace je ve funkcionálních jazycích velmi oblíbená. Skoro každý funkcionální programovací jazyk je vybaven nějakou filtrační procedurou vyššího řádu. Pokud ne, lze ji snadno naprogramovat jako tomu bylo v programu 6.2. S pomocí filtrace lze naprogramovat celou řadu užitečných procedur. V programu 6.3 máme příklady dvou z nich. Procedura remove je vlastně jen „nepatrnou modifikací“ předchozí filtrační procedury, která spočívá v tom, že prvky splňující danou vlastnost jsou ze seznamu odstraňovány místo toho aby byly ponechávány. S pomocí filter již můžeme remove naprogramovat snadno – stačí, abychom str146

5;Program 6.2 Filtrace prvků seznamu splňujících danou vlastnost.

(define filter
  (lambda (f l)
    (apply append
	   (map (lambda (x)
		  (if (f x)
		    (list x)
		    '()))
		l))))

5;Program 6.3 Odstraňování prvků seznamu a test přítomnosti prvku v seznamu.

(define remove
  (lambda (f l)
    (filter (lambda (x)
	      (not (f x)))
	    l)))
 
(define member?
  (lambda (elem l)
    (not (null? (filter
		  (lambda (x)
		    (equal? x elem))
		  l)))))

totiž aplikovali filter s vlastností reprezentujícínegaci vlastnosti pro remove, viz program 6.3. Druhou procedurou v programu 6.3 je predikát member? testující přítomnost daného prvku v seznamu. Myšlenka této procedury je založena na tom, že daný prvek E je obsažen v seznamu, pokud vyfiltrováním prvků vlastnosti „prvek je roven E“ vznikne neprázdný seznam (to jest musí být v něm aspoň jeden prvek roven E).

Viz příklady použití:

(member? 'a '()) ;⇒ #f 
(member? 'a '(1 2 3 4)) ;⇒ #f
(member? 'a '(1 2 a 3 4)) ;⇒ #t

V předchozí lekci jsme ukázali proceduru list-ref, která pro daný seznam a danou pozici (číslo) vrací prvek na dané pozici. Nynísi můžeme ukázat, jak lze pomocí filtrace danou proceduru naprogramovat, viz program 6.4. Myšlenka je v tomto případě následující.

5;Program 6.4 Procedura vracející prvek na dané pozici v seznamu.

(define list-ref
  (lambda (l index)
    (let ((indices (build-list (length l) (lambda (i) i))))
      (cdar
	(filter (lambda (cell) (= (car cell) index))
		(map cons indices l))))))

Procedura list-ref si nejprve s použitím procedury build-list vytvoří pomocný seznam indexů (0 1 2 3 · · ·, který je stejně dlouhý jako vstupní seznam.

str147 Pomocí mapování je potom vytvořen pomocný seznam párů ve tvaru ( index . prvek ), přitom prvek je právě prvek seznamu na pozici index . Pak už jen stačí vyfiltrovat z tohoto seznamu prvky (respektive prvek, bude jediný) s vlastností „první prvek páru (to jest index) má hodnotu danou argumentem index“.

Nakonec stačí jen z tohoto páru vybrat druhý prvek, což je element na dané pozici.

Další zajímavou aplikací filtrace by mohla být procedura list-indices, která vlastně provádí opak toho, co procedura list-ref. Procedura akceptuje jako argumenty seznam a element a vracíseznam pozic (indexů), na kterých se danýelement v seznamu vyskytuje. Obecně je toto řešení lepšínež vracet například jen jednu (první) pozici, protože prvek se může v seznamu vyskytovat na víc místech. Proceduru máme uvedenu v programu 6.5. Princip jejího vytvoření je podobný jako u procedury list-ref.

Program 6.5. Procedura vracející všechny pozice výskytu daného prvku.

(define list-indices
  (lambda (l elem)
    (let ((indices (build-list (length l) (lambda (i) i))))
      (remove null?
	      (map (lambda (x id)
		     (if (equal? x elem)
		       id
		       '()))
		   l
		   indices)))))

Opět si vytvoříme seznam pomocných indexů a mapováním přes předaný seznam a seznam indexů vytváříme nový seznam, který bude obsahovat buď indexy (v případě že na dané pozici prvek je), nebo prázdné seznamy. Z tohoto meziproduktu již nám pak stačí odstranit prázdné seznamy a získáme tak seznam indexů reprezentujících pozice všech výskytů daného prvku. Viz příklady použití:

(list-indices '(a b b a c d a) 'a) ;⇒ (0 3 6)
(list-indices '(a b b a c d a) 'd) ;⇒ (5)
(list-indices '(a b b a c d a) 10) ;⇒ ()
(list-indices '() 'a) ;⇒ (

)

V sekci 5.8 jsme implementovali procedury pro vytváření matic, a také procedury pro jejich sčítání a odčítání.

Nyní tuto sadu rozšíříme o transpozici matice matrix-transpose a násobení dvou matic matrix-*.

(define matrix-transpose
  (lambda (m)
    (apply map list m)))

Proceduru map jsme aplikovali na matici, která je reprezentovaná jako seznam seznamů. Mapováním procedury list na seznamy představující řádky, dostáváme seznam seznamů s čísly ve stejných sloupcích.

Tento seznam můžeme považovat za transponovanou matici.

Násobení matic bychom mohli implementovat následovně. Abychom pracovali jen s řádky, transponujeme druhou matici použitím matrix-transpose. Každý řádek x první matice skalárně vynásobíme s každým řádkem y transponované druhé matice a dostaneme prvek výsledné matice:

(define matrix-*
  (lambda (m1 m2)
    (let ((t (matrix-transpose m2)))
      (map (lambda (x)
	     (map (lambda (y)
		    (apply + (map * x y)))
		  t))
	   m1))))

str148

V sekci 5.8 jsme implementovali i selekce a projekce nad databázovými tabulkami. Tyto tabulky byly reprezentovány pomocíseznamů, jejichž prvky byly stejně dlouhé seznamy – řádky. Řádky při selekci byly přitom voleny na základě indexů těchto řádků. Pomocí filtrování můžeme vybírat řádky na základě predikátu. Procedura pro selekci (výběr řádků) bude vytvořena s využitím procedury filter:

(define selection
  (lambda (table property)
    (filter (lambda (x)
	      (apply property x))
	    table)))

Procedura selekce tak bude fungovat pro libovolný počet sloupců. Viz příklad použití:

(define mesta
  '((Olomouc 120 3 stredni)
    (Prostejov 45 2 male)
    (Prerov 50 3 male)
    (Praha 1200 8 velke)))
 
(selection mesta
	   (lambda (jmeno p-obyvatel p-nadrazi velikost)
	     (and (>= p-obyvatel 50)
		  (not (equal? velikost 'male))))) ;⇒ ((olomouc 120 3 stredni)
								(praha 1200 8 velke))

s6_.3

6.3 Procedury s nepovinnými a libovolnými argumenty

Řada primitivních procedur, se kterými jsme se doposud setkali, umožňovala mít při jejich aplikaci některé argument nepovinné. Například procedura map musela mít k dispozici jako argument proceduru a seznam a volitelně jako nepovinné argumenty ji mohly být předány ještě dalšíseznamy. Některé primitivní procedury, jako například +, * a append mohly být aplikovány dokonce s libovolným počtem argumentů, včetně žádného argumentu. V této sekci si ukážeme, jak lze vytvářet uživatelsky definované procedury s nepovinnými argumenty nebo s libovolnými argumenty.

Nejprve ukážeme, jak je možné vytvořit procedury, které mají několik povinných argumentů, které musejí být vždy uvedeny, a kromě nich mohou být předány dalšínepovinné argumenty. Platí podmínka, že nepovinné argumenty lze uvádět až za všemi povinnými. Při psaní λ-výrazů jejichž vyhodnocením mají vzniknout procedury pracujícís nepovinnými argumenty, píšeme místo tradičníspecifikace seznamu argumentů ( param1 param2 · · · paramn ), kterou jsme používali doposud, seznam argumentů ve tvaru

( param1 param2 · · · paramn . zbytek ),

kde param1 , param2 , . . . , paramn , zbytek jsou vzájemně různé symboly. To jest kromě povinných formálních argumentů (zapsaných jako dosud), jsme pomocí tečky „.“ oddělili poslednísymbol zbytek . Přísně vzato, struktura argumentů zapsaná v tomto tvaru již neníseznam, protože druhý prvek jeho „posledního páru“ není prázdný seznam. Úkol argumentu zbytek je následující. Při aplikaci procedury vzniklé vyhodnocením λ-výrazu se hodnoty všech povinných argumentů navážína symboly param1 , . . . , paramn (jako doposud). Pokud byly navíc při aplikaci použity další argumenty, pak je vytvořen seznam všech těchto dodatečných argumentů a při aplikaci procedury je tento seznam navázanýna symbol zbytek . Pokud tedy žádné nepovinné argumenty nebyly předány, na zbytek bude navázaný prázdný seznam.

str149 Následující příklad demonstruje použití nepovinných argumentů:

((lambda (x y . rest) (list x y rest)) 1 2) ;⇒ (1 2 ())
((lambda (x y . rest) (list x y rest)) 1 2 3) ;⇒ (1 2 (3))
((lambda (x y . rest) (list x y rest)) 1 2 3 4 5) ;⇒ (1 2 (3 4 5))
((lambda (x y . rest) (list x y rest)) 1) ;⇒ „CHYBA: Chybí argument.“

V předchozích případech jsme tedy definovali proceduru, která měla dva povinné argumenty (v proceduře reprezentované formálními argumenty x a y) a dále mohla mít nepovinné argumenty, jejichž seznam byl při aplikaci navázanýna symbol rest. V prvním případě byly předány právě dva povinné argumenty, takže seznam nepovinných argumentů byl prázdný. V druhém případě již seznam nepovinných argumentů obsahoval jeden prvek. V třetím případě bylo předáno celkem pět argumentů, takže seznam nepovinných argumentů obsahoval poslední tři z nich.

Příklad použití nepovinných argumentů je v programu 6.6.

5;Program 6.6 Test přítomnosti prvku v seznamu s navrácením příznaku.

(define find
  (lambda (elem l . not-found)
    (cond ((member? elem l) elem)
	  ((null? not-found) #f)
	  (else (car not-found)))))

Procedura find provádí podobnou činnost jako procedura member? z programu 6.3 na straně 147 (find je, jak vidíme, dokonce naprogramovaná pomocí member?). Procedura find má dva povinné argumenty, prvním z nich je element, druhým je seznam. Procedura slouží k rozhodování, zda-li se danýelement nachází v seznamu hodnot. V případě nalezení je ale vrácen samotnýelement (to se může v některých případech hodit), v případě nenalezení je vráceno standardně #f. Co kdybychom ale chtěli v seznamu hledat element „nepravda“, to jest samotné #f? Pak bychom vždy tak jako tak dostali jako výsledek aplikace #f (v případě nalezení i nenalezení prvku v seznamu). Problém bychom mohli napravit tak, že proceduře budeme předávat nepovinnýargument, jehož hodnota bude vrácena v případě, kdy prvek nalezen nebude. Pokud nepovinnýargument nebude uveden, pak při nenalezení prvku vrátíme standardní #f. Viz ukázky použití procedury:

(find 'a '(a b c d)) ;⇒ a
(find 'x '(a b c d)) ;⇒ #f
(find 'a '(a b c d) 'prvek-nenalezen) ;⇒ a
(find 'x '(a b c d) 'prvek-nenalezen) ;⇒ prvek-nenalezen
(find #f '(a b c d)) ;⇒ #f
(find #f '(a b #f d)) ;⇒ #f
(find #f '(a b c d) 'prvek-nenalezen) ;⇒ prvek-nenalezen
(find #f '(a b #f d) 'prvek-nenalezen) ;⇒ #f

Všimněte si, že procedura find pracuje de facto pouze s jedním nepovinným argumentem. Zbytek nepovinných argumentů, které by byly při její aplikaci předány v seznamu navázaném na symbol not-found, je procedurou ignorován.

Nyní obrátíme naši pozornost na problematiku předávání libovolného počtu argumentů. V předchozínotaci musela mít každý procedura aspoň jeden povinnýargument, protože výraz ( . rest) by nebyl syntakticky správně. Co když ale potřebujeme definovat proceduru, která může mít jakýkoliv počet argumentů. Z praxe takové procedury známe a víme o tom, že „libovolné argumenty“ jsou užitečné (vzpomeňme například jen proceduru append).

Uživatelsky definované procedury, které mají mít libovolný počet argumentů, vznikají vyhodnocením λ-výrazů, ve kterých je místo seznamu formálních argumentů uveden jedinýsymbol. Na tento jedinýsymbol bude při aplikaci navázán seznam všech argumentů. Viz příklady pro ilustraci:

((lambda args (list 'predano args)) 1 2 3 4 5 6) ;⇒ (predano (1 2 3 4 5 6))
((lambda args (list 'predano args))) ;⇒ (predano ())
((lambda args (reverse args)) 1 2 3 4 5 6) ;⇒ (6 5 4 3 2 1)

str150 V prvních dvou příkladech byla aplikována procedura, která jako výsledek vrátila dvouprvkový seznam: na jeho první pozici byl symbol predano a na druhé pozici byl seznam všech předaných argumentů. V třetím případě jsme viděli ukázku procedury, která dané argumenty vrátí v obráceném seznamu.

V programu 6.7 je uvedena procedura +2m provádějícísoučet čtverců přes libovolné argumenty.

5;Program 6.7 Součet druhých mocnin.

(define
  +2m
  (lambda values
    (apply + (map (lambda (x) (* x x)) values))))

V druhé lekci jsme v programu 2.1 na straně 51 definovali proceduru na výpočet součtu dvou čtverců jako jednu z prvních procedur vůbec. V programu 6.7 se tedy nachází její zobecnění pracující s libovolným počtem argumentů. Pomocí mapování je ze seznamu čísel vytvořen seznam jejich druhých mocnin a pomocí aplikace sčítání je získána výsledná hodnota. Vše opět funguje i v mezním případě, kdy je procedura +2m zavolána bez argumentu. Viz následující příklady:

(+2m) ;⇒ 0
(+2m 2) ;⇒ 4
(+2m 2 3) ;⇒ 13
(+2m 2 3 4) ;⇒ 29

Následující procedura provádíspojení libovolně mnoha seznamů v opačném pořadí:

(define rev-append
  (lambda lists
    (reverse (apply append lists))))

Proceduru můžeme použít následovně:

(rev-append) ;⇒ ()
(rev-append '(a b)) ;⇒ (b a)
(rev-append '(a b) '(c d)) ;⇒ (d c b a)
(rev-append '(a b) '(c d) '(1 2 3)) ;⇒ (3 2 1 d c b a)

V předchozí lekci jsme ukázali konstruktor seznamu list. Nyní je ale jasné, že pokud máme k dispozici aparát pro předávání libovolného množství argumentů pomocí jejich seznamu, pak lze proceduru list snadno naprogramovat tak, jak je to uvedeno v programu 6.8. V tomto programu je procedura list

5;Program 6.8 Vytvoření konstruktoru seznamu.

(define list
  (lambda list list))

definována jako procedura akceptující libovolné argumenty, která vrací seznam těchto argumentů, což je přesně to, co provádí list představený v předchozí lekci.

Následující definice shrnuje, jak vypadásyntaxe λ-výrazů. V tomto ani v následujícíčásti učebního textu (týkajícíse imperativních rysů při programování) ji již nebudeme nijak rozšiřovat.

str151 Definice 6.2 (λ-výraz s nepovinnými a libovolnými formálními argumenty). Každý seznam ve tvaru

  • (lambda (param1 param2 · · · paramm ) výraz1 výraz2 · · · výrazk ),
  • nebo (lambda ( param1 param2 · · · paramn . zbytek ) výraz1 výraz2 · · · výrazk ),
  • nebo (lambda parametry výraz1 výraz2 · · · výrazk ),

kde

  • n, k jsou kladnáčísla,
  • m je nezápornéčíslo,
  • param1 , param2 , . . . , paramn , zbytek jsou vzájemně různé symboly,
  • parametry je symbol, a výraz1 , . . . , výrazk jsou libovolné výrazy tvořící tělo,

se nazývá λ-výraz (lambda výraz). Symboly param1 , . . . , paramn se nazývají formální argumenty (někdy též parametry).

Čísla m, n nazýváme počet povinných formálních argumentů (parametrů). Symbol zbytek se nazývá formální argument (parametr) zastupujícíseznam nepovinných argumentů. Symbol parametry se nazývá formální argument (parametr) zastupujícíseznam všech argumentů.

V jazyku Scheme je možné vytvářet uživatelsky definované procedury, které mají jakýkoliv počet argumentů, nebo mají některé argumenty povinné, vždy alespoň jeden, a ostatní argumenty jsou nepovinné.

V obou případech jsou nepovinné argumenty předávány proceduře formou seznamu, který je navázanýna speciální formální argument.

Poznámka 6.3. Programovací jazyky mají různé způsoby, jak předat nepovinné argumenty. Jednou z oblíbených metod, kterou disponují například jazyky jako je Common LISP, PHP a další je předávání nepovinných argumentů, které jsou identifikovány svým jménem (tak zvaným klíčem).

s6_4

6.4 Vyhodnocování elementů a prostředí jako element prvního řádu

Nyní se budeme věnovat primitivní proceduře, pomocíniž budeme schopni získat na žádost hodnotu vzniklou vyhodnocením elementu. Analogicky jako jsme v předešlých sekcích řekli, že „Apply“ je k dispozici programátorovi prostřednictvím primitivní procedury vyššího řádu apply, tak i „Eval“ bude uživateli k dispozici prostřednictvím primitivní procedury (vyššího řádu) eval. Pomocí této primitivní procedury budeme moci provádět explicitní vyhodnocení elementů. Veškeré doposud používané vyhodnocování bylo vždy implicitní.

Primitivní procedura eval je aplikována se dvěma argumenty z nichž druhýargument je nepovinný. Prvním (povinným) argumentem je element, který chceme vyhodnotit. Druhým nepovinným argumentem je prostředí, ve kterém chceme daný element vyhodnotit. Pokud není prostředí uvedeno, eval bude uvažovat vyhodnocení v globálním prostředí PG. Výsledkem aplikace eval pro dané argumenty je výsledek vyhodnocení elementu v prostředí. Z toho, co jsme teď řekli plyne, že argumenty předávaneéval plně korespondujís argumenty pro „Eval“ tak, jak byla popsán v lekci 2, viz definici 2.7 na straně 48.

Uveďme si nyní nějaké příklady použití eval, zatím pouze s jedním argumentem jímž je element, který bude vyhodnocen:

(eval 10) ;⇒ 10
(eval '+) ;⇒ „procedura sčítáníčísel“
(eval '(+ 1 2)) ;⇒ 3

Předchozí tři příklady korespondují s body (A), (B) a (C) definice vyhodnocování, protože číslo se vyhodno-tilo na sebe sama, symbol + se vyhodnotil na svou vazbu a seznam se vyhodnotil obvyklým postupem. Zde upozorněme na fakt, že eval je skutečně procedura, tedy před její aplikací jsou vyhodnoceny její argumenty.

Proto jsme museli předat proceduře symbol + pomocí kvotování, stejně tak seznam (+ 1 2). Kdybychom to neučinili, symbol + by se vyhodnotil na svou vazbu a proceduře eval by byla předána k vyhodnocení procedura. V tom případě by se dle bodu (D) procedura vyhodnotila na sebe sama:

(eval +) ;⇒ „procedura sčítání čísel“
((eval +) 1 2) ;⇒ 3

V tomto bodu by nám asi mělo být jasné, proč jsme do definice vyhodnocování, viz definici 2.7 na straně 48, přidali bod (D). Doposud se během výpočtu vyhodnocovaly pouze elementy, které byly interními formami symbolických výrazů – těch, co jsme uvedli v programu. Pokud ale máme k dispozici evaluátor ve formě procedury eval, je možné mu předat libovolnýelement k vyhodnocení, tedy i element, kterýnení interní formou žádného symbolického výrazu, jak je tomu například u procedur.

str152 Pomocí eval je možné manipulovat s daty jako s programem. V předchozích lekcích jsme upozornili na fakt, že programy v jazyku Scheme lze chápat jako data. Interní formy seznamů jsou konstruovány pomocí párů. Pomocí eval tedy máme možnost vyhodnocovat datové struktury reprezentující „kusy programu“.

To nám na jednu stranu dávaóbrovský potenciál, protože můžeme třeba uživatelský vstup transformovat na kód a spustit jej, což usnadňuje řadu operací. Na druhou stranu je použití eval krajně nebezpečné a mělo by být vždy odůvodněné.

V následujícím příkladu ukazujeme konstrukci dvou seznamů (data), která jsou použita „jako program“:

(eval (cons '+ (cons 1 (cons 2 '())))) ;⇒ 3
(eval (cons + (cons 1 (cons 2 '())))) ;⇒ 3
(cons + (cons 1 (cons 2 '()))) ;⇒ („procedura sčítáníčísel“ 1 2)

Všimněte si, že na druhém řádku byl zkonstruován seznam („procedura sčítání čísel“ 1 2), který začíná procedurou a dalšími prvky jsou dvě čísla. Oproti prvnímu řádku tedy nestojína prvním místě seznamu symbol, ale přímo procedura. Této situace bychom nemohli dosáhnout, kdybychom nepoužívali eval explicitně.

V následující ukázce jsme vyhodnocením vytvořili proceduru a dále ji aplikovali. Jelikož eval s jedním argumentem vyhodnocuje elementy v globálním prostředí, bude prostředí vzniku této procedury právě globální prostředí:

(eval '(lambda (x) 10)) ;⇒ „konstantní procedura vracející 10“
((eval '(lambda (x) 10)) 20) ;⇒ 10
(apply (eval '(lambda (x) 10)) 20 '()) ;⇒ 10

Vyhodnocení následujícího výrazu končí chybou

(let ((x 10))
  (eval '(+ x 1))) ;⇒ „CHYBA: Symbol x nemá vazbu.“

protože seznam (+ x 1) byl vyhodnocen v globálním prostředí (ve kterém x nemá vazbu) a to i navzdory tomu, že eval jsme uvedli v let-bloku, kde měl symbol x vazbu.

Jako další příklad si uveďme následující proceduru vyššího řádu:

(define proc
  (lambda (c)
    (eval '(lambda (x) (+ x c)))))

Tato procedura při své aplikaci vracínovou proceduru, která byla ale vytvořena v globálním prostředí.

To jest při aplikaci proc je sice předán argument navázanýna c, jeho vazba ale není viditelnáz prostředí vzniku vrácené procedury. Kdybychom tuto vrácenou proceduru aplikovali, vazba symbolu c by byla hledána v globálním prostředí, viz ukázku:

((proc 10) 20) ;⇒ „CHYBA: Symbol c nemá vazbu.“
(define c 100)
((proc 10) 20) ;⇒ 120

Kdybychom někdy potřebovali vyrábět proceduru vyhodnocením seznamu (třeba protože část procedury by byla dodána až během činnosti programu pomocí interakce s uživatelem), pak bychom mohli problém s vazbou volných symbolů vyřešit tak, že místo symbolů bychom do seznamu rovnou dosadili výsledky jejich vyhodnocení – jejich vazby v aktuálním prostředí, ve kterém eval aplikujeme. Viz následující ukázku:

(define proc
  (lambda (c)
    (eval (list 'lambda
		(list 'x)
		(list '+ 'x c)))))

V tomto případě procedura proc vrací proceduru, která vznikne vyhodnocením seznamu v globálním prostředí. V tomto případě jsem ale do seznamu místo symbolu c vložili hodnotu jeho vazby v lokálním prostředí procedury proc. Vytvořili jsme tak vlastně seznam ve tvaru str153

(lambda (x) (+ x „hodnota c“))

a ten byl vyhodnocen v globálním prostředí. Vzniklou proceduru již tedy můžeme používat bez nutnosti provádět globální definici a procedura má kýžený efekt:

((proc 10) 20) ;⇒ 30

Z pohledu jazyka Scheme jsou data totéž co program. Program lze chápat jako data a data mohou být použita pomocí eval jako program. Při používání eval je však potřeba dbát velké obezřetnosti, protože jeho (nadměrné) používání často znesnadňuje ladění programu. Chyby mohou vznikat za běhu programu, aniž by byly v programu „vidět“ na nějakém jeho konkrétním místě.

Našim dalším cílem bude naimplementovat procedury forall a exists reprezentující kvantifikátory ∀ (všeobecný kvantifikátor „pro každý . . . “) a ∃ (existenční kvantifikátor „existuje . . . “). Budou jako argument brát predikát o jednom argumentu predikát a seznam seznam a vracet pravdivostní hodnotu. V případě forall to bude pravda #t, pokud každý prvek seznamu seznam splňuje predikát predikát a jinak #f.

Procedura pro existenční kvantifikátor bude vracet #t, pokud alespoň jeden prvek ze seznamu seznam splňuje predikát predikát . V opačném případě bude vracet #f. Jelikož obě procedury si budou podobné, omezíme se v následujícím na rozbor procedury forall modeující všeobecný kvantifikátor.

Pomocí map a daného predikátu dostaneme z původního seznamu seznam pravdivostních hodnot určujících, zda-li prvek na dané pozici splňuje podmínku danou predikátem: (map predikát seznam ).

Nyní potřebujeme zjistit, jaké pravdivostní hodnoty seznam obsahuje. V případě, že by and byla procedura, mohli bychom toho dosáhnout pomocí procedury apply. Ale jelikož jde o speciální formu, obdržíme při případném pokusu o aplikaci chybu:

(apply and '(#t #t #f)) ;⇒ „CHYBA: Nesprávné použitíspeciální formy and“

Potřebujeme tedy mít „and“ a „or“ jako procedury libovolně mnoha argumentů. Budeme se teď zabývat tímto problémem. Proceduru pro „and“ – and-proc bychom mohli implementovat například takto:

(define and-proc
  (lambda args
    (null? (remove (lambda (x) x) args))))

Nejdříve jsme použitím procedury remove ze seznamu argumentů navázaného na symbol args odstranili všechny prvky různé od #f, použitím procedury remove s procedurou identity. Poté jsme otestovali, zda je výsledný seznam prázdný. Pokud ano, znamená to, že žádnýargument procedury and-proc nebyl nepravda #f, a tedy výsledkem aplikace procedury and-proc bude pravda. V opačném případě bude výsledkem and-proc nepravda.

Procedura and-proc je tedy implementací operace logické konjunkce:

(and-proc) ;⇒ #t
(and-proc 1 2 3) ;⇒ #t

rozdíl oproti and:

(and 1 2 3) ;⇒ 3
(and-proc #t (< 1 2) #t) ;⇒ #f

Na and-proc je navázána procedura, nikoli speciální forma. Důsledkem toho je, jakým způsobem se vyhodnocují její argumenty:

(and-proc #f nenavazany-symbol #f) ;⇒ „CHYBA: Symbol nenavazany-symbol nemá vazbu“

Pro nás je důležitější ta skutečnost, že and-proc jako procedura může být použita třeba jako argument procedury apply:

(apply and-proc '(#t #t #t)) ;⇒ #t

K implementaci and-proc bychom také mohli chytře použít speciální formu and a proceduru eval. Máme-li seznam argumentů, můžeme na jeho začátek přidat symbol and a výsledný seznam explicitně vyhodnotit použitím eval.

str154

(define and-proc
  (lambda args
    (eval (cons 'and args))))

Analogicky můžeme vytvořit proceduru, která bude obdobou speciální formy or:

(define or-proc
  (lambda args
    (eval (cons 'or args))))
 
(and-proc 1 2 3 #f 10) ;⇒ #f
(and-proc (+ 1 2)) ;⇒ 3
(and-proc
  (if #f #t #t)) ;⇒ #t

Poznámka 6.4. Tato implementace ale není úplně korektní a bude pracovat správně jen do té doby, dokud výsledky vyhodnocení argumentů budou pravdivostní hodnoty, čísla nebo jineélementy, které se vyhodnocujísamy na sebe. Podívejme se na to na následujícím příkladě, kde dostáváme opačné hodnoty pro stejnýargument.

(and-proc '(if #f #t #f)) ;⇒ #f
(and '(if #f #t #f)) ;⇒ (if #f #t #f)

tedy hodnota považovaná za pravdu.

Speciální forma and nám vrací čtyřprvkový seznam (if #f #t #f). Ten vznikne vyhodnocením výrazu

'(if #f #t #f)

a je vrácen jako výsledek aplikace této formy, protože se jednaó poslední argument. Při aplikaci procedury and-proc dochází k nepříjemnému efektu, kterýnenína první pohled zřejmý. Protože se jedná o proceduru, jsou její argumenty implicitně vyhodnoceny. Do seznamu jejich vyhodnocení je přidán symbol and a pak je vyhodnocen použitím speciální formy eval. Při aplikaci formy and, jak je popsána v definici 2.22 na straně 66, se postupně vyhodnocují argumenty. Argumenty jsou tak vlastně vyhodnoceny dvakrát. Vyhodnocením seznamu (if #f #t #f) dostaneme #f. Odtud výsledná hodnota. S procedurou or-proc to samozřejmě bude podobné.

Pomocí procedur and-proc a or-proc můžeme konečně naprogramovat proceduru univerzálního kvantifikátoru forall a proceduru existenčního kvantifikátoru exists.

(define forall
  (lambda (f l)
    (apply and-proc (map f l))))
 
(define exists
  (lambda (f l)
    (apply or-proc (map f l))))

Procedura univerzálního kvantifikátoru forall tedy vrací pravdu, pokud predikát platí pro všechny prvky v seznamu:

(forall even? '(1 2 3 4 5)) ;⇒ #f
(forall even? '(2 4)) ;⇒ #t
(forall even? '(1 3 5)) ;⇒ #f
(forall even? '()) ;⇒ #t

Všimněte si posledního případu: každý prvek prázdného seznamu splňuje jakoukoliv vlastnost triviálně (souhlasís vlastnostmi všeobecného kvantifikátoru). Analogicky procedura existenčního kvantifikátoru exists vrací pravdu, pokud predikát platí alespoň pro jeden prvek v seznamu:

(exists even? '(1 2 3 4 5)) ;⇒ #t
(exists even? '(2 4)) ;⇒ #t
(exists even? '(1 3 5)) ;⇒ #f
(exists even? '()) ;⇒ #f

str155 Naše kvantifikátory můžeme rozšířit na procedury více argumentů. Podobně jako u procedury map pak vstupní predikát musí přijímat tolik argumentů, kolik je vstupních seznamů. Predikát je pak aplikován na prvky na stejných pozicích.

(define forall
  (lambda (f . lists)
    (apply and-proc (apply map f lists))))
 
(define exists
  (lambda (f . lists)
    (apply or-proc (apply map f lists))))

Všeobecný kvantifikátor forall pak zjišťuje, zda všechny prvky na stejných pozicích v seznamech splňují tento predikát.

(forall (lambda (x y) (<= x y)) '(10 20 30) '(11 22 33)) ;⇒ #t
(forall (lambda (x y) (<= x y)) '(10 23 30) '(11 22 33)) ;⇒ #f

V předchozí ukázce bychom přísně vzato nemuseli používat λ-výrazy, stačilo by pouze uvést:

(forall <= '(10 20 30) '(11 22 33)) ;⇒ #t
(forall <= '(10 23 30) '(11 22 33)) ;⇒ #f

A podobně existenční kvantifikátor exists pro více seznamů vrací pravdu #t, jestliže prvky na stejných pozicích splňují daný predikát.

(exists (lambda (x y) (> x y)) '(10 20 30) '(11 22 33)) ;⇒ #f
(exists (lambda (x y) (> x y)) '(10 23 30) '(11 22 33)) ;⇒ #t

Teď se budeme zabývat procedurou eval se dvěma argumenty. Jak již bylo řečeno, prvním argumentem je element k vyhodnocení, druhým argumentem je prostředí, ve kterém má k vyhodnocení dojít. Zde se vlastně dostáváme do zajímavého bodu, protože pokud chceme, abychom pomocí eval vyhodnocovali elementy relativně vzhledem k prostředí, pak musí být prostředí v jazyku Scheme elementem prvního řádu. Vskutku, prostředí jsou de facto tabulky obsahujícísymboly a jejich vazby plus ukazatele na svého předchůdce. Nic nám tedy nebrání abychom tyto „tabulky“ chápali jako elementy jazyka Scheme. Prostředí je pro nás tedy novýelement jazyka.

Proto, abychom mohli pracovat s prostředím jako s elementem, potřebujeme mít k dispozici nějaké primitivní procedury nebo speciální formy, které budou nějaká prostředí vracet. Nejprve budeme uvažovat speciální formu the-environment:

Definice 6.5 (speciální forma the-environment). Speciální forma the-environment se používá bez argumentu. Výsledkem její aplikace je prostředí, ve kterém byla aplikována (aktuální prostředí).

Před tím, než ukážeme příklad si uvědomme, proč je the-environment speciální forma a nikoliv procedura.

Při aplikaci procedur nehraje roli prostředí, ve kterém byly procedury aplikovány, protože používáme lexikální rozsah platnosti. Procedury ani nemají možnost zjistit, v jakém prostředí byly aplikovány. Naproti tomu speciální formy řídí vyhodnocování svých argumentů, musí mít tedy prostředísvé aplikace k dispozici. Speciální forma the-environment prostě udělá jen to, že toto prostředí vrátí jako výsledek. Viz příklady použití:

(the-environment) ;⇒ „globální prostředí“
((lambda (x)
   (the-environment))
 10) ;⇒ „lokální prostředí procedury, kde x → 10“
 
(let ((x 10))
  (the-environment)) ;⇒ „lokální prostředí procedury, kde x → 10“

str156 V druhém případě si všimněte, že procedura vzniklá vyhodnocením λ-výrazu ve svém těle provede pouze aplikaci the-environment. Při aplikaci této procedury je vytvořeno lokální prostředí, v němž je na x navázána hodnota 10 a toto prostředí je vráceno. V třetím případě se jednaó stejný případ, protože let-výraz je v podstatě jen zkrácením výrazu na druhém řádku.

Nyní již můžeme prové st vyhodnocení výrazu v aktuálním prostředí:

(let ((x 10))
  (eval '(+ x 1) (the-environment))) ;⇒ 11

Kdybychom v předchozím příkladu u eval neuvedli druhýargument, pak by byl výraz vyhodnocen v globálním prostředí a nastala by chyba. My jsme ale výraz vyhodnotili v aktuálním prostředí (v tele let-bloku), to jest v prostředí, kde je na x navázána hodnota.

Dále budeme v jazyku uvažovat proceduru environment-parent, která pro dané prostředí vrátí jeho předka.

V případě, že je environment-parent aplikována na globální prostředí, které předka nemá, pak vrátí #f.

Například použitím

(let* ((x 10)
       (y 20))
  (environment-parent (the-environment)))

bychom získali prostředí, ve kterém má vazbu symbol x, ale ve kterém nemá vazbu symbol y. Musíme si uvědomit, že speciální forma let* vytvářís každým symbolem nové prostředí a tato prostředí jsou do sebe zanořená, viz třetí lekci.

Procedura procedure-environment pro danou uživatelsky definovanou proceduru vrátí prostředí jejího vzniku. Například pomocí

(procedure-environment
    (let ((x 10))
          (lambda (y)
                  (+ x y))))

získáme prostředí vzniku procedury vzniklé vyhodnocením uvedeného λ-výrazu. To je prostředí vytvořené pomocí let, ve kterém je na symbol x navázána hodnota 10. Máme-li k dispozici procedure-environment, pak bychom již nutně nemuseli mít the-environment, protože kdekoliv v programu pomocí

(procedure-environment (lambda () #f))

můžeme získat aktuální prostředí. Samozřejmě, že toto řešení je méně efektivní, protože při něm vždy vytvoříme novou proceduru jen proto, abychom posléze získali prostředí jejího vzniku.

Poslední pomocnou procedurou, kterou představíme, je procedura environment→list, která pro dané prostředí vracíseznam tečkových párů ve tvaru ( symbol . vazba ) obsahující všechny vazby v daném prostředí. Pomocí této procedury tedy budeme schopni „srozumitelně vypisovat“ obsah prostředí. Samotná prostředí nemají žádnou čitelnou externí reprezentaci. Viz příklad použití právě popsané procedury:

(environment->list
  (procedure-environment
    (let ((x 10)
	  (z 20))
      (lambda (y)
	(+ x y))))) ;⇒ ((x . 10) (z . 20))
 
(environment->list
  ((lambda (x y)
     (the-environment))
   100 200)) ;⇒ ((x . 100) (y . 100))

Použitím předchozích procedur spolu s env můžeme provádět vyhodnocování elementů v aktuálním prostředí i v prostředích vzniku daných procedur. Například následující ukázka demonstruje vyhodnoceníseznamu v prostředí vzniku nějaké procedury.

str157

(eval '(* x x)
      (procedure-environment
	(let ((x 10))
	  (lambda (y) (+ x y))))) ;⇒ 100

Procedura vzniklá vyhodnocením (lambda (y) (+ x y)) není v předchozím příkladu vůbec aplikována.

Prostředí je v našem pojetí elementem prvního řádu. Na prostředí se taky můžeme dívat jako na speciální hierarchická data. Konstruktorem prostředí je aplikace uživatelsky definovaných procedur, protože při ní prostředí vznikají. Selektory prostředí jsou reprezentovány procedurami jako je environment-parent a podobně.

Pokud jsme o používání eval řekli, že je nebezpečné, pak bychom měli o používání eval s druhým argumentem (prostředím) říct, že je ještě mnohem víc nebezpečné a dát za to jeden velký tlustý vykřičník.

Pomocí eval totiž můžeme vyhodnocovat elementy při jejichž vyhodnocení dojde k vedlejšímu efektu, například ke změně vazby nebo překrytí vazby v nějakém prostředí. Od toho okamžiku mohou začít některé procedury vykazovat „zvláštníchování“. Demonstrujme si vše na následujícím větším příkladu.

Předpokládejme, že máme definovánu proceduru aux-proc následovně:

(define aux-proc
  (let ()
    (lambda (x)
      (+ x y))))

Procedura vznikla v prostředí, ve kterém nejsou žádné vazby, které vzniklo použitím let bez seznamu vazeb. Předkem tohoto prostředí je globální prostředí. Vyhodnocení následujícího výrazu pochopitelně končí chybou:

(aux-proc 10) ;⇒ „CHYBA: Symbol y nemá vazbu.“

Vyhodnocením následujícího výrazu:

(eval '(define y 20)
      (procedure-environment aux-proc))

došlo ke vzniku vedlejšího efektu, jímž byla definice nové vazby symbolu y. Výraz způsobující tuto definici jsme ale nevyhodnotili v globálním prostředí, nýbrž v prostředí vzniku procedury aux-proc. Takže v globálním prostředísymbol y zůstává i nadále bez vazby, ale aplikace aux-proc již proběhne bez chyby:

y ;⇒ „Symbol y nemá vazbu“
(aux-proc 10) ;⇒ 30

To co jsme teď provedli byl z programátorského hlediska „extrémně nečistý trik“ (slangově hack), kdy jsme lokálnímu prostředí procedury, které by za normálních podmínek nebylo z globálního prostředínijak dosažitelné, „vnutili“ novou vazbu symbolu. Přitom tato vazba nadále z venčínenína první pohled vidět, globální prostředí je nezměněno. Podíváme-li se nynína definici procedury aux-proc, nikde tam symbol y pochopitelně nevidíme. Externí pozorovatel, který by nevěděl o naší „černé magii“, by si myslel, že aplikace aux-proc bude končit chybou, stejně tak, jak to bylo v původním případě.

Při dalším předefinování y v prostředí vzniku procedury, by se aux-proc opět začala chovat jinak:

(eval '(define y 200)
      (procedure-environment aux-proc))
(aux-proc 10) ;⇒ 210

Pokud to nenínezbytně nutné, procedura eval by neměla být vůbec používána. Na druhou stranu, je-li její použitína místě a pokud může výrazně urychlit vývoj programu, pak jejímu použitínelze snad nic namítat. Proceduru bychom ale měli používat pokud možno tak, abychom vyhodnocováním výrazů co možnánejméně ovlivňovali činnost zbytku programu.

str158 Podotkněme, že procedura eval je popsána v definici R5RS jazyka Scheme, viz [R5RS]. V tomto reportu je popsána i verze eval se dvěma argumenty, ale pouze ve velmi omezené míře. Výše uvedená speciální forma the-environment a procedury procedure-environment, environment-parent a environment→list nejsou v R5RS vůbec zahrnuty. Některé široce používaneínterprety jazyka Scheme ale podobnými procedurami skutečně disponují, například interpret Elk. V poslední lekci v této části učebního textu do paradigmat programovánísi ukážeme implementaci skutečného interpretu jazyka Scheme, ve kterém budeme mít všechny tyto speciální formy a procedury k dispozici.

Poznámka 6.6. Ve funkcionálních programovacích jazycích je procedura eval, nebo nějaký její ekvivalent, obvykle k dispozici. Totéž se nedá říct o jiných programovacích jazycích. V procedurálních jazycích se procedury provádějící evaluaci vyskytují jen minimálně. V těchto vyšších programovacích jazycích také v podstatě neplatí, že program a data jsou totéž (teoreticky to možná platí, ale prakticky nikoliv). Možnosti vyhodnocování jsou někdy mylně přičítány jen interpretům programovacích jazyků. Protipříkladem mohou být jazyk Common LISP, který je kompilovaný (i interpretovaný) a ve kterém je eval přítomen (prostředízde ale není element prvního řádu).

Na závěr této sekce uvedeme několik příkladů použití procedury apply a speciální formy eval a odvozených procedur. Prvním z nich je přibližná rovnost vektorů. Vektory jsou representovány číselnými seznamy v1 a v2. Argument delta je pak tolerance, ve které se může pohybovat rozdíl jednotlivých složek, aby ještě vektory byly uznány za rovné. To pomáhá předejít problémům se zaokrouhlovacími chybami, které vznikají při manipulaci s neexaktními čísly. Například na některých platformách může nastat situace, kde

(= (- 1.2 1) 0.2) ;⇒ #f

Proceduru vec-equal? bychom mohli naimplementovat například takto:

(define vec-equal?
  (lambda (v1 v2 delta)
    (forall (lambda (x y)
	      (< (abs (- x y)) delta))
	    v1 v2)))

Teď uvádíme aplikace:

(vec-equal? '(0 1 3) '(0 1.2 3) 0.1) ;⇒ #f
(vec-equal? '(0 1 3) '(0 1.2 3.001) 0.3) ;⇒ #t

Asociativní pole

Asociativní pole je datová struktura, kteráse skládá z kolekce tak zvaných klíčů a kolekce hodnot. Každý klíč je přiřazen jedné hodnotě. Základní operace na této datové struktuře jsou:

  • přiřazení hodnoty nějakému klíči (respektive změna stávajícího přiřazení),
  • vyhledání hodnoty podle klíče
  • a zrušení stávajícího přiřazení.

My budeme asociativní pole reprezentovat seznamem přiřazení. Přiřazením přitom budeme rozumět pár, jehož první prvek je klíč a druhý prvek je přiřazená hodnota. Budeme implementovat první dvě zmíněné základní operace. Teď tedy přidání prvku do asociativního pole:

(define cons-assoc
  (lambda (key val assoc)
    (let ((cell (cons key val)))
      (if (exists (lambda (x) (equal? (car x) key))
		  assoc)
	(map (lambda (x)
	       (if (equal? (car x) key)
		 cell
		 x))
	     assoc)
	(cons cell assoc)))))

str159 Nejdříve jsme zjistili použitím procedury kvantifikátoru exists, jestli je k zadanému klíči key přiřazena hodnota. Jestliže ne, přidáme pár reprezentující přiřazení hodnoty ke klíči do asociativního pole pomocí procedury cons. Pokud ale přiřazení k takovému klíči již v poli je, použijeme proceduru map, abychom nahradili původní přiřazení novým.

Druhou základní operací je selekce. Použitím procedury filter vybereme ty prvky seznamu reprezentující asociativní pole, které mají shodný klíč s požadovaným klíčem. Pokud výsledný je výsledný seznam prázdný, nebylo přiřazení nalezeno. V opačném případě vracíme hodnotu z tohoto přiřazení.

(define assoc-key
  (lambda (assoc key)
    (let ((found (filter (lambda (x)
                           (equal? (car x) key))
                         assoc)))
      (if (null? found)
        #f
        (cdar found)))))

Další příklad se týká opět datových tabulek. Je vlastně vylepšení reprezentace datových tabulek, kterou jsme zavedli v sekci 5.8, tak, aby každá tabulka měla „hlavičku“, ve které jsou jména atributů, které budeme používat při selekci a projekci. Toto je příklad takové tabulky:

(define mesta
  '((jmeno p-obyvatel p-nadrazi velikost)
    (Olomouc 120 3 stredni)
    (Prostejov 45 2 male)
    (Prerov 50 3 male)
    (Praha 1200 8 velke)))

Procedura selekce bude brát jako argumenty tabulku a výraz reprezentující podmínku. V tomto výrazu používáme jména z hlavičky tabulku. Příklad použití může být třeba tento:

(selection mesta
	   '(and (>= p-obyvatel 50)
		 (not (equal? velikost 'male))))

Nejdůležitější rys použitý v této procedure je vytvoření λ-výrazu vyhodnocením výrazu

(list 'lambda head condition)

a jeho následné vyhodnocení procedurou eval. Tato procedura a tělo tabulky – to jest tabulka bez hlavičky – pak budou vstupními argumenty pro proceduru filter, která pak provede vyfiltrování požadovaných řádků.

(define selection
  (lambda (table condition)
    (let* ((head (car table))
	   (body (cdr table))
	   (property (eval (list 'lambda head condition))))
      (filter (lambda (x)
		(apply property x))
	      body))))

Toto naše řešení má ale mouchu. A to právě v použití procedury eval. Jde o to, že tato procedura, je-li použita s jedním argumentem, vyhodnocuje tento svůj argument v globálním prostředí. A z toho důvodu nebude fungovat následující kód, kde se ve výrazu, který reprezentuje podmínku odvoláváme na lokálně vázaný symbol.

(let ((x 50))
  (selection mesta
	     '(and (>= p-obyvatel x)
		   (not (equal? velikost 'male))))) ;⇒ „CHYBA: Symbol x nemá vazbu.“

str160 Tento problém bychom samozřejmě mohli vyřešit použitím procedury eval se dvěma argumenty. Druhým argumentem bude aktuální prostředí, to musíme předat jako další argument při spuštění selekce:

(define selection
  (lambda (table env condition)
    (let* ((head (car table))
	   (body (cdr table))
	   (property (eval (list 'lambda head condition) env)))
      (filter (lambda (x)
		(apply property x))
	      body))))

Viz příklad použití:

(let ((x 50))
  (selection mesta
	     (the-environment)
	     '(and (>= p-obyvatel x)
		   (not (equal? velikost 'male)))))

V jednom z dalších dílů textu si ukážeme mnohem elegantnější řešení tohoto problému.

s6_5

6.5 Reprezentace množin a relací pomocíseznamů

V této sekci ukážeme reprezentaci konečných množin a relací pomocíseznamů, a procedur pro manipulaci s nimi. Na nich demonstrujeme použití procedur apply, eval a procedur implementovaných v této sekci.

Také na nich ukážeme filtraci a vytváření procedur s nepovinnými argumenty a s libovolným počtem argumentů.

Za množinu budeme považovat seznam bez duplicit. V tomto seznamu pro nás bude důležitý pouze výčet prvků, nikoli jejich pořadí. Prázdná množina je reprezentovaná prázdným seznamem:

(define the-empty-set '())

Počet prvků množiny (kardinalita) se bude shodovat s délkou seznamu:

(define card
  (lambda (set)
    (length set)))

Procedura make-set vytváří množinu výběrem těch prvků z množiny universe , které mají vlastnost prop? . Jedna se o jednoduché použití procedury filter:

(define make-set
  (lambda (prop? universe)
    (filter prop? universe)))

Přidání prvku do množiny. Potřebujeme nejdříve zkontrolovat, jestli přidávaný prvek už v množině není.

V případě, že ne, přidáme prvek. Jinak je výsledkem původní množina. Tak se zabrání možnému vzniku duplicit.

(define cons-set
  (lambda (x set)
    (if (in? x set)
      set
      (cons x set))))

V proceduře tedy potřebujeme predikát in?, který by rozhodoval, zda je danýelement prvkem v seznamu.

To zjistíme tak, že vyfiltrujeme prvky, které jsou rovny (při porovnání pomocí equal?), a otestujeme, jestli je výsledný seznam neprázdný.

str161

(define in?
  (lambda (x set)
    (not (null? (filter (lambda (y) (equal? x y)) set)))))

Též bychom mohli použít proceduru exists a s její pomocízjišťovat, zda je alespoň jeden prvek množiny roven danému elementu. Kód by pak vypadal následně:

(define in?
  (lambda (x set)
    (exists (lambda (p) (equal? x p)) set)))

Další procedura set? bude testovat, jestli je její argument množina. Tedy ověří, že se jednaó seznam a pak pro každý prvek tohoto seznamu zjistíme, jestli je počet jeho výskytů roven jedné. Ke zjištění počtu výskytů je využita procedura occurrences, kterou napíšeme vzápětí.

(define set?
  (lambda (elem)
    (and (list? elem)
	 (forall (lambda (x)
		   (= (occurrences x elem) 1))
		 elem))))

Teď tedy k pomocné proceduře occurrences, kteráse používáse dvěma argumenty – elementem elem a seznamem l . Tato procedura vrací počet výskytů prvku elem v seznamu l . Můžeme ji realizovat například tak, že vyfiltrujeme ze seznamu l všechny prvky, které jsou shodné s elementem elem . Kód takové implementace by vypadal takto:

(define occurrences
  (lambda (elem l)
    (length (filter (lambda (x) (equal? x elem)) l))))

Jinou možností je vytvořit aplikací procedurou map zaměnit prvky shodné s elementem elem za jedničky a ostatníza nuly. Na takto vzniklý seznam pak aplikujeme proceduru sčítáníčísel. Než se začneme zabývat množinovými operacemi, vytvoříme si dvě pomocné procedury map-index a map-tail. Jednáse o obdoby procedury map (pro jeden seznam). Procedura map-index předává vstupní proceduře nejen prvky zadaného seznamu, ale také jejich indexy. Mapovaná procedura tedy bude přijímat dva argumenty – prvním z nich bude prvek z původního seznamu, druhým index tohoto prvku.

(define map-index
  (lambda (f l)
    (let ((indices (build-list (length l) (lambda (i) i))))
      (map f l indices))))

Procedura map-index je naprogramována tak, že vytvoříseznam indexů pomocí build-list, podobně jako v programu 6.4, to jest jako v implementaci procedury list-ref. Poté namapujeme předanou proceduru na původní seznam a seznam indexů. Viz příklady použití:

(map-index cons '(a b c d)) ;⇒ ((a . 0) (b . 1) (c . 2) (d . 3))
(map-index (lambda (x y) x) '(a b c d)) ;⇒ (a b c d)
(map-index (lambda (x y) y) '(a b c d)) ;⇒ (0 1 2 3)

Mapovací procedura map-tail bude předávat mapované proceduře místo jednotlivých prvků podseznamy.

Místo prvního prvku, bude předán celý seznam, namísto druhého seznam bez prvního prvku, a tak dále.

Až konečně namísto posledního prvku seznamu bude předán jednoprvkový seznam obsahující poslední prvek.

Tyto podseznamy budeme získávat pomocí procedury list-tail. Ta se používáse dvěma argumenty – prvním je seznam, a druhým číslo i . str162 Výsledkem aplikace je pak seznam bez prvních i prvků. Viz příklady požití:

(list-tail '(1 2 3 4 5) 1) ;⇒ (2 3 4 5)
(list-tail '(1 2 3 4 5) 3) ;⇒ (4 5)
(list-tail '(1 2 3 4 5) 5) ;⇒ ()
(list-tail '(1 2 3 4 5) 7) ;⇒ „CHYBA: Seznam má příliš malý počet prvků.“

Pomocí této procedury a map-index je implementace procedury map-tail velmi přímočará:

(define map-tail
  (lambda (f l)
    (map-index (lambda (x i)
		 (f (list-tail l i)))
	       l)))

Viz příklad použití procedury:

(map-tail (lambda (x) x) '(a b c d)) ;⇒ ((a b c d) (b c d) (c d) (d))

Nyní uděláme proceduru list→set, která bude konvertovat seznam na množinu. Tento seznam bude jejím jediným argumentem a procedura z něj odstraní duplicitní prvky.

(define list->set
  (lambda (l)
    (apply append
	   (map-tail (lambda (x)
		       (let ((head (car x))
			     (tail (cdr x)))
			 (if (in? head tail)
			   '()
			   (list head))))
		     l))))

Nyníse zaměříme na operace s množinami – na sjednocení množin (union), průnik množin (intersect) a množinový rozdíl. Implementace procedury pro sjednocení množin je velice jednoduchá. Množiny, tedy seznamy, spojíme aplikací procedury append. V takto vzniklém seznamu se ale mohou vyskytovat duplicitní prvky – ty odstraníme použitím list→set.

(define union
  (lambda (set-A set-B)
    (list->set (append set-A set-B))))

Průnik množin intersect bude pro nás aplikací make-set. Universem bude sjednocení množin vytvořené pomocí procedury union, požadovanou vlastností pak bude přítomnost prvku (zjištěná predikátem in?) v obou množinách:

(define intersect
  (lambda (set-A set-B)
    (make-set (lambda (x)
		(and (in? x set-A)
		     (in? x set-B)))
	      (union set-A set-B))))

Tyto dvě uvedené množinové operace můžeme sjednotit do procedury vyššího řádu set-operation:

(define set-operation
  (lambda (prop)
    (lambda (set-A set-B)
      (filter (lambda (x) (prop x set-A set-B))
	      (list->set (append set-A set-B))))))

str163 Pomocí set-operation můžeme definovat operace sjednocení a průniku množin.

(define union (set-operation (lambda (x A B) (or (in? x A) (in? x B)))))
(define intersect (set-operation (lambda (x A B) (and (in? x A) (in? x B)))))
 
;Nebo třeba operaci množinového rozdílu:
(define minus (set-operation (lambda (x A B) (and (in? x A) (not (in? x B))))))
(union '(10 20 30) '(20 30 40)) ;⇒ (10 20 30 40)
(intersect '(10 20 30) '(20 30 40)) ;⇒ (20 30)
(minus '(10 20 30) '(20 30 40)) ;⇒ (10)

Dále předchozí reprezentace množin použijeme k reprezentaci binárních relacína množinách. Připomeňme, že binární relace na množině je podmnožinou druhé kartézské mocniny této množiny. Kartézská mocnina množiny A je množina uspořádaných dvojic a, b takových, že první prvek a i druhý prvek b patří do množiny A. My budeme uspořádanou dvojici reprezentovat tečkovým párem (což se přímo nabízí). Vytvoříme si proto separátní konstruktory a selektory pro uspořádanou dvojici:

(define make-tuple cons)
(define 1st car)
(define 2nd cdr)

Procedura cartesian-square bude pro množinu vracet její druhou kartézskou mocninu.

(define cartesian-square
  (lambda (set)
    (apply append
	   (map (lambda (x)
		  (map (lambda (y)
			 (make-tuple x y))
		       set))
		set))))

Výraz (map (lambda (y) (make-tuple x y)) set) vytvoříi seznam všech dvojic, jejichž prvním prvkem je hodnota navázanána symbol x a durhým prvkem je prvek z množiny set. Vnějším použitím procedury map

(map (lambda (x)
       (map (lambda (y)
	      (make-tuple x y))
	    set))
     set)

dostáváme seznam obsahující pro každé x z množiny set seznam všech párů kódujících uspořádané dvojice x, y , kde y patří do množiny set. A tyto seznamy spojíme použitím procedury append.

Nyní můžeme přikročit k definici konstruktoru relace. Procedura make-relation bude procedurou dvou argumentů; prvním z nich bude vlastnost reprezentovaná predikátem dvou argumentů a druhým množina nad kterou bude relace definovaná.

(define make-relation
  (lambda (prop? universe)
    (filter (lambda (x)
	      (prop? (1st x) (2st x)))
	    (cartesian-square universe))))

Vytvořili jsme tedy druhou kartézskou mocniny množiny universe a z ní jsme aplikaci procedury filter vybrali ty dvojice, které splňují vlastnost prop?. str164 Následují příklady použití tohoto konstruktoru.

(define u '(0 1 2 3 4 5))
(make-relation (lambda (x y) #f) u) ;⇒ ()
(make-relation (lambda (x y) (= x y)) u) ;⇒ ((0 . 0) (1 . 1) (2 . 2) (3 . 3) (4 . 4) (5 . 5))
(make-relation (lambda (x y) (= (+ x 1) y)) u) ;⇒ ((0 . 1) (1 . 2) (2 . 3) (3 . 4) (4 . 5))
(make-relation (lambda (x y) (= (modulo (+ x 1) (length u)) y)) u) ;⇒ ((0 . 1) (1 . 2) (2 . 3) (3 . 4) (4 . 5) (5 . 0))
(make-relation (lambda (x y) (< x y)) u) ;⇒ ((0 . 1) (0 . 2) (0 . 3) (0 . 4) (0 . 5) (1 . 2) (1 . 3) (1 . 4) (1 . 5) (2 . 3) (2 . 4) (2 . 5) (3 . 4) (3 . 5) (4 . 5))

Protože relace jsou speciální množiny, můžeme na ně aplikovat procedury, které jsme výše vytvářeli pro množiny bez jakýchkoli změn:

(define r1 (make-relation (lambda (x y) (= (modulo (+ x 1) (length u)) y)) u))
(define r2 (make-relation (lambda (x y) (< x y)) u))
 
(union r1 r2) ;⇒ ((5 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4) (0 . 5) (1 . 2) (1 . 3) (1 . 4) (1 . 5) (2 . 3) (2 . 4) (2 . 5) (3 . 4) (3 . 5) (4 . 5))
(intersect r1 r2) ;⇒ ((0 . 1) (1 . 2) (2 . 3) (3 . 4) (4 . 5))
(minus r1 r2) ;⇒ ((5 . 0))
(minus r2 r1) ;⇒ ((0 . 2) (0 . 3) (0 . 4) (0 . 5) (1 . 3) (1 . 4) (1 . 5) (2 . 4) (2 . 5) (3 . 5))

Níže budeme potřebovat proceduru, která pro libovolné dvě relace vrátí jejich nejmenšíspolečneúniverzum. Použitím procedury map pro každou z těch dvou relací vytvoříme seznam všech prvků vyskytujících se v prvních prvcích dvojic a seznam všech prvků vyskytujících se v druhých prvcích dvojic. A tyto čtyři seznamy spojíme aplikací procedury append. Z výsledného seznamu pak vytvoříme množinu pomocí procedury list→set:

(define get-universe
  (lambda (rel-R rel-S)
    (list->set (append (map 1st rel-R) (map 2st rel-R)
		       (map 1st rel-S) (map 2nd rel-S)))))

Tuto proceduru můžeme zobecnit na proceduru libovolného počtu argumentů. get-universe tak bude vracet nejmenšíspolečneúniverzum pro jakýkoli počet relací. Procedura, která vznikne vyhodnocením λ-výrazu

(lambda (x) (append (map 1st x) (map 2nd x)))

vracíseznam prvků vyskytujících se v prvních prvcích dvojic v relaci, na kterou je aplikována. Tuto proceduru mapujeme na seznam relací relations. Na seznam seznamů, který bude výsledkem tohoto mapování, aplikujeme proceduru append a vytvoříme tak jeden seznam. Z toho vytvoříme množinu procedurou list→set, viz následující kód:

(define get-universe
  (lambda relations
    (list->set (apply append
		      (map (lambda (x)
			     (append (map 1st x) (map 2nd x)))
			   relations)))))

Zde uvádíme aplikace procedury get-universe na různý počet relací:

(get-universe) ;⇒ ()
(get-universe '()) ;⇒ ()
(get-universe '() '() '()) ;⇒ ()
(get-universe '() '((a . b)) '()) ;⇒ (a b)
(get-universe '((10 . 20) (20 . 30)) '((a . b)) '()) ;⇒ (10 20 30 a b)

str165 K relaci R můžeme uvažovat inverzní relaci R−1, to jest relaci { b, a | a, b ∈ R}. Vytvoříme proceduru invert-relation, která k dané relaci vrací inverzní relaci:

(define invert-relation
  (lambda (rel-R)
    (map (lambda (x)
	   (make-tuple (2nd x) (1st x)))
	 rel-R)))

Použitím procedury map jsme na každý prvek seznamu, který reprezentuje relaci aplikovali proceduru, která převrací pořadí prvků v uspořádané dvojici. Následuje ukázka použití procedury invert-relation.

(invert-relation '()) ;⇒ ()
(invert-relation r1) ;⇒ ((1 . 0) (2 . 1) (3 . 2) (4 . 3) (5 . 4) (0 . 5))

Relace lze také skládat. Máme-li binární relace R a S na množině M , jejich složením rozumíme takovou binární relaci R ◦ S na množině M , že platí x, y ∈ R ◦ S, právě když existuje prvek z ∈ M tak, že máme: x, z ∈ R a z, y ∈ S. Procedura compose-relations bere dva argumenty, kterými jsou relace, a vrací relaci jejich složení.

(define compose-relations
  (lambda (rel-R rel-S)
    (let ((universe (get-universe rel-R rel-S)))
      (make-relation
	(lambda (x y)
	  (exists (lambda (z)
		    (and (in? (make-tuple x z) rel-R)
			 (in? (make-tuple z y) rel-R)))
		  universe))
	universe))))

Implementace této procedury je vlastně přímým přepisem uvedeného předpisu. Nejdříve jsme pomocí procedury get-universe získali univerzum M a nad tímto univerzem jsme vytvořili relaci aplikací procedury make-relation. Vstupním argumentem této procedury byl mimo univerza predikát realizující vlastnost „existuje z ∈ M : x, z ∈ R a z, y ∈ S“. V něm jsme použili proceduru existenčního kvantifikátoru exists a predikát in?. Nyní tedy ukážeme aplikaci této procedury:

(compose-relations r1 r2) ;⇒ ((0 . 2) (1 . 3) (2 . 4) (3 . 5) (4 . 0) (5 . 1))
(compose-relations r2 r1) ;⇒ ((1 . 3) (1 . 4) (1 . 5) (2 . 4) (2 . 5) (3 . 5) (0 . 2) (0 . 3) (0 . 4) (0 . 5))

O binární relaci R na množině M říkáme, že je reflexivní, pokud pro každé x ∈ M platí x, x ∈ R. Predikát reflexive?, ktery źjišťuje zda je relace reflexivní bychom mohli napsat například tak, jak je uvedeno níže.

Opětně jde o přímý přepis předpisu.

(define reflexive?
  (lambda (rel-R)
    (forall (lambda (x)
	      (in? (make-tuple x x) rel-R))
	    (get-universe rel-R))))

A zde uvádíme aplikace:

(reflexive? (make-relation (lambda (x y) #f) u)) ;⇒ #t
(reflexive? (make-relation (lambda (x y) (= x y)) u)) ;⇒ #t
(reflexive? (make-relation (lambda (x y) (= (+ x 1) y)) u)) ;⇒ #f
(reflexive? (make-relation (lambda (x y) (= (modulo x 2) (modulo y 2))) u)) ;⇒ #t
(reflexive? (make-relation (lambda (x y) (< x y)) u)) ;⇒ #f

str166 Binární relace R na množině M je symetrická, pokud pro všechna x, y ∈ M platí, že pokud x, y ∈ R, pak y, x ∈ R:

(define symmetric?
  (lambda (rel-R)
    (let ((universe (get-universe rel-R)))
      (forall (lambda (x)
		(forall (lambda (y)
			  (if (in? (cons x y) rel-R)
			    (in? (cons y x) rel-R)
			    #t))
			universe))
	      universe))))

Zase šlo o přímý přepis uvedené definice. Zde uvádíme použití:

(symmetric? (make-relation (lambda (x y) #f) u)) ;⇒ #t
(symmetric? (make-relation (lambda (x y) (= x y)) u)) ;⇒ #t
(symmetric? (make-relation (lambda (x y) (= (+ x 1) y)) u)) ;⇒ #f
(symmetric? (make-relation (lambda (x y) (= (modulo x 2) (modulo y 2))) u)) ;⇒ #t
(symmetric? (make-relation (lambda (x y) (< x y)) u)) ;⇒ #f

Poslední vlastností relací jíž se budeme zabývat je tranzitivita. Binární relace R na množině M je tranzitivní, pokud pro všechna x, y, z ∈ M platí, že pokud x, y ∈ R a y, z ∈ R, pak x, z ∈ R:

(define transitive?
  (lambda (rel-R)
    (let ((universe (get-universe rel-R)))
      (forall (lambda (x)
		(forall (lambda (y)
			  (forall (lambda (z)
				    (if (and (in? (cons x y) rel-R)
					     (in? (cons y z) rel-R))
				      (in? (cons x z) rel-R)
				      #t))
				  universe))
			universe))
	      universe))))

Použití:

(transitive? (make-relation (lambda (x y) #f) u)) ;⇒ #t
(transitive? (make-relation (lambda (x y) (= x y)) u)) ;⇒ #t
(transitive? (make-relation (lambda (x y) (= (+ x 1) y)) u)) ;⇒ #f
(transitive? (make-relation (lambda (x y) (= (modulo x 2) (modulo y 2))) u)) ;⇒ #t
(transitive? (make-relation (lambda (x y) (< x y)) u)) ;⇒ #t

Shrnutí

Zabývali jsme se explicitní aplikací procedur a vyhodnocováním elementů. Představili jsme proceduru apply pomocíniž je možné aplikovat procedury s danými argumenty. Explicitní aplikaci procedur lze použít k agregaci více elementů do jednoho výsledku pomocí aplikace procedury. Ukázali jsme, jak lze s pomocí apply naprogramovat některéčasto používané procedury. Typickou úlohou, kterou lze vyřešit pomocí apply je filtrace prvků seznamu. V dalšíčásti jsme se zabývali problematikou vytváření uživatelsky definovatelných procedur s nepovinnými a s libovolnými argumenty. Provedli jsme rozšířeni λ-výrazů, které již si ponecháme (rozšíření bylo definitivní). Dále jsme ukázali proceduru eval a dalšísadu speciálních forem a procedur pro manipulaci s prostředím. Uvedli jsme, že prostředí lze bez újmy chápat jako element jazyka Scheme, dokonce jako element prvního řádu. Upozornili jsme na uśkalí při používání eval souvisejícíse vznikem těžko odhalitelných chyb v programech. Nakonec jsme ukázali reprezentaci množin a relací pomocí seznamů, na které jsme demonstrovali použití procedur apply a eval. str167

Pojmy k zapamatování

  • implicitní aplikace procedury, explicitní aplikace procedury,
  • implicitní vyhodnocení elementů, explicitní vyhodnocení elementů,
  • filtrace,
  • nepovinné argumenty, libovolné argumenty,
  • prostředí jako element prvního řádu.

Nově představené prvky jazyka Scheme

  • speciální forma the-environment,
  • procedury apply, eval, environment-parent, procedure-environment, environment→list Kontrolní otázky

1. Jaký je rozdíl mezi implicitní a explicitní aplikací procedury?

2. Jaké argumenty může mít procedura apply a jaký mají význam?

3. V kterých případech je nutné použít apply?

4. Jak se zapisují formální argumenty procedur s nepovinnými argumenty?

5. Jak se zapisují formální argumenty procedur s libovolnými argumenty?

6. Jaké omezení platí při použitínepovinných argumentů?

7. Jakéznáte speciální formy a procedury pro práci s prostředím?

8. Jak se provádí explicitní vyhodnocování elementů?

Cvičení

1. Naprogramujte proceduru na zpracovaníseznamu podle vzoru. Vzorem se myslíseznam o stejném počtu prvků, kteryóbsahuje:

  • symbol del, pak je prvek na odpovídající pozici smazán
  • symbol ins, pak je prvek na odpovídající pozici ponechán
  • procedury, pak je prvek seznamu na odpovídající pozici nahrazen aplikací této procedury na tento prvek.

Viz příklad volání:

(format '(1 2 3 4 5) (list 'del even? even? 'ins (lambda (x) (+ x 1)))) ;⇒ (#t #f 4 5)

2. Naprogramujte proceduru vracejícíseznam mocnin čísla k (od 0-té až po (n − 1)-té).

3. Naprogramujte proceduru konverze binary→decimal, které binární číslo, reprezentované číselným seznamem obsahujícím 0 a 1, převede na číslo (Scheme-ovské).

4. Implementujte pro reprezentaci množin uvedenou v sekci 6.5:

  • operaci symetrického rozdílu
  • predikát rovnosti množin
  • predikát zjišťující, zda je zadaný seznam množinou

str168 Úkoly k textu

1. Naprogramujte relace reprezentované páry univerzum . vlastnost . Kde univerzum seznam, a vlastnost je predikát představující funkci příslušnosti.

2. Implementujte reprezentace zobrazení jako speciálních relací.

3. Naprogramujte predikáty antisymetric?, ireflexive? a complete? pro zjištění antisymetrie, ireflexivity a úplnosti relace.

Relace R je

  • antisymetrická, pokud pro každé x a y platí, že pokud (x, y) ∈ R a (y, x) ∈ R, pak x = y.
  • ireflexivní, pokud pro každé x platí (x, x) ∈ R
  • úplná, pokud pro každé x a y platí, (x, y) ∈ R nebo (y, x) ∈ R.

Řešení ke cvičením

1.

(define format
  (lambda (l pattern)
    (apply append
	   (map (lambda (atom pat)
		  (cond ((equal? pat 'del) '())
			((equal? pat 'ins) (list atom))
			((procedure? pat) (list (pat atom)))
			(else #f)))
		l pattern))))
(format '(1 2 3 4 5) (list 'del even? even? 'ins (lambda (x) (+ x 1))))

2.

(define (power-list k n)
  (apply map *
	 (map
	   (lambda (r)
	     (build-list n (lambda (i)
			     (if (<= i r)
			       1
			       k))))
	   (build-list n (lambda (i) i)))))

3.

(define (binary->decimal bin)
  (apply + (map * (reverse bin) (power-list 2 (length bin)))))

4.

(define sminus
  (set-operation
    (lambda (x A B)
      (or (and (in? x A) (not (in? x B)))
	  (and (in? x B) (not (in? x A)))))))
 
(define sminus
  (lambda (set-A set-B)
    (union (minus set-A set-B)
	   (minus set-B set-A))))
  (define set-equal?
    (lambda (set-A set-B)
      (null? (sminus set-A set-B))))

str169

(define set?
  (lambda (elem)
    (apply and-proc
	   (map-tail (lambda (x)
		       (not (in? (car x) (cdr x))))
		     elem))))
 
(define set?
  (lambda (elem)
    (equal? (list->set elem) elem)))
2014/04/24 16:04

Cvičení 7

1. V sekci 7.3 jsme rozšířili proceduru min2 na proceduru libovolného počtu argumentů. Stejným způsobem rozšiřte proceduru na výběr čísla s extrémní absolutní hodnotou abs-min.

2. Napište predikát, který pro posloupnost zjistí, zda je neklesající. Posloupnost bude reprezentovaná seznamem, jehož prvky jsou čísla. Viz příklady aplikace:

(nondecreasing? '()) ;⇒ #t
(nondecreasing? '(1 2 3 4)) ;⇒ #t
(nondecreasing? '(1 2 4 3)) ;⇒ #f
(nondecreasing? '(1 4 2 3)) ;⇒ #f
(nondecreasing? '(4 1 2 3)) ;⇒ #f

3. Napište procedury after a before, jejichž argumenty budou element elem a seznam l . Procedura after bude vracet seznam prvku za posledním výskytem prvku elem (včetně) v seznamu l. Procedura before zase seznam prvků před prvním výskytem prvku elem (včetně) v seznamu l. Viz příklady použití:

(after 10 '(1 2 3 4 3 5 6)) ;⇒ ()
(after 3 '(1 2 3 4 3 5 6)) ;⇒ (3 5 6)
(after 6 '(1 2 3 4 3 5 6)) ;⇒ (6)
(before 10 '(1 2 3 4 3 5 6)) ;⇒ (1 2 3 4 5 6)
(before 1 '(1 2 3 4 3 5 6)) ;⇒ (1)
(before 3 '(1 2 3 4 3 5 6)) ;⇒ (1 2 3)

Řešení ke cvičením 1.

(define abs-min2
  (lambda (x y)
    (if (<= (abs x) (abs y)) x y)))
 
(define abs-min
  (lambda args
    (foldr abs-min2 (car args) (cdr args))))

2.

(define nondecreasing?
  (lambda (l)
    (foldr (lambda (x y)
             (if y
               (if (or (equal? y #t) (<= x y))
                 x
                 #f)
               #f))
           #t
           l)))

3.

(define conseq
  (lambda (elem x y)
    (if (car y)
      y
      (cons (equal? x elem)
            (cons x (cdr y))))))
 
(define after
  (lambda (elem l)
    (let ((found (foldr (lambda (x y) (conseq elem x y))
                        '(#f . ())cl
                        l)))
      (if (car found)
        (cdr found)
        #f))))

str189

(define before
  (lambda (elem l)
    (let ((found (foldl (lambda (x y) (conseq elem x y))
                        '(#f . ())
                        l)))
      (if (car found)
        (reverse (cdr found))
        #f))))

str190

2014/04/24 16:04

Cvičení 8

1. Naprogramujte proceduru perrin jednoho argumentu n , která vracín -týčlen Pn Perinovy posloupnosti. Perinova posloupnost je definována následujícím předpisem:

 3

pokud n = 0,

 0

pokud n = 1,

Pn =

2

pokud n = 2,

 Pn−2 + Pn−3

jinak.

Proceduru implementujte

(a) jako rekurzivní proceduru

(b) jako iterativní proceduru

© pomocí pojmenovaného let

2. Napište rekurzivní proceduru vracející aritmetický průměr čísel v seznamu.

3. Napište rekurzivní verzi procedury list-indices, kterou jsme definovali v programu 6.5.

4. Implementujte Euklidův algoritmus na výpočet největšího společného dělitele.

5. Naprogramuje proceduru reverse pomocí pojmenovaného let.

6. Doplňte sadu procedur pro práci s polynomy ze sekce 8.6 o:

(a) predikát poly?, který zjišťuje, zda je jeho argument reprezentací seznamu (b) konstruktor poly-roots libovolného počtu argumentů vytvářející polynom podle výčtu všech jeho kořenů.

© proceduru poly-gcd, která počítá největší společný dělitel dvou polynomů, a která bude implementaci Euklidova algoritmu na polygomech.

2014/03/14 22:19

Cvičení 9

1. pomocí y-kombinátoru naprogramujte následující procedury:

  • proceduru pro výpočet n-tého Fibonacciho čísla fib
  • mapování procedury přes jeden seznam map1
  • linearizace seznamu linearize

2. Implementujte následující procedury bez použití procedury depth-accum:

  • depth-filter – hloubková filtrace na seznamu
  • depth-map – hloubkové mapování procedury přes seznam
  • atom? – predikát zjišt’ující, jestli je element atomem seznamu

3. Implementujte procedury z předchozího úkolu pomocí první verze depth-accum.

4. Implementujte procedury z předchozího úkolu pomocí druhé verze depth-accum.

2014/03/14 22:19

Cvičení 11

1. Bez použití interpretru určete výsledky vyhodnocenıńásledujících výrazů:

(quasiquote symbol)

;=

`(symbol)

;=

(car ``symbol)

;=

`(+ 1)
 
`(,+ 1 2)
 
`(1 ,1)
 
`(1 ,,1)
 
`(,+ . ,-)
 
`(1 + 2 ,@3)
 
(quote (,@()))
 
(quasiquote quasiquote)
 
(quasiquote (+ 1 (unquote +)))
 
(quasiquote (1 2 ,(+ 1 2)))
 
`,(+ 1 2)
 
`,`,(+ 1 2)
 
`(1 2 ,@(build-list 5 (lambda (x) (* x x))) 3)
 
(quasiquote (1 2 (unquote-splicing (map list '(1 2 3))) 5))
 
unquote-splicing
 
```()
 
`'+
 
(quote unquote)

2. Upravte kód procedury diff v programu 11.6 tak, aby bylo možné derivovat výrazy, ve kterých je součet a součin použit na libovolné množství argumentů.

2014/03/14 22:11

Cvičení 12

1. Bez použití interpretu jazyka Scheme zjistěte, jak se vyhodnotí následující výrazy používající generické + tak, jak jsme jej představili v sekci 12.1:

(+ 2/3 "." 0.5) ;⇒
 
(+ (- 1) "x" (- 2)) ;⇒
 
(+ 1 2 "+" 3 4) ;⇒
 
(+ 2 (+ 2 "3") 10) ;⇒
 
(+ 2 (log (exp 2))) ;⇒
 
(apply + '("a" "b" (+ 1 2) 2)) ;⇒
 
(apply + (map number->string '(1 2 3))) ;⇒

2. Obohaťte vytvořenýinterpret jazyka Scheme o primitivní proceduru foldr. To jest foldr by měla být ve vytvořeném interpretu k dispozici přímo v počátečním prostředí a mělo by se jednat o primitivní proceduru, tedy nikoliv o uživatelsky definovanou proceduru. Naprogramujte tuto primitivní proceduru tak, aby mohla pracovat s libovolným množstvím seznamů (vždy však alespoň s jedním).

3. Analogicky proveďte obohacení interpretu o primitivní proceduru foldl.

4. Obohaťte vytvořený interpret jazyka Scheme o speciální formu or. Tuto speciální formu naprogramujte tak, aby se chovala přesně jako speciální forma or v jazyku Scheme, viz [R5RS].

5. Obohaťte vytvořenýinterpret jazyka Scheme o speciální formu let (nepojmenovanou verzi).

6. Obohaťte vytvořenýinterpret jazyka Scheme o pojmenovaný let. Jelikož v jazyku nemáme k dispozici define, musíme si při programování pojmenovaného let pomocí y-kombinátoru. Speciální formu ale vytvořte tak, abychom při rekurzivní aplikaci nemuseli předávat proceduru prostřednictvím jejího prvního argumentu. Vytvořený pojmenovaný let by se tedy z uživatelského pohledu měl chovat jako pojmenovaný let popsaný ve [R5RS].

7. Obohaťte interpret jazyka Scheme o speciální formu dyn-apply, která bude provádět aplikaci procedur podobně jako apply, ale při aplikaci procedur pomocí dyn-apply se budou při vyhodnocování těla procedury hledat vazby symbolů ve smyslu dynamického rozsahu platnosti, tedy v prostředí aplikace procedury. Na následujícím příkladu je vidět rozdíl použití apply a dyn-apply: str317

2)) 100) '(20))) 1000)

;⇒

120

3)) 100)

'(20)))

1000)

;⇒

1020

8. Obohat’te interpret o novou speciální formu delta, která je po syntaktické stránce shodnás formou lambda. Vyhodnocením δ-vy

́ razu vznikne speciální typ uživatelsky definované procedury. Při aplikaci procedury vzniklé vyhodnocením δ-výrazů je uplatněn dynamický rozsah platnosti. Zavedení δ-výrazů

do jazyka nám tedy umožní vytvářet uživatelsky definované procedury, jejichž vyhodnocování probíhá

v souladu s dynamickým rozsahem platnosti. Viz příklad použití a rozdíl v použitíspeciálních forem lambda a delta.

4)) 100) 20)) 1000)

;⇒

120

5)) 100) 20)) 1000)

;⇒

1020

Při implementaci využijte svých znalostíze sekce 2.6.

9. Napište, jak interpret Scheme vyhodnotínásledujícísymbolické výrazy: (environment→list

6) 10))

;⇒

7))

100)

;⇒

(eval '(+ x 1)

8) 10))

;⇒

9) (procedure-environment x)))

(lambda (x) 'blah)))

1000)

;⇒

(environment→list

(procedure-environment

10))

100)))

;⇒

318

U

́ koly k textu

1. Vytvořte systém generických procedur +, -, *, modulo, quotient a = sloužících pro práci s čísly a polynomy. Polynomy (jedné proměnné) reprezentujte seznamy jejich koeficientů tak, jak jsme to dělali v sekci 8.6. Základní aritmetické procedury +, -, * slouží k provádění aritmetických operacís čísly a polynomy. Například tedy pro * by to mělo pokrývat součin čísel, součin polynomů a součin čísla s polynomem. Procedury modulo a quotient by měly vracet podíl čísel nebo polynomů a zbytek po děleníčíslem nebo polynomem. Predikát = by měl sloužit k porovnáváníčísel a polynomů.

Při implementaci si pomozte tím, že čísla jsou de facto konstantní polynomy. Kde lze, provádějte automatické přetypování.

2. Po dokončení předchozího úkolu naprogramujte procedury pro sčítání a násobení matic. Pokud jsme provedli správnou implementaci v předchozím bodě, měla by vaše implementace operacís maticemi umožňovat pracovat s maticemi jejichž prvky jsou čísla nebo polynomy. Důkladně vaši implementaci otestujte.

3. Obohat’te interpret jazyka Scheme o speciální formy cond a let*. Obě speciální formy naprogramujte tak, aby se chovaly stejně, jak jsme je představili v lekcích 2 a 3. Implementace obou speciálních forem důkladně otestujte a přesvědčte se o jejich správnosti.

4. Obohat’te interpret jazyka Scheme o speciální formu named-lambda, která je po syntaktické stránce totožnáse speciální formou lambda. Speciální forma named-lambda slouží k vytváření procedur stejně jako speciální forma lambda, navíc však v těle procedury vytvořené pomocínamed-lambda je vždy na symbol self navázanásamotná procedura. Pomocíself je tedy možné provádět rekurzivní

volání, viz následující příklad použití.

(map (named-lambda (n)

(if (= n 0)

1

(* n (self (- n 1)))))

'(0 1 2 3 4 5 6 7 8))

;⇒

(1 1 2 6 24 120 720 5040 40320)

5. V předchozích příkladech na procvičení jsme viděli dva přístupy k aplikaci procedur řídícíse dynamickým rozsahem platnosti. První metodou bylo použití explicitní aplikace pomocí dyn-apply.

Druhým způsobem bylo zavedení δ-výrazů, pomocínichž vznikaly procedury aplikované vždy ve smyslu dynamického rozsahu platnosti. Ani jedno z těchto řešenínení úplně idé alní, protože v ně-

kterých případech by se mohlo hodit, abychom v těle jedné procedury uvažovali většinu symbolů ve smyslu lexikálního rozsahu platnosti (zajímat se budeme o lexikální vazby symbolů) a některé symboly ve smyslu dynamického rozsahu platnosti (zajímat se budeme o dynamické vazby symbolů).

Obohat’te interpret o speciální formu dynamic, jejímž jediným argumentem bude symbol. Výsledkem vyhodnocení (dynamic x) (v daném prostředí) je dynamická vazba symbolu x, tedy vazba, která

je hledána v dynamicky nadřazených prostředích (pokud nenínalezena v lokálním prostředí), viz sekci 2.6. Následující ukázka demonstruje použití dynamic.

11)) 100) 20)) 1000)

;⇒

120

12)) 100) 20)) 1000)

;⇒

1020

319

Řešení ke cvičením

1. “2/3.0.5”, “-1x-2”, “12+7”, “22310”, 4.0, Error: No method for these types, “123”

2. Vytvoříme pomocnou proceduru scm-foldr následovně:

(define scm-foldr
  (lambda (f basis . lists)
    (if (scm-null? (car lists))
      basis
      (scm-apply
        f
        (append (map pair-car lists)
                (list (apply
                        scm-foldr
                        f basis (map pair-cdr lists))))))))

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam: (foldr . ,(make-primitive scm-foldr))

3. Vytvoříme pomocnou proceduru scm-foldl následovně:

(define scm-foldl
  (lambda (f basis . lists)
    (let iter ((lists lists)
               (accum basis))
      (if (scm-null? (car lists))
        accum
        (iter (map pair-cdr lists)
              (scm-apply f (append (map pair-car lists)
                                   (list accum))))))))

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam: (foldl . ,(make-primitive scm-foldl))

4. Vytvoříme pomocnou proceduru scm-or následovně:

(define scm-or
  (lambda (env . exprs)
    (let or-eval ((exprs exprs))
      (cond ((null? exprs) scm-false)
            ((null? (cdr exprs)) (scm-eval (car exprs) env))
            (else (let ((result (scm-eval (car exprs) env)))
                    (if (equal? result scm-false)
                      (or-eval (cdr exprs))
                      result)))))))

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam: (or . ,(make-specform scm-or))

5. Vytvoříme pomocnou proceduru map-scm-list pro mapování přes seznam ve vnitřní reprezentaci: (define map-scm-list (lambda (f l) (convert-list scm-null? pair-car pair-cdr make-pair the-empty-list f l))) Dále vytvoříme pomocnou proceduru scm-let:

(define scm-let
  (lambda (env bindings body)
    (let ((proc (make-procedure
                  env
                  (map-scm-list pair-car bindings)
                  body)))
      (scm-apply proc
                 (map-scm-list->list
                   (lambda (elem)
                     (scm-eval (pair-car (pair-cdr elem)) env))
                   bindings)))))

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam: (let . ,(make-specform scm-let)) str320

6. Vytvoříme nejprve pomocný konstruktor seznamu v interní reprezentaci:

(define make-list
  (lambda args
    (if (null? args)
      the-empty-list
      (make-pair (car args)
                 (apply make-list
                        (cdr args))))))

Pro programování pomocné procedury, která bude v konstruovaném interpretu realizovat speciální formu „pojmenovaný let“ si musíme uvědomit, že kód ve tvaru

(let
  jméno (( symbol1
            výraz1 )
           ( symbol2
             výraz2 )
           .
           .
           .
           ( symboln
             výrazn ))
  tělo )

stačí nahradit kódem ve tvaru

((lambda (y)
   (y y
      výraz1
      výraz2 · · · výrazn ))
 (lambda ( jméno
           symbol1
           symbol2 · · · symboln )
   ((lambda ( jméno )
      tělo )
    (lambda ( symbol1
              symbol2 · · · symboln )
      ( jméno
        jméno
        symbol1
        symbol2 · · · symboln )))))

Podle tohoto postupu naprogramujeme pomocnou proceduru scm-named-let:

(define scm-named-let
  (lambda (env . args)
    (if (not (scm-symbol? (car args)))
      (apply scm-let env args)
      (let* ((name (car args))
             (bindings (cadr args))
             (body (caddr args))
             (y (make-symbol 'y))
             (y-comb (make-procedure
                       env
                       (make-list y)
                       (make-pair y
                                  (make-pair y
                                             (map-scm-list
                                               (lambda (elem)
                                                 (scm-eval (pair-car (pair-cdr elem)) env))
                                               bindings)))))
             (proc (make-procedure
                     env
                     (make-pair
                       name
                       (map-scm-list pair-car bindings))
                     (make-list
                       (make-list (make-symbol 'lambda)
                                  (make-list name)
                                  body)
                       (make-list (make-symbol 'lambda)
                                  (map-scm-list pair-car bindings)
                                  (make-pair name
                                             (make-pair name
                                                        (map-scm-list pair-car bindings))))))))
        (scm-apply y-comb (list proc))))))

str321

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam:

(let . ,(make-specform scm-named-let))

7. Vytvoříme pomocnou proceduru scm-dyn-apply následovně:

(define scm-dyn-apply
  (lambda (env proc . rest)
    (scm-eval
      (make-pair (make-symbol 'env-apply)
                 (make-pair
                   proc
                   (make-pair
                     env
                     (let iter ((ar rest))
                       (if (null? (cdr ar))
                         (make-pair (car ar) the-empty-list)
                         (make-pair (car ar)
                                    (iter (cdr ar))))))))
      env)))

Dále je nutné do tabulky vazeb prostředí „toplevel“ přidat záznam: (dyn-apply . ,(make-specform scm-dyn-apply))

8. Nejprve vytvoříme datovou reprezentaci nového typu elementu:

(define make-dyn-procedure
  (let ((make-physical-procedure (curry-make-elem 'dyn-procedure))) (lambda (args body)
                                                                      (make-physical-procedure (list args body)))))
 
(define dyn-procedure-arguments (lambda (proc) (car (get-data proc))))
(define dyn-procedure-body (lambda (proc) (cadr (get-data proc))))
(define scm-user-dyn-procedure? (curry-scm-type 'dyn-procedure))

Upravíme scm-procedure? tak, aby brala ohled i na nový typ procedury:

(define scm-procedure?
  (lambda (elem)
    (or (scm-primitive? elem)
        (scm-user-procedure? elem)
        (scm-user-dyn-procedure? elem))))

Dále přidáme do tabulky vazeb prostředí „toplevel“ záznam:

(delta . ,(make-specform
            (lambda (env args body)
              (make-dyn-procedure args body))))

Upravíme scm-eval tak, aby se při voláníscm-apply předávalo aktuální prostředí jako nový poslední argument. Kritický fragment kódu by měl vypadat takto:

.
.
.
((scm-procedure? f)
 (scm-apply f
            (map-scm-list->list
              (lambda (elem)
                (scm-eval elem env))
              args)
            env))
.
.
.

str322 Dále upravíme scm-env-apply a scm-apply následovně tak, že do nich přidáme větve ošetřující průběh aplikaci v případě procedur vzniklých vyhodnocením δ-výrazů.

(define scm-env-apply
  (lambda (proc env args)
    (cond ((scm-primitive? proc) (apply (get-data proc) args))
          ((scm-user-procedure? proc)
           (scm-eval (procedure-body proc)
                     (make-env env
                               (make-bindings (procedure-arguments proc)
                                              args))))
          ((scm-user-dyn-procedure? proc)
           (scm-eval (dyn-procedure-body proc)
                     (make-env env
                               (make-bindings (dyn-procedure-arguments proc)
                                              args))))
          (else (error "APPLY: Expected procedure")))))
 
(define scm-apply
  (lambda (proc args . env)
    (cond ((scm-primitive? proc) (scm-env-apply proc #f args))
          ((scm-user-procedure? proc)
           (scm-env-apply proc (procedure-environment proc) args))
          ((scm-user-dyn-procedure? proc)
           (scm-env-apply proc (car env) args))
          (else (error "APPLY: Expected procedure")))))

9.

((x . 10)),
-100,
11,
(1000 . x),
((y . 100))

str323

2014/04/24 16:04
1)
10 . 20) . 30) 10 20 30 ((10 20 . 30) . 40) 10 20 30 40 (10 (20 . 30) . 40) 10 20 30 40 ((10 . 20) 30 . 40) 10 20 30 40 101 5/Příklad 4.9 Tečkové páry z příklad 4.8 v boxovénotaci najdeme na obrázku 4.2. 5/Příklad 4.10 Přirozeně nemusíme konstruovat páry jen z čísel a párů, jako v doposud uvedených příkladech. Můžeme vytvářet páry z jakýchkoli elementů:
(cons + -) ;⇒ („procedura sčítání“ . „procedura odčítání“)
(cons and not) ;⇒ („speciální forma and“ . „procedura negace“)
(cons (if #f #f) #t) ;⇒ („nedefinovaná hodnota“ . #f)
Páry jsou elementy prvního řádu. Pokud se vrátíme k definice 2.17 na straně 56, pak můžeme jasně vidět, že páry je možno pojmenovat, předávat jako argumenty procedurám, vracet jako výsledky aplikace procedur a mohou být obsaženy v hierarchických datových strukturách (páry mohou být opět obsaženy v jiných párech). Poslední, co zbývá k tečkovým párům říct, je to, jak vlastně páry zapadají do Read a Eval částí REPL cyklu. Existenci párů jsme v lekci 1 při definici symbolických výrazů zatajili. Ve skutečnosti i externí reprezentace řady tečkových párů je čitelná readerem 5. V tuto chvíli můžeme obohatit množinu přípustných symbolických výrazů jazyka Scheme o speciální výrazy, které se shodujís externí reprezentacíněkterých tečkových párů. Rozšíříme definici 1.6 ze strany 19 o následujícínový bod:
  • Jsou-li e, f, e1, e2, . . . , en symbolické výrazy (n ≥ 0), pak (e e1 e2 · · · en . f )
je symbolický výraz. Pokud je n = 0, symbolický výraz (e . f ) nazveme pár. Teď nám ale dochází k nepříjemné dvojznačnosti: S-výraz (e . f ) teď můžeme považovat za tříprvkovýseznam obsahující výraz e, symbol „.“ a výraz f , a takéza tečkový pár obsahující výrazy e a f . Aby k této dvojznačnosti nedocházelo, je potřeba zpřísnit definici symbolu o následující rys: Samostatný znak „.“ nenísymbol. S-výraz (e . f ) tak může být jedině pár. Další nejednoznačnost je v terminologii. Musíme si ujasnit, že i když nazýváme symbolický výraz pár i element pár shodně, to jest „pár“, jednáse o dvě různé věci. Pár jako symbolický výraz určuje jak může vypadat část programu (je to syntaktický pojem), kdežto pár jako element reprezentuje konkrétní hodnoty, se kterými pracuje interpret při vyhodnocování, jednáse tedy o sémantický pojem těsně spjatýs (abstraktním) interpretem jazyka Scheme. Řekli jsme si tedy, že páry jsou čitelné readerem. Co jsme ale ještě neřekli je, jak se vyhodnocují. Podle toho, jak jsme nadefinovali Eval v definici 3.21 na straně 27, by se měl pár podle bodu (D) vyhodnotit sám na sebe. Podotkněme nyní, že z praktického hlediska se interprety jazyka Scheme dávají na vyhodnocování párů jinak. Zatím vyhodnocování párů ponecháme stranou a popíšeme je až v další sekci. Na konci této sekce uvádíme několik zajímavých příkladů: Příklad 4.11. V následujícím kódu vytváříme páry, které potom navazujeme na symboly. Nejprve na symbol a navážeme jeden pár a pomocíněj potom vytvoříme druhý pár a navážeme jej na symbol b. Pokud provedeme změnu vazby symbolu a, pár navázanýna symbolu b se (pochopitelně) nezmění:
(define a (cons 10 20))
(define b (cons (car a) 30)) b ;⇒ (10 . 30)
(define a (cons 5 -5)) b ;⇒ (10 . 30)
To vyplýváze sémantiky speciální formy define, viz definici 1.26 na straně 1.26 a z faktu, že cons je procedura. Při vyhodnocení výrazu (cons (car a) 30) je aplikována procedura cons na vyhodnocení výrazů (car a) a 30 – to jest na čísla 10 a 30. Výsledkem aplikace procedury cons je pak pár (10 . 30), a je navázán na symbol b. Předefinováním hodnoty navázanéna symbol a pomocí define se pak pár navázanýna symbol b nezmění. 5Někdy tomu tak ovšem být nemusí, vezměme si třeba tečkové páry z příkladu 4.10. Jejich externí reprezentace bude pro reader nečitelná, protože páry obsahují elementy s nečitelnou reprezentací (procedury, speciální formy a nedefinovanou hodnotu). str102 5/Příklad 4.12. Nadefinujeme proceduru, která vrací pár, jehož prvním prvkem je právě tato procedura:
(define a (lambda () (cons a #f)))
(a) ;⇒ („procedura“ . #f)
(car (a)) ;⇒ „procedura“
((car (a))) ;⇒ („procedura“ . #f)
(car ((car (a)))) ;⇒ „procedura“
...
5/Příklad 4.13. V lekci 2 jsme v příklady 2.11 na straně 69 definovali proceduru vyššího řádu extrem na vytváření procedur hledání extrémní hodnoty ze dvou argumentů vzhledem k nějakému uspořádání (viz program 2.11). Nyní můžeme vytvořit proceduru která vytváří dvě procedury současně – jednu na nalezení jednoho extrému a druhou na nalezení opačného extrému – a vrací je v páru:
(define extrem-pair
(lambda (p?)
(cons (extrem p?)
(extrem (lambda (a b) (not (p? a b)))))))
Aplikací procedury extrem jednou na výchozí predikát a jednou na predikát vytvořenýz výchozího pomocínegace podmínky dané tímto predikátem, jsme tedy dostali dvě procedury, ze kterých jsme pomocícons vytvořili tečkový pár. Procedury min a max pomocí procedury extrem-pair můžeme definovat třeba takto:
(define extrems (extrem-pair <))
(define min (car extrems))
(define max (cdr extrems))
Poznámka 4.14. Vrátíme-li se nyní k motivačnímu příkladu s řešením kvadratické rovnice ze začátku této sekce, pak snadno nahlédneme, že bychom mohli chybějící tělo v proceduře koreny doplnit výrazem (cons koren-1 koren-2). To by byl úplně nejjednodušší způsob, jak vrátit „dvě hodnoty současně.“ Z hlediska čistoty programu by již toto řešení bylo diskutabilní, jak uvidíme v další sekci. s4_3 ======= 4.3 Abstrakční bariéry založenéna datech ======= V předchozí lekci jsme mimo jiné mluvili o vrstvách programu a o abstrakčních bariérách založených na procedurách. Abstrakční bariéry založenéna datech jsou obecnějšínež abstrakční bariéry pomocí procedur, protože pro nás jsou procedury data (lze s nimi zacházet jako s daty). Procedury hrají ale i při datové abstrakci důležitou roli a tou je odstínění fyzické reprezentace dat od jejich uživatele. Při vytváření abstrakčních bariér v programech bychom se tedy měli soustředit jako na procedury tak na data. Jednostranné zaměření na to či ono skoro nikdy nepřinese nic dobrého. Účelem datové abstrakce je oddělit data na nižší úrovni od abstraktnějších dat a mít pro ně vytvořené separátní konstruktory a selektory (pomocí nichž je abstrakční bariéra de facto vytvořena). Opět zdůrazněme, že při vývoji programu je (i z pohledu dat) vhodné používat styl bottom-up, tedy pracovat a přemýšlet nad programem jako nad postupným obohacováním jazyka. V případě datové abstrakce jde o rozšiřování jazyka o nové datové typy. Pro ilustraci si uveďme následující příklad. 5/Příklad 4.15 Jako příklad použití abstraktních bariér uvádíme program 4.1 na výpočet kořenů kvadratické rovnice. Tento krátký program je rozdělen do tří vrstev, které jsou znázorněny na obrázku 4.3. Nejnižší vrstvu tvoří vrstva jazyka Scheme a konkrétní implementace tečkových párů. To jak tato implementace vypadánás ve vyšších vrstvách nezajímá, pro nás jsou důležité konstruktory a selektory párů, které nám tato vrstva nabízí. Hned nad touto nejnižší vrstvou je vrstva implementace dvojice kořenů. Dvojici kořenů implementujeme pomocí tečkových párů, to pro nás ale v dalších vrstvách není důležité. Co je důležité jsou procedury vrat-koreny, prvni-koren a druhy-koren sloužící jako konstruktor a selektory pro dvojici kořenů. Dále již pracujeme jen s nimi. Všimněte si, že v procedurách najdi-koreny a dvojnasobny? neuvažujeme dvojice kořenů jako páry. str103 Například definici procedury najdi-koreny by bylo chybou namísto (vrat-koreny · · · napsat (cons · · · , protože by tím došlo k porušení pomyslné abstrakční bariéry. Na symboly vrat-koreny a cons je sice navázanástejná procedura, ale při změně vrstvy „práce s kořeny“ (viz obrázek 4.3) bychom museli měnit i vyšší vrstvu. Třeba hned v úvodu dalšísekce ukážeme, jak bychom mohli zacházet s kořeny, kdybychom neměli k dispozici tečkové páry. Obdobným způsobem bychom mohli napsat i proceduru vrat-koreny. 5;Program 4.1 Příklad abstrakční bariéry: výpočet kořenů kvadratické rovnice.
(define vrat-koreny cons)
(define prvni-koren car)
(define druhy-koren cdr)
 
(define najdi-koreny
  (lambda (a b c)
    (let ((diskr (- (* b b) (* 4 a c))))
      (vrat-koreny (/ (- (- b) (sqrt diskr)) 2 a)
		   (/ (+ (- b) (sqrt diskr)) 2 a)))))
 
(define dvojnasobny?
  (lambda (koreny)
    (= (prvni-koren koreny)
       (druhy-koren koreny))))
Obrázek 4.3. Schéma abstrakčních bariér Pro každá data, kteráse v programu vyskytují, bychom měli vytvořit sadu nezávislých konstruktorů a selektorů. To vede ke snadneú́držbě kódu a k snadným případným změnám implementace. Vždy je potřeba najít vhodneékvilibrium mezi množstvím abstrakčních bariér a efektivitou programu (optima-104 lizací programu týkajícíse jeho rychlosti, spotřeby systémových zdrojů a podobně). Tyto dvě kvality programu jdou leckdy proti sobě. s4_4 ======= 4.4 Implementace tečkových párů pomocí procedur vyšších řádů ======= V této sekci se budeme zabývat tím, zda-li je nutné k vytvoření elementů zapouzdřující dvojice hodnot uvažovat noveélementy jazyka (tečkové páry) tak, jak jsme to dělali doposud, nebo jestli není možné je modelovat s tím, co už máme v jazyku Scheme k dispozici. V této sekci ukážeme, že páry lze plně implementovat pouze s využitím procedur vyšších řádů a lexikálního rozsahu platnosti. Nejdříve problematiku demonstrujeme na příkladu 5.1 s kořeny kvadratické rovnice z úvodu lekce. Poté tuto myšlenku zobecníme tak, že pomocí procedur vyšších řádů naimplementujeme vlastní tečkové páry. Zopakujme, že chceme vytvořit proceduru, která by pro kvadratickou rovnici ax2 + bx + c = 0 zadanou jejími koeficienty a, b a c spočítala její dva kořeny a předpokládejme při tom, že nemáme k dispozici cons, car a cdr o kterých jsme doposud hovořili. Kód z příkladu 4.1 doplníme tak, jak je to ukázáno v programu 4.2. Do těla let*-bloku (které v kódu z úvodu lekce chybělo) jsme dali výraz: 5;Program 4.2 Implementace procedury koreny pomocí procedur vyšších řádů.
(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))))
      (lambda (prvni-nebo-druhy)
	(if prvni-nebo-druhy koren1 koren2)))))
(lambda (prvni-nebo-druhy)
  (if prvni-nebo-druhy
    koren1
    koren2))
Ten je při aplikaci procedury koreny vyhodnocen v posledním prostředí P3 (viz obrázek 4.4) vytvořeném vyhodnocením let*-bloku. Tedy v prostředí, ve kterém jsou známy vazby na symboly koren1 a koren2. V tomto prostředí P3 nám tedy vzniká procedura, kterána základě pravdivostní hodnoty, na kterou je aplikovaná, vrací buďto element navázanýna symbol koren1 nebo na koren2. Obrázek 4.4. Vznik prostředí při aplikaci procedury z příkladu 4.2
(koreny 1 -2 2) ;⇒ procedura
 
(define oba-koreny (koreny 1 -2 2))
 
(oba-koreny #t) ;⇒ 1+i
 
(oba-koreny #f) ;⇒ 1-i
str105 Při aplikaci procedury navázanéna symbol oba-koreny s různými pravdivostními hodnotami jako argumenty tedy dostáváme jednotlivé kořeny. Je tomu skutečně tak, protože v prostředí vzniku procedury jsou symboly koren1 a koren2 navázanéna hodnoty vypočtené již při aplikaci procedury koreny. Podle toho také můžeme vytvořit selektory prvni-koren a druhy-koren. Ty budou proceduru zapouzdřující oba kořeny aplikovat na pravdivostní hodnoty, podle toho, kterýz nich chceme:
(define prvni-koren (lambda (oba) (oba #t)))
(define druhy-koren (lambda (oba) (oba #f)))
(prvni-koren oba-koreny) ;⇒ 1+i
(druhy-koren oba-koreny) ;⇒ 1-i
Nyní z tohoto příkladu vytáhneme základní myšlenku – možnost uchovat vazby dvou symbolů v prostředí, které mohou reprezentovat „dvě hodnoty pohromadě“, a možnost přístupu k těmto prvkům pomocí procedur vyšších řádů. Ukážeme tedy, jak naimplementovat tečkové páry pouze s využitím procedur vyšších řádů a s využitím vlastností lexikálního rozsahu platnosti. Bez něj by dále uvedeneú́vahy o implementaci párů neměly význam (při použití dynamického rozsahu platnosti bychom velmi brzy narazili na fatální problémy). Naše implementace nám zároveň dá odpověď na fundamentální otázku, zda jsou páry definovatelné pomocí procedur vyšších řádů (odpověď bude kladná). Pár v naší reimplementaci tedy bude procedura, která pro různé argumenty vrací různé prvky páru. Nově vytvářenýcons bude procedurou vyššího řádu, která bude náš pár vytvářet. Podívejme se na následující implementaci procedury cons:
(define cons
  (lambda (x y)
    (lambda (k)
      (if k x y))))
Při její aplikaci bude vytvořeno prostředí P, ve kterém budou existovat vazby na symboly x a y. Toto prostředí pak bude prostředím vzniku procedury (k), (if k x y), P . Výsledkem aplikace procedury cons tedy bude procedura, která v závislosti na jejím jednom argumentu k bude vracet buďto hodnotu navázanou na symbol x nebo y. Přitom x a y nejsou mezi formálními argumenty vrácené procedury, ta má pouze formální argument k. To jest vazby symbolů x a y se budou při vyhodnocování těla vrácené procedury hledat v nadřazeném prostředí a to je právě prostředí jejího vzniku, tedy P. Při aplikaci této procedury s různými pravdivostními hodnotami dostáváme jednotlivé složky páru.
((cons 1 2) #t) ;⇒ 1
((cons 1 2) #f) ;⇒ 2
Selektory car a cdr zavolají takto vzniklou proceduru s různým argumentem. Jde vlastně o totéž jako v programu 4.4. Přehledně je to znázorněno na obrázku 4.5.
(define car (lambda (p) (p #t)))
(define cdr (lambda (p) (p #f)))
(define p (cons 2 3))
p ;⇒ „procedura“
(car p) ;⇒ 2
(cdr p) ;⇒ 3
Můžeme udělat ještě jinou reimplementaci, která je z hlediska funkcionálního programovaníčistější. Provedeme vlastně totéž, ale s použitím procedur projekce. Z lekce 2 známe procedury projekce, vracející jeden z jejich argumentů. Pomocí těchto procedur můžeme jednoduše implementovat konstruktor a selektory párů, viz program 4.3. Výsledkem aplikace procedury cons bude procedura, v jejímž prostředí vzniku budou na str106 Obrázek 4.5. Prostředí vznikající při použití vlastní implementace párů 5;Program 4.3 Implementace tečkových párů pomocí procedur vyšších řádů.
(define cons
  (lambda (x y)
    (lambda (proj)
      (proj x y))))
 
(define 1-z-2 (lambda (x y) x))
 
(define 2-z-2 (lambda (x y) y))
 
(define car (lambda (p) (p 1-z-2)))
 
(define cdr (lambda (p) (p 2-z-2)))
symboly x a y navázané argumenty se kterými byla cons aplikována což jsou, stejně jako v předchozím případě, elementy z nichž chceme „vytvořit pár“. Tato procedura nebude brát jako argument pravdivostí hodnotu, nýbrž projekci. Selektory car a cdr pak opětně ve svém těle volají tuto proceduru s různými projekcemi. Opět se můžeme vrátit k abstrakčním bariérám založeným na datech. V předchozí podkapitole jsme uvedli, že bariéry založené na datové abstrakci jsou de facto obecnější než bariéry založenéna procedurální abstrakci. Když si nyní uvědomíme, že hierarchická data lze plně vyjádřit pouze pomocí procedur vyšších řádů, ihned dostaneme, že bariéry založenéna datové abstrakci jsou „stejně silné“ jako bariéry založenéna procedurální abstrakci. Podotkněme, že toto pozorování vlastně říká, že nemá příliš smysl odlišovat od sebe procedurální a datovou abstrakci – můžeme se bez újmy bavit pouze o jediné abstrakci (datové = procedurální). V drtivé většině programovacích jazyků si však takový „luxus“ dovolit nemůžeme, protože v nich nelze s programy (respektive s procedurami) zacházet jako s daty ani tak nelze činit obráceně. Právě popsaný pohled na datovou a procedurální abstrakci je silným rysem řady funkcionálních jazyků, především pak dialektů LISPu k nimž patří i jazyk Scheme. s4_5 ======= 4.5 Symbolická data a kvotování ======= Doposud jsme všechna složená data, která jsme používali, konstruovali až na výjimky pomocí párů z čísel. Na čísla se lze dívat jako na primitivní, nedělitelnáneboli nehierarchická data. V této sekci rozšíříme vyjadřovacísílu našeho jazyka uvedením možnosti pracovat s libovolnými symboly jako s daty. Nejprve řekněme, k čemu by nám to mohlo být dobré. Symboly slouží při programování jako „jména“ a v programech je leckdy potřeba pracovat se jmény jako s daty. Pomocísymboly můžeme například označovat některéčásti hierarchických datových struktur (uvidíme v dalších lekcích) nebo mohou sloužit přímo jako zpracovávaná data. Například symboly Praha, New-York, Prostejov a další můžeme chápat jako „jména měst“, symboly red, green, blue, … můžeme v programech chápat jako symbolická označení barev a tak dále. str107 Se symbolly můžeme pracovat jako s daty díky speciální formě quote, která zabraňuje vyhodnocování svého (jediného) argumentu. 9/Definice 4.16 (speciální forma quote). Speciální forma quote se používás jedním argumentem
(quote arg )
. Výsledkem aplikace této speciální formy je pak arg . Jinými slovy, speciální forma quote vracísvůj argument v nevyhodnocené podobě. Přesněji, označíme-li Q speciální formu navázanou na quote, pak Apply(Q, arg ) := arg . Zde máme příklady aplikace speciální formy quote.
(quote 10) ;⇒ 10
(quote blah) ;⇒ blah
(quote (a . b)) ;⇒ (a . b)
Poznámka 4.18. (a) Je naprosto zřejmé, že na symbol quote musí být navázána speciální forma. Kdyby to byla procedura, muselo by dojít k vyhodnocení jejího argumentu, jak vyplýváz definice 1.21. (b) Všimněte si, že je zbytečné kvotovat čísla. Stejně tak je zbytečné kvotovat jakýkoli jiný element, který se vyhodnocuje sám na sebe. V takovém případě se totiž vyhodnocený element rovná nevyhodnocenému. Konkrétně třeba výraz (quote 10) se vyhodnotína číslo 10, ale číslo 10 se vyhodnotísamo na sebe – tedy na číslo 10. © Slovo „quote“ znamená v angličtině „uvozovka“. Použití kvotování je analogické s použitím uvozovek v přirozeném jazyce. Porovnejte například věty: (i) Zobraz x; a (ii) Zobraz „x“. Pro zkrácení zápisu je ve Scheme možné namísto (quote arg ) psát jen 'arg . Tedy můžeme psát:
'blah ;⇒ blah
'10 ;⇒ 10
'(a . b) ;⇒ (a . b)
Poznámka 4.18. Apostrof ' je takzvaný syntaktický cukr pro quote a neměli bychom jej chápat ani jako samostatný symbol ani jako rozšíření syntaxe jazyka Scheme6. Z našeho pohledu je to v podstatě jen metasyntaktickáznačka (je „nad“ syntaxí jazyka Scheme), kterou zkracujeme delší výraz. Syntaktickýcukr je terminus technicus užívající se pro rozšíření zápisu programu, které jej dělajísnadnější („sladší“) pro použitíčlověkem. Syntaktický cukr dává člověku alternativní způsob psaní kódu, který je praktičtější tím, že je stručnějšínebo tím, že je podobnýně jakéznámé notaci. V případě jednoducheúvozovky ve Scheme vlastně jde o obojí. Zápis je stručnější a podobný použití uvozovek v přirozeném jazyce. Pozor! Je opět nutné rozlišovat symbol samotnýa element navázanýna symbol. Jde o dvě zcela odlišné věci, jak již dobře víme z předchozích lekcí. Nyní se tento kontrast ale zvětšuje, protože symboly jsou pro nás nejen jedny ze symbolických výrazů, ale díky quote již může pracovat se symboly jako s elementy jazyka. Například v následujícím kódu navážeme na symbol plus různé elementy – jednou proceduru navázanou na symbol +:
(define plus +)
(plus 1 2) ;⇒ 3
plus ;⇒ „procedura sčítání čísel“
a podruhé, s použitím kvotování, symbol +:
(define plus '+)
(plus 1 2) ;⇒ „CHYBA: + není procedura ani speciální forma.“
plus ;⇒ +
6 Při konstrukci konkrétního interpretu jazyka Scheme je však potřeba tento symbol načítat a brát jej v potaz. Reader musí být uzpůsoben k tomu, aby mohl zkrácené výrazy nahrazovat seznamy s quote. Takže někdo by v tuto chvíli mohl namítat, že apostrof je součástísyntaxe jazyka Scheme. U konkrétních interpretů tomu tak je. Z pohledu abstraktního interpretu Scheme však budeme apostrof uvažovat „mimo jazyk“ a tím pádem nebudeme muset opět rozšiřovat definici symbolických výrazů. str108 5/Příklad 4.19. Pomocí define můžeme zavést symboly, které se vyhodnocují na sebe sama:
(define blah 'blah)
blah ;⇒ blah
s4_6 ======= 4.6 Implementace racionální aritmetiky ======= V této sekci naimplementujeme vlastní racionální aritmetiku. Jedná se o komplexní příklad demonstrující práci s páry, datovou abstrakcí a abstrakčními bariérami. Nejprve vytvoříme konstruktor make-r a selektory numer a denom. První verze konstruktoru bude vypadat jednoduše – prostě ze dvou argumentů představujících jmenovatele a čitatele vytvoříme tečkový pár.
(define make-r (lambda (x y) (cons x y)))
Podle toho pak také budou vypadat selektory: numer bude vracet první prvek tohoto páru a denom jeho druhý prvek.
(define numer (lambda (x) (car x)))
(define denom (lambda (x) (cdr x)))
Nyní naimplementujeme procedury pro základní aritmetické operace s racionálními čísly: procedury r+ a r- pro sčítání a odčítání. Další procedury r* a r/ budou součástí úkolů na konci lekce. Procedury jsou přímým přepisem předpisu a c ad ± bc ± = b d bd Všimněte si, že v kódu už nebudeme používat procedury cons, car a cdr, protože se nacházíme za abstrakční bariérou a nepracujeme již s páry (s konkrétní reprezentací), ale s racionálními čísly (s abstrakcí).
(define r+
  (lambda (x y)
    (make-r (+ (* (numer x) (denom y))
	       (* (denom x) (numer y)))
	    (* (denom x) (denom y)))))
 
(define r-
  (lambda (x y)
    (make-r (- (* (numer x) (denom y))
	       (* (denom x) (numer y)))
	    (* (denom x) (denom y)))))
Též můžeme naimplementovat celou řadu predikátů. Protože by se jejich kódy téměr nelišily, vytvoříme je pomocí procedury vyššího řádu:
(define make-rac-pred
  (lambda (p?)
    (lambda (a b)
      (p? (* (numer a) (denom b))
	  (* (numer b) (denom a))))))
 
;Touto procedurou vytvoříme vlastní predikáty na porovnávání racionálních čísel:
(define r< (make-rac-pred <))
(define r> (make-rac-pred >))
(define r= (make-rac-pred =))
(define r<= (make-rac-pred <=))
(define r>= (make-rac-pred >=))
 
(r< (make-r 1 2) (make-r 2 3)) ;⇒ #t
(r> (make-r 1 2) (make-r 2 3)) ;⇒ #f
str109 Dále naprogramujeme procedury r-max a r-min jako analogie procedur max a min z lekce 2. Můžeme k tomu směle využít proceduru vyššího řádu extrem. Tuto proceduru jsme definovali v programu 2.11 na straně 69.
(define r-max (extrem r>))
(define r-min (extrem r<))
Máme tedy procedury na výběr většího či menšího racionálního čísla:
(r-max (make-r 1 2) (make-r 2 3)) ;⇒ (2 . 3)
(r-min (make-r 1 2) (make-r 2 3)) ;⇒ (1 . 2)
Nyní uděláme změnu v konstruktoru racionálního čísla, tak, aby zlomek při vytváření automaticky krátil. Tedy čitatele i jmenovatele vydělí jejich největším společným jmenovatelem. Zbytek kódu (ostatní procedury) se nezmění.
(define make-r
  (lambda (x y)
    (let ((g (gcd x y)))
      (cons (/ x g) (/ y g)))))
Teď provedeme reimplementaci cons, car a cdr tak, jak je to v programu 4.3. Dále pro vypisování doděláme proceduru r→number. To proto, že po reimpelemtaci budou racionálníčísla procedury, jejichž externí reprezentace nám neprozradí jejich složení.
(define r->number
  (lambda (x)
    (/ (numer x) (denom x))))
Všimněte si, že zbytek programu bude fungovat, aniž bychom jej museli měnit. Modifikovali jsme nejspodnější vrstvu programu (viz obrázek 4.6) bez nutnosti měnit vrstvy, které jsou nad ní. Ve vyšších vrstvách je změna neznatelná. Například procedury r-max a r-min budou pracovat bez jakékoli změny:
(r->number (r-max (make-r 1 2) (make-r 2 3))) ;⇒ 2/3
(r->number (r-min (make-r 1 2) (make-r 2 3))) ;⇒ 1/2
Obrázek 4.6. Vrstvy v implementaci racionální aritmetiky str110 A teď ještě jednou změníme procedury navázanéna symboly cons, car a cdr. Tentokrát tak, že zaměníme pořadí prvků v páru. Takže například výraz (cons 1 2) se nevyhodnotína pár (1 . 2), ale na pár (2 . 1). Tedy opět změníme nejspodnější vrstvu programu.
(define kons cons)
(define kar car)
(define kdr cdr)
(define cons (lambda (x y) (kons y x)))
(define car (lambda (p) (kdr p)))
(define cdr (lambda (p) (kar p)))
Díky dodržování abstrakčních bariér se však tato změna neprojeví ve vyšších vrstvách:
(r->number (r-max (make-r 1 2) (make-r 2 3))) ;⇒ 2/3
(r->number (r-min (make-r 1 2) (make-r 2 3))) ;⇒ 1/2
======= Shrnutí ======= V této lekci jsme se zabývali vytvářením abstrakcí pomocí dat. Představili jsme si tečkové páry, pomocínichž vytváříme hierarchické datové struktury. Rozšířili jsme symbolické výrazy o tečkové páry a doplnili Eval. Ukázali jsme rovněž, že tečkové páry bychom mohli plně definovat pouze pomocí procedur vyšších řádů. Dále jsme se zabývali kvotováním a jeho zkrácenou notací, jenž nám umožníchápat symboly jako data. Jako příklad datové abstrakce jsme uvedli implementaci racionální aritmetiky. Pojmy k zapamatování
  • datová abstrakce
  • konstruktor
  • kvotování
  • selektor
  • symbolická data
  • tečkové páry
  • syntaktický cukr
  • konkrétní datová reprezentace
Nově představené prvky jazyka Scheme
  • procedury cons, car, cdr
  • speciální forma quote
Kontrolní otázky
  1. 0;Otázky/L4/Co je datová abstrakce
  2. 0;Otázky/L4/Co jsou páry
  3. 0;Otázky/L4/Jak vypadá externí reprezentace párů
  4. 0;Otázky/L4/Co je boxová notace
  5. 0;Otázky/L4/Jak jsme změnili definici S-výrazu
  6. 0;Otázky/L4/Co je to kvotování
  7. 0;Otázky/L4/Jaká je zkrácená notace kvotování
  8. 0;Otázky/L4/Je možné naimplementovat páry pomocí procedur vyšších řádů? Jak
  9. Otazky/L4/bez hacku a carek
str111 ======= Cvičení 4 ======= 1 Napište bez použití interpretru vyhodnocenínásledujících výrazů:
cons ;⇒
(cons 1 2) ;⇒
(cons car cdr) ;⇒
(cdr (cons cdr cdr)) ;⇒ 
'cons ;⇒
(cons '(cons . cons) car) ;⇒
(cons lambda 'x) ;⇒
('+ 1 2 3 4) ;⇒
'10 ;⇒
'(20 . 40) ;⇒
(caar (cons (cons 1 2) 3)) ;⇒ 
(cadr '((1 . 2) . 4)) ;⇒ 
(car 'cons) ;⇒
(cdr 1 2) ;⇒
(define 'a 10) ;⇒
(if 'symbol 10 20) ;⇒
((car (cons and or))) ;⇒
2. Mějme hierarchická data znázorněná v boxovénotaci na obrázku 2. Napište výrazy, jejichž vyhodnocením vzniknou. Obrázek 4.7. Boxovánotace tečkových párů – zadání ke cvičení
X

#f

7

23

0

+

X

17

blah

13

303

111

X

#t

19

6

X

100

13

#t
3. Napište páry z obrázku 2 v tečkovénotaci. 4. Napište sekvenci procedur car a cdr (respektive složeniny), kterými se v hierarchických strukturách z obrázku 2 dostaneme k prvku X. 112 5. Napište proceduru map-pair, která bere jako argumenty proceduru o jednom argumentu proc a pár pár a vrací pár výsledků aplikací procedury proc na prvky páru pár . Příklady aplikace:
(map-pair - '(1 . 2)) ;⇒ (-1 . -2)
(map-pair (lambda (op) (op 3)) (cons + -)) ;⇒ (3 . -3)
6. Upravte konstruktor racionálních čísel tak, aby jmenovatel byl vždy přirozenéčíslo. Například: (
define r (make-r 3 -4))
(numer r) ;⇒ -3
(denom r) ;⇒ 4
;nikoli
(numer r) ;⇒ 3
(denom r) ;⇒ -4
7. Napište procedury r* a r/ na násobení a dělení racionálních čísel. ======= Úkoly k textu ======= 1. Podobným způsobem jako jsme naimplementovali páry pomocí procedur vyšších řádů (tedy bez použití procedur cons, car, cdr) naimplementujte uspořádané trojice. 2. Pomocí procedur kons,kar a kdr vytvořte obdoby párů z obrázku a nakreslete, jak vypadajá vzniklá hierarchie prostředí a vazby v nich. 3. Zamyslete se nad potřebou zpracovávat složená data. Uveďte jiné příklady, než jsou ukázány v úvodu této lekce, ze kterých tato potřeba vyplývá. Řešení ke cvičením 1. procedura cons, (1 . 2), (procedura car . procedura cdr), procedura cdr, cons, ((cons . cons) procedura car), (specialni forma lambda . x), chyba, 10, (20 . 40) 1, chyba, chyba, chyba, chyba 10, #t 2.
(cons (cons (cons 'X #f) 7) 23)
(cons
  (cons 0 (cons '+ 'X))
  (cons (cons 17 'blah) 13))
 
(cons 303
      (cons (cons 111 'X)
            (cons #t 19)))
 
(cons (cons (cons 6 'X)
            (cons 100 13))
      #t)
3.
(((X . #f) . 7) . 23)
 
((0 + . X) (17 . blah) . 13)
 
(303 (111 . X) #t . 19)
 
(((6 . X) 100 . 13) . #t)
4. caaar, cddar, cdadr, cdaar 5.
(define map-pair
  (lambda (f p)
    (cons (f (car p)) (f (cdr p)))))
6.
(define make-rac
  (lambda (n d)
    (let ((div ((if (< d 0) - +) (gcd n d))))
      (cons (/ n div) (/ d div)))))
str113 7.
(define r*
  (define r/
    (lambda (a b)
      (lambda (a b)
        (make-r (* (numer a) (numer b))
                (make-r (* (numer a) (denom b))
                        (* (denom a) (denom b)))))
      (* (denom a) (numer b)))))
2)
lambda (x) (apply ((lambda (x) (lambda (y) (+ x y
3)
lambda (x) (dyn-apply ((lambda (x) (lambda (y) (+ x y
4) , 11)
lambda (x) (((lambda (x) (lambda (y) (+ x y
5)
lambda (x) (((lambda (x) (delta (y) (+ x y
6) , 8)
lambda (x) (the-environment
7)
lambda (x) (eval '(- x) (the-environment
9)
lambda (x) ((lambda (x) (eval '(cons x (quote x
10)
lambda (y) (lambda (x) (+ x 1
12)
lambda (x) (((lambda (x) (lambda (y) (+ (dynamic x) y
PAPR1/Cviceni.txt · Last modified: 2014/03/14 22:10 (external edit)
CC Attribution-Noncommercial-Share Alike 4.0 International
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0