Obsah
1. Vytváření nových uživatelských funkcí
2. Pojmenování uživatelských funkcí
4. Anonymní funkce s proměnným počtem parametrů
5. Pojmenované funkce s proměnným počtem parametrů
7. Programová smyčka typu „do“
1. Vytváření nových uživatelských funkcí
V předchozí části seriálu o historii výpočetní techniky jsme si popsali některé základní programové konstrukce, ze kterých se skládají prakticky všechny programy napsané v programovacím jazyku Scheme. Ovšem pro tvorbu skutečných programů, nejenom jednoduchých demonstračních příkladů, je zapotřebí znát i některé další užitečné konstrukce. Naprostým základem při tvorbě každé jen trošku rozsáhlejší aplikace je dekompozice problému na menší části, které je možné realizovat snadněji, protože se výchozí problém více konkretizuje (a přibližuje se tak jak možnostem programovacího jazyka, tak i schopnosti vývojáře problém naprogramovat). V programovacím jazyku Scheme se, podobně jako v mnoha dalších imperativních a především funkcionálních programovacích jazycích, pro rozklad problému na menší části používají uživatelsky definované funkce, a to jak funkce pojmenované, tak i funkce anonymní (tento typ funkcí je představován lambda výrazy).
V této kapitole si popíšeme způsob tvorby pojmenovaných funkcí a v kapitole následující se budeme zabývat problémem tvorby funkcí anonymních, s čímž souvisí i problematika vytvoření a následného použití lokálních proměnných. Možná by na tomto místě bylo vhodné připomenout, že z čistě teoretického hlediska by se měly anonymní funkce popsat dříve než funkce pojmenované, protože právě anonymní funkce tvoří základ pro vytváření jak funkcí pojmenovaných, tak i lokálních proměnných (a mnoha dalších užitečných jazykových konstrukcí). Vytvoření uživatelské pojmenované funkce je v programovacím jazyku Scheme velmi jednoduché – použije se speciální forma define, za níž se do seznamu zapíše jméno nově vytvářené funkce i jména jejích formálních parametrů. Za tímto seznamem následuje tělo funkce, tj. výraz či sekvence výrazů, které se mají vyhodnotit (v těchto výrazech je samozřejmě možné používat formální parametry funkce).
Hodnota posledního vyhodnoceného výrazu se stává i návratovou hodnotou celé funkce, což mj. znamená, že všechny předchozí výrazy musí mít vedlejší efekt, jinak je jejich volání (použití v těle funkce) vlastně zbytečné. Formálně vypadá vytvoření nové funkce následovně:
(define ([jméno funkce] [formální parametry]) [tělo funkce])
Postup vytvoření uživatelské funkce s jedním parametrem a jejího následného použití:
(define (square x) (* x x)) (square 42) 1764 (square (+ 1 2)) 9 (+ (square 3) (square 4)) 25
Samozřejmě je možné vytvořit i funkci víceparametrickou:
(define (kvadratic a b c x) (+ (* a x x) (* b x) c)) (kvadratic 1 0 0 1) 1 (kvadratic 2 2 2 4) 42
2. Pojmenování uživatelských funkcí
V programovacím jazyku Scheme lze vytvářet i funkce, v jejichž názvu se nachází různé nealfanumerické znaky. Je to ostatně logické, protože se jedná o jeden z jazyků, v nichž neexistují ani operátory (zapisované většinou právě pomocí nealfanumerických znaků) ani většina dalších speciálních syntaktických konstrukcí. V předchozí části tohoto seriálu jsme si již ukázali některé predikáty, u nichž je obvyklé, že jsou jejich jména ukončena znakem otazník (?). Také jsme se seznámili s konverzními funkcemi používajícími ve svém názvu dvojici znaků ->. Mnohdy se také můžeme setkat s tím, že se jméno uživatelské funkce skládá z více slov oddělených pomlčkou (-), která je v jiných programovacích jazycích většinou rezervována pro zápis operátoru rozdílu popř. změny znaménka. V následujících příkladech je ukázáno, že jména uživatelských funkcí mohou opravdu obsahovat téměř jakýkoli nealfanumerický znak (výjimek je pouze několik, vypsány jsou například v R5RS):
(define (>= x y)
(or (> x y) (= x y))
)
; druhá možná definice
(define (>= x y)
(not (< x y))
)
První přiblížení k tomu, jak by se mohl zapsat ternární výraz. Tento příklad však má jeden poměrně závažný nedostatek vyplývající z vlastnosti jazyka Scheme. Dokážete přijít na to, o jaký nedostatek se jedná?
(define (?: podminka prvni-vyraz druhy-vyraz)
(if podminka prvni-vyraz druhy-vyraz)
)
; test
(?: #t 1 2)
1
(?: #f 1 2)
2
; Při tisku jednotlivých slov lze namísto
; řetězců použít i symboly
(?: (< 1 2) 'mensi 'vetsi)
mensi
(?: (< 2 1) 'mensi 'vetsi)
vetsi
Programátoři v Basicu pravděpodobně znají operátor <> (nerovnost), který lze ve Scheme velmi jednoduše vytvořit jako uživatelskou funkci:
(define (<> x y)
(not (= x y))
)
(<> 1 2)
#t
(<> 1 1)
#f
Ovšem výše uvedenou funkci můžeme též zobecnit na libovolný typ parametrů:
(define (<> a b)
(not (equal? a b))
)
(<> 'a 'b)
#t
(<> "hello" "world")
#t
(<> "hello" "hello")
#f
3. Anonymní funkce
Kromě pojmenovaných funkcí popsaných v předchozích dvou kapitolách je možné v programovacím jazyce Scheme, podobně jako v LISPu, ale i mnoha dalších jazycích umožňujících funkcionální programování, vytvářet a používat takzvané funkce anonymní. Tyto funkce, které je možné s výhodou využít například při zápisu iterací nad prvky seznamů či při omezování oblasti platnosti proměnných, se vytváří pomocí speciální formy lambda, jejíž název je odvozen ze slavné Churchovy teorie Lambda kalkulu, která má poměrně velký význam jak v teoretické informatice, tak i v dalších odvětvích informatiky (viz též odkazy uvedené v poslední kapitole). Samotný zápis anonymní funkce se příliš neliší od zápisu funkce pojmenované – jediný syntaktický rozdíl spočívá v tom, že se při zápisu speciální formy lambda nikde neuvádí jméno funkce, pouze seznam (jména) formálních parametrů, za nimiž následuje tělo funkce:
(lambda ([formální parametry]) [tělo anonymní funkce])
Zápis i volání anonymních funkcí si můžeme ihned vyzkoušet:
; pouze vytvoření anonymní funkce bez ; jejího dalšího použití (umělý příklad, který ; nemá větší význam, protože se anonymní funkce ; nikde nevolá) (lambda (x) (* x x)) #<procedure #f (x)> ; vytvoření anonymní funkce s jejím následným ; zavoláním s parametrem 42 ((lambda (x) (* x x)) 42) 1764 ; anonymní funkce s více parametry (lambda (a b c) (+ a b c)) #<procedure #f (a b c)> ((lambda (a b c) (+ a b c)) 1 2 3) 6
Mezi funkcemi pojmenovanými a anonymními existuje velmi úzká vazba, kterou si můžeme vysvětlit na jednoduchém příkladu. Mějme uživatelskou funkci nazvanou plus, která sečte své dva parametry (pro jednoduchost považujme tyto parametry vždy za čísla) a vrátí součet hodnot obou parametrů. Definice takové funkce je velmi jednoduchá:
(define (plus x y) (+ x y)) ; test (plus 1 2) 3
Výše uvedený zápis je ekvivalentní s následujícím zápisem, ve kterém se vytváří proměnná nazvaná plus, která jako svoji hodnotu obsahuje (anonymní) funkci. Již v úvodním článku o programovacím jazyku Scheme jsme si řekli, že funkce lze používat na stejných místech jako hodnoty jiných typů, takže je tento zápis korektní:
(define plus (lambda (x y) (+ x y))) ; test (plus 1 2) 3
4. Anonymní funkce s proměnným počtem parametrů
Kromě anonymních funkcí, v nichž jsou explicitně vyjmenovány všechny jejich parametry, lze v programovacím jazyku Scheme vytvářet a následně i volat funkce s proměnným počtem parametrů, což může být v některých případech velmi užitečné. V nejjednodušším případě, pokud mají být všechny parametry proměnné (tj. ve skutečnosti se anonymní funkce nemusí volat s parametrem žádným) se používá následující způsob vytvoření anonymní funkce:
(lambda [jméno jediného formálního parametru] [tělo anonymní funkce])
To tedy znamená, že mezi následujícími dvěma výrazy je poměrně velký rozdíl:
(lambda (x) ...) (lambda x ...)
Při volání této anonymní funkce se do formálního parametru předá seznam obsahující všechny skutečně předávané parametry. S tímto seznamem je možné pracovat jako s kterýmkoli jiným seznamem, tj. například lze procházet přes jeho prvky atd:
; jeden ze způsobů vytvoření seznamu ((lambda x x) 1 2 3 4) (1 2 3 4) ; součet hodnot všech předaných parametrů ; (apply bude popsána dále) ((lambda x (apply + x)) 1 2 3 4) ; na parametr (seznam) lze aplikovat různé funkce ((lambda x (length x)) 'a 'b 'c 'd) 4
Ve Scheme lze též použít kombinaci obou předchozích způsobů, tj. vytvoření anonymní funkce vyžadující pevný počet povinných parametrů s tím, že všechny ostatní hodnoty předané anonymní funkci jsou nepovinné. Všechny nepovinné hodnoty jsou při volání anonymní funkce uloženy do seznamu přiřazeného poslednímu parametru, přičemž tento parametr musí být při definici anonymní funkce od ostatních parametrů oddělen tečkou. Povšimněte si, že se v tomto případě nejedná o nějakou speciální syntaxi, kterou bylo nutné do jazyka zavést, ale pouze o využití již existujících možností Scheme, které podporuje, podobně jako LISP, explicitní zápis tečka-dvojic:
(lambda ([formální parametry].poslední parametr) [tělo anonymní funkce])
Následují příklady použití anonymní funkce s několika povinnými (pojmenovanými) parametry a možností předání dalších hodnot v seznamu předanému poslednímu parametru. Ve všech příkladech se v těle anonymní funkce pouze vytiskne obsah posledního „seznamového“ parametru:
((lambda (a . b) b) 1 2 3 4) (2 3 4) ((lambda (a b . c) c) 1 2 3 4) (3 4) ((lambda (a b c . d) d) 1 2 3 4) (4) ((lambda (a b c d . e) e) 1 2 3 4) ()
5. Pojmenované funkce s proměnným počtem parametrů
Vzhledem k tomu, že speciální formu define lze kdykoli zapsat pomocí speciální formy lambda, je ve Scheme možné nadefinovat pojmenovanou funkci akceptující proměnný (tj. v krajním případě i nulový) počet parametrů, z nichž je při volání funkce automaticky vytvořen seznam, se kterým je možné v těle funkce libovolným způsobem manipulovat. Syntakticky vypadá definice takové funkce následovně:
(define (jméno funkce . parametr) [tělo funkce])
Což je ekvivalentní zápisu:
(define jméno funkce (lambda parametr [tělo funkce]))
Příklad použití:
; funkce vracející počet skutečně předaných parametrů (define (foo . parametry) (length parametry)) (foo 1 2 3 4) 4 ; alternativní forma zápisu (define foo (lambda parametry (length parametry))) ; volání funkce se třemi parametry (zde se jedná o trojici symbolů) (foo 'a 'b 'c) 3 ; volání funkce bez parametrů (foo) 0
6. Rekurze
V úvodní části našeho povídání o programovacím jazyku Scheme jsme si mj. řekli, že iteraci, tj. opakování části kódu (většinou s různými parametry), lze vyjádřit buď pomocí rekurze nebo s využitím explicitně či implicitně zapsaných programových smyček. Použití rekurze je doporučovaná možnost, protože se nejvíce blíží funkcionálnímu stylu programování a v mnoha případech taktéž vychází rekurzivní zápis přímo z algoritmu, který se v jazyce Scheme implementuje. Následuje příklad několika jednoduchých funkcí zapsaných rekurzivně. Povšimněte si především toho, že se v těchto rekurzivních funkcích nevyskytují žádné pomocné lokální proměnné, jejichž použití bychom se nemohli vyhnout v případě zápisu obdobných výpočtů v nerekurzivní podobě:
; rekurzivní zápis výpočtu faktoriálu
(define (factorial n)
(if (<= n 1)
1
(* n (factorial (- n 1)))
)
)
; rekurzivní výpočet Fibonacciho posloupnosti
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))
)
)
; rekurzivní výpočet Ackermannovy funkce
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))
)
)
Pokud máte možnost některou konstrukci napsat pomocí rekurze nebo programové smyčky, pro co se rozhodujete častěji?
7. Programová smyčka typu „do“
Ovšem v některých případech může být vhodnější nahradit rekurzivní zápis algoritmu zápisem, v němž jsou použity programové smyčky. Pro tyto účely obsahuje jazyk Scheme universální smyčku představovanou speciální formou do. Tuto programovou smyčku lze použít například pro tvorbu cyklu, v němž se postupně mění hodnota řídicí proměnné (či řídicích proměnných), cyklu procházejícího přes prvky seznamu či cyklu, v němž se postupně načítají a zpracovávají data uložená v externím souboru. Při zápisu formy do je možné specifikovat seznam lokálních proměnných platných v těle smyčky (tyto proměnné mohou být použity například jako počitadla), výraz, pomocí kterého se hodnota těchto proměnných změní na konci těla smyčky, podmínka pro ukončení smyčky a samozřejmě též tělo smyčky, tj. příkazy prováděné v každé iteraci. Následuje jednoduchý příklad použití speciální formy do, pomocí něhož je vytvořena klasická počítaná smyčka:
(do ((i 1 (+ i 1))) ; počáteční hodnota počitadla a iterační výraz provedený na konci smyčky
((= i 10)) ; podmínka vyhodnocovaná pro ukončení smyčky
(display i) ; tělo smyčky
(newline)
)
1
2
3
4
5
6
7
8
9
Při zápisu speciální formy do lze vytvořit i větší množství lokálních proměnných platných v rámci těla smyčky, viz následující příklad s trojicí proměnných, z nichž každá se na konci smyčky (před začátkem další iterace) modifikuje na základě vyhodnocení různých výrazů:
(do (
(x 1 (* x 2)) ; počáteční hodnota proměnné a iterační výraz provedený na konci smyčky
(y 1000 (- y 1)) ; dtto
(z 0 (* x y)) ; dtto
)
((< y x)) ; podmínka vyhodnocovaná pro ukončení smyčky
(display (list x y z)) ; tělo smyčky
(newline)
)
(1 1000 0)
(2 999 1000)
(4 998 1998)
(8 997 3992)
(16 996 7976)
(32 995 15936)
(64 994 31840)
(128 993 63616)
(256 992 127104)
(512 991 253952)
V dalším příkladu je ukázáno postupné zpracování prvků uložených v seznamu (ovšem tento příklad by ve skutečnosti bylo možné napsat mnohem lépe a jednodušeji):
(do ((x '(1 2 3 4 5 6) (cdr x))) ; počáteční hodnota proměnné a iterační výraz provedený na konci smyčky
((null? x)) ; podmínka vyhodnocovaná pro ukončení smyčky
(display (car x)) ; tělo smyčky
(newline)
)
1
2
3
4
5
6
Následuje poněkud složitější příklad, ve kterém je ukázáno použití vnořených počítaných smyček při výpočtu podílu všech kombinací dvou celých čísel ležících v rozsahu 1 až 10 (připomeňme, že výsledkem podílu dvou celých čísel je ve Scheme hodnota typu rational tj. racionální číslo). Na tomto příkladu je patrné, že pro zápis složitějších programových struktur je vhodné používat pomocné funkce, což je ostatně zásada, kterou je vhodné dodržovat i v dalších programovacích jazycích:
(do ((y 1 (+ y 1))) ; počáteční hodnota počitadla a iterační příkaz
((> y 10)) ; podmínka pro ukončení smyčky
(do ((x 1 (+ x 1))) ; vnitřní smyčka
((> x 10)) ; podmínka pro ukončení vnitřní smyčky
(display (/ x y)) ; tisk výsledku
(display "\t") ; přechod na další tabelační zarážku
)
(newline) ; přechod na další řádek
)
1 2 3 4 5 6 7 8 9 10
1/2 1 3/2 2 5/2 3 7/2 4 9/2 5
1/3 2/3 1 4/3 5/3 2 7/3 8/3 3 10/3
1/4 1/2 3/4 1 5/4 3/2 7/4 2 9/4 5/2
1/5 2/5 3/5 4/5 1 6/5 7/5 8/5 9/5 2
1/6 1/3 1/2 2/3 5/6 1 7/6 4/3 3/2 5/3
1/7 2/7 3/7 4/7 5/7 6/7 1 8/7 9/7 10/7
1/8 1/4 3/8 1/2 5/8 3/4 7/8 1 9/8 5/4
1/9 2/9 1/3 4/9 5/9 2/3 7/9 8/9 1 10/9
1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10 1
8. Makro „while“
V některých případech může být použití speciální formy do zbytečně komplikované, především proto, že se při zápisu této formy používá velké množství závorek, které mohou být pro čtenáře programů poněkud matoucí (například pro ty uživatele, pro něž není jazyk Scheme „rodným programovacím jazykem“). V dialektu jazyka Scheme nazvaného Guile (s poměrně velkou pravděpodobností ho máte ve svém Linuxu nainstalovaný) se však mj. nachází i poměrně užitečné makro nazvané while, které se ze syntaktického (způsob zápisu) i sémantického (význam zápisu) hlediska podobá klasickým smyčkám while známým z mnoha imperativních programovacích jazyků. Toto makro lze použít velmi jednoduše – za jeho jméno postačuje zapsat podmínku vyhodnocovanou na začátku provádění každé iterace (podmínka je samozřejmě zapsána formou výrazu), za níž následuje tělo smyčky:
(define i 0) ; pomocná (globální) proměnná - počitadlo
(while (< i 10) ; podmínka pro ukončení provádění smyčky
(display i) ; tělo smyčky
(newline)
(set! i (+ i 1)) ; zvýšení hodnoty globální proměnné
) ; (použití nového define by zde vedlo k navázání nové proměnné)
0
1
2
3
4
5
6
7
8
9
Výpočet tabulky podílů dvou celých čísel, který jsme si již ukázali v předchozí kapitole, lze s využitím makra while napsat následovně:
(define x 1) ; řídicí proměnné obou smyček
(define y 1) ; je zapotřebí explicitně definovat
(while (<= y 10) ; podmínka pro ukončení vnější smyčky
(set! x 1)
(while (<= x 10) ; podmínka pro ukončení vnitřní smyčky
(display (/ x y)) ; tisk výsledku
(display "\t") ; přechod na další tabelační zarážku
(set! x (+ x 1))
)
(set! y (+ y 1))
(newline) ; přechod na další řádek
)
1 2 3 4 5 6 7 8 9 10
1/2 1 3/2 2 5/2 3 7/2 4 9/2 5
1/3 2/3 1 4/3 5/3 2 7/3 8/3 3 10/3
1/4 1/2 3/4 1 5/4 3/2 7/4 2 9/4 5/2
1/5 2/5 3/5 4/5 1 6/5 7/5 8/5 9/5 2
1/6 1/3 1/2 2/3 5/6 1 7/6 4/3 3/2 5/3
1/7 2/7 3/7 4/7 5/7 6/7 1 8/7 9/7 10/7
1/8 1/4 3/8 1/2 5/8 3/4 7/8 1 9/8 5/4
1/9 2/9 1/3 4/9 5/9 2/3 7/9 8/9 1 10/9
1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10 1
Poznámka: rekurzivní zápis předchozího příkladu by mohl vypadat následovně:
(define (forx x y limit)
(display (/ x y)) ; tisk výsledku
(display "\t") ; přechod na další tabelační zarážku
(if (< x limit)
(forx (+ x 1) y limit) ; rekurze
)
)
(define (fory y limit)
(forx 1 y limit) ; výpočet celého řádku hodnot
(newline) ; přechod na nový řádek
(if (< y limit)
(fory (+ y 1) limit) ; rekurze
)
)
(fory 1 10)
Který ze způsobů zápisu programu pro výpočet podílů dvou čísel vám připadá nejvhodnější?
9. Odkazy na Internetu
- Lambda calculus
http://en.wikipedia.org/wiki/Lambda_calculus - A Short Introduction to the Lambda Calculus
http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf - A Tutorial Introduction to the Lambda Calculus
http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf - (welcome '(schemers . org))
http://www.schemers.org/ - Revised5 Report on the Algorithmic Language Scheme
http://www.schemers.org/Documents/Standards/R5RS/ - The Revised6 Report on the Algorithmic Language Scheme
http://www.r6rs.org/ - Scheme
http://groups.csail.mit.edu/mac/projects/scheme/ - The Kawa language framework
http://www.gnu.org/software/kawa/ - Scheme 48
http://s48.org/ - Introductory textbooks for Schemers
http://www.schemers.org/Documents/#intro-texts - Scheme (programming language)
http://en.wikipedia.org/wiki/Scheme_(programming_language) - Scheme
http://cs.wikipedia.org/wiki/Scheme - Scheme-faq
http://community.schemewiki.org/?scheme-faq - Scheme implementations
http://community.schemewiki.org/?scheme-faq-standards#implementations - Successful Scheme
http://www.itworld.com/swol-1013-regex - Guy L. Steele, Jr.
http://en.wikipedia.org/wiki/Guy_L._Steele - Gerald Jay Sussman
http://en.wikipedia.org/wiki/Gerald_Jay_Sussman - PLT Scheme
http://www.plt-scheme.org/ - Quick: An Introduction to PLT Scheme with Pictures
http://docs.plt-scheme.org/quick/ - PLT Scheme
http://en.wikipedia.org/wiki/Plt_scheme - PLT Scheme Guide
http://docs.plt-scheme.org/guide/ - The DrScheme Project: An Overview
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.9543 - DrScheme
http://en.wikipedia.org/wiki/DrScheme - How to Design Programs
http://www.htdp.org/ - An Introduction to Scheme
http://www.acm.org/crossroads/xrds1–2/scheme.html
ČLÁNKY DO MAILU