Paradigmes de programmation et Lisp pour IA

Ce matériel couvre les paradigmes de programmation, avec un focus particulier sur le langage Lisp et son utilisation en intelligence artificielle (IA). Il s'adresse aux étudiants en informatique souhaitant comprendre la programmation fonctionnelle, maîtriser Lisp, et appliquer ce langage dans des contextes d'IA.

Les paradigmes de programmation

Le paradigme fonctionnel

La programmation fonctionnelle est une famille de langages qui mettent les fonctions au centre de la programmation. On raisonne comme en mathématiques, avec des démonstrations par récurrence et des analyses récursives. La récursivité est au cœur de ce paradigme.

Exemples : Haskell, Standard ML, Ocaml.

Le paradigme procédural

Le paradigme procédural, ou impératif, est le plus ancien. Il repose sur l'appel de procédures pour exécuter des calculs séquentiels. L'itération est le mécanisme central, la récursivité y est rarement optimisée. Un programme est vu comme une suite d'instructions pilotant l'ordinateur.

Exemples : Fortran, Pascal, C.

Le paradigme à objets

Ce paradigme s'appuie sur les classes et objets. Les objets possèdent des méthodes, qui sont des procédures destinées à être transmises sous forme de 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++.

Lisp : Langage de programmation pour l'IA

Introduction à Lisp

Conçu en 1958 par John McCarthy, Lisp est un des plus anciens langages de programmation, historiquement lié à la recherche en intelligence artificielle. Il est spécialement adapté à la manipulation des symboles.

Avantages :

• Simplicité de la syntaxe reposant sur la structure de liste.
• Équivalence complète entre données et programmes.
• Interactivité grâce à son interprétation.

Caractéristiques principales

• Langage fonctionnel et traitement symbolique.
• Code formé de listes parenthésées.
• Syntaxe simple mais avec de nombreuses parenthèses.
• Utilisation intensive de la récursivité.
• Typage dynamique des données.
• Pas de distinction entre données et programmes.
• Langage interprété.

Objets de base : Atomes et Listes

L’objet de base de Lisp est l’atome, qui peut être un nombre (ex. 126, -54) ou un symbole (ex. Le-Lisp, var, 1+x/y). Les symboles désignent les objets (données ou fonctions).

La structure de base est la liste, 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)
• () représente la liste vide, aussi appelée NIL.

Expressions élémentaires : S-expressions

Les S-expressions sont les unités syntaxiques de Lisp, qui peuvent être :

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

Évaluation des S-expressions

Chaque S-expression a une valeur. L’évaluateur Lisp agit ainsi :

• Si c’est un atome :
• La valeur d’un nombre est lui-même.
• La valeur d’un symbole est soit prédéfinie (ex. t, nil), soit une variable dynamique.
• Si c’est une liste :
• Le premier élément est un symbole désignant une fonction (non évalué).
• Les autres éléments sont évalués.
• La fonction est appliquée aux valeurs des arguments.

Exemple d'utilisation de quote pour empêcher l’évaluation :

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

Définition de fonctions

On définit une fonction avec la primitive defun :

? (defun carré (z) (* z z))
= carré

Récursivité

Une fonction est récursive si elle s'appelle elle-même dans sa définition.

Exemple : Factorielle

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

Exemple : Suite de Fibonacci

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

Cycle d'exécution de Lisp

L’interpréteur Lisp suit la boucle :

READ – EVAL – PRINT

Il lit une S-expression, l’évalue, puis imprime la valeur obtenue.

Symboles et valeurs

Lisp ne distingue pas lexicalement les symboles de fonctions et de variables. Deux types de systèmes existent :

• Systèmes bi-valents : un symbole peut avoir une valeur variable (C-val) et une valeur fonction (F-val).
• Systèmes mono-valents : un symbole ne peut avoir qu’une seule valeur (C-val).

Types de fonctions

• SUBR : fonction prédéfinie en langage machine évaluant ses arguments.
• EXPR ou LAMBDA : fonction écrite en Lisp évaluant ses arguments.
• FSUBR : fonction prédéfinie n’évaluant pas tous ses arguments (ex. setq).

Fonctions de base

• Addition : (+ … …)
• Soustraction : (- … …)
• Multiplication : (* … …)
• Division : (/ … …)

Fonctions de manipulation de 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 d’utilisation de car, cdr, cons

? (car '(1 2 3))
= 1

? (cdr '(1 2 3))
= (2 3)

? (cons 2 '(3 4))
= (2 3 4)

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 sinon.
• (eq <s1> <s2>) : teste l'identité de deux atomes.
• (equal <s1> <s2>) : teste l'égalité de deux S-expressions (listes ou atomes).
• (symbolp <s>) : teste si s est un symbole.
• (numberp <s>) : teste si s est un nombre.

Fonctions logiques

• (or <s1> … <sn>) : retourne la première valeur vraie, nil sinon. Évaluation courte-circuitée.
• (and <s1> … <sn>) : retourne la dernière valeur si toutes vraies, nil sinon. Évaluation courte-circuitée.

Structures conditionnelles

if :

(if (condition)
    (action-si-vrai)
    (action-si-faux))

Exemples :

? (if t 1 2)
= 1

? (if nil 1 2)
= 2

cond permet de tester plusieurs conditions :

(cond
  ((test1) (action1))
  ((test2) (action2))
  (t (action-par-defaut)))

Exemple :

(defun test (x y)
  (cond
    ((> x y) 'sup)
    ((= x y) 'egal)
    (t 'inf)))
? (test 12 5)
= sup
? (test 5 8)
= inf

Fonctions itératives

Les fonctions itératives utilisent des primitives comme prog, go, return et while.

Exemple : puissance itérative

(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 : dernier élément d’une liste

(defun dernier (liste)
  (prog ()
    encore
    (cond
      ((null (cdr liste)) (return (car liste)))
      (t (setq liste (cdr liste))))
    (go encore)))

Exemple : inverse itératif

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

Fonctions anonymes : lambda

Une fonction anonyme est définie avec lambda, qui crée une fonction sans nom utilisable dans la S-expression où elle est définie.

Exemples :

? ((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 : APPLY et MAPCAR

apply applique une fonction à une liste d’arguments :

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

? (apply 'append '((a b) (c d)))
= (a b c d)

mapcar applique une fonction aux éléments successifs d’une liste et retourne la liste des résultats :

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

? (mapcar 'car '((a b) (c) ((d e) f)))
= (a c (d e))

Avec plusieurs listes :

? (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 généraux

On peut définir une fonction générale de filtrage qui prend une fonction test et une liste, et retourne les éléments qui satisfont le test :

(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 peuvent s’écrire avec filtre :

(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 et d’évaluer des expressions dans un environnement provisoire :

(let ((x 2) (y 4))
  (* x y))
= 8

Les liaisons sont faites en parallèle, donc la valeur de y dans l'exemple est calculée avec la valeur initiale de x.

Manipulation avancée de listes

• length : retourne le nombre d'éléments de premier niveau d'une liste.
• nth : retourne l'élément à la nième position.
• append : concatène des listes.
• cons : ajoute un élément en tête d’une liste.
• reverse : inverse une liste.

Exemple : extraire le troisième élément d’une liste

(caddr '(a b c)) ; équivaut à (car (cdr (cdr '(a b c))))
= c

Fonctions itératives avec WHILE

Exemple : afficher un décompte

(defun decompte (n)
  (while (> n 0)
    (print n)
    (setq n (- n 1))))

Gestion des propriétés des symboles

Chaque symbole possède une P-liste, une liste de propriétés sous forme de paires (propriété, valeur).

Fonctions associées :

• (plist symb) : retourne la P-liste d’un symbole.
• (putprop symb val prop) : associe la valeur val à la propriété prop dans la P-liste de symb.
• (getprop symb prop) : retourne la valeur de la propriété prop dans la P-liste de symb.
• (remprop symb prop) : supprime la propriété prop de la P-liste de symb.

Évaluation explicite avec EVAL

La fonction eval force l’évaluation d’une expression :

? (setq a '(* 2 4))
= (* 2 4)

? (eval a)
= 8

Fonctions d'entrée/sortie

• print : évalue et affiche une expression.
• read : lit une expression entrée par l’utilisateur sans l’évaluer.
• princh : affiche un caractère un certain nombre de fois.
• terpri : effectue un saut de ligne.

Débogage

• trace : affiche les appels d’une fonction et les valeurs des variables.
• untrace : annule le trace.
• step : évaluation pas à pas d’une expression.

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 parenthèses.
• S-expression : expression symbolique, atome ou liste.
• Récursivité : fonction qui s’appelle elle-même.
• Lambda : fonction anonyme définie sans nom.
• Cons : constructeur de liste, ajoute un élément en tête.
• Car : retourne le premier élément d’une liste.
• Cdr : retourne la liste privée de son premier élément.
• Eval : fonction qui évalue une expression.
• Let : crée des variables locales dans un environnement temporaire.
• Mapcar : fonctionnelle appliquant une fonction à chaque élément d’une liste.
• Filtre : fonction générale pour sélectionner des éléments selon un test.
• Prog, Go, Return : primitives pour la programmation itérative.
• Trace : outil de débogage pour suivre les appels de fonction.
• P-liste : liste de propriétés attachées à un symbole.

Points clés à retenir

• Le paradigme fonctionnel privilégie les fonctions et la récursivité, contrairement aux paradigmes procédural et objet.
• Lisp est un langage fonctionnel ancien, adapté à la manipulation symbolique et à l’IA.
• Les S-expressions sont la base syntaxique de Lisp, composées d’atomes et de listes.
• L’évaluation Lisp distingue atomes (valeur directe) et listes (application de fonction).
• Les fonctions récursives sont centrales, avec des exemples classiques comme la factorielle et Fibonacci.
• Les fonctions anonymes (lambda) et fonctionnelles (apply, mapcar) permettent une programmation flexible.
• Les structures conditionnelles (if, cond) et itératives (prog, while) sont essentielles pour le contrôle de flux.
• Les fonctions de manipulation de listes (car, cdr, cons, append) sont fondamentales.
• Les filtres généraux facilitent la sélection d’éléments selon des critères dynamiques.
• Les outils de débogage (trace, step) et les fonctions d’entrée/sortie (print, read) améliorent l’interactivité.