1.3.1 Funções como Argumentos

Considere as três funções a seguir. A primeira calcula a soma dos inteiros de a até b:

Exemplo de Código

function sum_integers(a, b) {
  return a > b
         ? 0
         : a + sum_integers(a + 1, b);
}

function sum_integers(a, b) {
  return a > b
         ? 0
         : a + sum_integers(a + 1, b);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A segunda calcula a soma dos cubos dos inteiros no intervalo dado:

Exemplo de Código

function sum_cubes(a, b) {
  return a > b
         ? 0
         : cube(a) + sum_cubes(a + 1, b);
}

function sum_cubes(a, b) {
  return a > b
         ? 0
         : cube(a) + sum_cubes(a + 1, b);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A terceira calcula a soma de uma sequência de termos na série

\frac{1}{1\cdot3}+\frac{1}{5\cdot7}+\frac{1}{9\cdot11}+\cdots

que converge para $\pi/8$ (muito lentamente):¹

Exemplo de Código

function pi_sum(a, b) {
  return a > b
         ? 0
         : 1 / (a * (a + 2)) + pi_sum(a + 4, b);
}

function pi_sum(a, b) {
  return a > b
         ? 0
         : 1 / (a * (a + 2)) + pi_sum(a + 4, b);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Estas três funções claramente compartilham um padrão subjacente comum. Elas são, em sua maior parte, idênticas, diferindo apenas no nome da função, 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 uma das funções preenchendo os espaços no mesmo template:

function nome(a, b) {
    return a > b
           ? 0
           : termo(a) + nome(proximo(a), b);
}

A presença de tal padrão comum é forte evidência de que existe uma abstração útil esperando para ser trazida à superfície. De fato, matemáticos há muito tempo identificaram a abstração de somatório de uma série e inventaram a "notação sigma", por exemplo

\sum_{n=a}^{b} f(n) = f(a)+\cdots+f(b)

para expressar este conceito. O poder da notação sigma é que ela permite aos matemáticos lidar com o conceito de somatório 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 sendo somada.

Da mesma forma, como designers de programas, gostaríamos que nossa linguagem fosse poderosa o suficiente para que pudéssemos escrever uma função que expressa o conceito de somatório em si, em vez de apenas funções que calculam somas particulares. Podemos fazer isso prontamente em nossa linguagem funcional pegando o template comum mostrado acima e transformando os "espaços" em parâmetros:

Exemplo de Código

function sum(term, a, next, b) {
  return a > b
         ? 0
         : term(a) + sum(term, next(a), next, b);
}

function sum(term, a, next, b) {
  return a > b
         ? 0
         : term(a) + sum(term, next(a), next, b);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Observe que sum recebe como seus argumentos os limites inferior e superior a e b juntamente com as funções term e next. Podemos usar sum assim como usaríamos qualquer função. Por exemplo, podemos usá-la (junto com uma função inc que incrementa seu argumento em 1) para definir sum_cubes:

Exemplo de Código

function inc(n) {
  return n + 1;
}
function sum_cubes(a, b) {
  return sum(cube, a, inc, b);
}

function inc(n) {
  return n + 1;
}
function sum_cubes(a, b) {
  return sum(cube, a, inc, b);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

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

Exemplo de Código

sum_cubes(1, 10);

sum_cubes(1, 10);

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Com a ajuda de uma função identidade para calcular o termo, podemos definir sum_integers em termos de sum:

Exemplo de Código

function identity(x) {
  return x;
}
function sum_integers(a, b) {
  return sum(identity, a, inc, b);
}

function identity(x) {
  return x;
}
function sum_integers(a, b) {
  return sum(identity, a, inc, b);
}

Código editável · Ctrl+Enter executa · Esc solta o foco

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

Exemplo de Código

sum_integers(1, 10);

sum_integers(1, 10);

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Também podemos definir pi_sum da mesma forma:²

Exemplo de Código

function pi_sum(a, b) {
  function pi_term(x) {
      return 1 / (x * (x + 2));
  }
  function pi_next(x) {
      return x + 4;
  }
  return sum(pi_term, a, pi_next, b);
}

function pi_sum(a, b) {
  function pi_term(x) {
      return 1 / (x * (x + 2));
  }
  function pi_next(x) {
      return x + 4;
  }
  return sum(pi_term, a, pi_next, b);
}

Código editável · Ctrl+Enter executa · Esc solta o foco

Usando essas funções, podemos calcular uma aproximação de $\pi$ :

Exemplo de Código

8 * pi_sum(1, 1000);

8 * pi_sum(1, 1000);

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Uma vez que temos sum, podemos usá-la 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

\int_a^b f = \left[ f\left(a+\frac{dx}{2}\right) + f\left(a+dx+\frac{dx}{2}\right) + f\left(a+2dx+\frac{dx}{2}\right) + \cdots \right] dx

para valores pequenos de $dx$ . Podemos expressar isso diretamente como uma função:

Exemplo de Código

function integral(f, a, b, dx) {
  function add_dx(x) {
      return x + dx;
  }
  return sum(f, a + dx / 2, add_dx, b) * dx;
}

function integral(f, a, b, dx) {
  function add_dx(x) {
      return x + dx;
  }
  return sum(f, a + dx / 2, add_dx, b) * dx;
}

Código editável · Ctrl+Enter executa · Esc solta o foco

Exemplo de Código

integral(cube, 0, 1, 0.01);

integral(cube, 0, 1, 0.01);

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Exemplo de Código

integral(cube, 0, 1, 0.001);

integral(cube, 0, 1, 0.001);

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

(O valor exato da integral do cubo 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 + 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.) Declare uma função que recebe como argumentos $f$ , $a$ , $b$ e $n$ e retorna o valor da integral, calculado usando a Regra de Simpson. Use sua função para integrar cube entre 0 e 1 (com $n = 100$ e $n = 1000$ ), e compare os resultados com os da função integral mostrada acima.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. O coeficiente de $y_k$ é 1 nas pontas, 4 nos índices ímpares e 2 nos pares — então o termo da soma pode decidir o coeficiente olhando a paridade de $k$ , e sum faz o resto.

Exemplo de Código

function sum(term, a, next, b) {
  return a > b
         ? 0
         : term(a) + sum(term, next(a), next, b);
}
function inc(k) { return k + 1; }

function simpson(f, a, b, n) {
  const h = (b - a) / n;
  function y(k) { return f(a + k * h); }
  function term(k) {
      return k === 0 || k === n
             ? y(k)
             : k % 2 === 1
             ? 4 * y(k)
             : 2 * y(k);
  }
  return (h / 3) * sum(term, 0, inc, n);
}

function cube(x) { return x * x * x; }

display(simpson(cube, 0, 1, 100));
simpson(cube, 0, 1, 1000);

function sum(term, a, next, b) {
  return a > b
         ? 0
         : term(a) + sum(term, next(a), next, b);
}
function inc(k) { return k + 1; }

function simpson(f, a, b, n) {
  const h = (b - a) / n;
  function y(k) { return f(a + k * h); }
  function term(k) {
      return k === 0 || k === n
             ? y(k)
             : k % 2 === 1
             ? 4 * y(k)
             : 2 * y(k);
  }
  return (h / 3) * sum(term, 0, inc, n);
}

function cube(x) { return x * x * x; }

display(simpson(cube, 0, 1, 100));
simpson(cube, 0, 1, 1000);

Código editável · Ctrl+Enter executa · Esc solta o foco

Comparação. O valor exato de $\int_0^1 x^3\,dx$ é $0{,}25$ . A integral do texto com $dx = 0{,}01$ dá $\approx 0{,}24998$ ; a Regra de Simpson dá exatamente 0,25 já com $n = 100$ — para polinômios de grau até 3, Simpson não é só mais precisa, é exata (a menos de erros de arredondamento de ponto flutuante).

Resolvi o exercício 1.29

Exercício 1.30

A função sum acima gera uma recursão linear. A função pode ser reescrita de forma que a soma seja realizada iterativamente. Mostre como fazer isso preenchendo as expressões faltantes no corpo da função a seguir:

function sum(term, a, next, b) {
    function iter(a, result) {
        return ⟨??⟩
               ? ⟨??⟩
               : iter(⟨??⟩, ⟨??⟩);
    }
    return iter(⟨??⟩, ⟨??⟩);
}

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Exemplo de Código

function sum(term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), result + term(a));
  }
  return iter(a, 0);
}

function identity(x) { return x; }
function inc(x) { return x + 1; }

sum(identity, 1, inc, 100);

function sum(term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), result + term(a));
  }
  return iter(a, 0);
}

function identity(x) { return x; }
function inc(x) { return x + 1; }

sum(identity, 1, inc, 100);

Código editável · Ctrl+Enter executa · Esc solta o foco

Por que funciona. result acumula a soma dos termos já visitados — o invariante é result + soma-dos-termos-restantes = resposta. Quando a > b não restam termos e result é a resposta. Todo o estado vive nos argumentos de iter: processo iterativo, espaço constante.

Resolvi o exercício 1.30

Exercício 1.31

a. A função sum é apenas a mais simples de um vasto número de abstrações similares que podem ser capturadas como funções de ordem superior.³ Escreva uma função análoga chamada product que retorna o produto dos valores de uma função nos pontos em um dado intervalo. Mostre como definir factorial em termos de product. Além disso, use product para calcular aproximações de $\pi$ usando a fórmula⁴

\frac{\pi}{4} = \frac{2\cdot 4\cdot 4\cdot 6\cdot 6\cdot 8\cdots}{3\cdot 3\cdot 5\cdot 5\cdot 7\cdot 7\cdots}

b. Se sua função product gera um processo recursivo, escreva uma que gere um processo iterativo. Se ela gera um processo iterativo, escreva uma que gere um processo recursivo.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

a. Versão recursiva, factorial e a fórmula de Wallis:

Exemplo de Código

function product(term, a, next, b) {
  return a > b
         ? 1
         : term(a) * product(term, next(a), next, b);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

function factorial(n) {
  return product(identity, 1, inc, n);
}

function wallis_pi(n) {
  function term(k) {
      const numerator = k % 2 === 0 ? k + 2 : k + 1;
      const denominator = k % 2 === 0 ? k + 1 : k + 2;
      return numerator / denominator;
  }
  return 4 * product(term, 1, inc, n);
}

display(factorial(6));
wallis_pi(1000);

function product(term, a, next, b) {
  return a > b
         ? 1
         : term(a) * product(term, next(a), next, b);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

function factorial(n) {
  return product(identity, 1, inc, n);
}

function wallis_pi(n) {
  function term(k) {
      const numerator = k % 2 === 0 ? k + 2 : k + 1;
      const denominator = k % 2 === 0 ? k + 1 : k + 2;
      return numerator / denominator;
  }
  return 4 * product(term, 1, inc, n);
}

display(factorial(6));
wallis_pi(1000);

Código editável · Ctrl+Enter executa · Esc solta o foco

O termo de índice $k$ é $\frac{k+2}{k+1}$ para $k$ par e $\frac{k+1}{k+2}$ para $k$ ímpar — exatamente o padrão $\frac{2}{3}\cdot\frac{4}{3}\cdot\frac{4}{5}\cdots$ . Com $n = 1000$ , wallis_pi dá $\approx 3{,}1400$ — a série converge devagar.

b. A versão acima é recursiva; a iterativa segue o molde do exercício 1.30:

Exemplo de Código

function product(term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), result * term(a));
  }
  return iter(a, 1);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

product(identity, 1, inc, 6);

function product(term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), result * term(a));
  }
  return iter(a, 1);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

product(identity, 1, inc, 6);

Código editável · Ctrl+Enter executa · Esc solta o foco

Resolvi o exercício 1.31

Exercício 1.32

a. 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 geral de acumulação:

accumulate(combiner, null_value, term, a, next, b)

A função accumulate recebe como argumentos as mesmas especificações de termo e intervalo de sum e product, juntamente com uma função 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 esgotam. Escreva accumulate e mostre como sum e product podem ser definidos como simples chamadas a accumulate.

b. Se sua função accumulate gera um processo recursivo, escreva uma que gere um processo iterativo. Se ela gera um processo iterativo, escreva uma que gere um processo recursivo.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

a. A única diferença entre sum e product é como combinar (+ vs *) e o valor neutro (0 vs 1). Abstraia os dois:

Exemplo de Código

function accumulate(combiner, null_value, term, a, next, b) {
  return a > b
         ? null_value
         : combiner(term(a),
                    accumulate(combiner, null_value,
                               term, next(a), next, b));
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

function sum(term, a, next, b) {
  return accumulate((x, y) => x + y, 0, term, a, next, b);
}
function product(term, a, next, b) {
  return accumulate((x, y) => x * y, 1, term, a, next, b);
}

display(sum(identity, 1, inc, 10));
product(identity, 1, inc, 5);

function accumulate(combiner, null_value, term, a, next, b) {
  return a > b
         ? null_value
         : combiner(term(a),
                    accumulate(combiner, null_value,
                               term, next(a), next, b));
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

function sum(term, a, next, b) {
  return accumulate((x, y) => x + y, 0, term, a, next, b);
}
function product(term, a, next, b) {
  return accumulate((x, y) => x * y, 1, term, a, next, b);
}

display(sum(identity, 1, inc, 10));
product(identity, 1, inc, 5);

Código editável · Ctrl+Enter executa · Esc solta o foco

b. A versão iterativa acumula no argumento:

Exemplo de Código

function accumulate(combiner, null_value, term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), combiner(result, term(a)));
  }
  return iter(a, null_value);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

accumulate((x, y) => x + y, 0, identity, 1, inc, 10);

function accumulate(combiner, null_value, term, a, next, b) {
  function iter(a, result) {
      return a > b
             ? result
             : iter(next(a), combiner(result, term(a)));
  }
  return iter(a, null_value);
}
function inc(x) { return x + 1; }
function identity(x) { return x; }

accumulate((x, y) => x + y, 0, identity, 1, inc, 10);

Código editável · Ctrl+Enter executa · Esc solta o foco

(Para combinadores associativos como + e * as duas versões coincidem; com combinadores não associativos a ordem de combinação difere entre elas — vale experimentar com (x, y) => x - y.)

Resolvi o exercício 1.32

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 aqueles termos derivados de valores no intervalo que satisfaçam 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 uma função. Mostre como expressar o seguinte usando filtered_accumulate:

a. a soma dos quadrados dos números primos no intervalo de $a$ a $b$ (assumindo que você tenha uma função is_prime já escrita)

b. o produto de todos os inteiros positivos menores que $n$ que são relativamente primos a $n$ (isto é, todos os inteiros positivos $i < n$ tais que $\text{GCD}(i, n) = 1$ ).

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A abstração: igual a accumulate, mas termos reprovados no filtro entram como se não existissem.

Exemplo de Código

function filtered_accumulate(combiner, null_value, term,
                           a, next, b, filter) {
  return a > b
         ? null_value
         : filter(a)
         ? combiner(term(a),
                    filtered_accumulate(combiner, null_value, term,
                                        next(a), next, b, filter))
         : filtered_accumulate(combiner, null_value, term,
                               next(a), next, b, filter);
}
function inc(x) { return x + 1; }
function square(x) { return x * x; }
function identity(x) { return x; }

// a. soma dos quadrados dos primos em [a, b]
function sum_of_prime_squares(a, b) {
  return filtered_accumulate((x, y) => x + y, 0,
                             square, a, inc, b, is_prime);
}

// b. produto dos i < n com gcd(i, n) = 1
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}
function product_of_coprimes(n) {
  return filtered_accumulate((x, y) => x * y, 1,
                             identity, 1, inc, n - 1,
                             i => gcd(i, n) === 1);
}

display(sum_of_prime_squares(2, 10)); // 4 + 9 + 25 + 49
product_of_coprimes(10);              // 1 * 3 * 7 * 9

function filtered_accumulate(combiner, null_value, term,
                           a, next, b, filter) {
  return a > b
         ? null_value
         : filter(a)
         ? combiner(term(a),
                    filtered_accumulate(combiner, null_value, term,
                                        next(a), next, b, filter))
         : filtered_accumulate(combiner, null_value, term,
                               next(a), next, b, filter);
}
function inc(x) { return x + 1; }
function square(x) { return x * x; }
function identity(x) { return x; }

// a. soma dos quadrados dos primos em [a, b]
function sum_of_prime_squares(a, b) {
  return filtered_accumulate((x, y) => x + y, 0,
                             square, a, inc, b, is_prime);
}

// b. produto dos i < n com gcd(i, n) = 1
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}
function product_of_coprimes(n) {
  return filtered_accumulate((x, y) => x * y, 1,
                             identity, 1, inc, n - 1,
                             i => gcd(i, n) === 1);
}

display(sum_of_prime_squares(2, 10)); // 4 + 9 + 25 + 49
product_of_coprimes(10);              // 1 * 3 * 7 * 9

Código editável · Ctrl+Enter executa · Esc solta o foco

Verificação. sum_of_prime_squares(2, 10) = $4 + 9 + 25 + 49 = 87$ ; product_of_coprimes(10) = $1 \cdot 3 \cdot 7 \cdot 9 = 189$ .

Resolvi o exercício 1.33

Notas de Rodapé

1 Esta série, geralmente escrita na forma equivalente $\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$ , é devida a Leibniz. Veremos como usar isso como base para alguns truques numéricos sofisticados na seção 3.5.3.

2 Observe que usamos estrutura de blocos (seção 1.1.8) para incorporar as declarações de pi_next e pi_term dentro de pi_sum, uma vez que essas funções são improváveis de serem úteis para qualquer outro propósito.

3 A intenção dos exercícios 1.31-1.33 é demonstrar o poder expressivo que é alcançado pela abstração apropriada. Os exercícios foram projetados para que você experimente diferentes maneiras de expressar esses conceitos e se convença de que as abstrações discutidas são as ferramentas certas para alcançar essa expressividade.

4 Esta fórmula foi descoberta pelo matemático e capelão inglês do século XVII John Wallis.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

Erro de tradução (palavra incorreta, termo técnico errado)
Erro de ortografia ou gramática
Link quebrado
Código de exemplo que não funciona
Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

Dúvida sobre o conteúdo desta seção
Pergunta sobre um conceito do SICP
Dificuldade em entender algum exemplo
Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

Melhoria na explicação
Exemplo adicional
Recurso visual (diagrama, ilustração)
Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

Escolha de tradução de algum termo
Consistência de terminologia
Nuances do português

Discussão de tradução →

Exercício 1.29​

Exercício 1.30​

Exercício 1.31​

Exercício 1.32​

Exercício 1.33​

Notas de Rodapé​

📝 Encontrou algo errado nesta página?

🐛 Encontrou um erro?

❓ Tem uma dúvida?

💡 Tem uma sugestão de melhoria?

🌍 Quer discutir a tradução?

Exercício 1.29

Exercício 1.30

Exercício 1.31

Exercício 1.32

Exercício 1.33

Notas de Rodapé