Common Lisp

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

Spis treści

1 Składnia
2 Typy danych
3 Makra
4 Variable capture i shadowing
5 Common Lisp Object System
6 Porównanie z innymi dialektami Lispa
7 Implementacje
- 7.1 Lista implementacji
8 Żródła

[edytuj] Składnia

Common Lisp jest dialektem Lispa. 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
; 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

[edytuj] Typy danych

[edytuj] Typy skalarne

Do typów liczbowych należą liczby całkowite, zmiennoprzecinkowe i zespolone oraz ułamki zwykle. 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. Kilka nowych implementacji (jak np. SBCL) dopuszcza znaki ze standardu Unicode.

Typ symboliczny jest wspólny dla Lispów, ale zwykle nieznany poza nimi. Symbol to unikalny, 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ę.

[edytuj] Struktury danych

Do typów sekwencyjnych w CL zaliczają się listy, wektory, wektory bitowe i ciągi. 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 cells, czasami też używa się nazwy pary, 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 (arrays) 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.

Hash tablice przechowują przypisania obiektów. Każdy obiekt może być użyty zarówno jako klucz, jak i jako wartość. Hash tablice, podobnie do zwykłych tablic, są dynamicznie powiększane lub pomniejszane w razie potrzeby.

Paczki to zbiory symboli używane przeważnie do podziału programu na przestrzenie nazw. Paczka może eksportować symbole oznaczając je jako zewnętrzny interfejs.

Struktury, podobnie do struktur C i pascalowych rekordów, reprezentują złożone struktury danych z dowolną liczbą i typem pól (zwanych slotami).

Instancje klas są podobne do struktur, ale tworzone przez CLOS.

[edytuj] 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)).

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

Specjalnym operatorem (z ustalonej listy)
Zdefiniowanym wcześniej makrem
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.

[edytuj] Definiowanie funkcji

Makro defun służy do definiowania funkcji. Definicja zawiera nazwę funkcji, nazwy jej argumentów oraz jej ciało:

(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 (number 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.

[edytuj] 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.

Pytanie, czy oddzielna przestrzeń nazw dla funkcji jest zaletą, czy nie, jest źródłem sporów w społeczności Lispa. 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^[1].

[edytuj] Inne typy

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 plików w większości plików operacyjnych, co sprawia że dostęp do plików w różnych systemach operacyjnych 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.
Common Lisp ma wbudowany generator liczb pseudolosowych (PRNG). Losowy stan (random state) reprezentuje źródło liczb pseudolosowych, umożliwiając użytkownikowi pobranie liczby czy odtworzenie sekwencji "losowych" liczb.
Condition to typ reprezentujący błąd, wyjątek czy inne zdarzenie, na które program może odpowiedzieć.

[edytuj] Makra

Makra w użyciu przypominają funkcje. Jednakże, zamiast reprezentowania wartościowanego wyrażenia, reprezentują raczej transformację kodu źródłowego.

Makra pozwalają programistom tworzyć nowe syntaktyczne 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))

 ;; example
 (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 normalnym 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.

[edytuj] Variable capture i shadowing

Makra Common Lispa mogą doświadczać variable capture (przechwytywanie zmiennych), gdy symbole w rozwinięciu makra są identyczne jak symbole w kontekście wywołującym, co daje programiście dodatkowe możliwości modyfikacji składni.

Variable capture może powodować nieprzewidziane i niezwykłe błędy. Niektóre dialekty Lispa, jak Scheme, unikają ich dzięki używaniu składni tzw. "higienicznych makr". W Common Lispie można zwykle uniknąć niechcianego przechwycenia używając gensymów: symboli, których unikalność jest gwarantowana i możliwych do użycia w makrach bez ryzyka przechwycenia.

Kolejną sprawą jest nieumyślne przysłanianie operatorów 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.

Common Lisp częściowo rozwiązuje ten problem zabraniając redefiniowania operatorów wbudowanych, jak DO w przykładzie. Co więcej, użytkownicy mogą odseparować swój kod zamykając go w pakietach. Wbudowane symbole znajdują się w pakiecie COMMON-LISP, który nie będzie przysłaniany przez symbole w pakiecie użytkownika.

[edytuj] Common Lisp Object System

Common Lisp zawiera zestaw narzędzi do programowania zorientowanego obiektowo, Common Lisp Object System albo CLOS który jest jednym z najpotężniejszych systemów obiektowych dostępnych w jakimkolwiek języku. Początkowo zaproponowany jako dodatek, CLOS został przyjęty jako część standardu ANSI Common Lispa. CLOS jest dynamicznym systemem obiektowym i różni się znacznie od narzędzi do OOP znajdywanych w statycznych językach jak C++ czy Java.

[edytuj] Porównanie z innymi dialektami Lispa

Common Lisp jest najczęściej porównywany ze Scheme— ponieważ są one najpopularniejszymi dialektami Lispa. Scheme poprzedza CL, i pochodzi nie tylko z tej samej tradycji Lispa 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 Lispa. 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 zakresu zmiennych.

Większość z dialektów Lispa których konstrukcja nawiązuje do Common Lispa - jak ZetaLisp i Franz Lisp - używa dynamicznych zakresó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 zakresowania zmiennych. CL wspiera również zakresowanie dynamiczne, ale takie zmienne muszą być wyraźnie zadeklarowane jako "specjalne". Nie ma różnicy pomiędzy zakresowaniem interpreterów 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, np. te do przechowywania etykiet go, nazw bloków i słów kluczowych makra loop) 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ą optymalizacja 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.

[edytuj] 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.

Common Lisp został zaprojektowany do implementacji za pomocą kompilatorów inkrementalnych. Standardowe deklaracje optymalizujące kompilację (jak funkcje inline) zostały przedstawione w specyfikacji języka. Większość implementacji CL kompiluje funkcje do natywnego 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 Lispa zapewniają interaktywny wiersz poleceń i że funkcje są kompilowane jedna po drugiej, w sposób inkrementalny.

Niektóre uniksowe implementacje, jak CLISP, mogą być używane jako [http://clisp.cons.org/impnotes/quickstart.html#quickstart-unix interpretery skryptów uniksowych; tj. wywoływane przez system w przejrzysty sposób, jak interpreter Perla czy powłoki uniksowej.

[edytuj] Lista implementacji

Wolne implementacje CL to między innymi:

CMUCL, oryginalnie 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ść." [2]. 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. SBCL nie używa interpretera; wszystkie wyrażenia są kompilowane do kodu natywnego. Eksperymentalne wsparcie dla Windowsa.
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 zawierania w programach C.
OpenMCL [3], wolne/open source'owe odgałęzienie Macintosh Common Lispa. 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 Lispa 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 [4] 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 [5], biblioteka Javy która implementuje znaczny podzbiór Common Lispa.