Bill Gates

Ocasionalmente alguém cai no meu blog procurando a "Biografia de Bill Gates". A biografia que eu conheço e lí é Gates de Stephen Mames e Paul Andrews. A história do surgimento da industria dos computadores pessoais (incluindo a Microsoft) pode ser lida em Fire in the Valley de Paul Freiberger e Michael Swaine.

Da leitura destes livros me veio uma imagem de Bill Gates diferente daquilo que a media normalmente apresenta. Sem dúvida ele tem grande conhecimento técnico e é um grande programador. Também é inegável o seu faro em reconhecer oportunidades. Entretanto, tudo isso me parece secundário frente ao que considero ter sido o principal motivador de Bill: fechar o negócio. Para mim é esta agressividade comercial a principal marca da Microsoft, pelo menos até o ano 2000. Agressividade esta que às vezes encrencou a Microsoft e que levou a práticas algumas vezes consideradas ilegais pela justiça americana.

Relato abaixo duas situações famosas, descritas em detalhes nos livros que citei, e que acredito reforçarem a minha opinião sobre Bill Gates.

O Surgimento da Microsoft

A maioria das pessoas já ouviu falar de como Paul Allen foi correndo mostrar para Bill Gates a edição de janeiro de 1975 da revista Popular Electronics que trazia na capa o Altair 8800 da MITS e neste momento os dois decidiram fazer um interpretador BASIC para ele. Muitos talvez saibam que Bill Gates ofereceu o produto para a Altair, apesar de não ter começado o desenvolvimento, e como a primeira versão foi construída rapidamente. O que poucos sabem é que este foi um mau negócio na ponta do lápis.

O Altair 8800 que aparecia na capa era um mockup de papelão (o protótipo, que não incluia ainda o famoso barramento S-100, foi perdido no transporte). Para aparecer na capa da revista, Ed Roberts (o dono da MITS) chutou um preço bem baixo e corria o risco de ter prejuizo. A solução era lucrar nos acessórios e o principal deles era a placa de memória. O kit original vinha com apenas 256 bytes de Ram, quem queria fazer algo sério precisava da placa de 4K e do BASIC da Microsoft. A placa de memória tinha uma margem imensa e um imenso problema: não funcionava. Não demorou muito para alguém se cansar da placa de memória da MITS, projetar uma e descobrir que dava para vender uma placa que funcionava por um preço bem inferior. Ed Roberts resolveu apelar para o seu trunfo: o BASIC. A MITS tinha um contrato de exclusividade do BASIC da Microsoft para processadores 8080 e compatíveis e Ed Roberts passou a vender o BASIC por $150 para quem comprasse a placa da MITS e $500 para os outros. A reação dos clientes foi a pirataria do BAISC, que resultou em uma famosa "Carta Aberta aos Hobistas" do Bill Gates.

A exclusividade da MITS estava prejudicando a Microsoft com mais que as baixas vendas do BASIC. Embora a Microsoft tivesse fechado acordo com outros fabricantes que usavam outros processadores, o primeiro grande negócio em vista era com a Tandy/Radio Shack cujo TRS-80 usava o Z80 que estava coberto pela exclusividade da MITS. Em meados de 1977 a Microsoft estava em dificuldades financeiras. A sorte da Microsoft foi que Ed Roberts tinha negligenciado itens básicos do acordo, inclusive não pagando os royalties combinados. Com base nisto a Microsoft conseguiu cancelar o acordo na justiça e fechar o negócio com a Tandy e equilibrar as contas.

O Sistema Operacional do PC-IBM

Quando a IBM resolveu desenvolver o seu computador pessoal, ela decidiu usar componentes de mercado, inclusive o BASIC da Microsoft e o sistema operacional CP/M da Digital Research. Como todos sabem o PC-IBM acabou sendo lançado com um sistema operacional da Microsoft, o MS-DOS.

Até o final de sua vida, Gary Kildall (dono da Digital Research) teve que agüentar a versão de que ele tinha ido passear em seu avião ao invés de atender a IBM. Na verdade, Kildall cuidava mais da parte técnica da Digital Research, quem cuidava dos contratos com os fabricantes de hardware era a sua esposa, Dorothy.

No dia da visita da IBM, Gary foi cumprir uma visita agendada anteriormente com outro cliente (pilotando realmente o seu avião) e Dorothy atendeu os representantes da IBM. Antes de dizer qualquer coisa, um advogado da IBM solicitou que ela assinasse um NDA (Non-Disclosure Agreement). Dorothy fez aquilo que todos nós sabemos ser o certo antes de assinar um documento: leu-o cuidadosamente. O documento era terrivelmente favorável à IBM. Dorothy fez aquilo que os advogados sempre recomendam: recusou-se a assinar e passou a negociar o texto do contrato. Embora este impasse tenha sido vencido, a relação entre a Digital Research e a IBM nunca foi boa. Também não ajudou nada o fato do CP/M-86 ter sido repetidamente adiado.

Como foi que Bill Gates se comportou quando a IBM entrou em contato com ele? A reação inicial dele foi: "a IBM é uma grande companhia". Ao contrário de Kildall, Gates se envolvia diretamente nas negociações. E não teve dúvidas em cancelar uma reunião com o chairman da Atari para atender a IBM, vestir um terno e gravata e convocar para a reunião um assistente - Steve Balmer. Ao ser apresentado o NDA, Bill Gates deu uma passada de olhos e assinou sem hesitar.

Enquanto que a diferença de cultura entre as empresas era um problema na relação entre a Digital Research e a IBM, Bill Gates se esforçava para agradar a IBM, apesar de tanto a Microsoft como a Digital Research terem um bando de hippies nos seus quadros. Quando, preocupada com os atrasos e os conflitos com a Digital Research, a IBM perguntou a Bill Gates se ele poderia fornecer também um sistema operacional, ele já tinha a resposta na ponta da língua (embora ainda não tivesse o produto).

Construindo um Compilador - Parte 3

Vamos começar a estudar nesta parte como fazer um analisador sintático. Na parte anterior, usamos uma máquina de estados (também chamada de autômato finito) para fazer a análise léxica. Na máquina de estados do analisador léxico os itens léxicos são reconhecidos analisando a entrada sequêncialmente da esquerda para a direita.

Na análise sintática esta forma de operação não é suficiente. O reconhecimento de uma construção sintática requer o reconhecimento de vários trechos, não necessáriamente da esquerda para a direita. Além disso, é comum um item ser definido de forma recursiva. Consideremos este exemplo de linguagem, onde os itens léxicos são num, '*', '/', '+', '-', '(' e ')':

e vamos analisar o seguinte "programa fonte":

10 + ( 70 - 4 * 5 )

o reconhecimento dos vários itens léxicos e sintáticos gera um árvore:
A figura acima sugere duas estatégias básicas para a análise sintática:

• análise ascendente, onde itens sintáticos mais complexos vão sendo reconhecidos a partir de itens sintáticos mais simples.
• análise descentente, onde se procura identificar itens sintáticos cada ver mais simples.

O algorítimo que apresentarei utiliza a análise descendente. Em cada passo teremos como objetivo reconhecer um item sintático. Para isto utilizamos uma tabela que representa os grafos que indicam as várias alternativas disponíveis naquele instante, junto com uma pilha que guarda os sucessivos objetivos à medida em que descemos na análise.

Considerando a expressão de exemplo, teríamos os seguintes passos iniciais:

• O nosso objetivo inicial é reconhecer uma expressão.
• O primeiro item de uma expressão tem que ser um termo, salvamos na pilha o ponto em que estamos no reconhecimento da expressão e passamos a tentar reconhecer um termo.
• O primeiro item de um termo tem que ser um fator, salvamos na pilha o ponto em que estamos no reconhecimento do termo e passamos a tentar reconhecer um fator.
• Um fator pode começar com um '(' ou com um número. No nosso caso encontramos o número '10' e com isto concluímos o reconhecimento de um fator.
• Retiramos da pilha o nosso objetivo. Estamos reconhecendo um termo, já reconhecemos um fator. As alteranativas seguintes são '*', '/' ou final do reconhecimento. Como o item seguinte é um '+', damos por encerrado o reconhecimento do termo.
• Voltamos assim ao reconhecimento da expressão. Já reconhecemos um termo, as alternativas seguintes são '+', '-' ou fim do reconhecimento.
• Como temos um '+', passamos a reconhecer um novo termo

Este algorítimo, que usa um autômato finito com pilha, permite analisar uma grande variedade de linguagens, mas não todas. A principal restrição é que cada item léxico reconhecido determina imediatamente o próximo "ramo" da sintaxe a ser examinado.

No próximo post vamos ver em detalhes como se implementa este algorítimo.

Três Livros Sobre C#

No ano passado incluí na minha coleção três livros sobre C# de características bem difererentes:

Pro C# 2005 and the .NET 2.0 Platform, Third Edition
Andrew Troelsen

Um livro bastante ambicioso, que tenta descrever a linguagem C#, a plataforma .Net e o framework .Net (e ainda encontra espaço para falar de conceitos gerais sobre programação orientada a objetos). É um livro imenso (ainda estou no primeiro terço), mas que gostaria de ter lido quando comecei a aprender C#. É claro que alguns assuntos como Windows Forms, ASP.Net, ADO.Net e Web Services ficam um pouco corridos (afinal existem livros inteiros sobre estes assuntos), mas é um dos poucos livros que explica bem o básico (no sentido de fundamento não de simples).

ASP.NET 2.0 Website Programming
Marco Bellinaso

A idéia do livro é ótima: descrever a construção de um site real do começo ao fim. Cada capítulo possui três partes: o problema, o projeto e a solução. Na primeira são descritos os requisitos, na segunda são discutidas as alternativas para atendê-los e na terceira é apresentado com detalhes a implementação adotada. O código todo está disponível para download (inclusive foi adotado como um dos exemplos pela Microsoft, veja aqui) e o site está on-line em http://www.dotnet2themax.com/thebeerhouse/.

O autor não foge de assuntos complexos nem economiza linhas de código e utiliza os recursos mais recentes do C# e do ASP.Net. O único porém é a diagramação do livro que deixa a leitura cansativa.

Altamente recomendado para quem desenvolver uma aplicação Web mais real que os Next/Next/Finish dos wizards do Visual Studio.

Visual C# 2005 - A Developer´s Notebook
Jesse Liberty

Este é um livro curto, que se concentra em algumas poucas (e importantes) novidades do C# 2.0 e Visual Studio 2005 e se destaca pela parte visual (imita um caderno com direito a um quadriculado de fundo e manchas de copo). O texto é muito bom, mas nem sempre muito profundo ou completo. Resumindo, é um livro extremamente agradável de ler, voltado para quem já conhece as versões anteriores do C# e quer se atualizar.

PS: Para quem está aguardando a terceira parte da série sobre Compiladores, peço um pouco de paciência, pois as coisas estão um pouco corridas.

Livro do Mês - Montenegro

Em torno da compra deste livro existe um história. No começo de dezembro, meu pai pediu de presente de Natal o livro "Casimiro Montenegro Filho A Trajetoria De Um Visionario" de Ozires Silva e Décio Fischetti. Procurando na internet, encontrei o livro nas Livrarias Cultura e Siciliano. Nos dois locais o livro estava com prazo de 6 dias úteis, porém a Siciliano tinha um preço um pouco menor e ofertas de parcelamento e frete grátis para compras acima de um certo valor.

Deste forma, resolvi comprar na Siciliano este livro junto com outros para dar de presente aos sobrinhos. Descobri também nas buscas a existência de um outro livro sobre o mesmo assunto: "Montenegro - As aventuras do marechal que fez uma revolução nos céus do Brasil" de Fernando Morais (autor de Olga e Chatô, que eu já tinha ouvido falar mas ainda não li). Resolvi surpreender meu pai e comprar os dois livros, o que me dava como vantagem adicional uma segurança extra no caso do livro não chegar a tempo para o Natal.

E realmente o livro não veio. Como desconfiei desde o começo, o prazo de 6 dias significava que o livro não estava em estoque e tinha que ser encomendado à editora. Por motivos que desconheço, a editora não entregou o livro à Siciliano (que me manteve informado sobre o atraso e desde o começo deu a opção de cancelar o pedido). A Livraria Cultura teve mais sucesso e o livro chegou até a ser objeto da "entrega foguete" (entrega no mesmo dia para São Paulo). Em meados de fevereiro resolvi entregar os pontos e cancelar o pedido na Siciliano e comprar da Cultura. Neste ponto a Cultura estava indicando prazo de 3 dias e poucas unidades em estoque (no momento está com prazo de 15 dias úteis). No lugar da entrega foguete as opções de frete eram expresso e normal. A entrega normal tinha um preço baixo (R$ 3) e um prazo razoável (3 dias) e foi minha opção. O livro chegou em dois dias via Sedex, de Porto Alegre (onde a Cultura tem uma loja).

Folheando o livro antes de entregar para o meu pai fiquei com a impressão de ser inferior ao do Fernando Morais, o que veio a ser confirmado pelo meu pai. Curioso sobre o assunto do livro, peguei emprestado o Montenegro do Fernando Marais para ler e é ele o "livro do mês" de fevereiro.

Montenegro - As aventuras do marechal que fez uma revolução nos céus do Brasil

O livro é a biografia de Casimiro Montenegro Filho, um cearense nascido em 1904 e foi o principal responsável pela criação do ITA (origem do interesse do meu pai).

O primeiro sentimento que me veio lendo o livro foi o meu grande desconhecimento da história do Brasil, talvez fruto de ter feito primário e ginásio numa época em que se ensinava que Tiradentes tinha a mesma aparência que Jesus. A história de Montenegro se entrelaça com a história do Brasil, dos acontecimentos que testemunhou na infância até a ditadura militar de 64 que o afastou do ITA, passando pelas revoluções de 30 e 32.

Na minha cabeça, o ITA era uma escola militar e uma fábrica de loucos. Nada sabia das idéias e motivos por trás da sua criação. Embora Montenegro fosse um militar, na sua concepção o ITA era um instituto primordialmente civil. Inspirado no MIT americano, o ITA foi uma tentativa de criação de um instituto de ensino de alto nível, com independência administrativa, para formar profissionais altamente qualificados e viabilizar o surgimento de uma industria aeronáutica nacional. A existência da Embraer é uma prova de que grande parte dos objetivos foram cumpridos (embora a independência nunca tenha vindo por completo e foi sufocada após o golpe de 64).

As dificuldades para a construção do ITA foram imensas. Burocracias, intrigas, invejas e paranoias se somaram à audácia de um idéia extremamente ambiciosa.

É bastante claro o esforço do autor em obter informações precisas sobre os fatos, não hesitando em apresentar múltiplas versões quando as pesquisas foram inconclusivas. O livro é bastante cativante, fazendo o leitor se apaixonar pela causa de Montenegro, passando a vibrar com as conquistas e sofrer com os reveses. Os inúmeros 'causos' relatados oferecem ao mesmo tempo um tom humorístico e uma idéia dos inúmeros contratempos enfrentados.

Na história de Montenegro estão elementos que continuam presentes: as intrigas políticas, a questão da educação, os sonhos de fazer no Brasil coisas no mesmo nível que o Primeiro Mundo.

Leitura altamente recomendada.

Fontes do DOS para Download

De vez enquando dou uma olhada no statcounter para ver por onde as pessoas chegaram a este blog, tipicamente por uma busca no google.

Uma busca curiosa foi pelos fontes do DOS. Embora até onde eu saiba a Microsoft não publicou os fontes do MS-DOS, quem estiver curioso sobre como fazer um sistema compatível tem pelo menos duas opções:

• FreeDOS: um projeto de software livre, é usado pelo excelente DosBox para simular um PC antigo e permitir rodar programas antigos (particularmente jogos).

• DR-DOS: tem uma história longa e curiosa. A Digital Research era a lider dos sistemas operacionais para os computadores profissionais de 8 bits com o CP/M-80. No lançamento do PC, a IBM deu preferência ao MS-DOS. Após anos tentando sem sucesso vender o CP/M-86, a Digital Research aproveitou um momento em que a Microsoft estava ocupada com os projetos do Windows e do OS/2 para lançar o DR-DOS. Altamente compatível com o MS-DOS, o DR-DOS 5 vinha com utilitários adicionais e utilizava os recursos de gerenciamento de memória do 386. A resposta da Microsoft foi o MS-DOS 5 e uma série de ações que posteriormente foram julgadas anti-competitivas (alguns documentos a respeitos podem ser vistos aqui). A Novell adquiriu a Digital Research e lançou um bundle do DR-DOS 6 com um pacote de rede local peer-to-peer (durante toda a vida do MS-DOS, a comunicação via rede local sempre foi um item a parte e que era explorado por empresas como a Novell e a Lantastic). Apesar de todo este esforço, o DR-DOS nunca conseguiu decolar e entre várias mudanças de dono acabou tendo os fontes liberados para o uso não comercial.

Construindo um Compilador - Parte 2

Nesta parte vamos ver como se constrói um analisador léxico. Como vimos na parte 1, ele é responsável por reconhecer os itens léxicos no fonte.

Itens léxicos típicos são identificadores de variáveis e rotinas, palavras reservadas, constantes e símbolos. Cada um destes itens se caracteriza por uma seqüência de caracteres que segue uma regra simples (por exemplo, "um identificador deve começar por uma letra e possuir somente letras e números"). Isto recomenda o uso de máquinas de estado para o reconhecer os itens léxicos. Toda vez que o analisador léxico é chamado para reconhecer o próximo item léxico, ele parte de um estado inicial e vai mudando de estado a cada caractere examinado, até reconhecer o item ou detectar uma seqüência inválida de caracteres (um "erro léxico").

Por exemplo, vamos considerar um caso simples, em que os itens léxicos são números inteiros decimais e as operações + e -. De uma forma livre, teríamos o seguinte analisador léxico na linguagem C:

estado = INICIAL;
while (estado != FINAL)
{
c = ProximoCaracter();
switch (estado)
{
case INICIAL:
  if (c == EOF)
  {
     item = EOF;
     estado = FINAL;
  }
  else if (isdigit(c))
     estado = NUMERO;
  else if (c == '+')
  {
     item = MAIS;
     estado = FINAL;
  }
  else if (c == '-')
  {
     item = MENOS;
     estado = FINAL;
  }
  else if (!isspace(c))
  {
     item = ERRO;
     estado = FINAL;
  }
  break;
case NUMERO:
  if (c == EOF)
  {
     item = NUMERO;
     estado = FINAL;
  }
  if (!isdigit(c))
  {
     DevolveCaracter(c);
     item = NUMERO;
     estado = FINAL;
  }
}
}

Para não estender mais o código, não estamos guardando o valor do número (o que fica como exercício para o leitor). Reparar que eventualmente o código acima examina um caractere além do final do item e precisa "devolvê-lo". Tipicamente um analisador léxico não precisa guardar estados entre uma chamada e outra nem voltar atrás nos seus passos.

Algumas linguagens possuem idiossincrasias que dificultam o analisador léxico. Por exemplo, algumas versões do FORTRAN permitem colocar espaços no meio de identificadores, criando seqüências de difícil análise como:

DO 10 I = 1, 10

Somente ao encontrar a vírgula o analisador léxico descobre que os itens léxicos são <DO> <10> <I> <=> (comando DO) ao invés de <DO10I> <=> (o que seria um comando de atribuição).

O analisador léxico é também responsável por desprezar os comentários nos fontes.

No caso de identificadores e palavras reservadas, a máquina de estado apenas isola a seqüência de caracteres. O analisador léxico precisa também identificar o item.

No caso das palavras reservadas, normalmente existe uma tabela ou lista onde a seqüência isolada deve ser procurada. Uma forma simples, mas ineficiente, é fazer uma busca seqüencial. Uma forma mais inteligente é ordenar previamente a lista e fazer uma busca binária.

Uma forma ainda melhor é usar hashing. No hashing, calcula-se um número (hash) a partir da seqüência de caracteres e usa-se este número como índice para a tabela.

O principal problema com o hashing é que várias seqüências podem gerar o mesmo hash (gerando uma colisão). Ao inserir um item numa tabela de hash, se a posição já estiver ocupada é preciso fazer uma lista ligada na posição para colocar o novo item. Ao fazer uma busca, é preciso fazer uma busca seqüencial nesta lista ligada.

Uma opção para diminuir as colisões é aumentar a faixa de valores para o hash, porém isto leva ao desperdício de memória. No caso das palavras reservadas, a lista é constante, o que permite escolher previamente uma função de hash que evite colisões. Por exemplo, pode-se criar uma função parametrizada e deixar um computador procurando exaustivamente os parâmetros que otimizem a função de hash.

Uma vez determinado que uma seqüência não é uma palavra reservada, o analisador léxico deve tentar descobrir o tipo de identificador. Isto é feito procurando a seqüência em tabelas de nomes de variáveis, funções, etc construída pelo analisador semântico. Estas tabelas podem usar o hashing para otimizar a busca. Um truque simples mas eficaz consiste ao encontrar um item na lista ligada da tabela de hash mover este item para o início da lista. Isto faz com que a lista automaticamente se ordene em função do uso dos itens.

Em algumas linguagens é permitido usar um identificador que ainda não foi declarado e portanto tem tipo ignorado. Isto não afeta o analisador léxico porém complica o analisador sintático e pode obrigar o analisador semântico a segurar a geração do código objeto até que o identificador seja declarado.

Na próxima parte vamos ver o coração do compilador, o analisador sintático.