IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

Func' programming - un blog homéopathique

[Actualité] Une deuxième cuillère de LISP

Noter ce billet
par , 26/03/2015 à 18h09 (1085 Affichages)
- vous prendrez bien une autre cuillère de LISP ?
Bien que Common LISP ne soit pas un langage fonctionnel, il en a de nombreux traits. En particulier, les fonctions y sont des citoyens à part entière, à la différence du C, par exemple. En C, on peut définir une fonction- mais de façon statique, en prendre l’adresse et l’appeler directement ou par pointeur interposé, mais c’est tout. Dans les langages fonctionnels, et dans des langages de plus en plus nombreux qui ne se réclament pas de ce paradigme, on peut créer des fonctions de façon dynamique, qui capturent une partie de l’environnement existant (c’est ce qu’on appelle les closures), les assigner à des variables, etc. Des fonctions peuvent retourner des fonctions également.

Deux espaces de nommage, deux !
Dans Common LISP, cependant, les fonctions ont une particularité : elles résident dans leur propre espace de nommage. C’est-à-dire qu’il y a un espace de nommage pour les autres variables, et un pour les fonctions :

CL-USER> (setf a 5) ; ; espace de nommage des variables : { a : 5 }
5
CL-USER> (defun a () 6) ; ; espace de nommage des fonctions : { a : functionQuiRetourne6 }
A
CL-USER> a ; ; je demande la variable a
5
CL-USER> (a) ; ; je demande l’évaluation de la fonction a
6

Pour indiquer qu’on veut se référer à la fonction a mais sans l’évaluer (par exemple pour la passer en argument à une autre fonction), on fait précéder son nom de #’ :

CL-USER> #'a
#<Compiled-function A #xC8AF48E>

Ce n’est pas le cas dans la plupart des langages fonctionnels, qui n’ont qu’un espace de nommage – y compris des dialectes de LISP comme Scheme ou Clojure.

Les fonctions lambda
Les fonctions lambda sont des fonctions anonymes. Rien de révolutionnaire, donc, mais très pratique. En C, ou dans des versions antérieures de C++ ou de Java, s’il était besoin de passer une fonction à une autre fonction (algorithme de tri, par exemple), il fallait la définir loin de là où elle était utilisée, et pire encore, lui donner un nom (compareDeuxièmeChampOrdreInverse, par exemple). En LISP on utilisera une fonction lambda :

NB : sort prend deux arguments : la séquence à trier et une fonction comparant deux éléments
CL-USER> (sort '((1 2) (1 4) (1 3)) (lambda (x y) (> (second x) (second y)))) ; ; second renvoie le deuxième élément d’une liste
((1 4) (1 3) (1 2))

La syntaxe, donc :
( lambda (arg1 arg2 …) (corpsDeLaFonction) )

Les fonctions sont des arguments comme les autres
Comme il est très facile de créer des fonctions on the fly, les fonctions qui prennent d’autres fonctions sont très fréquentes dans le style fonctionnel. Quelques exemples dans Common LISP :
- mapcar fonction liste : crée une nouvelle liste résultant de l’application de fonction aux éléments de liste
- remove-if fonction liste : crée une liste contenant les éléments de liste pour lesquels fonction ne retourne pas Nil
- funcall fonction arg1 arg2 … : appelle la fonction fonction avec les arguments qui suivent
- apply fonction liste : appelle la fonction avec les arguments contenus dans la liste
- reduce fonction liste : accumule l’application de fonction aux membres de la liste

Exemples :
CL-USER> (mapcar #'1+ '(1 2 3 4))
(2 3 4 5)
CL-USER> (remove-if #'oddp '(1 2 3 4))
(2 4)
CL-USER> (funcall #'- 2 1)
1
CL-USER> (apply #'+ '(1 2 3 4))
10
CL-USER> (reduce #'* '(1 2 3 4))
24

Une fonction qui sera utile dans le prochain billet
Nous allons maintenant élaborer une fonction qui nous sera nécessaire dans le prochain billet, celui où nous jouerons au poker. Donnons lui un petit nom anglais pour qu’elle ne détone pas parmi les fonctions prédéfinies dans LISP : split-if-not (coupe-si-non). Elle prend pour argument une fonction à deux arguments et une liste, qu’elle découpe en sous-listes lorsque la fonction n’est plus vraie pour deux éléments qui se succèdent :

CL-USER> (split-if-not #'= '(1 1 2 3 3 3 4 5 5))
((1 1) (2) (3 3 3) (4) (5 5))
CL-USER> (split-if-not (lambda (x y) (= (1+ x) y)) '(1 2 3 5 6 8 9))
((1 2 3) (5 6) (8 9))

Je vous propose d’arrêter un instant votre lecture, de tenter par vous-même et de regarder la solution après !





Pour une fonction récursive, il faut un cas de base, ou cas d’arrêt, et un cas n+1 qui renvoie au cas n, jusqu’à renvoyer finalement au cas de base. C’est un processus identique au raisonnement par induction en mathématiques.
L’exemple canonique de la factorielle :
(defun fac (n)
(if (zerop n) 1 ; ; cas d’arrêt -vous comprenez zerop tous seuls, non ?
(* n (fac (1- n))))) ; ; cas n+1 / 1- décrémente son argument, évidemment

Pour split-if-not, le cas de base (hors le cas où la liste est vide, que je laisse de côté pour le moment), est le cas où la liste en argument ne comporte qu’un élément :

CL-USER> (split-if-not #'= '(1))
((1))

Dans le cas n+1, on compare l’élément traité au premier élément de la première liste de n. Par exemple :
(split-if-not #’= ‘(1 1))
< = >
(pseudo-code)
cas-n = ( (1) ) ; ; (split-if-not #’= ‘(1))
cas n+1 = soit x le premier élément de la première liste de cas-n; si x == 1 alors ‘((1 x))
sinon ‘((1) (x))

Soit, en LISP :
(defun split-if-not (pred lst)
(if (null (cdr lst)) ;; s'il n'y a qu'un élément dans la liste
(list lst) ; ; list renvoie une liste contenant ses arguments
(let ((nxt (split-if-not pred (cdr lst)))) ;; let crée un contexte avec la liste de variables locales en premier argument
(if (funcall pred (car lst) (caar nxt)) ; ; caar est la contraction de car car : (caar x) < = > (car (car x))
(cons (cons (car lst) (car nxt)) (cdr nxt))
(cons (list (car lst)) nxt)))))
Exercices :
- documentez-vous sur la fonction reduce : regardez les arguments optionnels et les différentes façons de l’utiliser. Essayez d’exprimer mapcar en terme de reduce ;
- lisez le billet « Misères de la conception objet, un cas pratique » sur le blog reac’programming et méditez-en la leçon ;
- devinez en quoi la fonction split-if-not va nous servir pour le poker ?

Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Viadeo Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Twitter Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Google Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Facebook Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Digg Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Delicious Envoyer le billet « Une deuxième cuillère de LISP » dans le blog MySpace Envoyer le billet « Une deuxième cuillère de LISP » dans le blog Yahoo

Mis à jour 27/03/2015 à 10h20 par stendhal666

Tags: lambda, lisp, map, reduce
Catégories
Programmation

Commentaires