Paradigmata programování 1 Vytváření abstrakcí pomocí procedur Vilém Vychodil Katedra informatiky, PřF, UP Olomouc
Přednáška 2
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
1 / 43
Přednáška 2: Přehled 1
Uživatelsky definované procedury: procedury a λ-výrazy, speciální forma lambda a vznik procedur aplikace procedur, prostředí a jejich hierarchie, rozšíření vyhodnocovacího procesu, lexikální a dynamický rozsah platnosti symbolů.
2
Procedury vyšších řádů: procedury jako elementy prvního řádu, procedury versus (matematické) funkce.
3
Jazyk Scheme: další podmíněné výrazy, speciální formy cond, and a or.
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
2 / 43
Opakování Syntax a sémantika jazyka syntax = tvar (jak se program zapisuje) sémantika = význam (co program znamená) Jazyk Scheme program = posloupnost S-výrazů, interpretace programu – daná popisem vyhodnocování elementů jazyka během vyhodnocování dochází k postupné aplikaci procedur Abstrakce pojmenováním hodnot definice vazeb symbolů v počátečním prostředí nutné zavést speciální formy vyšší míra abstrakce = vyšší programátorský komfort V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
3 / 43
Nový typ abstrakce: vytváření nových procedur Motivace redundance kódu – snaha eliminovat (čistota kódu / efektivita), vytvoření nové procedury (musíme zajistit), pojmenování nové procedury (známe define).
Příklad (Výpočet délky přepony) Místo: (sqrt (+ (* 3 3) (* 4 4)))
Chceme: (prepona 3 4)
Z=⇒
V. Vychodil (KI, UP Olomouc)
Z=⇒
5
5
Vytváření abstrakcí pomocí procedur
Přednáška 2
4 / 43
λ-výrazy a vznik procedur Vytvoření procedury: Z=⇒ #<procedure 8221f10> „procedura, která pro dané x vrací násobek x s xÿ (lambda (x) (* x x))
Přímá aplikace procedury: ((lambda (x) (* x x)) 8)
Z=⇒
64
Pojmenování a následná aplikace procedury: (define na2 (lambda (x) (* x x))) (na2 2) (+ 1 (na2 4)) (na2 (na2 8))
Z=⇒ Z=⇒ Z=⇒
4 17 4096
Mantra k zapamatování: procedury vznikají vyhodnocením λ-výrazů (!!) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
5 / 43
Syntaxe λ-výrazů Definice (λ-výraz) Každý seznam ve tvaru (lambda (hparam1 i hparam2 i · · · hparamn i) htěloi), kde
n je nezáporné číslo, hparam1 i, hparam2 i, . . . , hparamn i jsou vzájemně různé symboly, htěloi je libovolný symbolický výraz, se nazývá λ-výraz. λ-výraz je seznam (ve speciálním tvaru), symboly hparam1 i, . . . , hparamn i jsou formální argumenty (parametry), n je počet formálních argumentů (parametrů) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
6 / 43
Poznámky k λ-výrazům (lambda (hparam1 i hparam2 i · · · hparamn i) htěloi)
Formální argumenty: účel = pojmenování hodnot (se kterými je vytvořená proc. aplikována), připouští se i nula formálních argumentů (prázdný seznam !!). Tělo procedury: představuje „předpis proceduryÿ, je vykonáváno při aplikaci procedury, (obvykle) obsahuje symboly hparami i. Vyhodnocení λ-výrazů lambda nemůže být procedura, lambda je speciální forma, nutno specifikovat, jak se vyhodnocuje (!!) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
7 / 43
Volné a vázané výskyty symbolů Symboly vyskytující se v těle λ-výrazu dělíme na: 1 vázané symboly – symboly, které jsou formálními argumenty λ-výrazu 2 volné symboly – všechny ostatní symboly v těle λ-výrazu
Příklad (lambda (x y nepouzity) (* (+ 1 x) y))
nemají výskyt v těle: nepouzity vázané: x, y volné: +, * volné a vázané symboly – různé role konzistentní přejmenování vázaných symbolů nemění význam λ-výrazu V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
8 / 43
Zjednodušený model aplikace procedur Definice (aplikace uživatelsky definovaných procedur) Při aplikaci procedury vzniklé vyhodnocením λ-výrazu (lambda (hparam1 i hparam2 i · · · hparamn i) htěloi)
dojde k vytvoření lokálního prostředí, ve kterém: na symboly formálních argumentů hparam1 i, . . . , hparamn i jsou navázány hodnoty, se kterými je procedura aplikována požadavek: stejný počet argumentů a formálních argumentů v lokálním prostředí je vyhodnoceno htěloi procedury během vyhodnocení těla procedury se hledají vazby symbolů následovně: vazby vázaných symbolů se hledají v lokálním prostředí, vazby volných symbolů se hledají v počátečním prostředí.
výsledek aplikace procedury = hodnota vzniklá jako výsledek vyhodnocení těla V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
9 / 43
Příklad (Příklady uživatelsky definovaných procedur) (define (define (define (define . . .
na3 na4 na5 na6
(lambda (lambda (lambda (lambda
(x) (x) (x) (x)
(* x (na2 x)))) (na2 (na2 x)))) (* (na2 x) (na3 x)))) (na2 (na3 x))))
(define abs (lambda (x) (if (>= x 0) x (- x))))
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
10 / 43
Příklad (Identita) ((lambda (x) x) 20)
Z=⇒
20
(define id (lambda (x) x)) (id (* 2 20)) (id (+ 1 (id 20))) (id #f) ((id -) 10 20)
V. Vychodil (KI, UP Olomouc)
Z=⇒ Z=⇒ Z=⇒ Z=⇒
40 21 #f -10
Vytváření abstrakcí pomocí procedur
Přednáška 2
11 / 43
Příklad (Projekce) (lambda (x y z) x) (lambda (x y z) y) (lambda (x y z) z)
Z=⇒ Z=⇒ Z=⇒
první projekce druhá projekce třetí projekce
(define 1-z-3 (lambda (x y z) x)) (define 2-z-3 (lambda (x y z) y)) (define 3-z-3 (lambda (x y z) z)) (1-z-3 10 20 30) (2-z-3 10 (+ 1 (3-z-3 2 4 6)) 20) ((3-z-3 #f - +) 13) ((2-z-3 1-z-3 2-z-3 3-z-3) 10 20 30)
V. Vychodil (KI, UP Olomouc)
Z=⇒ Z=⇒ Z=⇒ Z=⇒
Vytváření abstrakcí pomocí procedur
10 7 13 20
Přednáška 2
12 / 43
Příklad (Konstantní procedury a procedury bez argumentu) (lambda (x) 10) (lambda (x) #f) (lambda (x) +) . . .
Z=⇒ Z=⇒ Z=⇒
procedura „vrať číslo 10ÿ procedura: „vrať pravdivostní hodnotu #fÿ procedura: „vrať hodnotu navázanou na symbol +ÿ
(define c (lambda (x) 10)) (+ 1 (c 20)) (((lambda (x) -) 10) 20 30)
Z=⇒ Z=⇒
11 -10
(define const-proc (lambda (x) 10)) (define noarg-proc (lambda () 10)) (const-proc 20) (noarg-proc)
V. Vychodil (KI, UP Olomouc)
Z=⇒ Z=⇒
10 10
Vytváření abstrakcí pomocí procedur
Přednáška 2
13 / 43
Nutné rozšíření (abstraktního) interpretu Scheme Aplikace uživatelsky definovaných procedur vyžaduje: 1
obecný pojem prostředí prostředí již není jen jedno (globální / počáteční) každé aplikace vyžaduje lokální prostředí pro uchování hodnot argumentů
2
rozšíření Eval předchozí chápání vyhodnocování nestačí (vyhodnocení symbolu je problém) vyhodnocování elementů musí být definováno relativně vzhledem k prostředí
3
přesný popis sémantiky speciální formy lambda z čeho se skládá procedura vzniklá vyhodnocením λ-výrazu
4
popis Apply pro uživatelsky definované procedury jak probíhá aplikace uživatelsky definované procedury V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
14 / 43
Prostředí a jejich hierarchie Definice (prostředí) Prostředí P obsahuje: tabulka vazeb mezi symboly a elementy (jako doposud), ukazatel na svého předka (ukazatel na jiné prostředí). Výjimka: globální (počíteční) prostředí – nemá předka (pouze tabulka vazeb).
Značení P1 ≺ P2 znamená: P1 je předkem prostředí P2 (také: P1 je nadřazeno P2 ) s 7→P E znamená: na symbol s je v prostředí P navázán element E (také: E je aktuální vazba symbolu s v prostředí P) zkrácené značení: s 7→ E pokud je P patrné z kontextu V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
15 / 43
Definice (vyhodnocení elementu E v prostředí P) Výsledek vyhodnocení elementu E v prostředí P, značeno Eval[E, P], je definován: (A) Pokud je E číslo, pak Eval[E, P] := E. (B) Pokud je E symbol, mohou nastat tři situace: (B.1) Pokud E 7→P F , pak Eval[E, P] := F . (B.2) Pokud E nemá vazbu v P a pokud P 0 ≺ P, pak Eval[E, P] := Eval[E, P 0 ]. (B.e) Pokud E nemá vazbu v P a pokud P = PG , pak „CHYBA: E nemá vazbuÿ.
(C) Pokud je E ve tvaru (E1 E2 · · · En ), pak F1 := Eval[E1 , P] a rozlišujeme: (C.1) Pokud F1 je procedura, pak pro F2 := Eval[E2 , P], . . . , Fn := Eval[En , P] položíme Eval[E, P] := Apply[F1 , F2 , . . . , Fn ]. (C.2) Pokud F1 je speciální forma, pak Eval[E, P] := Apply[F1 , E2 , . . . , En ]. (C.e) Pokud F1 není procedura ani speciální forma: „CHYBA: Nelze provést aplikaci: první prvek seznamu E se nevyhodnotil na proceduru ani na speciální formu.ÿ.
(D) Ve všech ostatních případech klademe Eval[E, P] := E. V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
16 / 43
Anatomie uživatelsky definovaných procedur Co jsou uživatelsky definované proedury: elementy jazyka Scheme, nemají čitelnou reprezentaci, skládají se z několika složek (komponent), které jsou potřeba pro jejich aplikaci.
Definice (uživatelsky definovaná procedura) Každá trojice ve tvaru hhparametryi, htěloi, Pi, kde hparametryi je seznam formálních argumentů, htěloi je libovolný element, P je prostředí, se nazývá uživatelsky definovaná procedura. V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
17 / 43
Sémantika speciální formy lambda Definice (speciální forma lambda) Při aplikaci speciální formy lambda vyvolané vyhodnocením λ-výrazu (lambda (hparam1 i hparam2 i · · · hparamn i) htěloi)
v prostředí P vznikne procedura h(hparam1 i hparam2 i · · · hparamn i), htěloi, Pi . Poznámky: při aplikaci speciální formy lambda se nic nevyhodnocuje (!!) vytvoření nové procedury je „levná záležitostÿ procedura: parametry, tělo, prostředí vzniku (prostředí aplikace lambda) lambda je „překvapivě jednoducháÿ Aktuální prostředí = prostředí, v němž byla vyvolána aplikace speciální formy V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
18 / 43
Definice (aplikace procedury) Mějme dánu proceduru E a nechť E1 , . . . , En jsou libovolné elementy jazyka. Aplikace procedury E na argumenty E1 , . . . , En (v tomto pořadí), značená Apply[E, E1 , . . . , En ] je definována následovně: Pokud je E primitivní procedura, . . . Pokud je E uživatelsky definovaná procedura ve tvaru h(hparam1 i · · · hparamm i), htěloi, Pi, pak: 1
Pokud se m 6= n, pak „CHYBA: Chybný počet argumentůÿ.
2
Vytvoří se nové prázdné prostředí Pl , které nazýváme lokální prostředí procedury.
3
Nastavíme předka prostředí Pl na hodnotu P.
4
V prostředí Pl se zavedou vazby hparami i 7→ Ei pro i = 1, . . . , n.
5
Položíme Apply[E, E1 , . . . , En ] := Eval[htěloi, Pl ].
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
19 / 43
Příklad (Výpočet délky přepony) (define na2 (lambda (x) (* x x))) (define soucet-ctvercu (lambda (a b) (+ (na2 a) (na2 b)))) (define prepona (lambda (odvesna-a odvesna-b) (sqrt (soucet-ctvercu odvesna-a odvesna-b)))) (prepona 3 4)
Z=⇒
V. Vychodil (KI, UP Olomouc)
5 (jak vypadají prostředí)
Vytváření abstrakcí pomocí procedur
Přednáška 2
20 / 43
Procedury vyšších řádů Pojmenované / anonymní procedury ve většině PJ vznikají procedury jako pojmenované (mají vždy jméno), ve Scheme vznikají jako anonymní (bezejmenné). Procedury vyšších řádů (pojem pochází z matematické logiky) procedury, kterým předáváme jiné procedury jako argumenty procedury, které vracejí jiné procedury jako výsledky aplikace Poznámka (nikoli okrajová): ve vetšině programocích jazyků jsou procedury vyšších řádů „černá magieÿ ve Scheme (a jiných funkcionálních jazycích) jsou „zadarmoÿ – všechny procedury ve Scheme jsou de facto procedury vyšších řádů
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
21 / 43
Příklad (Procedury jako argumenty) (define infix (lambda (x operace y) (operace x y))) (infix (infix (infix (infix
10 10 10 10
+ 20) - (infix 2 + 5)) (lambda (x y) x) 20) (lambda (x y) 66) 20)
(infix 10 (lambda (x) 66) 20) (infix 10 20 30)
V. Vychodil (KI, UP Olomouc)
Z=⇒ Z ⇒ = Z=⇒ Z=⇒ Z=⇒ Z=⇒
30 3 10 66
CHYBA! CHYBA!
Vytváření abstrakcí pomocí procedur
Přednáška 2
22 / 43
Příklad (Procedury jako návratové hodnoty) (define curry+ (lambda (c) (lambda (x) (+ x c)))) (define f (curry+ 10)) f (f 20)
Z=⇒ Z=⇒
#
30 (jak vypadají prostředí)
role symbolů: v těle f je x vázaný a c volný obecný princip rozkladu zvaný „curryingÿ (H. Curry) lze aplikovat na procedury jiné než + analogicky pro tři a více argumentů V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
23 / 43
Procedury (ve Scheme) × funkce (matematické) Procedury ve Scheme (speciální elementy jazyka) mají vstupní argumenty, po aplikaci produkují výstupní hodnoty Matematické funkce (zobrazení, více v kursu Úvod do informatiky) zobrazení z množin A1 , . . . , An do množiny B je relace f ⊆ A1 × · · · × An × B, pro kterou platí: pro každé a1 ∈ A1 , . . . , an ∈ An existuje právě jedno b ∈ B tak, že ha1 , . . . , an , bi ∈ f . označujeme f : A1 × · · · × An → B f (a1 , . . . , an ) = b místo ha1 , . . . , an , bi ∈ f Různé pojmy: některé procedury se nechovají jako zobrazení, některá zobrazení mohou být reprezentována procedurami, některá zobrazení nemohou být reprezentována procedurami. V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
24 / 43
Příklad (Procedury, které se nechovají jako matematické funkce) Nekončící série aplikací: (define f (lambda (x) (x x)) (f f) Z=⇒ · · ·
Aplikace procedury vracející pro stejné argumenty různé hodnoty: (random (random (random (random . . .
5) 5) 5) 5)
Z ⇒ = Z=⇒ Z=⇒ Z=⇒
3 2 1 3
(define f (lambda (x) (random 5))) (f 10) Z=⇒ 2 (f 10) Z=⇒ 3 . . . V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
25 / 43
Matematické funkce reprezentovatelné procedurami Příklad Funkce f : R → R dané předpisy x+1 , f (x) = |x|, . . . 2 lze reprezentovat procedurami vzniklými vyhodnocením: f (x) = x2 , f (x) =
(lambda (x) (* x x)) (lambda (x) (/ (+ x 1) 2)) (lambda (x) (if (>= x 0) x (- x))) . . .
V informatice (a matematice) běžná praxe: funkce (procedury) se vyjadřují pomocí jiných funkcí (procedur) (např. posunutím, škálováním, . . . ) funkce (procedury) lze skládat, . . . V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
26 / 43
Funkce vzniklé posunem f po osách x a y Definice (Funkce vzniklé posunutím) Mějme funkci f : R → R. Pak pro každé k ∈ R, zavedeme funkci fX,k : R → R a fY,k : R → R tak, že položíme fX,k (x) = f (x − k), x2
4
fY,k (x) = f (x) + k. 4
3
3
2
2
1
1 1
V. Vychodil (KI, UP Olomouc)
2
3
4
x2 + 1
1
Vytváření abstrakcí pomocí procedur
(x − 1)2
x2
2
3
4 Přednáška 2
27 / 43
Příklad (Vyjádření ve Scheme) (define x-shift (lambda (f k) (lambda (x) (f (- x k))))) (define y-shift (lambda (f k) (lambda (x) (+ k (f x))))) (x-shift na2 1) (y-shift na2 1) ((x-shift na2 1) 1) ((x-shift na2 1) 2)
V. Vychodil (KI, UP Olomouc)
Z=⇒ Z=⇒ Z=⇒ Z=⇒
„druhá mocnina posunutá o 1 na ose xÿ „druhá mocnina posunutá o 1 na ose yÿ 0 1
Vytváření abstrakcí pomocí procedur
Přednáška 2
28 / 43
Příklad (Procedura generující polynomické funkce) Funkce f : R → R daná
Odpovídající procedura: (define make-poly-f (lambda (a n) (lambda (x) (* a (expt x n)))))
f (x) = a · xn , kde a ∈ R a n ∈ R.
4 (make-poly-f (make-poly-f (make-poly-f (make-poly-f (make-poly-f
3.5 1) 1 2) 1 1) 1 1/2) 1 0)
Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒
f (x) = 3.5x f (x) = x2 f (x) = √ x f (x) = x f (x) = 1
3 √
2 1
Vytváření abstrakcí pomocí procedur
x
1 1
V. Vychodil (KI, UP Olomouc)
x
x2
3.5x
2
3
4 Přednáška 2
29 / 43
Příklad (Složení dvou funkcí / procedur) Mějme funkce f : X → Y a g : Y → Z. Pak složenou funkcí (f ◦ g) : X → Z nazveme funkci, jejíž hodnota je definovaná předpisem (f ◦ g)(x) = g f (x) pro každé x ∈ X. Vlastnosti operace skládání: f ◦ (g ◦ h) = (f ◦ g) ◦ h, ι ◦ f = f ◦ ι = f,
asociativita, neutralita vzhledem k ι(x) = x.
Ve Scheme: (define compose2 (lambda (f g) (lambda (x) (g (f x))))) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
30 / 43
Příklad (Skládání procedur – příklady) (define (define (define (define
f na2) g (make-poly-f 1/2 1)) f*g (compose2 f g)) g*f (compose2 g f))
f
4
f ◦g g◦f
3 f*g
g
2 1
g*f
1
2
V. Vychodil (KI, UP Olomouc)
3
Z=⇒ Z=⇒
(f ◦ g)(x) =
1 2 ·x 2
2 x (g ◦ f )(x) = 2
4 Vytváření abstrakcí pomocí procedur
Přednáška 2
31 / 43
Funkcionální přístup Výhodné: chápat procedury jako funkce snadné ladění (debugging / odbroukování) výsledky aplikace závisejí pouze na argumentech procedur (idealizace; pozor na symboly, které se vyskytují jako volné!)
Definice (element prvního řádu) Element prvního řádu je každý element jazyka, pro který platí: 1 element může být pojmenován, 2 element může být předán proceduře jako argument, 3 element může vzniknout aplikací (voláním) procedury, 4 element může být obsažen v hierarchických datových strukturách. Kouzlo Scheme: vše je (může být) element prvního řádu. (!!) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
32 / 43
Lexikální a dynamický rozsah platnosti Lexikální rozsah platnosti (symbolů / proměnných) vazby symbolů v těle procedury, jejichž vazby nejsou nalezeny v lokálním prostředí se hledají v prostředí vzniku procedury používá: většina programovacích jazyků včetně Scheme, C, Pascal, . . . plusy: strukturu prostředí lze vyčíst z programu někdy se nazývá: statický rozsah platnosti Dynamický rozsah platnosti (symbolů / proměnných) vazby symbolů v těle procedury, jejichž vazby nejsou nalezeny v lokálním prostředí se hledají v prostředí aplikace procedury používá: prakticky nikdo (FoxPro) minusy: vazby symbolů lze vyčíst až za běhu programu / obtížné ladění
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
33 / 43
Příklad (Statický vs. dynamický rozsah platnosti) (define curry+ (lambda (c) (lambda (x) (+ x c)))) (define c 100) (define f (curry+ 10)) (f 20) ((lambda (c) (f 20)) 1000)
V. Vychodil (KI, UP Olomouc)
Z=⇒
???
Z=⇒
???
Vytváření abstrakcí pomocí procedur
Přednáška 2
34 / 43
Scheme: negace pravdivostních hodnot Příklad (negace zobecněných pravdivostních hodnot) (not (not (not (not (not (not (not
#t) #f) 0) -12.5) (lambda (x) (+ x 1))) (<= 1 2)) (> 1 3))
Z=⇒ Z ⇒ = Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒
#f #t #f #f #f #f #t
Procedura not je definovatelná: (define not (lambda (x) (if x #f #t))) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
35 / 43
Scheme: vytváření podmínek pomocí konjunkce Příklad (konjunkce zobecněných pravdivostních hodnot) (and (= 0 0) (odd? 1) (even? 2)) (and (= 0 0) (odd? 1) (even? 2) 666) (and 1 #t 3 #t 4) (and 10) (and +) (and) (and (= 0 0) (odd? 2) (even? 2)) (and 1 2 #f 3 4 5)
Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒
#t 666 4 10
„procedura sčítáníÿ #t #f #f
Pozor: and ve Scheme je speciální forma (!!)
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
36 / 43
Definovatelnost and pomocí if (and htest1 i · · · htestn i)
lze nahradit vnořenými if-výrazy: (if htest1 i (if htest2 i (if · · · (if htestn−1 i
htestn i #f) . . . #f) #f) #f) V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
37 / 43
Scheme: vytváření podmínek pomocí disjunkce Příklad (konjunkce zobecněných pravdivostních hodnot) (or (even? 1) (= 1 2) (odd? 1)) (or (= 1 2) (= 3 4) 666) (or 1 #f 2 #f 3 4) (or (+ 10 20)) (or) (or #f) (or #f (= 1 2) #f)
Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒ Z=⇒
#t 666 1 30 #f #f #f
Pozor: or ve Scheme je speciální forma (!!)
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
38 / 43
Definovatelnost or pomocí if (or htest1 i · · · htestn i)
lze (zatím bez újmy) nahradit vnořenými if-výrazy: (if htest1 i
htest1 i (if htest2 i htest2 i (if · · · (if htestn i
htestn i #f) · · · )))
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
39 / 43
Příklad (příklady použití and a or) (define within? (lambda (x a b) (and (>= x a) (<= x b)))) (define overlap? (lambda (a b c (or (within? (within? (within? (within?
V. Vychodil (KI, UP Olomouc)
d) a c b c c a d a
d) d) b) b))))
Vytváření abstrakcí pomocí procedur
Přednáška 2
40 / 43
Definice (Speciální forma cond) Speciální forma cond se používá ve tvaru: (cond (htest1 i hdůsledek1 i) (htest2 i hdůsledek2 i) . . . (htestn i hdůsledekn i) (else hnáhradníki)), kde n ≥ 0 a náhradník je nepovinný
Aplikace cond probíhá: cond vyhodnocuje (v aktuálním prostředí) výrazy htest1 i, . . . , htestn i do toho okamžiku, až narazí na první htesti i, který se vyhodnotil na pravdu vyhodnocování dalších htesti+1 i, . . . , htestn i se neprovádí a výsledkem je hodnota vzniklá vyhodnocením výrazu hdůsledeki i v aktuálním prostředí jinak: vyhodnotí se hnáhradníki nebo je hodnota nedfinovaná V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
41 / 43
Příklad (Použití speciální formy cond) Funkce signum: −1 pokud x < 0, pokud x = 0, sgn x = 0 1 pokud x > 0. Implementace ve Scheme: (define sgn (lambda (x) (cond ((= x 0) 0) ((> x 0) 1) (else -1))))
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
42 / 43
Vztah cond a if
(if htest1 i (cond (htest1 i hdůsledek1 i) (htest2 i hdůsledek2 i) . . .
Z=⇒
(htestn i hdůsledekn i) (else hnáhradníki))
hdůsledek1 i (if htest2 i hdůsledek2 i (if · · · (if htestn i hdůsledekn i hnáhradníki) · · · )))
if pomocí cond ještě jednodušší . . .
V. Vychodil (KI, UP Olomouc)
Vytváření abstrakcí pomocí procedur
Přednáška 2
43 / 43