|
Scheme
Scheme je multiparadigmatický programovací jazyk. Funkcionální programovací paradigma patří mezi tzv. funkcionální paradigmata. Scheme je jeden ze dvou hlavních dialektů funkcionálního programovacího jazyka Lisp. Jazyk navrhli Guy Lewis Steele a Gerald Jay Sussman a jeho první popis byl sepsán v roce 1975. Scheme byl představen akademickému světu skrze sérii článků, nyní známých jako Sussmanovy a Steelovy Lambda Papers.[1] Jazyk Scheme definují dva standardy: oficiální IEEE standard a standard nazývaný Revisedn Report on the Algorithmic Language Scheme, ve zkratce RnRS, kde n je číslo revize. Současný standard je R5RS[2], a R6RS[3] je ve vývoji. Oproti Lispu se Scheme snaží o minimalismus – poskytovat co nejmenší počet základních funkcí, na nichž jsou pak v knihovnách postaveny složitější konstrukce. Díky tomu má dosud poslední reference jazyka jen 50 stran. Scheme byl prvním dialektem Lispu, který nabízel volbu mezi lexikálním nebo dynamickým rozsahem platnosti proměnné. Také byl jedním z programovacích jazyků, který podporoval „first-class continuation“. Tento jazyk je v praxi používaný jen zřídka, používá se především ve školách pro výuku programování algoritmů. Nejznámější implementací je grafický editor GIMP, jehož dodatečné zásuvné moduly a skripty jsou psány v dialektu jazyka Scheme. PůvodNa počátku zrodu jazyka Scheme stála potřeba Guye Steela a Geralda Sussmana z MIT (Massachusettský technický institut), vyzkoušet si některé aspekty modelu aktorů, který v roce 1973 veřejnosti představil Carl Hewitt. Protože LISP se k tomuto příliš nehodil, bylo potřeba navrhnout nový jazyk. Ten byl nakonec implementován v LISPu. A dokonce i syntaxí LISP hodně připomínal. Byl však o dost jednodušší, a odstraňoval některé z nepříjemných vlastností LISPu. "Chceme lépe porozumět Hewittovu Aktor modelu, ale máme problémy vztáhnout aktor model a jeho neobvyklou terminologii známých programových notací. Plánovali jsme zkonstruovat ukázkovou implementaci aktor jazyka tak, abychom si s ní mohli hrát. Použitím MacLisp, jakožto pracovního prostředí, jsme napsali tenký interpret Lispu a poté přidali mechanismus k vytváření aktorů a posílání zpráv.„ Poprvé byl jazyk Scheme veřejně popsán v roce 1975 v práci Sussmana a Steela “ Scheme: an interpreter for extended lambda calculus". V roce 1976 pak Sussman a Steele napsali dvě publikace "LAMBDA: The Ultimate Imperative" a "LAMBDA: The Ultimate Declarative", v nichž popsali, jak řešit běžné programové konstrukce. V roce 1978 byl jazyk Scheme standardizován. Základem se stala "Revidovaná zpráva o Scheme" – dialektu LISPu. Tato zpráva popisovala vývoj jazyka, poté co byla MIT implementace rozšířena o podporu inovativního kompilátoru. Další zpráva, která byla nazvána "Revize revize reportu Scheme, neboli neobvyklý LISP" byla publikována v roce 1985. Tradice revizí revize revize se zachovala a dnes je již na světě poslední pátá revize z února roku 1998. Původní název jazyka byl Schemer. Po vzoru dobových jazyků pro umělou inteligenci Planner a Conniver. Protože však autoři používali operační systém ITS, který limitoval délku souborů a adresářů šesti znaky, byly vždy soubory pro Schemer uloženy v adresáři Scheme. Z toho vzešel název Scheme, který tak nahradil Schemer. BudoucnostNový standardizační proces začal na 2003 Scheme workshopu, s cílem vytvoření R6RS standardu v roce 2006. R6RS přinese standardní modulární systém; povolí dělit mezi jádrem jazyka a knihovnami. Koncept R6RS specifikace (žertovně pojmenovaný "R5.91RS") byl uvolněn k testování v říjnu 2006. Aktualizovaný koncept, R5.92RS, byl uvolněn 19. ledna 2007, a další, R5.93RS, 22. března 2007. Poslední koncept je R5.95RS a byl uvolněn 25. června 2007. Ukázka kóduTradiční program hello world vypadá v jazyce Scheme třeba takto: (define (hello)
(display "Ahoj svete!")
(newline))
(hello)
Na prvním řádku začíná definice procedury hello, která vypíše text „Ahoj svete!“ a odřádkuje. Na čtvrtém řádku je pak tato procedura zavolána. Příkaz define slouží také k definici proměnných: (define pi 3.14)
Následující příklad ukazuje definici funkce, která vypočítá faktoriál zadaného čísla: (define fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1))))))
Psaní konstrukce lambda může být zdlouhavé, a tak Scheme nabízí zkratku: (define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
Funkci pak lze zavolat: (fact 4)
Na výstupu bychom dostali číslo 24. Výše uvedený příklad ukazuje několik zajímavých konstrukcí. Jednak je zřejmé, že v jazyce Scheme se používá prefixového zápisu: (+ 1 2) ; součet
(- 5 3) ; rozdíl
(* 4 5) ; součin
(/ 9 3) ; podíl
(+ 1 3 7) ; není třeba se omezovat na dvě čísla
Druhou zajímavou věcí je podmínka if. Ta má tvar (if (výraz) true false), kde větev true se provede, je-li výraz pravdivý (není-li vyhodnocen jako #f), větev false v případě, že je výraz nepravdivý (#f; ekvivalentní části else v jiných jazycích). Třetí zajímavou věcí je rekurzivní volání sebe sama na pátém řádku definice funkce. Funkci pro výpočet faktoriálu lze přepsat: (define (fact n)
(let fact-iter ((n n)
(result 1))
(if (= n 0)
result
(fact-iter (- n 1) (* n result)))))
V takovém to případě budou všechna rekurzivní volání koncově rekurzivní. Průběžné hodnoty nejsou ukládány na zásobník, ale jsou předávány jako argumenty rekurzivní funkce a interpret, může zahodit obsah zásobníku a znovu zavolat funkci. Tzn. že výpočet funkce probíhá v konstantním paměťovém prostoru. Standard jazyka Scheme R5RS, přesně definuje, kdy dojde ke koncovému volání. V ukázce kódu je také použitá konstrukce „pojmenovaný let“, která se používá na vytvoření rekurze v těle funkce, aniž bychom explicitně definovali funkci v globálním prostředí. To lze také za pomoci lambda výrazů: (define fact
((lambda (f) (f f))
(lambda (self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))))
Elementy jazykaKomentářeKaždý komentář je uvozen středníkem (;) a je platný po celý zbytek řádku. Některé implementace dovolují zakomentovat více řádků, obalí-li se do #|…|#. Identifikátory
x3, prumerny-plat, Maximum, ?$* Konvence pro identifikátory
Čísla
ŘetězceŘetězce jsou uzavřeny do dvojitých uvozovek: "ahoj světe". Pravdivostní hodnoty
DvojiceZákladem jazyka Scheme jsou tečkové páry. Je to (jediná) složená datová struktura s konstruktorem cons a selektory car a cdr [kudr]. Tečkový pár může například reprezentovat 2D souřadnice, imaginární číslo, nebo české a cizí slovo ve slovníku. > (define a (cons 1 2))
> a
(1 . 2)
> (car a)
1
> (cdr a )
2
SeznamySeznamy jsou definovány rekurzivně pomocí dvojic. Každý seznam je definován jako posloupnost tečkových párů, přičemž poslední tečkový pár má na své druhé pozici prázdný seznam. > (cons 1 (cons 2 (cons 3 ())))
(1 2 3)
Mohou obsahovat atomické hodnoty i další seznamy. Lze je vnořovat :
> (list 1 2 3)
(1 2 3)
K přistupování k hodnotám v seznamu slouží funkce car a cdr.
Procedury pro seznamy
Další ukázky práce se seznamy;odstraneni prvniho vyskytu prvku ze seznamu
(define (odstran-prvni p s)
(cond ((null? s) '())
((equal? p (car s)) (cdr s))
(else (cons (car s) (odstran-prvni p (cdr s))))))
;odstrani vsechny vyskyty prvku ze seznamu
(define (odstran-vsechny p s)
(cond ((null? s) '())
((equal? p (car s)) (odstran-vsechny p (cdr s)))
(else (cons (car s) (odstran-vsechny p (cdr s))))))
;; vrátí n-tý prvek ze seznamu
;; nehlídáme přitom, zda je index mimo seznam
(define (nprvek index seznam)
(if (= index 0) (car seznam)
(nprvek (- index 1) (cdr seznam))))
(nprvek 4 '(jan ales marketa petr josef))
;; N-tý prvek pole včetně kontroly, zda nejsme mimo index
;; Reagovat můžeme jakkoliv -- vrátit specifickou chybu nebo třeba prázdný seznam.
(define (nprvek index seznam)
(if (>= index (length seznam))
(error "Index je mimo seznam")
(let nprvek ((index index)
(seznam seznam))
(if (= index 0)
(car seznam)
(nprvek (- index 1) (cdr seznam))))))
;spojeni seznamu - vzdy prvni prvek s prvnim
(define (spoj-prvni s1 s2)
(if (or (null? s1) (null? s2)) '()
(cons (cons (car s1) (car s2))
(spoj-prvni (cdr s1) (cdr s2)))))
(odstran-prvni 'ivan '(jan ales libor tomas radek petr ivan ivan))
(odstran-vsechny 'ivan '(jan ales libor tomas radek petr ivan ivan ivan ivan))
(spoj-prvni '(milos ales petr jan alan) '(janicek novak kral novotny klaus havel))
;; Možná implementace funkce map beroucí pouze jeden seznam
(define (my-easy-map funkce seznam)
(if (null? seznam)
'()
(cons (funkce (car seznam))
(my-easy-map funkce (cdr seznam)))))
(my-easy-map - '(1 2 3 4 5 6))
; Vrátí: (-1 -2 -3 -4 -5 -6)
Proměnné
(define var1 value)
Výraz (let ((var1 value))
...
; scope of var1
...)
Rozdíl mezi (let ((a 10))
(cons
(let ((a 20))
(define a 30)
a)
a))
První
((lambda (var1)
...
; scope of var1
...) value)
Procedury1 (define fun
(lambda (arg1 arg2)
...))
2 (define (fun arg1 arg2)
...)
3 (fun value1 value2)
Procedury jsou ve Scheme first-class objekty. Mohou být argumenty jiných procedur a mohou být jinými procedurami vraceny. Mohou být přiřazeny do proměnné. Procedury jsou tvořeny V Scheme jsou procedury rozděleny do dvou základních kategorií: uživatelské procedury a primitiva (primitivní procedury). Všechna primitiva jsou procedury, ale ne všechny procedury jsou primitiva. Primitiva jsou předdefinované funkce jazyka Scheme. To zahrnuje např. (define (+ x y)
(- x y))
nebo jednoduše (define + -)
což způsobí, že CyklyCykly ve standardu Scheme neexistují, ale v různých implementacích se můžeme setkat například s cyklem (do ((<proměnná1> <výchozí hodnota 1> <změna1>)
(<proměnná2> <výchozí hodnota 2> <změna2>)
... )
(<test1> <test2>)
<příkaz1>
<příkaz2>
... )
Nejdříve následuje seznam proměnných, které budou iterovat, včetně výchozí hodnoty a indikátoru změny po každé iteraci. Jako druhý argument je uvedena ukončující podmínka cyklu. Ve chvíli, kdy je splněna, je cyklus ukončen. Následuje seznam příkazů, které se mají v cyklu provést. Příklad jednoduchého cyklu, který vytiskne čísla od jedné do devíti: (do ((x 1 (+ x 1)))
((= x 10))
(print x)
(newline))
Příklad cyklu procházející seznam: (do ((x '(1 2 3 4 5 6) (cdr x)))
((null? x))
(print (car x))
(newline))
RovnostScheme rozlišuje tři druhy rovnosti: " V Scheme dále existují: Řídící strukturyVyhodnocování podmínekPro vyhodnocování podmínek nabízí Scheme tři speciální formy. If, case a cond. If se až na formu zápisu nijak neliší od if, které používá většina ostatních jazyků. Forma cond dovoluje použít libovolné množství podmínek a návratovou hodnotu pro každou z nich. Forma case je podobná formě cond postupně vyhodnocuje seznamy a pokud nalezne odpovídající prvek, vrátí jeho příslušnou hodnotu.
(if test then-expr else-expr)
Výraz Použití (cond (test1 expr1 ...)
(test2 expr2 ...)
...
(else exprn))
První výraz, který bude true, bude vyhodnocen, jestliže všechny výsledky jsou Vstup/VýstupScheme užívá konceptu portů pro čtení a zápis. R5RS definuje dva výchozí porty, přístupné pomocí funkcí MakraScheme zná makra, což je velice mocná zbraň v rukou programátora. Makra transformují zdrojový kód, makroexpanzi provádí preprocesor a samotný interpret už žádná makra nevidí, vidí pouze hotový zdrojový kód, který je určen ke zpracování. Pomocí maker si programátor může dovolit různé věci, které by jinak nebyl schopný provést. První příklad bude anaforický if, který se chová podobně jako klasický if, pouze si výsledek podmínky uchovává do symbolu (define-macro aif
(lambda (cond true false)
`(let ((it ,cond))
(if it
,true
,false))))
;; Příklady použití
(aif (+ 5 5) it #f)
; 10
(aif (member 3 '(1 2 3 4 5 6)) it #f)
; (3 4 5 6)
Další příklad je makro (define-macro (dolist instrukce . telo)
(let ((symbol (car instrukce))
(seznam (cadr instrukce))
(iter (gensym)))
`(do ((,iter ',seznam (cdr ,iter))
(,symbol (car ',seznam)))
((null? ,iter))
(set! ,symbol (car ,iter))
,@telo)))
;; Příklady použití
(dolist (x (1 2 3 4 5 6)) (print x) (newline))
V příkladu také vidíme funkci (define-macro (dolist-ugly instrukce . telo)
(let ((symbol (car instrukce))
(seznam (cadr instrukce)))
`(do ((iter ',seznam (cdr iter))
(,symbol (car ',seznam)))
((null? iter))
(set! ,symbol (car iter))
,@telo)))
;; Příklad volání, kdy pocítíme symbol capture
(dolist-ugly (x (1 2 3 4)) (print iter))
; Vrátí: (1 2 3 4)(2 3 4)(3 4)(4) Přičemž by to mělo zobrazit chybu na neexistující symbol.
Příklady dalších užitečných maker: ;; Makro when se chová podobně jako if, pouze nemá žádnou else větev.
;; V případě, že podmínka není splněna, automaticky vrátí false.
;; True větev ale může obsahovat více výrazů.
(define-macro (when cond . true)
`(if ,cond
(begin
,@true)
#f))
; Příklady použití:
(when 1 2)
; 2
(when 1 (print 1) 2)
; 12
(when #f (print 1) 2)
; #f
;; Makro unless se chová opačně než makro when — neguje podmínku.
;; True větev se tudíž provede, není-li splněna předaná podmínka.
;; Prakticky to lze přepsat jako (when (not <podmínka>) ...).
(define-macro (unless cond . true)
`(if (not ,cond)
(begin
,@true)
#f))
; Příklady použití:
(unless 1 2)
; #f
(unless 1 (print 5) 10)
; #f
(unless (= 1 2) (print 5) 10)
; 510
Hezkým příkladem jsou také podmíněné výrazy pracující s pravděpodobností. Například klasický if upravený tak, že namísto podmínky přebírá pouze procentuální vyjádření pravděpodobnosti, zda se provede true větev. (define-macro (prob-if probability true false)
`(if (<= (+ 1 (random 100)) ,probability)
,true
,false))
; Příklady použití:
; (V 80 % případů se vrátí jednička, ve 20 % dvojka.)
> (prob-if 80 1 2)
1
> (prob-if 80 1 2)
1
> (prob-if 80 1 2)
1
> (prob-if 80 1 2)
2
> (prob-if 80 1 2)
1
> (prob-if 80 1 2)
1
StreamyPomocí maker můžeme také realizovat líné vyhodnocování, kdy se veškeré argumenty funkcí budou vyhodnocovat líně, tj. až když budou třeba. Díky tomuto můžeme naprogramovat if jako funkci. Líného vyhodnocení využijeme i při implementaci Streamů. Stream bude tvořen tečkovými páry, ale s tím rozdílem, že bude mít vyhodnocen pouze car část, nikoli cdr. To realizujeme tím způsobem, že cdr část uložíme jako proceduru, kterou vyhodnotíme až při volání cdr streamu: (define-macro (delay . expr)
`(lambda() ,@expr))
; Příklady použití
> (delay (print 100) (newline) (* 50 50))
#<procedure>
> (define d (delay (print 100) (newline) (* 50 50)))
> d
#<procedure:d>
> (d)
100
2500
Pomocí makra (define-macro (cons-stream car-str cdr-str)
`(cons ,car-str
(delay ,cdr-str)))
(define stream-car car)
(define (stream-cdr stream)
((cdr stream)))
A nyní už jen aplikace streamů: ;; Vrací nekonečný proud jedniček
(define (ones)
(cons-stream 1 (ones)))
> (ones)
(1 . #<procedure>)
> (stream-cdr (ones))
(1 . #<procedure>)
> (stream-cdr (stream-cdr (stream-cdr (stream-cdr (ones)))))
(1 . #<procedure>)
;; Vrací nekonečný proud přirozených čísel
(define (naturals n)
(cons-stream n (naturals (+ n 1))))
> (naturals 1)
(1 . #<procedure>)
> (stream-cdr (naturals 1))
(2 . #<procedure>)
> (stream-cdr (stream-cdr (stream-cdr (stream-cdr (naturals 1)))))
(5 . #<procedure>)
Související článkyExterní odkazy
Reference
|
||||||||||||||||||
