03/04/2018

Programando em C com inferência de tipos usando PsycheC

ÍNDICE DE CONTEÚDO

Há aproximadamente quatro décadas surgia a primeira versão da linguagem de programação C. Ao longo do anos, C vem se transformando (tendo hoje como referência o padrão C11), mas suas características fundamentais permanecem intactas: um sistema de #inclusão textual, modelo de programação imperativo, escopos lexicalmente delimitados e, entre outros aspectos, a tipagem de expressões acontece estaticamente.

O sistema de tipos de C, além de estático, o que significa que a verificação de tipos ocorre durante a compilação, também possui certas propriedades.

Ele é nominal, haja vista que a equivalência de tipos em C é determinada por nomes, aqueles especificados em declarações de tipo (e.g., de um struct). Essa abordagem contrasta com aquela conhecida como tipagem estrutural;
Quando declaramos uma variável em C, precisamos associá-la, explicitamente, a um tipo (e.g., int ou double). Ao contrário do que acontece em linguagens com inferência de tipos, em C é necessário anotarmos o tipo de um símbolo junto à sua declaração;
Apesar de não existir uma definição formal ou universalmente aceita para os termos “tipagem fraca” e “tipagem forte”, coloquialmente enquadramos C no primeiro grupo, pois seu sistema de tipos é relativamente permissivo. A conversão implícita de ponteiros void* é uma amostra dessa permissividade. Já a linguagem C++, a qual pode, questionavelmente, ser ou não enquadrada no segundo grupo, proíbe esse comportamento.

Uma discussão completa sobre sistemas de tipos vai longe…em especial se investigarmos questões sobre polimorfismo ad-hoc, paramétrico e de subtipagem. Mas meu objetivo se restringe ao tópico de inferência de tipos. Precisamente, gostaria de apresentar um “compilador” com suporte à inferência de tipos em C. Com essa ferramenta, você pode escrever um programa sem precisar declarar um struct ou typedef.

Reconstrução de programas com PsycheC

Antes de apresentar a ferramenta PsycheC (https://github.com/ltcmelo/psychec), é necessário distinguirmos entre a noção de inferência de tipos generalizada e a inferência de um tipo a partir de uma expressão inicializadora. Atualmente, várias linguagens oferecem a funcionalidade de “dedução automática”, na qual uma variável pode ser declarada sem o especificador de tipo, desde que acompanhada de um valor de inicialização.

void f() { auto v = 42; } // auto é o placeholder em C++
void g() { var v = 42; }  // em C#, o placeholder é var

1 2	void f() { auto v = 42; } // auto é o placeholder em C++ void g() { var v = 42; } // em C#, o placeholder é var

Nos trechos de código acima, acontece, de fato, uma inferência de tipo. Porém, em um contexto restrito. A implementação dessa funcionalidade é relativamente simples, e consiste, essencialmente, da inspeção de tipos das sub-expressões que compõe a expressão completa (sejam esses tipos obtidos por anotações em declarações ou por literais), combinada com a aplicação de regras impostas pela linguagem.

A inferência de tipos sobre a qual me refiro é mais complexa, podendo envolver todo o programa. Nessa formulação, temos um conjunto de expressões nas quais expressões completas não têm, necessariamente, sub-expressões declaradas com anotações de tipo. Temos, então, um sistema de restrições composto por inúmeras expressões. O problema final é encontramos o tipo mais genérico capaz de resolver esse sistema. Esse tipo é chamado de um principal type; exemplos clássicos de linguagens que dispõe de um sistema de tipos como esse, conhecido como Hindley-Milner type system, são ML e Haskell.

Seria possível integrarmos uma inferência avançada ao benevolente sistema de tipos de C? Pois é exatamente isso que PsycheC faz! Note que essa não é uma tarefa fácil. O sistema de tipos de C não é trivial. Temos o polimorfismo de void* e, entre outras, dificuldades com qualificadores de tipo: ponteiros não-const podem ser atribuídos a ponteiros const, mas o inverso não é verdade. Além disso, a linguagem C conta tanto com ambiguidades sintáticas (e.g., x * y; pode ser uma declaração de ponteiro ou uma multiplicação) quanto ambiguidades semânticas. (e.g., z = 0; pode ser a inicialização de um numeral ou de um ponteiro nulo), caso declarações estejam ausentes.

No sentido estrito, PsycheC não é um compilador. Até mesmo, pois é desejado que a sintaxe original de C seja preservada (i.e., não há introdução de uma nova palavra-chave como auto ou var). Na prática, PsycheC é um inferidor de tipos capaz de “descobrir” o principal type de expressões que aparecem em um programa, mas cujas declarações estejam faltando. Portanto, na verdade, PsycheC é um reconstrutor de tipos: caso ele encontre um nome T cujo qual a declaração não possa ser encontrada, ele constrói o tipo em questão ou cria um typedef para um tipo já existente.

int main()
{
    T v = 0;
    v->value = 3.14;
    v->next = v;
    return 0;
}

int main()

{

T v = 0;

v->value = 3.14;

v->next = v;

return 0;

}

Salve o conteúdo do snippet acima em um arquivo test.c e tente compilá-lo com gcc, clang, ou o compilador C de sua preferência. Você receberá um erro similar ao mostrado abaixo. Esse é um erro esperado, já que a declaração de T não está disponível no programa.

$ clang test.c
test.c:3:5: error: use of undeclared identifier 'T'
    T v = 0;
    ^

$ clang test.c

test.c:3:5: error: use of undeclared identifier 'T'

T v = 0;

No entanto, se a linguagem C fosse nativamente dotada de um inferidor de tipos, o compilador seria capaz de descobrir que uma solução para esse programa é fazer com que T seja um ponteiro para um struct, o qual é inicializado com 0; incorporando a T um campo de nome value, o qual tem tipo double; e incorporando também a T um campo de nome next, o qual se refere, recursivamente, ao seu próprio tipo. Essa inteligência é justamente o que a ferramenta PsycheC oferece, produzindo, para esse programa, as seguintes declarações.

typedef struct TYPE_2__ TYPE_1__ ;
struct TYPE_2__ { double value; struct TYPE_2__* next; } ;
typedef TYPE_1__* T ;

typedef struct TYPE_2__ TYPE_1__ ;

struct TYPE_2__ { double value; struct TYPE_2__* next; } ;

typedef TYPE_1__* T ;

Caso queira testar você mesmo, sem clonar o repositório do github, dê uma olhada nesta interface online.

Casos de uso: PsycheC na prática

Neste momento, você deve estar se questionando se vale a pena tanto trabalho. Depende… Caso queira simplesmente se aventurar em programar em C com um estilo próximo ao de Javascript ou Python, talvez seja legal apenas pela diversão. Mas, o PsycheC pode ser algo a mais do que um brinquedo. Os casos de uso típicos são os seguintes:

Você quer rapidamente prototipar um algoritmo focando em seu aspecto funcional, sem ter que se preocupar em como os tipos são representados. Sugestão: tente implementar a versão funcional do mergesort, sem declarar um struct sequer;
Você está trabalhando em um projeto legado, embarcado, ou cross-plataforma, no qual os tipos declarados estão disponíveis apenas na arquitetura target, mas não compilam no plataforma em que você está simulando ou testando o programa. Nessa situação, o PsycheC pode ser utilizado para reconstruir os headers incompatíveis;
Você precisa rodar uma análise, debugar, ou testar um snippet submetido via bug tracker, mas não tem acesso ou tempo para replicar/compilar o programa original completo. Em determinados casos, stubs de tipos são suficientes para reproduzir o problema.

Da academia para a indústria: Cnippet

O PsycheC é um projeto primariamente acadêmico. Inclusive, é o primeiro trabalho nacional (desenvolvido exclusivamente por universidades brasileiras) a ser publicado na prestigiada conferência Principles of Programming Languages (POPL), agora em 2018. Para utilizá-lo, é necessário seguir uma espécie de “protocolo” e, em seguida, invocar o gcc, clang, etc. com as declarações geradas.

Naturalmente, o ideal é que a inferência de tipos ocorra transparentemente durante o processo de compilação. Com o intuito de encapsular essa junção entre o PsycheC e o compilador nativo, foi criado o Cnippet, uma ferramenta que se integra ao gcc ou ao clang, abstraindo todas essas etapas de processamento. Além disso, o Cnippet entende parte da biblioteca padrão e sabe interpretar algumas macros típicas de plataformas usuais. A invocação do Cnippet propaga automaticamente flags passadas ao compilador.