Programming Paradigms and Lisp Language

Ce document présente les paradigmes de programmation, avec un focus particulier sur le langage Lisp. Il s’adresse aux étudiants en informatique souhaitant comprendre la programmation fonctionnelle, maîtriser les primitives de Lisp, écrire des fonctions récursives, et appliquer Lisp dans des contextes d’intelligence artificielle.

Les Paradigmes de Programmation

Le paradigme fonctionnel

La programmation fonctionnelle est une famille de langages où les fonctions occupent une place centrale. Elle permet de raisonner comme en mathématiques, notamment par des démonstrations par récurrence et des analyses récursives de complexité. La récursivité est au cœur de ce paradigme.

Exemples de langages fonctionnels : Haskell, Standard ML, Ocaml.

Le paradigme procédural

Le paradigme procédural, ou impératif, est le plus ancien. Il met l’accent sur l’appel de procédures pour effectuer un calcul séquentiel. L’itération est le mécanisme principal pour les calculs répétitifs, la récursivité y étant rarement optimisée. Le programme est vu comme une suite d’instructions pilotant l’ordinateur.

Exemples : Fortran, Pascal, C.

Le paradigme à objets

Ce paradigme repose sur les classes et objets. Les objets possèdent des méthodes, qui sont des procédures associées à l’objet et appelées par messages. Le calcul est décentralisé dans les objets, avec des méthodes fonctionnelles ou impératives. Il favorise la réutilisation et l’extensibilité du logiciel.

Exemples : Smalltalk, Java, C++.

Introduction au langage Lisp

Lisp, créé en 1958 par John McCarthy, est l’un des plus anciens langages de programmation, historiquement lié à la recherche en intelligence artificielle. Il est conçu pour la manipulation symbolique et se distingue par :

• Une syntaxe simple basée uniquement sur des listes parenthésées.
• Une équivalence complète entre données et programmes.
• Une interactivité grâce à son interprétation.

Quelques versions importantes :

• 1960 : Lisp 1.5
• 1966 : MACLISP
• 1967-1975 : INTERLISP, SCHEME
• 1984 : LE_LISP, Common LISP
• 1985-1986 : EULISP, AutoLISP

Caractéristiques :

• Syntaxe simple mais usage intensif des parenthèses.
• Récursivité très utilisée.
• Typage dynamique.
• Pas de distinction entre données et programmes.
• Langage interprété.

Les objets de base en Lisp

Atomes

L’objet de base est l’atome, qui peut être :

• Un nombre (exemple : 126, -54)
• Un symbole, toute séquence non vide de caractères (exemple : Le-Lisp, var, 1+x/y)

Les symboles désignent les objets, qu’ils soient données ou fonctions.

Listes

Une liste est une séquence ordonnée d’atomes ou de listes, délimitée par des parenthèses.

Exemples :

• (* 3 7)
• (+ (* 3 7) (- 8 4) 10)
• Liste vide : () qui correspond à NIL

S-expressions

Les expressions élémentaires sont les S-expressions, qui peuvent être :

• Atomes
• Listes
• Paires pointées (exemple : (A.B))

Évaluation des S-expressions

Chaque S-expression a une valeur. L’évaluateur Lisp procède ainsi :

• Si c’est un atome :
• Si c’est un nombre, sa valeur est lui-même.
• Si c’est un symbole :
• Soit une constante prédéfinie (t ou nil)
• Soit une variable dont la valeur est définie dynamiquement.
• Si c’est une liste (<s0> <s1> ... <sn>) :
• <s0> est un symbole désignant une fonction (non évalué).
• Les sous-expressions <s1> ... <sn> sont évaluées.
• La fonction désignée par <s0> est appliquée aux valeurs des arguments.

Exemple :

? (quote (1 2 3 4))
= (1 2 3 4)
? '(1 2 3 4)
= (1 2 3 4)

Définition de fonctions et récursivité

Les programmes Lisp sont constitués de fonctions définies avec la primitive defun.

Exemple de définition d’une fonction :

(defun carre (z)
  (* z z))

La récursivité est une notion clé : une fonction est récursive si elle s’appelle elle-même.

Exemple 1 : Factorielle

(defun fact (n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

Exemple 2 : Suite de Fibonacci

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))

Fonctions de base et primitives Lisp

Opérations arithmétiques

• (+ ... ...) addition
• (- ... ...) soustraction
• (* ... ...) multiplication
• (/ ... ...) division

Manipulation des listes

• (quote <expression>) : empêche l’évaluation, retourne l’expression telle quelle.
• (car <liste>) : retourne le premier élément d’une liste.
• (cdr <liste>) : retourne la liste privée de son premier élément.
• (cons <élément> <liste>) : ajoute un élément en tête d’une liste.
• (append <liste1> <liste2> ...) : concatène plusieurs listes.

Exemple :

? (cons 2 '(3 4))
= (2 3 4)
? (car '(1 2 3))
= 1
? (cdr '(1 2 3))
= (2 3)
? (append '(a b) '(c d))
= (a b c d)

Fonctions prédicats

• (atom <s>) : retourne t si s est un atome, nil sinon.
• (null <s>) : retourne t si s est la liste vide () (nil), nil sinon.
• (eq <s1> <s2>) : teste l’identité de deux atomes.
• (equal <s1> <s2>) : teste l’égalité de deux S-expressions (atomes ou listes).
• (numberp <s>) : teste si s est un nombre.
• Comparateurs : =, <, >, <=, >=

Contrôle de flux

• (if <condition> <alors> <sinon>) : structure conditionnelle simple.
• (cond (<test1> <action1>) ... (t <action par défaut>)) : structure conditionnelle multiple.
• (when <test> <expr1> ...) : exécute les expressions si test vrai.
• (unless <test> <expr1> ...) : exécute les expressions si test faux.

Exemple d’utilisation de cond :

(defun test (x y)
  (cond ((> x y) 'sup)
        ((= x y) 'egal)
        (t 'inf)))

? (test 12 5)
= sup
? (test 5 8)
= inf

Itération et programmation impérative en Lisp

Bien que Lisp soit fonctionnel, il propose des constructions pour l’itération :

• prog : structure impérative avec étiquettes et sauts (go, return).
• while : boucle tant que la condition est vraie.

Exemple de fonction itérative calculant la puissance :

(defun puissance (n p)
  (prog (resultat)
    (setq resultat 1)
    depart
      (setq resultat (* n resultat))
      (setq p (- p 1))
      (if (= p 0)
          (return resultat)
          (go depart))))

Exemple d’inverse d’une liste avec while :

(defun reverse (l)
  (let ((resultat ()))
    (while l
      (setq resultat (cons (car l) resultat))
      (setq l (cdr l)))
    resultat))

Fonctions anonymes et fonctionnelles d’ordre supérieur

Les fonctions anonymes sont définies avec lambda :

(lambda (x) (+ x x))
(lambda (x y) (+ (* 2 x) (* 3 y)))

Exemples d’utilisation :

? ((lambda (x y) (* x y)) 2 3)
= 6

? (setq a '(lambda (x y) (* x y)))
= (lambda (x y) (* x y))

? (apply a '(2 3))
= 6

Fonctionnelles importantes :

• apply : applique une fonction à une liste d’arguments.
• mapcar : applique une fonction à chaque élément d’une liste et retourne la liste des résultats.

Exemples :

? (apply '+ '(2 3 4))
= 9

? (mapcar '1+ '(1 2 3))
= (2 3 4)

? (mapcar '+ '(1 2 3) '(4 5 6))
= (5 7 9)

? (mapcar (lambda (x y) (+ (* 2 x) (* 3 y))) '(1 2 3) '(4 5 6))
= (14 19 24)

Filtres et fonctions génériques

Les fonctions petits et grands sélectionnent respectivement les éléments plus petits ou plus grands qu’un élément donné dans une liste. Elles peuvent être généralisées en une fonction filtre prenant une fonction de test en argument :

(defun filtre (test l)
  (cond ((null l) ())
        ((funcall test (car l)) (cons (car l) (filtre test (cdr l))))
        (t (filtre test (cdr l)))))

Exemple :

? (filtre (lambda (x) (>= x 9)) '(15 7 12 3))
= (15 12)

Les fonctions petits et grands s’expriment alors :

(defun petits (a l)
  (filtre (lambda (x) (< x a)) l))

(defun grands (a l)
  (filtre (lambda (x) (>= x a)) l))

Opérateur LET

let permet de créer des variables locales dans un environnement provisoire :

(let ((var1 s1) ... (varn sn))
  expr1 ... exprn)

Il évalue successivement s1...sn, lie var1...varn à ces valeurs, évalue expr1...exprn, délient les variables, et retourne la valeur de exprn.

Exemple :

? (setq x 2 y 4)
= 4
? (let ((x (- x y)) (y (+ x y))) (* x y))
= -12

Les liaisons se font en parallèle, la deuxième liaison utilise la valeur de x avant l’appel de let.

Gestion des symboles et valeurs

Il existe deux classes de systèmes Lisp :

• Systèmes bi-valents : chaque symbole a une valeur variable (C-val) et une valeur fonction (F-val).
• Systèmes mono-valents : chaque symbole ne reçoit qu’une seule valeur (C-val).

Exemple d’affectation :

(setq a 3)

Dans les systèmes bi-valents, on peut utiliser getdef pour obtenir la définition d’une fonction :

? (getdef 'fib)

Fonctions de modification et itératives

• nextl v : retourne (car v) et affecte à v la valeur (cdr v).
• newl v e : affecte à v (cons e v) et retourne cette valeur.
• while (test) expr1 ... exprn : boucle tant que test est vrai.

Exemple d’inverse itératif :

(defun reverse (l)
  (let ((resultat ()))
    (while l
      (setq resultat (cons (car l) resultat))
      (setq l (cdr l)))
    resultat))

Fonctions avancées et macros

Les macros Lisp s’évaluent en deux étapes : expansion en une forme Lisp évaluable, puis évaluation de cette forme.

Exemple de macro si traduite en cond :

(defmacro si (test vrai faux)
  `(cond
     (,test ,vrai)
     (t ,faux)))

Le caractère backquote ` construit une liste sans évaluer ses éléments, annulé par la virgule , ou ,@ :

? `(a b c d)
= (a b c d)

? (setq a `(toto riri))
= (toto riri)

? `(a b ,a a)
= (a b (toto riri) a)

? `(a b ,@a a)
= (a b toto riri a)

Exemples de fonctions sur les listes

• (length l) : retourne le nombre d’éléments de la liste.
• (nth n l) : retourne l’élément à la position n.
• (append l1 l2 ...) : concatène les listes.
• (list s1 ... sn) : crée une liste des éléments.

Exemple :

? (length '(a (b c) d))
= 3

? (caddr '(a b c))
= c

Fonctions récursives sur les ensembles

• (ensemble l) : teste si une liste est un ensemble (sans doublons).
• (inclus l1 l2) : teste si tous les éléments de l1 sont dans l2.
• (compare l1 l2) : teste l’égalité de deux ensembles.
• (unique l) : transforme une liste en ensemble.
• (union l1 l2) : crée un ensemble union des éléments de l1 et l2.
• (inter l1 l2) : crée un ensemble intersection.

Glossaire des termes clés

• Atome : élément de base en Lisp, nombre ou symbole.
• Liste : séquence ordonnée d’atomes ou de listes, délimitée par des parenthèses.
• S-expression : expression élémentaire en Lisp, atome, liste ou paire pointée.
• Cons : constructeur de listes, ajoute un élément en tête.
• Car : sélecteur, retourne le premier élément d’une liste.
• Cdr : sélecteur, retourne la liste privée de son premier élément.
• Lambda : fonction anonyme.
• Mapcar : fonctionnelle appliquant une fonction à chaque élément d’une liste.
• Apply : applique une fonction à une liste d’arguments.
• Let : crée des variables locales dans un environnement temporaire.
• Prog : structure impérative avec étiquettes et sauts.
• Macro : fonction évaluée en deux étapes, expansion puis exécution.
• Eval : évalue explicitement une expression.
• Trace : permet de suivre l’exécution d’une fonction récursive.

Points clés à retenir

• La programmation fonctionnelle place la fonction au centre du calcul, avec la récursivité comme mécanisme fondamental.
• Lisp est un langage fonctionnel historique, caractérisé par sa syntaxe basée sur les listes et l’équivalence entre données et programmes.
• Les S-expressions sont évaluées selon leur nature : atome ou liste, avec une fonction appliquée au premier élément d’une liste.
• Les fonctions récursives et itératives sont toutes deux possibles en Lisp, avec des constructions adaptées.
• Les fonctions anonymes (lambda) et fonctionnelles d’ordre supérieur (apply, mapcar) permettent une programmation puissante et flexible.
• Les macros permettent d’étendre le langage Lisp en créant des constructions personnalisées.
• L’opérateur let facilite la gestion de variables locales et d’environnements temporaires.
• Les fonctions prédicats et opérateurs de manipulation de listes sont essentiels pour traiter les structures de données Lisp.