Scheme (programovací jazyk)

Z Wikipédie

Scheme je funkcionálny programovací jazyk a je dialektom jazyka LISP. Vyvinuli ho Guy L. Steele a Gerald Jay Sussman v 70. rokoch 20. storočia najprv ako pokus o pochopenie Actor modelu a predstavili ho akademickému svetu pomocou série článkov, ktoré sú v súčastnosti označované Sussmanové a Steeleové Lambda články. Implementácie sa zvyknú líšiť v malých detailoch, preto je Scheme občas označovaný ako rodina tesne príbuzných programovacích jazykov.

Filozofia jazyku Scheme je nehanebne minimalistická. Jej cieľom nie je nahádzať jednu črtu na druhú, ale odstrániť slabosti a obmedzenia, ktoré spôsobujú, že nové črty vyzerajú byť potrebné. Preto Scheme poskytuje čo najmenší počet základných pojmov a kdekoľvek to je praktické v implementácií, snaží sa aby všetko ostatné bolo poskytované programovacími knižnicami, ktoré sú vybudované nad týmito základnými pojmami. Napríklad hlavný mechanizmus pre ovládanie toku riadenia je rekurzia na chvoste.

Scheme bol prvý dialekt jazyku Lisp, ktorý si zvolil statický (známy aj ako lexikálny) pred dynamický rozsahom platnosti premenných. Bol jedným z prvých programovacích jazykov s podporou explicitných pokračovaní. Scheme taktiež podporuje Automatickú správu pamäte.

Jazyk Scheme používa ako základnú údajovú štruktúru zoznam, ale podporuje aj vektory. Vzhľadom na svoj minimalistický návrh, neexistuje štandardná syntax pre vytváranie štruktúr s pomenovanými položkami, alebo pre objektovo orientované programovanie, ale veľa implementácií má takéto možnosti.

Obsah 1 Štandardy 2 Časti jazyka 2.1 Komentáre 2.2 Premenné 2.3 Funkcie 2.4 Zoznam 2.5 Údajové typy 2.6 Rovnosť 2.7 Riadiace štruktúry 2.7.1 Podmienené vyhodnocovanie 2.7.2 Cykly 2.8 Vstup/Výstup 3 Pozri aj 4 Literatúra

[úprava] Štandardy

Sú dva štandardy, ktoré definujú jazyk Scheme: oficiálny IEEE štandard a de facto štandard nazývaný Revisedⁿ Report on the Algorithmic Language Scheme takmer vždy skracovaný ako RnRS, kde n je číslo revízie. Posledná RnRS verzia (v januári 2006) je R5RS, je dostupná online.

Štandardizačný proces nového jazyka sa začal na 2003 Scheme workshop, ktorý ma za cieľ pripraviť R6RS štandard v roku 2006. Ukončuje jednohlasný postup použitý pri predchádzajúcich RnRS štandardoch. Súčasný stav sa nachádza na [http://schemers.org/Documents/Standards/Charter/ web stránke].

Asi najdôležitejšia nová vlastnosť v R6RS bude štandardný modulový systém. To umožní rozdelenie medzi hlavný jazyk a knižnice.

[úprava] Časti jazyka

[úprava] Komentáre

Komentáre začínajú bodkočiarkou (;) a pokračujú až po koniec riadku. Komentáre rozprestierajúce sa cez viaceré riadky sú ohraničené v #|...|# (môžu byť vnorené).

[úprava] Premenné

Premenné sú dynamicky typované. Premenné sú viazané pomocou define a let výrazov a pár ďalších Scheme form. Tie premenné, ktoré sú viazané s define na najvyššej úrovni, sa nachádzajú v globálnom rozsahu platnosti.

 (define prem1 hodnota)

Rozsah platnosti pre premenné viazané pomocou let je telo let formy.

 (let ((prem1 hodnota))
   ...
   ; rozsah platnosti premennej prem1
   ...)

[úprava] Funkcie

Funkcie sú prvotriedne objekty v Scheme (dá sa s nimi manipulovať ako s ostatnými hodnotami, napríklad číslami). Môžu byť priraďované do premenných. Napríklad funkcia s dvoma argumentami arg1 a arg2 sa dá definovať ako

 (define fun
   (lambda (arg1 arg2)
     ...))

čo sa dá nasledovne skrátiť:

 (define (fun arg1 arg2)
   ...)

Aplikácia funkcie má nasledujúcu syntax:

 (fun hodnota1 hodnota2)

Všimnite si, že aplikovaná funkcia je na prvom mieste v zozname zatiaľ čo zvyšok zoznamu obsahuje argumenty. Funkcia apply zoberie prvý argument a aplikuje ho na daný zoznam argumentov, takže predchádzajúce funkčné volanie môže byť zapísané aj ako:

 (apply fun (list hodnota1 hodnota2))

V Scheme sú funkcie rozdelené do dvoch základných kategórií: procedúry a primitíva. Všetky primitíva sú procedúrami, ale nie všetky procedúry sú primitívami. Primitíva sú preddefinované funkcie jazyku Scheme. To zahŕňa +, -, *, /, set!, car, cdr a ďalšie základné procedúry. Procedúry sú používateľom definované funkcie. Vo viacerých variantoch Scheme môže používateľ predefinovať primitívum. Napríklad kód

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

predefinuje primitívum + tak, aby vykonávalo odčítanie namiesto sčítania.

[úprava] Zoznam

Scheme používa dátovú štruktúru zreťazený zoznam v rovnakej forme aká existuje v Lispe.

• list vytvorí nový zreťazený zoznam. napríklad: (list 1 2 3) (list (list 1 2) 3)
• car vráti hodnotu hlavičkového uzla zreťazeného zoznamu. napríklad: (car (list 1 2 3)) vráti 1, (car (list (list 1 2) 3) vráti (1 2)
• cdr vráti zoznam za hlavičkovým uzlom zreťazeného zoznamu. napríklad: (cdr (list 1 2 3)) vráti (2 3), (cdr (list (list 1 2) 3) vráti (3)
• cons vytvorí nový zoznam s danou car hodnotou a cdr zoznamom. napríklad: (cons 1 (list 2 3)) vráti (1 2 3), (cons (list 1 2) (list 3)) vráti ((1 2) 3)

Podrobnejšie, každý uzol zreťazeného zoznamu je cons bunkou, tiež nazývanou pár, alebo bodka-dvojica. Ako implikuje pomenovanie pár, cons bunka sa skladá z dvoch položiek: prvý ja car a druhá je cdr. Zoznam (list 1 2 3) obsahuje tri cons bunky, alebo páry. Prvá cons bunka má v prvej položke číslo 1 a v druhej položke ukazovateľ na druhú cons bunku. Druhá cons bunka má v prvej položke číslo 2 a v druhej položke ukazovateľ na druhú cons bunku. Tretia cons bunka má v prvej položke číslo 3 a v druhej položke konštantu null. Konštanta null je väčšinou reprezentovaná ako '() alebo (quote ()). Funkcia cons vytvára tieto cons bunky a preto (cons 1 (list 2 3)) vráti zoznam (1 2 3). Ak oba argumenty nie sú zoznamy, tak vytvorí pár, väčšinou reprezentovaný pomocou bodky. Napríklad (cons 1 2) vráti (1 . 2), čo je cons bunka obsahujúca čísla 1 a 2 vo svojej prvej a druhej položke

[úprava] Údajové typy

Ostatné údajové typy v jazyku Scheme okrem funkcií a zoznamov sú: celé čísla, racionálne čísla, reálne čísla,komplexné čísla, symboly, reťazce, porty. Väčšina implementácií Scheme taktiež poskytuje asociatívne zoznamy, hašovacie tabuľky, vektory, polia a štruktúry. Od vtedy ako bol vydaný IEEE štandard a R4RS štandard určuje jazyk Scheme, že všetky hore uvedené typy sú disjunktné teda, že každá hodnota nemôže byť viac než jedného typu. Avšak niektoré zastaralé implementácie jazyku Scheme anti-datujú tieto štandardy tak, že #f a '() predstavujú tú istú hodnotu, rovnako ako v prípad jazyku Common Lisp.

Väčšina implementácií Scheme poskytujú plnú číselnú vežu a taktiež presnú a nepresnú aritmetiku.

Pravda a nepravda sú reprezentované ako #t a #f. Presnejšie iba #f je nepravda a kdekoľvek je požadovaná hodnota typu Boolean, je ľubovolná iná hodnota ako #f (aj prázdny zoznam) považovaná za pravda.

Symboly sa dajú vytvárať minimálne týmito spôsobmi:

 'symbol
 (string->symbol "symbol")

[úprava] Rovnosť

Scheme ma tri rôzne typy rovnosti:

eq?

Vracia #t ak jeho parametre reprezentujú tie isté dátové objekty v pamäti.

eqv?

Vo všeobecnosti to isté ako eq?, ale zaobchádza špeciálne s niektorými objektami (napr. so znakmi a číslami), tak aby čísla ktoré sú = rovné boli aj eqv? rovné aj keď nie sú eq? rovné.

equal?

Porovnáva údajové štruktúry ako napríklad zoznamy, vektory a reťazce, aby rozhodol či majú zhodnú štruktúru a eqv? rovný obsah.

[úprava] Riadiace štruktúry

[úprava] Podmienené vyhodnocovanie

 (if test tak-výraz inak-výraz)

Výraz test je vyhodnotený a ak výsledok vyhodnotenia je pravda (čokoľvek iné ako #f), tak je vyhodnotený výraz tak-výraz, inak je vyhodnotený inak-výraz.

Forma cond je vhodnejšia, keď sú podmienky vnorené:

 (cond (test1 výraz1)
       (test2 výraz2)
       ...
       (else výrazn))

Prvý výraz, pre ktorý sa vyhodnotí test ako pravdivý, bude vyhodnotený. Ak výsledkom všetkých testov je #f tak vyhodnotená else klauzula.

Variantom cond klauzuly je

 (cond ...
       (test => výraz)
       ...)

V tomto prípade sa má výraz vyhodnotiť na jednoargumentovú funkciu. Ak je test vyhodnotený ako pravdivý, je zavolaná táto funkcia s návratovou hodnotou testu.

[úprava] Cykly

Cykly v Scheme majú väčšinou formu rekurzie na chvoste. Je požadované, aby implementácie jazyku Scheme optimalizovali rekurziou na chvoste, tak aby sa odstránilo obsadzovanie zásobníkového miesta kdekoľvek to je možné, aby bolo možné používať túto techniku pre ľubovolne dlhé cykly.

Klasickým príkladom je funkcia faktoriál, ktorá sa dá definovať bez rekurzie na chvoste.

 (define (faktoriál n)
   (if (= n 0)
     1
     (* n (faktoriál (- n 1)))))

 (faktoriál 5)
 ;; => 120

Toto je priamy preklad matematickej rekurzívnej definície faktoriálu: faktoriál nuly (väčšinou zapisovaný 0!) je rovný 1, zatiaľ čo faktoriál ľubovolného väčšieho prirodzeného čísla n je definovaný ako n! = n * (n − 1)!.

Avšak, jednoduchá rekurzia prirodzene menej efektívna, lebo Scheme systém si musí udržovať záznamy o návratoch všetkých vnorených funkčných volaní. Definícia s rekurziou na chvoste je taká, čo zaistí, že v rekurzívnom prípade naj-vonkajšie volanie priamo vracia hodnotu von z funkcie. V našom prípade nebudeme priamo rekurzívne volať funkciu faktoriál, ale pomocnú rutinu s dvoma parametrami reprezentujúcimi stav iterácie:

 (define (faktoriál n)
   (let cyklus ((spolu 1)
              (i n))
     (if (= i 0)
       spolu
       (cyklus (* i spolu) (- i 1)))))

 (faktoriál 5)
 ;; => 120

Funkcia vyššieho rádu ako napríklad map, ktorá volá funkciu na každý prvok zoznamu a môže byť definovaná bez rekurzie na chvoste:

 (define (map f zoznam)
   (if (null? zoznam)
     zoznam
     (cons (f (car zoznam))
           (map f (cdr zoznam)))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;;  => (1 4 9 16)

Toto môže byť definované aj pomocou rekurzie na chvoste:

 (define (map f zoznam)
   (let cyklus ((zoznam zoznam)
              (res '()))
     (if (null? zoznam)
       (reverse res)
       (cyklus (cdr zoznam)
             (cons (f (car zoznam)) res)))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;; => (1 4 9 16)

V oboch prípadoch je verzia s rekurziou na chvoste vhodnejšia, kvôli menšej spotrebe pamäti

[úprava] Vstup/Výstup

Jazyk Scheme obsahuje koncept brán (angl. port) na čítanie a zápis. R5RS definuje dve implicitný brány prístupné pomocou funkcií: current-input-port, current-output-port. Väčšina implementácií taktiež poskytuje bránu: current-error-port.

[úprava] Pozri aj

• Structure and Interpretation of Computer Programs, klasická učebnica informatiky s veľkým množstvom programovacích cvičení v jazyku Scheme.
• How to Design Programs od Felleisena a ďalších. Určená pre výčbu návrhu programov pomocou Scheme.

[úprava] Literatúra

• Gerald Sussman a Guy Steele. SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975.
• Richard Kelsey, William Clinger, Jonathan Rees (editory), [http://www.schemers.org/Documents/Standards/R5RS/ Revised⁵ Report on the Algo

rithmic Language Scheme]

• Guy L. Steele, Jr., Richard P. Gabriel, The Evolution of Lisp

Významné programovacie jazyky (viac)

Ada | ALGOL | APL | AWK | BASIC | C | C++ | C# | COBOL | Delphi | Eiffel | Fortran | Haskell | IDL | Java | JavaScript | Lisp | LOGO | ML | Objective-C | Pascal | Perl | PHP | PL/I | Prolog | Python | Ruby | SAS | Scheme | sh | Simula | Smalltalk | SQL | Visual Basic