Lisp

Lisp^[1] - rodzina języków programowania z długą historią i charakterystyczną składnią. Po raz pierwszy określony w 1958 roku, Lisp jest drugim z kolei pod względem wieku językiem programowania wysokiego poziomu (starszy jest tylko Fortran). Podobnie jak Fortran, Lisp wiele się zmienił w porównaniu z początkami. W historii istniało wiele dialektów Lispu, jednak dziś do najpopularniejszych należą dwa - Common Lisp i Scheme.

Lisp został stworzony jako wygodna matematyczna notacja dla programów komputerowych, oparta na rachunku lambda stworzonym przez Alonzo Churcha. Lisp szybko stał się najchętniej wybieranym językiem do badania i rozwoju sztucznej inteligencji. Ponieważ był jednym z pierwszych języków programowania wysokiego poziomu, Lisp wprowadził wiele nowych pomysłów, takich jak struktury drzewiaste, garbage collection, dynamiczne typowanie czy nowe koncepcje w programowaniu obiektowym.

Nazwa Lisp pochodzi od List Processing Language. Podstawową struktura danych w Lispie jest lista, kod źródłowy programów w Lispie jest budowany z list. W wyniku tego, programy w Lispie mogą manipulować kodem źródłowym jak zwykłą strukturą danych, co umożliwia pisanie makr, które pozwalają programiście tworzyć nową składnię lub nawet małe zagnieżdżone w Lispie języki.

Kod tworzony jako struktura danych sprawia, że Lisp ma charakterystyczną składnię. Cały kod źródłowy jest w postaci tzw. S-wyrażeń (S-expressions), czyli list otoczonych nawiasami. Wywołanie funkcji, makra lub specjalnej formy ma postać listy z nazwą funkcji lub operatora jako pierwszego elementu listy (car) i argumentów jako następnych (cdr). Na przykład, wywołanie funkcji o nazwie f z argumentami a, b i c może być wykonane za pomocą następującego kodu: (f a b c).

[edytuj] Historia

Lisp został wymyślony przez Johna McCarthy'ego w 1958 podczas jego pobytu na MIT. Opublikował jego projekt w artykule "Communications of the ACM" w roku 1960, pod tytułem "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (Rekursywne funkcje wyrażeń symbolicznych i ich maszynowe obliczanie, część I, część II nie została nigdy opublikowana). Pokazał, że za pomocą kilku prostych operatorów i notacji dla funkcji można zbudować prosty język implementujący maszynę Turinga.

Pierwszą implementację Lispu wykonał Steve Russel na komputerze IBM 704. Russel przeczytał artykuł McCarthy'ego i doszedł do wniosku (ku zdziwieniu McCarthy'ego), że funkcja eval może zostać zaimplementowana jako interpreter Lispu^[2]

Pierwszy kompletny kompilator Lispu stworzony w Lispie został napisany w 1962 przez Tima Harta i Mike'a Levina w MIT. ^[3] Wprowadził on model kompilacji inkrementalnej (ang. incremental compilation), dzięki czemu nie było wprowadzane rozróżnienie na funkcje kompilowane i interpretowane. Język użyty przez Harta i Levina był dużo bliższy nowoczesnemu stylowi Lispu niż wcześniejszy kod McCarthy'ego.

[edytuj] Wczesna historia

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 do S-wyrażeń, 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^[4] autorstwa Horace Enea i CGOLu autorstwa Vaughan Pratt.

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). Różne dialekty Lispu wciąż używają nazw car i cdr dla funkcji zwracających odpowiednio pierwszy element i resztę listy.

[edytuj] Genealogia i odmiany

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.

[edytuj] Ważne historycznie dialekty

• LISP 1.5 [2] – Pierwsza szeroko rozprzestrzeniona wersja, stworzona przez McCarthy'ego i innych pracowników MIT. Zawierała trochę ulepszeń w stosunku do oryginalnego interpretera "LISP 1", nie była jednak całkowicie nowa, jaka miała być wersja "LISP 2", zatem zdecydowano się na taki właśnie numer wersji.
• Stanford LISP 1.6 [3] – Wersja następna po LISP 1.5 stworzona w Stanford AI Lab i szeroko rozprzestrzeniona pod systemem TOPS-10 na maszynach PDP-10. Została zastąpiona przez Maclispa i InterLispa.
• MACLISP [4] – stworzony dla "Projektu MAC" w MIT (bez związku z Apple Macintosh ani z McCarthym), bezpośredni spadkobierca LISP 1.5. Działał na PDP-10 pod Multicsem. (MACLISP później został przemianowany na Maclisp, często go również nazywani MacLispem)
• InterLisp [5] – stworzony w BBN Technologies na komputery PDP-10 działające z systemem Tenex, później zaadoptowany dla maszyn Lispu Xeroxa. Mała wersja zwana "InterLISP 65" została wydana dla komputerów marki Atari bazujących na procesorze MOS 6502. Przez pewien czas Maclisp i InterLisp były w równie szerokim użyciu.
• Franz Lisp – początkowo projekt Berkeley, później zaimplementowany przezFranz Inc. Nazwa jest żartobliwą deformacją imienia "Franz Liszt". Nazwa "Franz Lisp" nie odnosi się do Allegro Common Lisp, odmiany Common Lispu sprzedawanej przez Franz Inc. w ostatnim czasie.
• ZetaLisp – używany na maszynach Lispowych, bezpośredni następca Maclispu.
• Common Lisp (1984), opisany w Common Lisp: The Language - połączenie kilku różnych podejść (ZetaLisp, Spice Lisp, NIL i S-1 Lisp) do stworzenia następcy Maclispu z pewnymi wpływami ze Scheme. Ta wersja Common Lispu była dostępna na wiele platform i uznawana za standard do czasu pojawienia się specyfikacji ANSI Common Lisp (ANSI X3.226-1994).
• EuLisp - próba stworzenia nowego, wydajnego i oczyszczonego dialektu Lispu.
• ISLisp - próba stworzenia nowego, wydajnego i oczyszczonego dialektu Lispu. Ustandaryzowany jako ISO/IEC 13816:1997 i później skorygowany w ISO/IEC 13816:2007 - Information technology -- Programming languages, their environments and system software interfaces -- Programming language ISLISP.
• IEEE Scheme - standard IEEE, 1178-1990 (R1995)
• ANSI Common Lisp - specyfikacja American National Standards Institute (ANSI) Common Lispu, stworzona przez podkomisję X3J13, która rozpoczęła pracę[6] wychodząc od Common Lisp: The Language jako dokumentu bazowego i działała na zasadzie publicznego konsensusu co do zagadnień przenośności i kompatybilności implementacji Common Lispu. Pomimo iż formalnie jest to standard ANSI, implementacje, sprzedaż, wykorzystanie i wpływ ANSI Common Lispu było i jest widoczne na całym świecie.

[edytuj] Powiązania ze sztuczną inteligencją

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^[5]. 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, and 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.

[edytuj] Od 2000

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. 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ć poprzez sprzedaż papierowej wersji książki Practical Common Lisp autorstwa Petera Seibela, wstępu do CL dla nowych programistów Lispu, opublikowanej w 2004 roku^[6]. Była ona drugą co do popularności książką o programowaniu na Amazon. Aktualnie dostępna jest za darmo w internecie^[7]. Można również zauważyć zwiększoną frekwencję na związanych z Lispem konferencjach^[8] i aktywność na powiązanych grupach^[9].

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^[10]. Wpływ na odzyskiwanie popularności przez Lisp mógł mieć również komentarz Petera Norviga^[11], autora książekParadigms 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.

[edytuj] Główne nowoczesne dialekty

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ą Emacs Lisp w Emacsie i AutoLisp w AutoCADzie.

[edytuj] Wpływ na świat programowania

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 poprzez 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 przyklad 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.

Zobacz też "The evolution of Lisp"^[12], artykuł autorstwa Guya Steele'a Jr. i Richarda Gabriela.

[edytuj] Składnia i semantyka

Uwaga: Przykłady w tym artykule są pisane w Common Lispie (aczkolwiek większość z nich jest również prawidłowa w Scheme).

Lisp jest językiem zorientowanym na wyrażenia. 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 jezykó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)^[13]. 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 XMLem.

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ę poprzez 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 jest byłaby bardziej użyteczna gdyby podstawić jakieś nietrywialne wyrażenie w miejsce nil.

[edytuj] Lambda wyrażenia

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 zewaluowanego 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. Lambda wyrażenia są traktowane tak samo jak nazwane funkcje. Wyrażenie

 ((lambda (arg) (+ arg 1)) 5)

zwraca więc 6.

[edytuj] Atomy

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).

[edytuj] Komórki cons i listy

Diagram dla listy (42 69 613)

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 do np. 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.

[edytuj] S-wyrażenia jako reprezentacja list

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, a 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ępujaco: (a . (b . (c . d)))).

[edytuj] Funkcje przetwarzające listy

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ę zawierajacą 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ść O(n).

 (append '(1 2) '(3 4))
 ;zwraca (1 2 3 4)

 (append '(1 2 3) '() '(a) '(5 6))
 ;zwraca (1 2 3 a 5 6)

[edytuj] Dzielone struktury

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.

[edytuj] Ewaluowanie form i cytowanie

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 wynikem 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.

[edytuj] Zasięg i domknięcia

Nowe dialekty Lispu można podzielić na podstawie zasad zasięgu - 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.

[edytuj] Kod źródłowy jako lista

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 przetwarzajacych 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 intepretowana 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 bytecode'i przed wywołaniem.

[edytuj] Ewaluacja i REPL

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 wprowadzisz ciąg znaków "(+ 1 2)", read przetłumaczy go na listę z trzema elementami: symbolem +, liczbą 1 i liczbą 2. Tak się składa, że ta lista jest również prawidłowym kawałkiem kodu w Lispie, to znaczy może być ewaluowana. Jest to możliwe ze względu na fakt, iż car listy wskazuje na funkcję + - operator dodawania.

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 naszym 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ętla|pętli] (oczywiście, implementacja funkcji eval może być nieco 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.

[edytuj] Struktury kontrolne

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ą imperatywe 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^[14] określonych wskazówek odnośnie 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^[15] 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 programisŧę, 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 obł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 programoania 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, poczas 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 programowaniwa.

Dobrym przykładem jest funkcja w Scheme zwana map a w Common Lispie mapcar. Po podaniu funkcji i jednej lub kilku list, mapcar stosuję 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).

[edytuj] Przykłady

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))))

[edytuj] Systemy obiektowe

Wiele różnych systemów i modeli obiektowości zostało zbudowanych na podstawie Lispu, między innymi:

• ObjectLisp^[16], lub Object Lisp, używany przez Lisp Machines Incorporated
• LOOPS (Lisp Object-Oriented Programming System) i późniejszy CommonLOOPS
• Flavors, stworzony na MIT i jego spadkobierca New Flavors, używany przez Symbolics
• Common Lisp Object System, CLOS, następca New Flavors i CommonLOOPS
• Lush - zorientowany obiektowo język programowania bazujący na Lispie
• SageCLOS zorientowany obiektowo interfejs do AutoLISPu stworzony przez Ralpha Gimeneza

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.

[edytuj] Cytaty

SQL, Lisp i Haskell to jedyne języki programowania, jakie znam, w których spędza się więcej czasu na myślenie niż na pisanie.'

— Philip Greenspun, marzec 2007, [7]

Przypuszczam, że powinienem nauczyć się Lispa, ale wydaje się on taki obcy.

— Paul Graham, listopad 1983, [8]

Można nawet przypuszczać, że Lisp zawdzięcza swoje przeżycie faktowi, że jego programy są listami, co wszyscy, włącznie ze mną, uznawali za wadę.

— John McCarthy, twórca Lispu, "Early History of Lisp"

Każdy dostatecznie skomplikowany program napisany w C lub Fortranie zawiera tworzone "w biegu", nieformalnie podane i pełne błędów implementacje połowy cech Common Lispu.

— Philip Greenspun, zwykle zwana 10. reguła programowania Greenspuna^[17]

Proszę nie przyjmować, że Lisp nadaje się tylko do programowania Animacji i Grafiki, SI, Bioinformatyki, B2B i E-Commerce, Zbierania Danych, aplikacji EDA/Semiconductor, Systemów Eksperckich, Finansów, Inteligentnych Agentów, Zarządzania Wiedzą, Mechanicznych CAD, Modelowania i Symulacji, Naturalnych Języków, Optymalizacji, Badań i Rozwoju, Analizy Ryzyka, Planowania, Telekomunikacji i Tworzenia Stron WWW tylko dlatego, że te rzeczy zostały wymienione na liście.

— Kent Pitman

Lisp z wyglądu przypomina owsiankę z wmieszanymi obciętymi paznokciami.

— Larry Wall, twórca Perla

Lisp będący najpotężniejszym i najprzyzwoitszym z języków, to język, który projekt GNU zawsze preferuje.

— Richard Stallman

Najwspanialszy pojedynczy język programowania, jaki kiedykolwiek zaprojektowano.

— Alan Kay

"Emacs" jest napisany w Lispie, który jest jedynym pięknym językiem programowania.

— Neal Stephenson, w In the Beginning...was the Command Line

Programista Lisp zna wartość wszystkich rzeczy, ale nie zna kosztu żadnej z nich

— Alan Perlis, Epigrams on Programming

Sądzę, że jest to jedyny język programowania który można szanować pod względem matematycznym, gdyż tylko o nim jestem w stanie udowadniać teorie!

— Gregory Chaitin

[edytuj] Komiksy

xkcd: Lisp, Lisp Cycles, With Apologies to Robert Frost

[edytuj] Przypisy

1. ↑ Odmiana: M. Lisp, D. Lispu, C. Lispowi, B. Lisp, N. Lispem, M. Lispie
2. ↑ Paul Graham w swojej książce Hackers & Painters na stronie 185 przytoczył wypowiedź McCarthy'ego: "Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the eval in my paper into IBM 704 machine code, fixing bug, and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..."
3. ↑ Tim Hart and Mike Levin: AI Memo 39-The new compiler. [dostęp 2006-10-13].
4. ↑ David Canfield Smith: MLISP Users Manual. [dostęp 2006-10-13].
5. ↑ 36-bitowy rozmiar słowa na PDP-6/PDP-10 został wprowadzony ze względu na użyteczność trzymania dwóch 18-bitowych Lispowych wskaźników w jednym słowie. "The PDP-6 project started in early 1963, as a 24-bit machine. It grew to 36 bits for LISP, a design goal." ("Projekt PDP-6 został rozpoczęty w 1963 jako maszyna 24-bitowa. Urosła do 36 bitów dla LISPu, celu projektowego.") [1]
6. ↑ Informacja o trzecim wydaniu PCL
7. ↑ Practical Common Lisp
8. ↑ Keeping Lisp alive and practical | Reg Developer
9. ↑ Programming language popularity
10. ↑ The Road To Lisp Survey. [dostęp 2006-10-13].
11. ↑ A Retrospective on PAIP
12. ↑ Guy L Steele Jr, Richard P Gabriel: The evolution of Lisp. [dostęp 2006-10-12].
13. ↑ The Jargon File - Lisp. [dostęp 2006-10-13].
14. ↑ 3.2.2.3 Semantic Constraints in Common Lisp HyperSpec
15. ↑ 4.3. Control Abstraction (Recursion vs. Iteration) w Tutorial on Good Lisp Programming Style autorstwa Kenta Pitmana i Petera Norvig, sierpień 1993.
16. ↑ str. 17 z Bobrow 1986
17. ↑ Phillip Greenspun: Research. [dostęp 2006-10-13].

[edytuj] Źródła

• "A History and Description of CLOS", Jim Veitch. Strony 107-158 Handbook of Programming Languages, Volume IV: Functional and Logic Programming Languages, ed. Peter H. Salus. 1998 (pierwsze wydanie), Macmillian Technical Publishing; ISBN 1-57870-011-6
• "Lisp - opis, realizacja i zastosowania", Jacek Martinek, stron 204, Wydawnictwa Naukowo-Techniczne, Warszawa 1980
• "Kompilator języka LISP 1.5, Jacek Martinek, M. Stroiński, Prace CO PAN, Warszawa 1974, nr 155
• "System programowania minikomputera K-202 w języku Lisp 1.5. Instrukcja programisty, Poznań Instytut Automatyki Politechniki Poznańskiej 1974
• Structure and Interpretation of Computer Programs, autorstwa Harold Abelson, Gerald Jay Sussman i Julie Sussman. 1996 (drugie wydanie), MIT Press; ISBN 0262011530.
• Lispers.org - Wybór cytatów o Lispie autorstwa znanych programistów Lispu.
• The implementation of LISP, Stanford
• My Lisp Experiences and the Development of GNU Emacs, odpis wykładu Richard Stallmana, 28 października 2002 roku, na Międzynarodowej Konferencji Lispu
• The Nature of Lisp, DefMacro
• Paul Graham, Hackers & Painters. Big Ideas from the Computer Age, 2004, O'Reilly, ISBN 0-596-00662-4

[edytuj] Zobacz też

• Porównanie dialektów Lispu

[edytuj] Linki zewnętrzne

• (en) comp.lang.lisp grupa Usenetowa na Google Groups
• (en) Związek Użytkowników Lispu
• (en) Wiki Związku Użytkowników Lispu, miejsce ogólnych dyskusji na tematy związane z Lispem
• (en) Historia LISPu w Computer History Museum
• (en) LispMachine.net - książki i informacje na temat Lispu
• (en) On Lisp, książka Paula Grahama
• (en) Książka "Practical Common Lisp"
• (en) Książka "Successfull Lisp"
• (en) Wywiad z Richarem Gabrielem (podcast)
• (en) Lisp in a Box, użyteczna paczka dla początkujących w Lispie - dla Windowsa lub Uniksa.