Common Lisp

Common Lisp

Pojawienie się	1984, specyfikacja ANSI w 1994
Paradygmat	wieloparadygmatowy (funkcyjny, obiektowy, proceduralny)
Typowanie	dynamiczne (statyczne na życzenie)
Implementacje	CLISP, AllegroCL, CMUCL, GCL, LispWorks, MCL, SBCL
Pochodne	CLtL1, CLtL2, ANSI Common Lisp
Twórca	komitet ANSI X3J13
Platforma sprzętowa	wieloplatformowy
Platforma systemowa	wieloplatformowy
Strona internetowa

Common Lisp (często skracane do CL) – dialekt języka programowania Lisp, stworzony przez ANSI (X3.226-1994) jako specyfikacja, nie implementacja. Istnieje kilka implementacji, zarówno zamkniętych, jak i dostępnych jako FOSS. Common Lisp jest wieloparadygmatowym językiem programowania ogólnego przeznaczenia, skupiającym się na programowaniu funkcyjnym, pozwalając jednak stosować obiektowość, co daje programiście dużą swobodę.

Składnia

Common Lisp jest dialektem Lispu. Używa S-wyrażeń do opisywania kodu i struktur danych. Funkcje i wywołania makr zapisuje się w postaci list z nazwą funkcji (lub makra) jako pierwszym elementem.

(+ 2 2)           ; sumuje 2 i 2, zwraca 4

(setf p 3.1415)   ; ustawia wartość zmiennej p na 3.1415, zwraca 3.1415

#+(or) 37 42 ; komentowanie wyrażeń; wynik to 42

; tworzy funkcję podnoszącą liczbę do kwadratu
(defun kwadrat (x)
  (* x x))

; wywołuje powyższą funkcję
(kwadrat 3)        ; zwraca 9
; specjalna forma let tworzy nowe zmienne lokalne, których zasięg ogranicza się do końca bloku.
(let ((a 6) (b 4))
  (+ a b)) ; zwraca 10

Typy danych

Typy skalarne

Do typów liczbowych należą liczby całkowite, zmiennoprzecinkowe i zespolone oraz ułamki zwykłe. Common Lisp korzysta z dużych liczb do reprezentowania wartości liczbowych o dowolnym rozmiarze i precyzji. Typ ułamkowy nie jest dostępny w większości innych języków. Przy zwracaniu liczby CL automatycznie nadaje jej właściwy typ.

Znaki w CL nie muszą się koniecznie zawierać w standardzie ASCII. Wynika to z faktu, że Lisp został stworzony przed standardem. Niektóre implementacje dopuszczają znaki ze standardu Unicode.

Typ symboliczny jest wspólny dla Lispów, ale raczej nieznany poza nimi. Symbol to unikatowy, nazwany obiekt z kilkoma slotami na dane. Symbole w Lispie są często używane podobnie do nazw w innych językach (przechowywanie wartości zmiennej, nazywanie funkcji), jednakże istnieje wiele innych sposobów użycia. W CL w zależności od miejsca użycia symbol zwraca powiązaną z nim funkcję lub wartość. Część symboli przy użyciu zwraca same siebie, na przykład T, NIL czy wszystkie symbole z pakietu KEYWORDS.

Wartości logiczne w Common Lispie reprezentowane są przez symbole T oraz NIL, każda wartość, która nie jest NIL, jest automatycznie uznawana za prawdę.

Struktury danych

Do typów sekwencyjnych w CL zaliczają się listy i wektory. Wiele funkcji może pracować na różnych typach sekwencyjnych, na przykład map.

Listy w CL są tworzone za pomocą funkcji cons, czasami skracane do tej nazwy są także komórki cons (ang. cons cell, czasami też używa się nazwy para, ang. pair). Cons jest strukturą danych z dwoma slotami zwanymi car i cdr. Lista to łańcuch połączonych komórek cons. W liście slot car komórki cons zawiera element listy (na przykład liczbę, znak czy inną listę), a slot cdr wskazuje na następny element listy, lub na symbol NIL, gdy dany dana komórka jest ostatnia w liście. Listy mogą być wykorzystywane do implementacji drzew, grafów i innych struktur danych.

Common Lisp obsługuje wielowymiarowe tablice (array) i potrafi w razie potrzeby dynamicznie zmieniać ich rozmiar. Wielowymiarowe tablice mogą być używane na przykład do implementacji macierzy. Wektor (vector) to jednowymiarowa tablica. W tablicy można przechowywać wszystkie typy danych (nawet różne typy w jednej tablicy) lub można mieć tablice specjalizowane do przechowywania określonego typu, na przykład wektor liczb zmiennoprzecinkowych. W standardzie określone są dwie wyspecjalizowane tablice – string to wektor znaków, a wektor bitowy (bit-vector) to wektor zawierający bity.

Hashe przechowują zależności między kluczami a wartościami tak, by wydajne było pobranie wartości na podstawie klucza.

Przestrzenie nazw (package, znane w niektórych językach jako namespace) są realizowane jedynie dla symboli; parsing niekwalifikowanych ciągów znaków na symbole w przestrzeni nazw odbywa się zwykle podczas kompilacji, ale jeszcze przed semantyczną analizą grafu wyrażeń symbolicznych. Przestrzeń nazw może eksportować symbole, oznaczając je jako zewnętrzny interfejs, jednak ścisła enkapsulacja nie jest w żaden sposób zapewniona. Zawsze możliwe jest odwoływanie się do prywatnych symboli, jak i redefinicja cudzych klas, zmiennych czy we wzorcowych implementacjach samego kompilatora. Jest to filozofia tworzenia oprogramowania wewnątrz maszyny wirtualnej obecna również w Smalltalku wedle której używane biblioteki, aplikacja, kompilator tworzą organiczną całość.

Struktury, podobnie do struktur C i pascalowych rekordów, reprezentują złożone struktury danych z dowolną liczbą i typem pól (zwanych slotami). Struktury różnią się od zwykłych obiektów z metaklasą standard-class złożonością obliczeniową dostępu do slotu. Przy optymalnej implementacji pobranie wartości zapisanej w strukturze będzie zawsze O(1), niezależnie od ilości slotów, jednak za cenę niemożności redefinicji struktur, tudzież konieczności ponownej kompilacji kodu po redefinicji struktury.

CLOS

Klasy w Common Lisp Object System posiadają możliwość modyfikacji zachowania obiektów poprzez metaklasy i użycie „protokołu metaobiektowego”, pozwalając na zachowania nie planowane przez twórców, jak np. obiekty automatycznie dodające i uzupełniające się w bazie danych SQL czy korzystające z modelu propagacji więzów przypominającego w działaniu arkusz kalkulacyjny.

Protokół metaobiektowy (MOP) nie został zawarty w standardzie ANSI, jednak książka opisująca jego działanie i przykładową implementację stała się de-facto standardem wśród implementacji Lispu.

W przeciwieństwie do języków takich jak Smalltalk czy C++, metody nie należą do przestrzeni nazw klas; należą one do generic function znajdującej się w przestrzeni nazw pakietu (lub modułu, namespace). Możliwa jest specjalizacja typu nie tylko pierwszego argumentu (self, this) ale każdego z wymaganych argumentów. Określanie pasującej metody jest względnie wydajne dzięki sprytnej memoizacji opisanej w AMOP.

Funkcje

W CL funkcje są traktowane jako typ danych. Umożliwia to na przykład pisanie funkcji, które pobierają inne funkcje jako argument albo zwracających inne funkcje. Standardowa biblioteka CL szeroko wykorzystuje tę możliwość, na przykład funkcja sort pobiera funkcję porównującą jako argument. Pozwala to na sortowanie nie tylko każdego typu danych, ale także umożliwia sortowanie złożonych struktur danych zależnie od klucza.

 (sort (list 5 2 6 3 1 4) #'>)
 ; Sortuje listę używając > jako operatora porównującego.
 ; Zwraca (6 5 4 3 2 1).

 (sort (list '(9 a) '(3 b) '(4 c))
       (lambda (x y) (< (car x) (car y))))
 ; Sortuje listę zależnie od pierwszego elementu podlisty.
 ; Zwraca ((3 b) (4 c) (9 a)).
 ; Lub: (sort (copy-seq '((9 a) (3 b) (4 c))) #'< :key #'car)
 ; korzystając z ''keyword parameters'.

Model wartościowania dla funkcji jest bardzo prosty. Gdy parser napotyka na formę (F A1 A2 A3 ...), zakłada, że symbol F jest albo:

1. Specjalnym operatorem (z ustalonej listy)
2. Zdefiniowanym wcześniej makrem
3. Nazwą funkcji

Jeżeli F jest nazwą funkcji, argumenty A1, A2, A3 itd. są wartościowane w porządku od lewej do prawej oraz, o ile funkcja istnieje, jest wywoływana z wartościami zwróconymi przez argumenty. Jeśli zaś F desygnuje makro, zostanie ono rozszerzone rekursywnie aż zostaną jedynie specjalne formy i wywołania funkcji.

Definiowanie funkcji

Makro defun służy do definiowania funkcji. Definicja zawiera nazwę funkcji, nazwy jej argumentów oraz wyrażenia stanowiące zawartość funkcji (ang. body).

 (defun square (x)
    (* x x))

Definicja funkcji może zawierać deklaracje, które dostarczają kompilatorowi informacji o ustawieniach optymalizacji lub typach danych argumentów. Może także zawierać dane do dokumentacji, z których Lisp może generować interaktywną dokumentację:

 (defun square (x)
    (declare (integer x) (optimize (speed 3) (debug 0) (safety 1)))
    "Oblicza kwadrat liczby podanej w argumencie x"
    (* x x))

Anonimowe funkcje są definiowane przy użyciu lambda-wyrażeń. Styl programowania w Lispie często wykorzystuje anonimowe funkcje jako argumenty do innych funkcji.

Jest wiele operatorów związanych z definiowaniem i manipulowaniem funkcjami. Na przykład funkcja może zostać skompilowana za pomocą funkcji compile. Część implementacji CL uruchamia funkcje w interpreterze, jeżeli nie wydano instrukcji kompilacji, inne domyślnie kompilują w locie.

Przestrzeń nazw funkcji

Przestrzeń nazw funkcji jest oddzielona od przestrzeni zmiennych, co jest główną różnicą między CL a Scheme. Do operatorów definiujących nazwy w przestrzeni funkcji należą m.in. defun, flet i labels.

Aby poprzez nazwę przekazać funkcję jako argument do innej funkcji należy użyć specjalnego operatora function, zwykle skracanego do #'. Pierwszy przykład użycia funkcji sort (powyżej) odwołuje się do funkcji poprzez symbol > za pomocą #'>.

Model wartościowania Scheme jest prostszy – jest tylko jedna przestrzeń nazw i wszystkie elementy formy są wartościowane w dowolnej kolejności – nie tylko argumenty. Przez to kod napisany w jednym dialekcie może być mylący dla programisty bardziej doświadczonego w innym. Na przykład wielu programistów CL używa nazw opisujących zmienną (np. list czy string), co może powodować problemy poprzez lokalne przysłanianie nazw funkcji. By wywołać funkcję znajdującą się w przestrzeni wartości, konieczne jest użycie funkcji funcall czy apply - złożone formy jako pierwszy element ewaluowanej listy są bezwarunkowo niedozwolone. Pociągnęło to za sobą również pozornie nie związane odmienności w kulturach Scheme i Common Lispu - przykładowo, w CL-u klasy znajdują się w osobnej "przestrzeni nazw" z interfejsem find-class, zaś w Scheme dodawane do globalnego środowiska jak np. w systemie obiektowym Meroon.

Pytanie, czy oddzielna przestrzeń nazw dla funkcji jest zaletą, czy nie, jest źródłem sporów w społeczności Lispu. Jest to zwykle nazywane debatą Lisp-1 vs. Lisp-2. Nazwy te zostały wymyślone w artykule z 1988 r. przez Richarda Gabriela i Kenta Pitmana, którzy porównują w nim obydwa podejścia.

Inne typy danych

Do pozostałych typów w CL zaliczają się:

• Ścieżki (pathnames) reprezentują pliki w systemie plików. Ścieżki w CL są bardziej ogólne niż zasady nazewnictwa w większości systemów plików, co sprawia, że dostęp do plików w różnych systemach operacyjnych z poziomu Lispu jest zwykle identyczny.
• Strumienie (streams) wejścia i wyjścia reprezentują źródła danych binarnych lub tekstowych, takich jak np. terminal czy otwarte pliki.
• Condition to typ reprezentujący błąd, wyjątek czy inne zdarzenie, na które program może odpowiedzieć.

Makra

Makra w użyciu przypominają funkcje. W odróżnieniu od funkcji gdzie przekazane wyrażenia zostają obliczane a tylko wyniki tych wyrażeń przekazane do funkcji, do makr przekazywane są wyrażenia w całości. Makra reprezentują transformację kodu źródłowego, ponieważ zwracają one nowy kod w postaci listy s-wyrażeń które dopiero potem zostają wywołane. W skrócie można powiedzieć, że makra dostają kod w postaci danych (s-wyrażeń) i zwracają inny kod, który następnie zostaje obliczony.

Makra pozwalają programistom tworzyć nowe składniowe formy języka. Na przykład, makro działające jak until z Perla można napisać tak:

 (defmacro until (test &body body)
   `(do ()
        (,test)
      ,@body))

 ;; przyklad
 (until (= (random 10) 0)
   (write-line "Hello"))

Wszystkie makra muszą być rozwinięte, aby kod źródłowy zawierający je mógł być normalnie ewaluowany lub kompilowany. Makra można uznać za funkcje, które przyjmują i zwracają drzewa składniowe (lispowe S-wyrażenia). Są wywoływane przed ewaluatorem lub kompilatorem, by wyprodukować finalny kod źródłowy. Makra są pisane w pełni funkcjonalnym Common Lispie i mogą używać dostępnych w nim funkcji. Użyty powyżej zapis z backqoute (`) w CL upraszcza zwykły przypadek podstawiania w szablonie kodu.

Higiena makr i przechwytywanie zmiennych

Makra Common Lispu umożliwiają wstawianie symboli istniejących w środowisku wywołującym, pozwalając na generację kodu wykorzystującego zmienne istniejące w kontekście; są to tzw. niehigieniczne makra.

Taka praktyka może powodować nieprzewidziane i niezwykłe błędy. Niektóre dialekty Lispu, jak Scheme, unikają ich dzięki używaniu tzw. higienicznych makr. W Common Lispie można zwykle uniknąć niechcianego przechwycenia, używając unikatowych symboli (generowanych przez funkcję gensym) – ich użycie nigdy nie spowoduje kolizji z istniejącym symbolem.

Przydatne może się okazać klasyczne makro with-gensyms

(defmacro with-gensyms ((&rest syms) &body body)
  `(let ,(loop for i in syms collect (list i `(gensym ,(symbol-name i))))
     ,@body))

Kolejną sprawą jest nieumyślne przysłanianie istniejącej funkcji/makra w rozwinięciach makr. Na przykład w następującym (niepoprawnym) kodzie:

 (macrolet ((do (...) ... cos-innego ...))
    (until (= (random 10) 0) (write-line "Hello")))-

Kod makra UNTIL zostanie rozwinięty do formy wywołującej DO które powinno odwoływać się do wbudowanego makra DO. Jednak w tym kontekście, DO może mieć zupełnie inne znaczenie.

Porównanie z innymi dialektami Lispu

Common Lisp jest najczęściej porównywany ze Scheme — ponieważ są one najpopularniejszymi dialektami Lispu. Scheme poprzedza CL, i pochodzi nie tylko z tej samej tradycji Lispu, ale ma też kilku wspólnych twórców – Guy L. Steele'a, z którym Gerald Jay Sussman zaprojektował Scheme, przewodził komitetowi standaryzacyjnemu Common Lispu. Common Lisp, w przeciwieństwie do Emacs Lisp i AutoLISP (które są językami rozszerzeń osadzonymi w określonych produktach), jest językiem programowania ogólnego przeznaczenia. Tak jak Scheme, używa leksykalnego zasięgu zmiennych. Istnieją jednak pewne różnice kulturowe między społecznościami Scheme i CL i według Kenta Pitmana zachodzą wątpliwości, czy Scheme w ogóle zalicza się do rodziny języków lispowych.

Większość z dialektów Lispu których konstrukcja nawiązuje do Common Lispu – jak ZetaLisp i Franz Lisp – używa dynamicznych zasięgów zmiennych w swoich interpreterach a leksykalnych w kompilatorach. Scheme, zainspirowany ALGOLem 68 (w którym było to przez wielu uważane za dobry pomysł), wprowadził wyłączne użycie leksykalnego zasięgu zmiennych. CL wspiera również dynamiczny zasięg, ale takie zmienne muszą być wyraźnie zadeklarowane jako "specjalne". Nie ma różnicy pomiędzy zasięgiem w interpreterach i kompilatorów ANSI CL.

Common Lisp jest czasami nazywany Lispem-2 a Scheme Lispem-1, odnosząc się do używania przez CL osobnych przestrzeni nazw dla funkcji i zmiennych. (Prawdę mówiąc CL ma wiele przestrzeni nazw, listy własności (ang. property lists), makra zwykłe i kompilatora, wartość dynamiczna i funkcyjna) Pomiędzy zwolennikami CL i Scheme istnieje długotrwały spór na temat wad i zalet używania wielu przestrzeni nazw. W Scheme (najczęściej) trzeba unikać nadawania zmiennym nazw kolidujących z nazwami funkcji; funkcje napisane w Scheme mają często argumenty o nazwach lis, lst czy lyst by nie konfliktowały z wbudowaną funkcją list. W CL podczas przekazywania argumentu do funkcji trzeba się odwołać do jej przestrzeni nazw –- co jest również często spotykane, jak w przykładzie sort powyżej.

CL różni się od Scheme również pod względem obsługi zmiennych boolowskich. Scheme używa specjalnych wartości #t i #f by reprezentować prawdę i fałsz. CL, zgodnie z konwencją starszych Lispów używa symboli T i NIL, gdzie NIL oznacza również pustą listę. W CL, jakakolwiek wartość inna niż NIL jest traktowana jako prawda przez wyrażenia warunkowe takie jak if tak jak wartości inne niż #f w Scheme. To pozwala niektórym operatorom działać jako predykaty i zwracać użyteczną wartość dla dalszych obliczeń.

Na koniec, dokumenty standaryzacyjne Scheme wymagają optymalizacji rekursji ogonowej, podczas gdy standard CL nie. Większość implementacji CL oferuje optymalizację rekursji ogonowej, lecz zwykle tylko wtedy, gdy programista użyje dyrektywy optymalizacyjnej. Mimo wszystko styl programowania CL nie faworyzuje powszechnego stosowania rekursji jaki preferuje styl Scheme – to, co programista Scheme wyraziłby za pomocą rekursji ogonowej, programista CL wyraziłby raczej za pomocą wyrażenia iteracyjnego w do, dolist, loop czy (ostatnio) za pomocą pakietu iterate.

Implementacje

Common Lisp jest zdefiniowany przez specyfikację (jak Ada i C) a nie przez jedną implementację (jak Perl). Jest wiele implementacji, i standard wyraża obszary gdzie mogą się one różnić.

W dodatku, implementacje zwykle posiadają pakiety biblioteczne, które zapewniają funkcjonalność nie zawartą w standardzie. Zostało stworzonych wiele bibliotek Wolnego Oprogramowania by wspierać te właściwości w przenośny sposób, w szczególności Common-Lisp.net i projekt Common Lisp Open Code Collection. Istnieje również wiki cliki pomagające programistom w wymianie bibliotek i informacji o implementacjach.

Gdy ANSI CL był definiowany w 1984, nie istniał powszechny teraz zwyczaj definiowania w ramach standardu obsługi formatów plików, protokołów sieciowych etc. Dlatego w ANSI CL nie jest zdefiniowana nawet obsługa gniazd sieciowych. Mimo to istnieją de facto standardy uznawane przez społeczność, takie jak McCLIM jako interfejs graficzny czy usocket jako interfejs do gniazd sieciowych. Istnieje również klasa bibliotek stanowiących niewiele więcej niż interfejs zapewniający kompatybilność między implementacjami cliki.net.

Common Lisp został zaprojektowany do implementacji za pomocą kompilatorów przyrostowych. Standardowe deklaracje optymalizujące kompilację (jak funkcje inline) zostały przedstawione w specyfikacji języka. Większość implementacji CL kompiluje funkcje do kodu maszynowego. Inne kompilują do kodu bajtowego, który zwiększa przenośność kodu binarnego kosztem prędkości. Błędne mniemanie o tym, że Lisp jest językiem wyłącznie interpretowanym zostało spowodowane najprawdopodobniej przez fakt, że środowiska Common Lispu zapewniają interaktywny wiersz poleceń i kompilowanie funkcji jedna po drugiej, w sposób inkrementalny.

Niektóre uniksowe implementacje, jak CLISP, mogą być używane jako [4] interpretery skryptów uniksowych; tj. wywoływane przez system w przezroczysty sposób, jak interpreter Perla czy powłoki uniksowej.

Lista implementacji

Wolne implementacje CL to między innymi:

• CMUCL, pierwotnie napisany w Uniwersytecie Carnegie Mellon, obecnie utrzymywany przez grupę ochotników jako Wolne Oprogramowanie. CMUCL używa szybkiego kompilatora do kodu natywnego. Jest dostępny na Linuksie i BSD dla Intela x86; Linuksie dla Alpha; i Solaris, IRIX i HP-UX na ich natywnych platformach.
• Steel Bank Common Lisp (SBCL), odgałęzienie CMUCL. "Ogólnie mówiąc, SBCL w odróżnieniu od CMU CL kładzie większy nacisk na przenośność." [5]. SBCL działa na tych samych platformach co CMUCL, poza HP/UX; w dodatku działa na Linuksie dla PowerPC. SPARC i MIPS, oraz Mac OS X. Eksperymentalne wsparcie dla systemów Microsoft Windows.
• CLISP, przenośna implementacja kompilująca do kodu bajtowego, działa na wielu uniksowych i uniksopodobnych systemach (włączając Mac OS X), jak i Microsoft Windowsie i kilku innych systemach.
• GNU Common Lisp (GCL), kompilator CL spod znaku projektu GNU. Nie jest jeszcze w pełni zgodny ze standardem ANSI, GCL jest implementacją wybraną przez kilka wielkich projektów językowych włączając narzędzia matematyczne Maxima, AXIOM i ACL2. GCL działa pod GNU/Linuksem na jedenastu różnych architekturach, oraz pod Windowsem, Solaris i FreeBSD
• Embeddable Common Lisp (ECL), zaprojektowany do osadzania w programach C.
• OpenMCL [6], wolne/open source'owe odgałęzienie Macintosh Common Lispu. Jak sugeruje nazwa, OpenMCL był z początku natywny dla Macintosha, obecnie działa na Mas OS X, Darwinie i GNU/Linuksie dla PowerPC i Intela x86-64.
• Movitz implementuje środowisko Lispu na komputerach x86 bez żadnego systemu operacyjnego.
• System Poplog system implements a version of CL, with POP-11, and optionally Prolog, and Standard ML (SML), implementuje wersję CL za pomocą POP-11 i opcjonalnie Poploga oraz Standard MLa, pozwalając na programowanie mieszanym językiem. Posiada również zintegrowany, podobny do Emacsa, edytor komunikujący się z kompilatorem.
• Związane z Javą:
  • Armed Bear Common Lisp [7] to implementacja CL która działa na Wirtualnej Maszynie Javy. Zawiera kompilator do kodu bajtowego Javy i pozwala na dostęp do bibliotek Javy. Armed Bear CL jest składnikiem Armed Bear J Editora, choć może być używany niezależnie.
  • Jatha [8], biblioteka Javy która implementuje znaczny podzbiór Common Lispu.

Komercyjne implementacje to między innymi:

• Allegro Common Lisp od Franz, Inc.
• LispWorks od LispWorks Ltd.
• Macintosh Common Lisp od Digitool, Inc.
• Corman Lisp od Corman Technologies
• Scieneer Common Lisp od Scieneer Pty Ltd..

Bibliografia

• Common Lisp HyperSpec
• Kurs Programowania w języku Common Lisp
• Common Lisp Cookbook