SICP: Resumão e o que esperar

Este post é motivacional: justifica por que escolhi o SICP e não outro livro qualquer. Além disso, apresenta um resumo (uma visão de 10 mil pés de altitude) do conteúdo do livro, para que todo mundo saiba o que esperar dele. Como é um resumo de um livro com mais de 600 páginas, esse post é extenso. Porém, não é imprescindível. Quem quiser chegar logo aos exercícios resolvidos, pode ignorar todo o texto abaixo e ir direto ao próximo post.

O Structure and Interpretation of Computer Programs, carinhosamente chamado de SICP (pronúncia: seek p), é um dos melhores livros sobre computação jamais escritos. Síntese de alguns dos aspectos mais importantes sobre computação, o objetivo do livro é ensinar ao leitor a programar. Eu programo desde os 13 anos, e esse livro me ensinou a programar (de novo). O livro encara a programação não como mera maneira de fazer com que o computador faça algo, mas  como um meio de expressar e comunicar ideias. Mais precisamente, ideias sobre processos.

Programas, sendo elementos de comunicação, devem ser feitos para que humanos possam ler, e apenas eventualmente para que computadores possam executar. Sabe as constatações sobre a importância da legibilidade e manutenibilidade de código, que estão bem na moda nos últimos 3 a 5 anos? Esses caras já tinham notado a importância disso na década de 70!!!

O livro é uma viagem, no melhor sentido da palavra. Mas não é para os "fracos de coração". Pense bem, o que você espera de um livro cuja dedicatória é "Este livro é dedicado, em respeito e admiração, ao espírito que vive no computador". Só pode ser muito bom, ou muito ruim. Aliás, as opiniões das pessoas sobre o SICP (vide reviews do Amazon) são altamente polarizadas. Ninguém fica em cima do muro... Eu, obviamente, estou no grupo dos que adoram o SICP. Pra mim, ele tem pelo menos uma boa ideia (um momento a-ha!!!) em cada página. Às vezes, mais que isso...

Outro aspecto interessante de SICP é que ele ensina a programar, mas não ensina uma linguagem de programação. Sim, você entendeu bem, e não, isso não é um absurdo. A linguagem usada durante o livro é um subconjunto da linguagem Scheme. Scheme é um dialeto de Lisp e, assim sendo, tem muito pouca sintaxe. Além disso, a maioria das implementações utiliza um ambiente interativo no qual você pode digitar as expressões e visualizar seus resultados, sem se preocupar com entrada e saída. Ou seja, a parte de Scheme utilizada pelo livro é muito fácil de aprender, então não precisa ser ensinada explicitamente. Você vai "pegando o jeito" enquanto faz os exercícios.

Como síntese de diversos aspectos sobre computação, o livro faz um excelente trabalho. Tem apenas cinco capítulos, divididos em 22 seções. Meu plano é fazer um post por seção, mas caso alguma seção seja muito grande, farei mais de um post, em casos especiais. A seguir, apresento um resumo de cada capítulo.

Capítulo 1 - Construindo Abstrações com Prodedures

No primeiro capítulo, você aprende as características básicas da linguagem. Suas primitivas, meios de combinação, e meios de abstração. O principal meio é a definição de procedures. Os procedures definidos nos capítulos 1 e 2 são, de fato, funções, no sentido matemático da palavra. Isso quer dizer que a parte da linguagem usada nos dois primeiros capítulos é funcional, não tendo nenhum efeito colateral.

Além disso, inicialmente só se trabalha com números. Os conceitos mais importantes apresentados são o conceito de expressão, a avaliação de expressões pelo método da substituição, a relação entres procedures e os processos que eles geram, recursão linear e iteração, recursão em árvore e, principalmente, procedures de primeira classe.


Acredite: funções de primeira classe são a primeira revolução, apresentada no SICP, na maneira de pensar sobre programação. Scheme tem como um de seus pilares o fato de possuir procedures de primeira classe. Isso quer dizer que os procedures podem ser passados como argumentos para outros procedures, e podem ser retornados a partir de outros. Tais propriedades possibilitam novas maneiras de organizar os programas, evitando a repetição de código e a repetição de ideias.

Capítulo 2 - Construindo Abstrações com Dados

Todas as funções do capítulo 1 trabalham apenas com números. No capítulo 2, são apresentadas as ideias de dados compostos, dados hierárquicos, sequências, dados simbólicos (não encontrados em muitas linguagens), entre outras coisas. Basicamente, o capítulo serve para dar uma "embaçada" na ideia de que "funções e dados são coisas diferentes". Você deve estar pensando: "é lógico que funções e dados são coisas diferentes, afinal de contas as funções (ativas) processam os dados (passivos)". Bem, isso não é bem verdade (não falo mais pra não estragar a surpresa). Quem ler o livro vai entender...

Além disso, o capítulo mostra a importância de programar para uma representação abstrata de uma determinada estrutura, e não para sua representação concreta. Mais ainda, mostra uma maneira de organizar programas a partir da introdução de camadas de abstração, onde cada camada superior tem acesso as camadas inferiores, por meio de interfaces bem definidas.


Capítulo 3 - Modularidade, Objetos e Estado

Nos dois primeiros Capítulos, em nenhum momento se escreve o equivalente ao que, em C (ou Java), seria "int i; i = 3;". Ou seja, não há nenhum assignment. Isso mesmo, são mais de 200 páginas, 120 exercícios (alguns complexos como codificação de Huffman ou mesmo o problema das 8 rainhas), e nenhum assignment. Isso tem o efeito de uma bela sacudida. Antes de ler o SICP pela primeira vez, em 2007, eu simplesmente não pensava que isso fosse possível.

Ao perceber que você programou bastante sem usar assignment algum, você vê que, ao contrário do que pensava, assignments não devem ser necessariamente utilizados em todos os lugares. Aliás, atualmente (ou melhor, finalmente), é considerado boa prática de programação evitar a mutação de dados (assignments ou setters), utilizando-a somente quando estritamente necessário. Há uma grande classe de bugs que simplesmente deixa de aparecer nos seus programas quando não há efeitos colaterais (mutações). Além disso, fica mais fácil raciocinar sobre operaçoes concorrentes em objetos imutáveis, bem como fica mais fácil a paralelização automática de programas sem efeitos colaterais. Portanto, vá em frente e passe a usar o modificador  final em todos os atributos de suas classes que não necessitem ser alterados.

Apesar de não ser verdadeira a ideia de que a única maneira de programar é com assignments, há situações em que eles são imprescindíveis. Para representar estados de objetos que mudam com o tempo, como o saldo na sua conta bancária, por exemplo assignments são necessário. Uma vez constatado esse fato, o livro mostra os benefícios e os custos da introdução de assignment, depois mostra as novas regras para avaliação de expressões (uma vez que os assignments são introduzidos, a regra da substituição fica inválida). Em seguida, são mostrados exemplos de estruturas de dados mutáveis, um simulador para circuitos digitais, e um propagados de restrições (muito legal).

As duas seções mais importantes do capítulo 3 são, em minha opinião, a seção sobre concorrência e a seção sobre streams. A seção sobre concorrência mostra a relação entre tempo e sistemas concorrentes, e apresenta mecanismos para controle da concorrência. A seção sobre streams é, na minha opinião, a segunda revolução no livro. Mostra como podem ser implementadas estruturas de dados que, aparentemente, são infinitas. Basicamente, você representa uma estrutura infinita como uma lista preguiçosa (lazy), em que os elementos são carregados somente quando seus valores são necessários. Usando streams, é possível expressar vários algoritmos de maneira mais elegante e expressiva.

Capítulo 4 - Abstração Metalinguística

O capítulo 4 explora um fato a que se dá pouca importância: O interpretador da sua linguagem é apenas mais um programa. Tende-se a ver interpretadores (e compiladores) como entidades mágicas, e ter com respeito a eles um comportamento passivo. Uma vez que o interpretador é apresentado como apenas mais um programa (e um que nem é tão difícil assim de programar), isso dá bastante poder ao programador, que agora está em par com o designer da linguagem. O programador não precisa se limitar a contentar com o que lhe foi dado, e pode experimentar com linguagens. O programador é o novo designer... Lisp sempre teve esse espírito, por exemplo através do sistema de macros. Embora o SICP não aborde macros, ele dá um vislumbre do que é possível uma vez que se tenha acesso de escrita (e não apenas leitura) à sua linguagem.

São desenvolvidos vários interpretadores. O primeiro é um simples interpretador metacircular. Depois, é feito um interpretador com lazy evaluation, em seguida implementa-se o operador amb de backtracking e, finalmente, desenvolve-se um mecanismo para programação lógica que, embora tenha sintaxe Lisp, tem semântica parecida com o Prolog.

Capítulo 5 - Computando com Máquinas de Registrador

O interpretador desenvolvido no capítulo 4 é de Scheme, para Scheme. O observador atento dispara: "assim não vale: como você vai implementar o primeiro interpretador de Scheme?". Além disso, alguém mais atento ainda pode verificar que, por exemplo, o interpretador metacircular só será tail-recursive se o interpretador original também o for. Ou seja, o nível é muito alto...

O capítulo 5 corrige de certa forma esse problema. É mostrado o design de máquinas de registradores, que podem ser encaradas como máquinas abstratas, cujo comportamento é mais próximo do de um computador real. Em seguida, mostra-se uma linguagem para descrever máquinas de registradores, desenvolve-se um simulador para uma máquina, apresentam-se conteúdos sobre alocação dinâmica e coletor de lixo, e, finalmente, mostra-se um compilador de Scheme.


Finalmente...

Como se pode ter uma ideia, o livro é bem completo. Começa em operações com números e chega até a compilação da linguagem. Em cada seção, novos conhecimentos são apresentados e testados com exercícios bastante "desafiadores". O livro sem dúvidas é pra quem quer ter um maior entendimento da área de computação como um todo, e não pra quem quer apenas aprender um novo truque. Por outro lado, os conhecimentos mostrados no SICP são perenes, e vão me acompanhar durante toda a minha carreira na área. Espero que meus posts sejam úteis para mais alguém. No próximo post, falo sobre os exercícios da seção 1.1 - Os elementos da programação.