CAELUM

A alguns anos atrás fiz uma entrevista em uma grande empresa de Java, uma dessas com 3 letras, e a primeira frase que o entrevistador me dirigiu ao ver meu curriculum foi um sonoro:

“Essas competições de programação não dizem nada!”

Essas competições não dizem se o programador é um bom engenheiro de software ou profundo conhecedor de alguma tecnolgoia, é verdade. Nem é essa a intenção.
As questões dessas provas apresentam problemas mais complexos que o comumente exigido no mercado de TI, e não foca tanto na parte de desenvolvimento, mas mais na capacidade de encontrar soluções. Para um cientista da computação (ou um matemático, no meu caso), essa capacidade é mais importante do que o próprio desenvolvimento e codificação. Vou relatar aqui três competições as quais tiver a oportunidade de participar este ano. Em todas as três, grandes empresas como o Google e IBM, sempre estavam a caça de talentos. Pode-se dizer que um bom resultado nessas competições certamente atrairão diversas propostas de emprego, mestrado e doutorado.

Primeiro veio o Google Code Jam Latin America. Os problemas tinham o mesmo nível das competições internacionais, mas com menos fases. Na última etapa, em Belo Horizonte, tive a chance de encontrar alguns conhecidos e fazer novas amizades no meio dos 50 finalistas, dentre elas Jelani Nelson, aluno de PhD e técnico do MIT, participando pela Virgin Islands; Vinicius Fortuna ex-competidor e agora engenheiro de software do Google em Nova Iorque, que veio entrevistar os competidores; Wanderley Guimarães, atual técnico do IME-USP, além de já conhecidos e excelentes competidores do ITA e PUC-RIO. Pelo vídeo promocional, da para você ter uma idéia do quão a sério o Google leva essas competições:

Depois teve a final mundial da ACM (ACM-ICPC) em Tokyo, Japão, onde fui representando o time do IME-USP, depois da qualificação pela Maratona de Programação brasileira. Lá contamos com a presença de diversos nomes interessantes, como o criador do Ruby, Yukihiro Matsumoto, que palestrou sobre sua linguagem de programação. Entre seus comentários oportunos, disse que eficácia não é a grande preocupação de Ruby; 80% do design de uma linguagem está feito se o nome for curto, pequeno e bonito (Ruby). Outra frase dele foi “Web 2.0, o que é isso?”. Modesto.

Também estava presente Stuart Feldman que, além de presidente da ACM e criador do primeiro compilador de Fotran 77, fez parte do grupo que criou o Unix e o make. Yuhichi Nakamura, criador do Xerces (xml4j), e diretor do IBM Tokyo Research Lab estava ajudando na coordenação do evento.

Nessa competição, mais de seis mil equipes participaram do evento nas competições regionais, de mais de 1700 universidades diferentes do mundo inteiro. A competição foi emocionante, com os quatro times brasileiros bem colocados. Além disso, dois times brasileiros resolveram 4 problemas, um marco na história da competição, onde o problema mais simples envolvia um algoritmo do tipo Longest Common Subsequence. Esse é um algoritmo muito usado em inúmeros lugares, como em biologia computacional para verificar padrões de sequencias de DNA. No fim das contas, os problemas dessas competições não são tão irreais assim! Alguns problemas são muito difíceis, sendo que nenhuma equipe do mundo conseguiu resolver. Você pode ver a prova da competição aqui.

O evento aconteceu no Hilton Tokyo Bay, um hotel dentro da Disney de Tokyo e muito bonito. Os quartos tinham vista para o monte Fuji e foi possível conhecer um pouco do país e de sua história.

O Fórum Internacional de Software Livre preparou esse ano uma competição diferente, a Arena de programação, composta por duas fases. Para poder se inscrever, era necessário resolver um problema de lógica no próprio site, no estilo python-challenge, mas bem mais simples. A idéia era encontrar o caminho para a inscrição usando de seus dotes “hackers”. O Dorneles postou a descrição de como se inscrever em detalhes.

Chegando no evento, pronto para a primeira fase, a Arena era um cercado de vidro, quase um aquário, onde os animais eram os programadores.

A primeira fase terminou com alguns conhecidos entre os top. O Hugo Corbucci, colega de viagem ao fisl pelo IME-USP, o Klaus Wustefeld e o Kalecser Kurtz, o Dornelles Tremea e eu nos qualificamos entre os top 12. A segunda fase começou no dia seguinte e era composta por, supostamente, 24 horas de programação non-stop. Os 12 primeiros da fase anterior foram divididos em quatro grupos de três competidores. Na minha equipe? Kalecser, expert em Java e Dornelles, expert em Python e linux em geral. A tarefa? Resolver quatro bugs ou feature requests do Debian. Isso mesmo. Eles deram quatro códigos de bugs que estão ocorrendo em pacotes do Debian ou que feature requests que os usuários postaram e pediram para as equipes resolverem. Excelente proposta!

O primeiro bug envolvia um problema com o teclado. Você que é fã incondicional do Debian pode alternar para o tty1 (Ctrl+alt+F1), ativar o CAPS LOCK e tentar digitar “ABCD”… se o resultado for “ABcD”, você reproduziu o bug - que só funciona com alguns layouts de teclado. Encontramos muitas informações sobre o assunto e não conseguimos resolvê-lo, fomos capazes de encontrar textos indicando que o problema era mais delicado. Tudo isso após passar por muito código fonte em bash, perl etc. O segundo bug estava no pacote cdebconf, que é responsável pelo processo de configuração de pacotes debian durante o processo de instalação dos mesmos. Após correr por diversos arquivos feitos em C, com um “quê” de orientação a objeto, fomos capazes de isolar o bug e corrigi-lo, e o patch deve se tornar disponível em breve.

O terceiro bug envolve o bugtracking do debian, que não apresentava os dados da maneira que era requisitado, enquanto o último problema estava ligado ao particionador, que encontrava problemas durante o redimensionamento em determinados casos. Muito código perl apareceu enquanto solucionávamos o terceiro bug, mas não houve tempo suficiente para sequer olhar com calma o último. No dia seguinte, a segunda parte dessa fase envolveu o desenvolvimento do zero de um programa para facilitar a internacionalização dos pacotes debian. Nosso objetivo era utilizar o Lucene para fazer o partial matching de palavras ou frases já traduzidas anteriormente em outros pacotes, mas devido ao padrão de i18n adotado pelo debian, o Java acabou segurando um pouco o desenvolvimento, mas ainda fomos capazes de mostrar algo funcional com uma implementação do Edit Distance para procurar palavras similares.

O resultado de tudo isso saiu no final do dia, durante o fechamento do evento, nossa equipe ficou em primeiro lugar! O que ganhei com tudo isso? Conheci novas pessoas que trabalham com projetos open source de áreas diferentes de Java, coloquei em prática o meu conhecimento de C que só usava na teoria, e ajudei com um projeto que jamais sonhei ser possível ajudar. Claro, o notebook que deram para cada um de nossa equipe também conta! Fui entrevistado a respeito dessa competição. Espero encontrar vocês nas próximas!

Os desenvolvedores costumam levar um susto com as assinaturas dos métodos das interfaces do framework das coleções pós-java5: muito mais difícil do que o monte de Es, supers, extends, ?s e &s são os métodos que ainda recebem Object como argumento.

Um exemplo é o método contains. Apesar dele estar na interface parametrizada Collection<E> ele recebe Object em vez de E! Parece um paradoxo: a vantagem do generics não seria exatamente ter uma tipagem mais forte nesses casos, em especial em classes containers? Algumas pessoas acham que é por compatibilidade binária, mas não é, porque a erasure de um método que recebe T é Object, e isso manteria a compatibilidade.

Para entender melhor a decisão da Sun em cada uma dessas assinaturas de métodos você sempre precisa levar em conta dois pontos: erasure e o uso do coringa. Antes vamos relembrar esses conceitos. Considere o código que imprime uma lista de objetos Comparable:

  void imprime(List<Comparable> lista) {
    for (Comparable c : lista)
      System.out.println(c);
  }

Podemos passar para esse método uma List<Comparable>. E uma List<String>? Não podemos, porque uma List<String> não é uma List<Comparable>. Se isso fosse possível, poderíamos adicionar objetos Comparable que não apenas Strings dentro de uma List<String>, quebrando o contrato! Para resolver esse problema, mudamos a assinatura do nosso método para:

  void imprime(List<? extends Comparable> lista) {
    for (Comparable c : lista)
      System.out.println(c);
  }

Agora podemos passar uma List<String>, pois isso é uma List<? extends Comparable>, isto é, uma lista de algum tipo que é compatível com Comparable. Porque então não usamos sempre esse idiomismo? Repare então no seguinte método:

  public void adicionaString(List<Comparable> lista) {
    lista.add("caelum");    
  }

Aqui temos o mesmo problema. Não podemos receber como referência uma List<String>! Vamos tentar aplicar o mesmo procedimento:

  public void adicionaString(List<? extends Comparable> lista) {
    lista.add("caelum"); // não podemos invocar métodos que recebem o tipo
      // parametrizado (a menos que seja passado null)
  }

O código acima não compila! Isso ocorre porque List<? extends Comparable> pode receber uma lista de qualquer tipo que seja Comparable. Se isso fosse possível, alguém poderia passar como argumento uma List<Integer>, e no fim do método esta lista de inteiro estaria contendo uma String, quebrando o contrato novamente!

Como resolver esse problema? Não tem como! Se você recebe um objeto parametrizado pelo coringa ?, você nunca poderá invocar um método desse objeto, porque você não sabe qual o tipo que ele realmente aceita! A linguagem não permite isso porque não sabe exatamente o que você vai fazer com esse objeto. Em alguns casos, semanticamente, apesar de um método receber um tipo parametrizado, não tem problema ele receber um objeto que não esteja de acordo com seu tipo parametrizado. Esse é exatamente o caso do método contains: não haveria problema de passar um Integer para o contains de uma List<String>! Mas se contains recebesse E, o seguinte código não compilaria:

  public boolean contemCaelum(List<? extends Comparable> lista) {
    return lista.contains("caelum"); // ok, recebe Object!
  }

Essa situação é a mesma para outros métodos, como o Collection.remove(Object), e o Map.get(Object). Ambos os casos seriam catastróficos se recebessem o tipo parametrizado como argumento.

A API de coleções traz assinaturas muito mais estranhas. Eu demorei bastante até entender por completo a assinatura de alguns métodos da Collections, como por exemplo o Collections.min:

public static <T extends Object & Comparable<? super T>> T 
    min(Collection<? extends T> coll);

em vez de simplesmente uma ingênua assinatura como:

public static <T extends Comparable<T>> T min(Collection<T> coll);

Fica aí o desafio para você também queimar neurônios…

Muito tem se falado sobre o Java 7 SE e que mudanças na linguagem essa versão poderá trazer. Alex Miller criou um excelente post com muito links para JSRs e blogs sobre as propostas para a linguagem. Peter Ahe publicou também um interessante wish list.

Maneiras alternativas de criarmos coleções usando uma sintaxe mais enxuta já foram discutidas por Stephen Colebourne, Peter Ahe e Rafael Ferreira. Gostaria de salientar que o Java 5 já trouxe alguns métodos interessantes na Collections com essa finalidade. Exemplos são quando queremos criar uma coleção vazia ou com apenas um elemento:

List<String> x = Collections.emptyList();
List<Integer> y = Collections.singletonList(5);

Existem métodos análogos para a criação de conjuntos e mapas. A assinatura do método emptyList é <T> List<T> emptyList(). É interessante que a linguagem infere <T>, descobrindo que nesse primeiro caso T deve ser String. Mas isso nem sempre acontece:

  static void  metodo(List<String> lista) {
    // faz alguma coisa
  }
  
  // dentro do main:
  metodo(Collections.emptyList());

A invocação acima não compila, pois tenta fazer T como Object! Algumas pessoas acham que isso é um bug, mas o pessoal da Sun decidiu por não tentar inferir o tipo em determinadas situações. Na verdade, o compilador só tenta inferir o tipo em dois específicos casos: na clausula de return ou em uma atribuição.

A especificação da lingaugem Java tem uma sintaxe especial no caso de você querer indicar qual é o tipo que deve ser utilizado em uma invocação de método genérico:

  metodo(Collections.<String>emptyList());

Pronto! Agora o Java sabe que T deve ser String nessa invocação, e nosso código passa a compilar. Uma sintaxe esdruxula e pouco comum.

Enquanto todo mundo comenta sobre as closures do Java 7, sem dúvida meu principal interesse sobre o Java 7 é a reificação de tipos genéricos, isso é, em tempo de execução, poder determinar os tipos parametrizados de um objeto. Hoje em dia isso não é possível por causa da erasure, que mantém a compatibilidade com o código pré-generics: um objeto não sabe, em tempo de execução, quais são os tipos que foram usados nos seus parâmetros durante sua instanciação. Isso cria algumas clássicas questões nos fóruns, como “porque não posso criar uma array de T?” ou “Porque não posso usar T.class?“. Muitas pessoas consideram até a hipótese de quebrar a compatibilidade binária do Java, e fazem propostas interessantes para resolver esse problema.

Creio que o Java 7 trará muitas novas surpresas, algumas interessantes como as closures, outras infames como o suporte a literais XML dentro da linguagem. Só espero que eles continuem com a premissa do Java, de deixá-la legível e simples, e não façam como no C++, onde todo novo recurso interessante foi adicionado, tornando a linguagem de difícil legibilidade em alguns casos.