Programovací jazyk Scheme: definice anonymních i pojmenovaných funkcí, iterace

Obsah

1. Vytváření nových uživatelských funkcí

2. Pojmenování uživatelských funkcí

3. Anonymní funkce

4. Anonymní funkce s proměnným počtem parametrů

5. Pojmenované funkce s proměnným počtem parametrů

6. Rekurze

7. Programová smyčka typu „do“

8. Makro „while“

9. Odkazy na Internetu

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 R₅RS):

(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))))
    )
)

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)

9. Odkazy na Internetu

1. Lambda calculus
   http://en.wiki­pedia.org/wiki/Lam­bda_calculus
2. A Short Introduction to the Lambda Calculus
   http://www.cs­.bham.ac.uk/~ax­j/pub/papers/lam­bda-calculus.pdf
3. A Tutorial Introduction to the Lambda Calculus
   http://www.inf.fu-berlin.de/leh­re/WS03/alpi/lam­bda.pdf
4. (welcome '(schemers . org))
   http://www.sche­mers.org/
5. Revised⁵ Report on the Algorithmic Language Scheme
   http://www.sche­mers.org/Docu­ments/Standar­ds/R5RS/
6. The Revised⁶ Report on the Algorithmic Language Scheme
   http://www.r6rs­.org/
7. Scheme
   http://groups­.csail.mit.edu/mac/pro­jects/scheme/
8. The Kawa language framework
   http://www.gnu­.org/software/ka­wa/
9. Scheme 48
   http://s48.org/
10. Introductory textbooks for Schemers
    http://www.sche­mers.org/Docu­ments/#intro-texts
11. Scheme (programming language)
    http://en.wiki­pedia.org/wiki/Sche­me_(programmin­g_language)
12. Scheme
    http://cs.wiki­pedia.org/wiki/Sche­me
13. Scheme-faq
    http://communi­ty.schemewiki­.org/?scheme-faq
14. Scheme implementations
    http://communi­ty.schemewiki­.org/?scheme-faq-standards#imple­mentations
15. Successful Scheme
    http://www.it­world.com/swol-1013-regex
16. Guy L. Steele, Jr.
    http://en.wiki­pedia.org/wiki/Gu­y_L._Steele
17. Gerald Jay Sussman
    http://en.wiki­pedia.org/wiki/Ge­rald_Jay_Sussman
18. PLT Scheme
    http://www.plt-scheme.org/
19. Quick: An Introduction to PLT Scheme with Pictures
    http://docs.plt-scheme.org/quick/
20. PLT Scheme
    http://en.wiki­pedia.org/wiki/Plt_sche­me
21. PLT Scheme Guide
    http://docs.plt-scheme.org/guide/
22. The DrScheme Project: An Overview
    http://citese­erx.ist.psu.e­du/viewdoc/sum­mary?doi=10.1­.1.22.9543
23. DrScheme
    http://en.wiki­pedia.org/wiki/DrSche­me
24. How to Design Programs
    http://www.htdp­.org/
25. An Introduction to Scheme
    http://www.ac­m.org/crossro­ads/xrds1–2/scheme.html