'(Programovací (cons 'jazyk 'Scheme))

15. 4. 2010

Doba čtení: 13 minut

Líbí se vám článek?
Podpořte redakci

V dnešní části seriálu o historii výpočetní techniky se začneme zabývat jedním zajímavým dialektem programovacího jazyka LISP. Tento známý dialekt, který se mj. poměrně intenzivně používá při výuce programování, se jmenuje Scheme a je mimo jiné použit i ve známém grafickém editoru GIMP.

Obsah

1. Programovací jazyk Scheme – cesta k „čistšímu“ LISPu

2. Lambda Papers

3. Tajemná zkratka RnRS

4. Základní vlastnosti programovacího jazyka Scheme

5. Koncová rekurze (tail-recursion)

6. Některé rozdíly mezi LISPem a Scheme

7. Obsah následující části seriálu

8. Literatura

9. Odkazy na Internetu

1. Programovací jazyk Scheme – cesta k „čistšímu“ LISPu

V dnešní části seriálu o historii výpočetní techniky se seznámíme se základy programovacího jazyka Scheme, který je jednodušším a v některých ohledech i čistším dialektem jazyka LISP. Původními autory programovacího jazyka Scheme jsou Guy Lewis Steele a Gerald Jay Sussman (Steele and Sussman, někdy též zkracováno na S and S), kteří v době návrhu tohoto jazyka pracovali ve slavném Massachussetském technologickém institutu (MIT). První verze jazyka Scheme byla v průběhu roku 1975 naprogramována v samotném LISPu, konkrétně v MacLispu. Název tohoto dialektu programovacího jazyka LISP ovšem nemá nic společného s počítači firmy Apple, jednalo se o verzi LISPu vytvořenou taktéž na MIT, která byla původně určena pro počítače PDP-10 a operační systém Multics – viz též úvodní díly tohoto seriálu, v nichž byla stručně popsána historie vzniku operačního systému Unix i souvisejících technologií.

Guy Steele spolu s Geraldem Sussmanem chtěli nový jazyk použít pro zkoumání vlastností takzvaných aktorů, které se v dnešní době, tj. celých 35 let po vzniku jazyka Scheme, opět těší zvýšenému zájmu vědců i programátorů, především díky stále většímu důrazu na tvorbu systémů, v nichž je spouštěno velké množství paralelně běžících a vzájemně kooperujících procesů (aktory je možné považovat za speciální formu uzávěrů – closures, ostatně právě nutnost podpory uzávěrů ve Scheme poměrně zásadně ovlivnilo jeho návrh, zejména odlišný způsob určování rozsahu platnosti objektů). Výsledkem jejich snahy byl v mnoha ohledech minimalistický programovací jazyk podporující různá paradigmata programování, ovšem zaměřený především na paradigma funkcionální. Původně se tento nový programovací jazyk jmenoval SCHEMER, ovšem systém souborů používaný operačním systémem ITS na PDP-10, na němž byly uloženy zdrojové kódy interpretru, omezoval délku názvů na šest znaků, takže se postupně název zkrátil ze SCHEMER a Scheme. Oba autoři následně zveřejnili popis syntaxe a především sémantiky nového programovacího jazyka v sérii článků, které se dnes souhrnně nazývají „Lambda Papers“.

hist26

2. Lambda Papers

První článek o programovacím jazyku Scheme, který měl poměrně velký vliv na další vývoj i chápání významu programovacích jazyků z teoretického i praktického hlediska, se jmenoval „Scheme: an Interpreter for Extended Lambda Calculus“. Po tomto článku následovala dvojice neméně důležitých publikací s všeříkajícími názvy „Lambda: The Ultimate Imperative“ a „Lambda: The Ultimate Declarative“ s popisem toho, jakým způsobem je možné ve Scheme nahrazovat běžné programové konstrukce známé například z tehdy používaných imperativních programovacích jazyků (céčka, Fortranu, Algolu, posléze i Pascalu atd.). V následující tabulce jsou vypsány všechny publikace Guye Steela a Geralda Sussmana vydávané v letech 1975 až 1980, které se dnes souhrnně nazývají Lambda Papers (http://library.readscheme.org/page1.html). I přes svoje stáří jsou tyto publikace stále důležitou součástí celého oboru IT:

Rok vydání	Název publikace
1975	Scheme: An Interpreter for Extended Lambda Calculus
1976	Lambda: The Ultimate Imperative
1976	Lambda: The Ultimate Declarative
1977	Debunking the ‚Expensive Procedure Call‘ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO
1978	The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two)
1978	RABBIT: A Compiler for SCHEME
1979	Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode
1980	Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO
1980	Design of a Lisp-based Processor

3. Tajemná zkratka RnRS

Pro další vývoj programovacího jazyka Scheme byl důležitý rok 1978, kdy došlo ke vzniku jeho prvního standardu, jenž byl popsán v „Revidované zprávě o algoritmickém jazyku Scheme“ (Revised Report on the Algorithmic Language Scheme). Jazyk se samozřejmě dále vyvíjel, takže v roce 1985 vznikl další popis jeho standardu zveřejněný v dokumentu nazvaném „Revize revidované zprávy o Scheme, neboli neobvyklý LISP“. Tradice ve vydávání revizí (a revizí revizí) původní zprávy o programovacím jazyku Scheme zůstala zachována až do dnešní doby. Postupně vzniklo celkem šest revizí, což mj. znamená, že většina současných implementací tohoto programovacího jazyka odpovídá buď páté revizi („The Revised⁵ Report on the Algorithmic Language Scheme“) z roku 1998 nebo se přizpůsobuje revizi šesté („The Revised⁶ Report on the Algorithmic Language Scheme“), která byla schválena v roce 2007.

Jednotlivé zprávy (tj. vlastně faktické standardy jazyka Scheme dodržované většinou jeho implementací) se v literatuře velmi často označují pouze zkratkou RnRS, kde se za n dosazuje číslo revize. V současnosti se můžeme v různých návodech ale i odborných článcích setkat především se zkratkou R5RS označující pátou revizi či R6RS označující revizi šestou. Zajímavé je, že tyto zprávy, ač popisují prakticky všechna zákoutí jazyka Scheme i některé požadavky na jeho implementaci, mají po vytištění délku pouhých padesáti stran (vysázeny jsou T_EXem písmem Computer Modern), což mj. svědčí i o tom, že se jedná o čistě a v mnoha ohledech minimalisticky navržený jazyk (srovnejte si například padesátistránkovou R6RS s řádově rozsáhlejším standardem Common Lispu nebo normy jazyka C++). Ostatně název jedné z populárních implementací tohoto jazyka – Scheme48 – vznikl z toho, že první verze této implementace vznikla za pouhých 48 hodin.

hist26

4. Základní vlastnosti programovacího jazyka Scheme

Scheme je programovací jazyk, který podporuje různá paradigmata programování, především paradigma funkcionální (i když se nejedná o čistě funkcionální jazyk) a paradigma imperativní. Z funkcionálních jazyků se ve Scheme objevuje především koncept lambda výrazů, funkcí jakožto plnohodnotných datových typů, což mj. znamená, že funkce je možné předávat jako parametry jiným funkcím, funkce mohou být návratovými hodnotami jiných funkcí atd. Naopak z jazyků imperativních (mezi něž patří velká část v současnosti používaných programovacích jazyků) se ve Scheme objevuje bloková struktura kódu převzatá z Algolu 60, koncept globálních a lokálních proměnných s lexikální oblastí jejich platnosti (lexical scope, na rozdíl od dynamického vyhodnocování platnosti, které bylo použito v původních LISPu a teprve později se přešlo k vyhodnocování lexikálnímu) a podpora programových smyček, které se v čistě funkcionálních jazycích nahrazují rekurzí či speciálními formami, mezi něž patří například apply, map, for-each, mapcar či reduce.

5. Koncová rekurze (tail-recursion)

V naprosté většině algoritmů se objevují bloky kódu, které se mají iterativně opakovat. Při programování s využitím funkcionálního paradigmatu se iterace vyjadřuje formou rekurze. Ta je samozřejmě ve Scheme podporována (mezi jediné známější jazyky, které rekurzi nepodporovaly, patřil původní Fortran a Basic), ovšem specifikace jazyka Scheme jde ještě dále, protože určuje, ve kterých případech je skutečná rekurze (při níž se parametry a návratové adresy musí ukládat na zásobník) nahrazena takzvanou koncovou rekurzí, což zjednodušeně řečeno znamená, že se namísto skutečného rekurzivního volání funkce interně provede obyčejný skok (koncový skok či koncové volání) bez nutnosti alokace místa na zásobníku pro parametry volané funkce a návratové adresy. Koncová rekurze představuje při správném použití velmi silnou programovací techniku, protože umožňuje zapisovat mnoho algoritmů v mnohdy elegantní rekurzivní formě, ovšem skutečné zpracování takto zapsaných algoritmů je stejně efektivní jako provádění programové smyčky (každou koncovou rekurzi lze nahradit smyčkou a naopak).

Klasickým příkladem rozdílu mezi normální (plnou, skutečnou) rekurzí a koncovou rekurzí je výpočet faktoriálu. Ten můžeme zapsat mnoha způsoby, například (jak je to v matematice obvyklé), rekurzivně:

(define (factorial n)
    (if (= n 0) ; podmínka pro ukončení rekurzivního zanořování
        1       ; faktoriál nuly je definitoricky roven jedné
        (* n (factorial (- n 1)))
    )
)

Z teoretického hlediska není na výše uvedené funkci nic nekorektního, ovšem při jejím praktickém používání brzy narazíme na limit způsobený omezenou velikostí zásobníku. Povšimněte si, že jazyk Scheme nemá velikost datových typů omezen na int či double tak, jako tomu je u některých dalších programovacích jazyků, překvapivě i u mnoha jazyků vysokoúrovňových, kde by programátor teoreticky čekal vyšší úroveň abstrakce:

(factorial 1)
1

(factorial 10)
3628800

(factorial 100)
9332621544394415268169923885626670049071
5968264381621468592963895217599993229915
6089414639761565182862536979208272237582
51185210916864000000000000000000000000
; výsledek je pro potřeby článku rozdělen na čtyři řádky

; ovšem nyní výpočet zhavaruje
(factorial 1000)
ERROR: Stack overflow
ABORT: (stack-overflow)

Výše uvedený rekurzivní výpočet lze relativně malou úpravou převést na výpočet který (alespoň v programovacím jazyce Scheme) vede na koncové volání, což mj. znamená, že paměťové (prostorové) nároky tohoto programu jsou konstantní:

; výpočet faktoriálu využívající koncového volání
(define (factorial n)
    (let fact-iter (          ; pomocná vnitřní funkce
                  (n n)       ; počitadlo iterací
                  (result 1)) ; průběžný výsledek
        (if (= n 0)           ; po dosažení koncového stavu
            result            ; se vrátí průběžný výsledek
            (fact-iter (- n 1) (* n result)) ; koncové volání
        )
    )
)

O tom, že upravený algoritmus výpočtu faktoriálu nevyužívá zásobník pro ukládání mezivýsledků ani počitadla iterací, se můžeme jednoduše přesvědčit. Popravdě řečeno i tento výpočet pro nějaké velké n zhavaruje, protože se překročí limit paměti alokované pro uložení mezivýsledku – proměnné result (konkrétně po zavolání (factorial 100000) už moje EEE s 1GB paměti začíná nepříjemně swapovat):

(factorial 1)
1

(factorial 10)
3628800

(factorial 100)
9332621544394415268169923885626670049071
5968264381621468592963895217599993229915
6089414639761565182862536979208272237582
51185210916864000000000000000000000000
; výsledek je pro potřeby článku rozdělen na čtyři řádky

; zkusíme výpočet faktoriálu pro nějaké
; větší číslo
(factorial 1000)
4023872600770937735437024339230039857193
7486421071463254379991042993851239862902
0592044208486969404800479988610197196058
6316668729948085589013238296699445909974
2450408707375991882362772718873251977950
5950995276120874975462497043601418278094
6464962910563938874378864873371191810458
2578364784997701247663288983595573543251
3185323958463075557409114262417474349347
5534286465766116677973966688202912073791
4385371958824980812686783837455973174613
6085379534524221586593201928090878297308
4313928444032812315586110369768013573042
1616874760967587134831202547858932076716
9132448426236131412508780208000261683151
0273418279777047846358681701643650241536
9139828126481021309276124489635992870511
4964975419909342221566832572080821333186
1168115536158365469840467089756029009505
3761647584772842188967964624494516076535
3408198901385442487984959953319101723355
5566021394503997362807501378376153071277
6192684903435262520001588853514733161170
2103968175921510907788019393178114194545
2572238655414610628921879602238389714760
8850627686296714667469756291123408243920
8160153780889893964518263243671616762179
1689097799119037540312746222899880051954
4441428201218736174599264295658174662830
2955570299024324153181617210465832036786
9061172601587835207515162842255402651704
8330422614397428693306169089796848259012
5458327168226458066526769958652682272807
0757813918581788896522081643483448259932
6604336766017699961283186078838615027946
5955131156552036093988180612138558600301
4356945272242063446317974605946825731037
9008402443243846565724501440282188525247
0935190620929023136493273497565513958720
5596542287497740114133469627154228458623
7738753823048386568897646192738381490014
0767310446640259899490222221765904339901
8860185665264850617997023561938970178600
4081188972991831102117122984590164192106
8884387121855646124960798722908519296819
3723886426148396573822911231250241866493
5314397013742853192664987533721894069428
1434118520158014123344828015051399694290
1534830776445690990731524332782882698646
0278986432113908350621709500259738986355
4277196742822248757586765752344220207573
6305694988250879689281627538488633969099
5982628095612145099487170124451646126037
9029309120889086942028510640182154399457
1568059418727489980942547421735824010636
7740459574178516082923013535808184009699
6372524230560855903700624271243416909004
1536901059339838357779394109700277534720
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000

; uff :-)

6. Některé rozdíly mezi LISPem a Scheme

Zápis programů v jazyku Scheme se ze syntaktického a částečně i ze sémantického hlediska podobá zápisu programů v LISPu, ovšem mezi oběma jazyky existuje několik rozdílů, které poněkud komplikují převody programů mezi LISPem a Scheme a samozřejmě i převody opačným směrem. Nejzásadnějším rozdílem mezi Scheme a mnohými staršími interpretry jazyka LISP (kromě Common Lispu) je to, že zatímco se v LISPu oblast platnosti proměnných stanovuje dynamicky v čase běhu programu, ve Scheme a v některých implementacích LISPu je oblast platnosti proměnné určena na základě toho, v jakém bloku se proměnná nachází (tato vlastnost jazyka se označuje lexical scope), což je podobné chování, jaké nalezneme i u naprosté většiny dalších programovacích jazyků. Lexical scope je v běžných programech přehlednější (programátor může určit oblast platnosti pouze ze zdrojového kódu, nemusí přemýšlet nad tím, jak se program chová při spuštění) a dokonce se i snáze implementuje.

Druhou odlišností mezi Scheme a LISPem je rozdílná reprezentace pravdivostních hodnot. Zatímco LISP považuje prázdný seznam (), reprezentovaný též hodnotou nil, za nepravdu a všechny ostatní hodnoty za pravdu, existuje ve Scheme jen jediná globálně dostupná a v celém systému jedinečná nepravdivá hodnota označovaná symbolem #f. Všechny ostatní objekty, včetně prázdného seznamu, jsou považovány za hodnotu pravdivou, což může komplikovat převody zdrojových kódů programů, protože v poměrně velkém množství algoritmů se například zpracovávají seznamy takovým způsobem, že se z nich postupně odebírají prvky a algoritmus skončí v případě odebrání posledního prvku, neboť se prázdný seznam vyhodnotí na nepravdivou hodnotu.

hist26

7. Obsah následující části seriálu

V následující části tohoto seriálu si podrobněji popíšeme některé zajímavé vlastnosti programovacího jazyka Scheme, které si vysvětlíme na mnoha demonstračních příkladech. Řekneme si, kdy přesně interpretry i překladače tohoto jazyka nahrazují skutečnou rekurzi za paměťově i rychlostně efektivnější koncové volání (tail-call) ukázané v páté kapitole, jakým způsobem se ve Scheme pracuje s uzávěry (closures) či jaké interpretry tohoto jazyka lze v současnosti využít a zda pro Scheme existuje vhodné vývojové prostředí. Krátce se taktéž budeme zabývat problematikou tvorby skriptů pro známý grafický editor GIMP.

hist26

8. Literatura

Richard Kelsey, Jonathan Rees, Mike Sperber
„The Incomplete Scheme 48 Reference Manual for release 1.8“
(dodáváno ve společném balíku se Scheme 48)
Carl Hewitt; Peter Bishop and Richard Steiger
„A Universal Modular Actor Formalism for Artificial Intelligence“
1973
Hillis, D.
„New Computer Architectures and Their Relationship to Physics or Why CS is No Good“ Int J. Theoretical Physics 21 (3/4) 255–262.
Lewis W. Tucker, George G. Robertson,
„Architecture and Applications of the Connection Machine“ Computer, vol. 21, no. 8, pp. 26–38, August, 1988.
Arthur Trew and Greg Wilson (eds.) (1991)
„Past, Present, Parallel: A Survey of Available Parallel Computing Systems“ New York: Springer-Verlag. ISBN 0–387–19664–1.
W. Daniel Hillis and Lewis W. Tucker
„The CM-5 Connection Machine: A Scalable Supercomputer“ In Communications of the ACM, Vol. 36, No. 11 (November 1993)
Cliff Lasser, Jeff Mincy, J.P. Massar
„The Essential *LISP Manual“ Thinking Machines Corporation, 1986.
Anonymous
„Getting Started in *Lisp, Version 6.1“ Thinking Machines Corporation, Cambridge, Massachusetts, June 1991.
Anonymous
„*Lisp Dictionary“ Thinking Machines Corporation, Cambridge, Massachusetts.
Anonymous
„*Lisp Timesharing User's Guide“ Online at CMU AI Repository
Zdzislaw Meglicki
„The CM5 *Lisp Course“ Centre for Information Science Research, The Australian National University, 1994
McCarthy
„Recursive functions of symbolic expressions and their computation by machine, part I“
1960
Guy L. Steele
„History of Scheme“
2006, Sun Microsystems Laboratories
Kolář J., Muller K.:
„Speciální programovací jazyky“
Praha 1981
„AutoLISP Release 9, Programmer's reference“
Autodesk Ltd., October 1987
„AutoLISP Release 10, Programmer's reference“
Autodesk Ltd., September 1988
McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
„LISP 1.5 Programmer's Manual“
MIT Press. ISBN 0 262 130 1 1 4
Feiman, J.
„The Gartner Programming Language Survey (October 2001)“
Gartner Advisory