Лисп (програмски језик)
Лисп (историјски, ЛИСП) је фамилија програмских језика са дугом историјом. Лисп је други најстарији виши програмски језик који се и данас веома користи. Једино је Фортран старији (годину дана).[1][2] Данас постоји велики број дијалеката Лисп-а, а најпознатији међу њима су Common Lisp и Scheme.
| Лисп | |
|---|---|
 Лисп | |
| Оригинални назив | енгл. Lisp |
| Модел | функционална, процедурална, мета |
| Појавио се | 1958 |
| Аутор(и) | Џон Макарти,Стив Расел, Тимоти П. Харт, и Мајк Левин |
| Дијалекти | Arc, AutoLISP, Clojure, Common Lisp, Emacs Lisp, EuLisp, Franz Lisp, Hy, Interlisp, ISLISP, LeLisp, LFE, Maclisp, MDL, Newlisp, NIL, Picolisp, Portable Standard Lisp, Racket, RPL, Scheme, SKILL, Spice Lisp, T, Zetalisp |
| Утицаји | IPL |
| Утицао на | CLIPS, CLU, COWSEL, Dylan, Elixir, Falcon, Forth, Haskell, Io, Ioke, JavaScript, Julia, Logo, Lua, Mathematica, MDL, ML, Nim, Nu, OPS5, Перл, Python, R, Rebol, Ruby, Scala, Smalltalk, Tcl |
Чисти Лисп је пример функционалног програмског језика. У функционалном програмирању, функције се примењују на аргументе и вредности. Враћене вредности се користе као аргументи за друге функције. Функционално програмирање је супротно процедуралном програмирању, где се користе наредбе које мењају окружење програма на неки начин, као што је приписивање вредности променљивим. У функционалном програмирању, те промене окружења се минимизују коришћењем вредности које враћа позвана функција као директан улаз у другу функцију, без употребе приписивања наредби.
Име ЛИСП је настало од "LISt Processor". Повезане листе су један од главних типова података.
Историјат уреди
Лисп је пројектовао Џон Макарти 1958. године. Лисп је први пут имплементиран од стране Стива Расела на ИБМ 704 рачунару. Расел је прочитао Макартијев рад и закључио да израчунавање у Лиспу може да се имплементира на машинском језику. Резултат тога је интерпретатор који је могао да покреће Лисп програме, али и да рачуна вредности Лисп израза.
Први комплетан Лисп компајлер, написан у Лисп-у, имплементирали су Тим Харт и Мајк Левин 1962. године.
Током 1980-их и 1990-их радило се на уједињавању нових дијалеката Лисп-а. Тако је настао програмски језик Common Lisp. Први стандард за Common Lisp, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp.", objavio je ANSI 1994. године.
Едсгер Дајкстра је на додели Тјурингове награде 1972. године рекао: "Са неколико основних принципа свог заснивања, он (ЛИСП) је показао изузетну стабилност. Осим тога, ЛИСП је био носач значајног броја најсавременијих компјутерских апликација. ЛИСП је у шали описан као "најинтелигентнији начин да се злоупотреби рачунар". Мислим да је такав опис велики комплимент, јер преноси пун укус слободе: он је помогао велики број наших најталентованијих колега у размишљању о раније немогућим стварима."[3]
Синтакса и семантика уреди
Симболички изрази (С-изрази) уреди
Лисп је језик који се ослања на изразе. Када се израз евалуира, он враћа вредност, која се може искористити у другим изразима.
Свака вредност може бити било који тип података.
У Лисп-у се наводе два типа синтаксе: С-изрази (симболички изрази), који осликавају унутрашњу репрезентацију и кода и података, и M-изрази (мета изрази), који изражавају функције С-израза. Скоро сви Лисп језици данас користе С-изразе за код и податке.
Оно што је Лисп одмах одвојило од других породица језика, јесте употреба заграда. Синтакса која користи С-изразе је заслужна за лакше коришћење програмског језика Лисп. Међутим, синтакса Лисп-а није ограничена на традиционалну нотацију помоћу заграда. Може се проширити и укључити и друге нотације.
Ослањање на изразе даје велику флексибилност језику. Лисп функције су написане као листе, стога се оне могу обрађивати као било који други подаци. Ово омогућава лако писање програма који користе друге програме (метапрограмирање). Многи Лисп дијалекти користе ову одлику, користећи макро системе, што омогућава проширење језика готово без ограничења.
Листе уреди
Листа се записује тако што се између заграда наведу елементи листе, одвојени размацима. На пример, (1 2 foo) је листа чији елементи су три атома 1, 2 и foo; 1 и 2 јесу цели бројеви, док је фоо специјалан тип података у Лисп-у, симбол.
Празна листа () се такодје мозе представити као специјални атом nil. Ово је једини ентитет у Лисп-у
који је уједно и листа и атом.
Изрази се записују као листе, користећи префиксну нотацију. На пример, ако наведемо
(A B C D)
А представља име функције (име макроа, ламбда израз или име специјалног оператора), док су Б, C и D аргументи.
Листе могу бити угњеждене. На пример:
(A (B C) D (E (F G)))
Оператори уреди
Аритметички оператори се третирају на следећи начин:
(+ 1 2 3 4)
Овај израз има вредност 10. Еквивалентан израз у инфиксној нотацији јесте "1 + 2 + 3 + 4". Аритметички оператори у Лисп-у су н-арне функције, тако да могу имати било колико аргумената. Оператор инкрементирања у C-у "++" овде је имплементиран као:
(incf x)
што је еквивалентно са (сетq x (+ x 1)), које враћа нову вредност од x.
Специјални оператори, који се понекад називају и специјалним формама обезбеђују контролне структуре. На пример, специјални оператор иф има три аргумента. Ако први аргумент није нил, одређује се вредност другог аргумента, а ако јесте, онда се одређује вредност трећег аргумента. На пример,
(if nil
(list 1 2 "foo")
(list 3 4 "bar"))
биће (3 4 "bar").
Ламбда изрази и дефиниција функције уреди
lambda је један специјални оператор који се користи за везивање променљивих вредностима које су евалуиране унутар израза. Такође се користи за прављење функција. Аргументи оператора ламбда јесу листе аргумената, а вредност коју враћа је вредност последњег евалуираног израза. На пример, израз
(lambda (arg) (+ arg 1))
представља функцију која узима један аргумент, везује га за arg и враћа број за један већи од аргумента. Ламбда изрази се позивају на исти начин као и функције. На пример:
((lambda (arg) (+ arg 1)) 5)
враћа вредност 6.
Атоми уреди
У првобитном ЛИСП-у су постојале два основна типа података: атоми и листе. Листа је коначан низ елемената где је сваки елемент за себе листа или атом, а атом је или број или симбол, који има форму идентификатора. На пример,
(FOO (BAR 1) 2)
садржи три елемента: симбол ФОО, листу (БАР 1) и број 2. Суштинска разлика између атома и листи јесте та да су атоми непроменљиви и јединствени, док је свака листа посебан објекат која може да се мења независно од других листи.
Листе и елементи листе уреди
Лисп листа је једноструко повезана листа. Свака ћелија листе се назива cons(од CONStruct cell или CONStruct list) и састоји се од два показивача, који се називају car(Contents of Address part of Register) и cdr(Contents of Decrement part of Register). Они, редом, одговарају elementu и pokazivaču у повезаној листи.
Ако узмемо да нам дати cons буде глава повезане листе, онда његов car показивач показује на први елемент листе, а cdr показује на остатак листе. Из тог разлога car и cdr функције имају и назив prvi и ostatak када се говори о елементима који су део повезане листе.
Веома се често користе код рекурзивно написаних функција које у свом првом пролазу обрађују само један елемент, а затим се са цдр узима остатак листе који се рекурзивно прослеђује истој функцији да исти посао обави и за све друге елементе
Због тога што су cons и листе универзалне у Лисп системима, честа је заблуда да су они једине структуре података у Лисп-у. У ствари, постоје и друге структуре података, попут вектора (низова), хеш табели...
Cons може да се напише у dotted-pair нотацији као (a . b), где a представља car, а b представља cdr.
Функције за рад са листама уреди
Лисп има многе уграђене функције за приступ и контролу листи. Листа се може креирати директно помоћу функције list, која узима било који број аргумената и враћа листу тих аргумената.
(list 1 2 'a 3)
;Output: (1 2 a 3)
(list 1 '(2 3) 4)
;Output: (1 (2 3) 4)
Функција cons се може искористити за додавање на почетак листе.
(cons 1 '(2 3))
;Output: (1 2 3)
(cons '(1 2) '(3 4))
;Output: ((1 2) 3 4)
Функција reverse обрће листу.
(reverse '(a b c d))
;Output: (d c b a)
Функција length рачуна дужину листе.
(length ‘(a (b c) d))
;Output: 3
(length ‘(a b c d))
;Output: 4
Функција append спаја две или више листи.
(append '(1 2) '(3 4))
;Output: (1 2 3 4)
(append '(1 2 3) '() '(a) '(5 6))
;Output: (1 2 3 a 5 6)
Постоји још много функција овог типа, које проверавају да ли је одређен аргумент празна листа, да ли је тај аргумент уопште листа и сличне. ( нулл , листп…)
Дељене структуре уреди
Лисп листе, које су једноструко повезане, могу да поделе структуру међусобно. То јест, две листе могу да имају исти реп или крајњи низ cons ћелија. На пример, након извршења следећег Common Lisp кода
(setf foo (list 'a 'b 'c))
(setf bar (cons 'x (cdr foo)))
листе foo и bar су (a b c) и (x b c), редом. Међутим, реп (b c) је иста структура у обе листе. Није копија већ cons ћелије које показују на б и ц су на истој меморијској локацији.
Међутим, уколико се, у неком тренутку, замени б или ц у foo, замениће се и у bar, што је неочекивани резултат. Ово може бити извор грешака, па су функције које мењају своје аргументе означене као деструктивне, управо из овог разлога.
уреди
Лисп одређује вредност израза који корисник унесе. Симболи и листе одређују вредност неког другог израза, углавном једноставнијег. На пример, симбол одређује вредност променљиве коју именује; (+ 2 3) враћа 5. Како год, већина облика враћа вредност њих самих: ако се унесе 5 у Лисп-у, он враћа 5.
Сваки израз може бити обележен како би се спречила његова евалуација (ако је потребан за симболе и листе). То је улога специјалног оператора quote или скраћено' (једноструки наводник). На пример, ако се укуца foo вратиће се вредност одговарајуће променљиве (или грешка ако та променљива не постоји). Ако је потребно реферисати на неки литерални симбол, куца се (quote foo) или 'foo.
Самоевалуирајући облици и форме навођења су у Лисп-у еквиалентни са литералима. То омогућава модификацију (променљивих) литерала у програмском коду. На пример, ако фунција враћа неку форму навођења и код који позива функцију модификује форму, то може променити понашање функције у наредним итерацијама.
(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)
Простор имена уреди
Лисп је подељен око употребе динамичке и статичке (односно лексичке) употребе простора имена. Clojure, Common Lisp и Scheme подразумевано користе статичко дефинисање поља променљиве, док Newlisp, Picolisp и уграђени језици у Emacs-у и AutoCAD-у користе динамичко.
Списак структура програмског кода; макрои и компајлери уреди
Основна разлика између Лисп-а и осталих језика је у томе што је текстуална репрезентација програма прилично читљив опис саме унутрашње структуре података (повезаних листи, симбола, бројева, карактера, итд.) као што је у основи Лисп система.
Захваљујући томе, Лисп имплементира веома јак систем макроа. Као и у осталим макро језицима као што је C, макро враћа код који може бити компајлиран. За разлику од C-ових макроа, у Лисп-у су макрои функције и у њима је моћ Лисп-а.
Пошто код у Лисп-у има исту структуру као листе, макрои могу бити изражени помоћу било које функције за рад са листама. Укратко, све што може Лисп са структуром података, Лисп макрои могу са кодом.
У једноставној имплементацији Лисп-а, ова структура у виду листе је директно интерпретирана да покрене програм; функција је дословно део структуре листе која преведена од стране интерпретатора при извршавању. Већина Лисп система садржи и компајлер. Он преводи структуру листе на машински језик или бајткод за извршавање. Овај код може бити покренут једнако брзо као и у C-у, на пример.
Макрои нуде интересантне опције.
Неке имплементације Лисп-а имају механизам eval-when који омогућава коду да буде присутан за време компилације (кад затреба макроу) али није присутан у емитујућем модулу.[4]
Евалуација и read–eval–print петља уреди
Лисп језици су најчешће коришћени са интерактивном командном линијом, која се може комбиновати са IDE-ом. Лисп чита унете изразе, евалуира их и штампа резултат. Због овога, Лисп командна линија се назива "read–eval–print петља", односно REPL.
read функција прихвата текстуални С-израз као улаз и парсира га у унутрашњу структуру података.
На пример, ако се укуца текст (+ 1 2) у промпту, read га преводи у повезану листу са три елемента: симбол +, број 1 и број 2. Ова листа је такође валидан део Лисп кода и може се евалуирати.
Треба напоменути да се foo чита као појединачни симбол.
123 ће се прочитати као број сто двадесет три, а "123" ће се прочитати као стринг "123".
eval функција евалуира податке, враћа нула или више Лисп података као резултат. Евалуација не мора значити исто што и интерпретација; поједини Лисп системи компајлирају сваки израз у машински код који се може извршити директно од стране CPU. Свакако је једноставно објаснити евалуацију као интерпретирање: Да би се евалуирала листа чији car именује функцију,
eval прво евалуира сваки од аргумената који је прослеђен њеном cdr-у, потом примењује функцију на аргументе. У овом случају, функција је сабирање и примењујући је на аргументе листе (1 2) даје резултат 3. То је, заправо, резултат евалуације.
Симбол foo евалуира вредност симбола фоо. Податак као што је стринг "123" евалуира исти стринг. Листа (quote(1 2 3)) евалуира (1 2 3).
Посао функције print је да прикаже излаз кориснику. За једноставан резултат као што је 3 то је тривијално. Израз који евалуира део структуре листе би захтевао да print прође кроз листу и штампа је као С-израз.
За имплементацију Lisp REPL-а, неопходно је имплементирати наведене три функције и функцију "бесконачна петља". Наравно да имплементација функције eval није једноставна, посебно јер је потребно имплементирали све специјалне операторе као што су if или lambda.
Када је ово завршено, REPL није ништа друго до једна линија кода: (loop (print (eval (read)))).
Lisp REPL омогућава редиговање улаза, историју улаза, управљање грешкама као и интерфејс дибагера.
Лисп се углавном евалуира похлепно.
Контролне структуре уреди
Лисп је првобитно имао само неколико структура, али велики број је додаван током еволуције језика. (Лисп-ов првобитни условни оператор, cond, претходник је касније if-then-else структуре.
Поједине Лисп-ове контролне структуре су специјални оператори, еквиваленти синтаксним кључним речима других језика. Изрази који користе ове операторе имају исти изглед као позиви функција, разлика је једино у томе што аргументи не морају бити евалуирани или у итеративном случају могу бити евалуирани више од једанпут.
За разлику од осталих виших програмских језика, Лисп допушта програмеру да имплементира контролне структуре користећи језик. Неколико контролних струкутура је имплементирано као Лисп макрои, а неколико њих могу бити макро развијени од стране програмера који знају како то ради.
I Common Lisp и Scheme имају операторе за нелокалну контролу тока. Разлике у овим операторима уједно чине и разлике између ова два дијалекта.
Неретко, исти алгоритам у Лисп-у може бити исказан и императивним и функционалним стилом. Scheme преферира функционални стил користећи репну рекурзију. Како год, императивни стил је још увек могућ. Стил који преферирају Common Lisp програмери ближи је програмерима који користе структуиране језике као што је C, док је онај који преферирају Scheme програмери ближи чисто функционалним језицима као што је Haskell.
Лисп има широки спектар функција вишег реда које су у релацији са итарацијом у наредбама. У многим случајевима где би у другом језику била неопходна петља (као for у C-у) у Лисп-у ствар решава функција вишег реда.
Примери уреди
Ево примера Common Lisp кода.
Основни "Хелло Wорлд" програм:
(print "Hello world")
Лисп синтакса је подесна за рекурзију. Математички проблеми као што је набрајање рекурзивно дефинисаним скуповима једноставно се изражавају у овој нотацији.
Рачунање факторијела:
(defun factorial (n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
Алтернативна имплементација, често бржа од претходне ако Лисп систем има оптимизацију у виду репне рекурзије:
(defun factorial (n &optional (acc 1))
(if (= n 0) acc
(factorial (- n 1) (* acc n))))
Итеративна верзија у Common Lisp-у:
(defun factorial (n)
(loop for i from 1 to n
for fac = 1 then (* fac i)
finally (return fac)))
Наредна функција обрће листу. (Уграђена функција reverse ради исту ствар.)
(defun -reverse (list)
(let ((return-value '()))
(dolist (e list) (push e return-value))
return-value))
Објектни системи уреди
- The Common Lisp Object System, CLOS
- ObjectLisp[5] или Object Lisp, коришћен од стране Lisp Machines Incorporated и раније верзије Macintosh Common Lisp-а
- LOOPS (Lisp Object-Oriented Programming System) и каснији CommonLOOPS
- Flavors, nastao na MIT, i njegov naslednik New Flavors(developed by Symbolics).
- KEE коришћен као објектни систем назван UNITS и уграђен у inference engine{{ Veitch|1988|p=108}} и truth maintenance system (АТМС).
Спољашње везе уреди
Reference уреди
- ^ „SICP: Foreword”. Архивирано из оригинала 27. 07. 2001. г. Приступљено 19. 04. 2016. „Lisp is a survivor, having been in use for about a quarter of a century. Among the active programming languages only Fortran has had a longer life.”
- ^ „Conclusions”. Архивирано из оригинала 03. 04. 2014. г. Приступљено 19. 04. 2016.
- ^ Dijkstra, Edsger W. (1972), The Humble Programmer (EWD 340) (ACM Turing Award lecture).
- ^ Time of Evaluation - Common Lisp Extensions. Gnu.org. Retrieved on 2013-07-17.
- ^ Bobrow 1986, стр. 17.