SCHEME: An Interpreter for Extended Lambda Calculus
O artigo original de Steele e Sussman que define a linguagem Scheme. Na verdade, é um memo interno do laboratório de inteligência artificial do MIT; mas uma publicação respeitada mesmo assim.
Muitas informações históricas interessantes, mas alguma parte das informações técnicas ainda é relevante também. O memo é de 1975; tanto Landin quanto Reynolds já tinham publicado artigos importantes sobre o lambda-calculus e sua relação com as linguagens de programação, tanto que ambos são citados no memo. Mesmo assim, Scheme foi a primeira linguagem prática a implementar o lambda-calculus e ser explicitamente baseada nele (a LISP original chega perto, mas tem o problema de funções não serem valores).
A primeira parte é um manual de referência da linguagem Scheme; bastante primitiva se comparada com as versões atuais. O operador call/cc (call-with-current-continuation) se chamava CATCH. A definição original também incluía primitivas de multiprogramação: operações para criar e gerenciar processos, coisas que foram retiradas da linguagem para sempre, posteriormente. A parte é curta e vai direto ao ponto.
A segunda parte tem exemplos de programas em Scheme, começando com a tradicional função fatorial recursiva, depois tratando de funções iterativas implementadas recursivamente (usando recursão final, ou tail recursion se preferir), estilo de passagem de continuações, e dois exemplos maiores: a função SAMEFRINGE e uma função de reconhecimento de padrões, ambas usando continuações e CATCH extensivamente. No final, um exemplo de multi-processamento. Os exemplos são interessantes principalmente como uso de continuações e call/cc.
Na parte 3 discute-se a semântica da linguagem, utilizando o lambda-calculus de maneira um tanto quanto informal para basear a discussão. Fala-se da semântica de substituição típica da teoria de Church. A semântica de substituição é utilizada para justificar como programas com recursividade final são iterativos, pois não necessitam de uma pilha proporcional ao tamanho da entrada. Da mesma forma, analisa-se a execução de funções no estilo de passagem de continuações.
Em seguida, a quarta parte discute sobre a implementação da linguagem, destacando as principais dificuldades e como contorná-las. Steele e Sussman definem como principal dificuldade a eficiência da implementação. Aqui é apresentada a técnica de utilizar ambientes (environments) como forma eficiente de implementar a semântica de substituição do lambda-calculus; uma implementação ingênua, utilizando substituição textual, é bem mais complexa. Apresenta-se também a noção de fechamentos (closures), que são o resultado da avaliação de uma expressão lambda; o fechamento inclui a própria expressão lambda e o ambiente na qual ela foi avaliada, resultando numa das principais características da linguagem Scheme: o escopo léxico (as variantes Lisp da época utilizavam escopo dinâmico). Os autores chamam a atenção para a semelhança com ALGOL e o uso do conceito de fechamento em outros sistemas. Uma consequência importante é que o escopo léxico garante que os axiomas do lambda-calculus são válidos na linguagem. Por fim, discute-se os problemas relacionados ao fluxo de controle do interpretador e dos programas interpretados, o que traz à tona o assunto da ordem de avaliação (normal vs. aplicativa). Chama-se a atenção para o fato que a ordem normal, que é a tradicional no lambda-calculus, evita a implementação eficiente de algoritmos iterativos, e por isso Scheme usa a ordem aplicativa. Mesmo assim, formas especiais usadas como macros usam uma forma de ordem normal, efetivamente misturando as duas formas na mesma linguagem. Fala-se também sobre como o uso do estilo de passagem de continuações pode eliminar a dependência da ordem de avaliação específica; o mesmo já foi tratado por Reynolds em seu "Definitional Interpreters for Higher-Order Programming Languages" de 1972. Mais alguns detalhes são considerados, como extensões para constantes e operações primitivas.
A seção 5 conclui o artigo apresentando uma implementação "didática" (não totalmente otimizada) da linguagem, usando MacLisp como linguagem de implementação. O fato de MacLisp ser um tanto diferente do Common Lisp atual atrapalha um pouco o entendimento, mas nada que não possa ser superado. A principal idéia da implementação é pensar em baixo nível; não utilizar a recursividade da linguagem de implementação para expressar a recursividade na linguagem implementada, pois isso atrelaria as estruturas de controle desta às daquela. Uma parte interessante é a implementação da forma LABELS, que apresenta um ambiente recursivo no qual as expressões podem se referir umas às outras; o efeito é conseguido utilizando-se alterações destrutivas na estrutura do ambiente, cujos fechamentos são alterados para apontar para o próprio ambiente criado.
No final, os agradecimentos dão uma idéia das origens da linguagem Scheme. Isso termina o primeiro artigo da série dos "lambda papers" de Steele e Sussman. Os próximos já estão na fila de leitura.
Muitas informações históricas interessantes, mas alguma parte das informações técnicas ainda é relevante também. O memo é de 1975; tanto Landin quanto Reynolds já tinham publicado artigos importantes sobre o lambda-calculus e sua relação com as linguagens de programação, tanto que ambos são citados no memo. Mesmo assim, Scheme foi a primeira linguagem prática a implementar o lambda-calculus e ser explicitamente baseada nele (a LISP original chega perto, mas tem o problema de funções não serem valores).
A primeira parte é um manual de referência da linguagem Scheme; bastante primitiva se comparada com as versões atuais. O operador call/cc (call-with-current-continuation) se chamava CATCH. A definição original também incluía primitivas de multiprogramação: operações para criar e gerenciar processos, coisas que foram retiradas da linguagem para sempre, posteriormente. A parte é curta e vai direto ao ponto.
A segunda parte tem exemplos de programas em Scheme, começando com a tradicional função fatorial recursiva, depois tratando de funções iterativas implementadas recursivamente (usando recursão final, ou tail recursion se preferir), estilo de passagem de continuações, e dois exemplos maiores: a função SAMEFRINGE e uma função de reconhecimento de padrões, ambas usando continuações e CATCH extensivamente. No final, um exemplo de multi-processamento. Os exemplos são interessantes principalmente como uso de continuações e call/cc.
Na parte 3 discute-se a semântica da linguagem, utilizando o lambda-calculus de maneira um tanto quanto informal para basear a discussão. Fala-se da semântica de substituição típica da teoria de Church. A semântica de substituição é utilizada para justificar como programas com recursividade final são iterativos, pois não necessitam de uma pilha proporcional ao tamanho da entrada. Da mesma forma, analisa-se a execução de funções no estilo de passagem de continuações.
Em seguida, a quarta parte discute sobre a implementação da linguagem, destacando as principais dificuldades e como contorná-las. Steele e Sussman definem como principal dificuldade a eficiência da implementação. Aqui é apresentada a técnica de utilizar ambientes (environments) como forma eficiente de implementar a semântica de substituição do lambda-calculus; uma implementação ingênua, utilizando substituição textual, é bem mais complexa. Apresenta-se também a noção de fechamentos (closures), que são o resultado da avaliação de uma expressão lambda; o fechamento inclui a própria expressão lambda e o ambiente na qual ela foi avaliada, resultando numa das principais características da linguagem Scheme: o escopo léxico (as variantes Lisp da época utilizavam escopo dinâmico). Os autores chamam a atenção para a semelhança com ALGOL e o uso do conceito de fechamento em outros sistemas. Uma consequência importante é que o escopo léxico garante que os axiomas do lambda-calculus são válidos na linguagem. Por fim, discute-se os problemas relacionados ao fluxo de controle do interpretador e dos programas interpretados, o que traz à tona o assunto da ordem de avaliação (normal vs. aplicativa). Chama-se a atenção para o fato que a ordem normal, que é a tradicional no lambda-calculus, evita a implementação eficiente de algoritmos iterativos, e por isso Scheme usa a ordem aplicativa. Mesmo assim, formas especiais usadas como macros usam uma forma de ordem normal, efetivamente misturando as duas formas na mesma linguagem. Fala-se também sobre como o uso do estilo de passagem de continuações pode eliminar a dependência da ordem de avaliação específica; o mesmo já foi tratado por Reynolds em seu "Definitional Interpreters for Higher-Order Programming Languages" de 1972. Mais alguns detalhes são considerados, como extensões para constantes e operações primitivas.
A seção 5 conclui o artigo apresentando uma implementação "didática" (não totalmente otimizada) da linguagem, usando MacLisp como linguagem de implementação. O fato de MacLisp ser um tanto diferente do Common Lisp atual atrapalha um pouco o entendimento, mas nada que não possa ser superado. A principal idéia da implementação é pensar em baixo nível; não utilizar a recursividade da linguagem de implementação para expressar a recursividade na linguagem implementada, pois isso atrelaria as estruturas de controle desta às daquela. Uma parte interessante é a implementação da forma LABELS, que apresenta um ambiente recursivo no qual as expressões podem se referir umas às outras; o efeito é conseguido utilizando-se alterações destrutivas na estrutura do ambiente, cujos fechamentos são alterados para apontar para o próprio ambiente criado.
No final, os agradecimentos dão uma idéia das origens da linguagem Scheme. Isso termina o primeiro artigo da série dos "lambda papers" de Steele e Sussman. Os próximos já estão na fila de leitura.
posted by tautologico at
6:39 AM
0 Comments:
Post a Comment
<< Home