Review: Logicomix

Agosto 12, 2012

Logicomix é uma estória em quadrinhos sobre a busca do fundamento da matemática. É um livro fantástico porque mistura romance, história, mitologia e matemática. Além disso é uma meta-estória, pois relata o processo de desenvolvimento dos quadrinhos na própria estória.

Um dos autores (e personagem) do livro é Christos Papadimitriou, atualmente professor de teoria da computação em Berkeley. Durante minha iniciação científica cheguei a estudar um de seus livros escrito com Ken Steiglitz sobre Otimização Combinatória, mas achei muito difícil e acabei usando outro :P

Teóricos da computação fazem muito uso da lógica, especialmente os que trabalham com complexidade computacional e computabilidade. A estória dá a entender que Papadimitriou foi convidado como o especialista em lógica, embora o autor principal, Apostolos Doxiadis tenha formação matemática também.

Spoiler! O restante deste post contém um breve resumo do livro, além de uma análise pessoal.

Resumo

Tractatus Logico-Philosophicus

Bertrand Russell é o personagem central do livro que descreve sua saga em busca dos fundamentos da matemática.

Russell aparece em dois planos: em um está no presente, palestrando a um grupo de americanos contrários à adesão dos Estados Unidos à Segunda Guerra Mundial. Durante essa palestra ele conta a história de sua vida, que acontece em um outro plano. A grande maioria dos acontecimentos acontece nesse segundo plano e o Russell do plano presente serve mais como um narrador.

Além desses dois planos temos o plano em que os autores do livro estão elaborando a estória ao mesmo tempo em que ela acontece. Eles geralmente aparecem para justificar alguma discrepância entre a história e a estória, além de explicar conceitos mais técnicos.

Logo criança, Russell torna-se órfão e passa a viver com seus avós na mansão Pembroke. É apresentado aos trabalhos de Euclides por um professor particular de matemática.

Russell segue para o Trinity College, onde conhece Alfred Whitehead. Casa-se com Alys Smith e então fazem uma viagem ao continente, passando primeiramente pela Alemanha, onde conhecem Gottlob Frege e George Cantor (embora o livro deixe claro que Russell não os conheceu pessoalmente).

Na França, conhecem a esposa de Whitehead, Evelyn Wade. A estória retrata um interesse de Russell em Evelyn, embora em nenhum momento do livro pareça ter havido algo mais entre eles. Depois, Russell participa do congresso internacional de matemáticos onde David Hilbert divulga a famosa lista de 23 problemas abertos em matemática.

Neste ponto Russell descobre um paradoxo na teoria dos conjuntos, que abala o mundo da matemática. Whitehead e Russell decidem então começar a escrita do Principia mathematica, que se mostra uma tarefa desgastante.

Russell passa a dar aulas em Cambridge e é quando Ludwig Wittgenstein torna-se seu estudante de doutorado. Evelyn, a esposa de Whitehad acha que está prestes a morrer e pede para Russell consolar seu filho, Eric. Cansado de seus trabalhos com a lógica, Russell sente-se reconfortado por exercitar sentimentos como compaixão e amor para com Eric.

Começa a primeira Guerra Mundial. Russell se posiciona contra a adesão do Reino Unido, o que acaba o levando à prisão. Wittgenstein se alista ao exército Autro-Húngaro enquanto Eric, filho de Whitehead, faz o mesmo pelo lado britânico. Wittgenstein sobreviveu à guerra, fazendo-o mudar sua maneira de ver o mundo. Por outro lado, Eric é abatido em combate.

Após o fim da primeira guerra, Wittgenstein estava impedido de ir à Inglaterra por ser austríaco e portanto se encontra com Russell em território neutro: Haia, Holanda. Nesse encontro Wittgenstein contrapõe diversas ideias de Russell.

Russell casa-se pela segunda vez com Dora Black, tendo o seu primeiro filho. Seu casamento era bastante liberal, sendo que ele aceitava que amantes frequentassem sua casa. Seus pais também tiveram um casamento desta forma. Juntos decidiram fundar uma escola progressista para crianças, a Beacon Hill. À mesma época, Wittgenstein começa a dar aulas em escolas primárias.

O matemático Moritz Schlick passa a organizar o Círculo de Viena, uma associação de filósofos que se encontravam em torno da Universidade de Viena. Em uma dessas reuniões, Russell conhece Kurt Gödel e John Von Neumann e foi nesse encontro que Gödel anunciou seu primeiro teorema de incompletude, destruindo o sonho de Russell de definir um conjunto de axiomas que pudesse demonstrar todas as verdades matemáticas. Em seguida, as influências nazistas começaram a se espalhar pelo continente e em 1936, Schlick foi assassinado por um fanático nazista, o que pôs fim ao círculo e é nesse ponto que Russell conclui sua narrativa.

A estória termina voltando para o plano dos autores, que vão assistir à participação de Anne Bardy em uma encenação da peça Oresteia.

Matemática

Das diversas referências matemáticas presentes no livro, gostaria de comentar sobre as três que achei mais interessante.

Paradoxo de Russell

Em 1901, Russel apresenta um paradoxo da teoria dos conjuntos. Esse paradoxo por ser melhor entendido através de um exemplo, o paradoxo dos barbeiros.

Considere uma cidade onde existe apenas um barbeiro e uma lei que diz que o barbeiro deve fazer a barba de todos os homens que não se barbeiam sozinhos, mas não pode fazer a barba de quem se barbeia sozinho.

Consideremos duas possibilidades: o barbeiro se barbeia sozinho ou não. Se ele se barbeia sozinho, está infringindo a lei, porque ele não pode barbear quem se barbeia sozinho. Por outro lado, se ele não se barbeia, a lei o obriga a fazer sua própria barba. Conclui-se que a lei é contraditória.

A generalização para a teoria dos conjuntos é a seguinte: seja R conjunto de todos os conjuntos que não contém a si mesmos. Pergunta-se: R está contido em si mesmo? Vamos analisar duas possibilidades. Se R está contido em si mesmo, então R é um conjunto que contém a si mesmo e não poderia estar em R. Por outro lado, se R não está contido em si mesmo, ele é um conjunto que não contém a si mesmo e portanto deveria ser incluído em R :)

O Infinito e a Teoria dos Conjuntos

Em Logicomix, Russell descreve o paradoxo do hotel de Hilbert que exemplifica o quão contra-intuitivo é trabalhar com o conceito de infinito. A ideia por trás do paradoxo pode ser usada para provar, por exemplo, que existe uma bijeção entre os números naturais pares e os números naturais!

Isso está relacionado com o trabalho de George Cantor, que criou os conceitos de conjuntos enumeráveis e não enumeráveis, sendo os enumeráveis aqueles com mesma cardinalidade dos números naturais, ou seja, para os quais existe um mapeamento um pra um de seus elementos para com os números naturais.

Assim como os números naturais pares têm mesma cardinalidade dos números naturais, Cantor demonstrou que os números inteiros são enumeráveis assim como o conjunto dos números racionais! O conjuntos dos números reais não é enumerável.

Os 23 problemas de Hilbert

David Hilbert divulgou uma lista de 23 problemas não resolvidos à época de 1900. Há três problemas sobre os quais gostaria de comentar.

O principal problema da lista, e que até hoje não foi resolvido, é o problema 8, que é demonstrar a Hipótese de Riemann. O livro The music of primes, fornece uma introdução bem acessível sobre a hipótese, a função zeta de Riemann e a relação com números primos.

Um problema importante também é o número 2, provar que os axiomas da aritmética são consistentes. O segundo teorema da incompletude de Gödel mostra que não é possível provar esse teorema usando a própria aritmética. Entretanto, não há um consenso se isto é uma solução ou não para o problema.

Finalmente, um problema que eu acho particularmente interessante é o número 10: encontrar um algoritmo que determina se uma equação Diofantina polinomial com coeficientes inteiros tem uma solução.

Gosto desse problema porque é fácil de enunciar, está relacionado à área que pesquisei no mestrado (programação linear inteira) e porque foi resultado de um trabalho longo e de contribuição de diversas pessoas, Martin Davis, Yuri Matiyasevich, Hilary Putnam e Julia Robinson.

Mitologia

Algumas referências mitológicas aparecem na estória. A primeira é a um mito indiano sobre a tartaruga que segura o mundo. Russell faz a analogia como o mundo sendo a matemática e a tartaruga seus fundamentos.

Em certo ponto Whitehead mostra a Russell o quadro “As Danaides” de John Waterhouse. As Danaides são as 50 filhas de Dánao, que estavam prometidas aos 50 filhos de Egipto, seu irmão gêmeo. Todas exceto Hipernestra assassinaram seus esposos na noite de núpcias e como punição foram obrigadas por Hades a encherem um jarro de água com furos durante toda a eternidade.

As Danaides: pintura a óleo de John Waterhouse

Whitehead usou o mito como metáfora para o trabalho do Principia Mathematica. Russell queria encontrar um fundamento para a matemática, mas sempre via necessidade de fundamentar cada base que encontrava. Como se disse no livro, ele estava procurando a base da tartaruga que segurava o mundo, mas encontrou uma torre infinita de tartarugas.

Finalmente, temos a encenação peça Oresteia, uma trilogia escrita pelo dramaturgo grego Ésquilo.

O livro retrata a terceira peça, Eunêmides, no qual as Erínias, deusas da vingança decidem punir Orestes. Atena intervém e decide que o futuro de Orestes deve ser decidido por um júri popular.

Literatura e Teatro

Alguns clássicos da literatura e teatro aparecem na estória. O avô de Russell possuia uma biblioteca onde Bertie descobriu a Divina Comédia de Dante Alighieri, que foi chamado de o livro proibido.

Em Cambridge lê Pais e Filhos, de Ivan Turguniev. Segundo a Wikipédia, o protagonista do livro é Bazárov, um jovem intelectual materialista, que nega o amor, a arte, a religião e a tradição, e diz acreditar apenas em verdades cientificamente comprovadas pela experiência. Essa negação da religião e tradição podem ser encontradas na personalidade de Russell na estória.

A estória também retrata a peça de teatro Espectros, do norueguês Henrik Ibsen. Há um destaque para a frase “os pecados dos pais se repetem nos filhos”. Talvez seja uma referência ao estilo de vida dos pais de Russell, que acabou se repetindo em seu casamento com Dora.

Russell passa a recitar versos do poema Alastor, de Percy Shelley. Segundo a Wikipedia, Alastor conta a história de um poeta que persegue a parte mais obscura da natureza em busca de “verdades estranhas em terras desconhecidas”. Podemos enxergar um paralelo aqui com a busca pelos fundamentos da matemática por porte de Russell.

Ao conhecer Alys, Russell cita diversos personagens do livro Alice no País das Maravilhas, de Lewis Carroll, como o Tweedledee, Tweedledum, Gato de Cheshire e o Chapeleiro maluco.

Após o fim da Primeira Guerra Mundial Russell demonstra seu descontentamento com o dadaísmo e cita versos do poema The Second Coming, the William Butler Yeats, que refletem sua opinião.

Conclusão

Gostei bastante deste livro e recomendo a quem gosta de lógica e história da matemática. Eu particularmente não sou muito fã de história em quadrinhos, achei que se fosse em prosa a estória poderia conter mais detalhes. Lendo sobre a vida dos principais personagens na Wikipedia, penso que faltou um pouco de coesão nos fatos relatados.

Achei excelente inserir referências a clássicos da literatura para ajudar a caracterizar a personalidade de Russell. Fico feliz de ter escrito esse resumo e análise porque acho que consegui enxergar alguns detalhes que tinham passados despercebidos na primeira leitura.

Interpretei o fato da estória ser uma meta-estória como uma alusão ao paradoxo de Russell, que tem como base conjuntos que contêm a si mesmos. No caso do Logicomix é uma estória que contém a si mesma.

A encenação de Orestéia me pareceu desconexa com o restante da estória. Talvez a ideia fosse mesmo contar duas estórias independentes (a de Bertrand e a dos autores).

Leitura adicional

Alguns livros e links que eu selecionei para o aprofundamento no conteúdo do Logicomix. Na verdade só li o primeiro e é o único que posso recomendar. Os outros estão na minha pilha de leitura.

[1] The Music of the Primes de Marcus du Sautory – Já li, e gostei muito. Fala sobre os 23 problemas de Hilbert e a hipótese de Riemmann de uma maneira bastante acessível.
[2] Alice no país das maravilhas de Lewis Carroll – Lewis Carroll era um matemático e lógico. Este livro é mencionado no Logicomix.
[3] Scott Aaronson – Filosofia e Ciência da Computação Teórica, Scott Aaronson é um professor de Teoria de Computação no MIT e conhecido por seu trabalho em Computação Quântica.

Anúncios

Review – The Pragmatic Programmer: From Journeyman to Master

Julho 1, 2012

Faz algum tempo que comprei o livro The Pragmatic Programmer: From Journeyman to Master (há também a versão em português, dica do Leonardo) e recentemente terminei de lê-lo.

É um livro sobre desenvolvimento de software. Encontrei boas recomendações para ele em diversos sites e portanto decidi dar uma olhada. O livro está organizado em 8 capítulos que estão divididos em seções menores, num total de 46.

Cada uma dessas seções corresponde a uma dica relacionada a alguma das diversas fases do processo de desenvolvimento de sofware, incluindo levantamento de requisistos, projeto, desenvolvimento e teste. Vou comentar brevemente sobre os tópicos que achei mais interessantes.

A Teoria da janela quebrada. Uma janela quebrada em um prédio de uma cidade dá a impressão de abandono aos habitantes locais. Aí começam a aparecer pichações, danos estruturais começam a aparecer até que o senso de abando se torna evidente. Analogamente, uma janela quebrada no desenvolvimento de software são designs ou códigos ruins, que se forem deixados para consertar depois dão a sensação de descaso com a qualidade do software e fatalmente a qualidade do código se deteriorará.

Software bom o bastante. A dica pode ser resumida na frase “um ótimo software hoje é melhor do que um software perfeito amanhã”.

Seu portifólio de conhecimento. Os autores sugerem metas para construir e atualizar sua base de conhecimento:

  • aprenda uma linguagem todo ano
  • leia um livro técnico a cada trimestre
  • leia livros não-técnicos
  • assista aulas

Princípio DRY. Em inglês, DRY é um acrônimo Don’t Repeat Yourself. A motivação é que duplicação causa re-trabalho e devemos sempre manter as duplicações consistentes. Pra mim essa dica parecia óbvia, mas eu nunca tinha pensado nela conscientemente.

Um caso em que ela aparece é nos comentários de código. Um comentário que explica o código viola o princípio DRY porque o código em si já possui essa informação. De fato, já me deparei diversas vezes com código legado em que o comentário dizia uma coisa e o código fazia outra, provavelmente porque alguém alterou o código mas esqueceu de atualizar o comentário. Isso me lembra que uma citação:

Code never lies, comments sometimes do.

Ron Jeffries

O autor prega que código com bons nomes de variáveis e funções não exige comentário. Eu gosto de comentar pelo menos funções. Nesses casos, se estiver trabalhando com controle de versão, eu geralmente coloco o número da revisão em que em adicionei o comentário, pois se alguém quiser saber se o comentário corresponde ao código, basta fazer um diff. O uso ou não de comentários é um assunto controverso.

Balas traçantes. (Trace bullets) A analogia vem da situação em que você deseja acertar um alvo no escuro usando uma metralhadora. Uma abordagem é calcular precisamente a posição do alvo, a orientação da arma e atirar. Isso funciona bem quando o alvo é estático, mas em muitos casos o alvo é móvel e o tempo gasto calibrando o alvo pode ter sido em vão. Uma abordagem diferente é usar balas que deixam rastros luminosos definindo sua trajetória. Com isso o atirador tem um feedback que o ajuda a calibrar o próximo tiro.

No contexto de desenvolvimento de software, temos especificações que mudam com o tempo. Atirar com balas traçantes consiste em implementar uma arquitetura com o mínimo de funcionalidades, mas fazendo uso de todo o sistema desde a consultas simples a banco de dados até a interface gráfica. A vantagem deste método é que você consegue um feedback mais rápido do cliente, o que pode ajudar a consolidar as especificações.

Projeto por contrato. (Design by contract) O conceito de projeto por contrato foi desenvolvido por Bertrand Meyer para a linguagem de programação Eiffel. Basicamente, o contrato é caracterizado por pré-condições, pós-condições e invariantes em uma função. Pré-condições são hipóteses que a função supõe verdadeiras como por exemplo um parâmetro não nulo. As pós-condições são condições que devem ser satisfeitas após a execução do método. Finalmente, as invariantes são condições que valiam antes da chamada da função e continuam valendo depois, embora elas não necessariamente valessem ao longo da execução da função.

Contratos estão relacionados com testes e corretude de código. Recentemente o Google disponibilizou uma biblioteca chamada Cofoja (Contracts for Java) que permite o uso de contratos através de anotações.

Programação assertiva. Consiste no uso de assertivas para verificar condições que você supõe serem verdadeiras. A dica dada é se você acha que uma condição nunca ocorrerá em um determinado trecho de código, então adicione uma asserção para garantir que não irá de fato.

Eu particularmente gosto de assertivas, porque servem como forma de documentar o código e ajudam na depuração de erros, quando alguma hipótese foi violada.

Em Java as assertions são desabilitadas por padrão, pois o argumento é que elas podem impactar o desempenho do código se posta em produção. Eu acho que mesmo em produção assertivas podem ser usadas e se a verificação de alguma delas é tão complexa que pode interferir no tempo de execução do código, talvez valha a pena deixá-la como um teste.

Para garantir que assertivas estão ligadas em Java, podemos adicionar o seguinte trecho de código em alguma classe que será chamada durante a execução do código:

static {
  boolean assertsEnabled = false;
  // Linha não executada com assert desligado
  assert assertsEnabled = true; 
  if (!assertsEnabled)
    throw new RuntimeException("Asserts desabilitados!");
} 

Lei de Deméter. A lei de Deméter é um guia de desenvolvimento para diminuir o acoplamento entre partes de um software. No caso particular de métodos e funções, a lei diz que um método só deve chamar os métodos pertencendo: ao próprio objeto, a um objeto passado como parâmetro, a objetos instanciados dentro do método e a objetos declarados dentro do método.

O nome vem do projeto Demeter desenvolvido da Universidade Northeastern que é sobre programação adaptativa.

O nome do projeto faz referência à Deusa grega da agricultura, Deméter, pois os criadores do projeto estavam trabalhando em uma simplificação de uma linguagem chamada Zeus, queriam nomear a ferramenta com uma nome relacionado e optaram por Deméter, a irmã de Zeus [1].

Acoplamento temporal. Muitos designs buscam o baixo acoplamento estrutural, entre classes do projeto. Um termo que eu não conhecia, mas achei interessante, é o acoplamento temporal, que representa a dependência entre as ações executadas pelo software. Um baixo acoplamento temporal é desejável pois facilita o uso de programação paralela.

Conclusão

O livro contém diversas dicas e descrevi as que achei mais interessantes. O texto está bem escrito e é de leitura fácil. A divisão em pequenas seções facilita a leitura casual.

Outros tópicos cobertos sobre os quais não comentei são: refatoração, testes, levantamento de requisitos, escrita das especificações, uso de ferramentas de modelagem, etc. Pelo que pude perceber, a essência dos conselhos dados segue a linha da metodologia ágil.

Embora eu não esteja seguindo as metas sugeridas, eis aqui o status delas:

  • Livros técnicos: esse foi o primeiro que li no ano
  • Livros não-técnicos: faz muito tempo que não leio um :/
  • Nova linguagem: estou aprendendo Haskell desde o ano passado, mas ainda tenho vontade de aprender R e Erlang
  • Aulas: este ano fiz o curso de PGM! Pretendo me matricular no curso de Visão Computacional até o fim do ano.

Referências

[1] Demeter project: What is Demeter?