Lambda: the Ultimate Declarative
Outro artigo da "série Lambda" de Guy Steele e Gerald Sussman.
Este abre caminho para o projeto do compilador RABBIT que foi o objeto de estudo do mestrado de Steele. O foco é na definição de primitivas para estruturas de controle e operadores de ambiente, usando expressões-lambda como base sempre que possível; e em como compilar estas primitivas eficientemente para código de máquina (o PDP-10 é usado como plataforma-alvo).
Logo no começo há uma explicação bastante didática sobre recursividade final, porque ela é eficiente e como o interpretador Scheme apresentado no artigo "SCHEME: An Interpreter for Extended Lambda Calculus" implementa essa otimização (exatamente o que eu comentei em um post anterior).
Então são apresentadas duas primitivas fundamentais: a aplicação de funções como uma primitiva de controle fundamental (juntamente com expressões condicionais) e as expressões-lambda como operadores de renomeamento de quantidades de um ambiente. Seguem as propriedades dessas primitivas (controle e ambiente) que permitem uma compilação eficiente do código; há um exemplo de compilação mostrando como uma função recursiva é compilada para código de máquina iterativa.
A próxima seção trata de fechamentos e estilo de passagem de continuações. A continuação é apresentada como um parâmetro explícito que guarda o endereço de retorno, em contraste ao endereço de retorno implícito nas chamadas de função habituais. Também se mostra como o uso do CPS facilita o suporte a funções que retornam múltiplos valores. O uso de CPS em todo lugar acaba com o problema de ter primitivas que tiram o endereço de retorno da pilha, mas criam a necessidade de converter código para o CPS, e usar todas as primitivas em CPS.
A seção 3 é a que é mais fiel ao título do artigo: falando de estruturas de dados definidas proceduralmente, expõe técnicas para usar fechamentos e expressões lambda na representação de tipos de dados. Nisso, toca-se no assunto dos ADTs (Abstract Data Types), mencionando inclusive CLU, e em formas eficientes de compilar fechamentos que representam dados. Apenas sugestões mostrando o que é possível, mas nada concreto (lembrando que o artigo é uma proposta de tese).
Enfim, fala-se da estrutura proposta para o compilador Scheme que é o objeto da tese de mestrado de Guy Steele. Resumem-se as técnicas necessárias, requisitos e resultados esperados com o compilador. Interessante que a visão dos autores era a de usar Scheme como uma linguagem intermediária universal, pela facilidade de expressar as operações gerais das linguagens de programação com construções simples, a maioria baseada nas expressões lambda. Apesar de não ser o uso corrente da linguagem, isso se reflete em algumas linhas de trabalho, como a do livro Essentials of Programming Languages e do pessoal do PLT da universidade de Indiana.
A conclusão reapresenta as idéias principais do memo, com a parte mais interessante para mim sendo as analogias entre definição e aplicação de funções (eval/apply). Os dois apêndices tratam da conversão de código arbitrário para CPS.
No geral é um tanto heterogêneo para um artigo, já que é mais uma proposta de tese. Também inclui muitas referências específicas a trabalhos do AI Lab e ao PDP-10, mas ainda assim o memo vale a pena por condensar várias idéias sobre Scheme, focalizando na construção de um compilador.
Este abre caminho para o projeto do compilador RABBIT que foi o objeto de estudo do mestrado de Steele. O foco é na definição de primitivas para estruturas de controle e operadores de ambiente, usando expressões-lambda como base sempre que possível; e em como compilar estas primitivas eficientemente para código de máquina (o PDP-10 é usado como plataforma-alvo).
Logo no começo há uma explicação bastante didática sobre recursividade final, porque ela é eficiente e como o interpretador Scheme apresentado no artigo "SCHEME: An Interpreter for Extended Lambda Calculus" implementa essa otimização (exatamente o que eu comentei em um post anterior).
Então são apresentadas duas primitivas fundamentais: a aplicação de funções como uma primitiva de controle fundamental (juntamente com expressões condicionais) e as expressões-lambda como operadores de renomeamento de quantidades de um ambiente. Seguem as propriedades dessas primitivas (controle e ambiente) que permitem uma compilação eficiente do código; há um exemplo de compilação mostrando como uma função recursiva é compilada para código de máquina iterativa.
A próxima seção trata de fechamentos e estilo de passagem de continuações. A continuação é apresentada como um parâmetro explícito que guarda o endereço de retorno, em contraste ao endereço de retorno implícito nas chamadas de função habituais. Também se mostra como o uso do CPS facilita o suporte a funções que retornam múltiplos valores. O uso de CPS em todo lugar acaba com o problema de ter primitivas que tiram o endereço de retorno da pilha, mas criam a necessidade de converter código para o CPS, e usar todas as primitivas em CPS.
A seção 3 é a que é mais fiel ao título do artigo: falando de estruturas de dados definidas proceduralmente, expõe técnicas para usar fechamentos e expressões lambda na representação de tipos de dados. Nisso, toca-se no assunto dos ADTs (Abstract Data Types), mencionando inclusive CLU, e em formas eficientes de compilar fechamentos que representam dados. Apenas sugestões mostrando o que é possível, mas nada concreto (lembrando que o artigo é uma proposta de tese).
Enfim, fala-se da estrutura proposta para o compilador Scheme que é o objeto da tese de mestrado de Guy Steele. Resumem-se as técnicas necessárias, requisitos e resultados esperados com o compilador. Interessante que a visão dos autores era a de usar Scheme como uma linguagem intermediária universal, pela facilidade de expressar as operações gerais das linguagens de programação com construções simples, a maioria baseada nas expressões lambda. Apesar de não ser o uso corrente da linguagem, isso se reflete em algumas linhas de trabalho, como a do livro Essentials of Programming Languages e do pessoal do PLT da universidade de Indiana.
A conclusão reapresenta as idéias principais do memo, com a parte mais interessante para mim sendo as analogias entre definição e aplicação de funções (eval/apply). Os dois apêndices tratam da conversão de código arbitrário para CPS.
No geral é um tanto heterogêneo para um artigo, já que é mais uma proposta de tese. Também inclui muitas referências específicas a trabalhos do AI Lab e ao PDP-10, mas ainda assim o memo vale a pena por condensar várias idéias sobre Scheme, focalizando na construção de um compilador.
posted by tautologico at
12:16 PM
0 Comments:
Post a Comment
<< Home