Nesta breve nota, veremos como você pode implementar no Lisp mecanismos de software agora muito populares, como aplicação parcial e currying de funções. Ao fazer isso, usarei minha implementação Homelisp (este é um interpretador Lisp puro com alguns recursos adicionais).
Usar a aplicação parcial em Common Lisp é provavelmente complicado (porque você precisa usar funcall / apply para invocar um objeto de função computado); no esquema deve ser mais fácil. Eu pretendo postar uma nova versão do HomeLisp em breve, que não requer funcall / apply para chamar um objeto de função computada. Nos casos em que o comportamento do código é diferente, vou enfatizar isso.
A aplicação parcial e o currying são operações matemáticas estritas. Mas vamos considerá-los "nos dedos", sem recorrer ao cálculo lambda e à lógica combinatória.
Uma aplicação parcial da função f é obter da função f uma nova função f 'que já recebeu os argumentos fornecidos e está pronta para aceitar o resto. Para que serve a aplicação parcial? Por exemplo, para que um valor funcional possa ser retornado de uma função.
Vamos considerar um aplicativo parcial com um exemplo simples. Deixe a função f ser dada pela fórmula:
f (x, y, z) = x + y ** 2 + z ** 3
então a aplicação parcial desta função com argumentos x = 1 ey = 2 deve gerar a função:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
Em Haskell, a aplicação parcial não custa nada ao 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
No entanto, em Lisp, esta tentativa irá falhar:
(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
Claro, Lisp tem um mecanismo para criar funções com qualquer número de argumentos (a construção & rest); você pode criar uma função que terá dois ou três (ou dez) parâmetros:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
Mas é importante entender a diferença: esta função processa todos os parâmetros e retorna o resultado do cálculo, enquanto a aplicação parcial resulta em uma nova função que está "pronta para continuar o cálculo".
Vamos ver como podemos implementar um mecanismo de aplicação de função parcial em Lisp. E vai nos ajudar nisso ... sim, o aparato de funções anônimas (lambda). Alguns programadores pensam que funções anônimas são necessárias apenas para salvar nomes (eles dizem, seu lugar em qualquer mapa de fluxo-filtro-reduzir a fim de realizar uma ação curta em um elemento de sequência). Na verdade, as funções anônimas são capazes de muito mais, o que veremos agora.
Vamos começar examinando como uma função pode retornar outra função como resultado. Em Lisp, é muito simples:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Como você pode ver, a função retorna um fechamento no qual o valor da variável livre x é fixo (igual a 5). O resultado de uma função pode ser chamado como uma função. Para fazer isso, em Common Lisp e HomeLisp (com revisão do kernel <= 13.53), você terá que usar funcall:
(funcall (func-gen 5) 7)
==> 54
Agora está claro como podemos proceder se quisermos obter uma função f de n argumentos e um valor de x, e como resultado obter uma função de (n-1) argumentos. Vamos denotar a lista de parâmetros formais de nossa função por plist. Então, tudo que você precisa fazer é construir uma expressão lambda como esta:
(lambda (-plist) (apply f (cons x -plist)))
A ideia é muito simples: construímos uma expressão lambda, no corpo da qual simplesmente chamamos a função original na lista de parâmetros, na qual o cabeçalho é substituído pelo valor de x.
Isso significa que para a aplicação parcial da função, você precisa construir uma expressão lambda com base nesta função, que terá um argumento a menos, e o argumento especificado durante a aplicação parcial será "levado em consideração" na chamada interna de nossa função no corpo da expressão lambda.
Como implementar isso? Fácil ... HomeLisp tem uma função getd que fornece acesso à expressão de definição de uma função ou macro:
(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 você pode ver, getd retorna a expressão de definição da função, na qual "em vez de" o lambda há um átomo EXPR especial. Podemos pegar a lista de parâmetros de nossa função (o segundo elemento do resultado) e construir uma expressão lambda, cujos parâmetros serão a cauda da lista de parâmetros original, e no corpo da expressão lambda chamaremos a função original com a 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)))))
É fácil entender a partir do código acima que plist é a lista original da função f que queremos aplicar parcialmente. rlist é a lista original sem o primeiro elemento e clist é a lista completa de parâmetros, com o primeiro elemento substituído por x. Especificamente, para a função g acima, plist = (xyz), rlist = (yz) e clist = (ayz). Agora vamos verificar como funciona o aplicativo parcial:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Você pode ter certeza de que isso é exatamente o que foi planejado: part-apply retornou uma nova função, com um número a menos de argumentos. Se esta nova função for chamada com os parâmetros y e z, o resultado será exatamente o mesmo que chamar a função original g com três argumentos: 111 y e z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Abaixo de I (por brevidade) não especificarei funcall. No próximo núcleo do HomeLisp, o esquema para funções de cálculo será alterado - a sintaxe do "esquema" ficará disponível.
Vamos mais longe. Haverá agora um desejo natural de reaplicar o resultado da reaplicação. Isso é bastante simples - afinal, o resultado da aplicação parcial é uma expressão lambda, e ela é estruturada quase idêntica ao resultado retornado por getd. A lista de parâmetros da expressão lambda é o segundo item da lista. Todas essas considerações nos permitem construir a solução final para o 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: "))))
Adiciona-se aqui a análise do primeiro parâmetro: se é um átomo, deve "representar" uma função (do tipo EXPR); se o primeiro parâmetro não for um átomo "válido" ou uma expressão lambda, será gerada uma condição de erro. O código, é claro, poderia ser ainda mais reduzido, dois ramos quase idênticos são deixados para maior clareza. Agora vamos ver do que essa função é capaz:
(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
Agora vamos currying. Uma função curried, aceitando um número insuficiente de argumentos, retorna uma função que pode lidar com o resto. O principal objetivo do currying é fornecer uma aplicação parcial. Fomos do outro lado: agora vamos ver como o currying pode ser implementado se houver uma aplicação parcial.
Deixe uma função g de vários argumentos ser fornecida. Vamos construir uma versão curry com um nome diferente! G. A essência da construção será a seguinte: a função! G terá um número indefinido de argumentos. Após a chamada, ele deve verificar o número de argumentos passados. Se este número for igual ao número de argumentos da função original g, então de deve ser passado para a entrada g. Se houver mais argumentos do que g pode aceitar, uma condição de erro deve ser levantada. Mas se o número de argumentos for menor que o da função g, então ... sim, sim - você precisa executar uma aplicação parcial sequencial. Retorne o resultado desta aplicação.
Nesse caso, é conveniente usar uma macro. O código com comentários está abaixo:
(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 a pena comentar aqui a construção do novo nome da função. Para fazer isso, use as funções de explosão HomeLisp, que cria uma lista de seus símbolos constituintes a partir de um átomo, e implode, que compacta os símbolos da lista em um, criando um novo átomo.
Agora vamos verificar nossa macro em ação:
(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
Currying foi feito sem controle adicional. E não implementamos a expressão lambda currying. Você pode fazer tudo se quiser ...
É assim que você pode implementar a aplicação de função parcial e currying em Lisp sem muito esforço. Lisp é uma linguagem maravilhosa!
Obrigado pela atenção.