Lisp (langage de programmation)

Lisp (historiquement LISP ) est une famille de langages de programmation avec une longue histoire et une notation de préfixe distinctive entièrement Entre parenthèses . ^[3] Spécifié à l’origine en 1958, Lisp est le deuxième langage de programmation de haut niveau le plus ancien encore couramment utilisé. Seul Fortran est plus ancien, d’un an. ^{[4] [5]} Lisp a changé depuis ses débuts et de nombreux dialectes ont existé au cours de son histoire. Aujourd’hui, les dialectes Lisp à usage général les plus connus sont Racket , Common Lisp , Scheme et Clojure . ^{[citation nécessaire ]}

Zézayer

Paradigme	Multi-paradigme : fonctionnel , procédural , réflexif , méta
Conçu par	Jean McCarthy
Développeur	Steve Russell , Timothy P. Hart et Mike Levin
Première apparition	1958 ; il y a 64 ans (1958)
Discipline de frappe	Dynamique , fort
Dialectes
Arc AutoLISP Clojure Lisp commun Emacs LispComment EuLisp Franz Lisp Hy Interlisp ILISISP Le Lisp LFE Maclisp LMD nouveauLISP NÉANT Picolisp Lisp standard portable Raquette RPL Schème COMPÉTENCE Lips d’épices J Zétalisp
Influencé par
IPL
Influencé
CLIPS CLU Vache Dylan Élixir Quatrième Haskell Io Ioké Javascript Julia [1] Logo Lua ML Nim Nu OPS5 perle POP-2 / 11 Python R Rébol Rubis Scala Rapide Petit discours TCL Langue Wolfram [2]

Lisp a été créé à l’origine comme une notation mathématique pratique pour les programmes informatiques , influencée par (mais non dérivée à l’origine de) ^[6] la notation du calcul lambda d’ Alonzo Church . Il est rapidement devenu le langage de programmation privilégié pour la recherche sur l’intelligence artificielle (IA). ^[7] En tant que l’un des premiers langages de programmation, Lisp a été le pionnier de nombreuses idées en informatique , y compris les structures de données arborescentes , la gestion automatique du stockage , le typage dynamique , les conditions , les fonctions d’ordre supérieur ,recursion , le compilateur auto-hébergé , ^[8] et la boucle read–eval–print . ^[9]

Le nom LISP dérive de “LISt Processor”. ^[10] Les listes liées sont l’une des principales structures de données de Lisp , et le code source de Lisp est composé de listes. Ainsi, les programmes Lisp peuvent manipuler le code source comme une structure de données, donnant naissance aux systèmes de macros qui permettent aux programmeurs de créer une nouvelle syntaxe ou de nouveaux langages spécifiques à un domaine intégrés dans Lisp.

L’interchangeabilité du code et des données donne à Lisp sa syntaxe immédiatement reconnaissable. Tout le code du programme est écrit sous forme d’expressions s ou de listes Entre parenthèses. Un appel de fonction ou une forme syntaxique est écrit sous forme de liste avec le nom de la fonction ou de l’opérateur en premier, et les arguments suivants ; par exemple, une fonction fqui prend trois arguments serait appelée .(f arg1 arg2 arg3)

Histoire

John McCarthy (en haut) et Steve Russell

John McCarthy a développé Lisp en 1958 alors qu’il était au Massachusetts Institute of Technology (MIT). McCarthy a publié sa conception dans un article dans Communications of the ACM en 1960, intitulé “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. ^[11] Il a montré qu’avec quelques opérateurs simples et une notation pour les fonctions anonymes empruntée à Church, on peut construire un langage Turing-complet pour les algorithmes.

Le langage de traitement de l’information a été le premier langage d’ IA , à partir de 1955 ou 1956, et incluait déjà de nombreux concepts, tels que le traitement de liste et la récursivité, qui ont été utilisés dans Lisp.

La notation originale de McCarthy utilisait des ” expressions M ” Entre parenthèses qui seraient traduites en expressions S. Par exemple, la M-expression car[cons[A,B]]est équivalente à la S-expression . Une fois Lisp implémenté, les programmeurs ont rapidement choisi d’utiliser les expressions S, et les expressions M ont été abandonnées. Les expressions M ont refait surface avec des tentatives de courte durée de MLisp ^[12] par Horace Enea et CGOL par Vaughan Pratt .(car (cons A B))

Lisp a d’abord été implémenté par Steve Russell sur un ordinateur IBM 704 utilisant des cartes perforées . ^[13] Russell avait lu l’article de McCarthy et s’était rendu compte (à la surprise de McCarthy) que la fonction Lisp eval pouvait être implémentée en code machine .

Selon McCarthy : ^[14]

Steve Russell a dit, regardez, pourquoi ne programmerais-je pas cet eval … et je lui ai dit, ho, ho, vous confondez la théorie avec la pratique, cet eval est destiné à la lecture, pas à l’informatique. Mais il est allé de l’avant et l’a fait. C’est-à-dire qu’il a compilé l’ eval de mon article en code machine IBM 704 , en corrigeant les bogues , puis en a fait la publicité en tant qu’interpréteur Lisp, ce qui était certainement le cas. Donc, à ce moment-là, Lisp avait essentiellement la forme qu’il a aujourd’hui …

Le résultat était un interpréteur Lisp fonctionnel qui pouvait être utilisé pour exécuter des programmes Lisp, ou plus exactement, “évaluer des expressions Lisp”.

Deux macros de langage d’assemblage pour l’ IBM 704 sont devenues les opérations primitives pour décomposer les listes : car( Contenu de la partie Adresse du numéro de registre) et cdr( Contenu de la partie de décrémentation du numéro de registre), ^[15] où “registre” fait référence aux registres du l’ unité centrale de traitement (CPU) de l’ordinateur. Les dialectes Lisp utilisent encore caret cdr( / k ɑːr / et / ˈ k ʊ d ər /) pour les opérations qui renvoient respectivement le premier élément d’une liste et le reste de la liste.

Le premier compilateur Lisp complet, écrit en Lisp, a été implémenté en 1962 par Tim Hart et Mike Levin au MIT, et pourrait être compilé en faisant simplement en sorte qu’un interpréteur LISP existant interprète le code du compilateur, produisant une sortie de code machine pouvant être exécutée à 40 minutes. -multiplier l’amélioration de la vitesse par rapport à celle de l’interprète. ^[16] Ce compilateur a introduit le modèle Lisp de compilation incrémentielle , dans lequel les fonctions compilées et interprétées peuvent se mélanger librement. Le langage utilisé dans le mémo de Hart et Levin est beaucoup plus proche du style Lisp moderne que le code antérieur de McCarthy.

Les routines de collecte des ordures ont été développées par l’étudiant diplômé du MIT ^{[ citation nécessaire ]} Daniel Edwards , avant 1962. ^[17]

Au cours des années 1980 et 1990, un grand effort a été fait pour unifier le travail sur les nouveaux dialectes Lisp (principalement les successeurs de Maclisp tels que ZetaLisp et NIL (New Implementation of Lisp) en un seul langage. Le nouveau langage, Common Lisp , était quelque peu compatible avec les dialectes qu’il a remplacés (le livre Common Lisp the Language note la compatibilité de diverses constructions).En 1994, l’ ANSI a publié la norme Common Lisp, “ANSI X3.226-1994 Information Technology Programming Language Common Lisp”.

Chronologie

Chronologie des dialectes Lisp

• v
• t
• e

1955	1960	1965	1970	1975	1980	1985	1990	1995	2000	2005	2010	2015	2020
LISP 1, 1.5, LISP 2 (abandonné)
Maclisp
Interlisp
LMD
Lisp Machine Lisp
Schème	R5RS	R6RS	R7RS petit
NÉANT
ZIL (Langage d’implémentation de Zork)
Franz Lisp
Lisp commun
Le Lisp
Programme MIT
J
Chez Scheme
Emacs LispComment
AutoLISP
Picolisp
EuLisp
ILISISP
OpenLisp
Régime PLT	Raquette
Ruse GNU
LISP visuel
Clojure
Arc
LFE
Hy

Connexion à l’intelligence artificielle

Depuis sa création, Lisp a été étroitement lié à la communauté de recherche sur l’ intelligence artificielle , en particulier sur les systèmes PDP-10 ^[18] . Lisp a été utilisé comme implémentation du langage Micro Planner , qui a été utilisé dans le célèbre système AI SHRDLU . Dans les années 1970, alors que la recherche sur l’IA engendrait des ramifications commerciales, les performances des systèmes Lisp existants sont devenues un problème croissant. ^{[ citation nécessaire ]}

Généalogie et variantes

Au cours de ses soixante ans d’histoire, Lisp a engendré de nombreuses variations sur le thème central d’un langage d’expression S. De plus, chaque dialecte donné peut avoir plusieurs implémentations – par exemple, il existe plus d’une douzaine d’implémentations de Common Lisp .

Les différences entre les dialectes peuvent être assez visibles – par exemple, Common Lisp utilise le mot-clé defunpour nommer une fonction, mais Scheme utilise define. ^[19] Dans un dialecte qui est standardisé, cependant, les implémentations conformes prennent en charge le même langage de base, mais avec des extensions et des bibliothèques différentes.

Dialectes historiquement significatifs Une machine Lisp au MIT Museum 4.3 BSD de l’ Université du Wisconsin , affichant la page de manuel de Franz Lisp

• LISP 1 ^[20] – Première implémentation.
• LISP 1.5 ^[21] – Première version largement distribuée, développée par McCarthy et d’autres au MIT. Ainsi nommé parce qu’il contenait plusieurs améliorations par rapport à l’interpréteur “LISP 1” d’origine, mais n’était pas une restructuration majeure comme le serait le LISP 2 prévu.
• Stanford LISP 1.6 ^[22] – Il s’agissait d’un successeur de LISP 1.5 développé au Stanford AI Lab et largement distribué aux systèmes PDP-10 exécutant le système d’exploitation TOPS-10 . Il a été rendu obsolète par Maclisp et InterLisp.
• MACLISP ^[23] – développé pour le Projet MAC du MIT , MACLISP est un descendant direct de LISP 1.5. Il fonctionnait sur les systèmes PDP-10 et Multics . MACLISP s’appellera plus tard Maclisp, et est souvent appelé MacLisp. Le “MAC” dans MACLISP n’est lié ni au Macintosh d’Apple ni à McCarthy .
• Interlisp ^[24] – développé chez BBN Technologies pour les systèmes PDP-10 exécutant le système d’exploitation TENEX , adopté plus tard comme Lisp “West Coast” pour les machines Xerox Lisp sous le nom d’ InterLisp-D . Une petite version appelée “InterLISP 65” a été publiée pour la gamme d’ordinateurs de la famille Atari 8 bits basée sur 6502 . Pendant un certain temps, Maclisp et InterLisp étaient de sérieux concurrents.
• Franz Lisp – à l’origine un projet de l’Université de Californie à Berkeley ; développé plus tard par Franz Inc. Le nom est une déformation humoristique du nom ” Franz Liszt “, et ne fait pas référence à Allegro Common Lisp , le dialecte de Common Lisp vendu par Franz Inc., ces dernières années.
• XLISP , sur lequel AutoLISP était basé.
• Le Lisp standard et le Lisp standard portable ont été largement utilisés et portés, en particulier avec le système d’algèbre informatique REDUCE.
• ZetaLisp , également appelé Lisp Machine Lisp – utilisé sur les machines Lisp , descendant direct de Maclisp. ZetaLisp a eu une grande influence sur Common Lisp.
• LeLisp est un dialecte français Lisp. L’un des premiers constructeurs d’interfaces (appelé SOS Interface ^[25] ) a été écrit en LeLisp.
• Régime (1975). ^[26]
• Common Lisp (1984), tel que décrit par Common Lisp the Language – une consolidation de plusieurs tentatives divergentes (ZetaLisp, Spice Lisp , NIL et S-1 Lisp ) pour créer des dialectes successeurs ^[27] à Maclisp, avec des influences substantielles du Scheme dialecte aussi. Cette version de Common Lisp était disponible pour une large gamme de plates-formes et a été acceptée par beaucoup comme une norme de facto ^[28] jusqu’à la publication de l’ANSI Common Lisp (ANSI X3.226-1994). Parmi les sous-dialectes les plus répandus de Common Lisp figurent Steel Bank Common Lisp(SBCL), CMU Common Lisp (CMU-CL), Clozure OpenMCL (à ne pas confondre avec Clojure !), GNU CLisp et les versions ultérieures de Franz Lisp ; tous adhèrent à la dernière norme ANSI CL (voir ci-dessous).
• Dylan était dans sa première version un mélange de Scheme avec le Common Lisp Object System.
• EuLisp – tentative de développement d’un nouveau Lisp efficace et nettoyé.
• ILISP – tentative de développement d’un nouveau Lisp efficace et nettoyé. Normalisé en tant qu’ISO/CEI 13816:1997 ^[29] et ultérieurement révisé en tant qu’ISO/CEI 13816:2007 : ^[30] Technologies de l’information – Langages de programmation, leurs environnements et interfaces logicielles système – Langage de programmation ILISISP .
• Schéma IEEE – Norme IEEE, 1178–1990 (R1995).
• ANSI Common Lisp – une norme American National Standards Institute (ANSI) pour Common Lisp, créée par le sous-comité X3J13 , agréée ^[31] pour commencer avec Common Lisp: The Language comme document de base et pour travailler à travers un processus de consensus public pour trouver des solutions à problèmes partagés de portabilité des programmes et de compatibilité des implémentations Common Lisp. Bien qu’officiellement une norme ANSI, la mise en œuvre, la vente, l’utilisation et l’influence de l’ANSI Common Lisp ont été et continuent d’être observées dans le monde entier.
• ACL2 ou “A Computational Logic for Applicative Common Lisp”, une variante applicative (sans effet secondaire) de Common LISP. ACL2 est à la fois un langage de programmation qui peut modéliser des systèmes informatiques et un outil pour aider à prouver les propriétés de ces modèles.
• Clojure , un dialecte récent de Lisp qui se compile sur la machine virtuelle Java et met particulièrement l’ accent sur la concurrence .
• Game Oriented Assembly Lisp (ou GOAL) est un langage de programmation de jeux vidéo développé par Andy Gavin et l’ équipe Jak et Daxter de Naughty Dog . Il a été écrit en utilisant Allegro Common Lisp et utilisé dans le développement de toute la série de jeux Jak et Daxter .
• Chialisp, un dialecte de haut niveau compilant jusqu’à CLVM, l’environnement de programmation en chaîne dans la blockchain de Chia

2000 à aujourd’hui

Après avoir quelque peu décliné dans les années 1990, Lisp a connu un regain d’intérêt après 2000. La plupart des nouvelles activités se sont concentrées sur les implémentations de Common Lisp , Scheme , Emacs Lisp , Clojure et Racket , et incluent le développement de nouvelles bibliothèques et applications portables.

De nombreux nouveaux programmeurs Lisp ont été inspirés par des écrivains tels que Paul Graham et Eric S. Raymond pour poursuivre un langage que d’autres considéraient comme désuet. Les programmeurs New Lisp décrivent souvent le langage comme une expérience révélatrice et prétendent être nettement plus productifs que dans d’autres langages. ^[32] Cette augmentation de la notoriété peut être mise en contraste avec « l’ hiver de l’IA » et le bref gain de Lisp au milieu des années 1990. ^[33]

En 2010 ^[update], il y avait onze implémentations de Common Lisp activement maintenues. ^[34] Scieneer Common Lisp est une nouvelle implémentation commerciale dérivée de CMUCL avec une première version en 2002.

La communauté open source a créé une nouvelle infrastructure de support : CLiki est un wiki qui collecte des informations relatives à Common Lisp, le répertoire Common Lisp répertorie les ressources, #lisp est un canal IRC populaire et permet le partage et le commentaire d’extraits de code (avec le support de lisppaste , un bot IRC écrit en Lisp), Planet Lisp collecte le contenu de divers blogs liés à Lisp, sur LispForum , les utilisateurs discutent de sujets Lisp, Lispjobs est un service d’annonce d’offres d’emploi et il existe un service d’actualités hebdomadaire, Weekly Lisp News . Common-lisp.netest un site d’hébergement de projets open source Common Lisp. Quicklisp est un gestionnaire de bibliothèque pour Common Lisp.

Cinquante ans de Lisp (1958–2008) ont été célébrés à LISP50@OOPSLA. ^[35] Il y a régulièrement des réunions d’utilisateurs locaux à Boston, Vancouver et Hambourg. D’autres événements incluent la réunion européenne Common Lisp, le symposium européen sur le Lisp et une conférence internationale sur le Lisp.

La communauté Scheme maintient activement plus de vingt implémentations . Plusieurs nouvelles implémentations importantes (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) ont été développées dans les années 2000 (décennie). La norme Revised ⁵ Report on the Algorithmic Language Scheme ^[36] de Scheme a été largement acceptée dans la communauté Scheme. Le processus Scheme Requests for Implementation a créé de nombreuses bibliothèques et extensions quasi standard pour Scheme. Les communautés d’utilisateurs des implémentations individuelles de Scheme continuent de croître. Un nouveau processus de normalisation linguistique a été lancé en 2003 et a conduit à la R ⁶Norme RS Scheme en 2007. L’utilisation académique de Scheme pour l’enseignement de l’informatique semble avoir quelque peu diminué. Certaines universités n’utilisent plus Scheme dans leurs cours d’introduction à l’informatique; ^{[37] [38]} Le MIT utilise maintenant Python au lieu de Scheme pour son programme d’informatique de premier cycle et son cours en ligne ouvert massif MITx. ^{[39] [40]}

Il existe plusieurs nouveaux dialectes de Lisp : Arc , Hy , Nu , Liskell et LFE (Lisp Flavored Erlang). L’analyseur de Julia est implémenté en Femtolisp, un dialecte de Scheme (Julia s’inspire de Scheme, qui à son tour est un dialecte Lisp).

En octobre 2019, Paul Graham a publié une spécification pour Bel , “un nouveau dialecte de Lisp”.

Principaux dialectes

Common Lisp et Scheme représentent deux courants majeurs du développement de Lisp. Ces langages incarnent des choix de conception sensiblement différents.

Common Lisp est le successeur de Maclisp . Les principales influences étaient Lisp Machine Lisp , Maclisp , NIL , S-1 Lisp , Spice Lisp et Scheme . ^[41] Il possède de nombreuses fonctionnalités de Lisp Machine Lisp (un grand dialecte Lisp utilisé pour programmer Lisp Machines ), mais a été conçu pour être efficacement implémentable sur n’importe quel ordinateur personnel ou poste de travail. Common Lisp est un langage de programmation à usage général et possède donc un grand standard de langage comprenant de nombreux types de données, fonctions, macros et autres éléments de langage intégrés, ainsi qu’un système d’objets ( Common Lisp Object System ). Common Lisp a également emprunté certaines fonctionnalités de Scheme telles queportée lexicale et fermetures lexicales . Des implémentations Common Lisp sont disponibles pour cibler différentes plates-formes telles que LLVM , ^[42] la machine virtuelle Java , ^[43] x86-64, PowerPC, Alpha, ARM, Motorola 68000 et MIPS, ^[44] et des systèmes d’exploitation tels que Windows , macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD et Heroku. ^[45]

Scheme est un dialecte à portée statique et correctement récursif du langage de programmation Lisp inventé par Guy L. Steele, Jr. et Gerald Jay Sussman . Il a été conçu pour avoir une sémantique exceptionnellement claire et simple et peu de façons différentes de former des expressions. Conçu environ une décennie plus tôt que Common Lisp, Scheme est un design plus minimaliste. Il a un ensemble beaucoup plus petit de fonctionnalités standard mais avec certaines fonctionnalités de mise en œuvre (telles que l’optimisation des appels de queue et les continuations complètes) non spécifié dans Common Lisp. Une grande variété de paradigmes de programmation, y compris les styles impératifs, fonctionnels et de transmission de messages, trouvent une expression pratique dans Scheme. Scheme continue d’évoluer avec une série de normes (Revised ⁿ Report on the Algorithmic Language Scheme) et une série de Scheme Requests for Implementation .

Clojure est un dialecte récent de Lisp qui cible principalement la machine virtuelle Java , et le Common Language Runtime (CLR), la VM Python , la VM Ruby YARV , et la compilation vers JavaScript . Il est conçu pour être un langage pragmatique à usage général. Clojure tire des influences considérables de Haskell et met un accent très fort sur l’immuabilité. ^[46] Clojure fournit un accès aux frameworks et bibliothèques Java, avec des indications de type facultatives et une inférence de type , afin que les appels à Java puissent éviter la réflexion et permettre des opérations primitives rapides. Clojure n’est pas conçu pour être rétrocompatible avec d’autres dialectes Lisp. ^[47]

De plus, les dialectes Lisp sont utilisés comme langages de script dans de nombreuses applications, les plus connus étant Emacs Lisp dans l’ éditeur Emacs , AutoLISP et plus tard Visual Lisp dans AutoCAD , Nyquist dans Audacity et Scheme dans LilyPond . La petite taille potentielle d’un interpréteur Scheme utile le rend particulièrement populaire pour les scripts intégrés. Les exemples incluent SIOD et TinyScheme , qui ont tous deux été intégrés avec succès dans le processeur d’image GIMP sous le nom générique “Script-fu”. ^[48]LIBREP, un interpréteur Lisp de John Harper basé à l’origine sur le langage Emacs Lisp , a été intégré dans le gestionnaire de fenêtres Sawfish . ^[49]

Dialectes standardisés

Lisp a des dialectes officiellement normalisés : R6RS Scheme , R7RS Scheme , IEEE Scheme , ^[50] ANSI Common Lisp et ISO ISLISP .

Innovations linguistiques

Lisp a été le premier langage où la structure du code de programme est représentée fidèlement et directement dans une structure de données standard – une qualité bien plus tard appelée ” homoiconicité “. Ainsi, les fonctions Lisp peuvent être manipulées, modifiées ou même créées dans un programme Lisp sans manipulations de niveau inférieur. Ceci est généralement considéré comme l’un des principaux avantages du langage en ce qui concerne sa puissance expressive, et rend le langage adapté aux macros syntaxiques et à l’évaluation métacirculaire .

Un conditionnel utilisant une syntaxe if-then-else a été inventé par McCarthy dans un contexte Fortran. Il a proposé son inclusion dans ALGOL , mais cela n’a pas été intégré à la spécification Algol 58 . Pour Lisp, McCarthy a utilisé la cond -structure plus générale . ^[51] Algol 60 a repris if-then-else et l’a popularisé.

Lisp a profondément influencé Alan Kay , le chef de l’équipe de recherche qui a développé Smalltalk au Xerox PARC ; et à son tour Lisp a été influencé par Smalltalk , les dialectes ultérieurs adoptant des fonctionnalités de programmation orientées objet (classes d’héritage, encapsulation d’instances, transmission de messages, etc.) dans les années 1970. Le système d’objet Flavors a introduit le concept d’ héritage multiple et le mixin . Le système d’objets Common Lisp fournit un héritage multiple, des méthodes multiples avec une répartition multiple et des fonctions génériques de première classe , ce qui donne une forme flexible et puissante de répartition dynamique .. Il a servi de modèle pour de nombreux systèmes d’objets Lisp ultérieurs (y compris Scheme ), qui sont souvent implémentés via un protocole métaobjet , une conception métacirculaire réflexive dans laquelle le système objet est défini en lui-même : Lisp n’était que le deuxième langage après Smalltalk (et est encore l’un des rares langages) à posséder un tel système de métaobjets. De nombreuses années plus tard, Alan Kay a suggéré qu’en raison de la confluence de ces fonctionnalités, seuls Smalltalk et Lisp pouvaient être considérés comme des systèmes de programmation orientés objet correctement conçus. ^[52]

Lisp a introduit le concept de ramasse-miettes automatique , dans lequel le système parcourt le tas à la recherche de mémoire inutilisée. Les progrès des algorithmes modernes et sophistiqués de récupération de place, tels que la récupération de place générationnelle, ont été stimulés par son utilisation dans Lisp. ^[53]

Edsger W. Dijkstra dans sa conférence du prix Turing de 1972 a déclaré:

“Avec quelques principes très basiques à sa base, il [LISP] a montré une stabilité remarquable. En outre, LISP a été le support d’un nombre considérable de nos applications informatiques les plus sophistiquées. LISP a été décrit en plaisantant comme ” la manière la plus intelligente d’abuser d’un ordinateur”. Je pense que cette description est un grand compliment car elle transmet toute la saveur de la libération : elle a aidé un certain nombre de nos semblables les plus doués à penser à des pensées auparavant impossibles.” ^[54]

En grande partie à cause de ses besoins en ressources en ce qui concerne le matériel informatique ancien (y compris les premiers microprocesseurs), Lisp n’est pas devenu aussi populaire en dehors de la communauté de l’ IA que Fortran et le langage C descendant d’ ALGOL . En raison de son adéquation aux applications complexes et dynamiques, Lisp connaît un certain regain d’intérêt populaire dans les années 2010. ^[55]

Syntaxe et sémantique

Note : Les exemples de cet article sont écrits en Common Lisp (bien que la plupart soient également valides en Scheme ).

Expressions symboliques (expressions S)

Lisp est un langage orienté expression . Contrairement à la plupart des autres langages, aucune distinction n’est faite entre les “expressions” et les “instructions” ; ^{[ douteux – discuter ]} tout le code et les données sont écrits sous forme d’expressions. Lorsqu’une expression est évaluée , elle produit une valeur (en Common Lisp, éventuellement plusieurs valeurs), qui peut ensuite être intégrée dans d’autres expressions. Chaque valeur peut être n’importe quel type de données.

L’article de McCarthy de 1958 a introduit deux types de syntaxe : les expressions symboliques ( S-expressions , sexps ), qui reflètent la représentation interne du code et des données ; et les méta-expressions ( M-expressions ), qui expriment les fonctions des S-expressions. Les expressions M n’ont jamais été appréciées, et presque tous les Lisps utilisent aujourd’hui des expressions S pour manipuler à la fois le code et les données.

L’utilisation de parenthèses est la différence la plus évidente entre Lisp et les autres familles de langages de programmation. En conséquence, les étudiants ont longtemps donné des surnoms Lisp tels que Lost In Stupid Parentheses , ou Lots of Irritating Superfluous Parentheses . ^[56] Cependant, la syntaxe de l’expression S est également responsable d’une grande partie de la puissance de Lisp : la syntaxe est simple et cohérente, ce qui facilite la manipulation par ordinateur. Cependant, la syntaxe de Lisp ne se limite pas à la notation traditionnelle des parenthèses. Il peut être étendu pour inclure des notations alternatives. Par exemple, XMLisp est une extension Common Lisp qui utilise le protocole métaobjet pour intégrer des expressions S avec le langage de balisage extensible ( XML ).

Le recours aux expressions donne au langage une grande flexibilité. Comme les fonctions Lisp sont écrites sous forme de listes, elles peuvent être traitées exactement comme des données. Cela permet d’écrire facilement des programmes qui manipulent d’autres programmes ( métaprogrammation ). De nombreux dialectes Lisp exploitent cette fonctionnalité en utilisant des systèmes de macros, ce qui permet une extension du langage presque sans limite.

Listes

Une liste Lisp est écrite avec ses éléments séparés par des espaces et entourés de parenthèses. Par exemple, est une liste dont les éléments sont les trois atomes , , et . Ces valeurs sont implicitement typées : ce sont respectivement deux entiers et un type de données spécifique à Lisp appelé “symbole”, et n’ont pas à être déclarées comme telles.(1 2 foo) 12foo

La liste vide ()est également représentée par l’atome spécial nil. C’est la seule entité en Lisp qui soit à la fois un atome et une liste.

Les expressions sont écrites sous forme de listes, en utilisant la notation préfixée . Le premier élément de la liste est le nom d’une fonction, le nom d’une macro, une expression lambda ou le nom d’un “opérateur spécial” (voir ci-dessous). Le reste de la liste sont les arguments. Par exemple, la fonction listrenvoie ses arguments sous forme de liste, donc l’expression

( liste 1 2 ( citation foo ))

évalue à la liste . Le “quote” avant le dans l’exemple précédent est un “opérateur spécial” qui renvoie son argument sans l’évaluer. Toutes les expressions sans guillemets sont évaluées de manière récursive avant l’évaluation de l’expression englobante. Par example,(1 2 foo)foo

( liste 1 2 ( liste 3 4 ))

évalue à la liste . Notez que le troisième argument est une liste ; les listes peuvent être imbriquées.(1 2 (3 4))

Les opérateurs

Les opérateurs arithmétiques sont traités de la même manière. L’expression

( + 1 2 3 4 )

est évalué à 10. L’équivalent sous la notation infixe serait ” “.1 + 2 + 3 + 4

Lisp n’a aucune notion d’opérateurs tels qu’implémentés dans les langages dérivés d’Algol. Les opérateurs arithmétiques en Lisp sont des fonctions variadiques (ou n-ary ), capables de prendre n’importe quel nombre d’arguments. Un opérateur d’incrémentation ‘++’ de style C est parfois implémenté sous le nom incfdonnant la syntaxe

( incf x )

équivalent à (setq x (+ x 1)), renvoyant la nouvelle valeur de x.

Les “opérateurs spéciaux” (parfois appelés “formes spéciales”) fournissent la structure de contrôle de Lisp. Par exemple, l’opérateur spécial ifprend trois arguments. Si le premier argument est non nul, il est évalué au second argument ; sinon, il évalue au troisième argument. Ainsi, l’expression

( si nul ( liste 1 2 “foo” ) ( liste 3 4 “bar” ))

évalue à . Bien sûr, cela serait plus utile si une expression non triviale avait été substituée à la place de .(3 4 “bar”)nil

Lisp fournit également des opérateurs logiques et , ou et non . Les opérateurs et et ou effectuent une évaluation de court-circuit et renverront respectivement leur premier argument nul et non nul.

( ou ( et “zéro” nul “jamais” ) “James” ‘task ‘time )

évaluera à “James”.

Expressions lambda et définition de fonction

Un autre opérateur spécial, lambda, est utilisé pour lier des variables à des valeurs qui sont ensuite évaluées dans une expression. Cet opérateur est également utilisé pour créer des fonctions : les arguments à lambdasont une liste d’arguments et l’expression ou les expressions auxquelles la fonction évalue (la valeur renvoyée est la valeur de la dernière expression évaluée). L’expression

( lambda ( arg ) ( + arg 1 ))

évalue une fonction qui, lorsqu’elle est appliquée, prend un argument, le lie arget renvoie le nombre un supérieur à cet argument. Les expressions lambda ne sont pas traitées différemment des fonctions nommées ; ils sont invoqués de la même manière. Par conséquent, l’expression

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

évalue à 6. Ici, on fait une application de fonction : on exécute la fonction anonyme en lui passant la valeur 5.

Les fonctions nommées sont créées en stockant une expression lambda dans un symbole à l’aide de la macro defun.

( defun foo ( a b c d ) ( + a b c d ))

(defun f (a) b…)définit une nouvelle fonction nommée fdans l’environnement global. Il est conceptuellement similaire à l’expression :

( setf ( fdefinition ‘f ) #’ ( lambda ( a ) ( block f b… )))

où setfest une macro utilisée pour définir la valeur du premier argument d’un nouvel objet fonction. est une définition de fonction globale pour la fonction nommée . est une abréviation d’ opérateur spécial, renvoyant un objet fonction.fdefinition ‘ffdefinitionf#’function

Atomes

Dans le LISP original, il y avait deux types de données fondamentaux : les atomes et les listes. Une liste était une séquence ordonnée finie d’éléments, où chaque élément est soit un atome, soit une liste, et un atome était un nombre ou un symbole. Un symbole était essentiellement un élément nommé unique, écrit sous la forme d’une chaîne alphanumérique dans le code source et utilisé soit comme nom de variable, soit comme élément de données dans le traitement symbolique . Par exemple, la liste contient trois éléments : le symbole , la liste et le chiffre 2.(FOO (BAR 1) 2)FOO(BAR 1)

La différence essentielle entre les atomes et les listes était que les atomes étaient immuables et uniques. Deux atomes apparaissant à des endroits différents dans le code source mais écrits exactement de la même manière représentaient le même objet, ^{[ citation nécessaire ]} alors que chaque liste était un objet distinct qui pouvait être modifié indépendamment des autres listes et pouvait être distingué des autres listes par opérateurs de comparaison.

Au fur et à mesure que davantage de types de données ont été introduits dans les dialectes Lisp ultérieurs et que les styles de programmation ont évolué, le concept d’atome a perdu de son importance. ^{[ citation nécessaire ]} De nombreux dialectes conservaient encore l’ atome de prédicat pour la compatibilité héritée , ^{[ citation nécessaire ]} le définissant comme vrai pour tout objet qui n’est pas un contre.

Conséquences et listes

Diagramme de boîte et pointeur pour la liste (42 69 613)

Une liste Lisp est implémentée sous forme de liste chaînée . ^[57] Chaque cellule de cette liste est appelée un contre (dans Scheme, une paire ) et est composée de deux pointeurs , appelés la voiture et cdr . Ceux-ci sont respectivement équivalents aux champs dataet discutés dans la liste liée de l’article .next

Parmi les nombreuses structures de données qui peuvent être construites à partir de cellules cons, l’une des plus élémentaires s’appelle une liste appropriée . Une liste propre est soit le symbole spécial nil(liste vide), soit un symbole dans lequel le carpoint pointe vers une donnée (qui peut être une autre structure contre, telle qu’une liste) et le cdrpoint vers une autre liste propre.

Si un cons donné est considéré comme la tête d’une liste chaînée, alors sa voiture pointe vers le premier élément de la liste et son cdr pointe vers le reste de la liste. Pour cette raison, les fonctions caret cdrsont également appelées firstet restlorsqu’elles font référence à des cons qui font partie d’une liste chaînée (plutôt que, disons, d’un arbre).

Ainsi, une liste Lisp n’est pas un objet atomique, comme le serait une instance d’une classe conteneur en C++ ou Java. Une liste n’est rien de plus qu’un agrégat de conséquences liées. Une variable qui fait référence à une liste donnée est simplement un pointeur vers le premier cons de la liste. Le parcours d’une liste peut être effectué en parcourant la liste ; c’est-à-dire prendre des cdr successifs pour visiter chaque contre de la liste ; ou en utilisant l’une des nombreuses fonctions d’ordre supérieur pour mapper une fonction sur une liste.

Parce que les cons et les listes sont si universels dans les systèmes Lisp, c’est une idée fausse commune qu’ils sont les seules structures de données de Lisp. En fait, tous les Lisps, sauf les plus simplistes, ont d’autres structures de données, telles que des vecteurs ( tableaux ), des tables de hachage , des structures, etc.

Les expressions S représentent des listes

Les expressions S Entre parenthèses représentent des structures de liste chaînée. Il existe plusieurs manières de représenter la même liste sous la forme d’une S-expression. Un contre peut être écrit en notation pointée comme , où est la voiture et le cdr. Une liste appropriée plus longue pourrait être écrite en notation pointée. Ceci est conventionnellement abrégé comme dans la notation de liste . Une liste impropre ^[58] peut être écrite dans une combinaison des deux – comme pour la liste des trois conses dont le dernier cdr est (c’est-à-dire la liste sous une forme entièrement spécifiée).(a . b)ab(a . (b . (c . (d . nil))))(a b c d)(a b c . d)d(a . (b . (c . d)))

Procédures de traitement des listes

Lisp fournit de nombreuses procédures intégrées pour accéder aux listes et les contrôler. Les listes peuvent être créées directement avec la listprocédure, qui prend un nombre quelconque d’arguments et renvoie la liste de ces arguments.

( liste 1 2 ‘a 3 ) ;Sortie : (1 2 a 3) ( liste 1 ‘ ( 2 3 ) 4 ) ;Sortie : (1 (2 3) 4)

En raison de la manière dont les listes sont construites à partir de paires cons , la consprocédure peut être utilisée pour ajouter un élément au début d’une liste. Notez que la consprocédure est asymétrique dans la façon dont elle gère les arguments de liste, en raison de la façon dont les listes sont construites.

( contre 1 ‘ ( 2 3 )) ;Sortie : (1 2 3) ( contre ‘ ( 1 2 ) ‘ ( 3 4 )) ;Sortie : ((1 2) 3 4)

La appendprocédure ajoute deux listes (ou plus) l’une à l’autre. Parce que les listes Lisp sont des listes liées, l’ajout de deux listes a une complexité temporelle asymptotique O ( n ) {displaystyle O(n)}

( ajouter ‘ ( 1 2 ) ‘ ( 3 4 )) ;Sortie : (1 2 3 4) ( ajouter ‘ ( 1 2 3 ) ‘ () ‘ ( a ) ‘ ( 5 6 )) ;Sortie : (1 2 3 a 5 6) Structure partagée

Les listes Lisp, étant de simples listes chaînées, peuvent partager une structure entre elles. C’est-à-dire que deux listes peuvent avoir la même queue , ou séquence finale de conses. Par exemple, après l’exécution du code Common Lisp suivant :

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

les listes fooet barsont et respectivement. Cependant, la queue a la même structure dans les deux listes. Ce n’est pas une copie; les cellules contre pointant vers et sont dans les mêmes emplacements de mémoire pour les deux listes.(a b c)(x b c)(b c)bc

Le partage de la structure plutôt que la copie peut améliorer considérablement les performances. Cependant, cette technique peut interagir de manière indésirable avec les fonctions qui modifient les listes qui leur sont transmises en tant qu’arguments. La modification d’une liste, par exemple en remplaçant le cpar un goose, affectera l’autre :

( setf ( troisième foo ) ‘oie )

Cela se transforme fooen , mais aussi en – un résultat peut-être inattendu. Cela peut être une source de bogues, et les fonctions qui modifient leurs arguments sont documentées comme destructrices pour cette raison.(a b goose)bar(x b goose)

Les aficionados de la programmation fonctionnelle évitent les fonctions destructrices. Dans le dialecte Scheme, qui privilégie le style fonctionnel, les noms des fonctions destructrices sont marqués d’un point d’exclamation d’avertissement, ou “bang” – comme set-car!(lire set car bang ), qui remplace la voiture d’un contre. Dans le dialecte Common Lisp, les fonctions destructrices sont monnaie courante ; l’équivalent de set-car!est nommé rplacapour “remplacer la voiture”. Cette fonction est cependant rarement vue, car Common Lisp inclut une fonction spéciale, setf, pour faciliter la définition et l’utilisation des fonctions destructrices. Un style fréquent dans Common Lisp est d’écrire du code de manière fonctionnelle (sans appels destructeurs) lors du prototypage, puis d’ajouter des appels destructeurs comme optimisation là où il est sûr de le faire.

Formulaires d’auto-évaluation et devis

Lisp évalue les expressions saisies par l’utilisateur. Les symboles et les listes s’évaluent à une autre expression (généralement plus simple) – par exemple, un symbole s’évalue à la valeur de la variable qu’il nomme; évalue à . Cependant, la plupart des autres formes s’évaluent d’elles-mêmes : si elles entrent dans Lisp, elles renvoient .(+ 2 3)555

Toute expression peut également être marquée pour empêcher son évaluation (comme cela est nécessaire pour les symboles et les listes). C’est le rôle de l’ quoteopérateur spécial, ou son abréviation ‘(un guillemet). Par exemple, généralement si vous entrez le symbole foo, il renvoie la valeur de la variable correspondante (ou une erreur, s’il n’y a pas une telle variable). Pour faire référence au symbole littéral, entrez ou, généralement, .(quote foo)’foo

Common Lisp et Scheme prennent également en charge l’ opérateur backquote (appelé quasiquote dans Scheme), entré avec le `caractère ( accent grave ). C’est presque la même chose que le guillemet simple, sauf qu’il permet d’évaluer les expressions et d’interpoler leurs valeurs dans une liste entre guillemets avec les opérateurs d’épissure comma , unquote et comma-at ,@ splice . Si la variable snuea la valeur alors évalue à , alors qu’évalue à . Le backquote est le plus souvent utilisé pour définir les extensions de macro. <sup>[59] [60]</sup>(bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)

Les formes auto-évaluées et les formes entre guillemets sont l’équivalent Lisp des littéraux. Il peut être possible de modifier les valeurs des littéraux (mutables) dans le code du programme. Par exemple, si une fonction renvoie un formulaire entre guillemets et que le code qui appelle la fonction modifie le formulaire, cela peut modifier le comportement de la fonction lors des appels ultérieurs.

( defun devrait-être-constant () ‘ ( un deux trois )) ( let (( stuff ( should-be-constant ))) ( setf ( third stuff ) ‘bizarre )) ) ; mal! ( devrait-être-constant ) ; retours (un deux bizarre)

La modification d’une forme entre guillemets comme celle-ci est généralement considérée comme un mauvais style et est définie par ANSI Common Lisp comme erronée (entraînant un comportement “indéfini” dans les fichiers compilés, car le compilateur de fichiers peut fusionner des constantes similaires, les mettre en mémoire protégée en écriture, etc.).

La formalisation de la citation par Lisp a été notée par Douglas Hofstadter (dans Gödel, Escher, Bach ) et d’autres comme un exemple de l’ idée philosophique d’ auto-référence .

Portée et clôture

La famille Lisp se divise sur l’utilisation de la portée dynamique ou statique (alias lexicale) . Clojure, Common Lisp et Scheme utilisent la portée statique par défaut, tandis que newLISP , Picolisp et les langages intégrés dans Emacs et AutoCAD utilisent la portée dynamique. Depuis la version 24.1, Emacs utilise à la fois la portée dynamique et lexicale.

Structure de la liste du code de programme ; exploitation par macros et compilateurs

Une distinction fondamentale entre Lisp et les autres langages est qu’en Lisp, la représentation textuelle d’un programme est simplement une description lisible par l’homme des mêmes structures de données internes (listes chaînées, symboles, nombres, caractères, etc.) que celles qui seraient utilisées par le système Lisp sous-jacent.

Lisp l’utilise pour implémenter un système de macros très puissant. Comme d’autres langages macro tels que celui défini par le préprocesseur C (le préprocesseur macro pour les langages de programmation C , Objective-C et C++ ), une macro renvoie du code qui peut ensuite être compilé. Cependant, contrairement aux macros du préprocesseur C, les macros sont des fonctions Lisp et peuvent donc exploiter toute la puissance de Lisp.

De plus, comme le code Lisp a la même structure que les listes, les macros peuvent être construites avec n’importe laquelle des fonctions de traitement de liste du langage. En bref, tout ce que Lisp peut faire à une structure de données, les macros Lisp peuvent le faire pour coder. En revanche, dans la plupart des autres langages, la sortie de l’analyseur est purement interne à l’implémentation du langage et ne peut pas être manipulée par le programmeur.

Cette fonctionnalité facilite le développement de langages efficaces au sein des langages. Par exemple, le Common Lisp Object System peut être implémenté proprement en tant qu’extension de langage à l’aide de macros. Cela signifie que si une application a besoin d’un mécanisme d’héritage différent, elle peut utiliser un système objet différent. Ceci est en contraste frappant avec la plupart des autres langues; par exemple, Java ne prend pas en charge l’héritage multiple et il n’existe aucun moyen raisonnable de l’ajouter.

Dans les implémentations simplistes de Lisp, cette structure de liste est directement interprétée pour exécuter le programme ; une fonction est littéralement un morceau de structure de liste qui est traversé par l’interpréteur lors de son exécution. Cependant, la plupart des systèmes Lisp importants incluent également un compilateur. Le compilateur traduit la structure de la liste en code machine ou en bytecode pour l’exécution. Ce code peut s’exécuter aussi rapidement que du code compilé dans des langages conventionnels tels que C.

Les macros se développent avant l’étape de compilation, et offrent ainsi des options intéressantes. Si un programme a besoin d’une table précalculée, une macro peut créer la table au moment de la compilation, de sorte que le compilateur n’a besoin que de sortir la table et n’a pas besoin d’appeler du code pour créer la table au moment de l’exécution. Certaines implémentations Lisp ont même un mécanisme, eval-when, qui permet au code d’être présent au moment de la compilation (lorsqu’une macro en aurait besoin), mais pas présent dans le module émis. ^[61]

Évaluation et boucle lecture-évaluation-impression

Les langages Lisp sont souvent utilisés avec une ligne de commande interactive , qui peut être combinée avec un environnement de développement intégré (IDE). L’utilisateur tape des expressions sur la ligne de commande ou demande à l’EDI de les transmettre au système Lisp. Lisp lit les expressions saisies, les évalue et imprime le résultat. Pour cette raison, la ligne de commande Lisp est appelée une boucle de lecture-évaluation-impression ( REPL ).

Le fonctionnement de base du REPL est le suivant. Il s’agit d’une description simpliste qui omet de nombreux éléments d’un vrai Lisp, tels que les guillemets et les macros.

La readfonction accepte les expressions S textuelles en entrée et les analyse dans une structure de données interne. Par exemple, si vous tapez le texte à l’invite, le traduit en une liste chaînée à trois éléments : le symbole , le chiffre 1 et le chiffre 2. Il se trouve que cette liste est également un morceau de code Lisp valide ; c’est-à-dire qu’elle peut être évaluée. C’est parce que la voiture de la liste nomme une fonction – l’opération d’addition.(+ 1 2)read+

Notez que a foosera lu comme un seul symbole. 123sera lu comme le nombre cent vingt-trois. “123”sera lu comme la chaîne “123”.

La evalfonction évalue les données, renvoyant zéro ou plusieurs autres données Lisp en conséquence. L’évaluation n’est pas synonyme d’interprétation; certains systèmes Lisp compilent chaque expression en code machine natif. Il est cependant simple de décrire l’évaluation comme une interprétation : pour évaluer une liste dont la voiture nomme une fonction, evalévalue d’abord chacun des arguments donnés dans son cdr, puis applique la fonction aux arguments. Dans ce cas, la fonction est addition, et l’appliquer à la liste d’arguments donne la réponse . C’est le résultat de l’évaluation.(1 2)3

Le symbole fooest évalué à la valeur du symbole foo. Des données telles que la chaîne “123” évaluent la même chaîne. La liste est évaluée à la liste (1 2 3).(quote (1 2 3))

C’est le travail de la printfonction de représenter la sortie à l’utilisateur. Pour un résultat aussi simple que 3celui-ci, c’est trivial. Une expression évaluée à un morceau de structure de liste nécessiterait de printparcourir la liste et de l’imprimer en tant qu’expression S.

Pour implémenter un Lisp REPL, il suffit d’implémenter ces trois fonctions et une fonction de boucle infinie. (Naturellement, l’implémentation de evalsera complexe, puisqu’elle doit également implémenter tous les opérateurs spéciaux comme ifou lambda.) Ceci fait, un REPL de base est une ligne de code : .(loop (print (eval (read))))

Le Lisp REPL fournit généralement également l’édition des entrées, un historique des entrées, la gestion des erreurs et une interface avec le débogueur.

Lisp est généralement évalué avec impatience . Dans Common Lisp , les arguments sont évalués dans l’ ordre applicatif (“le plus à gauche à l’intérieur”), tandis que dans Scheme , l’ ordre des arguments n’est pas défini, laissant la place à l’optimisation par un compilateur.

Structures de contrôle

Lisp avait à l’origine très peu de structures de contrôle, mais beaucoup d’autres ont été ajoutées au cours de l’évolution du langage. (L’opérateur conditionnel original de Lisp, cond, est le précurseur des if-then-elsestructures ultérieures.)

Les programmeurs utilisant le dialecte Scheme expriment souvent des boucles en utilisant la récursivité terminale . Les points communs de Scheme dans l’informatique académique ont conduit certains étudiants à croire que la récursivité de queue est la seule ou la plus courante façon d’écrire des itérations en Lisp, mais c’est incorrect. Tous les dialectes Lisp souvent vus ont des constructions d’itération de style impératif, de la doboucle de Scheme aux expressions complexes de Common Lisp . loopDe plus, le problème clé qui en fait une question objective plutôt que subjective est que Scheme impose des exigences spécifiques pour le traitement des appels de queue ., et donc la raison pour laquelle l’utilisation de la récursivité terminale est généralement encouragée pour Scheme est que la pratique est expressément soutenue par la définition du langage. En revanche, ANSI Common Lisp ne nécessite pas ^[62] l’optimisation communément appelée une élimination d’appel de queue. Ainsi, le fait que le style récursif de queue comme remplacement occasionnel de l’utilisation de constructions d’ itération plus traditionnelles (telles que do, dolistou loop) soit découragé ^[63] dans Common Lisp n’est pas seulement une question de préférence stylistique, mais potentiellement une question d’efficacité (puisque un appel de queue apparent dans Common Lisp peut ne pas se compiler comme un simple saut ) et l’exactitude du programme (puisque la récursivité de la queue peut augmenter l’utilisation de la pile dans Common Lisp, risquantdébordement de pile ).

Certaines structures de contrôle Lisp sont des opérateurs spéciaux , équivalents aux mots-clés syntaxiques d’autres langages. Les expressions utilisant ces opérateurs ont la même apparence de surface que les appels de fonction, mais diffèrent en ce que les arguments ne sont pas nécessairement évalués ou, dans le cas d’une expression d’itération, peuvent être évalués plus d’une fois.

Contrairement à la plupart des autres langages de programmation majeurs, Lisp permet d’implémenter des structures de contrôle à l’aide du langage. Plusieurs structures de contrôle sont implémentées sous forme de macros Lisp, et peuvent même être macro-étendues par le programmeur qui veut savoir comment elles fonctionnent.

Common Lisp et Scheme ont tous deux des opérateurs pour le flux de contrôle non local. Les différences entre ces opérateurs sont parmi les différences les plus profondes entre les deux dialectes. Scheme prend en charge les continuations réentrantes à l’aide de la call/ccprocédure, ce qui permet à un programme de sauvegarder (et de restaurer ultérieurement) un emplacement particulier en cours d’exécution. Common Lisp ne prend pas en charge les continuations réentrantes, mais prend en charge plusieurs façons de gérer les continuations d’échappement.

Souvent, le même algorithme peut être exprimé en Lisp dans un style impératif ou fonctionnel. Comme indiqué ci-dessus, Scheme a tendance à privilégier le style fonctionnel, en utilisant la récursivité de queue et les continuations pour exprimer le flux de contrôle. Cependant, le style impératif est encore tout à fait possible. Le style préféré par de nombreux programmeurs Common Lisp peut sembler plus familier aux programmeurs habitués aux langages structurés tels que C, tandis que celui préféré par Schermers ressemble plus étroitement aux langages fonctionnels purs tels que Haskell .

En raison de l’héritage précoce de Lisp dans le traitement des listes, il dispose d’un large éventail de fonctions d’ordre supérieur relatives à l’itération sur des séquences. Dans de nombreux cas où une boucle explicite serait nécessaire dans d’autres langages (comme une forboucle en C) en Lisp, la même tâche peut être accomplie avec une fonction d’ordre supérieur. (Il en va de même pour de nombreux langages de programmation fonctionnels.)

Un bon exemple est une fonction qui dans Scheme est appelée mapet dans Common Lisp est appelée mapcar. Étant donné une fonction et une ou plusieurs listes, mapcarapplique la fonction successivement aux éléments des listes dans l’ordre, en collectant les résultats dans une nouvelle liste :

( carte #’ + ‘ ( 1 2 3 4 5 ) ‘ ( 10 20 30 40 50 ))

Cela applique la +fonction à chaque paire correspondante d’éléments de liste, donnant le résultat .(11 22 33 44 55)

Exemples

Voici des exemples de code Common Lisp.

Le programme de base « Hello, World ! » :

( imprimez “Hello, World!” )

La syntaxe Lisp se prête naturellement à la récursivité. Les problèmes mathématiques tels que l’énumération d’ensembles définis de manière récursive sont simples à exprimer dans cette notation. Par exemple, pour évaluer la factorielle d’un nombre :

( defun factoriel ( n ) ( if ( zerop n ) 1 ( * n ( factoriel ( 1- n )))))

Une implémentation alternative prend moins d’espace de pile que la version précédente si le système Lisp sous-jacent optimise la récursivité de queue :

( defun factoriel ( n &facultatif ( acc 1 )) ( if ( zerop n ) acc ( factoriel ( 1- n ) ( * acc n ))))

Comparez les exemples ci-dessus avec une version itérative qui utilise la macro de Common Lisp :loop

( defun factoriel ( n ) ( boucle pour i de 1 à n pour fac = 1 puis ( * fac i ) enfin ( retour fac )))

La fonction suivante inverse une liste. (La fonction inverse intégrée de Lisp fait la même chose.)

( defun -reverse ( liste ) ( let (( valeur de retour )) ( dolist ( e liste ) ( push e valeur de retour )) valeur de retour ))

Systèmes d’objets

Divers systèmes et modèles d’objets ont été construits au-dessus, à côté ou dans Lisp, notamment :

• Le Common Lisp Object System , CLOS, fait partie intégrante de l’ANSI Common Lisp. CLOS est issu de New Flavours et CommonLOOPS. ANSI Common Lisp a été le premier langage de programmation orienté objet standardisé (1994, ANSI X3J13).
• ObjectLisp ^[64] ou Object Lisp , utilisé par Lisp Machines Incorporated et les premières versions de Macintosh Common Lisp
• LOOPS (Lisp Object-Oriented Programming System) et le dernier CommonLOOPS
• Flavours , construit au MIT , et son descendant New Flavours (développé par Symbolics ).
• KR (abréviation de Knowledge Representation), un système d’objets basé sur des contraintes développé pour faciliter l’écriture de Garnet, une bibliothèque graphique pour Common Lisp .
• Knowledge Engineering Environment (KEE) a utilisé un système objet nommé UNITS et l’a intégré à un moteur d’inférence ^[65] et à un système de maintien de la vérité (ATMS).

Systèmes d’exploitation

Plusieurs systèmes d’exploitation , y compris des systèmes basés sur des langages, sont basés sur Lisp (utilisent les fonctionnalités, conventions, méthodes, structures de données de Lisp, etc.), ou sont écrits en Lisp, ^[66] dont :

Genera , renommé Open Genera, ^[67] par Symbolics ; Medley, écrit en Interlisp, à l’origine une famille de systèmes d’exploitation graphiques qui s’exécutaient sur les dernières stations de travail Star de Xerox ; ^{[68] [69]} Mezzano ; ^[70] Intérimaire ; ^{[71] [72]} ChrysaLisp, ^[73] par les développeurs du TAOS de Tao Systems ; ^[74] et le très Lisp-like Urbit, ^[75] utilisant la technologie de crypto-monnaie Ethereum. ^[76]

Voir également

• Code auto-modifiable

Références

1. ^ “Introduction” . Le Manuel Julia . Lisez la documentation. Archivé de l’original le 2016-04-08 . Récupéré le 10/12/2016 .
2. ^ “Questions et réponses sur la langue de Wolfram” . Recherche Wolfram . Récupéré le 10/12/2016 .
3. ^ Edwin D. Reilly (2003). Jalons de l’informatique et des technologies de l’information . Groupe d’édition Greenwood. p. 156–157. ISBN 978-1-57356-521-9.
4. ^ “SICP : Avant-propos” . Archivé de l’original le 2001-07-27. Lisp est un survivant, utilisé depuis environ un quart de siècle. Parmi les langages de programmation actifs, seul Fortran a eu une durée de vie plus longue.
5. ^ “Conclusions” . Archivé de l’original le 2014-04-03 . Récupéré le 04/06/2014 .
6. ^ “L’Art de l’Interprète, ou le Complexe de Modularité (Parties Zéro, Un et Deux), Partie Zéro, P. 4” . Bibliothèques du MIT. hdl : 1721.1/6094 . Récupéré le 01/08/2020 .
7. ^ “Les meilleurs langages de programmation en intelligence artificielle” . Intelligence Artificielle . APRO. Archivé de l’original le 2020-10-30 . Récupéré le 15/02/2021 .
8. ^ Paul Graham. “La revanche des nerds” . Récupéré le 14/03/2013 .
9. ^ Chisnal, David (2011-01-12). Langages de programmation influents, partie 4 : Lisp .
10. ^ Jones, Robin; Maynard, Clive; Stewart, Ian (6 décembre 2012). L’art de la programmation Lisp . Springer Science et médias d’affaires. p. 2. ISBN 9781447117193.
11. ^ McCarthy, John. “Fonctions récursives d’expressions symboliques et leur calcul par machine, partie I” . Archivé de l’original le 2013-10-04 . Récupéré le 13/10/2006 .
12. ^ Forgeron, David Canfield. Manuel d’utilisation MLISP (PDF) . Récupéré le 13/10/2006 .
13. ^ McCarthy, John (12 février 1979). “Histoire de Lisp: Laboratoire d’intelligence artificielle” (PDF) .
14. ^ Stoyan, Herbert (1984-08-06). Début de l’histoire de LISP (1956–1959) . LFP ’84: Actes du Symposium ACM 1984 sur LISP et programmation fonctionnelle. Association pour les machines informatiques . p. 307. doi : 10.1145/800055.802047 . Archivé de l’original le 2005-04-05.
15. ^ McCarthy, John. “Préhistoire LISP – été 1956 à été 1958” . Récupéré le 14/03/2010 .
16. ^ Cerf, Tim; Lévin, Mike. “AI Memo 39-Le nouveau compilateur” (PDF) . Archivé de l’original (PDF) le 2020-12-13 . Récupéré le 18/03/2019 .
17. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1962, (15e impression, 1985)). Manuel du programmeur LISP 1.5 (PDF) (2e éd.). p. Préface. {{cite book}}: Vérifier les valeurs de date dans : |date=( aide )
18. ^ La taille de mot 36 bits du PDP-6 / PDP-10 a été influencée par l’utilité d’avoir deux pointeurs Lisp 18 bits dans un seul mot. Peter J. Hurley (18 octobre 1990). “L’histoire de TOPS ou la vie dans les AC rapides” . Newsgroup : alt.folklore.computers . Usenet : 84950@tut.cis.ohio-state.edu . Le projet PDP-6 a débuté au début de 1963, en tant que machine 24 bits. Il est passé à 36 bits pour LISP, un objectif de conception.
19. ^ Common Lisp :(defun f (x) x)
    Schéma :(define f (lambda (x) x))ou(define (f x) x)
20. ^ McCarthy, J. ; Brayton, R. ; Edwards, D. ; Fox, P. ; Hodes, L. ; Luckham, D. ; Maling, K. ; Park, D. ; Russell, S. (mars 1960). “Manuel du programmeur LISP I” (PDF) . Boston , Massachusetts : groupe d’intelligence artificielle, centre de calcul et laboratoire de recherche du MIT. Archivé de l’original (PDF) le 17/07/2010. {{cite journal}}: Cite journal requires |journal= (help)Consulté le 11 mai 2010.
21. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985) [1962]. Manuel du programmeur LISP 1.5 (PDF) (2e éd.). Presse du MIT . ISBN 0-262-13011-4.
22. ^ Quam, Lynn H.; Diffle, Whitfield. Manuel Stanford LISP 1.6 (PDF) .
23. ^ “Manuel de référence Maclisp” . 3 mars 1979. Archivé de l’original le 14/12/2007.
24. ^ Teitelman, Warren (1974). Manuel de référence InterLisp (PDF) . Archivé de l’original (PDF) le 2006-06-02 . Récupéré le 19/08/2006 .
25. ↑ Outils de génération d’interfaces : état de l’art et classification par H. El Mrabet
26. ^ Gerald Jay Sussman et Guy Lewis Steele Jr. (décembre 1975). “Schéma: un interprète pour le calcul Lambda étendu” (PDF) . Mémos IA . Laboratoire d’IA du MIT . BUT-349 . Récupéré le 23 décembre 2021 .
27. ^ Steele, Guy L., Jr. (1990). “Objectif” . Common Lisp the Language (2e éd.). ISBN 0-13-152414-3.
28. ^ Kantrowitz, Marc; Margolin, Barry (20 février 1996). “Histoire : d’où vient Lisp ?” . FAQ : Lisp Foire Aux Questions 2/7 .
29. ^ “ISO/CEI 13816:1997” . Iso.org. 2007-10-01 . Récupéré le 15/11/2013 .
30. ^ “ISO/CEI 13816:2007” . Iso.org. 2013-10-30 . Récupéré le 15/11/2013 .
31. ^ “Charte X3J13” .
32. ^ “L’enquête Road To Lisp” . Archivé de l’original le 2006-10-04 . Récupéré le 13/10/2006 .
33. ^ “Tendances pour l’avenir” . Faqs.org. Archivé de l’original le 2013-06-03 . Récupéré le 15/11/2013 .
34. ^ Weinreb, Daniel. “Implémentations de Common Lisp : une enquête” . Archivé de l’original le 2012-04-21 . Récupéré le 4 avril 2012 .
35. ^ “LISP50@OOPSLA” . Lisp50.org . Récupéré le 15/11/2013 .
36. ^ Documents : Normes : R5RS . schemaers.org (2012-01-11). Consulté le 17/07/2013.
37. ^ “Pourquoi le MIT utilise maintenant python au lieu de schéma pour son programme CS de premier cycle” . cemerick.com . 24 mars 2009. Archivé de l’original le 17 septembre 2010 . Consulté le 10 novembre 2013 .
38. ^ Broder, Evan (8 janvier 2008). “La fin d’une époque” . mitadmissions.org . Consulté le 10 novembre 2013 .
39. ^ “Programmes de premier cycle MIT EECS” . www.eecs.mit.edu . Génie électrique et informatique du MIT . Récupéré le 31 décembre 2018 .
40. ^ “Le cours d’introduction à Python du MITx atteint 1,2 million d’inscriptions” . MIT EECS . Génie électrique et informatique du MIT . Récupéré le 31 décembre 2018 .
41. ^ Chapitre 1.1.2, Historique, norme ANSI CL
42. ^ [1] Clasp est une implémentation Common Lisp qui interagit avec C++ et utilise LLVM pour la compilation juste-à-temps (JIT) en code natif.
43. ^ [2] “Armed Bear Common Lisp (ABCL) est une implémentation complète du langage Common Lisp comprenant à la fois un interpréteur et un compilateur, fonctionnant dans la JVM”
44. ^ [3] Archivé le 22/06/2018 sur Wayback Machine Common Lisp Implémentations: Une enquête
45. ^ [4] Comparaison des implémentations Common Lisp activement développées
46. ^ Un regard approfondi sur les collections Clojure , récupéré le 24/06/2012
47. ^ “Clojure rationnel” . Récupéré le 27 août 2019 . Clojure est un Lisp non contraint par la rétrocompatibilité
48. ^ Script-fu dans GIMP 2.4 , récupéré le 29/10/2009
49. ^ librep sur Sawfish Wikia, récupéré le 29/10/2009
50. ^ “Schéma IEEE” . IEEE 1178-1990 – Norme IEEE pour le langage de programmation de schémas . Récupéré le 27 août 2019 .
51. ^ “Préhistoire LISP – été 1956 à été 1958” . J’ai inventé des expressions conditionnelles en relation avec un ensemble de routines de mouvement légal d’échecs que j’ai écrites en FORTRAN pour l’IBM 704 au MIT en 1957–58 … Un article définissant les expressions conditionnelles et proposant leur utilisation dans Algol a été envoyé aux Communications de l’ACM mais a été arbitrairement rétrogradé à une lettre à l’éditeur, car elle était très courte.
52. ^ “Signification de la” programmation orientée objet “selon le Dr Alan Kay” . 2003-07-23. Je ne comprenais pas l’idée monstre LISP de métalangage tangible à l’époque, mais je me suis un peu rapproché des idées sur les langages extensibles … La deuxième phase consistait à enfin comprendre LISP, puis à utiliser cette compréhension pour faire beaucoup plus agréable et plus petit et plus des sous-structures puissantes et plus tardives … Pour moi, la POO ne signifie que la messagerie, la rétention et la protection locales et la dissimulation du processus d’état, et la liaison tardive extrême de toutes choses. Cela peut être fait en Smalltalk et en LISP. Il existe peut-être d’autres systèmes dans lesquels cela est possible, mais je ne les connais pas.
53. ^ Lieberman, Henri; Hewitt, Carl (juin 1983), “Un récupérateur de place en temps réel basé sur la durée de vie des objets” , Communications of the ACM , 26 (6): 419–429, CiteSeerX 10.1.1.4.8633 , doi : 10.1145/358141.358147 , hdl : 1721.1/6335 , S2CID 14161480
54. ^ Edsger W. Dijkstra (1972), Le programmeur humble (EWD 340) (Conférence du prix ACM Turing).
55. ^ “Un regard sur Clojure et la résurgence du Lisp” .
56. ^ “Le Fichier Jargon – Lisp” . Récupéré le 13/10/2006 .
57. ^ Sebesta, Robert W. (2012). ” “2.4 Programmation fonctionnelle : LISP” ;”6.9 Types de listes”;”15.4 Le premier langage de programmation fonctionnelle : LISP””. Concepts of Programming Languages ​​(imprimé) (10e éd.). Boston, MA, États-Unis: Addison-Wesley. pp. 47–52, 281–284, 677–680. ISBN 978-0-13-139531-2.
58. ^ NB: une soi-disant “liste pointillée” n’est qu’un type de “liste impropre”. L’autre type est la “liste circulaire” où les contre-cellules forment une boucle. Généralement, cela est représenté en utilisant #n=(…) pour représenter la cellule contre cible qui aura plusieurs références, et #n# est utilisé pour faire référence à ce contre. Par exemple, (#1=(ab) . #1#) serait normalement imprimé comme ((ab) ab) (sans l’impression de structure circulaire activée), mais rend la réutilisation de la cellule cons claire. #1=(a . #1#) ne peut normalement pas être imprimé car il est circulaire, bien que (a…) soit parfois affiché, le CDR de la cellule contre définie par #1= est lui-même.
59. ^ “CSE 341 : Schéma : Citation, Quasiquote et Métaprogrammation” . Cs.washington.edu. 1999-02-22 . Récupéré le 15/11/2013 .
60. ^ Quasiquotation en Lisp Archivé le 03/06/2013 à la Wayback Machine , Alan Bawden
61. ^ Temps d’évaluation – Extensions Common Lisp . Gnu.org. Consulté le 17/07/2013.
62. ^ 3.2.2.3 Contraintes sémantiques dans Common Lisp HyperSpec
63. ^ 4.3. Control Abstraction (Recursion vs. Iteration) dans Tutorial on Good Lisp Programming Style par Kent Pitman et Peter Norvig , août 1993.
64. ^ page 17 de Bobrow 1986
65. ^ Veitch, page 108, 1988
66. ^ Éprouvé, Liam (29 mars 2022). “Le monde sauvage des systèmes d’exploitation non-C” . Le Registre . Récupéré le 02/02/2022 .
67. ^ “Symboliques Open Genera 2.0” . Archives Internet GitHub . 7 janvier 2020 . Récupéré le 02/02/2022 .
68. ^ “Projet Interlisp.org” . Interlisp.org . 15 mars 2022 . Récupéré le 02/02/2022 .
69. ^ “Interlisp Medley” . GitHub . mars 2022 . Récupéré le 02/02/2022 .
70. ^ froggey (1er août 2021). “Mezzano” . GitHub . Récupéré le 02/02/2022 .
71. ^ Hartmann, Lukas F. (10 septembre 2015). « Intérimaire » . Interim-os . Récupéré le 02/02/2022 .
72. ^ Hartmann, Lukas F. (11 juin 2021). « Intérimaire » . GitHub . Récupéré le 02/02/2022 .
73. ^ Hinsley, Chris (23 février 2022). “Chrysalisp” . GitHub . Récupéré le 02/02/2022 .
74. ^ Forgeron, Tony (21 août 2013). “Le micro pionnier britannique Chris Shelton: L’esprit derrière le Nascom 1” . Le Registre . Récupéré le 02/02/2022 .
75. ^ “Un système d’exploitation et un réseau de table rase pour le 21e siècle” . Urbit.org . Récupéré le 02/02/2022 .
76. ^ O’Leary, Rachel-Rose (13 septembre 2021). “Urbit déplace sa galaxie de serveur virtuel vers Ethereum” . CoinDesk . Récupéré le 02/02/2022 .

Lectures complémentaires

• McCarthy, John (1979-02-12). “L’implémentation de Lisp” . Histoire de Lisp . Université Stanford . Récupéré le 17/10/2008 .
• Steele, Jr., Guy L.; Richard P. Gabriel (1993). L’évolution de Lisp (PDF) . La deuxième conférence ACM SIGPLAN sur l’histoire des langages de programmation. New York, NY : ACM. p. 231–270. ISBN 0-89791-570-4. Archivé de l’original (PDF) le 2006-10-12 . Récupéré le 17/10/2008 .
• Veitch, Jim (1998). “Une histoire et une description du CLOS”. Dans Salus, Peter H (éd.). Manuel des langages de programmation . Vol. IV, Langages de programmation fonctionnels et logiques (première éd.). Indianapolis, IN : édition technique Macmillan. p. 107–158 . ISBN 1-57870-011-6.
• Abelson, Harold ; Sussman, Gérald Jay ; Susman, Julie (1996). Structure et interprétation des programmes informatiques (2e éd.). Presse du MIT. ISBN 0-262-01153-0.
• My Lisp Experiences and the Development of GNU Emacs , transcription du discours de Richard Stallman , 28 octobre 2002, à l’ International Lisp Conference
• Graham, Paul (2004). Hackers et peintres. Les grandes idées de l’ère informatique . O’Reilly. ISBN 0-596-00662-4.
• Berkeley, Edmund C. ; Bobrow, Daniel G. , éds. (mars 1964). Le langage de programmation LISP : son fonctionnement et ses applications (PDF) . Cambridge, Massachusetts : MIT Press.
  • Article largement basé sur le chapitre LISP – A Simple Introduction : Berkeley, Edmund C. (septembre 1964). “Le langage de programmation Lisp : une introduction et une évaluation” . Informatique et automatisation : 16 -23.
• Weissman, Clark (1967). Introduction à LISP 1.5 (PDF) . Belmont, Californie : Dickenson Publishing Company Inc.

Liens externes

Lisp (langage de programmation)dans les projets frères de Wikipédia

• Définitions du Wiktionnaire
• Médias de Commons
• Citations de Wikiquote
• Textes de Wikisource
• Manuels de Wikibooks
• Ressources de Wikiversité

Histoire

• Histoire de Lisp – Histoire de John McCarthy du 12 février 1979
• Lisp History – L’histoire d’Herbert Stoyan compilée à partir des documents (reconnue par McCarthy comme plus complète que la sienne, voir: liens d’histoire de McCarthy )
• Histoire de LISP au Computer History Museum

Associations et réunions

• Association des utilisateurs Lisp
• Réunion commune européenne sur le lisp
• Symposium européen Lisp
• Conférence internationale Lisp

Livres et tutoriels

• Casting SPELs in Lisp , un tutoriel d’introduction de style bande dessinée
• On Lisp , un livre gratuit de Paul Graham
• Practical Common Lisp , édition freeware par Peter Seibel
• Lisp pour le web
• Pays de Lisp
• Laissez tomber Lambda

Entrevues

• Entretien d’histoire orale avec John McCarthy au Charles Babbage Institute , Université du Minnesota, Minneapolis. McCarthy discute de son rôle dans le développement du temps partagé au Massachusetts Institute of Technology. Il décrit également ses travaux en intelligence artificielle (IA) financés par l’Advanced Research Projects Agency, notamment l’IA basée sur la logique (LISP) et la robotique.
• Entretien avec Richard P. Gabriel (Podcast)

Ressources

• CLiki : le wiki Common Lisp
• Le répertoire Common Lisp (via la Wayback Machine ; archivé à partir de l’original )
• Index FAQ Lisp
• pâte à papier
• Planète Lisp
• Nouvelles Lisp hebdomadaires
• newLISP – Un langage de script moderne et polyvalent
• Lisp à Curlie