Základy jazyka Scheme
Scheme je multiparadigmatický programovací jazyk určený především pro vědecké a výukové potřeby. Nástroj DrScheme na programování v tomto jazyce můžete stáhnout z webu PLT Scheme. Jako jazyk v tomto nástroji zvolte Pretty Big.
Nástroj má dvě textová pole. První (vrchní) textové pole slouží pro zápis celých definic jenž se vykonají až po stisku tlačítka Run (Ctrl+T). Druhé (spodní) textové pole vykoná operaci ihned po ukončení řádku (Enter) a zároveň ukazuje výsledek operace.
Ukázkový program. Ukázkový program vypíše nápis „Ahoj svete!“. Ukázka správného i chybného programu.
Chyby při programování:
Chyby sémantiky: Kód, program funguje – avšak špatně. Výsledky jsou nesprávné…
Chyby syntaxe: Kód nefunguje – jsou použity neexistující, chybné příkazy či proměnné…
Struktura Scheme a vykonávání programu:
Kód, program je vykonáván postupně od prvního řádku a znaku. Vyhodnocení probíhá na čísla, symboly nebo seznamy (tzv. Symbolické výrazy).
Čísla: 0 15 -9 -237.4 0.75 35.22e-14 -5i 2+3i 3/7
Čísla se vyhodnotí na sebe sama.
Symboly: + – cokoliv 15n x-3y sqrt
Symboly se vyhodnotí na aktuální vazbu či proceduru (operaci)
Některé symboly jako např. + – mají předdefinované procedury (operace, funkce) např. sčítání a odčítání.
Nedefinovaným symbolům můžeme (a musíme) přiřadit nějakou proceduru. Pokud žádnou proceduru nepřiřadíme a takový symbol použijeme, počítač symbol nezná a upozorní na chybu.
Mezery, závorky a tečky nelze použít jako symboly.
Seznamy: (+ 3 2) (něco1 něco2 něco3)
Seznamy jsou uzavřené v závorkách oddělené mezerami, tabulátory, řádky).
Nejdříve se vyhodnotí první prvek seznamu na proceduru.
Následně se vyhodnotí zbylé prvky.
Aplikuje se procedura.
Zápis kódu:
Kód je zapisován prefixově. Symbol operace (operátor) je zapsán před operandy.
Sčítání dvou čísel: (+ 3 5) (výsledek: 8)
Sčítání vícero čísel: (+ 8 7 12 3) (výsledek: 30)
Odčítání: (- 5 2) (výsledek: 3)
Násobení: (* 4 3) (výsledek: 12)
Dělení: (/ 20 5) (výsledek: 4)
Odmocnina: (sqrt 9) (výsledek 3)
Scheme tedy nejprve řeší co má dělat a až následně s čím to má dělat. Sčítání, odčítání atd. jsou tzv. primitivní procedury.
Textový řetězec (speciální forma):
(display "Ahoj svete!")
(display „Textovy retezec“)
Vypíše textový řetězec Ahoj svete!
(newline)
Vloží nový řádek.
;———————— Koment —————
Středníkem začíná komentář na jednom řádku
Příklad 01: Práce s textem. Program vypíše text, vloží nový řádek a vypíše další text.
(display "Toto je prvni radek.") (newline) (display "Toto je druhy radek.")
Vstup od uživatele pomocí read:
(read) (+ 2 (read)) (+ 10 (read) (read))
Definice (speciální forma):
Vytvoření definice: define. Definuje vazbu symbolu vyska jako číslo 20.
(define vyska 20)
(define nazev hodnota)
Nelze navázat proceduru. Proceduru lze takto pojmenovat.
Původní vazba je zrušena.
Vazba se týká globálního prostředí (celého programu).
Podmíněná operace if (speciální forma):
If testuje podmínku zda-li je a větší než b. Pokud je podmínka splněna, vyhodnotí výsledek na c. Je-li podmínka nesplněna vyhodnotí se výsledek na d (nemusí se uvádět).
(if (> a b) c d)
(if testovana_podminka nasledek_splneno nasledek_nesplneno)
Příklad 02: Definice a podmínka. Program definuje čtyři symboly a b c d jako čísla. Dále testuje podmínku (zda je symbol a větší než symbol b). Symboly a b se vyhodnotí na čísla 40 a 30. Pokud je podmínka splněna, vyhodnotí se symbol c na číslo 1. Pokud je podmínka nesplněna, vyhodnotí se symbol d na číslo 0.
(define a 40) (define b 30) (define c 1) (define d 0)(if (> a b) c d)
Logické operátory:
Logická 1 (pravda, true): #t
Logická 0 (nepravda, false): #f
Negace, opak: not
Konjunkce (a): and
Disjunkce (nebo): or
Test sudých čísel: even?
Test lichých čísel: odd?
Příklad 03: Logické podmínky.
(and (< 1 3) (< 6 10))(and (even? 3) (even? 10))(or (odd? 1) (odd? 2))(or (odd? 10) (odd? 20) )
Testovací podmínka cond (speciální forma):
Testovací podmínka cond hledá, prochází podmínky umístěné za sebou. Jakmile najde podmínku jenž je splněna jako pravda, vyhodnotí její následek. Na podmínce s první pravdou končí a další podmínky nehledá. Lze přidat následek else, jenž je vyhodnocen pokud žádná podmínka není vyhodnocena na pravdu.
(cond ((< 3 2) 0) ((> 3 2) 1))
(cond ((podminka1) nasledek1) ((podminka2) nasledek2) .....)
(cond ((podminka1) nasledek1) ((podminka2) nasledek2) (else nasledek_nic_nesplneno))
Příklad 04: Testovací podmínka:
(cond ((< 4 3) 1) ((< 6 1) 2) ((< 2 8) 3) ((< 3 5) 3)) (cond ((< 4 3) 1) ((< 6 1) 2) ((< 2 1) 3) ((< 3 2) 3) (else 0)) (cond ((< 3 2) (- 2 3)) ((< 2 3) (- 3 2)))
Procedura (speciální seznam)
Speciální seznam obsahující lambda vytváří proceduru. V první části očekává vstupní parametr. Následuje operace se vstupními parametry.
(lambda (x) (* x x))
(lambda (vstupní parametry) (operace) (prostředí))
Procedury nahrazují neustálé opakování stejných pravidel kódu. Můžeme je volat dle potřeby.
Jako návratová hodnota (výstup) nemusí být jen číslo ale také jiná (další vnořená) procedura.
Lambda nevyhodnocuje své parametry.
Příklad 05: Přímá aplikace procedury. Aplikace vytvoří proceduru druhé mocniny zadaného čísla x. Výsledek je 25.
((lambda (x) (* x x)) 5)
Příklad 06: Vytvoření, pojmenování, aplikace procedury. Volaná procedura na2 očekává jedno vstupní číslo. Procedura je použita pro 2², 3² a 2² + 5².
(define na2 (lambda (x) (* x x))) (na2 2) (na2 3) (+ (na2 2) (na2 5))
Příklad 07: Procedura se dvěma vstupními parametry. Volaná procedura vypocet očekává dvě vstupní čísla. Výsledek je 30.
(define vypocet (lambda (x y) (+(* x x) y)))(vypocet 5 5)
Příklad 08: Obsah obdélníku. Výsledky jsou 12, 50, 48.
(define obsah_obdelniku (lambda (a b) (* a b))) (obsah_obdelniku 4 3) (obsah_obdelniku 10 5) (obsah_obdelniku 12 4)
Příklad 09: Převod z infixového zápisu do prefixového. Pro dvě čísla.
(define PTI (lambda (x znamenko y) (znamenko x y)))(PTI 3 + 2) (PTI 5 * 6) (PTI 10 * (PTI 2 + 3)) (PTI 30 / 8)
Prostředí a vazby symbolů:
Aby program věděl co je s čím spojeno, svázáno, definováno atd. využívá prostředí jenž si lze představit jako tabulku. Výchozí vazby jsou definovány v tzv globálním (hlavním) prostředí. Jakékoliv další procedury, procesy (zanořování) a jejich proměnné operace jsou zpracovány v lokálních prostředích, jenž se tvoří automaticky dle potřeby.
Každé lokální prostředí má v hlavičce uvedeno kde vzniklo (odkaz na své nadřazené prostředí – svého předka). Pokud se tedy hledá nějaký symbolický výraz v lokálním prostředí a nenajde se, pokračuje hledání v nadřazeném prostředí (lexikální, statický rozsah platnosti). Pokud se však symbolický výraz nikde nenajde, skončí program chybou.
Do stejného prostředí můžeme již vytvořené definice přepisovat – jako proměnné. Tak lze jedno prostředí využívat stále dokola (např. a = 3, a = 12, a = 37, …) . Toto je vhodné skrz ušetření operační paměti počítače – každé nové prostředí = nově zabraná paměť.
Ukázka: Na počátku se vytvoří globální prostředí. Žádné další prostředí není třeba.
(define a 30) (define b 7) (define c 5) (+ a b c)
Ukázka: Na počátku se vytvoří globální prostředí. Procedura obsah_obdelniku pracuje ale se dvěma symboly a proto je třeba pro ně vytvořit další lokální prostředí
(define obsah_obd (lambda (a b) (* a b))) (obsah_obd 4 3)
Příklad 10: Procedura vnořená do procedury. Program vypočítá cenu s DPH ze základní ceny bez DPH. Výsledky jsou 121, 1185.8.
(define sDPH (lambda (d) (lambda (c) (* d c))))(define vypocitej (sDPH 1.21))(vypocitej 100) (vypocitej 980)
Příklad 11: Procedura random. Generuje náhodné číslo od 0 do zadané limity.
(random 100) (random 100) (random 100) (random 100)
Příklad 12: Vnořená procedura: Obsah trojúhelníku dle Heronova vzorce. Sestává z mezivýpočtu s jenž se následně dosazuje celkem 4× do dalšího vzorce. Abychom tento mezivýpočet nemuseli opakovat, vytvoříme vnořenou proceduru. Postačí tedy zadat jen délky stran a b c.
(define obsah_t ;definice názvu procedury (lambda (a b c) ;vytvoření procedury se vstupními parametry a b c ((lambda (s) ;vytvoření procedury se vstupním parametrem s (sqrt(* s (- s a) (- s b) (- s c)))) ;výpočet S a dosazení s (/ (+ a b c) 2)))) ;výpočet vstupního parametru s (obsah_t 3 4 5) ;zavolání procedury s parametry a b c
Krátkodobé vazby symbolů let:
Pro vytvoření krátkodobých vazeb symbolů pro použití po dobu životnosti lokálního prostředí slouží let (speciální seznam). Po dobu životnosti lokálního prostředí překryje vazby nadřazených prostředí. Hodnoty se nejdříve vyhodnotí a až následně jako číslo (hodnota) přiřadí. Symboly vazeb musí být různé!
(let ((a 5) (b 2)) (+ a b))
(let ((symbol1 hodnota1) (symbol2 hodnota2) (symbol3 hodnota3)) (operace))
Příklad 13: Překrytí globálních vazeb. První výsledek je 7 (čísla 50 a 20 jsou překryty). Druhý výsledek je 70 protože byl ukončen let blok.
(define a 50) (define b 20) (let ((a 5) (b 2)) (+ a b)) (+ a b)
Krátkodobé vazby symbolů let*:
Pro vytvoření krátkodobých vazeb symbolů pro použití po dobu životnosti lokálního prostředí slouží let* (speciální seznam). Po dobu životnosti lokálního prostředí překryje vazby nadřazených prostředí. Hodnoty se nejdříve vyhodnotí a až následně jako číslo (hodnota) přiřadí. Symboly vazeb mohou být stejné!
(let* ((a 5) (a 2)) (* a a))
(let* ((symbol1 hodnota1) (symbol2 hodnota2) (symbol1 hodnota3)) (operace))
Příklad 14: Opakovaný zápis do jednoho symbolu x. Výsledek je 16.
(let* ((x 2) (x (* x 2)) (x (* x 2)) (x (* x 2))) x)
Tečkový pár:
Tečkový pár zapouzdřuje dvě hodnoty (čísla, symboly). Hodnota může obsahovat další tečkový pár.
(define par (cons 10 20)
(define nazev (cons prvni_hodnota druha hodnota)
Příkaz cons vytvoří tečkový pár dvou hodnot (v tomto případě čísel 10 a 20)
První hodnotu vypíšeme příkazem car a druhou hodnotu příkazem cdr.
(car par) (car nazev) (cdr par) (cdr nazev)
Ukázka: Složený tečkový pár (hodnota a tečkový pár).
(define par (cons 10 (cons 20 30))) (car par) (cdr par)
Ukázka: Složený tečkový pár (dva tečkové páry).
(define par (cons (cons 10 20) (cons 30 40)))(car par) (cdr par)
Ukázka: Složený tečkový pár (dva tečkové páry). Výběr jednotlivých hodnot. Sekvence a-d (car cdr) lze opakovat až do délky 4 znaků (car caar cdr cdar caadr). To pomáhá vyselektovat požadované hodnoty i ze složitých složených tečkových párů.
(define par (cons (cons 10 20) (cons 30 40))) (car par) (cdr par) (caar par) (cdar par) (cadr par) (cddr par)
Příklad 15: Záměna hodnot tečkového páru.
(define P1 (cons 10 20)) (define P2 (cons (cdr P1) (car P1)))(car P2) (cdr P2)
Příklad 16: Procedura uvnitř tečkového páru. Výsledek SOUČINU je zapsán pomocí vnořeného tečkového páru jako ((ČINITEL . ČINITEL) . SOUČIN)
(define VYNASOB (lambda (A B) (cons (cons A B) (* A B))))(VYNASOB 2 5)
Kvótování (speciální forma):
Kvótováním zakážeme vyhodnocení následovaného symbolu na proceduru. Pro kvótování slouží příkaz quote nebo znak horní jednoduché uvozovky.
(quote XX) 'XX '+ '(3 + 3)
Seznamy:
Seznamy vycházejí z tečkového páru. Prázdný seznam má podobu ().
() Prázdný seznam ()
(x . ()) Jednoprvkový seznam (x)
(x . (y . (z . ()))) Tříprvkový seznam (a b c)
Konstrukce seznamů za použití procedury cons.
(cons 'x '()) → (x) (cons 1 (cons 2 (cons 3 '()))) → (1 2 3) (cons 1 (cons (cons 3 4)'())) → (1 (3 . 4))
Operace výpisů:
car - vrací první prvek seznamucdr - vrací seznam bez prvního prvku
Příklad 17: Procedura a seznam. Procedura uprav zpracuje na vstupu seznam a upraví jej do podoby jednoprvkového seznamu.
(define uprav (lambda (x) (cons x ()))) (uprav '(2)) (uprav '(2 -1 3))
Příklad 18: Procedura a seznam. Procedura uprav zpracuje na vstupu seznam a upraví jej do podoby dvouprvkového seznamu.
(define uprav (lambda (x y) (cons x (cons y ())))) (uprav '(2) '(3))
Příklad 19: Vytvoření seznamu dle uživatelského vstupu.
(let ((x (read))) (cons '+ (cons 1 x)))
Manipulace se seznamy:
(list)
(list 1 2 3)
(list (list 1) (list 2))
Procedura list vytváří seznam dle výčtu jeho prvků () nebo (1 2 3) nebo ((1) (2)).
Může také obsahovat proceduru (list (+ 1 2)) protože před aplikací list jsou další procedury vyhodnoceny (3).
(build-list 5 +)
(build-list delka aplikace_procedury)
(build-list 8 (lambda (x) x))
Vytváří seznam o zadané délce dle vložené procedury.
(lenght '(1 2 3))
(lenght '(1 (2 3) 4))
Vrací, zjišťuje délku seznamu.
(list-ref '(a (b c) d) 0)
(list-ref '(a (b c) d) 1)
Vrací prvek na dané pozici seznamu (počínaje první pozicí 0).
(reverse '(1 2 3 4 5))
(define seznam '(1 2 3 4 5)) (reverse seznam) seznam
Vrací původní seznam v opačném pořadí prvků.
(append '(1 2 3) '(4 5))
(append '(a b) '(c d) '(e f))
Spojí dva a více seznamů do jednoho.
Příklad 20: Vlastní procedura reverse.
(define opak (lambda (l) (let ((len (length l))) (build-list len (lambda (i) (list-ref l (- len i 1))))))) (opak '(a b c d))
Příklad 21: Vlastní procedura append.
(define spojka (lambda (l1 l2) (let ((len1 (length l1)) (len2 (length l2))) (build-list (+ len1 len2) (lambda (i) (if (< i len1) (list-ref l1 i) (list-ref l2 (- i len1)))))))) (spojka '(a b c d) '(e f))
Aplikace procedury na prvky seznamu, mapování seznamu:
(map)(map procedura seznam)(map even? Seznam_Cisel)
Procedura se aplikuje na každý prvek seznamu a vrátí seznam vyhodnocených prvků.
(map + Sez1 Sez2 Sez3)
Mapovat procedurou lze i více seznamů. Seznamy však musí míst stejnou délku.
Příklad 22: Sudá a lichá čísla v seznamu.
(define s1 '(1 2 3 4 5 6 7 30 20 37 79 101))
(map even? s1) ;je cislo sude? (map even? s1) ;je cislo liche?
Příklad 23: Sčítání dvou seznamů.
(define s1 '(10 20 30 40 50)) (define s2 '(1 2 3 4 5)) (map + s1 s2)
Příklad 24: Porovnání dvou seznamů.
(define s1 '(10 20 30 40 50)) (define s2 '(1 20 3 40 5))
(map = s1 s2)
Příklad 25: Duplikace první a poslední položky seznamu.
(define s1 '(1 2 3 4 5)) (define dupf (lambda (L) (cons (car L) L))) (define dupl (lambda (L) (reverse (dupf (reverse L))))) (dupf s1) ;duplikuj první prvek seznamu (dupl s1) ;duplikuj poslední prvek seznamu
Příklad 26: Generování seznamu čísel od A do B.
(define rozsah (lambda (A B) (build-list (+ 1 (- B A)) ;délka seznamu (lambda (i) (+ i A))))) ;index seznamu i + A
(rozsah 7 23)
Příklad 27: Generování násobků čísla od A do B.
(define nasobky (lambda (A B) (build-list (+ 1 (- B A)) (lambda (i) (* (+ i A ) 3)))))
(nasobky 1 10)
Příklad 28: Vymazání N-tého prvku seznamu. Procedura vypíše prvky před pozicí N a za pozicí N. Není vytvořena podmínka pro výpis samotné pozice N. Nic se tedy nemaže ale spíše se tvoří z původního seznamu seznam nový.
(define vymaz (lambda (L N) ;L seznam, N pozice (build-list (- (length L) 1) ;délka seznamu L -1 (lambda (i) ;i prvek seznamu (if (< i N) ;pokud prvek v seznamu před pozicí N (list-ref L i) ;vypíše prvek na pozici seznamu L (list-ref L (+ i 1))))))) ;jinak vypíše další prvek
(define seznamX '(0 1 2 3 4 5 6 7 8 9 10)) (define seznamY '(1 2 3 4 5 6 7 8 9 10 11))
(vymaz seznamX 7) ;seznam pocita od 0 (vymaz seznamY 7) ;seznam pocita od 0
Příklad 29: Přidání nového prvku do seznamu na N-tou pozici.
(define pridej (lambda (L N prvek) (build-list (+ (length L) 1) (lambda (i) (cond ((< i N) (list-ref L i)) ((= i N) prvek) (else (list-ref L (- i 1))))))))
(define SEZ '(0 1 2 3 4 5 6 7 8 9 10))
(pridej SEZ 2 'XX) (pridej SEZ 2 '77)
Aplikace procedury mezi prvky seznamu:
(apply)
(apply procedura seznam)
Příklad 30: Aplikace procedury mezi prvky seznamu.
(define Sez1 '(0 1 2 3 4 5)) (define Sez2 '(1 2 3 4 5))
(apply + Sez1) ;výsledek 15 (apply * Sez1) ;výsledek 0 (apply * Sez2) ;výsledek 120
Filtrování seznamu:
(filter)
(filter podmínka seznam)
Příklad 31: Filtrování sudých a lichých čísel seznamu.
(define Seznam '(0 1 2 4 5 26 27 28 29 30))
(filter even? Seznam) (filter odd? Seznam)
