A teoria por trás de um mecanismo de busca de código

Entendendo sobre tokenização, embeddings e cálculos de similaridades

Me siga no X | Me siga no LinkedIn | Apoie a Newsletter | Solicite uma consultoria

---

Pessoas desenvolvedoras frequentemente buscam por exemplos de código para realizar tarefas de programação. Por ser tão comumente empregada, talvez nem se perceba como bons mecanismos de buscas de código podem impactar a produtividade de pessoas e times.

Considere por um instante ter que deixar de fazer buscas por código e ter que ler (e se ambientar) com a documentação (extra-)oficial de uma APIs. As vezes nem sabemos exatamente qual API devemos procurar, quanto mais o que procurar na API. Expressar nossas dúvidas em linguagem natural simplifica muito o processo. Talvez por isso que plataforma como StackOverflow se tornaram tão populares.

Mas como funciona um mecanismo sofisiticado de busca de código como do Stack Overflow?

Por exemplo, como poderíamos fazer para receber uma query como “como iterar por uma HashMap?” e retornar um trecho de código que esteja relacionado com essa consulta?

Existem várias abordagens, e esse texto vai tentar brevemente destacar algumas abordagens clássicas.

Abordagem clássica para busca de código

Muitas dessas plataformas como StackOverflow implementam mecanismos de busca de código usando técnicas como Recuperação de Informação (do Inglês, Information Retrieval — IR). IR refere-se a utilização de algoritmos e estruturas de dados adequadas, para realizar consultas em grandes conjuntos de dados e encontrar informações específicas.

Como exemplo, em meados dos anos 2000s, Sourcerer foi uma engine de busca popular no meio acadêmico de código desenvolvidas por pesquisadores da UCI. Uma das ideias de destaque do Sourcerer foi criar mecanismos de busca que utilizavam não somente as palavras-chave da query, mas que também levavam em consideração elementos estruturais do código fonte (como laços, condicionais, elementos de orientação a objeto, concorrência, etc); algo que era então novidade para a época.

Passado cerca de 20 anos da introdução do Sourcerer, hoje a comunidade técnico-científica já entendeu diversas limitações dessas abordagens de IR. Um problema fundamental é que buscas de código baseada em IR tem dificuldades em relacionar as intenções de alto nível, escritas em linguagem natural, das queries com as implementações em baixo nível do código fonte. Hoje entendemos com mais clareza as heterogeneidades entre um código fonte e um texto de linguagem natural.

Por exemplo, embora a query e o código fonte resultante sejam semanticamente relacionados, eles nem sempre compartilham os mesmos tokens, sinônimos ou estrutura de linguagem.

Levando em consideração a query do início desse texto (e.g., “como iterar por uma HashMap?”), poderíamos ter a seguinte implementação¹:

public static void printMap(Map mp) {
    Iterator it = mp.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println(pair.getKey() + " = " + pair.getValue());
        it.remove(); // avoids a ConcurrentModificationException
    }
}

No entanto, abordagens de IR teriam dificuldades em retornar essa solução, uma vez que o código fonte resultante não contem as palavras “iterar”, “uma”, ou até mesmo “HashMap”. Esse exemplo ilustra a importância de se implementar mecanismos para mapeamento semântico de alto nível entre as consultas escritas em linguagem natural e o código fonte resultante. Além disso, estratégias baseadas em IR tem dificuldades em entender e processar queries mal formuladas (e.g., utilizando termos irrelevantes).

Novas abordagens para busca de código

Como forma de abrandar essas limitações, os trabalhos mais recentes em busca de código utilizam técnicas de aprendizado de máquina (do Inglês, Machine Learning — ML) e aprendizado profundo (do Inglês, Deep Learning — DL).

Em particular, os avanços recentes no uso de DL para busca de código podem ser parcialmente atribuídos ao uso de embeddings. Embeddings é uma técnica para representação de entidades (como palavras, sentenças imagens, ou mesmo código-fonte) em vetores multi-dimensionais.

Através dos embeddings, é possível criar vetores numéricos de tamanho único de diferentes tipos de entidades. Dessa forma, podemos comparar a similaridade de entidades diferentes usando o cálculo de similaridade de cossenos. Ou seja, dois vetores podem ser considerados semelhantes quando estão próximos um do outro no espaço vetorial. Por exemplo, suponha que o termo execute seja representado pelo vetor [0.12, -0.32, 0.01], enquanto o termo run seja representado por este outro vetor [0.12, -0.31, 0.02]. Com estes vetores, é possível estimar suas distâncias e identificar possíveis relações semânticas.

Com esta representação unificada de vetores, trechos de código semanticamente relacionados a uma query em linguagem natural podem ser recuperados de acordo com a proximidade de seus vetores. Palavras semanticamente relacionadas também podem ser reconhecidas e palavras irrelevantes nas consultas podem ser tratadas.

Meu primeiro embedding de código

Vamos criar nosso primeiro embedding usando como base o exemplo de código abaixo:

for (entry : map.entrySet()) {
    System.out.println(entry);
}

O próximo passo é tornar este trecho de código mais próximo de uma representação textual. Esse processo é conhecido como análise léxica, que é uma etapa comumente empregada no processo de compilação. A análise léxica tem como objetivo dividir o código fonte em unidades menores chamadas de “tokens”. Um analisador léxico percorre o código fonte em busca de identificadores, operadores, números, símbolos especiais. Cada um destes elementos é convertido em um token. Estes analisadores podem ainda remover comentários, remover espaços em branco, normalizar caracteres e converter literais em valores numéricos.

Dado o nosso programa acima, a possível saída tokenizada seria a seguinte:

for entry map entry set system out println entry

Aqui preciso dizer algo sobre como transformar cada token em um vetor de embedding

Depois desse passo, podemos mapear cada palavra da nossa lista de tokens para seu embedding correspondente. Por exemplo, o token for poderia ser representado pelo vetor [0.2, −1.0, 3.8], e o token entry poderia ser representado pelo vetor [0.8,0.9,−2.0]. Dessa forma, temos um vetor de embedding para cada token. No entanto, essa abordagem não é muito apropriada, pois precisamos de um único vetor de embeddings que seja capaz de representar todo nosso trecho de código.

Para unificar os vetores de cada token em um único vetor, podemos seguir duas abordagens: a primeira, mais simples, que não considera a ordem dos tokens (como a técnica de bag-of-words) e a segunda, mais complexa, que considera a ordem dos tokens (utilizando Redes Neurais Recorrentes ou Transformers). Embora considerar a ordem dos tokens seja importante por causa da estrutura e da semântica presentes no código fonte, nesse texto vamos optar por utilizar a abordagem mais simples, implementada na forma de um bag-of-words.

O bag-of-words é um modelo de classificação de documentos frequentemente utilizado em contextos em que a frequência de um termo é utilizado como features no processo de treinamento de algoritmos de aprendizado de máquina. Em resumo, o bag-of-words conta a ocorrência repetida dos itens no documento. Nosso embedding seria o resultado da contagem de frequência para a lista de tokens acima, no caso: [1, 2, 1, 1, 1, 1, 1]. Neste vetor, cada número representa a frequência de cada token, sendo o token entry contabilizado como 2 pois aparece duas vezes na lista.

De maneira similar, podemos gerar o embedding do primeiro trecho de código deste texto. Primeiro, precisamos tokeniza-los.

public static void printmap map mp iterator it while it hasnext map entry pair map entry it next system out println pair getkey pair getvalue it remove

Em seguida, calcula-los o bag-of-words, resultando no seguinte embedding: [1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1]. Agora que nossos trechos de código foram codificados em dois embeddings, é possível compará-los. No entanto, como eles tem tamanhos diferentes, uma outra etapa é necessária para antes normaliza-los; por exemplo, reduzindo o vetor maior para o tamanho do vetor menor.

A abordagem de bag-of-words embora seja simples e intuitiva, é muito limitante. Por exemplo, como a bag-of-words trata os tokens individualmente, é difícil manter as relações de tokens (como por exemplo, na chamada do System.out.println()) no vetor de embeddings. Estudos recentes também observaram que a falta de ordem do embedding resultante tender a ser outro fator limitante, uma vez que ordem dos elementos de um programa adicionam semântica. Trabalhos mais recentes na área de busca de código utilizam técnicas como o Word2Vec.

O Word2vec calcula a representação vetorial de palavras usando uma rede neural de duas camadas que pode ser treinada sem supervisão, de modo que as palavras que compartilham contextos comuns (como o System.out.println()) estejam localizadas próximas umas das outras no espaço vetorial.

Embeddings para código e texto em linguagem natural

No exemplo que usamos acima, utilizamos uma técnica simples para gerar um embedding partido de um trecho de código.

No entanto, novas abordagens de busca de código precisam considerar também o texto em linguagem natural expressado na query. Os embeddings que relacionam dois tipos diferentes de dados são chamados de bi-modal embeddings (podem também ser e chamados de multi-modal embeddings, quando estes tratam de mais de dois tipos de dados diferentes).

O objetivo dos bi-modal embeddings é criar em uma representação única e compacta de diferentes tipos de dados. Com uma representação comum, é possível descrever e relacionar diferentes tipos de dados. Embora a query e os trechos de código tenham o mesmo tipo de representação, estas representações (embeddings) são criadas de maneiras diferentes.

Existem várias abordagens para criar bi-modal embeddings, como o uso de redes neurais convolucionais, redes neurais recorrentes ou modelos baseados em transformers. Geralmente se utiliza uma rede neural que processa cada tipo de dado separadamente para obter representações específicas e, em seguida, combina-se essas representações em um espaço compartilhado usando técnicas como concatenação, soma ou multiplicação.

Por meio dos bi-modela embedding, podemos agora facilmente relacionar dados heterogêneos por meio de seus vetores, uma vez que a consulta e o trecho de código correspondentes estão embedados em vetores próximos.

Aplicar meu embedding para busca de código

Finalmente, quando o usuário faz uma consulta do tipo “como iterar por um HashMap”, a consulta é codificada no seguinte vetor de embedding [0.2,0.4,0.5]. Para buscar trechos de código relevantes, o embedding do código pode ser buscado baseado no embedding da query. Por fim, os top N resultados, baseados na similaridade, são retornados ao usuário.

Conclusão

Realizar buscas de código é uma tarefa complexa que requer domínio de diversas teorias e técnicas de programação e inteligência artificial. Hoje em dia, muitas dessas técnicas estão disponíveis em implementações de bibliotecas especializadas, mas ainda se faz necessário montar este quebra cabeça.

Existe alguns projetos open source que tentam entregar um mecanismo sofisticado de busca de código, empregando vários dos conceitos abordados nesse tópico, como é o caso do sem (acrônimo para semantic code search). Se você chegou até aqui e despertou interesse no assunto, talvez navegar no fonte de um projeto como o sem seja uma próxima parada interessante!

1. Solução extraída deste link: https://stackoverflow.com/questions/1066589/iterate-through-a-hashmap