Abstração Metalinguística

A homoiconicidade de Scheme foi brevemente mencionada na seção introdutória. Vejamos agora como utilizar essa característica para facilmente produzir procedimentos. Assim, estaremos utilizando Scheme como uma metalinguagem para Scheme, podendo enfim afirmar que ela é uma linguagem metacircular, ou seja, capaz de falar sobre ela mesma.

Processamento Simbólico

O procedimento eval (complementado por apply) é a principal ferramenta para abstração metalinguística em Scheme. Para utilizá-lo, basta fornecer uma expressão simbólica válida e um objeto representando o ambiente computacional onde ela será avaliada; o retorno de eval será o valor resultante da interpretação daquela expressão.

(define env (scheme-report-environment 5))

'(+ 1 1)              ; => (+ 1 1)
(list '+ 1 1)         ; => (+ 1 1)
(+ 1 1)               ; => 2
(eval '(+ 1 1) env)   ; => 2

(define x 7)
(define y 5)
'(- x y)              ; => (- x y)
(list '- x y)         ; => (- 7 5)
(- x y)               ; => 2
`(- ,x ,y)            ; => (- 7 5)
(eval `(- ,x ,y) env) ; => 2
(eval '(- x y) env)   ; => Unbound variable: x

Com base nos exemplos anteriores, explique como funcionam as citações parciais com os símbolos ` e ,

O método de Horner costuma ser utilizado para calcular o valor de um polinômio de forma a evitar exponenciações; efetua apenas n adições e n multiplicações para um polinômio de grau n.

\[ Pn(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n \] \[ Pn(x) = a_0 + x (a_1 + x (a_2 + x(...a_n...))) \]

Vamos aplicar o método de uma maneira um tanto não-convencional, em um algoritmo que "compila" uma lista de coeficientes e gera um procedimento que calcula o polinômio equivalente na forma de Horner:

(define (horner x pn)
    (if (null? (cdr pn))
        (car pn)
        `(+ ,(car pn) (* ,x ,(horner x (cdr pn))))))

(define (make-polynomial x first-coef . rest-coefs)
  (let ((polynomial (horner x (cons first-coef rest-coefs))))
    (eval
      (list 'lambda (list x) polynomial)
      (interaction-environment))))

Diferenciação Analítica

Um outra maneira de utilizar Scheme como metalinguagem circular é na obtenção da derivada analítica de uma função. Nesse caso, não é o procedimento que computa a função que é passado ao gerador (como era o caso na diferenciação numérica utilizada no método de Newton de uma seção anterior), mas sim uma descrição de como seria o código desse procedimento na linguagem Scheme.

(define (differentiate var sexpr)
  (cond ((number? sexpr) 0)
        ((variable? sexpr)
         (if (same-variable? sexpr var) 1 0))
        ((sum? sexpr)
         (make-sum (differentiate var (augend sexpr))
                   (differentiate var (addend sexpr))))
        ((product? sexpr)
         (make-sum
           (make-product (multiplier sexpr)
                         (differentiate var (multiplicand sexpr)))
           (make-product (differentiate var (multiplier sexpr))
                         (multiplicand sexpr))))
        (else
         (error "unknown expression type -- DERIV" sexpr))))

(define (make-derivative var sexpr)
  (let ((deriv (differentiate var sexpr)))
    (eval
      `(lambda (,var) ,deriv)
      (interaction-environment))))


(define (variable? x)
  (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum augend addend)
  (cond ((and (number? addend) (number? augend)) (+ augend addend))
        ((and (number? augend) (= augend 0)) addend)
        ((and (number? addend) (= addend 0)) augend)
        (else (list '+ augend addend))))

(define (sum? x)
  (and (list? x) (eq? (car x) '+)))

(define (augend s)
  (cadr s))

(define (addend s)
  (caddr s))

(define (make-product multiplier multiplicand)
  (define (=number? sexpr num)
    (and (number? sexpr) (= sexpr num)))
  (cond ((or (=number? multiplier 0) (=number? multiplicand 0))
          0)
        ((and (number? multiplier) (number? multiplicand))
          (* multiplier multiplicand))
        ((=number? multiplier 1) multiplicand)
        ((=number? multiplicand 1) multiplier)
        (else (list '* multiplier multiplicand))))

(define (product? x)
  (and (list? x) (eq? (car x) '*)))

(define (multiplier p)
  (cadr p))

(define (multiplicand p)
  (caddr p))

Adicione mais algumas regras de diferenciação no programa acima.

A partir do código dado temos um sistema capaz de gerar procedimentos que computam polinômios arbitrários (de uma variável independente), assim como suas derivadas (incluindo derivadas parciais).

(define coefs '(-1 -1 1))

(define p
  (apply horner
         (list 'x coefs))) ;; p = x^2 - x - 1

(define f
  (apply make-polynomial
         (cons 'x coefs))) ;; f(x) = p(x)

(define df
  (make-derivative 'x p))  ;; df(x) = p'(x) = 2x - 1

Pense sobre como seria possível expandir esse programa para permitir a geração de polinômios multivariados. Você pode discutir suas ideias na seção de comentários desse site.