Light Mode

Aller au contenu

Lisp

Un article de Wikipedia, l'encyclopedie libre.

Cet article concerne le langage de programmation. Pour le protocole Internet, voir Locator/Identifier Separation Protocol.

Pour les articles homonymes, voir Lisp (homonymie).

Lisp
Date de premiere version 1958
Paradigmes fonctionnel, imperatif
Auteur John McCarthy
Typage dynamique
Dialectes Common Lisp, Emacs Lisp, Scheme, Clojure
Influence par Information Processing Language
Systeme d'exploitation Multiplate-forme
modifier

Lisp est la plus ancienne famille de langages de programmation a la fois imperatifs et fonctionnels[1]. Developpe initialement en tant que modele pratique pour representer des programmes (par contraste avec la notion theorique de machine de Turing), il est devenu, dans les annees 1970 et 80, un des langages de choix (comme le langage Prolog) pour la recherche en intelligence artificielle. Les langages Lisp sont aujourd'hui utilises dans de nombreux domaines, de la programmation Web a la finance[2], et dans certains cursus de formation en informatique[3].

Le terme Lisp a ete forge a partir de l'anglais << list processing >> (<< traitement de listes >>). Tous les dialectes de Lisp partagent les memes operateurs de manipulation de listes chainees simples. Lisp se distingue en outre par une syntaxe simple en notation prefixee, son typage dynamique des donnees, le support pour la programmation fonctionnelle, sa gestion automatique de la memoire et la faculte de manipuler le code source en tant que structure de donnees.

Les langages Lisp sont reconnaissables immediatement a leur apparence. Le code source des programmes est ecrit en utilisant la meme syntaxe que celle des listes -- la syntaxe parenthesee des S-expressions. Chaque sous-expression d'un programme (ou structure de donnees) est delimitee par des parentheses. Cela simplifie grandement l'analyse syntaxique des programmes Lisp et rend simple la metaprogrammation -- la creation de programmes qui creent d'autres programmes ou modifient le programme courant.

Si l'on excepte le langage machine et le langage d'assemblage (ou plus communement << assembleur >>), Lisp est le deuxieme langage le plus ancien (juste apres Fortran) parmi les langages qui se sont largement diffuses. Lisp a beaucoup evolue depuis le debut des annees 1960 et a ainsi donne naissance a de nombreux dialectes.

Le langage Lisp fut invente par John McCarthy en 1958 alors qu'il etait au Massachusetts Institute of Technology (MIT). Il publia un article intitule << Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I >>[4] (soit << Fonctions Recursives d'expressions symboliques et leur evaluation par une Machine, partie I >>) dans la revue CACM en 1960 ; la partie II ne fut jamais publiee.

Le premier interpreteur fonctionnait sur un ordinateur IBM 704 et deux instructions de cette machine devinrent les deux operations primitives de Lisp pour decomposer les listes :

  • car (contents of address register) : le premier element de la liste ;
  • cdr (contents of decrement register) : le reste de la liste.

L'operation qui consiste a fabriquer une liste a partir d'un premier element et d'une liste est notee cons.

Dans son article, John McCarthy introduit deux syntaxes : les S-expressions (expressions symboliques, parfois appelees << sexp >>) et les M-expressions (meta-expressions permettant l'homoiconicite pour exprimer les fonctions manipulant des S-expressions autrement dit pour mettre en oeuvre la reflexion ). Les M-expressions n'ont jamais ete tres appreciees et la plupart des Lisps de nos jours utilisent des S-expressions pour les programmes comme pour les donnees. C'est la syntaxe des S-expressions qui fait reprocher a Lisp son abondance de parentheses, mais c'est aussi une des raisons de la puissance et de la souplesse du langage.

En raison de son expressivite et de sa flexibilite, Lisp eut beaucoup de succes dans la communaute de l'intelligence artificielle (cf. Apports).

Dans les annees 1970, on crea des ordinateurs specialises dans l'execution de programmes Lisp : les machines Lisp.

Durant les annees 1980 et 1990, on fit de grands efforts pour unifier les nombreux dialectes de Lisp qui etaient apparus. Le resultat fut la normalisation de Common Lisp dont la norme ANSI fut publiee en 1994 sous la reference << ANSI X3.226-1994 Information Technology Programming Language Common Lisp >>. L'ISO publia de son cote en 1997 la norme ISLISP (en) ISO/IEC 13816:1997(E), revisee en 2007 par la norme ISO/IEC 13816:2007(E). A ce moment, Lisp etait bien moins florissant qu'a sa grande epoque.

Bien qu'eclipse par des langages proches de la machine (C, C++) ou des langages plus structures et types (Haskell), Lisp reste un langage relativement utilise, en particulier en tant que langage embarque dans des applications, ou il sert de langage d'extension[ref. necessaire]. Les cas les plus connus d'utilisation embarquee de Lisp sont l'editeur de texte Emacs et le langage AutoLISP (en) d'AutoCAD. On notera par ailleurs que Lisp vient en quatrieme position en termes de lignes de codes utilisees pour implementer les 8 600 paquets sources disponibles dans le systeme d'exploitation Debian publie en . Les huit premiers langages se distribuent ainsi : C (57 %), C++ (16,8 %), Shell (9 %), Lisp (3 %), Perl (2,8 %), Python (1,8 %), Java (1,6 %), Fortran (1,2 %)[5]. En , Lisp se place en 15e position de l'index TIOBE. En juillet 2020, il est classe 34e.

Les listes sont delimitees par des parentheses et leurs elements sont separes par des espaces : (1 2 "foo"). Un programme Lisp est un arbre de syntaxe compose avec des listes. Cette utilisation des parentheses donne lieu a des moqueries utilisant l'acronyme LISP : << Lots of Irritating and Silly Parentheses >> (<< Des tas de parentheses irritantes et idiotes >>), ou << Lots of Insipid and Stupid Parentheses >> (<< Des tas de parentheses insipides et stupides >>), ou << Langage Informatique Stupidement Parenthese >>, ou << Langage Insipide Sature de Parentheses >>.

Lisp est un langage oriente expression : il ne fait pas de distinction entre << expressions >> et << instructions >> comme le font de nombreux langages (par exemple Pascal) ; tout est expression et retourne une valeur ou un ensemble de valeurs.

La plupart des expressions Lisp sont des applications de fonction. Ce que d'autres langages ecrivent

f(a,b,c)

Lisp l'ecrit

(f a b c)

Ainsi une somme ne se note pas

1+2+3+4

ni

somme(1,2,3,4)

mais

(+ 1 2 3 4)

On utilise la meme notation prefixee (dite notation polonaise[6]) pour les << formes speciales >> et les << macros >> : le premier element dans la liste, dans ces cas, determine comment les elements suivants seront traites. Une expression peut etre une application de fonction, une forme speciale ou une application de macro suivant la nature du premier element.

Syntaxe en notation EBNF

[modifier | modifier le code]

Le langage Lisp dispose d'une syntaxe tres simple et elegante, utilisant un minimum de concepts. Cette economie de concepts mene Gregory Chaitin a qualifier cette syntaxe de << joyau de splendeur mathematique et de beaute intellectuelle austere >>[7].

A contrario, elle ne permet pas la detection d'erreur.

L'essentiel du langage Lisp est defini par seulement trois regles EBNF :

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

Ces regles peuvent se traduire de la maniere suivante en francais :

  • un programme Lisp est une liste d'expressions :
  • une expression peut etre un atome ou une liste (recursion) ;
  • un atome est soit : un nombre, un nom, une chaine de caracteres, un operateur.

Les programmes suivants ne sont pas typiques des vrais programmes Lisp. Ils sont typiques de la presentation que l'on fait de Lisp dans les cours d'informatique. Les exemples sont donnes en syntaxe Common Lisp.

La factorielle est un grand classique :

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

On peut aussi ecrire plus efficacement (voir recursion terminale) :

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

Un autre exemple typique est cette fonction qui renverse une liste (Lisp a une fonction integree reverse a cet effet) :

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

Par opposition a la programmation numerique developpee jusqu'alors, Lisp qui travaille sur des symboles plutot que des nombres a permis de creer un style de programmation different, rendant possible l'intelligence artificielle.[ref. necessaire]

D'ou, par exemple, des dialogues pseudo-naturels (cf Eliza, test de Turing).

De plus, ses fonctions et programmes ont la meme forme que ses donnees (propriete d'homoiconicite).

On peut donc en Lisp passer a travers le miroir. Ainsi,

  • on peut simuler un robot qui, au recu d'une mission (liste de commandes a executer avec une certaine liberte), en raisonnant d'abord sur cette liste et son environnement, ordonnance ces commandes, puis les execute dans l'ordre qu'il a adopte ; en effet, (eval commande) traitera le libelle de commande, jusque-la donnee statique, en expression a evaluer ;
  • en retroconception, on peut partir de la trace d'une fonction inconnue pour tenter de retrouver cette fonction ; combiner diverses techniques (differences premieres, secondes... et quotients similaires) permet alors
    • de proposer des identifications, et caracteriser leur plausibilite ;
    • a l'aide d'une fonction generatrice utilisant la fonction (define ) qui lie un nom de fonction et une definition, engendrer le code Lisp concretisant chaque identification, afin de pouvoir la tester plus finement ;
  • on peut meme donner en Lisp le principe d'un interprete Lisp.

Une particularite du langage Lisp, qui pendant longtemps resta uniquement un langage interprete, est que contrairement aux autres langages interpretes des annees 1960 et 1970 son execution etait aussi -- voire parfois plus -- rapide que celle des langages compiles. Cette particularite provient de sa syntaxe qui fait que la place de chaque type d'objet (fonction, operateur, donnee) est previsible et ne requiert pas l'analyse prealable d'une sequence de code source avant de construire la sequence de code d'execution.

Ce langage comportait un ramasse-miettes des sa premiere version[8].

Extension : Lisp et les objets

[modifier | modifier le code]

Sous l'influence de Simula, divers systemes a objets ont ete construits a partir de Lisp, notamment :

  • Flavors, concu au MIT
  • Le Common Lisp Object System (CLOS), un descendant de Flavors

CLOS offre de l'heritage multiple, la selection multiple et un puissant systeme de combinaison de methodes. Common Lisp (dont CLOS fait partie) fut le premier langage oriente-objet standardise.

<< LISP a un petit nombre de concepts elementaires puissants, et tout le reste est construit au-dessus de ca, ce qui correspond a la facon de travailler des mathematiciens ; c'est a ca que ressemblent les theories mathematiques. Ces theories, les bonnes theories, consistent a definir quelques nouveaux concepts clefs, et a partir de la le feu d'artifice commence : elles revelent de nouvelles allees, elles ouvrent la porte a des mondes radicalement nouveaux. LISP est comme ca aussi ; il est plus proche des maths que la plupart des langages de programmation. Du moins si vous eliminez les parties utiles qui ont ete ajoutees, les ajouts qui ont fait de LISP un outil pratique. Ce qui reste si vous faites cela, c'est le LISP original, le coeur conceptuel de LISP, un coeur qui est un joyau de beaute mathematique et de beaute intellectuelle austere. >>

-- Gregory Chaitin, Meta Maths : The quest of Omega, 2006, Atlantic, p. 46

Aujourd'hui, certains diraient que Scheme est le derive de Lisp atteignant la beaute decrite par Chaitin ; et il est certain que Common Lisp, le descendant en ligne droite des grandes cuvees des dialectes passes de LISP (Maclisp, Interlisp, Zetalisp) penche plus du cote de la boite a outils geante, bien qu'ayant conserve intact son coeur conceptuel.

G. Chaitin a utilise ce Lisp idealise pour ses recherches : Elegant LISP Programs[9].

<< The most powerful programming language is Lisp. If you don't know Lisp (or its variant, Scheme), you don't know what it means for a programming language to be powerful and elegant. Once you learn Lisp, you will see what is lacking in most other languages.
Unlike most languages today, which are focused on defining specialized data types, Lisp provides a few data types which are general. Instead of defining specific types, you build structures from these types. Thus, rather than offering a way to define a list-of-this type and a list-of-that type, Lisp has one type of lists which can hold any sort of data. >>

-- Richard Stallman , How I do my computing[10]

<< Le langage de programmation le plus puissant est Lisp. Si vous ne connaissez pas Lisp (ou sa variante, Scheme), vous ne savez pas ce qu'est un langage de programmation puissant et elegant. Apres avoir appris Lisp, vous verrez ce qu'il manque dans la majorite des autres langages.
Contrairement a la plupart des langages d'aujourd'hui, qui se concentrent sur la definition de types de donnees specialises, Lisp offre peu de types de donnees, mais ils sont generiques. Au lieu de definir des types specifiques, vous construisez des structures a partir de ceux-la. Ainsi, au lieu d'offrir une methode pour definir un type de liste-de-ceci ou un type de liste-de-cela, Lisp a un type de liste qui peut contenir n'importe quel genre de donnees. >>

-- How I do my computing[10]

Genealogie et variantes

[modifier | modifier le code]

Notes et references

[modifier | modifier le code]
  1. | (en) D. A. Kent << Some History of Functional Programming Languages >> () (lire en ligne) [PDF]
    --TFP12 (lire en ligne)
  2. | awesome-lisp-companies.
  3. | Description du cours << Structure and Interpretation of Computer Programs >>, MIT
  4. | John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM, Vol. 3 Issue 4, April 1960 DOI 10.1145/367177.367199
  5. | UPGRADE (European Journal for the Informatics Professional), juin 2005, p. 14
  6. | Formellement, il s'agit de notation prefixee, mais l'usage particulier des parentheses dans le langage Lisp induit qu'il s'agit reellement de notation polonaise, le role meme de l'interpreteur etant de reduire les expressions parenthesees en expressions lineaires interpretables de gauche a droite, les operateurs en premier.
  7. | Gregory Chaitin Hasard et complexite en mathematiques Flammarion 2009.
  8. | Comme le dit Daniel J. Edwards dans l'interview qu'il donne a Jeffrey R. Yost << Oral history interview with Daniel J. Edwards >>, Charles Babbage Institute,
  9. | Elegant LISP Programs
  10. | (en) << How I do my computing >> (consulte le )
  11. | Eligis
  12. | ISO/IEC 13816:1997(E)
  13. | ISO/IEC 13816:2007(E)

Sur les autres projets Wikimedia :

  • Lisp, sur le Wiktionnaire

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]