Type-Based Analysis and Applications

Artigo de Jens Palsberg

Um survey paper que apresenta uma visão geral da área de análises estáticas de programas baseadas em tipos. Após introduzir o assunto e definir análise baseada em tipos (uma análise baseada em tipos assume que o programa é aprovado pelo verificador de tipos, e a análise toma proveito deste fato), o artigo mostra um exemplo simples de análise para determinação do fluxo de controle, primeiro usando um sistema que não se baseia em tipos (0-CFA), depois três técnicas baseadas em tipos. Neste exemplo as análises baseadas em tipos são divididas em sistemas de tipos e efeitos e tipos-como-discriminadores.

A próxima seção discorre sobre as vantagens das análises baseadas em tipos, resumidas nos tópicos simplicidade, eficiência, corretude e competitividade (com outras formas de análise estática). Em seguida são dados exemplos de várias ferramentas e técnicas já desenvolvidas utilizando análise baseada em tipos, e uma breve seção sobre outros tipos de análises já experimentadas. Um comentário interessante é o que diz respeito às diferenças entre as ferramentas implementadas e as técnicas pesquisadas: a maioria das ferramentas usa a técnica tipos-como-discriminadores, que parece mais simples, enquanto a maior parte da pesquisa se concentra no uso de sistemas de tipos e efeitos. A sugestão é que mais sistemas práticos devem ser formalizados, e mais sistemas pesquisados devem ser implementados.

Das aplicações apresentadas duas bem interessantes e que eu já estava de olho são gerenciamento de memória e detecção de condições de corrida em sistemas concorrentes. Por que não pensar em gerenciamento de recursos baseados em tipos ? Análise de efeitos colaterais me parece interessante também, principalmente para o projeto de linguagens de programação. Nesse sentido, é uma boa ver o artigo de Wadler, "The Marriage of Effects and Monads".

Palsberg mantém um site sobre o assunto.

Gerenciamento de recursos em sistemas distribuídos

Preciso elaborar um projeto de pesquisa para dar entrada na PROPESQ que pode ser aproveitado como o projeto da minha dissertação, e aí eu já aproveito e apresento isso como planejamento na disciplina de metodologia.

O ponto de partida é usar os estudos sobre gerência de memória e tentar generalizar para gerência de recursos em grids e clusters. Eu prefiro enfocar nos primeiros. O interessante é que tem muito espaço para explorar e tentar técnicas avançadas: tipos lineares, tipos dependentes, etc etc.

Espero que saia um bom projeto daí.

Comparação, round 2

Para tirar um pouco da poeira aqui, vão os números finais da comparação informal C versus OCaml.

Recaptulando: eu precisei alterar os algoritmos de gerenciamento de memória de um interpretador de uma linguagem funcional simples. A estrutura do programa é a seguinte:

1. um frontend traduz o programa fonte em uma estrutura de grafos; aqui estão o lexer e o parser;
   
2. essa estrutura é compilada para um grafo de combinadores básicos (SKI);
   
3. o grafo de combinadores é otimizado para usar os combinadores de Turner;
4. o grafo é avaliado (reduzido), efetivamente executando o programa fonte;
5. o runtime consiste de algumas funções pré-definidas e um coletor de lixo modular, que deve usar diferentes estratégias (mark-scan, coletor de cópia ou contagem de referências)
   

O interpretador original tinha sido escrito em C. Não muito bem, diga-se de passagem. Quando eu tentei alterar o que eu queria, core dumps e ponteiros nulos pularam de todos os recantos escuros para me atingir. Em pouco tempo descobri o modo atroz que o programa tratava os ponteiros, e decidi que demoraria muito consertar. O melhor seria fazer de novo. Então decidi fazer em OCaml, depois de ver que Haskell não seria legal (vide posts anteriores).

Há umas semanas isso ficou pronto. Funcionando melhor que a versão C, e feito em aproximadamente um mês de trabalho. Os resultados final da contagem de linhas:

• C - 11486 linhas de código
• OCaml - 1964 linhas de código

Ou seja, o programa em C é uma ordem de magnitude maior. Bem, a comparação não é completamente justa por um motivo: o programa C inclui lexer e parser, enquanto que o similar OCaml trata diretamente com uma sintaxe abstrata; faltaria implementar um frontend que traduzisse da sintaxe concreta para a abstrata. Para deixar a história um pouco mais justa: a parte do frontend no programa em C usa umas 2 mil linhas; mesmo que fosse retirada, ainda seria uma economia de quase 5 vezes. Mas recentemente eu implementei um frontend simples em SML; acredito que para a linguagem em questão, e usando OCaml, não seria muito diferente: lexer + parser em 200 linhas de código, apenas.

Características principais em OCaml que ajudaram a fazer tanta diferença: pattern-matching em estruturas de dados, funções de ordem superior e tipos de dados algébricos.