Cours 7

Ce cours s'adresse aux étudiants en informatique ou en programmation souhaitant approfondir leur compréhension des listes d'association en Common Lisp, ainsi que la définition et la gestion des fonctions, notamment la gestion avancée des paramètres. Il couvre les fonctions d'application fonctionnelles, les listes d'association, les différents types d'égalités, ainsi que les diverses formes de paramètres dans les fonctions Lisp.

Listes d'association

Une liste d'association (ou alist) est une liste dont les éléments sont des paires (cons). Chaque paire associe une clé (stockée dans le car) à une valeur (stockée dans le cdr). Cette structure sert de table indexée simple.

Bien que peu efficace pour les grandes tables, elle est très pratique pour des petites collections grâce aux fonctions intégrées de Common Lisp.

La fonction fondamentale pour manipuler une liste d'association est assoc. Elle prend une clé et une liste d'association, et retourne la première paire dont la clé correspond à celle donnée, ou nil si aucune correspondance n'est trouvée.

(assoc 'oeuf '((eau . water) (oeuf . egg) (sel . salt)))
; Résultat : (OEUF . EGG)

Exemple avec une liste plus complexe :

(defparameter *languages*
  '((symbolic . (lisp ml haskell))
    (imperative . (lisp c pascal cobol fortran))
    (object-oriented . (lisp c++ java))
    (numeric . (lisp fortran))))

(assoc 'imperative *languages*)
; Résultat : (IMPERATIVE LISP C PASCAL COBOL FORTRAN)

(cdr (assoc 'imperative *languages*))
; Résultat : (LISP C PASCAL COBOL FORTRAN)

(assoc 'postfix *languages*)
; Résultat : NIL

Remarque : Une paire de la forme (a . (b ...)) est équivalente à la liste (a b ...). La fonction print affiche toujours la forme liste, expliquant la différence d'affichage.

L'idiome (cdr (assoc ...)) permet d'obtenir la valeur associée à une clé, même si la clé n'existe pas (car (cdr nil) vaut nil).

Par défaut, assoc utilise le prédicat eql pour tester l'égalité des clés. On peut spécifier un autre prédicat avec l'argument mot-clé :test. Exemple :

(assoc "oeuf"
       '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : NIL

(assoc "oeuf"
       '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
       :test #'string-equal)
; Résultat : ("oeuf" . "egg")

On peut aussi utiliser :test-not pour tester la négation, ou :key pour appliquer une fonction à la clé avant le test :

(assoc "oe"
       '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt"))
       :test #'string-equal :key (lambda (s) (subseq s 0 2)))
; Résultat : ("oeuf" . "egg")

Les fonctions assoc-if et assoc-if-not sont similaires à assoc, mais prennent un prédicat appliqué à la clé et retournent la première paire pour laquelle le prédicat (ou sa négation) est vrai. Exemple :

(assoc-if
   #'(lambda (s) (string-equal (subseq s 0 2) "oe"))
   '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : ("oeuf" . "egg")

(assoc-if-not
   #'(lambda (s) (> (length s) 3))
   '(("eau" . "water") ("oeuf" . "egg") ("sel" . "salt")))
; Résultat : ("eau" . "water")

Pour ajouter un élément en tête d'une liste d'association, on peut utiliser cons ou push. La fonction acons crée une paire et l'ajoute simultanément :

(acons 'a 1 '((b . 2) (c . 3)))
; Résultat : ((A . 1) (B . 2) (C . 3))

La fonction pairlis construit une liste d'association à partir d'une liste de clés et d'une liste de valeurs.

Pour supprimer une paire, on utilise remove, remove-if, remove-if-not ou leurs versions destructives delete, delete-if, delete-if-not.

Pour modifier la valeur associée à une clé, on utilise l'idiome :

(setf (cdr (assoc clé alist)) nouvelle-valeur)

Les fonctions rassoc, rassoc-if et rassoc-if-not fonctionnent comme assoc et ses variantes, mais en inversant les rôles clé-valeur.

Enfin, comme une liste d'association est une liste, on peut appliquer toutes les fonctions sur listes et séquences (comme find, member, position) aux listes d'association. Pour copier une liste d'association, on utilise copy-alist.

Définition de fonctions globales

En Common Lisp, la majorité des fonctions sont globales, accessibles partout par leur nom, qui est un symbole distinct de celui des variables (espaces de noms différents).

La macro principale pour définir une fonction globale est defun :

(defun nom lambda-liste
  expression-1
  ...
  expression-n)

Le corps de la fonction est un progn implicite : la valeur de la dernière expression est la valeur retournée par la fonction.

Exemple simple :

(defparameter *count* 0)

(defun next ()
  (incf *count*)
  (1- *count*))

(next)
; Résultat : 0

(next)
; Résultat : 1

Une version plus idiomatique :

(defun next ()
  (prog1 *count* (incf *count*)))

(next)
; Résultat : 0

(next)
; Résultat : 1

On peut aussi définir une fonction globale à l'intérieur d'une autre expression, ce qui crée une fermeture (closure) :

(let ((count -1))
  (defun next ()
    (incf count)))

(next)
; Résultat : 0

(next)
; Résultat : 1

La macro defun modifie la fonction associée à un symbole, accessible via symbol-function :

(eq #'next (symbol-function 'next))
; Résultat : T

(setf (symbol-function 'next) #'+)

(next 10 4)
; Résultat : 14

Liste de paramètres

La liste des paramètres d'une fonction peut contenir plusieurs types de paramètres : requis, facultatifs, reste, mots-clés.

Paramètres requis

Ce sont les paramètres obligatoires, représentés par des symboles. Lors de l'appel, une valeur doit être fournie pour chacun.

(defun muladd (x y z)
  (+ (* x y) z))

(muladd 3 4 5)
; Résultat : 17

Les paramètres requis sont des variables lexicales modifiables dans le corps de la fonction :

(defun bizarre (x)
  (incf x 3)
  (expt 2 x))

(bizarre 4)
; Résultat : 128

Paramètres facultatifs

Ils sont introduits par &optional. Si un argument n'est pas fourni, la valeur par défaut est nil ou une expression spécifiée.

(defun f (a b &optional c d)
  (list a b c d))

(f 1 2)
; Résultat : (1 2 NIL NIL)

(f 1 2 3)
; Résultat : (1 2 3 NIL)

(f 1 2 3 4)
; Résultat : (1 2 3 4)

Exemple avec valeur par défaut dynamique :

(defparameter *l* (list 9 8 7 6 5 4 3 2 1))

(defun f (a b &optional c (d (pop *l*)))
  (list a b c d))

(f 1 2 3 4)
; Résultat : (1 2 3 4)

(f 1 2 3)
; Résultat : (1 2 3 9)

(f 1 2)
; Résultat : (1 2 NIL 7)

Paramètre reste

Introduit par &rest, il capture tous les arguments supplémentaires dans une liste.

(defun f (a b &optional c (d (pop *l*)) &rest e)
  (list a b c d e))

(f 1 2 3)
; Résultat : (1 2 3 9 NIL)

(f 1 2 3 4 5)
; Résultat : (1 2 3 4 (5))

(f 1 2 3 4 5 6 7 8 9)
; Résultat : (1 2 3 4 (5 6 7 8 9))

On peut aussi détecter si un argument facultatif a été fourni :

(defun f (x &optional (y 25 y-supplied-p))
  (list x y y-supplied-p))

(f 1)
; Résultat : (1 25 NIL)

(f 1 25)
; Résultat : (1 25 T)

Paramètres mots-clés

Introduits par &key, ils sont passés sous forme de paires nom-valeur, où le nom est un symbole précédé de :. Si non fournis, la valeur est nil ou une valeur par défaut.

(defun f (x &key y z)
  (list x y z))

(f 1)
; Résultat : (1 NIL NIL)

(f 1 :y 2)
; Résultat : (1 2 NIL)

(f 1 :z 3)
; Résultat : (1 NIL 3)

(f 1 :z 3 :y 2)
; Résultat : (1 2 3)

Valeur par défaut avec expression :

(defun f (x &key (y (cons 'a 'b)) z)
  (list x y z))

(f 1)
; Résultat : (1 (A . B) NIL)

(f 1 :y 2)
; Résultat : (1 2 NIL)

Détection de la présence d'un argument :

(defun f (x &key (y 25 y-supplied-p))
  (list x y y-supplied-p))

(f 1)
; Résultat : (1 25 NIL)

(f 1 :y 25)
; Résultat : (1 25 T)

Le symbole &allow-other-keys permet d'ignorer les mots-clés non déclarés :

(defun f (x &key y &allow-other-keys)
  (list x y))

(f 23)
; Résultat : (23 NIL)

(f 23 :y 2)
; Résultat : (23 2)

(f 23 :y 2 :lskdfjs 22)
; Résultat : (23 2)

En combinaison avec &rest, le paramètre reste contient tous les couples mot-clé/valeur :

(defun f (x &rest r &key y &allow-other-keys)
  (list x y r))

(f 23)
; Résultat : (23 NIL NIL)

(f 23 :y 2)
; Résultat : (23 2 (:Y 2))

(f 23 :y 2 :lsdfjs 22)
; Résultat : (23 2 (:Y 2 :LSDFJS 22))

Exemples de listes de paramètres

(defun make-rotation-transformation (angle &optional origin)
  (if origin
      (make-rotation-transformation* angle (point-x origin) (point-y origin))
      (make-rotation-transformation* angle 0 0)))

(defun find-frame-manager (&rest options
                         &key port &allow-other-keys)
  (declare (special *frame-manager*))
  (if (boundp '*frame-manager*)
      *frame-manager*
      (if (and *default-frame-manager*
               (frame-manager-p *default-frame-manager*))
          *default-frame-manager*
          (first (frame-managers
                  (or port (apply #'find-port options)))))))

(defun make-pane (type &rest args)
  (apply #'make-pane-1 *pane-realizer* *application-frame* type args))

Définitions de fonctions locales

Les opérateurs spéciaux flet et labels permettent de définir des fonctions locales, visibles uniquement dans un bloc donné.

Syntaxe :

(flet ((fn-1 lambda-liste corps)
       ...
       (fn-m lambda-liste corps))
  expr-1
  ...
  expr-n)

(labels ((fn-1 lambda-liste corps)
         ...
         (fn-m lambda-liste corps))
  expr-1
  ...
  expr-n)

Exemple avec flet :

(flet ((square (x) (* x x))
       (add3 (x) (+ x 3)))
  (square (add3 5)))
; Résultat : 64

Différence principale : avec flet, les fonctions locales ne peuvent pas s'appeler mutuellement, alors qu'avec labels, elles peuvent (portée étendue).

Exemple avec flet redéfinissant temporairement + :

(flet ((+ (&rest l) (print l) (apply #'+ l)))
  (+ 2 3 4))
; Affiche : (2 3 4)
; Résultat : 9

Exemple avec labels pour une fonction récursive :

(labels ((fact (n) (if (< n 2) 1 (* n (fact (1- n))))))
  (fact 40))
; Résultat : 815915283247897734345611269596115894272000000000

La liaison entre nom et fonction est locale, mais la fonction elle-même a une durée de vie indéfinie :

(labels ((fact (n) (if (< n 2) 1 (* n (fact (1- n))))))
  (setf *fn* #'fact))

(funcall *fn* 40)
; Résultat : 815915283247897734345611269596115894272000000000

Glossaire des termes clés

• Liste d'association (alist) : liste de paires (cons) associant une clé à une valeur.
• assoc : fonction cherchant une paire dans une alist selon une clé.
• eql : prédicat d'égalité par défaut pour assoc.
• acons : crée une paire et l'ajoute en tête d'une alist.
• pairlis : construit une alist à partir de deux listes (clés et valeurs).
• rassoc : comme assoc mais recherche par valeur.
• defun : macro pour définir une fonction globale.
• paramètre requis : argument obligatoire d'une fonction.
• paramètre facultatif (&optional) : argument optionnel avec valeur par défaut.
• paramètre reste (&rest) : capture les arguments supplémentaires dans une liste.
• paramètre mot-clé (&key) : argument nommé passé sous forme de paires nom-valeur.
• flet : définition locale de fonctions sans récursion mutuelle.
• labels : définition locale de fonctions avec récursion mutuelle possible.
• closure (fermeture) : fonction qui capture son environnement lexical.

Points clés à retenir

• Les listes d'association sont des structures simples pour des tables indexées, manipulables avec assoc, acons, pairlis, etc.
• assoc utilise eql par défaut, mais on peut spécifier d'autres prédicats avec :test ou :test-not.
• Les fonctions globales sont définies avec defun, et leur liste de paramètres peut contenir des paramètres requis, facultatifs, reste et mots-clés.
• Les paramètres facultatifs et mots-clés peuvent avoir des valeurs par défaut évaluées dynamiquement.
• Le paramètre reste permet de récupérer un nombre variable d'arguments supplémentaires sous forme de liste.
• flet et labels permettent de définir des fonctions locales, labels autorisant la récursion mutuelle.
• Les fonctions sont des objets de première classe, pouvant être manipulées, assignées et passées en arguments.