Dans cette brève note, nous verrons comment vous pouvez implémenter en Lisp des mécanismes logiciels désormais très populaires tels que l'application partielle et le currying de fonctions. Pour ce faire, j'utiliserai mon implémentation Homelisp (il s'agit d'un interpréteur Lisp pur avec quelques fonctionnalités supplémentaires).
L'utilisation d'une application partielle en Common Lisp est susceptible d'être délicate (car vous devez utiliser funcall / apply pour appeler un objet fonction calculé); dans Scheme, cela devrait être plus facile. Je prévois de publier une nouvelle version de HomeLisp bientôt, qui ne nécessite pas funcall / apply pour appeler un objet fonction calculé. Dans les cas où le comportement du code est différent, je soulignerai ceci.
L'application partielle et le curry sont des opérations mathématiques strictes. Mais nous les considérerons «sur les doigts», sans recourir au calcul lambda et à la logique combinatoire.
Une application partielle de la fonction f est d'obtenir de la fonction f une nouvelle fonction f 'qui a déjà pris les arguments donnés et est prête à accepter le reste. À quoi sert une application partielle? Par exemple, pour qu'une valeur fonctionnelle puisse être renvoyée à partir d'une fonction.
Considérons une application partielle avec un exemple simple. Soit la fonction f donnée par la formule:
f (x, y, z) = x + y ** 2 + z ** 3
puis une application partielle de cette fonction avec les arguments x = 1 et y = 2 doit générer la fonction:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
Dans Haskell, une application partielle ne coûte rien au programmeur:
Prelude> f x y z = x+y**2+z**3 --
f :: Floating a => a -> a -> a -> a
Prelude> f 1 2 3 -- ...
32.0 -- !
it :: Floating a => a
Prelude> f' = f 1 2 -- x=1 y=2 f'
f' :: Floating a => a -> a
Prelude> f' 3 -- f'
32.0 --
it :: Floating a => a
Cependant, en Lisp, une telle tentative échouera:
(defun f (x y z) (+ x (* y y) (* z z z))) ;;
==> F
(f 1 2 3) ;;
==> 32 ;;
(f 1 2) ;; ...
PairLis:
: F
: (X Y Z)
: (1 2)
==> ERRSTATE
Bien sûr, Lisp a un mécanisme pour créer des fonctions avec n'importe quel nombre d'arguments (la construction & rest); vous pouvez créer une fonction qui prendra deux ou trois (ou dix) paramètres:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
Mais il est important de comprendre la différence: cette fonction traite tous les paramètres et renvoie le résultat du calcul, tandis qu'une application partielle aboutit à une nouvelle fonction qui est «prête à continuer le calcul».
Voyons comment nous pouvons implémenter un mécanisme d'application de fonction partielle en Lisp. Et cela nous aidera avec cela ... oui, l'appareil des fonctions anonymes (lambda). Certains programmeurs pensent que les fonctions anonymes ne sont nécessaires que pour enregistrer les noms (ils disent, leur place dans n'importe quel stream-map-filter-Reduce afin d'effectuer une courte action sur un élément de séquence). En fait, les fonctions anonymes sont capables de bien plus, ce que nous allons maintenant voir.
Commençons par regarder comment une fonction peut renvoyer une autre fonction en conséquence. En Lisp, c'est très simple:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Comme vous pouvez le voir, la fonction renvoie une clôture dans laquelle la valeur de la variable libre x est fixe (égale à 5). Le résultat d'une fonction peut être appelé en tant que fonction. Pour ce faire, en Common Lisp et HomeLisp (avec une révision du noyau <= 13.53), vous devrez utiliser funcall:
(funcall (func-gen 5) 7)
==> 54
Maintenant, il est clair comment nous pouvons procéder si nous voulons prendre une fonction f à partir de n arguments et une valeur de x, et par conséquent obtenir une fonction à partir de (n-1) arguments. Notons la liste des paramètres formels de notre fonction par plist. Ensuite, tout ce que vous avez à faire est de créer une expression lambda comme celle-ci:
(lambda (-plist) (apply f (cons x -plist)))
L'idée est très simple: nous construisons une expression lambda dans le corps de laquelle nous appelons simplement la fonction d'origine sur la liste de paramètres, dans laquelle la tête est remplacée par la valeur x.
Cela signifie que pour une application partielle de la fonction, vous devez construire une expression lambda basée sur cette fonction, qui aura un argument de moins, et l'argument spécifié en application partielle sera "pris en compte" dans l'appel interne de notre fonction dans le corps de l'expression lambda.
Comment mettre en œuvre cela? Facile ... HomeLisp a une fonction getd qui permet d'accéder à l'expression ou à la macro de définition d'une fonction:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
Comme vous pouvez le voir, getd renvoie l'expression de définition de la fonction, dans laquelle "au lieu de" le lambda, il y a un atome EXPR spécial. Nous pouvons prendre la liste des paramètres de notre fonction (le deuxième élément du résultat) et construire une expression lambda, dont les paramètres seront la queue de la liste de paramètres d'origine, et dans le corps de l'expression lambda, nous appellerons la fonction d'origine avec la liste complète des paramètres.
(defun part-apply (f a)
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
Il est facile de comprendre à partir du code ci-dessus que plist est la liste originale de la fonction f que nous voulons appliquer partiellement. rlist est la liste d'origine sans le premier élément, et clist est la liste complète des paramètres, le premier élément étant remplacé par x. Plus précisément, pour la fonction g ci-dessus, plist = (xyz), rlist = (yz) et clist = (ayz). Voyons maintenant comment fonctionne l'application partielle:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Vous pouvez voir que c'est exactement ce qui était prévu: part-apply a renvoyé une nouvelle fonction, avec un nombre d'arguments en moins. Si cette nouvelle fonction est appelée avec les paramètres y et z, le résultat est exactement le même que l'appel de la fonction d'origine g avec trois arguments: 111 y et z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Ci-dessous, je (par souci de concision) ne spécifierai pas funcall. Dans le prochain noyau de HomeLisp, le schéma de calcul des fonctions sera modifié - la syntaxe du «schéma» deviendra disponible.
Allons plus loin. Il y aura maintenant une envie naturelle de réappliquer le résultat de la réapplication. Cela s'avère assez simple - après tout, le résultat d'une application partielle est une expression lambda, et il est structuré presque identique au résultat renvoyé par getd. La liste des paramètres de l'expression lambda est le deuxième élément de la liste. Toutes ces considérations nous permettent de construire la solution finale au problème:
(defun part-apply (f a)
(cond ((and (atom f) (member 'expr (proplist f))) ;; *** ***
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
((eq 'lambda (car f)) ;; *** - ***
(let* ((plist (cadr f)) ;;
(rlist (cdr plist)) ;;
(clist (cons x rlist))) ;; x
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
(t (raiseerror "part-apply: "))))
Ici s'ajoute l'analyse du premier paramètre: s'il s'agit d'un atome, alors il doit "représenter" une fonction (de type EXPR); si le premier paramètre n'est ni un atome «valide» ni une expression lambda, alors une condition d'erreur est levée. Le code, bien sûr, pourrait être encore raccourci, deux branches presque identiques sont laissées pour plus de clarté. Voyons maintenant de quoi cette fonction est capable:
(part-apply (part-apply 'g 1) 2) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
((part-apply (part-apply 'g 1) 2) 3) ;;
==> 9
(part-apply (part-apply (part-apply 'g 111) 1) 2) ;;
==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))
((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ...
==> 444
(setq u (part-apply 'g 111)) ;;
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
;; U
(part-apply u 1) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))
((part-apply u 1) 2) ;;
==> 444
Maintenant, faisons le curry. Une fonction curry, acceptant un nombre d'arguments insuffisant, retourne une fonction capable de gérer le reste. L'objectif principal du curry est de fournir une application partielle. Nous sommes partis de l'autre bout: voyons maintenant comment le curry peut être implémenté s'il y a une application partielle.
Soit une fonction g de plusieurs arguments. Nous en construirons une version curry sous un autre nom! G. L'essence de la construction sera la suivante: la fonction! G prendra un nombre indéfini d'arguments. Après l'appel, il doit vérifier le nombre d'arguments passés. Si ce nombre est égal au nombre d'arguments de la fonction d'origine g, alors from doit être passé à l'entrée g. S'il y a plus d'arguments que g ne peut accepter, une condition d'erreur doit être levée. Mais si le nombre d'arguments est inférieur à celui de la fonction g, alors ... oui, vous devez effectuer une application partielle séquentielle. Renvoie le résultat de cette application.
Dans ce cas, il est pratique d'utiliser une macro. Le code avec des commentaires est ci-dessous:
(defmacro curry (f)
(let* ((parmlist (cadr (getd f))) ;; f
(body (cddr (getd f))) ;; f
(lp (length parmlist)) ;; f
(cf (implode (cons '! (explode f))))) ;;
`(defun ,cf (&rest x)
(let ((lx (length x))) ;;
(cond ((= lx ,lp) ;;
(let ((e `(lambda ,parmlist ,@body)))
(apply e x)))
((> lx ,lp) ;;
(raiseerror "curry: "))
(t (let ((tmp nil)) ;;
(iter (for a in x) ;;
(setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))
tmp)))))))
Il vaut la peine de commenter la construction du nouveau nom de fonction ici. Pour ce faire, utilisez les fonctions d'éclatement de HomeLisp, qui construit une liste de ses symboles constitutifs à partir d'un atome, et implosent, ce qui compresse les symboles de la liste en un seul, donnant naissance à un nouvel atome.
Voyons maintenant notre macro en action:
(curry g) ;; g
==> !G ;;
(!g 1 2 3) ;;
==> 9 ;; g
(!g 1 2) ;; -
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
;; :
((!g 1 2) 3) ;;
==> 9
((!g 1) 2 3) ;;
==> 9
(!g 1 2 3 4) ;;
curry:
==> ERRSTATE
Le curry a été fait sans contrôle supplémentaire. Et nous n'avons pas implémenté l'expression lambda de curry. Si vous le souhaitez, vous pouvez faire tout cela ...
C'est ainsi que vous pouvez implémenter une application de fonction partielle et un currying en Lisp sans trop d'effort. Lisp est un langage merveilleux!
Merci de votre attention.