SICP Seção 1.2 - Procedures e os Processos que eles geram - Parte 1

Como eu disse num post anterior, quando a seção for muito grande, eu vou dividir os posts em várias seções. Pois bem, ocorre que a seção 1.2 pede diversas avaliações manuais, de modo que as soluções dos exercícios ficam muito extensas. Assim, pra não matar ninguém de tédio, vou dividir essa seção em partes menores. Aqui estão as soluções dos exercícios 1.9 e 1.10.

Exercício 1.9
Cada um dos dois procedures a seguir define um método para adicionar dois inteiros positivos, em termos dos procedures inc, que incrementa seu argumento em 1 unidade, e dec, que decrementa seu argumento de 1.

Usando o modelo da substituição, ilustre o processo gerado por cada procedure na avaliação de (+ 4 5). Esses processos são iterativos ou recursivos?
Solução:Primeiramente, vamos ver o processo de avaliação para (+ 4 5), utilizando a primeira definição apresentada:

Ora, vimos que, para a primeira definição, processo primeiro expande as expressões, depois calcula os resultados. O processo é, portanto, recursivo. Mais especificamente, é linearmente recursivo em a.
Agora, vejamos a avaliação de (+ 4 5), usando o segundo procedure mostrado:

Vimos, portanto, que a segunda definição de + apresentada desenvolve um processo iterativo.
Dica: quem quiser testar no DrScheme, deve definir inc e dec em termos de -. Como você estará redefinindo +, definir inc em termos do + redefinido vai causar uma recursão infinita (pense e descobrirá). As definições de inc e dec devem ser:

No exercício, é mais fácil considerar inc e dec como primitivas...

Exercício 1.10
O procedure abaixo computa uma função matemática denominada função de Ackerman.

Quais os valores das seguintes expressões?
(A 1 10)
(A 2 4)
(A 3 3)
Considere os seguintes procedures, em que A é o procedure definido acima:
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))
Dê expressões matemáticas concisas para as funções computadas pelos procedures f, g e h para valores positivos de n. Por exemplo, (k n) computa 5n^2.
Solução: A maneira mais fácil de saber o valor das expressões (A 1 10), (A 2 4) e (A 3 3) é definir a função A no DrScheme e calcular seus valores pela janela de interações... Mas creio que não seja esse o objetivo do exercício. Vou resolver as perguntas finais, sobre f, g e h, e depois faço a resolução das expressões manualmente.
Expressão para (f n) = (A 0 n)
Hipótese: (f n) = 2*n.
Prova: Muito simples. O enunciado fala em valores positivos de n (portanto 0 estaria fora), mas vamos fazer com valores não-negativos. Vamos fazer uma avaliação parcial de A, substituindo x por 0 e y por n. Temos, então, que (f n) é equivalente a:

Repare que nem inseri a expressão correspondente ao else, pois como a segunda cláusula do cond sempre avaliará para #t, a cláusula do else é inacessível. De qualquer forma, para n = 0, temos (f n) = 0 (ou seja, 2*0), e para n diferente de zero, a segunda cláusula do cond avalia para #t e o resultado da expressão é (* 2 n). Ou seja, de qualquer forma, temos (f n) = (* 2 n).

Expressão para (g n) = (A 1 n)
Analogamente ao anterior:

Considerando valores positivos de n, vemos que (g n) as duas primeiras cláusulas do cond sempre avaliarão para #f, de modo que o resultado sempre será equivalente à expressão abaixo.

Mas a expressão do corpo de g ainda pode ser simplificada, notando que (A 0 n) = (f n) = (* 2 n), e (A 1 (- n 1)) = (g (- n 1)). Temos, portanto:

Daí, fica fácil ver por indução que, de fato, (g n) 2^n.

Expressão para (h n) = (A 2 n)
Podemos fazer da mesma maneira que fizemos para g. Vamos pular os passos semelhantes e chegar direto em:

Novamente, podemos notar que (A 1 n) = 2^n e (A 2 (- n 1)) = (h (- n 1)), ou seja:

Também por indução, dá pra ver que a fórmula é
(2^ (2^ (2^...))), em que o número de 2 que aparece é exatamente n. Assim, para (h 1) = 2,(h 2) = (2^ 2) e (h 3) = (2^ (2^ 2)) = 16.

Agora, vamos à avaliação das expressões que o enunciado pede.

Avaliação de (A 1 10)

Avaliação de (A 2 4)

Avaliação de (A 3 3)