Seção 1.1 - Os Elementos da Programação

Antes de Começar

Scheme é uma linguagem relativamente fácil de se implementar (se você não se preocupar com completeza e performance). De fato, durante a resolução dos exercícios vou implementar algumas variantes de interpretadores, no capítulo 4, e mesmo um pequeno compilador, no capítulo 5. A linguagem tem uma especificação IEEE, datada de 1990, mas os padrões de facto são os RnRS, ou seja, os Relatórios Revisados sobre a linguagem Scheme, cuja direção é dada pela própria comunidade de programadores.  Até o R5RS, a especificação da linguagem tinha menos de 50 páginas. Com o R6RS, veio o suporte a Unicode, módulos, entre outros, e o padrão cresceu um pouco.

A relativa facilidade de se implementar Scheme fez com que implementações proliferassem. Algumas implementações são boas e completas. Outras, nem tanto. Assim, um dos primeiros desafios pelo qual o aspirante a Schemer deve passar é a escolha de boas implementações. Eu particularmente vou adotar PLT Scheme, uma excelente implementação que vem já com um bom ambiente de desenvolvimento e excelente documentação offline. Caso tenha dúvidas sobre algum conceito, é só apertar F1 no ambiente do DrScheme e buscar na documentação.

Na primeira vez que o DrScheme for iniciado, é necessário que se escolha uma linguagem de trabalho. Basta clicar na região adequada no canto inferior esquerdo e escolher a linguagem Module. Você vai reparar que a primeira linha do arquivo na região de definições vai se tornar #lang scheme. Para resolver os exercícios do SICP, você não precisa saber o que isso significa exatamente. Quem quiser se aprofundar mais no uso de Scheme (além do requerido para o SICP), pode ler o Guia na documentação do PLT Scheme ou, alternativamente, o livro The Scheme Programming Language, de Kent Dybvig, também disponível gratuitamente na internet. Vale lembrar que Dybvig, além de um notável Schemer e pesquisador, é o desenvolvedor da Chez Scheme, sem dúvida a implementação mais rápida que há por aí... Chez Scheme é paga, mas no site você também encontra o Petite Chez Scheme, que é a basicamente a mesma coisa, só que sem o compilador. Petite é gratis...

Uma vez escolhido o ambiente de desenvolvimento, vamos começar com os exercícios. A seção 1.1 introduz os três elementos de qualquer linguagem de programação: primitivas, meios de combinação e meios de abstração. Apenas um detalhe. Apesar de os comentários serem em português, faço meus códigos todos em inglês (nomes de variáveis, funções, módulos, etc.), pois acredito que isso mantém a uniformidade. Se houver dúvida quanto ao significado de alguma coisa, basta comentar que eu esclareço.

Exercício 1.1
Abaixo está uma sequência de expressões. Qual o resultado impresso pelo interpretador em resposta a cada expressão? Assuma que a sequência deve ser avaliada na ordem em que é apresentada.

Solução: O objetivo deste exercício é ver se o leitor entendeu o básico da avaliação de expressões. Ou seja, tal exercício deve ser resolvido sem ajuda do interpretador. Uma maneira boa de se apresentar a solução é por meio de um arquivo interpretável é usar o mecanismo de testes do DrScheme. O mecanismo é muito simples. Basicamente, você define testes com check-expect e os executa por meio da execução da expressão (test). A forma check-expect (não digo função pois não é uma função, já que os testes só são definidos com check-expect, ou seja, os argumentos não são avaliados) aceita dois argumentos. O primeiro é a expressão que se quer testar e o segundo é o resultado esperado.


Exercício 1.2
Traduza a seguinte expressão em forma prefixa:

Solução: O objetivo desse exercício é saber se o leitor consegue converter entre notação infixa e prefixa. Tenho algumas dicas:

1. operadores aritméticos permitem múltiplos argumentos, então a + b + c vira (+ a b c).
2. olhe para a expressão meio que "de trás pra frente". Assim, a primeira coisa que se nota na expressão em questão é a divisão.
3. Scheme suporta números racionais, então é possível escrever 4/5 direto em vez de (/ 4 5).

Exercício 1.3
Defina um procedure que recebe três números como argumentos e retorna a soma dos quadrados dos dois maiores.
Solução: O segredo para fazer menos comparações é, em vez de procurar os dois maiores, procurar o menor e retornar o quadrado dos dois outros. Vale lembrar que a função para calcular o quadrado, no PLT Scheme, denomina-se sqr.
Observação: Os dez testes que eu codifiquei antes da própria função podem ser considerados overkill e, de fato, o são. Mas o programa é tão pequeno que compensa testar todas as combinações possíveis de estados (três argumentos iguais, dois argumentos iguais, e três argumentos distintos).


Exercício 1.4
Observe que nosso modelo de avaliação permite combinações cujos operadores são expressões compostas. Use essa observação para descrever o comportamento do seguinte procedure:


Solução: Basicamente, a função calcula a + |b|. O jeito "padrão" de fazer esse cálculo (em C, por exemplo), é usando a + abs(b). Em Scheme, é possível observar a expressão na íntegra. Quando b é maior que zero, a + |b| é a + b, ou, em Scheme (+ a b). Caso contrário, a expressão torna-se a – b, isto é, (- a b). Observe que a única diferença entre as expressões é o operador. Assim sendo, é possível usar um condicional para definir o operador adequado para cada situação. A pergunta é: por que isso é possível em Scheme? Lembre-se que o algoritmo para avaliar uma combinação é recursivo: Para avaliar uma combinação, avaliam-se as suas sub-expressões e aplica-se o resultado da avaliação da sub-expressão da esquerda (o operador) aos resultados das avaliações das demais sub-expressões (os argumentos). Vamos mostrar (parcialmente) os passos da avaliação de (a-plus-abs-b a b) para um valor positivo e um valor negativo de b.
Valor positivo:

Analogamente, para valor negativo


Exercício 1.5
Ben Bitdiddle inventou um teste para determinar se o interpretador com o qual ele interage está usando ordem aplicativa de avaliação ou ordem normal de avaliação. Ele define os dois procedures abaixo:

Depois ele avalia a expressão:

Qual comportamento Ben observará com um interpretador que usa ordem aplicativa de avaliação? Qual comportamento ele observará com um interpretador que usa ordem normal de avaliação? Explique sua resposta. (Assuma que a regra de avaliação para a forma especial if é a mesma caso o interpretador use ordem normal ou aplicativa: A expressão-predicado é avaliada primeiro, e o resultado determina se o conseqüente ou o alternativo deve ser avaliado).
Solução: Para resolver esse problema, primeiro observa-se que p é uma recursão infinita. Cada vez que p é chamada, ela se chama novamente. Assim sendo, a avaliação nunca termina. Vale observar que, como Scheme apresenta otimização de tail-calls, a pilha não cresce com as chamadas recursivas de p... Assim, não haverá sequer o erro de estouro de memória. A avaliação simplesmente nunca acaba, mesmo que a memória esteja limitada a apenas 1MB...
Agora, vamos à expressão de teste: (test 0 (p)).
Se o interpretador usa ordem normal de avaliação, cada argumento de test só são avaliados quando (e se) seu valor for necessário. Usando o modelo de substituição, temos:

Agora, para se avaliar o resultado do if, é necessário avaliar a expressão (= 0 0). O resultado de tal avaliação é #t. Temos, portanto:

Veja que o valor de (p) não é necessário para que a avaliação possa se completar, então (p) nunca é, de fato, avaliada. Resumindo: num interpretador com ordem normal de avaliação, a expressão (test 0 (p)) produz o resultado 0.
Por outro lado, se o interpretador for de ordem aplicativa, temos a regra: para avaliar uma combinação, avaliamos as sub-expressões e aplicamos o resultado da sub-expressão da esquerda às demais sub-expressões. Assim sendo, as sub-expressões são avaliadas antes da aplicação, independentemente de seus resultados serem ou não necessários.
Para avaliar (test 0 (p)) num interpretador com ordem aplicativa (supondo ordem de avaliação da esquerda para a direita), temos os seguintes passos:

1. Avalie test
2. Avalie 0
3. Avalie (p)
4. Aplique o resultado da avaliação de test aos argumentos 0 e (p)

Até aí, tudo bem. O problema é que o passo 3 nunca retorna. Como a avaliação da expressão de teste depende da avaliação de (p), ela também não retorna. Ou seja, se o interpretador usar ordem aplicativa de avaliação, o comportamento que Bitdiddle observará é que a expressão de teste nunca produzirá um valor, ficando travada em loop infinito.

Exercício 1.6
Alyssa P. Hacker não vê por que if deve ser disponibilizado como uma forma especial. Por que não posso definir um procedure regular em termos de cond?, ela pergunta. A amiga de Alyssa, Eva Lu Ator, diz que isso pode de fato ser feito, e define uma nova versão de if.

Eva demonstra o programa para Alyssa:

Satisfeita, Alyssa usa new-if para reescrever o programa da raiz quadrada:

O que acontece quando Alyssa tenta usar esse procedure para computar raízes quadradas? Explique.
Solução: Quando Alyssa tenta sqrt-iter definido em termos de new-if, o programa produz infinitas chamadas (cada sqrt-iter invoca um novo new-if, que por sua vez invoca outro sqrt-iter, e assim por diante...) e jamais produz uma resposta. Explicação: A razão pela qual sqrt-iter não responde tem a ver com o fato de o interpretador usar a ordem aplicativa de avaliação. Ora, new-if é uma função e, assim sendo, deve avaliar seus argumentos antes que possa a eles ser aplicada. No caso de sqrt-iter, temos uma espécie de "dependência circular". Antes que sqrt-iter possa produzir um resultado, a expressão new-if que ocorre em seu corpo deve ser avaliada. Ou seja, sqrt-iter depende de new-if. Por outro lado, antes que new-if possa produzir um resultado, ela precisa avaliar uma nova expressão sqrt-iter. Embora a nova expressão sqrt-iter tenha argumentos distintos, uma chamada a sqrt-iter sempre ocasionará uma nova chamada a sqrt-iter, numa espécie de recursão infinita que nunca retorna.

Exercício 1.7
O teste good-enough? usado na computação de raízes quadradas não será muito efetivo para encontrar as raízes quadradas de números muito pequenos. Além disso, em computadores reais, as operações aritméticas são quase sempre executadas com precisão limitada. Isso faz com que nosso teste seja inadequado para números muito grandes. Uma estratégia alternativa de implementação de good-enough? é ver como guess muda de uma iteração para a próxima e parar quando a mudança for uma fração muito pequena de guess. Projete um procedure square-root que use esse tipo de teste de parada. Tal teste funciona melhor para números pequenos e grandes?
Solução: Abaixo mostro as definições de sqrt dada pelo livro, junto com outras funções associadas.

Usando essas definições, podemos avaliar sqrt para números pequenos, digamos, 10^-4 e 10^-6. Os resultados são:

Resultados aceitáveis deveriam ser aproximadamente 1.0e-2 e 1.0e-3, respectivamente. Ou seja, o procedure >sqrt de fato não funciona para números muito pequenos. Isso acontece porque, quando os números cuja raiz desejamos calcular aproximam a constante usada no teste, good-enough? vai , às vezes, retornar #t mesmo quando o guess não é bom o suficiente. Isso tem a ver com a relação entre a constante utilizada no teste good-enough? e o número cuja raiz se deseja calcular. De fato, mesmo quando os números são marginalmente menores que a constante (no caso 0.001), o resultado não é bom.

O procedure expt vem na distribuição padrão com o PLT Scheme, enquanto sqrt é o mostrado pelo livro. Pode-se ver que a diferença entre a raiz calculada por sqrt e a calculada por expt é bastante significativa.
Uma "mostração" (não confundir com demonstração) simples de que sqrt não funciona para números pequenos é dada a seguir: Se considerarmos que sqrt é não-decrescente, ou seja, que (x . >= . y) implica ((sqrt x) . >= . (sqrt y)), tem-se que o menor valor que a função sqrt pode retornar é aquele que ela retorna quando o argumento é 0, ou seja (sqrt 0). Assim, podemos estar certos de que sqrt não vai funcionar para qualquer número m cuja raiz for menor que (sqrt 0). No caso das constantes 0.001 para good-enough? e 1.0 como o chute inicial, todos os números cuja raiz for menor que 0.03125 vão apresentar resultados ruins. Mas o fato que eu "mostrei" é que, independentemente da constante, sempre haverá um intervalo para o qual ela será inadequada.
Agora vamos testar para números grandes (10^200 e 10^300):

Para 1.0e200, o resultado está correto, mas para 1.0e300, sqrt nunca produz um resultado. Isso acontece porque o procedure good-enough? jamais retorna #t se o guess for um número grande. Vejamos: se o argumento for suficientemente grande, sua raiz também o será. Assim, para que a raiz de um número grande seja retornada, o sistema deve ser capaz de trabalhar com um valor alto para guess. Porém, como o computador tem precisão (de ponto flutuante) limitada, nesse caso a diferença entre (square guess) e x não pode ser calculada com a precisão desejada (0.001, no caso). Assim, se guess for suficientemente grande, good-enough? sempre retorna #f e a avaliação nunca termina.
Vamos reescrever as funções de acordo com a dica no exercício. Eu reescrevi todas as funções relacionadas colocando um "i"(de improved) no começo do nome. O novo isqrt agora também funciona para números negativos (veja que Scheme suporta números complexos). Além disso, zero agora é um caso especial.

Agora, isqrt funciona bem em números muito pequenos, e muito grandes.


Exercício 1.8
O método de Newton para as raízes cúbicas é baseado no fato de que, se y é uma apresentação para a raiz cúbica de x, então uma melhor aproximação é dada pelo valor

Use esta fórmula para implementar um procedure cube-root análogo ao da raiz quadrada.Solução: O algoritmo é absolutamente análogo ao da raiz quadrada. A principal mudança é no método improve. Ao invés de usar a fórmula (y + x/y)/2, em que y é a aproximação atual, eu uso a fórmula dada pelo exercício.

Alguns testes: