Programming Paradigms

Ce document présente les principaux paradigmes de programmation ainsi qu'une introduction détaillée au langage LISP, un langage historique et fondamental en intelligence artificielle. Il s'adresse aux étudiants en informatique souhaitant comprendre les différences entre paradigmes et maîtriser les concepts essentiels de LISP, notamment la manipulation des listes, la définition de fonctions et la récursion.

Les paradigmes de programmation

Le paradigme fonctionnel

La programmation fonctionnelle désigne une famille de langages qui accordent un rôle central aux fonctions. On peut raisonner en programmation fonctionnelle comme en mathématiques, notamment en utilisant des démonstrations par récurrence et des analyses récursives de complexité. Les fonctions récursives sont au cœur de ce paradigme.

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

Le paradigme procédural (ou impératif)

Le paradigme procédural 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 central pour les calculs répétitifs, la récursivité y est rarement optimisée. La programmation impérative considère un programme comme une suite d'instructions pilotant un ordinateur.

Exemples historiques : Fortran (1967), Pascal (1970-1990). Aujourd'hui, C est le représentant majoritaire de ce paradigme.

Le paradigme à objets

Ce paradigme s'appuie sur la notion de classe et d'objet. 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, dont les méthodes peuvent être fonctionnelles ou impératives. Ce paradigme favorise la réutilisation et l'extensibilité du logiciel.

Exemples : Smalltalk (1970), popularisé avec Java et C++ dans les années 1990.

Introduction au langage LISP

Conçu en 1958 par J. McCarthy, LISP est l'un des plus anciens langages de programmation, longtemps utilisé en intelligence artificielle. Il se distingue par sa capacité à manipuler des symboles et par une syntaxe très simple basée uniquement sur la structure de listes.

Avantages de LISP

• Simplicité de la syntaxe, reposant uniquement sur les listes.
• Puissance du langage, notamment l'équivalence complète entre données et programmes.
• Interactivité grâce à un interpréteur principalement utilisé.

Les objets de base en LISP

L'atome

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

• Un nombre (exemples : 126, -54)
• Un symbole, c'est-à-dire une séquence non vide de caractères (exemples : Le-Lisp, var, 1+x/y)

Les symboles servent à désigner les différents objets, qu'ils soient données ou fonctions.

La liste

La structure de base de LISP est la liste, une séquence ordonnée, éventuellement vide, d'atomes ou de listes, délimitée par des parenthèses.

Exemples :

• (* 3 7)
• (+ (* 3 7) (- 8 4) 10)

La liste vide, notée (), joue un rôle très important en LISP.

Expressions élémentaires et évaluation

Une expression élémentaire en LISP est une S-expression, qui est soit un atome, soit une liste.

Chaque S-expression a une valeur, notée VALEUR<s>. L'interpréteur LISP évalue une S-expression pour déterminer sa valeur.

Évaluation des atomes

• La valeur d'un nombre est lui-même.
• La valeur d'un symbole peut être :
• Prédéfinie et non modifiable (exemples : t et nil, où t vaut lui-même et nil vaut la liste vide ( )).
• Définie et modifiée dynamiquement, dans le cas d'une variable.

Évaluation des listes

Une liste (<s0> ... <sn>) est évaluée ainsi :

• <s0> est un symbole désignant une fonction, il n'est pas évalué.
• Les sous-expressions <s1> à <sn> sont évaluées pour obtenir VALEUR<s1> ... VALEUR<sn>.
• La fonction associée à <s0> est appliquée aux arguments VALEUR<s1> ... VALEUR<sn>.
• La valeur de la liste est le résultat de cette application.

Exemple d'erreur

Une parenthèse ouvrante doit toujours être suivie d'un nom de fonction :

(1 2 3 4)

Cette expression provoque une erreur car 1 n'est pas une fonction.

Éviter l'évaluation d'une S-expression

Pour désigner une S-expression sans l'évaluer, on utilise la fonction quote :

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

Abbréviation : '(1 2 3 4)

Définition de fonctions

Un programme LISP est une fonction ou un ensemble de fonctions, définies avec la primitive de.

Exemple :

(de **(z) (* z z))

Cette expression définit la fonction ** qui calcule le carré de z. La valeur retournée est le nom de la fonction définie.

Récursion

Une fonction est récursive si son nom figure dans sa propre définition.

Exemple 1 : Factorielle

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

Exemple 2 : Suite de Fibonacci

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

Fonctionnement de l'interpréteur LISP

Le rôle de l'interpréteur est d'évaluer successivement des S-expressions selon le processus :

1. Lire une S-expression
2. Évaluer la S-expression
3. Imprimer la valeur obtenue

Une session LISP consiste à faire évaluer plusieurs expressions respectant cette syntaxe simple.

Gestion des symboles fonctions et variables

LISP ne distingue pas lexicalement les symboles de fonctions et de variables, ce qui permet notamment de définir des fonctions récursives.

Deux classes de systèmes LISP existent :

• Systèmes bi-valents : chaque symbole peut avoir deux valeurs, une pour la variable (C-val) et une pour la fonction (F-val). Exemple : Le-Lisp, Mac-Lisp.
• Systèmes mono-valents : un symbole ne peut avoir qu'une seule valeur (C-val). L'évaluation d'une fonction donne directement sa définition.

Exemple d'affectation dans un système bi-valent

(setq a 3)

Cela met 3 dans la C-valeur de a. Les symboles comme +, -, * ont une F-valeur prédéfinie.

Types de fonctions en LISP

• SUBR : fonction prédéfinie en langage machine qui évalue ses arguments.
• EXPR ou LAMBDA : fonction écrite en LISP qui évalue ses arguments.
• FSUBR : fonction prédéfinie en langage machine qui n'évalue pas tous ses arguments (exemple : setq).

On peut obtenir le type d'une fonction avec la primitive typefn :

?(typefn 'fact) = expr
?(typefn 'car) = subr
?(typefn '*) = nsubr

Constructeurs et sélecteurs de listes

cons

Ajoute un atome ou une liste en tête d'une liste.

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

car

Retourne le premier élément (tête) d'une liste.

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

cdr

Retourne la liste sans son premier élément.

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

Accès aux éléments suivants

• cadr : second élément
• caddr : troisième élément

Exemple :

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

Autres combinaisons

?(cdadr '(a (b c) d)) = (c d)
?(cddr '(a b c d)) = (c d)
?(cddar '((a b c d) (e) f)) = (c d)
?(cadar '((a b c) d e)) = b

append

Concatène plusieurs listes.

?(append '(ceci est) '(un support de cours) '(en Lisp)) = (ceci est un support de cours en Lisp)

list

Retourne une liste composée des éléments donnés.

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

length

Retourne le nombre d'éléments de premier niveau d'une liste, ou 0 si l'argument est un atome.

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

Prédicats

Les fonctions prédicats évaluent toujours leurs arguments et retournent nil si le prédicat est faux. Si vrai, la valeur peut varier selon le système, souvent t est utilisé pour vrai.

• (atom <s>) : retourne t si VALEUR<s> est un atome, sinon () si c'est une liste non vide.
• (null <s>) : retourne t si VALEUR<s> est la liste vide (), sinon ()
• (eq <s1> <s2>) : teste l'identité de deux atomes, retourne t si identiques, sinon ()
• (symbolp <s>) : retourne t si s est un symbole, sinon nil
• (constantp <s>) : retourne t si s est une constante (nombre, chaîne, ou nil), sinon nil
• (consp <s>) : retourne t si s est une liste non vide, sinon nil
• (listp <s>) : retourne t si s est une liste, sinon nil

Fonctions logiques

Les fonctions logiques retournent une valeur vraie ou fausse selon les valeurs logiques de leurs arguments. L'évaluation s'arrête dès qu'un résultat est déterminé pour éviter des calculs inutiles.

• (or <s1> ... <sN>) : retourne la valeur du premier argument différent de nil, sinon nil. Évaluation arrêtée dès qu'un argument vrai est trouvé.
• (and <s1> ... <sN>) : retourne la valeur du dernier argument si tous sont vrais, sinon nil.

Séquenceurs

(progn <s1> ... <sN>) évalue séquentiellement ses arguments et retourne la valeur du dernier.

Structures conditionnelles

IF

(IF <s1> <s2> <s3>) : si VALEUR<s1> est différente de nil, retourne VALEUR<s2>, sinon évalue et retourne VALEUR<s3>.

Exemples :

?(IF t 1 2) = 1
?(IF nil 1 2) = 2
?(IF nil 1) = nil

WHEN et UNLESS

• (WHEN <test> <s1> ... <sN>) : si test est vrai, évalue toutes les expressions s1 à sN.
• (UNLESS <test> <s1> ... <sN>) : si test est faux, évalue toutes les expressions s1 à sN.

COND

La fonction conditionnelle la plus complète. Chaque clause est une liste (<ss> <s1> ... <sN>) où <ss> est une expression test. COND sélectionne la première clause dont VALEUR<ss> est différente de nil. Si le corps est vide, retourne VALEUR<ss>, sinon évalue les expressions du corps et retourne la valeur de la dernière.

Exemple de fonction utilisant COND

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

Fonctions d'entrée/sortie

print

(print <expr>) évalue son argument, affiche la valeur obtenue et la retourne.

?(setq a 3) = 3
?(print a)
a
= 3

Souvent utilisé avec des chaînes de caractères :

?(print 'salut)
salut
= salut

?(setq salut "Bonjour")
= Bonjour

?(print salut)
Bonjour
= Bonjour

L'usage de print est justifié lorsque le résultat de l'évaluation n'est pas automatiquement affiché.

read

(read) est une fonction sans argument qui retourne la réponse de l'utilisateur sans l'évaluer. Le système invite l'utilisateur à saisir une expression.

?(setq x (read))
? 5 ; réponse de l'utilisateur
= 5

Glossaire des termes clés

• Atome : élément de base en LISP, soit un nombre, soit un 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, soit un atome, soit une liste.
• VALEUR<s> : valeur d'une S-expression s après évaluation.
• cons : fonction ajoutant un élément en tête d'une liste.
• car : fonction retournant le premier élément d'une liste.
• cdr : fonction retournant la liste sans son premier élément.
• Récursion : définition d'une fonction qui s'appelle elle-même.
• SUBR : fonction prédéfinie en langage machine évaluant ses arguments.
• FSUBR : fonction prédéfinie en langage machine n'évaluant pas tous ses arguments.
• EXPR/LAMBDA : fonction écrite en LISP évaluant ses arguments.
• Prédicat : fonction retournant t ou nil selon une condition.
• IF, COND, WHEN, UNLESS : structures conditionnelles en LISP.
• print : fonction d'affichage et de retour de valeur.
• read : fonction d'entrée interactive.

Points clés à retenir

• Les paradigmes fonctionnel, procédural et à objets proposent des approches différentes de la programmation.
• LISP est un langage symbolique basé sur les listes, avec une syntaxe simple et une évaluation basée sur les S-expressions.
• La distinction entre symboles de fonctions et variables est gérée différemment selon les systèmes LISP (bi-valents ou mono-valents).
• Les fonctions récursives sont fondamentales en LISP, permettant de définir des calculs complexes comme la factorielle ou la suite de Fibonacci.
• Les fonctions de manipulation de listes (cons, car, cdr, append, list) sont essentielles pour travailler efficacement en LISP.
• Les structures conditionnelles (IF, COND) et les fonctions logiques (and, or) permettent de contrôler le flux d'exécution.
• Les fonctions d'entrée/sortie (print, read) facilitent l'interactivité avec l'utilisateur.