Základy programování v jazyku Scheme

Obsah

1. Základní operace se symboly

2. Čísla, výrazy s čísly, funkce pro práci s čísly

3. Znaky a řetězce

4. Řetězce

5. Pravdivostní hodnoty a logické výrazy

6. Predikáty

7. Zápis podmínek

8. Použití forem and a or při zápisu podmínek

9. Odkazy na Internetu

1. Základní operace se symboly

V předchozí části seriálu o historii výpočetní techniky jsme se seznámili s programovacím jazykem Scheme. Řekli jsme si, že se jedná o jeden ze známých a v některých oblastech IT poměrně často používaných dialektů jazyka LISP, který se od původního „klasického“ LISPu v několika ohledech nepatrně odlišuje. Autoři Scheme (známý Guy L. Steele a Gerald Jay Sussman) vytvořili jazyk vhodný mj. i pro výuku programování (i když to nebylo jejich primárním cílem, původně se jednalo o jazyk určený pro jejich vlastní výzkumné účely), což znamená, že programy napsané ve Scheme bývají čitelnější než obdobné programy napsané v původním LISPu (který se mj. vyznačoval i dynamickým rozsahem viditelnosti proměnných). Dnes si ukážeme základní programové konstrukce, které lze ve Scheme vytvářet. Základní syntaxí i způsobem vyhodnocování funkcí se nebudeme detailně zabývat, protože se v tomto ohledu Scheme příliš neliší od LISPu (některé rozdíly si samozřejmě ukážeme).

Programovací jazyk Scheme je, podobně jako LISP, zaměřen na práci se symboly, takže nás pravděpodobně nepřekvapí, že jedním ze základních typů, se kterými je možné ve Scheme pracovat, jsou právě symboly. Symboly je možné použít hned několika způsoby – jako hodnoty výčtového typu, jako klíče asociativních polí (hešovacích tabulek) i pro jména proměnných. Symbol je v programu reprezentován svým jménem, které je v celém programu unikátní (existuje právě jednou). Z tohoto důvodu je možné symboly porovnávat pomocí efektivní operace (eq) namísto equal? (i tuto operaci, přesněji řečeno predikát, lze samozřejmě použít). Pokud se symbol zapisuje do programu, je nutné před jeho jméno přidat znak ' (quote), protože v opačném případě by interpretr jazyka Scheme jméno symbolu chápal jako jméno proměnné a snažil by se tuto proměnnou vyhodnotit na její hodnotu. Při práci se symboly je možné využít několika funkcí, z nichž ty nejčastěji používané jsou vypsány v následující tabulce:

Následuje několik příkladů práce se symboly. Na tomto místě možná stojí za připomenutí, že #t značí ve Scheme pravdivostní hodnotu true a #f naopak pravdivostní hodnotu false:

; vytvoření nového symbolu
'abc
abc

; jméno symbolu může obsahovat i některé nealfanumerické znaky
'x^y
x^y

'ěščřžýáíé
ěščřžýáíé

; použití predikátu symbol?
(symbol? 'hello)
#t
(symbol? "hello")
#f
(symbol? 42)
#f

; různé způsoby porovnání symbolů
(eq? 'aaa 'aaa)
#t

(eq? 'aaa 'bbb)
#f

(equal? 'aaa 'aaa)
#t

; porovnání symbolů a proměnných nesoucích symbol
; povšimněte si, že v tomto případě není rozdíl
; mezi chováním eq, eqv a equal (u jiných typů dat
; tomu však tak být nemusí)
(define X 'aaa)
(define Y 'aaa)
(eq? X Y)
#t
(eq? X 'aaa)
#t
(eqv? X Y)
#t
(eqv? X 'aaa)
#t
(equal? X Y)
#t
(equal? X 'aaa)
#t

; převod symbolu na řetězec
(symbol->string 'aaa)
"aaa"

; převod řetězce na symbol (v tomto případě se vytvoří nový symbol)
(string->symbol "hello")
hello

2. Čísla, výrazy s čísly, funkce pro práci s čísly

Dalším datovým typem, s nímž se můžeme setkat prakticky v každém programu, je numerický datový typ. Programovací jazyk Scheme dělí numerické hodnoty (čísla) do několika kategorií, přičemž s každou kategorií interně pracuje poněkud odlišným způsobem. Jedná se o celá čísla (integer), racionální čísla (rationals) reprezentovatelná zlomkem s celočíselným čitatelem i jmenovatelem, reálná čísla (real) a konečně čísla komplexní (complex). Reálná čísla se navíc rozlišují podle toho, zda je může interpretr jazyka Scheme reprezentovat přesně nebo jen s určitou přesností. Zajímavý je způsob uložení numerických hodnot v operační paměti počítače. Interpretry jazyka Scheme například celá čísla, jejichž hodnota leží v rozsahu běžných čtyřbajtových nebo osmibajtových celých čísel zpracovávaných přímo mikroprocesorem (v céčku by se jednalo o datové typy int a long, popř. long long), uchovávají i zpracovávají stejným způsobem, jaký známe například z céčka, Pascalu či Javy, tj. každá numerická hodnota je uložena ve čtyřech či osmi bajtech paměti, podle toho, jaké typy jsou podporovány CPU a jaké lze uložit do pracovních registrů procesoru..

Pro větší celočíselné hodnoty se používá vícebajtová aritmetika, což mj. znamená, že rozsah reprezentovaných hodnot je omezen pouze rychlostí zpracování těchto hodnot a kapacitou operační paměti (viz příklad výpočtu faktoriálu uvedený v předchozí části tohoto seriálu). Scheme tedy, jako vysokoúrovňový programovací jazyk, programátory odstiňuje od konkrétního způsobu uložení a zpracování numerických hodnot počítačem a na druhou stranu, pokud je to možné, používá efektivní způsob uložení dat i rychlý způsob výpočtu aritmetických výrazů. Užitečná je i existence čísel racionálních, pomocí nichž lze obejít některé nedostatky reálných čísel, přesněji řečeno způsob uložení podmnožiny reálných čísel v datových typech float či double. Například je známým faktem, že reálnou hodnotu 0.1 není možné přesně uložit ani v proměnné typu float ani double. Naproti tomu reprezentace racionálních čísel v programovacím jazyku Scheme je zcela přesná a navíc i přehledná – postačuje napsat 1/10. Při numerických výpočtech je možné použít velké množství různých funkcí, například:

Následuje několik příkladů práce s čísly:

; ve Scheme lze používat různé základy číselné soustavy:

; binární reprezentace
#b101010
42

; reprezentace v osmičkové soustavě
#o52
42

; použití hexadecimální soustavy
#x2a
42

; zápis reálného čísla, které nelze reprezentovat přesně
#i1.4142135623731
1.4142135623731

; výpočty s reálnými čísly, které nelze reprezentovat přesně
(- #i1000.0 #i999.9)
#i0.10000000000002274
; výsledkem by měla být hodnota 0.1

; podíl dvou celých čísel, výsledkem je číslo racionální
(/ 20 100)
1/5

(/ 10 7)
10/7

; práce se zlomky i s jejich zjednodušováním
(+ 1/3 1/4)
7/12

(/ 1/3 1/4)
4/3

; použití predikátů
(number? #i0.999)
#t

(number? 42)
#t

(number? (/ 123 456))
#t

(number? "hello")
#f

(number? 'symbol)
#f

; složitější výpočty se zapisují a vyhodnocují
; podobně jako v LISPu
(gcd (- 20 10) (+ 2 3))
5

; práce s velkými celými čísly (big integers)
(expt 123 456)

99250068772098856700831462057469632637295940819886900519816
29888138286710474939907792112866142614463805542423693627187
24928003527416499021181438196726015699981001207904967595176
36465445895625741609866209900500198407153244604778968016963
02805031026141761591446872991824068548787861764597693906346
43579861657117309763994785076492286863414669671679101266533
42134942744851463899927487092486610977146112763567101672645
95313219648143933987301708814041466127119850033325571309614
23351514146306516830655187840812036784877030028020820912366
03519026256880624499681781387227574035484831271515683123742
14909556926046360965597770093884458061193124649516620869554
03136981400116380273225662526897808381363518287953142721621
11222231170901715612355701347552371530013693855379834865667
06001464330245910042978365396691378300229078428345562828335
54705299329560514844771293338811599302127586876027950885792
30431661696010232187390436601614145603241902386663442520160
735566561

3. Znaky

Dalšími dvěma základními datovými typy používanými (samozřejmě nejenom) v programovacím jazyce Scheme jsou znaky a řetězce. Nejprve si řekněme, jakým způsobem se pracuje s jednotlivými znaky. Ty jsou interně reprezentovány jako 21 bitové hodnoty, v nichž jsou uloženy kódy znaků odpovídající standardu Unicode (zda je oněch 21 bitů uloženo ve čtyřech bajtech či jiným způsobem, je již ponecháno na konkrétní implementaci Scheme, zde si pouze povšimněte rozdílu v chápání datového typu „char“ ve Scheme a například v Javě, kde se ve skutečnosti nejedná o plnohodnotné znaky schopné reprezentovat všechny národní abecedy). Pro převody mezi znaky a jejich kódy se používá dvojice funkcí nazvaných char->integer a integer->char. Tisk znaku lze provést pomocí funkce display. Tisknutelný znak je ve zdrojovém kódu programů i ve výstupech interpretru reprezentován trojicí znaků #\X, kde X je grafická podoba tisknutelného znaku, například:

#\A
#\A

#\a
#\a

#\(
#\(

#\#
#\#

#\\
#\\

Pro znaky, které nemají tisknutelnou podobu, nebo které by se složitě zapisovaly do zdrojového kódu (národní abecedy) se používá formát #\uCAFE, kde CAFE je hexadecimálně zapsaný kód znaku definovaný v Unicode. Některé znaky mohou být v programech reprezentovány svým symbolickým jménem; typickým příkladem je #\space. Následující příklady používají výše popsané převodní funkce char->integer, integer->char i funkci display:

(display #\A)
A

(integer->char 65)
#\A

(char->integer #\A)
65

(char->integer #\space)
32

(integer->char 32)
#\space

(integer->char 27)
#\esc

4. Řetězce

Programovací jazyk Scheme samozřejmě podporuje i práci s řetězci, které se zapisují, jak je tomu ostatně zvykem v mnoha dalších programovacích jazycích, do uvozovek. Na rozdíl od již popsaných symbolů, které jsou v programu jedinečné, mohou být řetězce se stejným obsahem (tj. se stejnou sekvencí znaků) uloženy v paměti vícekrát, takže je jejich porovnávání poněkud složitější, než v případě symbolů. Ostatně si to můžeme ukázat na jednoduchém příkladu, v němž je nejprve vytvořena dvojice proměnných obsahujících obsahově shodné řetězce, ovšem každý z řetězců může ležet v jiné oblasti paměti, což znamená, že porovnání jejich referencí (adres) pomocí funkce (predikátu) eq? vrátí pravdivostní hodnotu #f, zatímco porovnání skutečného obsahu řetězců funkcí equal? naopak vrátí očekávanou hodnotu #t.

(define A "hello")
(define B "hello")

(eq? A B)
#f

(equal? A B)
#t

Pro lepší čitelnost programů, zejména v případě, že si programátor je jistý, že předané hodnoty jsou skutečně typu řetězec, je výhodnější porovnávat řetězce pomocí následující dvojice funkcí:

Výše uvedené funkce si můžeme ihned vyzkoušet:

(define A "hello")
(define B "hello")
(define C "Hello")

(string=? A B)
#t

(string=? B C)
#f

(string-ci=? B C)
#t

Další skupina funkcí dokáže zjistit, zda nějaký znak spadá do určité kategorie znaků, tj. zda se například jedná o písmeno, číslo nebo nějaký „bílý“ znak:

(char-alphabetic? #\A)
#t

(char-numeric? #\0)
#t

(char-whitespace? #\newline)
#t

5. Pravdivostní hodnoty a logické výrazy

S pravdivostními hodnotami jsme se již několikrát setkali v demonstračních příkladech uvedených v předchozích kapitolách. Proto si pouze připomeňme, že Scheme se v tomto ohledu poněkud odlišuje od LISPu v němž je prakticky vše kromě prázdného seznamu považováno za hodnotu „pravda“ a prázdný seznam (ekvivalentní se symbolem nil) je považován za „nepravdu“. V programovacím jazyku Scheme se logická hodnota „pravda“ zapisuje pomocí (jedinečného) symbolu #t a „nepravda“ pomocí symbolu #f. Všechny hodnoty kromě #f (ale včetně prázdného seznamu) se při vyčíslování pravdivostních výrazů, podmínek atd. považují taktéž za pravdu, ostatně podobně je tomu i v dalších vysokoúrovňových programovacích jazycích. Při zápisu logických výrazů je možné použít speciální formy and, or a not, jak je ostatně ukázáno v následujících příkladech:

; symboly #t a #f se vyhodnocují samy na sebe,
; proto se před ně nemusí psát apostrof
#t
#t

#f
#f

; použití funkce not, na níž si můžeme demonstrovat,
; jak se všechny ostatní hodnoty kromě #f automaticky
; převádí na #t (pravdu)
(not #t)
#f

(nor #f)
#t

(not 'A)
#f

(not (not 'A))
#t

(not 42)
#f

(not (not 42))
#t

; jak se bude chovat "negace prázdného seznamu"?
(not '())
#f
(not (not '()))
#t

6. Predikáty

V předchozím textu jsme se několikrát setkali se slovem „predikát“. Na predikátech není vůbec nic tajemného, neboť se jedná o pojmenování funkcí vracejících pravdivostní hodnotu #t nebo #f v závislosti na tom, zda byla či naopak nebyla splněna nějaká podmínka. Predikáty lze ve Scheme poznat velice snadno, neboť se jedná o funkce končící znakem otazník (jak jste si již mohli všimnout, může se ve jménech funkcí vyskytovat velké množství nealfanumerických znaků, což je mj. umožněno i díky tomu, že Scheme používá prefixovou syntaxi se striktním oddělením jednotlivých jazykových prvků buď nějakým bílým znakem nebo levou či pravou kulatou závorkou). Mezi standardní predikáty patří například funkce zjišťující, zda je předaný parametr určitého typu – viz tabulka uvedená pod tímto odstavcem. Přitom platí důležitá podmínka, že každý objekt v jazyce Scheme patří pouze do jedné z následujících kategorií:

Příklady použití výše uvedených predikátů:

(boolean? #t)
#t

(boolean? #f)
#t

(boolean? 42)
#f

(number? 42)
#t

(number? 42)
#t

(string? 42)
#f

(string? "42")
#t

; V článku o programovacím jazyku LISP jsme si mj. uvedli
; jakým způsobem jsou v operační paměti reprezentovány seznamy.
; Ze znalosti uložení seznamů lze odvodit, proč se predikát
; pair? chová tak, jak je naznačeno v těchto příkladech:
(pair? '())
#f

(pair? '(a))
#t

(pair? '(a b))
#t

(pair? '(a.b))
#t

(pair? '(a b c))
#t

Kromě výše uvedených predikátů jsou ve Scheme dostupné i mnohé predikáty další, například:

7. Zápis podmínek

Při programování prakticky jakéhokoli složitějšího programu se nevyhneme nutnosti zápisu podmíněných bloků kódu (v bloku se může například vyskytovat volání nějaké funkce atd.). V programovacím jazyku Scheme je možné podmíněné příkazy zapisovat několika způsoby, z nichž nejpoužívanější je konstrukce se speciální formou if a cond. Oba typy konstrukcí byly převzaty z původního LISPu a posléze u nichž došlo k několika úpravám. Nejprve si na příkladech ukažme použití formy if, která se příliš neliší od příkazu typu if v dalších programovacích jazycích (samozřejmě až na nutnost používat kulaté závorky):

(define x -42)

; použijeme pouze jednu větev speciální formy if
; která se provede v případě, že se podmínka vyhodnotí na #t
(if (number? x) (display "parametr je typu cislo"))
parametr je typu cislo

; použijeme obě větve speciální formy if
(if (positive? x) (display "kladna hodnota") (display "zaporna hodnota"))
zaporna hodnota

; poněkud čitelnější zápis předchozí podmínky
(if (positive? x)                ; podmínka
    (display "kladna hodnota")   ; větev "then"
    (display "zaporna hodnota")  ; větev "else"
)
zaporna hodnota

; co se stane když není zavolána první větev formy if
; a druhá větev neexistuje?
(define x 'symbol)
(if (number? x) (display "parametr je typu cislo"))
; nic se nevrátilo

Forma cond (zkrácenina od slova „condition“) se sice zdánlivě podobá příkazu switch z céčka či Javy, ovšem je zde jeden významný rozdíl – cond vrací, jako mnoho dalších speciálních forem i funkcí (včetně dalších typů podmínek), hodnotu, takže ji lze použít ve výrazu. V následujícím příkladu se vrátí jeden ze tří řetězců v závislosti na tom, jaká číselná hodnota je formě cond předána:

(define x -42)

(cond
    ((negative? x) "zaporne cislo")
    ((positive? x) "kladne cislo")
    (else "nula")                   ; znáte "default" v Javě/céčku?
)
"zaporne cislo"

(define x 0)
(cond
    ((negative? x) "zaporne cislo")
    ((positive? x) "kladne cislo")
    (else "nula")
)
"nula

8. Použití forem and a or při zápisu podmínek

V některých případech může být výhodnější namísto speciální formy if použít formy and či or, tj. logický součin a logický součet, protože druhý (či jakýkoli další) parametr těchto speciálních forem je vyhodnocován pouze v tom případě, pokud NENÍ z vyhodnoceného prvního parametru zřejmý výsledek výrazu. Jedná se o takzvané zkrácené vyhodnocování logických výrazů, které poměrně často používají například programátoři v jazyce Perl (jedná se o jeden z idiomů tohoto programovacího jazyka):

(define x 0)

; poněkud nepříjemné je to, že and a or mohou vrátit
; pravdivostní hodnotu - výsledek vyhodnocení prvního parametru
(and (negative? x) (display "sem vubec nedojdu"))
#f

; první parametr se vyhodnotí na #t, takže se
; musí vyhodnotit i parametr druhý
(and (zero? x) (display "a sem naopak dojdu"))
a sem naopak dojdu

; forma or se chová podobně, akorát vyhodnocuje druhý
; parametr tehdy, když je první parametr #f
(or (negative? x) (display "sem dojdu"))
sem dojdu

(or (zero? x) (display "a sem zase ne"))
#t

Výhoda použití speciálních forem and a or spočívá v tom, že je možné tvořit řetězce příkazů, které jsou prováděny pouze tehdy, pokud se všechny předchozí parametry vyhodnotily na #t (v případě speciální formy and) nebo naopak na #f (pokud je použita forma or). Interpretr programovacího jazyka Scheme totiž zaručuje, že parametry budou vyhodnocovány zleva doprava a díky zkrácenému vyhodnocování se zavolají jen ty (nejlevější) parametry, které jsou nutné pro určení výsledné hodnoty formy and či or (díky prefixové notaci mohou obě formy akceptovat libovolný počet parametrů):

; POZOR - následující příklady jsou značně umělé, pro plné využití
;         speciálních forem and a or ještě neznáme všechny prostředky
;         programovacího jazyka Scheme

; řetězec vypsaný funkcí display a návratová hodnota formy and
(and #t (display "tady jsem") #f (display "a tady uz ne"))
tady jsem#f

; vyhodnotí se jen první parametr, ostatní se ignorují
(and #f (display "tady jsem") #f (display "a tady uz ne"))
#f

; vyhodnotí se všechny parametry
(and #t (display "nekolik ") (display "zretezenych ") (display "volani."))
nekolik zretezenych volani

9. Odkazy na Internetu

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