LISP

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

LISP (ang. LISt Processing) jest językiem programowania zorientowanym na programowanie funkcyjne. Główne cechy to:

notacja prefiksowa
dynamiczne typowanie (zmienne nie mają przypisanego typu, ale ich wartości tak)
zdolność traktowania kodu źródłowego jako obiektów pierwszej klasy (ang. first-class objects)

Poza różnymi językami maszynowymi i asemblerami, Lisp jest drugim po Fortranie najstarszym, nadal w powszechnym użyciu, językiem. Podobnie jak Fortran, Lisp zmienił się znacząco od czasu powstania. Dokładniej, Lisp stał się dziś raczej rodziną języków znanych jako "dialekty Lispa".

[edytuj] Historia Lispa

Lisp został stworzony w roku 1958 przez Johna McCarthy na MIT. McCarthy wydał artykuł w CACM w roku 1960, zatytułowany "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (Rekursywne Funkcje Wyrażeń Symbolicznych i ich Maszynowe Obliczanie, część I - części drugiej nigdy nie opublikowano). Lisp został pierwotnie zaimplementowany na komputerze IBM 704, a dwie z instrukcji tej maszyny stały się podstawowymi operacjami Lispa do rozbioru list: car (Contents of Address Register - Zawartość rejestru adresowego) i cdr (Contents of Decrement Register - Zawartość rejestru dekrementacji). Do dziś operacje lispa zwracające pierwszy element i resztę listy są nazywane car i cdr.

Z powodu elastyczności i wyrazistości, Lisp stał się popularny w środowiskach związanych ze sztuczną inteligencją. Jednak Lisp ma również słabe strony: programy w Lispie tworzą znaczne ilości danych pośrednich, co zajmuje pamięć i wymusza garbage collection. To sprawiło, że trudno było uruchomić Lispa na tańszym sprzęcie. W latach siedemdziesiątych rosnąca społeczność Lispa i dotacje rządu USA doprowadziły do stworzenia maszyn Lispa - sprzętu dedykowanego do uruchamiania programów lispowych.

W latach osiemdziesiątych i dziewięćdziesiątych dwudziestego wieku podjęto wielki wysiłek zunifikowania niezliczonych dialektów Lispa w jeden język. Nowy język, Common Lisp, był zasadniczo nadzbiorem dialektów, które zastąpił. W roku 1994 ANSI opublikowało standard Lispa pod tytułem ANSI X3.226-1994 Information Technology Programming Language Common Lisp. Niestety, do tego czasu światowa popularność Lispa stała się znacznie mniejsza niż w czasach rozkwitu.

Język ten jest jednym z najstarszych będących nadal w użyciu. W podobnym wieku są Algol, Fortran i COBOL, z których dwa ostatnie nadal są używane.

[edytuj] Wydajność

Przez długi czas wydajność programów w Lispie była dużym problemem - wymagania zarówno pamięciowe, jak i obliczeniowe były kilkukrotnie większe niż w przypadku innych, popularnych w tamtym czasie języków, np. C czy Fortran. Dzisiejsze kompilatory są jednak bardziej zaawansowane i posiadają bardzo dobre techniki optymalizacyjne - program napisany w Lispie jest najczęściej szybszy od swojego odpowiednika w C++ lub Javie, co w połączeniu z znacznie krótszym czasem implementacji algorytmu (średnio 8 razy), czyni Lisp wyjątkowo atrakcyjnym językiem.[1]

[edytuj] Składnia

Lisp jest językiem zorientowanym na wyrażenia. W odróżnieniu od wielu innych języków, nie ma w nim rozróżnienia między wyrażeniem a instrukcją. Cały kod i dane są zapisywane jako wyrażenia. Kiedy wyrażenie jest wartościowane, tworzy wartość (lub listę wartości), które mogą zostać użyte w innych wyrażeniach.

Artykuł McCarthy'ego z roku 1958 wprowadził dwa typy składni: S-wyrażenia (wyrażenia symboliczne), które nazywane są również sexpami, oraz M-wyrażenia (metawyrażenia), które wyrażają funkcje S-wyrażeń. M-wyrażenia nigdy nie zdobyły popularności i dziś prawie wszystkie Lispy używają S-wyrażeń do operowania zarówno danymi jak i kodem. Nadmiar nawiasów w S-wyrażeniach był często krytykowany, a jednym z żartobliwych akronimów na Lisp stało się "Lots of Irritating Superfluous Parenthesis" (czyli Wiele Denerwujących Zbędnych Nawiasów). Niemniej to właśnie składnia S-wyrażeń jest jedną z większych przyczyn mocy Lispa, gdyż jest wyjątkowo regularna, co ułatwia komputerową obróbkę.

Poleganie na wyrażeniach daje Lispowi dużą elastyczność. Ponieważ funkcje w Lispie są również listami, więc mogą być obrabiane dokładnie tak, jak dane. Można łatwo pisać programy manipulujące kodem innych programów. Nazywa się to metaprogramowaniem. Wiele dialektów Lispa wykorzystuje tę cechę do tworzenia systemów makr (umożliwiają stworzenie własnego języka do specyficznego zadania - przykładem jest np. makro format albo loop).

Lista w Lispie jest zapisywana w nawiasach okrągłych, elementy listy są rozdzielone spacjami. Elementami listy mogą być atomy oraz listy. Pusta lista () jest często oznaczana symbolem nil.

Na przykład:

(1 2 "foo")

jest listą, której elementy mają wartości: 1, 2, "foo". Te wartości mają proste typy: są to dwie wartości całkowite i ciąg znaków, i nie muszą być deklarowane jako takie.

Atomy mogą składać się z dowolnych znaków np.:

12
x^2-2x+5
Wikipedia
e-m@il
+++
x-2         to wcale nie znaczy "x minus 2", jest to pełnoprawna nazwa atomu "x-2"

W przypadku gdy atom reprezentuje liczbę, np. 123, łańcuch znaków, np. "foo", albo coś „oczywistego” dla danej implementacji Lispa (np. Common Lisp zapis liczba/liczba interpretuje jako ułamek zwykły), wówczas wartość jest obliczana natychmiast, natomiast dla innych atomów nie jest to możliwe. Na przykład:

> 15                                         liczba
15
> "Wikipedia"                                łańcuch znaków
"Wikipedia"
> wikipedia                                  atom
Zmiennej WIKIPEDIA nie przypisano wartości

Atomom można przypisać wartość, czyli innymi słowy nadać nazwę pewnej wartości; co więcej, pojedyncza wartość może mieć kilka nazw.

> 1
1
> (setq jeden 1)                             atomowi 'jeden' przypisuje wartość (liczbę)
> jeden
1
> (setq wikipedia "Wolna Encyklopedia")      atomowi 'wikipedia' przypisujemy wartość (łańcuch znaków)
> wikipedia
"Wolna Encyklopedia"

Nic nie stoi na przeszkodzie, aby z atomem nie była związana żadna wartość.

Wyrażenia są zapisywane jako listy, z użyciem notacji przedrostkowej. Pierwszy element listy jest nazwą formy, czyli funkcji, operatora, makra lub formy specjalnej (patrz niżej). Pozostała część listy to argumenty. Na przykład funkcja list zwraca swoje argumenty jako listę, więc wyrażenie:

(list 1 2 "foo")

zostanie zwartościowane jako lista (1 2 "foo"). Jeśli któreś z argumentów są wyrażeniami, to wartościuje się je rekurencyjnie przed zwartościowaniem wyrażenia głównego. Na przykład:

(list 1 2 (list 3 4))

da w wyniku listę (1 2 (3 4)). Uwaga: trzeci argument jest listą - listy mogą być zagnieżdżane.

Podobnie traktuje się operatory arytmetyczne. Wyrażenie:

(+ 1 2 3 4)

da wynik 10. Należy zwrócić uwagę, że jest to zapis bardziej oszczędny (chociaż nie tak znajomy) niż "1+2+3+4", co jest odpowiednikiem w zapisie wrostkowym.

Formy specjalne to Lispowy odpowiednik konstrukcji kontrolnych. Na przykład forma specjalna if wymaga trzech argumentów. Jeśli pierwszy z nich jest różny od nil to obliczany jest drugi argument. W przeciwnym wypadku oblicza się trzeci argument. Zatem wyrażenie:

(if nil
    (list 1 2 "foo")
  (list 3 4 "bar"))

da w wyniku (3 4 "bar"). (Oczywiście, byłoby znacznie użyteczniej umieścić nietrywialne wyrażenie zamiast nil!)

Inna forma specjalna, defun, jest używana do definiowania funkcji. Argumenty defun to lista wartości i wyrażenie, które funkcja ma obliczać.

[edytuj] Przykładowe programy

Oto przykłady kodu lispowego. O ile nie są one typowe dla Lispa stosowanego w praktyce, o tyle są typowe dla Lispa nauczanego na kursach informatyki.

Jak można zauważyć z powyższej dyskusji, składnia Lispa pozwala na naturalne zastosowanie rekursji. Skomplikowane matematycznie problemy są często proste do zapisania w Lispie. Paradoksalnie, "łatwe" zadania bywają w podstawowym Lispie trudne do rozwiązania. Na przykład składnia Lispa nie ułatwia pisania programów w sposób sekwencyjny (w stylu programowania proceduralnego), co jest punktem startowym większości innych języków programowania. Pisanie programów sekwencyjnie ułatwiają liczne makra, np. LOOP - mini-język oparty o makra, umożliwiający bardzo łatwe tworzenie bardzo skomplikowanych pętli.

Następująca funkcja oblicza silnię swojego parametru:

(defun factorial (n)
  (if (<= n 1)
      1
    (* n (factorial (- n 1)))))

Ta funkcja jest wydajniejsza, bo używa rekursji prawostronnej:

(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
    (factorial (- n 1) (* acc n))))

Kolejna funkcja pobiera listę argumentów i zwraca jej odwrócenie. (Chociaż Lisp ma wbudowaną funkcję reverse, robiącą dokładnie to samo).

(defun reverse (l &optional acc)
  (if (atom l)
      acc
    (reverse (cdr l) (cons (car l) acc))))

Przykład użycia makra format[2] do wypisania tekstu:

(format nil "Here ~[are~;is~:;are~] ~:*~R pupp~:@P." 1)
"Here is one puppy"

(format nil "Here ~[are~;is~:;are~] ~:*~10R pupp~:@P." 5)
"Here are 5 puppies."

(setf psy-Ani '("Mika" "Reksio" "Jerzy" "Ares"))
(format nil "~{~#[Ania nie ma psów.~:;Imiona psów Ani to: ~@{~A~^,~}~]~:}" psy-Ani)
"Imiona psow Ani to: Mika,Reksio,Jerzy,Ares"

(setf psy-Ani '())
(format nil "~{~#[Ania nie ma psów.~:;Imiona psów Ani to: ~@{~A~^,~}~]~:}" psy-Ani)
"Ania nie ma psów"

W rzeczywistości zostanie to zamienione na kilka(naście) instrukcji Lispa.

[edytuj] System obiektowy

Do użytku z Lispem zaprojektowano wiele systemów obiektów, między innymi:

Flavors, stworzony w MIT
The Common Lisp Object System, CLOS (potomek Flavors)

Cechy CLOS to dziedziczenie wielokrotne, przydzielanie wielokrotne (multiple dispatch) i system łączenia metod. W rzeczywistości Common Lisp, zawierający w sobie CLOS, był pierwszym językiem zorientowanym obiektowo, który został oficjalnie ustandaryzowany.

[edytuj] Genealogia i odmiany

LISP, oryginalna wersja McCarthy'ego, rozwijana na MIT.
MACLisp, bezpośredni potomek LISPa, stworzony dla projektu MAC na MIT (nie ma to żadnego związku z Apple Macintosh)
ZetaLisp, używany na maszynach lispowych Lisp machine, bezpośredni potomek MACLispa.
InterLisp, rozwijany na MIT, później zaadaptowany jako Lisp "west coast" dla maszyn lispowych Xeroxa. Mała wersja, zwana "InterLisp 65" została stworzona dla komputerów Atari z procesorem MOS 6502.
Franz Lisp, pierwotnie projekt Berkeley później prowadzony przez Franz Inc.
Common Lisp, wywodzi się od ZetaLisp i Franz, z odrobiną InterLisp.
Gold Hill Common Lisp, wczesna implementacja dla komputerów PC.
Coral Lisp, implementacja dla Macintosha.
Scheme, minimalistyczny Lisp zaprojektowany do nauczania. Pierwszy dialekt używający zmiennych leksykalnych zamiast dynamicznych.
AutoLISP/Visual LISP, język umożliwiający pisanie rozszerzeń AutoCADa.
Emacs Lisp, język skryptowy edytora Emacs.
Oak Lisp, Lisp zorientowany obiektowo, oparty na Scheme.
Cambridge Lisp, pierwotnie zaimplementowany na komputerach mainframe IBM. Wydany przez Metacomco dla Amigi.