Lisp (programski jezik)

 

 

Džon Makarti (gore) i Stiv Rasel (dole)

Lisp je projektovao Džon Makarti 1958. godine. Lisp je prvi put implementiran od strane Stiva Rasela na IBM 704 računaru. Rasel je pročitao Makartijev rad i zaključio da izračunavanje u Lispu može da se implementira na mašinskom jeziku. Rezultat toga je interpretator koji je mogao da pokreće Lisp programe, ali i da računa vrednosti Lisp izraza.

Prvi kompletan Lisp kompajler, napisan u Lisp-u, implementirali su Tim Hart i Majk Levin 1962. godine.

Tokom 1980-ih i 1990-ih radilo se na ujedinjavanju novih dijalekata Lisp-a. Tako je nastao programski jezik Common Lisp. Prvi standard za Common Lisp, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp.", objavio je ANSI 1994. godine.

Edsger Dajkstra je na dodeli Tjuringove nagrade 1972. godine rekao: "Sa nekoliko osnovnih principa svog zasnivanja, on (LISP) je pokazao izuzetnu stabilnost. Osim toga, LISP je bio nosač značajnog broja najsavremenijih kompjuterskih aplikacija. LISP je u šali opisan kao "najinteligentniji način da se zloupotrebi računar". Mislim da je takav opis veliki kompliment, jer prenosi pun ukus slobode: on je pomogao veliki broj naših najtalentovanijih kolega u razmišljanju o ranije nemogućim stvarima."^[3]

Lisp je jezik koji se oslanja na izraze. Kada se izraz evaluira, on vraća vrednost, koja se može iskoristiti u drugim izrazima.

Svaka vrednost može biti bilo koji tip podataka.

U Lisp-u se navode dva tipa sintakse: S-izrazi (simbolički izrazi), koji oslikavaju unutrašnju reprezentaciju i koda i podataka, i M-izrazi (meta izrazi), koji izražavaju funkcije S-izraza. Skoro svi Lisp jezici danas koriste S-izraze za kod i podatke.

Ono što je Lisp odmah odvojilo od drugih porodica jezika, jeste upotreba zagrada. Sintaksa koja koristi S-izraze je zaslužna za lakše korišćenje programskog jezika Lisp. Međutim, sintaksa Lisp-a nije ograničena na tradicionalnu notaciju pomoću zagrada. Može se proširiti i uključiti i druge notacije.

Oslanjanje na izraze daje veliku fleksibilnost jeziku. Lisp funkcije su napisane kao liste, stoga se one mogu obrađivati kao bilo koji drugi podaci. Ovo omogućava lako pisanje programa koji koriste druge programe (metaprogramiranje). Mnogi Lisp dijalekti koriste ovu odliku, koristeći makro sisteme, što omogućava proširenje jezika gotovo bez ograničenja.

Lista se zapisuje tako što se između zagrada navedu elementi liste, odvojeni razmacima. Na primer, (1 2 foo) je lista čiji elementi su tri atoma 1, 2 i foo; 1 i 2 jesu celi brojevi, dok je foo specijalan tip podataka u Lisp-u, simbol.

Prazna lista () se takodje moze predstaviti kao specijalni atom nil. Ovo je jedini entitet u Lisp-u koji je ujedno i lista i atom.

Izrazi se zapisuju kao liste, koristeći prefiksnu notaciju. Na primer, ako navedemo

 (A B C D)

A predstavlja ime funkcije (ime makroa, lambda izraz ili ime specijalnog operatora), dok su B, C i D argumenti.

Liste mogu biti ugnježdene. Na primer:

 (A (B C) D (E (F G)))

Aritmetički operatori se tretiraju na sledeći način:

 (+ 1 2 3 4)

Ovaj izraz ima vrednost 10. Ekvivalentan izraz u infiksnoj notaciji jeste "1 + 2 + 3 + 4". Aritmetički operatori u Lisp-u su n-arne funkcije, tako da mogu imati bilo koliko argumenata. Operator inkrementiranja u C-u "++" ovde je implementiran kao:

 (incf x)

što je ekvivalentno sa (setq x (+ x 1)), koje vraća novu vrednost od x.

Specijalni operatori, koji se ponekad nazivaju i specijalnim formama obezbeđuju kontrolne strukture. Na primer, specijalni operator if ima tri argumenta. Ako prvi argument nije nil, određuje se vrednost drugog argumenta, a ako jeste, onda se određuje vrednost trećeg argumenta. Na primer,

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

biće (3 4 "bar").

lambda je jedan specijalni operator koji se koristi za vezivanje promenljivih vrednostima koje su evaluirane unutar izraza. Takođe se koristi za pravljenje funkcija. Argumenti operatora lambda jesu liste argumenata, a vrednost koju vraća je vrednost poslednjeg evaluiranog izraza. Na primer, izraz

 (lambda (arg) (+ arg 1))

predstavlja funkciju koja uzima jedan argument, vezuje ga za arg i vraća broj za jedan veći od argumenta. Lambda izrazi se pozivaju na isti način kao i funkcije. Na primer:

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

vraća vrednost 6.

U prvobitnom LISP-u su postojale dva osnovna tipa podataka: atomi i liste. Lista je konačan niz elemenata gde je svaki element za sebe lista ili atom, a atom je ili broj ili simbol, koji ima formu identifikatora. Na primer,

 (FOO (BAR 1) 2)

sadrži tri elementa: simbol FOO, listu (BAR 1) i broj 2. Suštinska razlika između atoma i listi jeste ta da su atomi nepromenljivi i jedinstveni, dok je svaka lista poseban objekat koja može da se menja nezavisno od drugih listi.

 

Lisp lista je jednostruko povezana lista. Svaka ćelija liste se naziva cons(od CONStruct cell ili CONStruct list) i sastoji se od dva pokazivača, koji se nazivaju car(Contents of Address part of Register) i cdr(Contents of Decrement part of Register). Oni, redom, odgovaraju elementu i pokazivaču u povezanoj listi.

Ako uzmemo da nam dati cons bude glava povezane liste, onda njegov car pokazivač pokazuje na prvi element liste, a cdr pokazuje na ostatak liste. Iz tog razloga car i cdr funkcije imaju i naziv prvi i ostatak kada se govori o elementima koji su deo povezane liste.

Veoma se često koriste kod rekurzivno napisanih funkcija koje u svom prvom prolazu obrađuju samo jedan element, a zatim se sa cdr uzima ostatak liste koji se rekurzivno prosleđuje istoj funkciji da isti posao obavi i za sve druge elemente

Zbog toga što su cons i liste univerzalne u Lisp sistemima, česta je zabluda da su oni jedine strukture podataka u Lisp-u. U stvari, postoje i druge strukture podataka, poput vektora (nizova), heš tabeli...

Cons može da se napiše u dotted-pair notaciji kao (a . b), gde a predstavlja car, a b predstavlja cdr.

Lisp ima mnoge ugrađene funkcije za pristup i kontrolu listi. Lista se može kreirati direktno pomoću funkcije list, koja uzima bilo koji broj argumenata i vraća listu tih argumenata.

 (list 1 2 'a 3)
 ;Output: (1 2 a 3)

 (list 1 '(2 3) 4)
 ;Output: (1 (2 3) 4)

Funkcija cons se može iskoristiti za dodavanje na početak liste.

 (cons 1 '(2 3))
 ;Output: (1 2 3)

 (cons '(1 2) '(3 4))
 ;Output: ((1 2) 3 4)

Funkcija reverse obrće listu.

 (reverse '(a b c d))
 ;Output: (d c b a)

Funkcija length računa dužinu liste.

 (length ‘(a (b c) d)) 
 ;Output: 3

 (length ‘(a b c d)) 
 ;Output: 4

Funkcija append spaja dve ili više listi.

 (append '(1 2) '(3 4))
 ;Output: (1 2 3 4)

 (append '(1 2 3) '() '(a) '(5 6))
 ;Output: (1 2 3 a 5 6)

Postoji još mnogo funkcija ovog tipa, koje proveravaju da li je određen argument prazna lista, da li je taj argument uopšte lista i slične. ( null , listp…)

Lisp liste, koje su jednostruko povezane, mogu da podele strukturu međusobno. To jest, dve liste mogu da imaju isti rep ili krajnji niz cons ćelija. Na primer, nakon izvršenja sledećeg Common Lisp koda

(setf foo (list 'a 'b 'c))
(setf bar (cons 'x (cdr foo)))

liste foo i bar su (a b c) i (x b c), redom. Međutim, rep (b c) je ista struktura u obe liste. Nije kopija već cons ćelije koje pokazuju na b i c su na istoj memorijskoj lokaciji.

Međutim, ukoliko se, u nekom trenutku, zameni b ili c u foo, zameniće se i u bar, što je neočekivani rezultat. Ovo može biti izvor grešaka, pa su funkcije koje menjaju svoje argumente označene kao destruktivne, upravo iz ovog razloga.

Lisp određuje vrednost izraza koji korisnik unese. Simboli i liste određuju vrednost nekog drugog izraza, uglavnom jednostavnijeg. Na primer, simbol određuje vrednost promenljive koju imenuje; (+ 2 3) vraća 5. Kako god, većina oblika vraća vrednost njih samih: ako se unese 5 u Lisp-u, on vraća 5.

Svaki izraz može biti obeležen kako bi se sprečila njegova evaluacija (ako je potreban za simbole i liste). To je uloga specijalnog operatora quote ili skraćeno' (jednostruki navodnik). Na primer, ako se ukuca foo vratiće se vrednost odgovarajuće promenljive (ili greška ako ta promenljiva ne postoji). Ako je potrebno referisati na neki literalni simbol, kuca se (quote foo) ili 'foo.

Samoevaluirajući oblici i forme navođenja su u Lisp-u ekvialentni sa literalima. To omogućava modifikaciju (promenljivih) literala u programskom kodu. Na primer, ako funcija vraća neku formu navođenja i kod koji poziva funkciju modifikuje formu, to može promeniti ponašanje funkcije u narednim iteracijama.

(defun should-be-constant ()
  '(one two three))

(let ((stuff (should-be-constant)))
  (setf (third stuff) 'bizarre))   ; loše!

(should-be-constant) ; vraća (one two bizarre)

Lisp je podeljen oko upotrebe dinamičke i statičke (odnosno leksičke) upotrebe prostora imena. Clojure, Common Lisp i Scheme podrazumevano koriste statičko definisanje polja promenljive, dok Newlisp, Picolisp i ugrađeni jezici u Emacs-u i AutoCAD-u koriste dinamičko.

Osnovna razlika između Lisp-a i ostalih jezika je u tome što je tekstualna reprezentacija programa prilično čitljiv opis same unutrašnje strukture podataka (povezanih listi, simbola, brojeva, karaktera, itd.) kao što je u osnovi Lisp sistema.

Zahvaljujući tome, Lisp implementira veoma jak sistem makroa. Kao i u ostalim makro jezicima kao što je C, makro vraća kod koji može biti kompajliran. Za razliku od C-ovih makroa, u Lisp-u su makroi funkcije i u njima je moć Lisp-a.

Pošto kod u Lisp-u ima istu strukturu kao liste, makroi mogu biti izraženi pomoću bilo koje funkcije za rad sa listama. Ukratko, sve što može Lisp sa strukturom podataka, Lisp makroi mogu sa kodom.

U jednostavnoj implementaciji Lisp-a, ova struktura u vidu liste je direktno interpretirana da pokrene program; funkcija je doslovno deo strukture liste koja prevedena od strane interpretatora pri izvršavanju. Većina Lisp sistema sadrži i kompajler. On prevodi strukturu liste na mašinski jezik ili bajtkod za izvršavanje. Ovaj kod može biti pokrenut jednako brzo kao i u C-u, na primer.

Makroi nude interesantne opcije. Neke implementacije Lisp-a imaju mehanizam eval-when koji omogućava kodu da bude prisutan za vreme kompilacije (kad zatreba makrou) ali nije prisutan u emitujućem modulu.^[4]

Lisp jezici su najčešće korišćeni sa interaktivnom komandnom linijom, koja se može kombinovati sa IDE-om. Lisp čita unete izraze, evaluira ih i štampa rezultat. Zbog ovoga, Lisp komandna linija se naziva "read–eval–print petlja", odnosno REPL.

read funkcija prihvata tekstualni S-izraz kao ulaz i parsira ga u unutrašnju strukturu podataka.

Na primer, ako se ukuca tekst (+ 1 2) u promptu, read ga prevodi u povezanu listu sa tri elementa: simbol +, broj 1 i broj 2. Ova lista je takođe validan deo Lisp koda i može se evaluirati.

Treba napomenuti da se foo čita kao pojedinačni simbol. 123 će se pročitati kao broj sto dvadeset tri, a "123" će se pročitati kao string "123".

eval funkcija evaluira podatke, vraća nula ili više Lisp podataka kao rezultat. Evaluacija ne mora značiti isto što i interpretacija; pojedini Lisp sistemi kompajliraju svaki izraz u mašinski kod koji se može izvršiti direktno od strane CPU. Svakako je jednostavno objasniti evaluaciju kao interpretiranje: Da bi se evaluirala lista čiji car imenuje funkciju, eval prvo evaluira svaki od argumenata koji je prosleđen njenom cdr-u, potom primenjuje funkciju na argumente. U ovom slučaju, funkcija je sabiranje i primenjujući je na argumente liste (1 2) daje rezultat 3. To je, zapravo, rezultat evaluacije.

Simbol foo evaluira vrednost simbola foo. Podatak kao što je string "123" evaluira isti string. Lista (quote(1 2 3)) evaluira (1 2 3).

Posao funkcije print je da prikaže izlaz korisniku. Za jednostavan rezultat kao što je 3 to je trivijalno. Izraz koji evaluira deo strukture liste bi zahtevao da print prođe kroz listu i štampa je kao S-izraz.

Za implementaciju Lisp REPL-a, neophodno je implementirati navedene tri funkcije i funkciju "beskonačna petlja". Naravno da implementacija funkcije eval nije jednostavna, posebno jer je potrebno implementirali sve specijalne operatore kao što su if ili lambda.

Kada je ovo završeno, REPL nije ništa drugo do jedna linija koda: (loop (print (eval (read)))).

Lisp REPL omogućava redigovanje ulaza, istoriju ulaza, upravljanje greškama kao i interfejs dibagera.

Lisp se uglavnom evaluira pohlepno.

Lisp je prvobitno imao samo nekoliko struktura, ali veliki broj je dodavan tokom evolucije jezika. (Lisp-ov prvobitni uslovni operator, cond, prethodnik je kasnije if-then-else strukture.

Pojedine Lisp-ove kontrolne strukture su specijalni operatori, ekvivalenti sintaksnim ključnim rečima drugih jezika. Izrazi koji koriste ove operatore imaju isti izgled kao pozivi funkcija, razlika je jedino u tome što argumenti ne moraju biti evaluirani ili u iterativnom slučaju mogu biti evaluirani više od jedanput.

Za razliku od ostalih viših programskih jezika, Lisp dopušta programeru da implementira kontrolne strukture koristeći jezik. Nekoliko kontrolnih strukutura je implementirano kao Lisp makroi, a nekoliko njih mogu biti makro razvijeni od strane programera koji znaju kako to radi.

I Common Lisp i Scheme imaju operatore za nelokalnu kontrolu toka. Razlike u ovim operatorima ujedno čine i razlike između ova dva dijalekta.

Neretko, isti algoritam u Lisp-u može biti iskazan i imperativnim i funkcionalnim stilom. Scheme preferira funkcionalni stil koristeći repnu rekurziju. Kako god, imperativni stil je još uvek moguć. Stil koji preferiraju Common Lisp programeri bliži je programerima koji koriste struktuirane jezike kao što je C, dok je onaj koji preferiraju Scheme programeri bliži čisto funkcionalnim jezicima kao što je Haskell.

Lisp ima široki spektar funkcija višeg reda koje su u relaciji sa itaracijom u naredbama. U mnogim slučajevima gde bi u drugom jeziku bila neophodna petlja (kao for u C-u) u Lisp-u stvar rešava funkcija višeg reda.

Evo primera Common Lisp koda.

Osnovni "Hello World" program:

  (print "Hello world")

Lisp sintaksa je podesna za rekurziju. Matematički problemi kao što je nabrajanje rekurzivno definisanim skupovima jednostavno se izražavaju u ovoj notaciji.

Računanje faktorijela:

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

Alternativna implementacija, često brža od prethodne ako Lisp sistem ima optimizaciju u vidu repne rekurzije:

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

Iterativna verzija u Common Lisp-u:

 (defun factorial (n)
   (loop for i from 1 to n
         for fac = 1 then (* fac i)
         finally (return fac)))

Naredna funkcija obrće listu. (Ugrađena funkcija reverse radi istu stvar.)

(defun -reverse (list)
  (let ((return-value '()))
    (dolist (e list) (push e return-value))
    return-value))

• The Common Lisp Object System, CLOS
• ObjectLisp^[5] ili Object Lisp, korišćen od strane Lisp Machines Incorporated i ranije verzije Macintosh Common Lisp-a
• LOOPS (Lisp Object-Oriented Programming System) i kasniji CommonLOOPS
• Flavors, nastao na MIT, i njegov naslednik New Flavors(developed by Symbolics).
• KEE korišćen kao objektni sistem nazvan UNITS i ugrađen u inference engine{{ Veitch|1988|p=108}} i truth maintenance system (ATMS).

https://common-lisp.net/