Lisp

Lisp
Logo.
Dato for første version 1958
Paradigmer funktionel , bydende nødvendigt
Forfatter John McCarthy
Indtastning dynamisk
Dialekter Almindelig Lisp , Emacs Lisp , Ordning , Clojure
Påvirket af Information Processing Language
Operativ system Tværplatform

Lisp er den ældste familie af både tvingende og funktionelle programmeringssprog . Oprindeligt udviklet som en praktisk model til at repræsentere programmer (i modsætning til den teoretiske forestilling om Turing's maskine ) blev det i 1970'erne og 80'erne det valgte sprog for forskning inden for kunstig intelligens . Lisp-sprog bruges i dag på mange områder, fra webprogrammering til finansiering og i nogle computeruddannelseskurser.

Udtrykket Lisp blev opfundet af den engelske "  listebehandling  ". Alle dialekter af Lisp deler de samme enkle linkede manipulationsoperatører. Lisp adskilles yderligere ved en simpel syntaks i præfiksnotation , dens dynamiske datatypning , understøttelse af funktionel programmering , automatisk hukommelsesstyring og evnen til at manipulere kildekoden som en datastruktur .

Lisp-sprog genkendes straks ved deres udseende. Den kilde programmet er skrevet med samme syntaks som lister - den parentes syntaks i S-udtryk . Hver underekspression af et program (eller datastruktur) afgrænses af parenteser. Dette forenkler i høj grad parsing af Lisp-programmer og gør metaprogrammering enkel - oprettelse af programmer, der opretter andre programmer eller ændrer det aktuelle program.

Hvis vi undtager maskinsprog og samlingssprog (eller mere almindeligt "  samling  "), er Lisp det næstældste sprog (lige efter Fortran ) blandt de sprog, der er blevet meget udbredt. Lisp har udviklet sig meget siden begyndelsen af 1960'erne og har født mange dialekter.

Historie

Lisp-sproget blev opfundet af John McCarthy i 1958, mens han var ved Massachusetts Institute of Technology (MIT). Han offentliggjorde en artikel med titlen "Rekursive funktioner ved symbolske udtryk og deres beregning ved maskine, del I" i tidsskriftet CACM i 1960  ; del II blev aldrig offentliggjort.

Den første tolk kørte på en IBM 704- computer, og to instruktioner fra denne maskine blev Lisps to primitive operationer til nedbrydning af lister:

Funktionen med at oprette en liste ud fra et første element og en liste bemærkes cons.

I sin artikel introducerer John McCarthy to syntakser: S-udtryk (symbolske udtryk, undertiden kaldet "  sexp ") og M-udtryk (meta-udtryk tillader homoicitet at udtrykke funktioner, der håndterer S-udtryk, med andre ord for at fremhæve implementere refleksionen ). M-udtryk har aldrig været meget populære, og de fleste Lisps bruger i disse dage S-udtryk til både programmer og data. Det er syntaksen for S-udtryk, der får Lisp til at kritisere sin overflod af parenteser, men det er også en af ​​grundene til sprogets kraft og fleksibilitet.

På grund af sin ekspressivitet og fleksibilitet var Lisp meget succesrig i det kunstige intelligenssamfund (jf. Bidrag).

I 1970'erne blev der oprettet computere, der har specialiseret sig i at køre Lisp-programmer: Lisp-maskiner .

I løbet af 1980'erne og 1990'erne blev der gjort en stor indsats for at forene de mange dialekter af Lisp, der var opstået. Resultatet var standardiseringen af Common Lisp , hvis ANSI- standard blev offentliggjort i 1994 under referencen "ANSI X3.226-1994 Information Technology Programming Language Common Lisp  ". Den ISO offentliggjort på hans side i 1997 standarden ISLISP  (i) ISO / IEC 13816: 1997 (E) , revideret i 2007 af standarden ISO / IEC 13816: 2007 (E) . På det tidspunkt blomstrede Lisp meget mindre end i sin storhedstid.

Selvom formørket af sprog tæt på maskinen (C, C ++) eller mere strukturerede og typede sprog ( Haskell ), forbliver Lisp et relativt brugt sprog, især som et sprog indlejret i applikationer, hvor det fungerer som en sprog udvidelse . Lisps mest kendte indlejrede brugssager er teksteditoren Emacs og sprog AutoLISP  (in) i AutoCAD . Bemærk også, at Lisp kommer i fjerde position med hensyn til kodelinjer, der bruges til at implementere de 8.600 kildepakker, der er tilgængelige i Debian- operativsystemet offentliggjort iJuni 2005. De øverste otte sprog er fordelt som følger: C (57%), C ++ (16,8%), Shell (9%), Lisp (3%), Perl (2,8%), Python (1,8%), Java (1,6%), Fortran (1,2%). IJuli 2013Lisp anbringes i 15 th position af TIOBE indeks . I juli 2020 rangeret 34 th .

Syntaks

Lister er afgrænset af parenteser, og deres elementer er adskilt af mellemrum: (1 2 " foo ") . Et Lisp-program er et syntaks-træ sammensat med lister. Denne brug af parenteser giver anledning til hån ved at bruge akronymet LISP: "  Masser af irriterende og fjollede parenteser  " eller "  Masser af modige og dumme parenteser  " usmageligt og dumt ") eller" Dumt parentesiseret computersprog "eller" Smagløst sprog mættet med parenteser ".

Lisp er et udtryksorienteret sprog: det skelner ikke mellem "udtryk" og "instruktioner", ligesom mange sprog (f.eks. Pascal ); alt er udtryk og returnerer en værdi eller et sæt værdier.

De fleste Lisp-udtryk er funktionsapplikationer. Hvad andre sprog skriver

f(a,b,c)

Lisp skriver det

(f a b c)

Så et beløb skrives ikke ned

1+2+3+4

eller

somme(1,2,3,4)

Men

(+ 1 2 3 4)

Den samme præfiksnotation (kendt som polsk notation ) bruges til "specielle figurer" og "makroer": det første element på listen bestemmer i disse tilfælde, hvordan efterfølgende emner skal håndteres. Et udtryk kan være en funktionsapp, en speciel form eller en makroapp afhængig af arten af ​​det første element.

Syntaks i EBNF-notation

Lisp-sproget har en meget enkel og elegant syntaks, der bruger et minimum af begreber. Denne begrebsøkonomi får Gregory Chaitin til at kvalificere denne syntaks som "en juvel af matematisk pragt og streng intellektuel skønhed" .

Omvendt tillader det ikke detektering af fejl.

Det meste af Lisp-sproget er kun defineret af tre EBNF- regler  :

list -> '(' expression* ')' expression -> atom | list atom -> number | name | string | operator

Disse regler kan oversættes som følger på fransk:

  • et Lisp-program er en liste over udtryk:
  • et udtryk kan være et atom eller en liste ( rekursion );
  • et atom er enten: et tal, et navn, en tegnstreng, en operator.

Eksempler

Følgende programmer er ikke typiske for rigtige Lisp-programmer. De er typiske for den præsentation, vi laver af Lisp i computerundervisning. Eksemplerne er givet i Common Lisp- syntaks .

Faktoriet er en stor klassiker:

(defun factorial (n) "Calcule la factorielle de l'entier n." (if (<= n 1) 1 (* n (factorial (- n 1)))))

Vi kan også skrive mere effektivt (se terminalrekursion ):

(defun factorial (n &optional (acc 1)) "Calcule la factorielle de l'entier n." (if (<= n 1) acc (factorial (- n 1) (* acc n))))

Et andet typisk eksempel er denne funktion, som vender en liste (Lisp har en indbygget omvendt funktion til dette formål):

(defun reverse (l &optional (acc '())) "Renverse la liste l." (if (null l) acc (reverse (cdr l) (cons (car l) acc))))

Bidrag

I modsætning til digital programmering, der hidtil er udviklet, har Lisp, der fungerer med symboler snarere end tal, skabt en anden programmeringsstil, der gør kunstig intelligens mulig .

Derfor fx pseudo-naturlige dialoger (jf. Eliza , Turing test ).

Desuden har dens funktioner og programmer den samme form som dets data ( homoiconicity-egenskab ).

Vi kan derfor i Lisp passere gennem spejlet . Så,

  • vi kan simulere en robot, som ved modtagelse af en mission (liste over kommandoer, der skal udføres med en vis frihed) ved først at ræsonnere på denne liste og dens miljø beordrer disse kommandoer og derefter udfører dem i den rækkefølge, som han vedtog; ja, ( eval kommando) vil behandle billedteksten af kommandoen , hidtil statiske data, som et udtryk, der skal evalueres;
  • i reverse engineering kan vi starte fra sporet af en ukendt funktion for at forsøge at finde denne funktion; ved at kombinere forskellige teknikker (første forskelle, sekunder ... og lignende kvoter) tillader det derefter
    • at foreslå identifikationer og karakterisere deres sandsynlighed
    • ved hjælp af en generatorfunktion ved hjælp af ( definer ) -funktionen, der forbinder et funktionsnavn og en definition, genererer Lisp-koden, der indeholder hver identifikation, for at kunne teste den mere fint;
  • vi kan endda give Lisp princippet om en Lisp-tolk.

En ejendommelighed ved Lisp-sproget, som i lang tid kun forblev et fortolket sprog , er, at i modsætning til andre fortolkede sprog fra 1960'erne og 1970'erne var dets udførelse som - eller undertiden endda hurtigere - end for kompilerede sprog . Denne specificitet kommer fra dens syntaks, hvilket gør, at stedet for hver type objekt (funktion, operatør, data) er forudsigeligt og ikke kræver en foreløbig analyse af en kildekodesekvens, før kodesekvensen udføres.

Udvidelse: Lisp og genstande

Under indflydelse af Simula blev forskellige objektsystemer bygget fra Lisp, herunder:

  • Smagsstoffer , designet hos MIT
  • Den fælles Lisp Object System ( CLOS ), en efterkommer af Flavours

CLOS tilbyder flere arv, flere valg og et kraftfuldt system til kombination af metoder. Common Lisp (hvoraf CLOS er en del) var det første standardiserede objektorienterede sprog.

Citater

”LISP har et lille antal kraftfulde elementære begreber, og alt andet er bygget oven på det, hvilket er den måde, matematikere arbejder på; sådan ser matematiske teorier ud. Disse teorier, de gode teorier, består i at definere nogle nye nøglekoncepter, og derfra begynder fyrværkeriet: de afslører nye veje, de åbner døren til radikalt nye verdener. LISP er også sådan; det er tættere på matematik end de fleste programmeringssprog. I det mindste hvis du fjerner de nyttige dele, der blev tilføjet, tilføjelserne, der gjorde LISP til et praktisk værktøj . Hvad der er tilbage, hvis du gør dette, er den oprindelige LISP, det konceptuelle hjerte af LISP, et hjerte, der er en perle af matematisk skønhed og streng intellektuel skønhed. "

-  Gregory Chaitin , Meta Maths: The Quest of Omega , 2006, Atlantic, s. 46

I dag vil nogle sige, at skemaet er afledet af, at Lisp opnår den skønhed, der er beskrevet af Chaitin  ; og det er sikkert, at Common Lisp , den lige efterkommer af de store cuvéer fra de tidligere dialekter af LISP (Maclisp, Interlisp, Zetalisp) læner sig mere mod den kæmpe værktøjskasse , på trods af at den har holdt sin konceptuelle kerne intakt.

G. Chaitin brugte denne idealiserede Lisp til sin forskning: Elegante LISP-programmer .

Det mest kraftfulde programmeringssprog er Lisp. Hvis du ikke kender Lisp (eller dens variant, Scheme), ved du ikke, hvad det betyder for et programmeringssprog at være stærk og elegant. Når du først har lært Lisp, vil du se, hvad der mangler på de fleste andre sprog.
I modsætning til de fleste sprog i dag, som er fokuseret på at definere specialiserede datatyper, giver Lisp et par datatyper, som er generelle. I stedet for at definere bestemte typer bygger du strukturer ud fra disse typer. I stedet for at tilbyde en måde at definere en liste af denne type og en liste over den type, har Lisp således en type lister, der kan indeholde enhver form for data.

-  Richard Stallman , hvordan jeg laver min computer

”Det mest magtfulde programmeringssprog er Lisp. Hvis du ikke kender Lisp (eller dens variant, Scheme), ved du ikke, hvad et kraftfuldt og elegant programmeringssprog er. Efter at have lært Lisp, vil du se, hvad der mangler på de fleste andre sprog.
I modsætning til de fleste sprog i dag, der fokuserer på at definere specialiserede datatyper, tilbyder Lisp få datatyper, men de er generiske. I stedet for at definere bestemte typer bygger du strukturer ud af dem. Så i stedet for at tilbyde en metode til at definere en liste-af-denne type eller en liste-af-den type, har Lisp en listetype, der kan indeholde enhver form for data. "

-  Hvordan jeg laver min computer

Slægtsforskning og varianter

  • Lisp (den originale version af John McCarthy, da han var på MIT )
  • MacLisp (relateret til MACSYMA-projektet på MIT - og ikke relateret til Apple Macintosh ), direkte efterkommer af Lisp
  • ZetaLisp , efterfølger til MACLisp, der kører på Lisp-maskiner
  • InterLisp  (en) , født BBN Lisp, som blev brugt til at udvikle de første grafiske brugergrænseflader
  • VLISP udviklet ved University of Paris VIII - Vincennes
  • Lisp  (en) , udviklet hos INRIA , og derefter markedsført af Eligis og Ilog
  • EuLisp  (en) , en "europæisk Lisp"
  • Emacs Lisp , forenklet version, der bruges til at programmere Emacs teksteditor
  • Fælles Lisp , efterkommer af den mest berømte Lisp
  • ISLISP  (en) , ISO- standard for ISLISP-sproget, der kan betragtes som en delmængde af Common Lisp , standard 13816: 1997 (E), revideret i 2007 af ISO / IEC 13816: 2007 (E).
  • AutoLISP, en Lisp, der bruges i AutoCAD til programmering
  • Ordning , en ren Lisp
  • Nyquist, en Lisp plejede at arbejde med lyde
  • xLispStat , en Lisp, der bruges til statistiske analyser af data
  • XLisp , en delmængde af Lisp-sproget udviklet af David Michael Betz
  • QLisp , en udvidelse af Xlisp4.3 med hundreder af billedanalyserutiner
  • Arc , meget raffineret derivat, oprettet af Paul Graham
  • Clojure , kører på en virtuel Java-maskine og transpilerer forskellige sprog.
  • OpenLisp  (in) , fuld implementering af standard ISLISP  (in) med mange kompatible udvidelser Common Lisp .

Noter og referencer

  1. (in) DA Kent (12). “  Nogle historik over funktionelle programmeringssprog  ” (pdf) i TFP12 . 
  2. [1] .
  3. Beskrivelse af kurset "  Struktur og fortolkning af computerprogrammer  " , MIT
  4. John McCarthy, rekursive funktioner i symbolske udtryk og deres beregning efter maskine, del I , kommunikation fra ACM, bind. 3 Udgave 4, april 1960 DOI : 10.1145 / 367177.367199
  5. UPGRADE (European Journal for the Informatics Professional), juni 2005, s. 14
  6. Formelt er dette en forudgående notation, men den særlige anvendelse af parenteser i Lisp-sproget indebærer, at det virkelig er polsk notation, idet selve tolkens rolle er at reducere parentesudtryk til lineære udtryk, der kan fortolkes fra venstre mod højre, operatørerne først.
  7. Gregory Chaitin Chance og kompleksitet i matematik Flammarion 2009.
  8. Elegante LISP-programmer
  9. (in) "  Hvordan laver jeg min computer  " (adgang til 5. februar 2017 )
  10. Eligis
  11. ISO / IEC 13816: 1997 (E)
  12. ISO / IEC 13816: 2007 (E)

Se også

Relaterede artikler

  • Lambda-beregning  : matematisk sprog, som Lisp, ligesom andre funktionelle computersprog, er inspireret af.
  • Fælles Lisp  : direkte efterkommer af McCarthy's Lisp; udtrykket Lisp bruges i dag lige så meget til at henvise til den oprindelige Lisp som til Common Lisp.
  • Ordning  : en anden efterkommer af Lisp, mere fokuseret på funktionel programmering end makroprogrammering.
  • S-udtryk

eksterne links