Lambda: the Ultimate Imperative

Mais um artigo de Steele e Sussman.

São apresentados modelos semânticos de algumas estruturas de linguagens de programação. A linguagem usada para especificar a semântica é Scheme (claro). O título vem do fato da maioria das estruturas serem consideradas imperativas, e os modelos utilizarem expressões lambda quase que exclusivamente ("o poder do lambda-calculus"). As estruturas são:

• recursão simples
• iteração
• sequenciamento de expressões (comandos compostos)
• saltos com goto
• atribuição
• passagem de continuações
• expressões de escape (saídas não-locais)
• variáveis fluidas (escopo dinâmico)
• convenções de passagem de parâmetros: call by name, call by need e call by reference

O mote do artigo é que essas estruturas são modeladas usando apenas expressões lambda, expressões condicionais (if) e, em alguns poucos casos, atribuição. Na maior parte dos casos os modelos são realizados a partir de transformações sintáticas locais, mantendo a mesma estrutura do programa original.

Os dois primeiros itens são gratuitos em Scheme. O sequenciamento consegue-se pelo aproveitamento da ordem de avaliação aplicativa em expressões lambda. Assim, a sequência S1; S2 vira ((lambda (dummy) S2) S1). Neste exemplo, S1 é executada apenas pelos efeitos colaterais. Os saltos também são consequência da recursividade final, que garante que uma chamada de função seja apenas uma transferência de controle direto (ver últimos posts). A atribuição pode ser modelada também com expressões lambda, usando uma chamada de função para cada novo valor da variável. Expressões compostas são consequência de como o sequenciamento é implementado; nada de novo. Continuações também ficam simples graças à recursividade final; expressões de escape são modeladas com CATCH ou com continuações.

A parte mais longa e elaborada do artigo são os modelos para escopo dinâmico e as convenções de chamada. Para escopo dinâmico utiliza-se um ambiente fluido que é transmitido entre todas as funções que podem fazer atribuições a variáveis dinâmicas. É preciso alguma convenção sintática para diferenciar as variáveis léxicas das fluidas. Se a implementação usa o estilo de passagem de continuações em todas as funções, o ambiente fluido pode ser incorporado na mesma função da continuação.

Para as convenções de chamada, o call-by-name da linguagem ALGOL é simulado usando thunks, que são expressões lambda sem argumentos: uma expressão E1 é transformada para (lambda () E1). Pode-se adicionar memoização permantente, chegando ao esquema call-by-need. Embora semelhante, o call-by-need é diferente do call-by-name, mas mesmo assim pode-se utilizar algumas formas de memoização para tornar o call-by-name mais eficiente. O problema da atribuição de parametros passador por nome e por referência é tratado por último, incluindo algumas considerações gerais de como, por exemplo, tornar o car de uma lista, ou qualquer outra localização de valor, atribuível. Assim, discute-se sobre convenções de atribuição em outras linguagens.

A conclusão nota que Landin e Reynolds já tinham realizado modelos de algumas das mesmas estruturas usando técnicas similares; entretanto, eles utilizaram formalismos mais complexos do que a linguagem Scheme utilizada neste artigo. Além disso, os modelos para expressões de escape, escopo dinâmico e chamada por nome não tinham sido apresentados antes.

Em seguida: Lambda, the Ultimate Declarative.