Lisp

lisp
John McCarthy og Steve Russell
Generell informasjon
Paradigme Multiparadigme : funksjonell , prosessuell , refleksjon , metaprogrammering
Dukket opp i 1958
Designet av John McCarthy
type system flere
implementeringer flere
dialekter Common Lisp , Scheme , Emacs Lisp , Clojure , AutoLISP , Hy , Arc , Franz Lisp , Maclisp , Racket
påvirket av Informasjonsbehandlingsspråk
har påvirket Perl , Python , Javascript , Lua , Scala , Ruby , R , Elixir , Haskell , Forth , Julia , Smalltalk , CLOS , Dylan , Wolfram

Lisp (historisk LISP ) er en familie av multi - paradigme type dataprogrammeringsspråk med en lang historie og en særegen og nyttig homoikonisk syntaks basert på polsk notasjon .

Opprinnelig utviklet i 1959 av John McCarthy og hans samarbeidspartnere ved Massachusetts Institute of Technology , er Lisp det nest eldste programmeringsspråket på høyt nivå ; den dukket opp et år etter FORTRAN og et år før COBOL .

I likhet med COBOL og FORTRAN har Lisp endret seg mye siden starten, og det har vært et stort antall dialekter i historien. I dag er de mest brukte Lisp-dialektene Scheme (1975), Common Lisp (1984), Emacs Lisp (1985) og Clojure (2007).

Lisp ble opprinnelig laget som en praktisk matematisk notasjon for dataprogrammer, basert på Alonzo Churchs lambda-kalkulus . Det ble raskt favorittprogrammeringsspråket i forskning på kunstig intelligens (AI). Som forløper programmeringsspråk var Lisp banebrytende for mange ideer innen informatikk , inkludert tredatastrukturer , automatisk lagringsadministrasjon , dynamisk skriving og den selvstendige kompilatoren .

Akronymet LISP står for LIS t Processor . Koblede lister er en av de viktige datastrukturene i Lisp, og selve Lisp -kildekoden er bygd opp av lister. Som et resultat kan Lisp-programmer manipulere Lisp-kildekoden som om det var enkle data, noe som gir opphav til makrosystemer som lar programmerere lage domenespesifikke språk innebygd i Lisp.

Utskiftbarheten av kode og data gir også Lisp dens umiddelbart gjenkjennelige syntaks. All programkode skrives som S-uttrykk , eller lister i parentes. Et funksjonskall eller syntaksform skrives som en liste, med funksjonen eller operatørnavnet først, og argumentene etter; for eksempel kan en funksjon f som tar tre argumenter kalles ved å bruke (f x y z).

Historikk

Lisp ble oppfunnet av John McCarthy i 1958 mens han var ved Massachusetts Institute of Technology (MIT). McCarthy publiserte designen sin i 1960 i en Communications of the ACM- artikkel med tittelen "Recursive Functions of Symbolic Expressions and Their Machine Computation, Part I" [ 1 ] ("Part II" ble aldri publisert). Der viste han at med noen enkle operatorer og en notasjon for funksjoner, kan man bygge et Turing-komplett språk for behandling av algoritmer .

Allerede i 1955 eller 1956 var informasjonsbehandlingsspråket det første AI-språket, og hadde allerede inkludert mange av konseptene, som listebehandling og rekursjon , som kom til å bli brukt i Lisp.

McCarthys originale notasjon brukte " M-uttrykk " i hakeparenteser som ville bli oversatt til S-uttrykk . Som et eksempel er uttrykket M car[cons[A,B]]ekvivalent med uttrykket S (car (cons A B)). Når Lisp ble implementert, valgte programmerere raskt å bruke S-uttrykk, og M-uttrykk ble forlatt. M-uttrykk dukket opp igjen med de kortvarige forsøkene på Horace Eneas MLISP [ 2 ] og Vaughan Pratts CGOL .

Lisp ble først implementert av Steve Russell på en IBM 704 -datamaskin . Russell hadde lest McCarthys artikkel, og innså (til McCarthys overraskelse) at Lisps evalfunksjon kunne implementeres i maskinkode . Resultatet ble en fungerende Lisp- tolk som kunne brukes til å kjøre Lisp-programmer, eller mer korrekt, "evaluere Lisp-uttrykk".

To assembly- språkrutiner for IBM 704 ble de primitive operasjonene for å dekomponere lister: bil (innhold av adresseregister) og cdr (innhold av dekrementregister). Lisp-dialekter bruker fortsatt car og cdr (uttales /ˈkɑr/ og /ˈkʊdər/ ) for operasjoner som returnerer henholdsvis det første elementet og resten av listen.

Den første komplette Lisp-kompilatoren, skrevet i Lisp, ble implementert i 1962 av Tim Hart og Mike Levin ved MIT. [ 3 ] Denne kompilatoren introduserte Lisp-modellen for inkrementell kompilering, der kompilerte og tolkede funksjoner fritt kan blandes. Språket i Hart og Levin- memoene er mye nærmere moderne Lisp-stil enn den tidligere McCarthy-koden.

Slektsforskning og varianter

I løpet av sin femti år lange historie har Lisp produsert mange varianter av grunntemaet til et uttrykksspråk S. På den annen side kan hver gitt dialekt ha flere implementeringer, for eksempel er det mer enn et dusin implementeringer av Common Lisp .

Forskjeller mellom dialekter kan være svært synlige, for eksempel bruker Common Lisp og Scheme ulike nøkkelord for å definere funksjoner. Innenfor en dialekt som er standardisert, støtter imidlertid samsvarende implementeringer det samme basisspråket, men med forskjellige utvidelser og biblioteker.

Forholdet til kunstig intelligens

Fra starten var Lisp nært knyttet til forskningsmiljøet for kunstig intelligens , spesielt på PDP-10- systemer . [ 4 ] Det ble brukt som implementering av Micro Planner -programmeringsspråket som var grunnlaget for det berømte SHRDLU AI-systemet . På 1970-tallet, da AI-forskning skapte kommersielle etterkommere, ble ytelsen til eksisterende Lisp-systemer et økende problem.

Lisp var et vanskelig system å implementere med vanlig maskinvare og kompilatorteknikker på 1970-tallet. Søppelinnsamlingsrutiner , utviklet av daværende MIT-student Daniel Edwards, gjorde det praktisk å kjøre Lisp på generelle datasystemer. , men effektivitet var fortsatt en utgave. Dette førte til etableringen av Lisp-maskiner : dedikert maskinvare for å kjøre Lisp-programmer og miljøer. Fremskritt innen både maskinvare og kompilatorteknologi gjorde snart Lisp-maskiner foreldet, til skade for Lisp-markedet.

I løpet av 1980- og 1990-tallet ble det gjort mye arbeid for å forene de mange dialektene til Lisp til ett enkelt språk (spesielt InterLisp , Maclisp , ZetaLisp , MetaLisp og Franz Lisp ) . Det nye språket, Common Lisp , var i hovedsak en kompatibel undergruppe av dialektene det erstattet. I 1994 publiserte ANSI Common Lisp-standarden, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp". På den tiden var verdensmarkedet for Lisp mye mindre enn det er i dag. [ referanse nødvendig ]

Siden 2000

Etter å ha falt noe på 1990-tallet, opplevde Lisp en ny boom med fokus på åpne implementeringer av Common Lisp og utvikling av applikasjoner og nye bærbare biblioteker. Et eksempel på denne interessen var da den trykte versjonen av Peter Seibels Practical Common Lisp , en veiledning for nye programmerere publisert i 2004, [ 5 ] kort var på Amazon.com som den nest mest populære programmeringsboken. Boken er tilgjengelig på nett uten kostnad. [ 6 ]

Mange nye Lisp-programmerere ble inspirert av forfattere som Paul Graham og Eric S. Raymond som kjempet for et språk som andre anser som utdatert. Nye Lisp-programmerere beskriver ofte språket som en øyeåpnende opplevelse og hevder at det er betydelig mer produktivt enn andre språk. [ 7 ] Denne økningen i bevissthet kan kontrasteres med " vinteren med kunstig intelligens " og den korte veksten til Lisp på midten av 1990-tallet. [ 8 ]

I sin undersøkelse av Common Lisp-implementeringer lister Dan Weinreb opp elleve aktivt vedlikeholdte implementeringer. Scieneer Common Lisp er en ny kommersiell implementering som ga CMUCL med en første utgivelse i 2002.

Open source-fellesskapet har laget ny støtteinfrastruktur: Cliki er en Wiki som samler informasjon relatert til Common Lisp, Common Lisp-katalogen viser ressurser, #lisp er en populær IRC-kanal (støttet av en Bot skrevet i Lisp), lisppaste støtter distribusjonen og deling og kommentering av snutter, Planet Lisp samler innholdet i ulike Lisp-relaterte blogger, i LispForum diskuterer brukeren Lisp-emner, Lispjobs er en tjeneste for å annonsere tilbud som fungerer og det er en ny ukentlig nyhetstjeneste ( Weekly Lisp News ).

50 år med Lisp (1958-2008) har blitt feiret på LISP50@OOPSLA . Det er flere regelmessige lokale brukermøter (Boston, Vancouver, Hamburg ,...), Lisp-møter ( European Common Lisp Meeting , European Lisp Symposium ) og en internasjonal Lisp-konferanse .

Scheme-fellesskapet opprettholder aktivt mer enn tjue implementeringer. Flere betydelige nye implementeringer har blitt utviklet de siste årene (Chicken, Gauche, Ikarus, Larceny, Ypsilon). Scheme Revised 5 Report on the Algorithmic Language Scheme- standarden var allment akseptert i Scheme-fellesskapet. Scheme Requests for Implementation - prosessen har skapt mange nesten standard biblioteker og utvidelser til ordningen. Brukerfellesskapet for individuelle Scheme-implementeringer fortsetter å vokse. I 2003 ble det startet en ny språkstandardiseringsprosess som førte til ordningens R 6 RS-standard i 2007. Den akademiske bruken av ordningen for å undervise i informatikk ser ut til å ha gått noe ned. Noen universiteter bruker ikke lenger Scheme i sine innledende informatikkkurs.

Det er også noen nye Lisp-dialekter. Spesielt: Newlisp (et skriptspråk), Arc (utviklet av Paul Graham) og nylig Clojure (utviklet av Rich Hickey) og NU for programmering med Apples Cocoa.

Hoveddialekter

De to viktigste Lisp-dialektene som brukes til generell programmering i dag er Common Lisp og Scheme . Disse språkene representerer betydelig forskjellige designalternativer.

Common Lisp , som primært stammer fra MacLisp , Interlisp og Lisp Machine Lisp , er et utvidet supersett av tidligere Lisp-dialekter, med en stor språkstandard inkludert mange innebygde datatyper og syntaktiske former, samt et objektsystem. Opplegget er et mer minimalistisk design, med et mye mindre sett med standardfunksjoner, men med visse implementeringsfunksjoner (som tail call-optimalisering og full fortsettelse ) som ikke nødvendigvis finnes i Common Lisp. Common Lisp lånte også visse trekk fra Scheme som leksikalsk omfang og leksikalsk avslutning .

Scheme er en statisk scoped, ekte rekursiv haledialekt av Lisp-språket oppfunnet av Guy Lewis Steele Jr. og Gerald Jay Sussman . Den ble designet for å ha eksepsjonelt klar og enkel semantikk og få forskjellige måter å danne uttrykk på. Et bredt utvalg av programmeringsparadigmer finner praktiske uttrykk i Scheme, inkludert imperative, funksjonelle og meldingsoverføringsstiler. Ordningen fortsetter å utvikle seg med en rekke standarder (Revidert n rapport om det algoritmiske språkskjemaet) og en serie med forespørsler om implementering .

I tillegg brukes Lisp-dialekter som skriptspråk i en rekke applikasjoner, hvor de mest kjente er Emacs Lisp i Emacs -editoren , Visual Lisp i AutoCAD , Nyquist i Audacity .

Språkinnovasjoner

Det var i Lisp at mange informatikkideer ble født , inkludert tredatastrukturen , automatisk søppelinnsamling , dynamisk skriving , betingelser , funksjoner av høyere orden som kart og redusering , rekursjon , den selvstendige kompilatoren og REPL . [ 9 ]​ [ 10 ]

Lisp var det første homoikoniske programmeringsspråket : hele kildekoden til programmet er samtidig en språkdatastruktur ( nestede lister eller trær ). Som et resultat er metaprogrammering i Lisp relativt enkelt. Siden Lisp-kildekoden har en direkte samsvar med programmets abstrakte syntakstre , kan du lage Lisp-kode for å manipulere mer Lisp-kode, eller til og med lage den fra bunnen av, uten behov for omfattende parsing eller manipulering av binær maskinkode. Dette anses generelt som en av de viktigste fordelene med språk med hensyn til dets uttrykksevne, og gjør språk gunstig for metasirkulær evaluering .

Den allestedsnærværende strukturen IF THEN ELSE, nå innrømmet som et viktig element i ethvert programmeringsspråk, ble oppfunnet av McCarthy for bruk i Lisp, hvor den så sin første opptreden i en mer generell form (strukturen cond). Det ble arvet av ALGOL , som populariserte det.

Lisp påvirket Smalltalk dypt , og så ble Lisp på sin side påvirket av Smalltalk, og tok i bruk funksjonene til objektorientert programmering (klasser, forekomster, etc.) på slutten av 1970-tallet .

Lisp introduserte konseptet med søppelinnsamling , der systemet søker i haugen av dynamisk minne for å fjerne foreldede objekter uten eksplisitt inngripen fra programmereren. [ 11 ]

Stort sett på grunn av ressurskravene med hensyn til tidlig maskinvare (inkludert tidlige mikroprosessorer ), ble ikke Lisp like populær utenfor kunstig intelligens -samfunnet som FORTRAN og ALGOL -språkets etterkommer , språket . C. _ Nyere språk som Java og Python har innlemmet noen begrensede versjoner av noen av Lisps funksjoner, men de kan ikke nødvendigvis gi sammenhengen og synergien til de fullstendige konseptene som finnes i Lisp. På grunn av sin egnethet for dårlig definerte, komplekse og dynamiske applikasjoner, nyter Lisp for tiden noe av en gjenoppblomstring av populær interesse.

Lister

Det grunnleggende elementet i Lisp er listen , i begrepets bredeste forstand, siden både data og programmer er lister. Det er der navnet kommer fra, siden Lisp er et akronym for "ListProcessing".

Lister i LISP er avgrenset med parenteser. Herfra kommer spøken om betydningen av LISP: «LostInStupidParentheses» som selv om med godt humør er helt fiktiv.

Noen av Lisps innebygde funksjoner har kjente symboler (+ for summen, * for produktet), men andre er mer eksotiske, spesielt to som tjener nettopp til å manipulere lister, og bryte dem ned i deres komponenter. Navnene deres (" bil " og " cdr ") er litt merkelige, relikvier fra svunne tider og strukturen til andregenerasjons datamaskiner, "bil" returnerer hodet på en liste og "cdr" sin hale eller resten.

Lisp følger en filosofi om ikke-destruktiv behandling av parametere, slik at de fleste funksjoner returnerer en liste som er et resultat av å utføre en transformasjon på den de mottok, men uten å endre sistnevnte.

En av grunnene til at Lisp er spesielt godt egnet for AI er fordi kode og data behandles likt (som lister); dette gjør det spesielt enkelt å skrive programmer som kan skrive andre programmer avhengig av omstendighetene.

Lisp var et av de første programmeringsspråkene som inkluderte unntakshåndtering med catch and throw - primitiver .

Avledet fra Lisp er programmeringsspråket Logo . Uten å gå i detaljer kan det sies at Logo er Lisp uten parentes og med infiks aritmetiske operatorer.

Opprinnelsen til "bil" og "cdr"

De er operasjoner av instruksjonssettet til IBM 704

Eksempler

Hei verden

( format t "Hei, verden!" ) Arbeide med lister ************************************************** ****************** Funksjonsdefinisjon : _ _ ( defun tom ( l ) ( cond ( ( null l ) 1 ) ; hvis listen er tom returnerer 1 ( t 0 ))) ; ellers (full liste) returnerer 0 Funksjonsanrop : _ _ ( tom ' ( 1 3 4 )) ; Listen er ikke tom, den vil returnere 0 ( tom ' ()) ; Listen er tom, den vil returnere 1 ***************************************** *** ************************ ( defun last ( liste ) ( cond (( null ( cdr- liste )) ( char list )) ( t ( siste ( cdr- liste ))))) ( siste ' ( 1 2 3 4 5 6 7 )) ; returnerer den siste av listen: 7 ************************************************** ***************** ; Faktoriell(x) = 1 hvis x=0 grunntilfelle ; x*faktoriell(x-1) hvis x>0 rekursivt tilfelle ;Faktoriell funksjon laget med ikke-endelig rekursjon ( defun factorial ( n ) ( if ( = 0 n ) 1 ; base case ( * n ( factorial ( - n 1 )))))) ; rekursivt tilfelle ( faktoriell 4 ) ; dette vil returnere 24=4*3*2*1 ************************************************** *****************

Store verdier av Ackermann-funksjonen

;Foreslått av Nikolai Coica ( defun ackermann ( m n ) "The Ackermann Function" ( cond (( = m 0 ) ( + n 1 )) (( = m 1 ) ( + n 2 )) (( = m 2 ) ( + 3 ( * n 2 ))) (( = m 3 ) ( + 5 ( * 8 ( - ( expt 2 n ) 1 )))) ( t ( cond (( = n 0 ) ( ackermann ( - m 1 ) 1 )) ( t ( ackermann ( - m 1 ) ( ackermann m ( - n 1 ))))))))

Referanser

  1. ↑ John McCarthy. "Rekursive funksjoner av symbolske uttrykk og deres beregning med maskin, del I" . Hentet 2021-01-21 . 
  2. ↑ David Canfield-Smith. MLISP brukerhåndbok . Arkivert fra originalen 2006-09-24 . Hentet 13. oktober 2006 . 
  3. ↑ Tim Hart og Mike Levin. "AI Memo 39 - Den nye kompilatoren" . Hentet 13. oktober 2006 . 
  4. ↑ 36-biters ordstørrelsen til PDP-6 / PDP-10 ble påvirket av nytten av å ha to Lisp 18-bits pekere i et enkelt ord. Lum Johnson (18. oktober 1990). "Historien om TOPS eller livet i de raske AC-ene" . alt.folklore.datamaskiner . [email protected] . «PDP-6-prosjektet startet tidlig i 1963, som en 24-bits maskin. Den vokste til 36 biter for LISP, et designmål. » 
  5. ^ "Praktisk Common Lisp går i tredje utskrift" . Arkivert fra originalen 20. juni 2009 . Hentet 19. september 2009 . 
  6. ↑ Praktisk vanlig lisp
  7. ^ "Veien til Lisp-undersøkelsen" . Arkivert fra originalen 4. oktober 2006 . Hentet 13. oktober 2006 . 
  8. ^ "Trender for fremtiden" . Arkivert fra originalen 3. juni 2013 . Hentet 19. september 2009 . 
  9. ^ Chisnall, David (12. januar 2011). Innflytelsesrike programmeringsspråk, del 4: Lisp . Hentet 22. mai 2020 . 
  10. ↑ "Nerdens hevn" . www.paulgraham.com . Hentet 22. mai 2020 . 
  11. ↑ Lieberman Henry; HewittCarl (1. juni 1983). "En søppelsamler i sanntid basert på gjenstanders levetid" . Kommunikasjon til ACM . doi : 10.1145/358141.358147 . Hentet 22. mai 2020 . 

Se også

Eksterne lenker

Søknader i Lisp

Blant de mest vellykkede søknadene skrevet i Lisp kan vi nevne:

Lisp-kompilatorer