Scheme

Schemejemultiparadigmatickýprogramovací jazyk. Funkcionální programovací paradigma patří mezi tzv.funkcionální paradigmata. Scheme je jeden ze dvou hlavních dialektůfunkcionálníhoprogramovacího jazykaLisp. Jazyk navrhli Guy Lewis Steele a Gerald Jay Sussman a jeho první popis byl sepsán v roce1975.
Scheme byl představen akademickému světu skrze sérii článků, nyní známých jako Sussmanovy a SteelovyLambda Papers.Jazyk Scheme definují dva standardy: oficiálníIEEEstandard a standard nazývanýRevisedReport on the Algorithmic Language Scheme, ve zkratce RRS, kdenje číslo revize. Současný standard jeRRS, aRRSje 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-classcontinuation“.
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ý editorGIMP, jehož dodatečné zásuvné moduly a skripty jsou psány v dialektu jazyka Scheme.
Na 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 modeluaktorů, který v roce 1973 veřejnosti představilCarl 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 HewittovuAktormodelu, 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 implementaciaktorjazyka tak, abychom si s ní mohli hrát. Použitím MacLisp, jakožto pracovního prostředí, jsme napsali tenkýinterpretLispua 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 inteligenciPlanneraConniver. Protože však autoři používali operační systémITS, 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.
Nový standardizační proces začal na 2003 Scheme workshopu, s cílem vytvoření RRS standardu v roce 2006.
RRS přinese standardní modulární systém; povolí dělit mezi jádrem jazyka a knihovnami.
Koncept RRS specifikace (žertovně pojmenovaný "RRS") byl uvolněn k testování v říjnu 2006.
Aktualizovaný koncept, RRS, byl uvolněn 19. ledna 2007, a další, RRS, 22. března 2007. Poslední koncept je RRS a byl uvolněn 25. června 2007.
Tradiční programhello worldvypadá v jazyce Scheme třeba takto:
Na prvním řádku začíná definice proceduryhello, 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:
Následující příklad ukazuje definici funkce, která vypočítáfaktoriálzadaného čísla:
Psaní konstrukcelambdamůže být zdlouhavé, a tak Scheme nabízí zkratku:
Funkci pak lze zavolat:
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:
Druhou zajímavou věcí je podmínkaif. Ta má tvar(if (výraz) true false), kde větevtruese provede, je-li výraz pravdivý (není-li vyhodnocen jako#f), větevfalsev případě, že je výraz nepravdivý (#f; ekvivalentní částielsev jiných jazycích).
Třetí zajímavou věcí jerekurzivnívolání sebe sama na pátém řádku definice funkce. Funkci pro výpočet faktoriálu lze přepsat:
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 SchemeR5RS, 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ů:
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 #|…|#.
příklady:
Řetězce jsou uzavřeny do dvojitých uvozovek: "ahoj světe".
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.
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.
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.
K přistupování k hodnotám v seznamu slouží funkce car a cdr.
Výrazdefinemodifikuje vazbu symbolu v aktuálním prostředí. Oproti tomu speciální formaletvytváří nové prostředí (scope) a v tomto prostředí navazuje na symboly nové vazby.letjako takový nedokáže přepsat již existující vazbu, vždy pouze vytváří nová prostředí. To je hlavní rozdíl oproti speciální formědefine, který dokáže přepsat existující vazby.
Rozdíl meziletadefinemůžeme zčásti ilustrovat na následujícím příkladu:
Prvníletvytvoří své prostředí, ve kterém naváže naahodnotu 10. Druhý let také vytvoří prostředí a naváže naahodnotu 20. Pokud bychom nepoužilidefine, byl by výsledkem operace tečkový pár20 . 10, protože sice existují dva symbolya, ale v jiných prostředí, kde mají vlastní vazbu.defineale modifikuje vazbu v aktuálním prostředí, takže ve vnořeném vnitřním letu změní vazbu symboluana třicet. Výsledkem operace tak bude tečkový pár30 . 10.
letje 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:
Procedury jsou ve Schemefirst-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řenylambdaformami. Například procedury se dvěma argumentyarg1jsou 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ředdefinované 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:
nebo jednoduše
což způsobí, že+primitivum provede rozdíl namísto součtu.
Cykly ve standardu Scheme neexistují, ale v různých implementacích se můžeme setkat například s cyklemdo. Ačkoliv programujeme-li funkcionálně, cykly nevyužijeme, protože jsou založené na vedlejším efektu. Častěji se používá rekurze. Syntaxe cykludoje následující:
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:
Příklad cyklu procházející seznam:
Scheme rozlišuje tři druhy rovnosti: "eq?" vrací#tjestliže jeho parametry reprezentují stejné datové objekty v paměti; "eqv?" je to samé jakoeq?, 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ž nejsoueq?;equal?porovnává datové struktury jako seznamy, vektory, řetězce k zjištění, že mají stejnou strukturu aeqv?obsah.
V Scheme dále existují:string=?; porovnání řetězců;char=?porovnání znaků;=porovnání čísel
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:
Výraztestje vyhodnocen takto: jestliže výsledek vyhodnocení je „true“ (což je něco jiného nežli#f), pak je vyhodnocen výrazthen-expr, jinakelse-expr.
Použitícond:
První výraz, který bude true, bude vyhodnocen, jestliže všechny výsledky jsou#f, pak je vyhodnocenaelseklauzule.
Scheme užívá konceptuportůpro čtení a zápis. RRS definuje dva výchozí porty, přístupné pomocí funkcícurrent-input-portacurrent-output-port, což koresponduje s Unixovými pojmy stdin and stdout. Mnoho implementací poskytuje téžcurrent-error-port.
Scheme 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 symboluit, takže v těle anaforického ifu se můžeme lehce odkázat na výsledek podmínky:
Další příklad je makrodolist, které provádí iteraci přímo nad seznamem. Bere jako argument iterační symbol, do kterého se bude vždy ukládat hodnota aktuálně procházeného prvku seznamu, seznam samotný a pak tělo.
V příkladu také vidíme funkcigensym, která slouží ke generování náhodných proměnných, ke kterým nemá uživatel přístup. Slouží to k ochraně před tzv.„symbol capture“, což nastává v případě, kdy makro potřebuje nějakou vnitřní pomocnou proměnnou. Pokud bychom nepoužili náhodný symbol, mohl by uživatel k tomuto symbolu přistupovat. Špatně definované makrodolistby mohlo vypadat takto:
Příklady dalších užitečných maker:
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.
Pomocí 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:
Pomocí makradelayjsme odložili vyhodnocení výrazů(print 100) (newline) (* 50 50)až do chvíle, kdy jsme to opravdu potřebovali — když jsme zavolali(d). Zbytek už nadefinujeme snadno:
A nyní už jen aplikace streamů: