 Logo języka | |
| Pojawienie się | 1970 |
|---|---|
| Paradygmat | |
| Typowanie | |
| Aktualnawersja stabilna | R7RS-small |
| Twórca | Guy L. Steele Jr., Gerald Jay Sussman |
| Platforma sprzętowa | |
| Platforma systemowa | |
| Strona internetowa | |
Scheme –funkcyjnyjęzyk programowania, dialekt (wariant)Lispu, który został zaprojektowany naMIT przezGuy L. Steele'a iGeralda Jaya Sussmana w latach 70. Jego główną ideą jest minimalizm, co oznacza, że sam język zawiera jedynie podstawowe mechanizmy, a na ich bazie, już z użyciem Scheme, tworzone są bardziej zaawansowane rozwiązania. Scheme nie jest czysto funkcyjnym językiem programowania, co oznacza, że dopuszczalne są efekty uboczne obliczeń. Scheme umożliwia również tworzenie programów w stylu proceduralnym i obiektowym. Jest to język o dynamicznym systemie typów. Zarządzanie pamięcią jest w pełni automatyczne. Scheme był pierwszym dialektemLispu, który używał zmiennych leksykalnych i pierwszym, który wymagał od implementacji optymalizacji wywołań z rekurencją ogonową.
Scheme jest ustandaryzowany przez organizacjęIEEE oraz przezspecyfikacjeRevisedn Report on the Algorithmic Language Scheme (RnRS)[1], z których najczęściej implementowane są R5RS z 1998 roku, R6RS z 2007 roku oraz najnowszy R7RS (small) z 2013 roku. Przy czym wersja R6RS ma mieszane opinie w gronieprogramistów używających języka Scheme. Głównym powodem negatywnych opinii na temat tej specyfikacji jest jej duża objętość[2]. Dodatkowo istnieją oficjalne rozszerzenia języka tzw. SRFI (ang. Scheme Request For Implementation)[3]. Niektóry SRFI stały się częścią standardów RnRS.
Składnia języka jest budowana z S-wyrażeń w sposób klasyczny dla Lispu. Różne elementy języka, jak np.deklaracje i definicje, warunki,podstawienia,selekcje itp. przedstawione są w postaci list. Lista taka składa się z elementówoddzielonych tzw.białymi znakami (czyli znakami odstępu, tabulacji lub nowego wiersza) i otoczona jest parąnawiasów (w niektórychimplementacjach dopuszcza się też w celu poprawienia czytelności kodu nawiasy kwadratowe). Pierwszym elementem listy jest identyfikator (nazwa) funkcji, kolejnymi sąargumenty.
Działania, tak jak wszystkie inne funkcje, zapisujemy wnotacji prefiksowej, to znaczy znak działania przed argumentami:
(+2(*22))(+1234)
W istocie działania matematyczne to zwykłe funkcje.
Można przekazywać im więcej niż 2 argumenty. Operatory działań mogą być przesłaniane podobnie jak innezmienne (zobacz przykład przy podstawieniu).
Identyfikatory można tworzyć zliteralfabetu łacińskiego (A-Z ia-z), cyfr (0-9) oraz znaków! $ % & * + – . / : < = > ? @ ^ _ ~. Dodatkowo, aby uniemożliwić mylenie identyfikatorów zestałymi liczbowymi, niedozwolone są identyfikatory rozpoczynające się od znaków, od których mogą zaczynać się liczby – czyli odcyfr lub jednego ze znaków:+ – .. Od tej reguły też jednak są wyjątki:+ – i ... są prawidłowymi identyfikatorami. Niektóre implementacje mogą dopuszczać też użycie innych identyfikatorów, które rozpoczynają się od tych znaków, ale nie są liczbami. Dodatkowo przyjmuje się następujące konwencje tworzenia identyfikatorów:
?. W szczególności zapytania o typ zmiennej tworzymy z nazwy typu i znaku zapytania (np.vector?).!, np.set!typ1 → typ2vector-,char- istring-. Czasem stosowane jest to też do operacji na listach.Komentarz dokodu źródłowego (tekst pomijany przez interpreter/kompilator) rozpoczyna się od średnika i rozciąga się aż do znaku nowej linii. W specyfikacji R7RS istnieją także komentarze S-Wyrażeń dzięki składnihash średnik, które poprzedza dane wyrażenie.
W języku tym istnieje wiele sposobówprzypisania zmiennym wartości.
(definezmwyr)
Deklaruje zmiennązm inadaje jej wartość wyrażeniawyr. Zmienna jest dostępna do końca bloku, w którym została zdefiniowana. Próba ponownego zdefiniowania tej samej zmiennej skończy się błędem (nie we wszystkich implementacjach).
(let((zm_1wyr_1)...(zm_nwyr_n))wyrazenie)
ustawia wartość zmiennych (zm_1, ...zm_n) na wyniki odpowiadających im wyrażeń (wyr_1, ...wyr_n) i wylicza na ich podstawie wartość wyrażeniawyrazenie. Zmienne nie są dostępne poza obrębemlet. Jeśli zmienne te istnieją, to zostaną przesłonięte.
(let*((zm_1wyr_1)...(zm_nwyr_n))wyrazenie)
Znaczenie podobne do let, jednak przy wyliczaniu wartości wyrażeń wyr_2, ...wyr_n brane są pod uwagę wartości wcześniej ustawionelet-em.
(set!zmiennawartosc)
Podstawienie podobne do znanych ze „zwykłych” języków programowania. Zmienia wartość zmiennej na nową, najczęściej policzoną w jakimśwyrażeniu. Zmienna musi być zadeklarowana (np. przez define lub let albo byćparametrem funkcji tworzonej przezlambda).
Przykłady:
(let((x(+35))(y(-47)))(*xy))
Wartość wyrażenia
(let((+*))(+38))
będzie równa 24 (= 3 * 8), ponieważ wewnątrzlet + oznacza*.
Zmienne są typowane dynamicznie, czyli zmienna nie ma ustalonego typu – jest takiego typu jak wartość, którą przechowuje. Czasem musimy więc sprawdzić czy rzeczywiście przechowuje ona wartość odpowiedniego typu (np. przed użyciem w funkcji, które przyjmują wartości tylko określonego typu lub chcąc wybrać sposób potraktowania danych zależnie od typu)
(number?5)(number?"foo")(string?"foo")
Pytania o typ składają się z nazwy typu iznaku zapytania (?).
Równość dwóch zmiennych sprawdzamy predykatem eq?. Dwie zmienne są równe jeśli są tą samą liczbą, tym samym symbolem lub wskazują na tę samą parę (w szczególności listę). Dwie listy o takich samych elementach zostaną wzięte za różne jeśli powstały niezależnie od siebie (czyli jedna z nich nie przyjęła wartości przez podstawienie drugiej).
(eq?"foo""bar")(eq?5(+23))(eq?(eq?23)(eq?34))
Wartości logiczneprawda ifałsz reprezentowane sąodpowiednio symbolami#t i#f. Możemy na nich wykonywać np. operacjeor (alternatywalub),and (koniunkcjai) oraznot (negacjanie). Mają one jednak odrobinę szersze zastosowanie.
Funkcje definiuje się za pomocą konstrukcji:(lambda (lista argumentów) (ciało funkcji)), przy czym może ona zostać wartością zmiennej (np. przez define lub let) albo zostać użyta bez nadawania jej nazwy.
(definefact(lambda(x)(if(=x0)1(*x(fact(-x1))))))(definefib(lambda(n)(cond((=n0)0)((=n1)1)(else(+(fib(-n1))(fib(-n2)))))))(definesum(lambda(x)(cond((null?x)0)(else(+(carx)(sum(cdrx)))))))(fact14)(fib10)(map(lambda(x)(*x(+1x)));;; obliczy listę wartości wyrażenia x*(x+1)'(1369));;; kolejno dla 1, 3, 6 i 9(sum'(666100))(sum(mapfib'(1234)));; zamiast tworzyć procedurę sum, możemy również użyć apply:(apply+'(666100))
Zamiastpętli wykorzystuje się możliwości stwarzane przezrekurencję, szczególnie przezrekurencję ogonową w której wywołanie rekurencyjne występuje jako ostatnie wyrażenie, funkcje z rekurencją ogonową zamieniane są na pętle przez kompilator.
Przykład funkcji z rekurencją ogonową do obliczania silni.
(define(!n)(letiter((nn)(product1))(if(zero?n)product(iter(-n1)(*productn)))))
Tak zdefiniowana rekurencja może być wykonywana bez odkładania parametrów na stos, czyli tak jak zwykłaiteracja.
Za pomocą makr można przetwarzać kod scheme jak dane. Makra są przetwarzane najczęściej w czasie kompilacji. Makro musi zwracać kod jako dane (tzn. listę symboli), które zostaną obliczone (według specyfikacji języka scheme makra tworzy się za pomocą define-syntax, let-syntax, syntax-rule ale większość implementacji udostępnia makro define-macro lub defmacro, za pomocą którego definiuje się makra w styluCommon Lispa).
Znak ` (tylny apostrof) działa tak jak ' (cytat) z tym że wewnątrz można użyć przecinka, który oblicza dane wyrażenie lub ,@ (przecinek małpa) który oblicza wyrażenie i usuwa zewnętrzne nawiasy.
"`" jest to skrót do funkcji quasiquote, "," – to skrót do unquote a ",@" to skrót do unquote-splicing
(define-macro(forparams.body)(let((iter(gensym))(step(if(=(lengthparams)4)(cadddrparams)1)))`(let,iter((,(carparams),(cadrparams)))(if(<=,(carparams),(caddrparams))(begin,@body(,iter(+,(carparams),step))))))); przykład użycia(for(i110)(displayi)(newline))(define-macro(whentest.body)`(if,test(begin,@body)))(define-macro(for-listparams.body)(let((iter(gensym))(list(gensym)))`(let,iter((,(carparams)(car,(cadrparams)))(,list(cdr,(cadrparams))))(when(not(null?,(carparams))),@body)(when(not(null?,list))(,iter(car,list)(cdr,list))))));; przykład użycia(for-list(i(list102030))(displayi)(newline))
Problem z makrami lispowymi jest taki, że rozwinięcie makra jest wstawiane w kod użytkownika. Nawet gdy używamy funkcji gensym do generowania symboli, w kodzie pozostają nazwy funkcji i form specjalnych (lub makr), które mogą być nadpisane przez użytkownika, co wcale nie musi być takie rzadkie. Użytkownik może użyć zmiennej, która wcześniej może być nazwą makra lub funkcji użytej w rozwinięciu.
Przykład:
(define-macro(unlesstest.body)`(if(not,test)(begin,@body)))(let((not(lambda(x)x)))(unless#t(display"x")(newline)))
Mimo że makro unless dostaje wartość#t, zostanie wyświetlona wartość"x". Inny bardziej realny przypadek to użycie funkcjilist wewnątrz makra, która często jest używana jako nazwa zmiennej, która przechowuje przetwarzaną listę. Aby móc korzystać z makr lispowych, które używają funkcjilist trzeba by zapisywać każdą listę jakolst aby przypadkiem nie zepsuć makra. W języku Common lisp problem kolizji rozwiązano dzięki użyciu systemu pakietów oraz dwóch przestrzeni nazw (dla zmiennych i funkcji). W języku Scheme inaczej rozwiązano ten problem, specyfikacja języka Scheme wprowadziła makra higieniczne, które używają języka wzorców (ang.pattern language):
(define-syntaxunless(syntax-rules()((_testrest...)(if(nottest)(beginrest...)))))(let((not(lambda(x)x)))(unless#f(display"x")(newline)))
Higieniczność makr, oznacza że nie jest możliwa zmiana zachowania makra, za pomocą kodu użytkownika. Zmiana definicji funkcjinot, nie ma wpływu na makro higieniczne. Implementacja makr higienicznych, może polegać na automatycznej zmianie nazw wszystkich wolnych zmiennych (np. na wartości zwracane przez funkcje gensym). Jest to jednak pewne uproszczenie, mechanizm jest o wiele bardziej skomplikowany. Zamiana nazw musi brać pod uwagę konstrukcje, które tworzą nowe zmienne jaklet czylambda.
Makra higieniczne, ze specyfikacji R5RS, nie dawały wszystkich możliwości jakie miały marka lispowe, np. makra anaforyczne:
(define-macro(aiftestifelse)`(let((it,test))(ifit,if,else)))(let((alist'((foo.10)(bar.20))))(aif(assoc'fooalist)(cdrit)));; => 10
W powyższym kodzie makro aif udostępnia zmiennąit, która zawiera testowaną wartość, dlatego nie trzeba dwa razy wywoływać tego samego wyrażenia. Niektóre implementacje języka Scheme umożliwiają pisanie mark anaforycznych, za pomocą makrasyntax-case. Makra te jednak nie są częścią specyfikacji języka. Innym sposobem użycia makr anaforycznych, w języku Scheme, jest użycie Biblioteki SRFI-139[4].
Dość unikalną cechą Scheme jest wbudowane w język wsparcie dla kontynuacji. Za pomocą standardowej funkcjicall-with-current-continuation lubcall/cc możliwy jest dostęp do następnego wyrażenia podlegającego ewaluacji. W przykładowym wyrażeniu(foo (bar (baz) (xenu))) kontynuacją(bar (baz) (xenu)) będzie(foo x) gdziex jest wartością zwracaną przez(bar ...).
Szczególną cechą kontynuacji jest możliwość wywołania ich wielokrotnie czy zapisania w zmiennej do użycia na później, po odwinięciustosu. W przeciwieństwie do funkcji biblioteki standardowej Csetcontext, wzorcowa implementacja Scheme nie powoduje żadnego narzutu wydajności przy pobraniu czy wywołaniu kontynuacji. Stosowany jest tutajstyl przekazywania kontynuacji, gdzie stos nie istnieje i pobranie/wywołanie kontynuacji niczym nie różni się od wywołania funkcji.
Przykładowe zastosowanie kontynuacji to implementacja natychmiastowego wyjścia z funkcji.
(define(finditemlst)(call-with-current-continuation(lambda(return)(for-each(lambda(x)(if(equal?xitem)(returnx))(displayx)(newline))lst))))(let((result(find'x'(abdxyzf))))(display"wynik: ")(displayresult)(newline))
W powyższym przykładzie mamy funkcje for-each, która iteruje po wszystkich elementach listy. Ale dzięki dostępowi do kontynuacji jest możliwe natychmiastowe zakończenie funkcji po znalezieniu szukanego elementu.
Inny przykład to implementacjawspółprogramów czygeneratorów takich jak te wPythonie czyC#. Przykładowa implementacja generatora:
(define(make-coroutine-generatorproc)(definereturn#f)(defineresume#f)(defineyield(lambda(v)(call/cc(lambda(r)(set!resumer)(returnv)))))(lambda()(call/cc(lambda(cc)(set!returncc)(ifresume(resume(if#f#f)); void? or yield again?(begin(procyield)(set!resume(lambda(v)(return(eof-object))))(return(eof-object))))))))
Powyższy przykład pochodzi z implementacji SRFI-158[5][6].
Przykładowy generator liczb 0, 1 oraz 2 z dokumentu SRFI-190[7].
(definecounter(make-coroutine-generator(lambda(yield)(do((i0(+i1)))((<=3i))(yieldi)))))
Użycie takiego generatora może wyglądać tak:
(define(print-numbers)(let((i(counter)))(if(not(eof-object?i))(begin(displayi)(newline)(print-numbers)))))(print-numbers)
Zmiennacounter zawiera funkcje (główne wyrażenie lambda z funkcjimake-coroutine-generator), które wywołane zwraca kolejne wartości aż do uzyskania wartości końcowego znacznika (eof -ang. end of file).
Ten sam kod może służyć do tworzenia nieskończonych generatorów.
Kontynuacje wykorzystywane są także by nadać wrażenie synchroniczności typowo asynchronicznym operacjom takim jak np. zapytania HTTP[8]. Niestety, przez obecność kontynuacji jakotyp danych pierwszej klasy w Scheme nie jest możliwe orzeknięcie czy dany blok kodu będzie jeszcze wywoływany, komplikując zamykanie zasobów takich jak deskryptory plików i inneuchwyty[9].
Jeszcze innym przykładem użycia kontynuacji jest implementacja wyrażenia try..catch[10].
Wejście i wyjście w języku Scheme reprezentowane jest przez porty. Są to obiekty, które (odpowiednio) są źródłem znaków (obiektów typu char) lub które mogą przyjmować znaki. Podstawowe procedury odczytu i zapisu toread iwrite. Przykład zastosowania:
(write(+(read)(read)))
Standard języka opisuje również funkcje otwierające pliki i otwierające i zamykające porty.Funkcja czytająca linie z pliku i zwracająca listę (działająca w interpreterze Guile).
(define(read-linesfilename)(call-with-input-filefilename(lambda(file)(let((line""))(letloop((result'()))(set!line(read-linefile))(if(eof-object?line)result(loop(appendresult(listline)))))))))
Funkcja zapisująca listę stringów do pliku
(define(write-linestringport)(displaystringport)(newlineport))(define(write-linesfilenamelist)(call-with-output-filefilename(lambda(file)(letloop((listlist))(unless(null?list)(write-line(carlist)file)(loop(cdrlist)))))));; unless to jest macro(define-macro(unlesstest.body)`(if(not,test)(begin,@body)));; lub(define(write-lineslistport)(for-each(lambda(line)(write-linelineport))list))
Język Scheme ciągle się rozwija, dwa główne elementy tego rozwoju to dokument opisujący rdzeń języka (RnRS) oraz proces zgłaszania dokumentów SRFI (Scheme Requests for Implementation) czyli propozycji rozszerzeń i ulepszeń języka opracowywanych przez użytkowników.
Język Scheme opisany jest w dwóch dokumentach[11]:
Raport RnRS jest powszechnie uważany za oficjalną i podstawową definicję języka: programiści piszą programy zgodne z RnRS, o implementacjach języka Scheme mówi się, że są w całości lub częściowo zgodne z raportem RnRS.
Pierwszy dokument opisujący język Scheme powstał w roku 1975: „Scheme: an interpreter for extended lambda calculus”, autorami byli Gerald Jay Sussman i Guy Lewis Steele Jr., twórcy języka. Raport R5RS został opublikowany 20 lutego 1998 roku, Do sierpnia 2007 roku trwały prace nad nową definicją języka – raportem R6RS[12]. Wstępna wersja nowego raportu o numerze 5.97 została poddana pod głosowanie osób, które zgłosiły zainteresowanie procesem tworzenia dokumentu. Głosowanie zakończyło się 12 sierpnia, 29 sierpnia ogłoszono wyniki głosowania i ratyfikację nowego raportu – R6RS[13]. Wersja R7RS w wersji mniejszej (ang. small) została zatwierdzona w 2013[14] aktualnie trwają prace nad wersją większą (ang. large)[15].
Dokumenty zgłoszone i przyjęte w procesie SRFI (ang.Scheme Requests for Implementation)[16] są sposobem na w miarę szybkie wprowadzanie, przenośnych między implementacjami języka, rozwiązań ułatwiających tworzenie programów. Istnieje ponad 100 dokumentów SRFI. Opisują one sposób zaimplementowania takich funkcji czy rozwiązań jak np. sposób notacji tablic, strumienie, obsługa wyjątków, rozszerzenia makr higienicznych, wykonywanie skryptów języka Scheme w systemach operacyjnych UNIX czy obsługa wielowątkowości. Rozwiązania te nie wchodzą w skład oficjalnej definicji języka, jednak mogą być brane pod uwagę przy tworzeniu kolejnych wersji raportu RnRS.
| 1GL | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2GL/ Język drugiej generacji/ Asembler | |||||||||||||||
| 3GL / Język trzeciej generacji |
| ||||||||||||||
| 4GL/ Język czwartej generacji/ Język dziedzinowy |
| ||||||||||||||
| 5GL/Logiczne | |||||||||||||||
| Ezoteryczne | |||||||||||||||
| Inne |