Lisp at 4. Exemple 2 : Mesure informelle du pouvoir d'expression d'un langage

Home
Up
Previous
Next

Chapitre 4.    Exemple 2 - Mesure informelle du pouvoir d'expression d'un langage

Du point de vue de la théorie du calcul, tous les langages de programmation usuels sont équivalents (plus précisément Turing équivalent, du mathématicien anglais Alan Turing). Ceci concerne le pouvoir d'expression théorique d'un langage de programmation mais n'exprime en rien le pouvoir d'expression effectif d'un langage, c'est-à-dire la facilité avec laquelle un langage permet de programmer un problème donné.

Il n'y a pas de test formel de mesure du pouvoir d'expression effectif d'un langage. On a montré dans l'exemple précédent, comment les moyens d'abstraction du Lisp contribuaient au pouvoir d'expression du Lisp. D'autre part, on peut mesurer le pouvoir d'expression effectif d'un langage de façon informelle, par la facilité relative avec laquelle il permet la résolution de certains problèmes fondamentaux réputés difficiles.

En 1983, un problème de ce type fût proposé par Ken Thomson lors d'un exposé dans le cadre de la chaire Turing; ce "défi", lancé à la communauté informatique, était d'écrire un programme n'ayant d'autre fonction que de s'auto-reproduire et qui soit le plus court possible (l'exécution de ce programme doit donc reproduire une copie exacte du programme tel que le programmeur l'a écrit; autrement dit, il s'agit d'écrire un programme source qui, une fois compilé et exécuté, produit le programme source).

Ken Thomson, l'auteur de ce problème et un des créateurs d'UNIX, a écrit une version en langage C de ce programme; celui-ci comporte 233 lignes d'un code pas très attrayant (voir [VALD91]). La version Pascal est plus courte (28 lignes) mais également peu lisible.

En Lisp, ce programme ne prend que 2 lignes et est d'une lecture aisée pour qui comprend un peu de Lisp:

((LAMBDA (X) (LIST X (LIST 'QUOTE X)))
    '(LAMBDA (X) (LIST X (LIST 'QUOTE X))))

L'évaluation de cette expression Lisp donne donc à nouveau la même expression, soit:

((LAMBDA (X) (LIST X (LIST 'QUOTE X)))
    '(LAMBDA (X) (LIST X (LIST 'QUOTE X))))
=>
((LAMBDA (X) (LIST X (LIST 'QUOTE X)))
    '(LAMBDA (X) (LIST X (LIST 'QUOTE X))))

Commentaires

Cette expression Lisp se lit comme l'application de la fonction anonyme (LAMBDA (X) (LIST X (LIST 'QUOTE X)) à l'argument (LAMBDA (X) (LIST X (LIST 'QUOTE X)). L'argument étant lui-même un programme (c'est-à-dire une expression Lisp), on a ici l'exemple d'un programme manipulant un programme.

Voyez dans le chapitre 3 la notion de fonction anonyme, ainsi que l'annexe 1 pour les notions relatives à l'application d'une fonction et aux opérateurs LIST et QUOTE (ou à l'abréviation de QUOTE par le caractère macro apostrophe - ' -).

Home    Previous    Up    Next
contact
site map
Last update : 27/11/2001