Análise baseada em tipos

Da idéia de fazer gerenciamento de memória e gerenciamento de recursos baseados em tipos, generalizando um pouco, aparece a idéia de análise de programas baseada em tipos. Resumindo, é analisar certas propriedades de programas através dos tipos de dados empregados, possivelmente em conjunto com análise de fluxo de controle e de fluxo de dados. O gerenciamento de memória baseado em regiões é um exemplo de análise baseada em tipos, onde o compilador procura identificar os objetos que têm tempo de vida limitado a algum escopo e os aloca em uma disciplina de pilha.

Agora achei uma página bem interessante para pesquisar sobre o assunto: Type-Based Analysis and Applications.

Vamos ver o que vai sair.

Comparação

Há algum tempo terminei de reescrever o programa de teste dos algoritmos de contagem de referências (como mencionado em outro post); a versão anterior era escrita em C, a atual foi escrita em OCaml.

Claro que eu já vinha percebendo que a nova versão era mais compacta que a anterior, mas só para ter uma idéia eu comparei o número de linhas de código apenas na parte do interpretador (responsável por reduzir os grafos e obter os resultados dos programas). O Resultado:

• Versão anterior (C): 1600 linhas de código
• Versão atual (OCaml): 200 linhas de código

E não é manipulação: essas 200 linhas de OCaml fazem exatamente o mesmo, nada menos, que as 1600 linhas de C. Além do poder de expressão da linguagem, a tarefa também é bem adequada à linguagem: a família ML se dá muito bem para a escrita de compiladores e interpretadores de linguagens de programação. E uma coisa que ajudou muito a reduzir o tamanho foi utilizar funções de ordem superior. Functional programming rules.

Depois eu pretendo levantar o tamanho completo das duas versões e postarei aqui.

Gerando texto

Na última parte da disciplina de Métodos Matemáticos, estudamos processos aleatórios e técnicas relacionadas à teoria das probabilidades. As tarefas foram preparar seminários demonstrando aplicações dos tipos de processos aleatórios estudados.

Para demonstrar cadeias de Markov, eu escolhi uma aplicação na geração de textos aleatórios. É algo que eu vi há algum tempo e achei interessante, mas não sabia como funcionava; quando estudei sobre o assunto juntei as idéias e pensei nisso: fazer um programa que gera textos, a partir de um outro texto que serve de base.

É como aquela história, junte alguns macacos digitando aleatoriamente e, dado tempo suficiente, devem surgir até as obras completas de Shakespeare :) Aliás, os macacos fariam toda a Biblioteca de Babel, mas isto é outra história.

Enfim, para quem se interessar, aqui está a apresentação (PDF, PPT) e o programa utilizado.

Um exemplo de texto gerado com base em Dom Casmurro, de Machado de Assis, está neste post do outro blog.