Programmation fonctionnelle (valeur du prédicat)

VDH-Bruno · le 23 mai 2011

Bonjour,

J’arrive un peu près à ce que je veux réaliser dans ce style de programmation maintenant je suis au stade ou je souhaite optimiser un peu mes codes.. Il y a un point qui me pose encore quelques difficultés (ou incertitudes), c’est comment récupérer la valeur d’un prédicat de façon à le passer comme argument de l’appel récursif ?

Pour illustrer ma difficulté je vous présente un code simple qui résume bien le cas de figure que je veux exposer. A savoir réaliser la fonction complémentaire à la fonction member :

 ;; ---------------------------------------------------------------
;; (bv:c-member expr lst) -> fonction complémentaire de member 
;; Recherche une expression dans une liste et renvoie les éléments
;; précédents la première expression trouvé. 
;; Si la liste ne contient pas l'expression recherchée, la liste 
;; initiale est retourné. 
;; ---------------------------------------------------------------
;; Exemples: 
;; (bv:c-member 'c '(a b c d c e)) -> (A B) 
;; (bv:c-member 'z '(a b c d c e)) -> (A B C D C E) 
;; (bv:c-member 'a '(a b c d c e)) -> nil 

(defun bv:c-member (expr lst / fun)

 (defun fun (lst)
   (if	(member expr lst)
     (fun (cdr (member expr lst)))
     lst
   ) ;_ Fin de if
 ) ;_ Fin de defun

 (reverse (fun (reverse lst)))
) ;_ Fin de defun

La fonction donne bien le résultat escompter, toute fois il y a une optimisation possible dans l’appel récursif de fun à savoir que l’expression ( member expr lst) et executé 2 fois, une fois comme prédicat de la fonction if et une second fois comme argument dans l’appel récursif de fun.

Une voie possible mais qui n’est pas celle que je recherche, c’est de stocker avec setq la valeur de ( member expr lst) de la façon suivante :

 (defun fun (lst / x)
 (if (setq x (member expr lst))
   (fun (cdr x))
   lst
 ) ;_ Fin de if
) ;_ Fin de defun

La solution que je recherche c’est de réalisé la même chose avec un appel de fonction, actuellement j’arrive à coder ça avec la fonction lambda, en m’inspirant de ce qui m’a été montré dans mon poste sur le triangle de pascal.

 (defun bv:c-member (expr lst / fun)

 (defun fun (lst)
   ((lambda (l)
      (if l
 (fun (cdr l))
 lst
      ) ;_ Fin de if
    ) ;_ Fin de lambda
     (member expr lst)
   )
 ) ;_ Fin de defun

 (reverse (fun (reverse lst)))
) ;_ Fin de defun

Question est ce la bonne méthode ou a-t-il d’autres solutions (ou optimisation possible).. Car au petit jeu du benchmark les résultats ne sont pas forcément là:

(benchmark '((bv:c-member1 'c '(a b c d c e c c c c c c c c c c c c c c c c c c c c))
(bv:c-member2 'c '(a b c d c e c c c c c c c c c c c c c c c c c c c c))
(bv:c-member3 'c '(a b c d c e c c c c c c c c c c c c c c c c c c c c))
))

Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

(BV:C-MEMBER2 (QUOTE C) (QUOTE (A B ...).....1516 / 1.13
(BV:C-MEMBER1 (QUOTE C) (QUOTE (A B ...).....1563 / 1.1
(BV:C-MEMBER3 (QUOTE C) (QUOTE (A B ...).....1718 / 1

(Note: bv:c-member1 bv:c-member2 bv:c-member3 sont les évaluations respectives des codes dans l'ordre de leurs présentations. On peut remarquer que bv:c-member2 est naturellement optimisé contrairement à bv:c-member3, l'appel à lambda consomme visiblement plus de ressource que l'évaluation redondante du (member expr lst) dans bv:c-member1, le mieux est il l'ennemi du bien???).

Tous les avis sont les biens venus, d’avance merci.

A+ VDH

Patrick_35 · le 23 mai 2011

Salut

Pourquoi toujours faire une récursive ?

(defun pa:c-member (expr lst / tab)
 (while (and (/=  (car lst) expr) lst)
   (setq tab (cons (car lst) tab)
  lst (cdr lst)
   )
 )
 (reverse tab)
)

@+

(gile) · le 23 mai 2011

Pourquoi toujours faire une récursive ?

Il me semble que Bruno parle de programmation fonctionnelle.

Ce style de programmation privilégie la récursivité pour éviter l'utilisation de variables (changements d'état des données et effets de bord).

Ceci n’empêche pas d'utiliser setq pour attacher une valeur à un symbole mais cette valeur doit être immuable (c'est la cas par défaut en F# avec le mot clé let).

Dans la seconde version de fun de Bruno, l'utilisation de setq est 'compatible' avec un style fonctionnel, la valeur affectée à x ne change pas.

Dans la fonction de Patrick l'utilisation de setq est caractéristique d'un style impératif utilisant une variable (la valeur affectée à tab change à chaque itération).

On arrive souvent à éviter l'utilisation de setq avec une fonction lambda comme tu l'as fait, mais, à mon avis, ça ne fait que rendre le code moins lisible.

Pour une fonction (récursive) complémentaire à member, on peut faire plus simple (fonction donnée, entre autres, ici) :

(defun gc:trunc (expr lst)
 (if (and lst (not (equal expr (car lst))))
   (cons (car lst) (gc:trunc expr (cdr lst)))
 )
)

Concernant les prédicats en AutoLISP, une particularité des fonctions utilisant des prédicats (if, cond, etc.) est que ces fonctions n'exigent pas que la conditionnelle retourne un type Booléen Vrai ou Faux (T ou nil) mais simplement une valeur non nil ou nil.

VDH-Bruno · le 23 mai 2011

Bonsoir,

Tout d’abord, je n’ai pas pris assez de recul avec mon teste au benchmark, tel qu’il était formulé j’effectuais la comparaison entre une fonction lambda et une fonction member à chaque répétion et pas l’évaluation de l’optimisation réalisé dans mon code. Le bon teste ressemblerai plus à une comparaison de ce type, désolé pour l’étourderie.

(benchmark '((bv:c-member1 'c '(a b c d e f g h i j k l m a b c d e f g h i j k l m))
(bv:c-member2 'c '(a b c d e f g h i j k l m a b c d e f g h i j k l m))
(bv:c-member3 'c '(a b c d e f g h i j k l m a b c d e f g h i j k l m))
))
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):
(BV:C-MEMBER2 (QUOTE C) (QUOTE (A B ...).....1172 / 1.04
(BV:C-MEMBER3 (QUOTE C) (QUOTE (A B ...).....1203 / 1.01
(BV:C-MEMBER1 (QUOTE C) (QUOTE (A B ...).....1219 / 1

Pour une fonction (récursive) complémentaire à member, on peut faire plus simple

Oui (gile), on pouvait faire différemment, d’ailleurs j’avais déjà la structure de base dans une fonction quasi similaire bv:l=npe (il ne restait qu’à la retoucher un peu).

 ;; ---------------------------------------------------------------
;; (bv:l=npe n lst)                                               
;; ---------------------------------------------------------------
;; Renvoie une Liste égal aux N Premiers Eléments.                
;; Exemple :                                                      
;;    (bv:l=npe 0 '(a b c d e))       renvoie  nil                
;;    (bv:l=npe 2 '(a b c d e))       renvoie  (A B)              
;;    (bv:l=npe 8 '(a b c d e))       renvoie  (A B C D E)        

(defun bv:l=npe	(n lst / fun)
 (defun fun (n lst)
   (if	(< 0 n)
     (cons (car lst) (bv:l=npe (1- n) (cdr lst)))
   ) ;_ Fin de if
 ) ;_ Fin de defun

 (if (< n (length lst))
   (fun n lst)
   lst
 ) ;_ Fin de if
) ;_ Fin de defun

Que j’avais écrit en même temps que la fonction bv:l-npe.

 ;; ---------------------------------------------------------------
;; (bv:l-npe n lst)                                               
;; ---------------------------------------------------------------
;; Renvoie une Liste des privés de ses N Premiers Eléments,       
;; Exemple :                                                      
;;    (bv:l-npe 0 '(a b c d e))       renvoie  (A B C D E)        
;;    (bv:l-npe 2 '(a b c d e))       renvoie  (C D E)            
;;    (bv:l-npe 8 '(a b c d e))       renvoie  nil                
(defun bv:l-npe	(n lst)
 (cond
   ((< 3 n) (bv:l-npe (- n 4) (cddddr lst)))
   ((< 2 n) (bv:l-npe (- n 3) (cdddr lst)))
   ((< 1 n) (bv:l-npe (- n 2) (cddr lst)))
   ((< 0 n) (bv:l-npe (- n 1) (cdr lst)))
   (T lst)
 ) ;_ Fin de cond
) ;_ Fin de defun

Pour écrire une fonction sublist qui travaille directement sur la tête de liste et non sur l’indice (ou position) des élèments comme tu l’a fait dans la tienne.

Mais pour en revenir à c-member, j’ai voulu tenter une approche différente surtout depuis hier lorsque je me suis aperçu que ces fonctions avaient déjà été évoqué dans le challenge n° 22 ( Au passage dure dure de passer après vous mais cela doit être un peu normal, je n’ai que 10 ans de retard à rattraper). Mais j’avoue que ta fonction trunc à l’avantage d’être linéaire dans sa performance contrairement à la mienne qui dépend de l’âge du capitaine (c.a.d. du nombre d’éléments identique constituant lst).

Dans la seconde version de fun de Bruno, l'utilisation de setq est 'compatible' avec un style fonctionnel, la valeur affectée à x ne change pas. […) On arrive souvent à éviter l'utilisation de setq avec une fonction lambda comme tu l'as fait, mais, à mon avis, ça ne fait que rendre le code moins lisible.

Merci pour le retour, convaincu par ta reflexion sur la lisibilité.

Pourquoi toujours faire une récursive ?

Patrick_35, non pas forcément d’ailleurs en général en tant qu’apprenant, je m’efforce de coder les deux histoires de ne pas m’enfermer complément dans un style plus que dans un autre. Mais j’avoue avoir un gros penchant pour le côté fonctionnelle que je privilégie toujours en première approche et effectivement comme l’a dit (gile) des qu’il est question de prédicat dans un processus répétitif difficile en programmation fonctionnelle d’éviter de faire une récursive.

Au passage je trouve ce type de fonctions beaucoup plus souple pour le traitement et le travail sur les listes (qui sont d’ailleurs elles-mêmes des structures récursives), prenons en exemple la fonction pa:c-member et la fonction gc:trunc pour moi c’est le même traitement à la différence prés qu’avec une boucle while tu ne peux conser ta liste que dans un sens ce qui t’oblige à un reverse. Alors qu’en récursif tu peux conser en descendant dans tes appels (avec un argument suplémentaire en guise d’accumulateur) cas de la recursion terminal et la tu devrais également employer un reverse, ou alors tu peux conser en remontant tes appels récursif (ce que fait la fonction trunc) cas de la recursion enveloppante et la plus besoin de reverse.

Il est également très difficile d’explorer avec while des listes de profondeur inconnue, alors qu’avec la récursion multiple rien de plus facile :

 ;; ---------------------------------------------------------------
;; (bv:profondeur lst)                                            
;; ---------------------------------------------------------------
;; Renvoie la profondeur maxi d'une liste.                        
;; Exemples :                                                     
;;    (bv:profondeur '(a b c d e))         renvoie  1             
;;    (bv:profondeur '((a b) c (((d e))))) renvoie  4             
;;    (bv:profondeur '())                  renvoie  0             
(defun bv:profondeur (lst)
 (if (atom lst)
   0
   (max (1+ (bv:profondeur (car lst)))
 (bv:profondeur (cdr lst))
   ) ;_ Fin de max
 ) ;_ Fin de if
) ;_ Fin de defun

De plus les fonctions de boucle tel que repeat while me semble limiter aux imbriquations de répétition, alors que la récursion permet de les croiser voir ici pour la dernière publication en date de ce type de boucle.

Pour finir j’ai jamais réussie à me servir correctement des outils de débogage de Visual Lisp, alors que en récursif il y a la fonction trace. Je crois que l’on reste fortement influencé par le style de ses débuts et quant j’ai commencé l’aventure Lisp, je me suis très vite intéressé à cette aspect de la programmation (le côté fonctionnelle), au début par défit, maintenant c’est plus par « jeux ».

A+ VDH

(gile) · le 24 mai 2011

Re,

Pour bv:l=npe aussi tu peux faire plus simple (pas besoin de fonction auxiliaire, c'est la fonction principale qui est récursive) :

(defun gc:take (n lst)
 (if (and lst (    (cons (car lst) (gc:take (1- n) (cdr lst)))
 )
)

VDH-Bruno · le 24 mai 2011

Bonjour,

Pour bv:l=npe aussi tu peux faire plus simple (pas besoin de fonction auxiliaire, c'est la fonction principale qui est récursive)

Oui (gile), tu as raison c’était comme cela que je l’avais vu à l'origine, la coquille ligne 4 de mon code (cons (car lst) (bv:l=npe (1- n) (cdr lst))) en atteste, ce qui est une étourderie de copier-colller, la bonne version est la suivante :

 (defun bv:l=npe  (n lst / fun)
 (defun fun (n lst)
   (if     (< 0 n)
     (cons (car lst) (fun (1- n) (cdr lst)))
   ) ;_ Fin de if
 ) ;_ Fin de defun

 (if (< n (length lst))
   (fun n lst)
   lst
 ) ;_ Fin de if
) ;_ Fin de defun

Cette version (et donc la fonction auxiliaire fun) résulte d’un effort de logique pour optimiser les ressources déployer dans le calcul du prédicat, logique qui dit que si n est inférieur à la longueur de la liste, il n’y aura jamais besoin de vérifier l’existence de lst et il n’y aura plus besoin du and dans le calcul du prédicat précédent tous les appels de fun, contrairement à la version que tu publie. Je te le concède d'avance l’optimisation est plus que discutable (perte de la concision, calcul de length sur tous les éléments de lst ect..) mais en général sur les grandes listes avec des valeurs de n élevé on s’y retrouve..

En guise de clin d’œil à Patrick_35 (que je remercie au passage pour ses routines et ses lignes de codes dans lesquels il m’arrive de puiser allègrement). La même version écrit avec un repeat..

 (defun bv2:l=npe (n lst / res)
 (if (< n (length lst))
   (progn
     (repeat n
           (setq res (cons (car lst) res)
                 lst (cdr lst)
           )
     )
     (reverse res)
   )
   lst
 )
)

A+

(Ps : Dans l’exemple pa:c-member il y a une coquille, en lisp une expression peut être considéré comme un atome ou une liste. La fonction /= (tout comme la fonction =) ne s’applique qu’aux atomes (nombres, chaines, symboles). Quant aux fonctions < > >= et <= qui sont des comparateurs numériques elles ne s’appliquent qu’exclusivement aux nombres et aux chaînes).

 (/= (list 1 2) (list 1 2)); retourne T
(/= (list 1 3) (list 1 2)); retourne T

Patrick_35 · le 25 mai 2011

Salut

Je n'ai pas le temps de m'étendre sur le sujet, mais je trouve que la prog itérative/impératif est plus intuitif et simple à mettre en oeuvre (a mon sens). De plus, elle évite les débordements de pile.

Définir une variable voir deux (pour les itérative) contre une fonction (pour les récursives). Why not!

Quant aux "effets de bords", je veux bien croire que cela peut avoir une incidence en c++, mais en lisp... Surtout si le prog est bien structuré et que l'on a bien fait attention à ses variables (locale/globale)

Donc pour vérifier que jé n'ai pas oublié de variable qui "traine", j'utilise cette procédure

(setq vtmp (atoms-family 1))

Je lance le lisp et fait toutes les manips possible.

Et pour vérifier que tout est ok au niveau variables

(vl-remove-if '(lambda(x)(member x vtmp))(atoms-family 1))

ps : Je ne reste pas fermé aux récursives, bien au contraire, mais je préfère le simple et fonctionnel, surtout quand il s'agit de modifier un lisp qui a été fait, il y a quelques temps déjà.

pps : Bien vu pour la coquille.

ppps : Que je remercie au passage pour ses routines et ses lignes de codes dans lesquels il m’arrive de puiser allègrement

Merci, c'est gentil et tu as raison, c'est de cette manière que l'on progresse

pppps : ben non, ça suffit ;)

@+

(gile) · le 25 mai 2011

Salut,

Heureusement, la plupart des langages de programmation modernes sont 'multi-paradigme'*.

AutoLISP, dérivé du LISP (premier langage fonctionnel) permet la programmation fonctionnelle et impérative et donc à chacun de choisir de privilégier l'un ou l'autre.

Je pense que la tendance de chacun à utiliser un style plutôt qu'un autre relève de la façon de penser de chacun. Il m'arrive de penser d'abord récursif pour résoudre certains problème puis de traduire ensuite en itératif pour optimisation.

Mais la programmation fonctionnelle ne se réduit pas à la récursivité (qui, par ailleurs, est aussi utilisée en style impératif quand elle est incontournable).

Certains aspects d'AutoLISP relèvent plus exclusivement de la programmation fonctionnelle comme les fonctions dites d'ordre supérieur (fonctions qui requièrent une autre fonction comme argument) comme mapcar, apply, etc. ou les expressions lambda, et là encore, on voit bien que certains suivant leurs 'mode de pensée' ont plus ou moins de facilité à les utiliser.

* un langage qui serait 'purement fonctionnel' ne permettrait que d'interagir avec le compilateur (ou l'interpréteur) pour faire des calculs.

VDH-Bruno · le 25 mai 2011

Bonsoir,

Moi non plus je ne pense pas m’étendre d’avantage sur cette aspect de la programmation (je ne veux pas faire de prosélytisme), je dirai simplement que si je m’essaie à la programmation fonctionnel, c’est parce que c’est ce qui caractérise le Lisp (bien qu’AutoLISP soit 'multi-paradigme' comme l’a précisé (gile)), avec le peu de recul que j’ai, je reste persuadé de 2 choses :

En 1 – Qu’il n’est pas fondamentalement pas plus difficile d’apprendre la programmation fonctionnel que la programmation impérative pour quelqu’un qui par de zéro comme moi.

En 2 – Que par la suite il est certainement plus facile de passer de la programmation fonctionnelle à la programmation impérative (si besoin est), la réciproque me semblant moins évidente…

Pour ce qui est de la récursion je conseil ce tut sur le site du zero (pour ceux qui en recherche), il n’est pas spécifique au Lisp (php et Ocalm) mais suffisamment général et détaillé pour être facilement transposable, de plus il y de bonnes réflexions sur son emploie, sa soi-disant lenteur d’exécution et les débordements de pile (ce qui est vrai en AutoLISP, mais pas forcément dans d’autres langages…).

(setq vtmp (atoms-family 1))
(vl-remove-if '(lambda(x)(member x vtmp))(atoms-family 1))

Sinon un grand bravo Patick_35 pour ces quelques lignes, que je me suis empressé de convertir en fonction (au passage atoms-family à 0 améliorera par 5 le traitement de la fonction). Fonction sur laquelle je pensais bien plancher un jour mais pas si vite.. Je suis heureux de ton intervention qui m’aura donné l’occasion de gagner un temps précieux.

 ;; ---------------------------------------------------------------
;; (bv1:auditfun 'fun)                                             
;; Retourne la liste des nouvelles variables et fonctions non     
;; localisées. Suite à l'appel de fun                             
;; ---------------------------------------------------------------
;; Adapté d'un code de Patrick_35 (source CADXP)                  
(defun bv1:auditfun (fun)
 ((lambda (lst)
    (eval fun)
    (vl-remove-if '(lambda (x) (member x lst)) (atoms-family 0))
  )
   (atoms-family 0)
 )
)

;|
;; variante qui a l’avantage de ne pas pister la variable lst 
;; pour ceux que cela gênerai
(defun bv1:auditfun (fun / lst)
 (setq	lst T
lst (atoms-family 0)
 )
 (eval fun)
 (vl-remove-if '(lambda (x) (member x lst)) (atoms-family 0))
)
|;

Pour tester

 (defun n*n ()
 (defun carre (n)
   (* n n)
 ) 
 (carre (getreal "Saisissez un nombre: "))
)

Teste

_$ (bv1:auditfun '(n*n))
(CARRE)
_$

Sinon une autre façon de faire (propre et élégante).

 
;; ---------------------------------------------------------------
;; (bv2:auditfun)                                                 
;; Retourne la liste des nouvelles variables et fonctions non     
;; localisées.                                                    
;; ---------------------------------------------------------------
;; Adapté d'un code de Patrick_35 (source CADXP)                  
;; Exemple:                                                       
;;    (bv2:auditfun) ;1er appel liste l'état actuel des symboles  
;;                   ;définie                                     
;;    (Mafonction)   ;fonction à analyser                         
;;                                                                
;;    (bv2:auditfun) ;2éme appel renvoie les symboles nouvellement
;;                   ;crée                                        
;; Note: L'argument lst en également listé.                       
(defun bv2:auditfun ()
 ((lambda (lst)
    (if lst
      (progn
 (setq lstsym nil)
 (vl-remove-if '(lambda (x) (member x lst)) (atoms-family 0))
      )
      (setq lstsym (atoms-family 0))
    )
  )
   lstsym
 )
)

;|
;; variante qui ne liste pas l'argument lst
(defun bv2:auditfun (/ lst)
 (if *lstsym*
   (progn
     (setq lst	*lstsym*
    *lstsym* nil
     )
     (vl-remove-if '(lambda (x) (member x lst)) (atoms-family 0))
   )
   (setq lst	   T
  *lstsym* (atoms-family 0)
   )
 )
)
|;

Teste

_$ (setq *lstsym* nil x nil lst nil carre nil)
nil
_$(bv2:auditfun)
... vla-put-DockedVisibleLines [...] vla-get-ShowPlotStyles vla-get-NumCellStyles)
_$ (n*n)
25.0
_$ (bv2:auditfun)
(CARRE)
_$

A+ Bruno

[Edité le 25/5/2011 par VDH-Bruno]

Connexion

Programmation fonctionnelle (valeur du prédicat)

Messages recommandés

VDH-Bruno

Patrick_35

(gile)

VDH-Bruno

(gile)

VDH-Bruno

Patrick_35

(gile)

VDH-Bruno

Créer un compte ou se connecter pour commenter

Créer un compte

Se connecter

Forums

Naviguer

Activité

Information importante