1.3Formulando Abstrações com Procedimentos de Ordem Superior

Vimos que procedimentos são, na verdade, abstrações que descrevem operações compostas sobre números, independentemente dos números particulares. Por exemplo, quando definimos:

(define (cube x) (* x x x))

Não estamos falando sobre o cubo de um número específico, mas sim sobre um método para obter o cubo de qualquer número. Claro, poderíamos viver sem nunca definir esse procedimento, sempre escrevendo expressões como:

(* 3 3 3)
(* x x x)
(* y y y)

E nunca mencionando explicitamente cube. Isso nos colocaria em uma séria desvantagem, forçando-nos a trabalhar sempre no nível das operações particulares que são primitivas na linguagem (multiplicação, neste caso), em vez de termos operações de nível mais alto. Nossos programas seriam capazes de calcular cubos, mas nossa linguagem careceria da capacidade de expressar o conceito de cubagem. Uma das coisas que devemos exigir de uma linguagem de programação poderosa é a capacidade de construir abstrações, atribuindo nomes a padrões comuns e, em seguida, trabalhar diretamente em termos dessas abstrações. Procedimentos fornecem essa capacidade. É por isso que todas as linguagens de programação, exceto as mais primitivas, incluem mecanismos para definir procedimentos.

No entanto, mesmo no processamento numérico, seremos severamente limitados em nossa capacidade de criar abstrações se estivermos restritos a procedimentos cujos parâmetros devem ser números. Muitas vezes, o mesmo padrão de programação será usado com vários procedimentos diferentes. Para expressar tais padrões como conceitos, precisaremos construir procedimentos que possam aceitar procedimentos como argumentos ou retornar procedimentos como valores. Procedimentos que manipulam procedimentos são chamados de procedimentos de ordem superior. Esta seção mostra como procedimentos de ordem superior podem servir como mecanismos poderosos de abstração, aumentando enormemente o poder expressivo de nossa linguagem.

1.3.1Procedimentos como Argumentos

Considere os seguintes três procedimentos. O primeiro calcula a soma dos inteiros de a até b:

(define (sum-integers a b)
  (if (> a b) 
      0 
      (+ a (sum-integers (+ a 1) b))))

O segundo calcula a soma dos cubos dos inteiros no intervalo dado:

(define (sum-cubes a b)
  (if (> a b) 
      0 
      (+ (cube a) 
         (sum-cubes (+ a 1) b))))

O terceiro calcula a soma de uma sequência de termos na série:

que converge para $\mathrm{\pi <!--\; \pi \; -->}/8$ (muito lentamente):⁴⁹

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) 
         (pi-sum (+ a 4) b))))

Esses três procedimentos compartilham claramente um padrão subjacente comum. Eles são, na maior parte, idênticos, diferindo apenas no nome do procedimento, na função de a usada para calcular o termo a ser adicionado e na função que fornece o próximo valor de a. Poderíamos gerar cada um dos procedimentos preenchendo espaços no mesmo modelo:

(define (⟨name⟩ a b)
  (if (> a b)
      0
      (+ (⟨term⟩ a) 
         (⟨name⟩ (⟨next⟩ a) b))))

A presença de tal padrão comum é uma forte evidência de que há uma abstração útil esperando para ser trazida à tona. De fato, os matemáticos há muito identificaram a abstração da somação de uma série e inventaram a “notação sigma”, por exemplo:

para expressar esse conceito. O poder da notação sigma é que ela permite que os matemáticos lidem com o conceito de soma em si, em vez de apenas com somas particulares — por exemplo, para formular resultados gerais sobre somas que são independentes da série particular que está sendo somada.

Da mesma forma, como projetistas de programas, gostaríamos que nossa linguagem fosse poderosa o suficiente para que pudéssemos escrever um procedimento que expressasse o conceito de soma em si, em vez de apenas procedimentos que calculam somas particulares. Podemos fazer isso facilmente em nossa linguagem procedural, tomando o modelo comum mostrado acima e transformando os “espaços” em parâmetros formais:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

Observe que sum recebe como argumentos os limites inferior e superior a e b, juntamente com os procedimentos term e next. Podemos usar sum como usaríamos qualquer procedimento. Por exemplo, podemos usá-lo (junto com um procedimento inc que incrementa seu argumento em 1) para definir sum-cubes:

(define (inc n) (+ n 1))

(define (sum-cubes a b)
  (sum cube a inc b))

Usando isso, podemos calcular a soma dos cubos dos inteiros de 1 a 10:

(sum-cubes 1 10)
3025

Com a ajuda de um procedimento de identidade para calcular o termo, podemos definir sum-integers em termos de sum:

(define (identity x) x)

(define (sum-integers a b)
  (sum identity a inc b))

Então podemos somar os inteiros de 1 a 10:

(sum-integers 1 10)
55

Também podemos definir pi-sum da mesma maneira:⁵⁰

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

Usando esses procedimentos, podemos calcular uma aproximação de $\mathrm{\pi <!--\; \pi \; -->}$:

(* 8 (pi-sum 1 1000))
3.139592655589783

Uma vez que temos sum, podemos usá-lo como um bloco de construção na formulação de conceitos adicionais. Por exemplo, a integral definida de uma função $f$ entre os limites $a$ e $b$ pode ser aproximada numericamente usando a fórmula:

para pequenos valores de $dx$. Podemos expressar isso diretamente como um procedimento:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b) 
     dx))

(integral cube 0 1 0.01)
.24998750000000042

(integral cube 0 1 0.001)
.249999875000001

(O valor exato da integral de cube entre 0 e 1 é 1/4.)

Exercício 1.29: A Regra de Simpson é um método mais preciso de integração numérica do que o método ilustrado acima. Usando a Regra de Simpson, a integral de uma função $f$ entre $a$ e $b$ é aproximada como:

$$\frac{h}{3}(y_0+4y_1+2y_2+4y_3+2y_4+\cdots <!--\; \cdots \; -->+2y_{n-<!--\; -\; -->2}+4y_{n-<!--\; -\; -->1}+y_n),$$

onde $h=(b-<!--\; -\; -->a)/n$, para algum inteiro par $n$, e $y_k=f(a+kh)$. (Aumentar $n$ aumenta a precisão da aproximação.) Defina um procedimento que recebe como argumentos $f$, $a$, $b$ e $n$ e retorna o valor da integral, calculado usando a Regra de Simpson. Use seu procedimento para integrar cube entre 0 e 1 (com $n=100$ e $n=1000$), e compare os resultados com os do procedimento integral mostrado acima.

Exercício 1.30: O procedimento sum acima gera uma recursão linear. O procedimento pode ser reescrito para que a soma seja realizada iterativamente. Mostre como fazer isso preenchendo as expressões ausentes na seguinte definição:

(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))

Exercício 1.31:

1. O procedimento sum é apenas o mais simples de um vasto número de abstrações semelhantes que podem ser capturadas como procedimentos de ordem superior.⁵¹ Escreva um procedimento análogo chamado product que retorna o produto dos valores de uma função em pontos sobre um determinado intervalo. Mostre como definir factorial em termos de product. Também use product para calcular aproximações de $\mathrm{\pi <!--\; \pi \; -->}$ usando a fórmula⁵²:

$$\frac{\mathrm{\pi <!--\; \pi \; -->}}{4}=\frac{2\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->6\cdot <!--\; \cdot \; -->6\cdot <!--\; \cdot \; -->8\cdot <!--\; \cdot \; -->\cdots <!--\; \cdots \; -->}{3\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->\cdots <!--\; \cdots \; -->}.$$

Se o seu procedimento product gerar um processo recursivo, escreva um que gere um processo iterativo. Se ele gerar um processo iterativo, escreva um que gere um processo recursivo.

Exercício 1.32:

1. Mostre que sum e product (Exercício 1.31) são ambos casos especiais de uma noção ainda mais geral chamada accumulate que combina uma coleção de termos, usando alguma função de acumulação geral:

(accumulate 
 combiner null-value term a next b)

Accumulate recebe como argumentos as mesmas especificações de termo e intervalo que sum e product, juntamente com um procedimento combiner (de dois argumentos) que especifica como o termo atual deve ser combinado com a acumulação dos termos anteriores e um null-value que especifica qual valor base usar quando os termos se esgotarem. Escreva accumulate e mostre como sum e product podem ser definidos como chamadas simples para accumulate.

Se o seu procedimento accumulate gerar um processo recursivo, escreva um que gere um processo iterativo. Se ele gerar um processo iterativo, escreva um que gere um processo recursivo.

Exercício 1.33: Você pode obter uma versão ainda mais geral de accumulate (Exercício 1.32) introduzindo a noção de um filtro nos termos a serem combinados. Ou seja, combine apenas os termos derivados de valores no intervalo que satisfazem uma condição especificada. A abstração resultante filtered-accumulate recebe os mesmos argumentos que accumulate, juntamente com um predicado adicional de um argumento que especifica o filtro. Escreva filtered-accumulate como um procedimento. Mostre como expressar o seguinte usando filtered-accumulate:

1. A soma dos quadrados dos números primos no intervalo de $a$ a $b$ (assumindo que você já tenha um predicado prime? escrito).
2. O produto de todos os inteiros positivos menores que $n$ que são relativamente primos a $n$ (ou seja, todos os inteiros positivos $i<n$ tais que $\text{GCD}(i,n)=1$).

1.3.2Construindo Procedimentos Usando Lambda

Ao usar sum como em 1.3.1, parece muito incômodo ter que definir procedimentos triviais como pi-term e pi-next apenas para que possamos usá-los como argumentos para nosso procedimento de ordem superior. Em vez de definir pi-next e pi-term, seria mais conveniente ter uma maneira de especificar diretamente “o procedimento que retorna sua entrada incrementada em 4” e “o procedimento que retorna o recíproco de sua entrada vezes sua entrada mais 2”. Podemos fazer isso introduzindo a forma especial lambda, que cria procedimentos. Usando lambda, podemos descrever o que queremos como:

(lambda (x) (+ x 4))

e

(lambda (x) (/ 1.0 (* x (+ x 2))))

Então, nosso procedimento pi-sum pode ser expresso sem definir nenhum procedimento auxiliar como:

(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))

Novamente usando lambda, podemos escrever o procedimento integral sem ter que definir o procedimento auxiliar add-dx:

(define (integral f a b dx)
  (* (sum f (+ a (/ dx 2.0))
            (lambda (x) (+ x dx))
            b) 
     dx))

Em geral, lambda é usado para criar procedimentos da mesma forma que define, exceto que nenhum nome é especificado para o procedimento:

(lambda (⟨formal-parameters⟩) ⟨body⟩)

O procedimento resultante é tão procedimento quanto um que é criado usando define. A única diferença é que ele não foi associado a nenhum nome no ambiente. Na verdade,

(define (plus4 x) (+ x 4))

é equivalente a

(define plus4 (lambda (x) (+ x 4)))

Podemos ler uma expressão lambda da seguinte forma:

(lambda                     (x)     (+   x     4))
    |                        |       |   |     |
o procedimento de um argumento x que adiciona x e 4

Como qualquer expressão que tem um procedimento como seu valor, uma expressão lambda pode ser usada como o operador em uma combinação, como:

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

ou, mais geralmente, em qualquer contexto onde normalmente usaríamos um nome de procedimento.⁵³

Usando let para criar variáveis locais

Outro uso de lambda é na criação de variáveis locais. Muitas vezes precisamos de variáveis locais em nossos procedimentos além daquelas que foram vinculadas como parâmetros formais. Por exemplo, suponha que desejemos calcular a função:

que também poderíamos expressar como:

Ao escrever um procedimento para calcular $f$, gostaríamos de incluir como variáveis locais não apenas $x$ e $y$, mas também os nomes de quantidades intermediárias como $a$ e $b$. Uma maneira de conseguir isso é usar um procedimento auxiliar para vincular as variáveis locais:

(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y)) 
            (- 1 y)))

Claro, poderíamos usar uma expressão lambda para especificar um procedimento anônimo para vincular nossas variáveis locais. O corpo de f então se torna uma única chamada para esse procedimento:

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a)) 
        (* y b) 
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

Essa construção é tão útil que há uma forma especial chamada let para tornar seu uso mais conveniente. Usando let, o procedimento f poderia ser escrito como:

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

A forma geral de uma expressão let é:

(let ((⟨var₁⟩ ⟨exp₁⟩)
      (⟨var₂⟩ ⟨exp₂⟩)
      …
      (⟨varₙ⟩ ⟨expₙ⟩))
  ⟨body⟩)

que pode ser pensada como dizendo:

let ⟨var₁⟩ tenha o valor ⟨exp₁⟩ e
    ⟨var₂⟩ tenha o valor ⟨exp₂⟩ e
    …
    ⟨varₙ⟩ tenha o valor ⟨expₙ⟩
  em ⟨body⟩

A primeira parte da expressão let é uma lista de pares nome-expressão. Quando o let é avaliado, cada nome é associado ao valor da expressão correspondente. O corpo do let é avaliado com esses nomes vinculados como variáveis locais. A maneira como isso acontece é que a expressão let é interpretada como uma sintaxe alternativa para:

((lambda (⟨var₁⟩ … ⟨varₙ⟩)
   ⟨body⟩)
 ⟨exp₁⟩
 …
 ⟨expₙ⟩)

Nenhum novo mecanismo é necessário no interpretador para fornecer variáveis locais. Uma expressão let é simplesmente açúcar sintático para a aplicação subjacente de lambda.

Podemos ver a partir dessa equivalência que o escopo de uma variável especificada por uma expressão let é o corpo do let. Isso implica que:

• Let permite vincular variáveis o mais localmente possível ao local onde elas serão usadas. Por exemplo, se o valor de x é 5, o valor da expressão:

(+ (let ((x 3))
     (+ x (* x 10)))
   x)

é 38. Aqui, o x no corpo do let é 3, então o valor da expressão let é 33. Por outro lado, o x que é o segundo argumento para o + mais externo ainda é 5.

• Os valores das variáveis são computados fora do let. Isso importa quando as expressões que fornecem os valores para as variáveis locais dependem de variáveis que têm os mesmos nomes que as variáveis locais. Por exemplo, se o valor de x é 2, a expressão:

(let ((x 3)
      (y (+ x 2)))
  (* x y))

terá o valor 12 porque, dentro do corpo do let, x será 3 e y será 4 (que é o x externo mais 2).

Às vezes, podemos usar definições internas para obter o mesmo efeito que com let. Por exemplo, poderíamos ter definido o procedimento f acima como:

(define (f x y)
  (define a 
    (+ 1 (* x y)))
  (define b (- 1 y))
  (+ (* x (square a))
     (* y b)
     (* a b)))

No entanto, preferimos usar let em situações como essa e usar define interno apenas para procedimentos internos.⁵⁴

Exercício 1.34: Suponha que definamos o procedimento:

(define (f g) (g 2))

Então temos:

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

O que acontece se (perversamente) pedirmos ao interpretador para avaliar a combinação (f f)? Explique.

1.3.3Procedimentos como Métodos Gerais

Introduzimos procedimentos compostos em 1.1.4 como um mecanismo para abstrair padrões de operações numéricas, de modo a torná-los independentes dos números particulares envolvidos. Com procedimentos de ordem superior, como o procedimento integral de 1.3.1, começamos a ver um tipo mais poderoso de abstração: procedimentos usados para expressar métodos gerais de computação, independentes das funções particulares envolvidas. Nesta seção, discutimos dois exemplos mais elaborados — métodos gerais para encontrar zeros e pontos fixos de funções — e mostramos como esses métodos podem ser expressos diretamente como procedimentos.

Encontrando raízes de equações pelo método da bissecção

O método da bissecção é uma técnica simples, mas poderosa, para encontrar raízes de uma equação $f(x)=0$, onde $f$ é uma função contínua. A ideia é que, se nos forem dados pontos $a$ e $b$ tais que $f(a)<0<f(b)$, então $f$ deve ter pelo menos um zero entre $a$ e $b$

Para localizar um zero, seja $x$ a média de $a$ e $b$, e calcule $f(x)$. Se $f(x)>0$, então $f$ deve ter um zero entre $a$ e $x$. Se $f(x)<0$, então $f$ deve ter um zero entre $x$ e $b$. Continuando dessa forma, podemos identificar intervalos cada vez menores nos quais $f$ deve ter um zero. Quando chegamos a um ponto onde o intervalo é pequeno o suficiente, o processo para. Como o intervalo de incerteza é reduzido pela metade a cada passo do processo, o número de passos necessários cresce como $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->(L/T))$, onde $L$ é o comprimento do intervalo original e $T$ é a tolerância de erro (ou seja, o tamanho do intervalo que consideraremos "pequeno o suficiente"). Aqui está um procedimento que implementa essa estratégia:

(define (search f neg-point pos-point)
  (let ((midpoint 
         (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond 
           ((positive? test-value)
            (search f neg-point midpoint))
           ((negative? test-value)
            (search f midpoint pos-point))
           (else midpoint))))))

Assumimos que inicialmente recebemos a função $f$ junto com pontos onde seus valores são negativos e positivos. Primeiro calculamos o ponto médio dos dois pontos dados. Em seguida, verificamos se o intervalo dado é pequeno o suficiente, e se for, simplesmente retornamos o ponto médio como nossa resposta. Caso contrário, calculamos como valor de teste o valor de $f$ no ponto médio. Se o valor de teste for positivo, continuamos o processo com um novo intervalo que vai do ponto negativo original ao ponto médio. Se o valor de teste for negativo, continuamos com o intervalo do ponto médio ao ponto positivo. Finalmente, existe a possibilidade de que o valor de teste seja 0, caso em que o ponto médio é a própria raiz que estamos procurando.

Para testar se os pontos finais estão "próximos o suficiente", podemos usar um procedimento semelhante ao usado em 1.1.7 para calcular raízes quadradas:⁵⁵

(define (close-enough? x y) 
  (< (abs (- x y)) 0.001))

Search é difícil de usar diretamente, porque podemos acidentalmente fornecer pontos onde os valores de $f$ não têm o sinal necessário, caso em que obtemos uma resposta errada. Em vez disso, usaremos search através do seguinte procedimento, que verifica qual dos pontos finais tem um valor de função negativo e qual tem um valor positivo, e chama o procedimento search de acordo. Se a função tiver o mesmo sinal nos dois pontos dados, o método do intervalo médio não pode ser usado, caso em que o procedimento sinaliza um erro.⁵⁶

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) 
                (positive? b-value))
           (search f a b))
          ((and (negative? b-value) 
                (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of 
                   opposite sign" a b)))))

O exemplo a seguir usa o método do intervalo médio para aproximar $\mathrm{\pi <!--\; \pi \; -->}$ como a raiz entre 2 e 4 de $\sin <!--\; \; -->x=0$:

(half-interval-method sin 2.0 4.0)
3.14111328125

Aqui está outro exemplo, usando o método do intervalo médio para procurar uma raiz da equação $x^3-<!--\; -\; -->2x-<!--\; -\; -->3=0$ entre 1 e 2:

(half-interval-method 
 (lambda (x) (- (* x x x) (* 2 x) 3))
 1.0
 2.0)
1.89306640625

Encontrando pontos fixos de funções

Um número $x$ é chamado de ponto fixo de uma função $f$ se $x$ satisfaz a equação $f(x)=x$. Para algumas funções $f$ podemos localizar um ponto fixo começando com uma estimativa inicial e aplicando $f$ repetidamente, $$f(x),f(f(x)),f(f(f(x))),\dots <!--\; \dots \; -->,$$ até que o valor não mude muito. Usando essa ideia, podemos criar um procedimento fixed-point que recebe como entradas uma função e uma estimativa inicial e produz uma aproximação de um ponto fixo da função. Aplicamos a função repetidamente até encontrarmos dois valores sucessivos cuja diferença é menor que alguma tolerância prescrita:

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) 
       tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Por exemplo, podemos usar este método para aproximar o ponto fixo da função cosseno, começando com 1 como uma aproximação inicial:⁵⁷

(fixed-point cos 1.0)
.7390822985224023

Da mesma forma, podemos encontrar uma solução para a equação $y=\sin <!--\; \; -->y+\cos <!--\; \; -->y$:

(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
1.2587315962971173

O processo de ponto fixo é semelhante ao processo que usamos para encontrar raízes quadradas em 1.1.7. Ambos são baseados na ideia de repetidamente melhorar uma estimativa até que o resultado satisfaça algum critério. Na verdade, podemos facilmente formular o cálculo da raiz quadrada como uma busca por ponto fixo. Calcular a raiz quadrada de algum número $x$ requer encontrar um $y$ tal que $y^2=x$. Colocando essa equação na forma equivalente $y=x/y$, reconhecemos que estamos procurando um ponto fixo da função⁵⁸ $y\mapsto <!--\; \mapsto \; -->x/y$, e podemos, portanto, tentar calcular raízes quadradas como

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

Infelizmente, essa busca por ponto fixo não converge. Considere uma estimativa inicial $y_1$. A próxima estimativa é $y_2=x/y_1$ e a próxima estimativa é $y_3=x/y_2=x/(x/y_1)=y_1$. Isso resulta em um loop infinito em que as duas estimativas $y_1$ e $y_2$ se repetem continuamente, oscilando em torno da resposta.

Uma maneira de controlar essas oscilações é evitar que as estimativas mudem tanto. Como a resposta está sempre entre nossa estimativa $y$ e $x/y$, podemos fazer uma nova estimativa que não esteja tão longe de $y$ quanto $x/y$ calculando a média de $y$ com $x/y$, de modo que a próxima estimativa após $y$ seja $\frac{1}{2}(y+x/y)$ em vez de $x/y$. O processo de fazer tal sequência de estimativas é simplesmente o processo de procurar um ponto fixo de $y\mapsto <!--\; \mapsto \; -->\frac{1}{2}(y+x/y)$:

(define (sqrt x)
  (fixed-point 
   (lambda (y) (average y (/ x y)))
   1.0))

(Note que $y=\frac{1}{2}(y+x/y)$ é uma transformação simples da equação $y=x/y;$ para derivá-la, adicione $y$ a ambos os lados da equação e divida por 2.)

Com essa modificação, o procedimento de raiz quadrada funciona. Na verdade, se desvendarmos as definições, podemos ver que a sequência de aproximações para a raiz quadrada gerada aqui é precisamente a mesma que a gerada por nosso procedimento original de raiz quadrada de 1.1.7. Essa abordagem de média de aproximações sucessivas para uma solução, uma técnica que chamamos de amortecimento médio, frequentemente ajuda a convergência de buscas por ponto fixo.

Exercício 1.35: Mostre que a proporção áurea $\mathrm{\phi <!--\; \phi \; -->}$ (1.2.2) é um ponto fixo da transformação $x\mapsto <!--\; \mapsto \; -->1+1/x$, e use esse fato para calcular $\mathrm{\phi <!--\; \phi \; -->}$ por meio do procedimento fixed-point.

Exercício 1.36: Modifique fixed-point para que ele imprima a sequência de aproximações que gera, usando as primitivas newline e display mostradas em Exercício 1.22. Em seguida, encontre uma solução para $x^x=1000$ encontrando um ponto fixo de $x\mapsto <!--\; \mapsto \; -->\log <!--\; \; -->(1000)/\log <!--\; \; -->(x)$. (Use a primitiva log do Scheme, que calcula logaritmos naturais.) Compare o número de passos que isso leva com e sem amortecimento médio. (Observe que você não pode começar fixed-point com uma estimativa de 1, pois isso causaria divisão por $\log <!--\; \; -->(1)=0$.)

Exercício 1.37:

1. Uma fração contínua infinita é uma expressão da forma $$f=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\dots <!--\; \dots \; -->}}}.$$ Como exemplo, pode-se mostrar que a expansão de fração contínua infinita com os $N_i$ e os $D_i$ todos iguais a 1 produz $1/\mathrm{\phi <!--\; \phi \; -->}$, onde $\mathrm{\phi <!--\; \phi \; -->}$ é a proporção áurea (descrita em 1.2.2). Uma maneira de aproximar uma fração contínua infinita é truncar a expansão após um dado número de termos. Tal truncamento—uma chamada fração contínua finita k-term finite continued fraction—tem a forma $$\frac{N_1}{D_1+\frac{N_2}{\ddots <!--\; \ddots \; -->+\frac{N_k}{D_k}}}.$$ Suponha que n e d sejam procedimentos de um argumento (o índice do termo $i$) que retornam o $N_i$ e o $D_i$ dos termos da fração contínua. Defina um procedimento cont-frac tal que avaliar (cont-frac n d k) calcule o valor da fração contínua finita de $k$ termos. Verifique seu procedimento aproximando $1/\mathrm{\phi <!--\; \phi \; -->}$ usando

   (cont-frac (lambda (i) 1.0)
              (lambda (i) 1.0)
              k)

   para valores sucessivos de k. Quão grande você deve fazer k para obter uma aproximação que seja precisa até 4 casas decimais?

2. Se o seu procedimento cont-frac gerar um processo recursivo, escreva um que gere um processo iterativo. Se ele gerar um processo iterativo, escreva um que gere um processo recursivo.

Exercício 1.38: Em 1737, o matemático suíço Leonhard Euler publicou um artigo De Fractionibus Continuis, que incluía uma expansão de fração contínua para $e-<!--\; -\; -->2$, onde $e$ é a base dos logaritmos naturais. Nessa fração, os $N_i$ são todos 1, e os $D_i$ são sucessivamente 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …. Escreva um programa que use o seu procedimento cont-frac do Exercício 1.37 para aproximar $e$, com base na expansão de Euler.

Exercício 1.39: Uma representação de fração contínua da função tangente foi publicada em 1770 pelo matemático alemão J.H. Lambert: $$\tan <!--\; \; -->x=\frac{x}{1-<!--\; -\; -->\frac{x^2}{3-<!--\; -\; -->\frac{x^2}{5-<!--\; -\; -->\dots <!--\; \dots \; -->}}},$$ onde $x$ está em radianos. Defina um procedimento (tan-cf x k) que calcula uma aproximação da função tangente com base na fórmula de Lambert. k especifica o número de termos a serem calculados, como no Exercício 1.37.

1.3.4Procedimentos como Valores Retornados

Os exemplos acima demonstram como a capacidade de passar procedimentos como argumentos aumenta significativamente o poder expressivo de nossa linguagem de programação. Podemos alcançar ainda mais poder expressivo criando procedimentos cujos valores retornados são eles mesmos procedimentos.

Podemos ilustrar essa ideia olhando novamente para o exemplo de ponto fixo descrito no final de 1.3.3. Formulamos uma nova versão do procedimento de raiz quadrada como uma busca por ponto fixo, começando com a observação de que $\sqrt{x}$ é um ponto fixo da função $y\mapsto <!--\; \mapsto \; -->x/y$. Então usamos o amortecimento médio para fazer as aproximações convergirem. O amortecimento médio é uma técnica geral útil por si só. Ou seja, dada uma função $f$, consideramos a função cujo valor em $x$ é igual à média de $x$ e $f(x)$.

Podemos expressar a ideia de amortecimento médio por meio do seguinte procedimento:

(define (average-damp f)
  (lambda (x) 
    (average x (f x))))

Average-damp é um procedimento que recebe como argumento um procedimento f e retorna como valor um procedimento (produzido pelo lambda) que, quando aplicado a um número x, produz a média de x e (f x). Por exemplo, aplicando average-damp ao procedimento square produz um procedimento cujo valor em algum número $x$ é a média de $x$ e $x^2$. Aplicando esse procedimento resultante a 10 retorna a média de 10 e 100, ou 55:⁵⁹

((average-damp square) 10)
55

Usando average-damp, podemos reformular o procedimento de raiz quadrada da seguinte forma:

(define (sqrt x)
  (fixed-point 
   (average-damp 
    (lambda (y) (/ x y)))
   1.0))

Observe como essa formulação torna explícitas as três ideias do método: busca por ponto fixo, amortecimento médio e a função $y\mapsto <!--\; \mapsto \; -->x/y$. É instrutivo comparar essa formulação do método de raiz quadrada com a versão original dada em 1.1.7. Lembre-se de que esses procedimentos expressam o mesmo processo e observe como a ideia fica mais clara quando expressamos o processo em termos dessas abstrações. Em geral, existem muitas maneiras de formular um processo como um procedimento. Programadores experientes sabem como escolher formulações procedurais que são particularmente perspicazes e onde elementos úteis do processo são expostos como entidades separadas que podem ser reutilizadas em outras aplicações. Como um exemplo simples de reutilização, observe que a raiz cúbica de $x$ é um ponto fixo da função $y\mapsto <!--\; \mapsto \; -->x/y^2$, então podemos imediatamente generalizar nosso procedimento de raiz quadrada para um que extrai raízes cúbicas:⁶⁰

(define (cube-root x)
  (fixed-point 
   (average-damp 
    (lambda (y) 
      (/ x (square y))))
   1.0))

Método de Newton

Quando introduzimos o procedimento de raiz quadrada, em 1.1.7, nós mencionamos que este era um caso especial do método de Newton. Se $x\mapsto <!--\; \mapsto \; -->g(x)$ é uma função diferenciável, então uma solução da equação $g(x)=0$ é um ponto fixo da função $x\mapsto <!--\; \mapsto \; -->f(x)$ onde $$f(x)=x-<!--\; -\; -->\frac{g(x)}{Dg(x)}$$ e $Dg(x)$ é a derivada de $g$ avaliada em $x$. O método de Newton é o uso do método de ponto fixo que vimos acima para aproximar uma solução da equação encontrando um ponto fixo da função $f$.⁶¹

Para muitas funções $g$ e para estimativas iniciais suficientemente boas para $x$, o método de Newton converge muito rapidamente para uma solução de $g(x)=0$.⁶²

Para implementar o método de Newton como um procedimento, devemos primeiro expressar a ideia de derivada. Observe que "derivada", como o amortecimento médio, é algo que transforma uma função em outra função. Por exemplo, a derivada da função $x\mapsto <!--\; \mapsto \; -->x^3$ é a função $x\mapsto <!--\; \mapsto \; -->3x^2$. Em geral, se $g$ é uma função e $dx$ é um número pequeno, então a derivada $Dg$ de $g$ é a função cujo valor em qualquer número $x$ é dado (no limite de $dx$ pequeno) por $$Dg(x)=\frac{g(x+dx)-<!--\; -\; -->g(x)}{dx}.$$ Assim, podemos expressar a ideia de derivada (tomando $dx$ como, por exemplo, 0.00001) como o procedimento

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

junto com a definição

(define dx 0.00001)

Como average-damp, deriv é um procedimento que recebe um procedimento como argumento e retorna um procedimento como valor. Por exemplo, para aproximar a derivada de $x\mapsto <!--\; \mapsto \; -->x^3$ em 5 (cujo valor exato é 75) podemos avaliar

(define (cube x) (* x x x))

((deriv cube) 5)
75.00014999664018

Com a ajuda de deriv, podemos expressar o método de Newton como um processo de ponto fixo:

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) 
            ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) 
               guess))

O procedimento newton-transform expressa a fórmula no início desta seção, e newtons-method é facilmente definido em termos disso. Ele recebe como argumentos um procedimento que calcula a função para a qual queremos encontrar um zero, junto com uma estimativa inicial. Por exemplo, para encontrar a raiz quadrada de $x$, podemos usar o método de Newton para encontrar um zero da função $y\mapsto <!--\; \mapsto \; -->y^2-<!--\; -\; -->x$ começando com uma estimativa inicial de 1.⁶³

Isso fornece mais uma forma do procedimento de raiz quadrada:

(define (sqrt x)
  (newtons-method 
   (lambda (y) 
     (- (square y) x)) 
   1.0))

Abstrações e procedimentos de primeira classe

Vimos duas maneiras de expressar o cálculo da raiz quadrada como uma instância de um método mais geral, uma como uma busca por ponto fixo e outra usando o método de Newton. Como o método de Newton foi ele mesmo expresso como um processo de ponto fixo, na verdade vimos duas maneiras de calcular raízes quadradas como pontos fixos. Cada método começa com uma função e encontra um ponto fixo de alguma transformação da função. Podemos expressar essa ideia geral como um procedimento:

(define (fixed-point-of-transform 
         g transform guess)
  (fixed-point (transform g) guess))

Este procedimento muito geral recebe como argumentos um procedimento g que calcula alguma função, um procedimento que transforma g e uma estimativa inicial. O resultado retornado é um ponto fixo da função transformada.

Usando essa abstração, podemos reformular o primeiro cálculo de raiz quadrada desta seção (onde procuramos um ponto fixo da versão amortecida de $y\mapsto <!--\; \mapsto \; -->x/y$) como uma instância desse método geral:

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (/ x y))
   average-damp
   1.0))

Da mesma forma, podemos expressar o segundo cálculo de raiz quadrada desta seção (uma instância do método de Newton que encontra um ponto fixo da transformação de Newton de $y\mapsto <!--\; \mapsto \; -->y^2-<!--\; -\; -->x$) como

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (- (square y) x))
   newton-transform
   1.0))

Começamos a seção 1.3 com a observação de que procedimentos compostos são um mecanismo crucial de abstração, porque nos permitem expressar métodos gerais de computação como elementos explícitos em nossa linguagem de programação. Agora vimos como procedimentos de ordem superior nos permitem manipular esses métodos gerais para criar mais abstrações.

Como programadores, devemos estar atentos a oportunidades para identificar as abstrações subjacentes em nossos programas e construir sobre elas e generalizá-las para criar abstrações mais poderosas. Isso não significa que devemos sempre escrever programas da maneira mais abstrata possível; programadores experientes sabem como escolher o nível de abstração apropriado para sua tarefa. Mas é importante ser capaz de pensar em termos dessas abstrações, para que possamos estar prontos para aplicá-las em novos contextos. A importância dos procedimentos de ordem superior é que eles nos permitem representar essas abstrações explicitamente como elementos em nossa linguagem de programação, para que possam ser manipulados como outros elementos computacionais.

Em geral, as linguagens de programação impõem restrições sobre as maneiras pelas quais elementos computacionais podem ser manipulados. Elementos com as menores restrições são ditos ter status de primeira classe. Alguns dos "direitos e privilégios" dos elementos de primeira classe são:⁶⁴

• Eles podem ser nomeados por variáveis.
• Eles podem ser passados como argumentos para procedimentos.
• Eles podem ser retornados como resultados de procedimentos.
• Eles podem ser incluídos em estruturas de dados.⁶⁵

Lisp, ao contrário de outras linguagens de programação comuns, concede aos procedimentos status completo de primeira classe. Isso impõe desafios para uma implementação eficiente, mas o ganho resultante em poder expressivo é enorme.⁶⁶

Exercício 1.40: Defina um procedimento cubic que pode ser usado junto com o procedimento newtons-method em expressões da forma

(newtons-method (cubic a b c) 1)

para aproximar zeros do cúbico $x^3+a{x}^2+bx+c$.

Exercício 1.41: Defina um procedimento double que recebe um procedimento de um argumento como argumento e retorna um procedimento que aplica o procedimento original duas vezes. Por exemplo, se inc é um procedimento que adiciona 1 ao seu argumento, então (double inc) deve ser um procedimento que adiciona 2. Qual valor é retornado por

(((double (double double)) inc) 5)

Exercício 1.42: Sejam $f$ e $g$ duas funções de um argumento. A composição $f$ após $g$ é definida como a função $x\mapsto <!--\; \mapsto \; -->f(g(x))$. Defina um procedimento compose que implementa a composição. Por exemplo, se inc é um procedimento que adiciona 1 ao seu argumento,

((compose square inc) 6)
49

Exercício 1.43: Se $f$ é uma função numérica e $n$ é um inteiro positivo, então podemos formar a $n^{\text{th}}$ aplicação repetida de $f$, que é definida como a função cujo valor em $x$ é $f(f(\dots <!--\; \dots \; -->(f(x))\dots <!--\; \dots \; -->))$. Por exemplo, se $f$ é a função $x\mapsto <!--\; \mapsto \; -->x+1$, então a $n^{\text{th}}$ aplicação repetida de $f$ é a função $x\mapsto <!--\; \mapsto \; -->x+n$. Se $f$ é a operação de elevar um número ao quadrado, então a $n^{\text{th}}$ aplicação repetida de $f$ é a função que eleva seu argumento à $2^n\text{-th}$ potência. Escreva um procedimento que recebe como entradas um procedimento que calcula $f$ e um inteiro positivo $n$ e retorna o procedimento que calcula a $n^{\text{th}}$ aplicação repetida de $f$. Seu procedimento deve ser capaz de ser usado da seguinte forma:

((repeated square 2) 5)
625

Dica: Você pode achar conveniente usar compose do Exercício 1.42.

Exercício 1.44: A ideia de suavização de uma função é um conceito importante no processamento de sinais. Se $f$ é uma função e $dx$ é algum número pequeno, então a versão suavizada de $f$ é a função cujo valor em um ponto $x$ é a média de $f(x-<!--\; -\; -->dx)$, $f(x)$, e $f(x+dx)$. Escreva um procedimento smooth que recebe como entrada um procedimento que calcula $f$ e retorna um procedimento que calcula a versão suavizada de $f$. Às vezes é valioso suavizar repetidamente uma função (ou seja, suavizar a função suavizada, e assim por diante) para obter a função suavizada n-vezes. Mostre como gerar a função suavizada n-vezes de qualquer função dada usando smooth e repeated do Exercício 1.43.

Exercício 1.45: Vimos em 1.3.3 que tentar calcular raízes quadradas encontrando ingenuamente um ponto fixo de $y\mapsto <!--\; \mapsto \; -->x/y$ não converge, e que isso pode ser corrigido pelo amortecimento médio. O mesmo método funciona para encontrar raízes cúbicas como pontos fixos da função amortecida $y\mapsto <!--\; \mapsto \; -->x/y^2$. Infelizmente, o processo não funciona para raízes quartas—um único amortecimento médio não é suficiente para fazer uma busca por ponto fixo para $y\mapsto <!--\; \mapsto \; -->x/y^3$ convergir. Por outro lado, se amortecermos a média duas vezes (ou seja, usarmos o amortecimento médio do amortecimento médio de $y\mapsto <!--\; \mapsto \; -->x/y^3$) a busca por ponto fixo converge. Faça alguns experimentos para determinar quantos amortecimentos médios são necessários para calcular $n^{\text{th}}$ raízes como uma busca por ponto fixo baseada em amortecimento médio repetido de $y\mapsto <!--\; \mapsto \; -->x/y^{n-<!--\; -\; -->1}$. Use isso para implementar um procedimento simples para calcular $n^{\text{th}}$ raízes usando fixed-point, average-damp, e o procedimento repeated do Exercício 1.43. Assuma que quaisquer operações aritméticas necessárias estão disponíveis como primitivas.

Exercício 1.46: Vários dos métodos numéricos descritos neste capítulo são instâncias de uma estratégia computacional extremamente geral conhecida como melhoria iterativa. A melhoria iterativa diz que, para calcular algo, começamos com uma estimativa inicial para a resposta, testamos se a estimativa é boa o suficiente, e caso contrário, melhoramos a estimativa e continuamos o processo usando a estimativa melhorada como a nova estimativa. Escreva um procedimento iterative-improve que recebe dois procedimentos como argumentos: um método para dizer se uma estimativa é boa o suficiente e um método para melhorar uma estimativa. Iterative-improve deve retornar como seu valor um procedimento que recebe uma estimativa como argumento e continua melhorando a estimativa até que ela seja boa o suficiente. Reescreva o procedimento sqrt de 1.1.7 e o procedimento fixed-point de 1.3.3 em termos de iterative-improve.