Loading AI tools
język programowania Z Wikipedii, wolnej encyklopedii
Lisp[1] – rodzina języków programowania z długą historią i charakterystyczną składnią. Zaprojektowany przez Johna McCarthy’ego na MIT w 1958 roku. Pierwszym interpreterem języka Lisp była implementacja funkcji eval wykonana przez studenta McCarthy’ego – Steve’a Russella. Lisp jest drugim z kolei pod względem wieku językiem programowania wysokiego poziomu pozostającym w użyciu (starszy jest tylko Fortran). Podobnie jak Fortran, Lisp ulegał na przestrzeni czasu licznym zmianom. Powstało również wiele jego dialektów. Dziś do najpopularniejszych należą trzy: Common Lisp, Scheme i Clojure.
![]() Logo języka | |
Pojawienie się | |
---|---|
Paradygmat | |
Typowanie | |
Pochodne |
Common Lisp, Scheme, Emacs Lisp, AutoLISP, Clojure i inne |
Twórca |
Lisp powstał jako wygodna matematyczna notacja dla programów komputerowych, oparta na rachunku lambda stworzonym przez Alonzo Churcha. Szybko został najchętniej wybieranym językiem do badania i rozwoju sztucznej inteligencji. Wywodzi się z niego wiele technik programistycznych, takich jak struktury drzewiaste, odśmiecanie pamięci, dynamiczne typowanie czy nowe koncepcje w programowaniu obiektowym (Common Lisp Object System).
Nazwa Lisp pochodzi od LISt Processing. Podstawową strukturą danych w Lispie jest lista; kod źródłowy programów w Lispie składa się z list. Dzięki temu język jest homoikoniczny, tzn. programy w Lispie mogą manipulować kodem źródłowym jak zwykłą strukturą danych. Umożliwia to pisanie makr, pozwalających programiście tworzyć nową składnię lub nawet małe, zagnieżdżone w Lispie, języki DSL.
Kod tworzony jako struktura danych sprawia, że Lisp ma charakterystyczną składnię. Cały kod źródłowy ma postać tzw. S-wyrażeń (S-expressions), czyli list otoczonych nawiasami. Wywołanie funkcji, makra lub formy specjalnej ma postać listy, której pierwszym elementem jest nazwa funkcji, makra lub formy specjalnej lub wyrażenie, którego wynikiem jest funkcja, a następnymi elementami – argumenty. Na przykład funkcję o nazwie f
z argumentami a
, b
i c
wywołuje się za pomocą kodu (f a b c)
, natomiast gdy (g a b)
zwraca funkcje można użyć ((g a b) c d)
.
Lisp został wymyślony przez Johna McCarthy’ego w 1958 podczas jego pobytu na MIT. W roku 1960 McCarthy opublikował swój projekt w Communications of the ACM, w artykule pod tytułem „Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”[2] (Rekursywne funkcje wyrażeń symbolicznych i ich maszynowe obliczanie, część I; części II nigdy nie opublikowano). Pokazał, że za pomocą kilku operatorów i notacji dla funkcji można zbudować język implementujący maszynę Turinga.
Pierwszą implementację Lispu opracował Steve Russell na komputerze IBM 704. Russell przeczytał artykuł McCarthy’ego i doszedł (ku zdziwieniu McCarthy’ego) do wniosku, że funkcję eval można zaimplementować jako interpreter Lispu[3].
Pierwszy kompletny kompilator Lispu stworzony w Lispie napisali w 1962 Tim Hart i Mike Levin na MIT[4]. W kompilatorze tym wprowadzono model kompilacji przyrostowej (ang. incremental compilation), dzięki czemu funkcje kompilowane i interpretowane nie były rozróżniane. Język użyty przez Harta i Levina był dużo bliższy nowoczesnemu stylowi Lispu niż wcześniejszy kod McCarthy’ego.
Information Processing Language był pierwszym językiem zaprojektowanym do tworzenia sztucznej inteligencji i już zawierał kilka pomysłów, które później zostały użyte w Lispie, jak na przykład przetwarzanie list czy rekurencja.
Oryginalna notacja McCarthy’ego używała M-wyrażeń, które potem były przetwarzane na S-wyrażenia, na przykład M-wyrażenie car[cons[A,B]]
jest równoznaczne z S-wyrażeniem (car (cons A B))
. Gdy tylko Lisp został zaimplementowany, programiści szybko porzucili M-wyrażenia na rzecz S-wyrażeń. M-wyrażenia powróciły na chwilę w MLISPie[5] autorstwa Horace’a Enea i CGOLu autorstwa Vaughana Pratta.
Dwa makra asemblera na maszynie IBM 704 stały się podstawowymi operacjami do przetwarzania list: car
(Contents of Address Register) i cdr
(Contents of Decrement Register)[6]. Różne dialekty Lispu wciąż używają nazw car
i cdr
dla funkcji zwracających odpowiednio pierwszy element i resztę listy.
Przez ponad 50 lat powstało wiele różnorakich dialektów Lispu – języka ze składnią złożoną z S-wyrażeń. Co więcej, część dialektów miało kilka implementacji – Common Lisp, na przykład, posiada ich ponad tuzin.
Różnice między poszczególnymi dialektami mogą być znaczące – Common Lisp i Scheme używają na przykład różnych słów kluczowych do definiowania funkcji. Jednak wewnątrz dialektu takie różnice nie występują, każda zgodna implementacja obsługuje ten sam zestaw funkcji, poza którym często oferuje dodatkowe rozszerzenia i biblioteki.
Od swoich początków Lisp był blisko powiązany ze społecznością badającą i rozwijającą sztuczną inteligencję, szczególnie na PDP-10[8]. Lisp został użyty w implementacji języka programowania Micro Planner, który był podstawą znanego systemu SI SHRDLU. W latach 70., gdy badania nad AI rozwinęły się również po stronie komercyjnej, wydajność istniejących systemów Lispu stawała się coraz ważniejszym problemem.
Lisp był trudny do implementacji na zwykłych kompilatorach i sprzęcie dostępnym w 1970. Garbage collection, stworzone przez Daniela Edwardsa, wpłynęło na użyteczność Lispu na sprzęcie obliczeniowym ogólnego przeznaczenia, ale wydajność wciąż była problemem. Doprowadziło to do stworzenia maszyn lispowych: dedykowanego sprzętu do uruchamiania środowisk i programów w Lispie. Postęp w dziedzinie sprzętu komputerowego, jak również w kompilatorach wkrótce sprawił, że maszyny lispowe stały się przestarzałe, co zaszkodziło rynkowi Lispu.
W latach 80. i 90. włożono duży wysiłek w zunifikowanie wielu dialektów Lispu (szczególnie dialektów InterLisp, Maclisp, ZetaLisp, i Franz Lisp) w pojedynczy język. Nowy język, Common Lisp był istotnie kompatybilnym podzbiorem dialektów, które zastępował. W 1994, ANSI opublikowało specyfikację Common Lispu, „ANSI X3.226-1994 Information Technology Programming Language Common Lisp”. W tamtym czasie światowy rynek Lispu był dużo mniejszy niż obecnie.
Po spadku popularności w latach 90. wywołanym m.in. upowszechnieniem się C++ i silnym marketingiem Javy, jak również brakiem dobrych i wolnych implementacji Lispu, Lisp doświadcza wzrostu zainteresowania od roku 2000[potrzebny przypis]. Większość aktywności skupia się wokół stworzenia open source’owych implementacji Common Lispu i zawiera rozwój nowych przenośnych bibliotek i aplikacji. Zainteresowanie to można częściowo zmierzyć przez sprzedaż papierowej wersji książki Practical Common Lisp autorstwa Petera Seibela, wstępu do CL dla nowych programistów Lispu, opublikowanej w 2004 roku[9]. Była ona drugą co do popularności książką o programowaniu na Amazon. Aktualnie dostępna jest za darmo w internecie[10]. Można również zauważyć zwiększoną frekwencję na związanych z Lispem konferencjach[11] i aktywność na powiązanych grupach[12].
Wielu nowych programistów Lispu zostało zainspirowanych przez wypowiedzi takich postaci jak Paul Graham czy Eric S. Raymond by spopularyzować język uznawany za przestarzały. Nowi programiści zwykle opisują język jako dający nowe spojrzenie na programowanie i twierdzą, że dzięki temu stali się dużo bardziej wydajni niż w innych językach[13]. Wpływ na odzyskiwanie popularności przez Lisp mógł mieć również komentarz Petera Norviga[14], autora książek Paradigms of AI Programming: Case Studies in Common Lisp i Artificial Intelligence: A Modern Approach lub Phillip Greenspun, który odniósł sukces biznesowy używając Lispu.
Dwoma głównymi dialektami Lispu ogólnego przeznaczenia aktualnie są Common Lisp i Scheme. Języki te reprezentują znacząco różne podejścia projektowe.
Common Lisp, bazujący głównie na Maclispie, InterLisp i dialektach z maszyn lispowych, jest poszerzonym nadzbiorem wcześniejszych dialektów, z szeroką specyfikacją, obejmującą wiele wbudowanych typów danych i form syntaktycznych, jak również system obiektowy.
Scheme reprezentuje podejście minimalistyczne, ze znacznie mniejszym zbiorem standardowych funkcji, ale za to z określonymi cechami implementacyjnymi (jak na przykład optymalizacja rekursji ogonowej czy pełne kontynuacje), które niekoniecznie mogą być dostępne w Common Lispie. CL zapożyczył również pewne cechy ze Scheme jak na przykład leksykalny zasięg czy leksykalne domknięcie.
Poza tym, dialekty Lispu są używane jako języki skryptowe w aplikacjach, z czego najbardziej znanymi są:
Nowe dialekty Lispa to:
Lisp był pierwszym językiem, w którym kod źródłowy był również strukturą danych używaną przez język – w tym przypadku listą. Umożliwiło to wprowadzenie makr (których nie należy mylić z prostymi makrami podstawieniowymi znanymi na przykład z preprocesora C), których zadaniem jest tworzenie kodu źródłowego podczas interpretowania (lub kompilacji) programu – makra to zatem programy piszące programy. Pozwalają one na pisanie eleganckiego kodu na wyższym poziomie abstrakcji i zredukowanie jego ilości.
Konstrukcja if-then-else, współcześnie uznawana za konieczny element każdego języka programowania, została wymyślona przez McCarthy’ego dla Lispu w bardziej ogólnej formie (jako konstrukcja cond). Pomysł został skopiowany i spopularyzowany przez Algola. Lisp wprowadził również koncepcję dynamicznego typowania i mechanizm garbage collection.
Lisp wpłynął na Alana Kaya, który prowadził badania nad Smalltalkiem, by następnie ulec wpływowi Smalltalka przez wprowadzenie cech programowania obiektowego (klasy, metody itd.) pod koniec lat 70.
Głównie ze względu na wymagania systemowe Lisp nie zyskał takiej popularności poza społecznością badającą SI jak na przykład Fortran czy C. Nowsze języki, takie jak Java czy Ruby oferują część jego cech, mimo tego nie jest możliwe spójne zaimplementowanie dla nich wszystkich cech Lispu. W ostatnich latach wiodące implementacje Lispu zaczęły dorównywać wydajnością kompilatorom popularnych języków[15], w tym przewyższając o rzędy wielkości wydajność popularnych języków skryptowych, głównie ze względu na przejmowanie cech Lispu (GC, dynamiczne typowanie, refleksja) przez względnie „popularne” języki.
Zobacz też „The evolution of Lisp”[16], artykuł autorstwa Guya Steele’a Jr. i Richarda Gabriela.
Lisp jest językiem, którego składnia składa się z wyrażeń. W przeciwieństwie do większości innych języków, nie ma w nim podziału na wyrażenia i instrukcje – cały kod i dane są zapisane jako wyrażenia. Wynikiem ewaluacji (wartościowania) wyrażeń jest wartość (lub lista wartości), która może być użyta jako argument do innego wyrażenia.
McCarthy w artykule z 1958 roku wprowadził dwa modele składni – S-wyrażenia (Symbolic Expressions, wyrażenia symboliczne, zwane również sexpami), które odzwierciedlały wewnętrzną reprezentację kodu i danych, jak również M-wyrażenia (Meta Expressions, meta wyrażenia), które wyrażały zewnętrzny kod. M-wyrażenia nigdy nie stały się zbyt popularne i wszystkie popularne Lispy korzystają z S-wyrażeń do określania zarówno kodu, jak i danych.
Sposób użycia nawiasów jest najlepiej widocznym na pierwszy rzut oka faktem pozwalający odróżnić Lisp od innych rodzin języków. Z tego powodu Lisp był często krytykowany, głównie przez programistów innych języków, niektórzy nadali Lispowi takie przydomki jak Lost In Stupid Parentheses (Zagubiony w głupich nawiasach) czy Lots of Irritating Superfluous Parentheses (Wiele irytujących zbytecznych nawiasów)[17]. Jednakże składnia oparta na S-wyrażeniach leży u podstaw możliwości Lispu; jest niezwykle regularna, co ułatwia jej przetwarzanie przez komputer. Lisp nie jest jednak ograniczony do notacji nawiasowej – możliwe jest takie poszerzenie go by używał innych, alternatywnych notacji. XMLisp na przykład to rozszerzenie Common Lispu integrujące S-wyrażenia z XML-em.
Bazowanie na wyrażeniach daje językowi dużą elastyczność. Ponieważ funkcje w Lispie są zapisywane jako listy, mogą być manipulowane jak zwykłe dane. Umożliwia to łatwe pisanie programów, które operują na innych programach (metaprogramowanie). Wiele dialektów wykorzystuje tę cechę przez użycie systemu makr, które pozwalają na niemal nieograniczone poszerzanie języka.
Lista w Lispie jest zapisywana jako elementy rozdzielone białymi znakami i otoczone nawiasami. Na przykład (1 2 foo)
to lista, której elementami są trzy atomy, wartości 1
, 2
, i foo
. Te wartości są domyślnie typowane (ich typy nie muszą być deklarowane): są to odpowiednio dwie liczby całkowite i specyficzny dla Lispu typ symboliczny.
Wyrażenia są zapisywane jako listy z wykorzystaniem notacji polskiej. Pierwszym elementem listy jest nazwa formy, czyli funkcji, makra lub specjalnego operatora. Pozostałe elementy listy są argumentami. Na przykład funkcja list
zwraca listę zbudowaną ze swoich argumentów, więc ewaluacja wyrażenia
(list '1 '2 'foo)
zwróci listę (1 2 foo)
. Apostrof przed każdym argumentem to skrócona forma specjalnego operatora quote (ang. cytuj), który zapobiega ewaluacji argumentów (stosowanie go do liczb nie jest konieczne, ponieważ 1 jest ewaluowane do 1 itp.). Każde wyrażenie niepoprzedzone apostrofem jest rekursywnie wartościowane przed ewaluacją otaczającego wyrażenia. Na przykład
(list 1 2 (list 3 4))
zostanie ewaluowane do (1 2 (3 4))
. Zauważ, że trzecim argumentem jest lista; listy mogą być zagnieżdżane.
Operatory arytmetyczne są traktowane podobnie, jako że same w sobie są również funkcjami. Wyrażenie
(+ 1 2 3 4)
zwraca po ewaluacji 10. Odpowiednik w notacji infiksowej wyglądałby 1 + 2 + 3 + 4
. Funkcje arytmetyczne mogą przyjmować dowolną ilość argumentów.
Specjalne operatory (zwane również specjalnymi formami) zapewniają Lispowi struktury kontrolne. Na przykład specjalny operator if
pobiera trzy argumenty i ewaluuje drugi, jeżeli pierwszy argument jest różny od nil, w przeciwnym razie ewaluuje trzeci. Zatem poniższy kod
(if nil
(list 1 2 "foo")
(list 3 4 "bar"))
zwraca (3 4 "bar")
. Oczywiście konstrukcja byłaby bardziej użyteczna gdyby podstawić jakieś nietrywialne wyrażenie w miejsce nil
.
Inny specjalny operator, lambda
, służy do tworzenia anonimowych funkcji, argumentami są lista argumentów funkcji wynikowej i wyrażenie, na podstawie którego wartościowana jest funkcja (wartością zwracaną jest wartość ostatniego obliczonego wyrażenia). Wyrażenie
(lambda (arg) (+ arg 1))
zwraca funkcję, która przy wywołaniu pobiera jeden argument, przypisuje go do arg
i zwraca go zwiększonego o jeden. Wyrażenia lambda traktowane są tak samo jak nazwane funkcje. Wyrażenie
((lambda (arg) (+ arg 1)) 5)
zwraca więc 6
.
W oryginalnym LISPie dostępne były dwa podstawowe typy danych: atomy i listy. Lista była skończoną uporządkowaną sekwencją elementów, w której każdy element był albo atomem albo listą, a atom był liczbą lub symbolem. Symbol był unikalnym nazwanym obiektem, zapisanym jako alfanumeryczny ciąg znaków w kodzie źródłowym i używany był albo jako nazwa zmiennej, albo jako obiekt danych. Na przykład lista (FOO (BAR 1) 2)
zawiera trzy elementy: symbol FOO, listę (BAR 1)
i liczbę 2.
Podstawową różnicą pomiędzy atomami i listami był fakt, iż atomy były niezmienne i unikalne. Dwa atomy, które pojawiły się w różnych miejscach w kodzie źródłowym, ale były zapisane w dokładnie ten sam sposób, reprezentowały ten sam obiekt, podczas gdy każda lista była oddzielnym obiektem, mogła być modyfikowana niezależnie od innych list i odróżniana od nich za pomocą funkcji porównujących.
Gdy w późniejszych dialektach Lispu wprowadzono więcej typów danych, a styl programowania się zmienił, pojęcie atomu straciło swoją ważność. Wiele dialektów wciąż utrzymywało predykat atom dla wstecznej kompatybilności, definiując go jako prawdę dla wszystkiego, co nie było komórką cons (np. listy lub częściowej listy).
Lista w Lispie jest jednokierunkowa. Każda komórka nazywa się cons (w Scheme para, ang. pair) i składa się z dwóch wskaźników, zwanych car i cdr.
Spośród wielu struktur danych, jakie mogą być zbudowane za pomocą komórek cons, najbardziej podstawową jest tzw. prawidłowa lista. Prawidłowa lista składa się albo ze specjalnego symbolu nil, reprezentującego pustą listę, albo z komórki cons, w której pierwszy wskaźnik ma wskazywać na obiekt przechowywany w komórce, a drugi na następny element listy, lub na nil, jeżeli jest to element ostatni.
Jeżeli rozważamy komórkę, która jest głową listy, wtedy jej car wskazuje na pierwszy element, a cdr na resztę listy. Z tego powodu funkcje car
i cdr
są również zwane first
(pierwszy) and rest
(reszta), gdy odnosimy się do komórek cons, które są częściami listy (w przeciwieństwie np. do drzewa).
Wynika z tego, że lista w Lispie nie jest podstawowym obiektem, jak na przykład instancja kontener w C++ czy Javie. Lista jest zbiorem bardziej podstawowych obiektów, jakimi są komórki cons. Zmienna, która wskazuje na listę, wskazuje tak naprawdę na pierwszą komórkę listy. Przejście po liście można wykonać np. za pomocą kolejnych wywołań funkcji cdr
na liście lub za pomocą którejś z funkcji wyższego rzędu.
Ponieważ komórki cons i listy są takie powszechne w systemach lispowych, uznaje się często niepoprawnie, że są jedynymi strukturami danych w Lispie. Tak naprawdę wszystkie (poza najprostszymi) dialekty Lispu mają inne struktury danych, np. wektory (tablice, ang. vector), hash tablice, struktury itd.
S-wyrażenia reprezentują strukturę list. Jest kilka sposobów, by opisać tę samą listę za pomocą S-wyrażenia. Komórka cons może być opisana za pomocą notacji kropkowanych par (ang. dotted-par notation) jako (a . b)
, gdzie a
jest wskazywane przez car, natomiast b
przez cdr. Prawidłowa lista może być opisana za pomocą tej notacji jako (a . (b . (c . (d . nil))))
, co jest zwykle skracane do (a b c d)
za pomocą notacji listy (ang. list notation). Nieprawidłowa lista może być zapisana za pomocą kombinacji obydwu tych sposobów – S-wyrażenie (a b c . d)
reprezentuje listę trzech komórek cons, z czego w ostatniej cdr wskazuje na d
(ta sama lista zapisana za pomocą pełnej notacji wyglądałaby następująco: (a . (b . (c . d)))
).
Lisp zapewnia wiele wbudowanych funkcji służących do manipulowania listami. Listy mogą być tworzone bezpośrednio za pomocą funkcji list
, która pobiera dowolną liczbę argumentów i zwraca listę zawierającą te argumenty:
(list 1 2 'a 3)
;zwraca (1 2 a 3)
(list 1 '(2 3) 4)
;zwraca (1 (2 3) 4)
Ze względu na fakt, iż listy są tworzone z komórek cons, funkcja cons
może być użyta do dodania elementu na początek listy. Zauważ, że ta funkcja jest asymetryczna ze względu na sposób, w jaki obsługuje listy jako argumenty. Przyczyną tego jest wewnętrzna budowa list.
(cons 1 '(2 3))
;zwraca (1 2 3)
(cons '(1 2) '(3 4))
;zwraca ((1 2) 3 4)
Funkcja append
łączy dwie lub więcej list w jedną. Ponieważ listy w Lispie są listami łączonymi jednostronnie, połączenie dwóch list ma złożoność
(append '(1 2) '(3 4))
;zwraca (1 2 3 4)
(append '(1 2 3) '() '(a) '(5 6))
;zwraca (1 2 3 a 5 6)
W Lispie listy, ze względu na jednostronne łączenie, mogą dzielić strukturę z innymi. To znaczy, że dwie listy mogą mieć ten sam ogon lub tę samą końcówkę. Na przykład po wykonaniu następującego kodu w Common Lispie:
(setf foo (list 'a 'b 'c))
(setf bar (cons 'x (cdr foo)))
listy foo
i bar
to odpowiednio (a b c)
i (x b c)
. Jednakże ogon (b c)
w obu listach to ta sama struktura. Nie jest to kopia, komórki wskazujące na b
i c
znajdują się w tym samym miejscu w pamięci dla obu list.
Dzielenie struktur zamiast kopiowania może owocować dużym wzrostem wydajności. Ta technika jednak może oddziaływać w niepożądany sposób z funkcjami, które modyfikują listy przekazane do nich jako argument. Modyfikacja jednej listy, jak na przykład zamiana symbolu c
na goose
, zaowocuje modyfikacją obydwu:
(setf (third foo) 'goose)
Ten kod zmienia foo
na (a b goose)
, przy okazji jednak zmieniając bar
na (x b goose)
, co może być niepożądane. Takie zachowanie może być przyczyną wielu błędów, a funkcje, które modyfikują przekazywane argumenty, są z tego powodu nazywane destrukcyjnymi.
Zwolennicy programowania funkcyjnego unikają funkcji destrukcyjnych. W dialekcie Scheme, który zaleca styl funkcyjny, nazwy funkcji destrukcyjnych są oznaczone ostrzegawczym wykrzyknikiem, lub, jak to jest popularnie nazywane, znakiem „bang” – na przykład funkcja set-car!
(czytaj set car bang), która zamienia car komórki cons. W Common Lispie funkcje destrukcyjne są powszechne; odpowiednikiem set-car!
jest funkcja rplaca
(skrót od „replace car”). Niemniej jednak ta funkcja jest dość rzadko używana, ponieważ Common Lisp zawiera specjalne udogodnienie, setf
, ułatwiające definiowanie i używanie funkcji destrukcyjnych. Częstym stylem programowania w CL jest pisanie kodu funkcyjnego (bez wywołań destrukcyjnych) podczas pisania wersji początkowej, by następnie dodać funkcje destrukcyjne jako optymalizację tam, gdzie to bezpieczne.
Lisp ewaluuje wyrażenia wprowadzane przez użytkownika. Symbole i listy zwracają zwykle jakieś prostsze wyrażenia – na przykład symbol zwraca wartość zmiennej, którą nazywa; (+ 2 3)
zwraca 5
. Większość innych form zwraca jednak same siebie – jeżeli wprowadzisz 5
do Lispu, zwróci 5
.
Każde wyrażenie może zostać zacytowane by zapobiec ewaluacji (jest to konieczne przy wprowadzaniu symboli i list). Tę rolę pełni specjalny operator quote
, lub jego skrót '
(pojedynczy znak apostrofu). Na przykład zwykle jeżeli wprowadzisz symbol foo
, dostaniesz z powrotem wartość odpowiadającej zmiennej (lub błąd, jeżeli takowa zmienna nie istnieje). Jeżeli jednak chcesz odwoływać się nie do zmiennej, a do samego symbolu, musisz użyć (quote foo)
lub, co znacznie popularniejsze, 'foo
.
Zarówno Common Lisp, jak i Scheme obsługują również operator backquote (zwykle zwany quasiquote przez użytkowników Scheme) wprowadzany jako znak '
. Jedyną różnicą ze zwykłym quote jest fakt, iż backquote pozwala na ewaluację i wstawienie wyniku wyrażenia do cytowanej listy za pomocą operatorów comma i comma-at. Jeżeli zmienna snue
ma wartość (bar baz)
, to '(foo ,snue)
jest ewaluowane do (foo (bar baz))
, podczas gdy '(foo ,@snue)
ewaluuje się do (foo bar baz)
. Backquote jest najczęściej używany przy definiowaniu makr.
Formy ewaluujące się do samych siebie i formy cytowane są odpowiednikiem literałów, znanych z innych języków. Możliwa jest jednak modyfikacja literałów wewnątrz kodu źródłowego. Na przykład jeżeli funkcja zwraca formę cytowaną, a kod wywołujący funkcje modyfikuje ją, wpłynie to na wynik zwracany przez kolejny wywołania danej funkcji.
(defun powinna-byc-stala
'(jeden dwa trzy))
(let ((zmienna (powinna-byc-stala)))
(setf (third zmienna) 'cos)) ; źle!
(powinna-byc-stala) ; zwraca (jeden dwa cos)
Modyfikacja formy cytowanej w taki sposób jest ogólnie uznawana za przykład złego stylu programowania, a część implementacji definiuje ją jako błędną (czego wynikiem jest zachowanie nieokreślone w plikach kompilowanych, ponieważ kompilator może połączyć podobne stałe, umieścić je w obszarze pamięci tylko do odczytu itp). Kiedy takie zachowanie jest zamierzone, odpowiednim sposobem jest użycie domknięcia.
Nowe dialekty Lispu można podzielić na podstawie zasad zasięgu (wiązania zmiennych) – część z nich używa zasięgów dynamicznych, część statycznych (leksykalnych). Scheme i Common Lisp używają domyślnie zasięgu leksykalnego, podczas gdy bardziej prymitywne dialekty używane jako języki zagnieżdżone w Emacsie i AutoCADzie używają zasięgów dynamicznych.
Przykład zasięgu dynamicznego w Emacs-Lisp
(defun foo ()
(* x x))
(defun bar ()
(let ((x 10))
(message (int-to-string (foo)))))
(bar)
Chociaż zmienna x nie została zdefiniowana wewnątrz funkcji foo to wywołanie funkcji bar wyświetli liczbę 100. W przypadku zasięgu dynamicznego zmienne zachowują się tak jakby były globalne, ale czas ich istnienia jest ograniczony do bloku, w którym zostały zdefiniowane.
Ten sam kod przepisany w Common Lispie zwróci błąd informujący, że zmienna x wewnątrz funkcji foo jest niezdefiniowana.
(defun foo ()
(* x x))
(defun bar ()
(let ((x 10))
(print (foo))))
(bar)
W przypadku funkcji która została utworzona z zasięgiem dynamicznym, jeśli dana zmienna nie znajduje się wewnątrz funkcji to jest ona poszukiwana od miejsca w którym została wywołana w górę aż do zasięgu globalnego. W przypadku zasięgu leksykalnego zmienne są poszukiwane od miejsca w którym ta funkcja została zdefiniowana. Drugi przypadek jest najczęściej stosowany w innych językach programowania.
Przykład domknięcia leksykalnego w dialekcie Scheme
(define (make-counter x)
(let ((count x))
(define (counter)
(set! count (+ count 1))
count)
counter))
(define count-form-10 (make-counter 10))
(display (count-form-10))
(newline)
(display (count-form-10))
(newline)
;Powyższy kod wyświetli 11 i 12.
Funkcja make-counter tworzy nową funkcję counter. Chociaż zakres zmiennej count po zakończeniu wywołania funkcji make-counter powinien się zakończyć, to funkcja counter zwrócona przez funkcję make-counter ma nadal do niej dostęp, tzn. zmienna count jest domknięta wewnątrz funkcji counter.
Główną różnicą między Lispem a innymi językami jest fakt, iż w Lispie kod źródłowy programu nie jest po prostu tekstem. S-wyrażenia, jak opisano wyżej, są drukowaną reprezentacją kodu, jednak gdy tylko zostają wprowadzone do systemu Lispu, są tłumaczone przez parser (funkcję read
) do postaci listy i struktur drzewiastych w pamięci.
Makra Lispu operują na tych strukturach. Ponieważ kod w Lispie ma taką samą strukturę jak lista, makra mogą być tworzone za pomocą wszystkich funkcji przetwarzających listy dostępnych w języku. W skrócie, wszystko, co Lisp może zrobić ze strukturą danych, makra Lispu mogą zrobić z kodem. W przeciwieństwie do tego, wynik parsowania w większości języków jest wyłącznie do użytku przez implementację i niedostępny dla programisty. Makra w C na przykład działają na poziomie preprocesora, zanim parser jest uruchamiany, i nie mogą restrukturyzować kodu programu tak jak makra Lispu.
W prostych implementacjach Lispu, ta struktura jest bezpośrednio interpretowana podczas uruchamiania programu; funkcja to dosłownie pewna lista, przez którą interpreter przechodzi podczas uruchamiania danej funkcji. Większość systemów Lispu do poważnych zastosowań zawiera jednak również kompilator. Kompilator tłumaczy listę do kodu maszynowego lub kodu bajtowego przed wywołaniem.
W wielu dialektach Lispu dostępna jest interaktywna linia poleceń, która może zostać włączona do IDE. Użytkownik wpisuje wyrażenia do linii poleceń, lub sprawia, by IDE wysyłało je do systemu Lispu. Lisp czyta (ang. read) wprowadzone wyrażenie, ewaluuje je (ang. evaluate) i wypisuje (ang. print) wynik. Z tego powodu linia poleceń Lispu jest nazywana „read-eval-print loop” (pętla wczytaj-ewaluuj-wypisz), lub w skrócie REPL.
Oto podstawowy opis działania REPL. Jest on uproszczony, nie bierze pod uwagę wielu elementów prawdziwego Lispu, jak na przykład cytowanie czy makra.
Funkcja read akceptuje ciąg znaków zawierający S-wyrażenie jako argument i zwraca odpowiadającą mu listę. Na przykład jeżeli użytkownik wprowadzi ciąg znaków „(+ 1 2)
”, read
przetłumaczy go na listę z trzema elementami: symbolem +
, liczbą 1 i liczbą 2. Ta lista jest również prawidłowym kawałkiem kodu w Lispie, to znaczy może być ewaluowana. Jest to możliwe, ponieważ car listy wskazuje na funkcję +
– operator dodawania, a dokładnie symbol plus, który wskazuje na funkcje, która dodaje liczby. Jest to ważne rozróżnienie, gdyż użytkownik może przypisywać takie same funkcje do prawie dowolnych ciągów symboli.
Funkcja eval
ewaluuje listę, zwracając inną listę jako wynik. Ewaluacja nie jest konieczne interpretacją – część systemów Lispu kompiluje w locie każde wyrażenie do kodu maszynowego. Opisywanie ewaluacji jako interpretacji jednak jest dużo prostsze: by zewaluować listę, w której car wskazuje na funkcję, eval
najpierw rekurencyjnie ewaluuje każdy argument w cdr, by następnie z wynikami tych ewaluacji wywołać daną funkcję. W danym przykładzie funkcją jest dodawanie, wywoływane z listą argumentów (1 2)
zwraca wynik 3
. Jest to wynik ewaluacji.
Zadaniem funkcji print
jest reprezentacja wartości wynikowej w sposób czytelny dla użytkownika. Dla prostych wartości takich jak 3
, to zadanie jest trywialne. Dla list print
musi przetworzyć całą strukturę i wypisać ją jako S-wyrażenie.
By zaimplementować lispowy REPL, wystarczy zaimplementować te trzy funkcje i funkcję nieskończonej pętli (implementacja funkcji eval
może być skomplikowana, gdyż wymaga implementacji wszystkich specjalnych operatorów takich jak if
). Gdy to zostanie wykonane, podstawowy REPL może być wprowadzony za pomocą tylko jednej linii kodu: (loop (print (eval (read))))
.
Kod w Lispie jest wartościowany zachłannie. W Common Lispie argumenty są wartościowane w kolejności od lewej do prawej, podczas gdy specyfikacja Scheme tego nie definiuje, pozostawiając kompilatorom możliwość optymalizacji.
Lisp początkowo miał niewiele struktur kontrolnych, wiele zostało dodanych w czasie, gdy język ewoluował. Pierwotny operator warunkowy Lispu, cond
, jest prekursorem późniejszej konstrukcji if-then-else
.
Programiści Scheme zwykle wyrażają pętle za pomocą rekursji ogonowej. Powszechność Scheme w nauczaniu akademickim sprawiła, że wielu uczniów zaczęło myśleć, że rekursja jest jedyną (lub najpopularniejszą) metodą opisywania iteracji w Lispie, co jest nieprawdą. Wszystkie często spotykane dialekty Lispu mają imperatywne konstrukcje pętli, począwszy od znanej ze Scheme pętli do
po złożoną konstrukcję loop
z Common Lispu. Przyczyną tak wielkiej popularności rekursji ogonowej w Scheme jest wsparcie tego w specyfikacji – daje ona określone zasady, jak traktować wywołania ogonowe, dzięki czemu programiści mogą mieć pewność, że zostaną one zamienione na pętlę. W przeciwieństwie do tego ANSI Common Lisp nie daje[18] określonych wskazówek odnośnie do rekursji ogonowej, co sprawia, że część implementacji traktuje wywołania ogonowe jak zwykłe. W związku z tym fakt, iż używanie rekursji ogonowej jako zamiennika pętli jest w Common Lispie niezalecane[19] nie jest jedynie kwestią stylistyczną, ale również wpływ na to ma wydajność (ponieważ nawet oczywiste wywołanie ogonowe niekoniecznie może być zamienione na pojedynczy skok) i poprawność (ponieważ wiele wywołań ogonowych niezamienionych na skok może grozić przepełnieniem stosu).
Część wyrażeń w Lispie to specjalne operatory, odpowiadające znanym z innych języków słowom kluczowym. Wyrażenia te wyglądają z zewnątrz tak samo, jak wywołania funkcji, różnią się jednak tym, że argumenty nie zawsze są wartościowane – lub, w przypadku pętli, mogą być wartościowane więcej niż raz.
W przeciwieństwie do większości innych języków, Lisp pozwala programiście na implementację własnych struktur kontrolnych wewnątrz samego języka. Część wbudowanych struktur kontrolnych jest zaimplementowanych jako makra i mogą być (za pomocą funkcji macroexpand
lub macroexpand-1
) rozwinięte przez programistę, który chce się dowiedzieć, jak działają.
Zarówno Common Lisp, jak i Scheme zawierają operatory służące do nielokalnej kontroli przepływu. Różnice między tymi operatorami to najgłębsze różnice między tymi dwoma dialektami. Scheme obsługuje wielowejściowe kontynuacje za pomocą operatora call/cc
, który pozwala na zapisanie (i późniejsze przywrócenie) określonego miejsca w wykonywaniu. Common Lisp nie obsługuje takich kontynuacji, ale zapewnia kilka sposobów na obsługę kontynuacji wyjścia.
Często ten sam algorytm może być wyrażony w Lispie zarówno funkcyjnie, jak i imperatywnie. Jak zaznaczono powyżej, Scheme raczej rekomenduje styl funkcyjny, używając rekursji ogonowej i kontynuacji do kontroli przepływu. Imperatywny styl programowania jest jednak wciąż możliwy. Styl preferowany przez wielu programistów Common Lispu może wydawać się bardziej znajomy programistom przyzwyczajonym do strukturalnych języków takich jak C, podczas gdy styl Scheme bardziej przypomina języki czysto funkcyjne takie jak np. Haskell.
Ze względu na wczesne specjalizowanie w przetwarzaniu list, Lisp posiada szeroką gamę funkcji wyższego rzędu służących do przechodzenia po sekwencjach. Często tam, gdzie w innych językach potrzebna byłaby bezpośrednia pętla (jak for
w C), w Lispie to samo zadanie może być wykonane przy pomocy jednej z funkcji wyższego rzędu, podobnie jest w innych funkcyjnych językach programowania.
Dobrym przykładem jest funkcja w Scheme zwana map
, a w Common Lispie mapcar
. Po podaniu funkcji i jednej lub kilku list, mapcar
stosuje tę funkcję kolejno do elementów list, zbierając wyniki do nowej listy.
(mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))
W tym przypadku funkcja +
stosowana jest do odpowiadających sobie par argumentów, zwracając w wyniku listę (11 22 33 44 55)
.
Oto kilka przykładów kodu w Common Lispie.
Program „Hello world”:
(print "Hello world")
Jak czytelnik mógł wywnioskować z powyższych opisów, składnia Lispu naturalnie skłania się ku rekursji. Matematyczne problemy, takie jak generacja rekursywnie zdefiniowanych zbiorów, są proste do zapisania w tej notacji.
Obliczenie silni danej liczby:
(defun factorial (n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))
Alternatywna implementacja, zwykle szybsza, jeżeli dana implementacja Lispu stosuje optymalizację rekursji ogonowej:
(defun factorial (n &optional (acc 1))
(if (<= n 1)
acc
(factorial (- n 1) (* acc n))))
Jeszcze inna implementacja, zamiast rekurencji wykorzystująca makro loop
z Common Lispu:
(defun factorial (n)
(loop for i from 1 to n
for fac = 1 then (* fac i)
finally (return fac)))
Funkcja odwracająca listę (wbudowana funkcja reverse
wykonuje to samo zadanie, istnieje też destrukcyjny odpowiednik nreverse
):
(defun -reverse (l &optional acc)
(if (atom l)
acc
(-reverse (cdr l) (cons (car l) acc))))
Funkcje wyższego rzędu są jednym z elementów programowania funkcyjnego. W Lispie funkcje można przypisywać do zmiennych przekazywać jako parametry do innych funkcji, mogą być także zwracane jako wartości przez funkcję. Funkcja, która operuje na innych funkcjach, jest nazywana funkcją wyższego rzędu (and Higher Order Procedure).
Przykład funkcji w Common Lispie
(print (reduce #'+ '(1 2 3 4 5 6 7 8)))
> 36
W powyższym przykładzie funkcja reduce jest funkcją wbudowaną, która skraca listę do pojedynczej wartości wywołując kolejno funkcję przekazywaną jako parametr dla wyniku poprzedniego wywołania funkcji i kolejnego elementu listy. W dialekcie Common Lisp przekazując funkcję jako parametr należy poprzedzić je dodatkowo znakiem cytowania, ponieważ w tym dialekcie istnieją dwie przestrzenie nazw dla zmiennych i funkcji. W przypadku tworzenia funkcji wyższego rzędu w dialekcie Scheme nie stosuje się cytowania.
(defun fun (x)
(lambda (a b)
(setq x (1+ x))
(+ a b x)))
(print (reduce (fun 0) '(1 2 3 4 5 6 7 8)))
W powyższym przykładzie zastosowano dodatkowo funkcję wyższego rzędu fun która zwraca funkcję sumującą, która dodatkowo dodaje indeks elementu w liście. Parametr x jest domknięty wewnątrz funkcji anonimowej. W miejsce wywołania funkcji fun można wstawić wyrażenie lambda.
(let ((x 0))
(print (reduce (lambda (a b)
(setq x (1+ x))
(+ a b x))
'(1 2 3 4 5 6 7 8))))
W Common Lispie aby wywołać funkcję przechowywaną w zmiennej lub parametrze trzeba ją wywołać za pomocą funkcji funcall lub apply
(defun make-fun (x)
(lambda (a b)
(setq x (1+ x))
(+ a b x)))
(defvar fun (make-fun 20))
(print (funcall fun 2 3))
;lub
(print (apply fun '(2 3)))
Jeżeli funkcja jest wewnątrz zmiennej nie trzeba jej cytować.
W przypadku dialektu Scheme czy Clojure nie stosuje się cytowania funkcji ponieważ oba języki posiadają jedną przestrzeń nazw dla funkcji i zmiennych, nie występuje w nich także funkcja funcall ponieważ funkcje wewnątrz zmiennych wywołuje się tak samo jak zwykłe funkcje.
Przykład funkcji w języku Clojure
(defn sum [& list]
(reduce + list))
Inne powszechnie stosowane funkcje wyższego rzędu to funkcja mapująca (wywołująca funkcję dla każdego elementu listy i zwracająca nową listę) i funkcja filtrująca (która zwraca listę pomniejszoną o te elementy dla których funkcja przekazana jako parametr zwraca wartość fałszu).
Makra są najpotężniejszym elementem języka Lisp i są dla niego unikalne. Dzięki makrom można dodawać nowe elementy do języka. Makro lispowe w odróżnieniu np. od makr występujących w pre-procesorze języka C operuje na kodzie języka Lisp tak jak na danych. W przypadku funkcji wyrażenia które są przekazywane jako parametry są obliczane przed wywołaniem samej funkcji a wynik tego wyrażenia jest przekazywany jako parametr, w przypadku makra wyrażenia nie są obliczane, ale przekazane w całości jako dane w parametrze, które są przez makro przetwarzane, następnie makro powinno zwrócić kod lispowy także w postaci listy która zostanie obliczona.
(defmacro def (name val)
(list 'setq name val))
Przykład makra do tworzenia zmiennych. Aby ułatwić pisanie makr dodano specjalny zapis cytowania z odwrotnym apostrofem. Odwrotne cytowanie działa tak jak normalne z wyjątkiem specjalnych znaków przecinka i przecinka i małpy, które obliczają wyrażeni (wyłączają cytowanie), przecinek małpa dodatkowo usuwa otaczające nawiasy (stosuje się to np. wtedy gdy przekazujemy ciąg wyrażeń do makra w parametrze typu &body). Wszystkie trzy znaki są to skróty interpretera Lipsu które są zamieniane na funkcje.
(defmacro while (test &body body)
'(do ()
((not ,test))
,@body))
Powyższe makro tworzy nowe wyrażenie implementujące pętlę while. Do testowania makr służą dwie funkcje macroexpand, która rozwija makro rekurencyjnie aż do napotkania podstawowych wyrażeń i funkcji oraz macroepxand-1, która rozwija makro o jeden poziom. Przykład użycia funkcji w interpreterze CLISP
(print (macroexpand '(while (< x 10)
(print x)
(setq x (1+ x)))))
(BLOCK NIL
(LET NIL
(TAGBODY #:LOOP-11439 (IF (NOT (< X 10)) (GO #:END-11440)) (PRINT X)
(SETQ X (1+ X)) (PSETQ) (GO #:LOOP-11439) #:END-11440
(RETURN-FROM NIL (PROGN)))))
Wywołanie macroexpand rozwinęło oprócz naszego makra także wbudowane makro do.
(print (macroexpand-1 '(while (< x 10)
(print x)
(setq x (1+ x)))))
(DO NIL ((NOT (< X 10))) (PRINT X) (SETQ X (1+ X)))
Dopiero wywołanie macroexpand-1 pokazało nasze makro po rozwinięciu.
Wiele różnych systemów i modeli obiektowości zostało zbudowanych na podstawie Lispu, między innymi:
CLOS obsługuje wielokrotne dziedziczenie, multimetody i system „kombinacji metod”. W gruncie rzeczy Common Lisp zawierający CLOS był pierwszym oficjalnie ustandaryzowanym językiem zorientowanym obiektowo.