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:
- operadores aritméticos permitem múltiplos argumentos, então a + b + c vira (+ a b c).
- 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.
- 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:
- Avalie
test
- Avalie
0
- Avalie
(p)
- 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:
