Tiago Charters Azevedo Index Faz qualquer coisa Dose Diária Recomendada Notas sobre diy

Diferenciando funções (cont.)

A implementação da função de John McCarthy definida na entrada anterior (que aqui se repete) levantou, no meu espírito, algumas questões. A afirmação final

Basta apenas escrever uma outra função que simplifica o output para ficar completa...

não deixa de ser curiosa e é reveladora da minha ignorância sobre algoritmos de manipulação simbólica.

(defun differentiate (y x)
  "Calculates the derivative of y as a function of x. Only for polynomials y=P(x)
written in prefix notation."
  (cond ((atom y)
         (cond ((eq x y)
                1)
               (t
                0)))
        ((eq (car y) '+)
         (cons '+ (maplist (lambda (z)
                             (differentiate (car z) x))
                           (cdr y))))
        ((eq (car y) '*)
         (cons '+ (maplist (lambda (z)
                             (cons '* (maplist (lambda (w) (if (not (eq z w))
                                                               (car w)
                                                             (differentiate (car w) x)))
                                               (cdr y))))
                           (cdr y))))))

Uma pesquisa rápida pela rede revela imediatamente quais as dificuldades inerentes à implementação de uma tal vontade. O livro Structure and Interpretation of Computer Programs (SICP) na página 149 tem uma resposta parcial a este problema.

Consideremos então a seguinte versão em Common Lisp do código do SICP:

(defun derive (y x)
  (cond ((atom y)
         (cond ((eq y x) 1)
               (t 0)))
        ((eq (car y) '+)
         (bin-sum (derive (cadr y) x)
                  (derive (caddr y) x)))
        ((eq (car y) '*)
         (bin-sum
          (bin-product (cadr y)
                       (derive (caddr y) x))
          (bin-product (derive (cadr y) x)
                       (caddr y))))))

Esta função implementa de uma forma mais explicita as regras de derivação usuais e depende de duas outras funções bin-sum e bin-product que não fazem mais do que, respectivamente, somar ou multiplicar dois números:

(defun bin-sum (a b)
  (list '+ a b))

(defun bin-product (a b)
  (list '* a b))

ou antes retornam, respectivamente, as listas (+ u v) e (* u v), não fazem a operação nem mesmo quando u e v são números. Por exemplo

> (bin-sum 1 2)

(+ 1 2)

e

> (bin-product 1 2)

(* 1 2)

Assim usando a função derive para calcular a derivada de (+ (* 1 x) x) dá

> (derive '(+ (* 1 x) x) 'x)

(+ (+ (* 1 1) (* 0 x)) 1)

que é uma forma, no mínimo, pouco usual de escrever o número 2. Pode-se através da modificação das funções bin-sum e bin-product obter uma simplificação razoável das expressões das derivadas obtidas através de derive. Tomemos as seguintes novas definições para essas funções

(defun bin-sum (a b)
  (cond ((eq a 0) b)
        ((eq b 0) a)
        ((and (numberp a) (numberp b))
         (+ a b))
        (t
         (list '+ a b))))

(defun bin-product (a b)
  (cond ((eq a 0) 0)
        ((eq b 0) 0)
        ((eq a 1) b)
        ((eq b 1) a)
        ((and (numberp a) (numberp b))
         (* a b))
        (t
         (list '* a b))))

Assim, agora temos,

> (bin-sum 1 2)

3

e

> (bin-product 1 2)

2

e ainda

> (bin-sum 1 'x)

(+ 1 x)

e

> (bin-product 1 'x)

x

Voltando a concretizar o exemplo da derivada de (+ (* 1 x) x) 'x)

> (derive '(+ (* 1 x) x) 'x)

2

A substituição das funções bin-sum e bin-product por estas novas versões resolve o problema. No entanto, como mostra o exemplo seguinte, ainda falta muito para se conseguir uma expressão final "simples"; a simplicidade é relativa e depende muito da utilização final que se que dar à derivada calculada.

> (derive '(* (* (+ 1 x) (+ x 3)) 1) 'x)

(+ (+ 1 x) (+ x 3))

Palavras chave/keywords: Emacs Lisp, diff, John McCarthy, Common Lisp, regras de simplificação

---

Voltar à página inicial.

---

(c) Tiago Charters de Azevedo