Definitional Interpreters for Higher-Order Programming Languages

Artigo de John C. Reynolds.

O seu propósito é sumarizar o estado-da-arte (da época, 1972) na construção de interpretadores utilizados para definir a semântica de linguagens de programação. Basicamente, ele classifica os interpretadores conhecidos, e demonstra como um interpretador de uma classe pode ser transformado em um de outra classe, clarificando as relações entre as classes. As classes são definidas em dois eixos: se a linguagem definida depende ou não da ordem de avaliação (normal ou aplicativa) da linguagem definidora; e se o interpretador usa funções de alta ordem ou não.

Começando com um interpretador meta-circular que depende da ordem de avaliação da linguagem definidora e com funções de alta ordem, o artigo mostra como retirar as dependências, assim informando como construir uma linguagem com funções de alta ordem com base em outra linguagem que não as possui, e como tornar a linguagem definida independente da ordem de avaliação da linguagem definidora.

Um aspecto interessante é como um tipo de interpretador é transformado em outro através de transformações locais que preservam o significado do programa. Esta idéia é muito presente na literatura produzida pelo grupo do PLT Scheme.

Interessantíssimo para quem quer aprender mais sobre a natureza das linguagens, especialmente as funcionais. Podem-se perceber as influências do artigo em várias partes, por exemplo nas linguagens funcionais atuais (tanto Scheme quanto ML) . Claro que as idéias no artigo em si não eram novas (embora a abordagem seja), já que ele resume idéias de vários outros trabalhos. Por isso mesmo, serve como um excelente guia para a literatura da época sobre o assunto. E é fácil de entender para quem tem alguma exposição a linguagens aplicativas ou ao lambda-calculus.

Vale a pena ver também o follow-up "Definitional Interpreters Revisited".