En esta breve nota, veremos cómo puede implementar en Lisp mecanismos de software tan populares en la actualidad como la aplicación parcial y el procesamiento de funciones. Al hacerlo, usaré mi implementación de Homelisp (este es un intérprete Lisp puro con algunas características adicionales).
Es probable que el uso de una aplicación parcial en Common Lisp sea un poco complicado (ya que funcall / apply debe usarse para invocar un objeto de función calculada); en Scheme debería ser más fácil. Planeo publicar una nueva versión de HomeLisp pronto, que no requiere funcall / apply para llamar a un objeto de función calculada. En los casos en que el comportamiento del código sea diferente, enfatizaré esto.
La aplicación parcial y el curado son operaciones matemáticas estrictas. Pero los consideraremos "en los dedos", sin recurrir al cálculo lambda y la lógica combinatoria.
Una aplicación parcial de la función f es obtener de la función f una nueva función f 'que ya ha tomado los argumentos dados y está lista para aceptar el resto. ¿Para qué sirve la solicitud parcial? Por ejemplo, para que una función pueda devolver un valor funcional.
Consideremos una aplicación parcial con un ejemplo simple. Sea la función f dada por la fórmula:
f (x, y, z) = x + y ** 2 + z ** 3
entonces la aplicación parcial de esta función con argumentos x = 1 y y = 2 debería generar la función:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
En Haskell, la aplicación parcial no le cuesta nada al programador:
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
Sin embargo, en Lisp este intento fallará:
(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
Por supuesto, Lisp tiene un mecanismo para crear funciones con cualquier número de argumentos (la construcción & rest); puede crear una función que tome dos o tres (o diez) parámetros:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
Pero es importante entender la diferencia: esta función procesa todos los parámetros y devuelve el resultado del cálculo, mientras que la aplicación parcial da como resultado una nueva función que está “lista para continuar con el cálculo”.
Veamos cómo puede implementar un mecanismo de aplicación de función parcial en Lisp. Y nos ayudará con eso ... sí, el aparato de funciones anónimas (lambda). Algunos programadores piensan que las funciones anónimas son necesarias solo para guardar nombres (dicen, su lugar en cualquier stream-map-filter-reduce para realizar una acción corta en un elemento de secuencia). De hecho, las funciones anónimas son capaces de mucho más, lo que veremos ahora.
Comencemos viendo cómo una función puede devolver otra función como resultado. En Lisp, es muy simple:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Como puede ver, la función devuelve un cierre en el que el valor de la variable libre x es fijo (igual a 5). El resultado de una función se puede llamar como una función. Para hacer esto, en Common Lisp y HomeLisp (con revisión del kernel <= 13.53), tendrá que usar funcall:
(funcall (func-gen 5) 7)
==> 54
Ahora está claro cómo podemos proceder si queremos tomar una función f de n argumentos y un valor de x, y como resultado obtener una función de (n-1) argumentos. Denotemos la lista de parámetros formales de nuestra función como plist. Entonces todo lo que tienes que hacer es construir una expresión lambda como esta:
(lambda (-plist) (apply f (cons x -plist)))
La idea es muy simple: construimos una expresión lambda, en el cuerpo del cual simplemente llamamos a la función original en la lista de parámetros, en la que la cabeza se reemplaza con el valor de x.
Esto significa que para la aplicación parcial de la función, debe crear una expresión lambda basada en esta función, que tendrá un argumento menos, y el argumento especificado durante la aplicación parcial se "tendrá en cuenta" en la llamada interna de nuestra función en el cuerpo de la expresión lambda.
¿Cómo implementar esto? Fácil ... HomeLisp tiene una función getd que proporciona acceso a la expresión o macro que define una función:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
Como puede ver, getd devuelve la expresión definitoria de la función, en la que "en lugar de" la lambda hay un átomo EXPR especial. Podemos tomar la lista de parámetros de nuestra función (el segundo elemento del resultado) y construir una expresión lambda, cuyos parámetros serán la cola de la lista de parámetros original, y en el cuerpo de la expresión lambda llamaremos a la función original con la lista completa de parámetros.
(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)))))
A partir del código anterior, es fácil entender que plist es la lista original de la función f que queremos aplicar parcialmente. rlist es la lista original sin el primer elemento, y clist es la lista completa de parámetros, con el primer elemento reemplazado por x. Específicamente, para la función g anterior, plist = (xyz), rlist = (yz) y clist = (ayz). Ahora veamos cómo funciona la aplicación parcial:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Puede ver que esto es exactamente lo que se planeó: part-apply devolvió una nueva función, con un número menos de argumentos. Si esta nueva función se llama con los parámetros y y z, el resultado es exactamente el mismo que llamar a la función original g con tres argumentos: 111 y y z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Debajo de I (por brevedad) no especificaré funcall. En el siguiente núcleo de HomeLisp, se cambiará el esquema para calcular funciones: la sintaxis del "esquema" estará disponible.
Vayamos más lejos. Ahora habrá un deseo natural de volver a aplicar el resultado de la nueva aplicación. Esto resulta ser bastante simple; después de todo, el resultado de la aplicación parcial es una expresión lambda y está estructurada casi idéntica al resultado devuelto por getd. La lista de parámetros de la expresión lambda es el segundo elemento de la lista. Todas estas consideraciones nos permiten construir la solución final al problema:
(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: "))))
Aquí se agrega el análisis del primer parámetro: si es un átomo, entonces debe "representar" una función (de tipo EXPR); si el primer parámetro no es un átomo "válido" ni una expresión lambda, se genera una condición de error. El código, por supuesto, podría acortarse aún más, se dejan dos ramas casi idénticas para mayor claridad. Ahora veamos de qué es capaz esta función:
(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
Ahora hagamos el curry. Una función curry, que acepta un número insuficiente de argumentos, devuelve una función que puede manejar el resto. El propósito principal del curado es proporcionar una aplicación parcial. Pasamos del otro extremo: ahora veamos cómo se puede implementar el curry si hay una aplicación parcial.
Sea una función g de varios argumentos. ¡Construiremos una versión al curry con un nombre diferente! G. La esencia de la construcción será la siguiente: la función! G tomará un número indefinido de argumentos. Después de la llamada, debe verificar el número de argumentos pasados. Si este número es igual al número de argumentos de la función original g, entonces debe pasarse from a la entrada g. Si hay más argumentos de los que puede aceptar g, se debe generar una condición de error. Pero si el número de argumentos es menor que el de la función g, entonces ... sí, necesita realizar una aplicación parcial secuencial. Devuelve el resultado de esta aplicación.
En este caso, es conveniente utilizar una macro. El código con comentarios está a continuación:
(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)))))))
Vale la pena comentar sobre la construcción del nuevo nombre de función aquí. Para hacer esto, use las funciones de explosión de HomeLisp, que crea una lista de sus símbolos constituyentes a partir de un átomo, e implosión, que comprime los símbolos de la lista en uno, creando un nuevo átomo.
Ahora veamos nuestra macro en acción:
(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
El curry se realizó sin control adicional. Y no hemos implementado la expresión de curry lambda. Si lo desea, puede hacer todo esto ...
Así es como puede implementar la aplicación de funciones parciales y el procesamiento en Lisp sin mucho esfuerzo. ¡Lisp es un idioma maravilloso!
Gracias por su atención.