Lisp

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Lisp, förkortning av "LISt Processing", är ett funktionellt programspråk skapat av

John McCarthy 1958. Det är det näst äldsta programspråket fortfarande i allmänt bruk, bara Fortran är äldre. Liksom Fortran har det ändrats mycket sedan den första versionen. På grund av de många varianter och dialekter av Lisp som skapats sedan dess, är det kanske riktigare att säga att Lisp inte är ett språk, utan en grupp av besläktade språk. Kända dialekter är Common Lisp, Emacs Lisp, AutoLISP och Scheme.

Innehåll

Historia

McCarthy publicerade en beskrivning av sitt språk i en artikel i Communications of the ACM 1960. Han visade där att man utgående från ett fåtal enkla operationer och en notation för funktioner, kunde bygga upp ett helt programspråk. Den första implementationen av Lisp gjordes för datorn IBM 704, och två av denna maskins maskininstruktioner gav namn åt två grundläggande operationer i Lisp för att manipulera listor: car (Contents of Address Register) och cdr (Contents of Decrement Register). De flesta dialekter av Lisp använder fortfarande dessa namn för de operationer som ger första elementet i en lista respektive resten av elementen i en lista.

Under 1980-talet och 1990-talet gjordes flera försök att förena de många dialekterna och skapa en enhetlig standard av språket. Common Lisp var huvudsakligen ett sammanförande av många varianter, och 1994 publicerade ANSI standarden "ANSI X3.226-1994 Information Technology Programming Language Common Lisp."

Syntax

Syntaxen för Lisp karakteriseras av en extrem enkelhet med en minimal uppsättning språkliga konstruktioner. Till skillnad från de flesta andra programspråk skiljer man inte mellan uttryck och instruktioner. All kod och alla data skrivs som speciella uttryck ("S-exprs") och alla värden i språket är antingen ett primitivt värde eller en lista av värden eller andra listor. Skriven Lisp-kod består därför av ett stort antal parenteser, som inleder och avslutar varje lista. Namnet Lisp har till och med skämtsamt tolkats som "Lots of Irritating Superfluous Parentheses".

Språkets teoretiska grundvalar och den flytande gränsen mellan Lispkod och de data som koden hanterar, gjorde språket populärt inom artificiell intelligens (AI).

Avigsidorna med språket var att en stor mängd mellanresultat genererades vid tolkningen av koden, vilket tog upp mycket minne och krävde speciell skräpsamling ("garbage collection") för att rensas bort. Detta var ett stort problem för dåtidens datorer där minne var en bristvara. För att råda bot på detta, har flera försök gjorts att skapa speciell hårdvara, Lisp-maskiner, för att köra Lispprogram.

Programexempel

Hello, world!

; LISP - definierar en funktion som skriver "Hello World"
(defun hello_world ()
  (print (list 'Hello 'World)))

(Common LISP), skriver "Hello World!"

(format t "Hello world!~%")

(Scheme), skriver "Hello, world!"

(display "Hello, world!")
(newline)

Rekursion

Rekursion är en mycket vanlig programmeringsstil i Lisp, där föredras framför iteration. Det naiva schemeprogrammet nedan räknar längden av en lista med hjälp av rekursion: om listan är tom är längden 0, om den inte är tom är listans längd = 1 + längden av listan man får om man tar bort den första länken:

(define (length lst)
  (if (pair? lst)
      (+ 1 (length (cdr lst)))
      0))

Ett problem är att programmet kräver ett returstackdjup som är proportionellt mot listans längd; detta kan spränga stacken om listan är alltför lång. Om programmet skrivs om med hjälp av svansrekursion krävs ingen djup stack:

(define (length lst)
  (define (length-aux lst count)
    (if (pair? lst)
        (length-aux (cdr lst) (+ count 1))
        count))
  (length-aux lst 0))

Se även

Externa länkar

Personliga verktyg