Scheme

Scheme

Paradigma:	funkcionální programování
Vznikl v:	1975
Autor:	Guy L. Steele a Gerald Jay Sussman
Typování:	silné, dynamické
Hlavní implementace:	PLT Scheme, MIT/GNU Scheme, Scheme 48, Chicken, Gambit, FLUENT, Guile, Bigloo, Chez Scheme, STk, STklos, Larceny, SCM
Dialekty:	T

Scheme je multiparadigmatický programovací jazyk. Funkcionální programovací paradigma patří mezi tzv. deklarativní 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ý Revisedⁿ Report on the Algorithmic Language Scheme, ve zkratce RⁿRS, kde n je číslo revize. Současný standard je R⁵RS^[2], a R⁶RS^[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.

[editovat] Původ

Na počátku zrodu jazyka Scheme stála potřeba Guye Steela a Geralda Sussmana z MIT (Massachussetský 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 sní 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 zprava popisovala vývoj jazyka, poté co byla MIT implementace rozšířena o podporu inovativního kompileru. Další zpráva, která byla nazvána "Revize revize reportu Scheme, neboli neobvyklý LISP" byla publikována v roce 1985. Tradice revizi revize revize se zachovala a dnes je jiz 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 tohoto název Scheme, který tak nahradil Schemer.

[editovat] Budoucnost

Nový standardizační proces začal na 2003 Scheme workshopu, s cílem vytvoření R⁶RS standardu v roce 2006. R⁶RS přinese standardní modulární systém; povolí dělit mezi jádrem jazyka a knihovnami. Koncept R⁶RS specifikace (žertovně pojemovaný "R^5.91RS") byl uvolněn k testování v říjnu 2006. Aktualizovaný koncept, R^5.92RS, byl uvolněn 19. ledna 2007, a další, R^5.93RS, 22.března 2007. Poslední koncept je R^5.95RS a byl uvolněn 25. června 2007.

[editovat] Ukázka kódu

Tradič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)
  (define (iter nn result)
    (if (= nn 0)
      result
      (iter (- nn 1) (* result nn))))
  (iter n 1))

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í fce. a interpretr, může zahodit obsah zásobníku a znovu zavolat funkci. Tzn. že výpočet funkce probíhá v konstantní paměťovém prostoru. Standard jazyka Scheme R5RS, přesně definuje, kdy dojde ke koncovému volání.

[editovat] Elementy jazyka

[editovat] Komentáře

Kaž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 #|…|#.

[editovat] Identifikátory

• extrémně volná pravidla;
• mohou obsahovat:
  • písmena a–z, A–Z ;
  • číslice;
  • znaky ? ! . + – / < = > : $ % ^ & _ ~
• nesmí obsahovat závorky;

příklady:

 x3, prumerny-plat, Maximum, ?$*

[editovat] Konvence pro identifikátory

• jména predikátů (vracejí pravdivostní hodnotu) končí otazníkem, např. number?;
• jména procedur s vedlejšími efekty (např. změna hodnoty nějaké proměnné) končí vykřičníkem, např. pridej-prvek!;
• procedury konvertující jeden typ na druhý bývají pojmenovány typ1->typ2.

[editovat] Čísla

• celá: 160, +24, –78;
• racionální (zlomky): 1/2, –29/30;
• s plovoucí řádovou čárkou: 3.14, .33, –7.689e4;
• komplexní: 3+2i;
• nemá přísnou typovou kontrolu ani typované proměnné, výpočet může kombinovat několik typů.

[editovat] Řetězce

Řetězce jsou uzavřeny do dvojitých uvozovek: "ahoj světe".

[editovat] Pravdivostní hodnoty

• true a false zapisovány jako #t a #f
• revidovaná specifikace umožňuje místo #f používat ve stejném významu i prázdný seznam ()

[editovat] Dvojice

Zá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

[editovat] Seznamy

Seznamy 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 : ((1) (2 (3 4) 5 6) 7 ((8))). Všechny seznamy mají konečnou délku a jsou ukončeny prázdným seznamem.

• prázdný seznam je reprezentován konstantami nil, ()
  • seznam s jedním prvkem: (cons 1 () )
• neprázdný seznam je dvojice hlava (první prvek) a ocas (seznam zbylých prvků), anglicky head a tail
  • uzavřen do závorek, prvky oddělovány mezerami: (a b c), (12 "šroubek" .8)

• procedura list: konstrukce seznamu, s proměnným počtem argumentů.

> (list 1 2 3)
(1 2 3)

K přistupování k hodnotám v seznamu slouží funkce car a cdr.

• car - vrací první prvek v seznamu (hlavičku), seznam musí být nenulový;
• cdr - vrací zbytek seznamu (ocásek), pokud seznam obsahuje jediný prvek, vrací prázdný seznam;
• příklad: zisk třetího prvku seznamu: (car (cdr (cdr x))).

[editovat] Procedury pro seznamy

• (list? x) je x seznam?
• (pair? x) je x pár?
• (null? x) je x prázdný seznam?
• (list operandy) vyhodnotí operandy a vytvoří seznam obsahující výsledky vyhodnocení
  • (list 6 (* 3 5) 'a) vytvoří seznam (6 15 a)
• (length seznam) počet prvků seznamu
• (append seznam1 seznam2 seznam3 …) spojí seznamy do jednoho
• (reverse seznam) obrátí pořadí prvků v seznamu

[editovat] 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))))))
 
;vrati n-ty prvek ze seznamu
(define (nprvek c s)
  (if (= c 1) (car s)
      (nprvek (- c 1) (cdr s))))
(nprvek 5 '(jan ales marketa petr josef))
 
;spojeni seznamu - vzdy prvni prvek s prvnim
(define (spoj-prvni s1 s2)
  (if (or (null? s1) (null? s2)) '()
      (begin
      (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))

[editovat] Proměnné

• dynamicky typované
• uvozeny výrazem define.

  (define var1 value)

Výraz define je ekvivalent k výrazu let, jehož tělo je zbytek aktuálního oboru platnosti proměnné.

  (let ((var1 value))
    ...
    ; scope of var1
    ...)

let je pouze konvenční syntaxe, která není nezbytná a může být přímo nahrazena použitím procedury. Například kód výše je přímým ekvivalentem zápisu:

  ((lambda (var1)
    ...
    ; scope of var1
    ...) value)

[editovat] Procedury

1 (define fun
   (lambda (arg1 arg2)
     ...))
2 (define (fun arg1 arg2)
   ...)
3 (fun value1 value2)

Procedury jsou ve Scheme first-class objekty. Můžou 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 lambda formami. Například procedury se dvěma argumenty arg1 jsou definovány na řádku 1, řádek 2 je kratší, ekvivalentní výraz. Řádek 3 ukazuje jak jsou procedury spouštěny. Na prvním místě je název procedury a zbytkem jsou její argumenty.

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ředdefinové funkce jazyka Scheme. To zahrnuje např. +, -, *, /, set!, car, cdr, a další. V různých variacích Scheme může uživatel redefinovat primitivum. Příklad:

(define (+ x y)
  (- x y))

nebo jednoduše

(define + -)

což způsobí, že + primitivum provede rozdíl namísto součtu.

[editovat] Cykly

Cykly ve Scheme neexistují a jejich úlohu přebírá použití rekurze.

[editovat] Rovnost

Scheme rozlišuje tři druhy rovnosti: "eq?" vrací #t jestliže jeho parametry reprezentují stejné datové objekty v paměti; "eqv?" je to samé jako eq?, ale zachází s některými objekty (např. znaky a čísly) speciálně tak, že čísla, která jsou si = jsou také eqv? pouze když nejsou eq?; equal? porovnává dtové struktury jako seznamy, vektory, řetězce k zjištění, že mají stejnou strukturu a eqv? obsah.

V Scheme dále existují: string=?; porovnání řetězců; char=? porovnání znaků; = porovnání čísel

[editovat] Řídící struktury

[editovat] Vyhodnocování podmínek

Pro 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.

Použití if:

(if test then-expr else-expr)

Výraz test je vyhodnocen takto: jestliže výsledek vyhodnocení je „true“ (což je něco jiného nežli #f), pak je vyhodnocen výraz then-expr, jinak else-expr.

Použití cond:

(cond (test1 expr1 ...)
      (test2 expr2 ...)
      ...
      (else exprn))

První výraz, který bude true, bude vyhodnocen, jestliže všechny výsledky jsou #f, pak je vyhodnocena else klauzule.

[editovat] Input/output

Scheme užívá konceptu portů pro čtení a zápis. R⁵RS definuje dva defaultní porty, přístupné pomocí funkcí current-input-port a current-output-port, což koresponduje s Unixovými pojmy stdin and stdout. Mnoho implementací poskytuje též current-error-port.

[editovat] Související články

• Rekurze
• Prolog (programovací jazyk)
• Logické programování
• Deklarativní programování
• GIMP

[editovat] Externí dokazy

• oficiální stránky jazyka Scheme
• www.schemers.org - informace, reference jazyka,
• Skripta k Paradigmata programování — Scheme
• Teach yourself Scheme in fixnum days - velmi dobrá online učebnice Scheme
• Přednášky a cvičení pro podporu předmětu „Alternativní metody programování“ - na TUL Liberec
• r6rs.org
• Online verze Lambda Papers (PDF format)

[editovat] Reference

1. ↑ The Original 'Lambda Papers' [online]. . Dostupné online.
2. ↑ R⁵RS Revised⁵ Report on the Algorithmic Language Scheme [online]. 2007-6-25. Dostupné online. (anglicky)
3. ↑ R⁶RS R6RS.org [online]. . Dostupné online.