Schizoid Classes

Artigo na ACM Queue.

Através dos métodos (e variáveis) de instância e de classe, as classes em Java e C++ misturam o conceito de tipo com o de módulo, criando uma crise de múltipla personalidade. Em contraste, na linguagem Smalltalk os métodos e variáveis de instância e de classe são conceitualmente unificados através do uso de metaclasses e metaobjetos. Em outras linguagens, classes e módulos coexistem, reconhecendo o fato que nenhum dos dois pode substituir o outro.

Artigo curto e de boa leitura; é uma demonstração do que acontece quando você tenta construir linguagens sem uma visão geral de projeto; Smalltalk tem essa visão, C++ e Java não. C++ é um frankenstein ao qual foram adicionadas características (por vezes conflitantes) ao longo dos anos, e Java é uma "linguagem política" que foi feita para tentar satisfazer a gregos e troianos. Não se pode dizer que nenhuma das duas tenha "integridade conceitual".

An Axiomatic Basis for Computer Programming

Um artigo clássico de C. A. R. Hoare, datado de 1969. Esse artigo lançou as bases para provas axiomáticas de corretude de programas e para a semântica axiomática.

O método axiomático foi usado com sucesso na matemática desde que Euclides publicou uma axiomatização da geometria nos seus Elementos. Com o tempo, o método foi aperfeiçoado e hoje é a base de praticamente todas as teorias matemáticas; Aristóteles já chamava a atenção para o fato que uma cadeia de demonstrações deve começar em algum lugar, algumas verdades que são assumidas. Estes são os axiomas.

A tese de Hoare é que é possível estabelecer axiomas básicos para a programação de computadores, e a partir deles, usando regras de inferência também estabelecidas, provar propriedades dos programas, especialmente a sua corretude. Um programa é correto se ele realiza as especificações que foram determinadas para ele, ou seja, se ele faz o que deve fazer. Além disso, os axiomas podem ser utilizado na definição formal de linguagens de programação.

Para exemplificar a plausibilidade do método axiomático na programação, o artigo apresenta alguns axiomas relacionados aos números inteiros e a construções básicas de programação: atribuição, sequenciamento, iteração. Com isso, prova-se que um programa que calcula o máximo divisor comum de dois números é correto, satisfazendo as propriedades matemáticas necessárias para o cálculo.

A seção 5 discute provas de corretude para programas; a idéia, já antiga, de que erros de programação custam caro e que testes nunca podem provar completamente que um programa está correto. Um trecho é interessante:

The practice of supplying proofs for nontrivial programs will not become widespread until considerably more powerful proof techniques become available, and even then will not be easy.

Coisa que até hoje não aconteceu; ainda é trabalhoso demais provar a corretude de programas além dos mais triviais. Entretanto, em alguns casos mais críticos isso já foi feito, principalmente com a ajuda de theorem provers especializados. Muitos microprocessadores também passam por processos de prova formal atualmente; é possível que os métodos formais realizem, um dia, os benefícios visualizados por pioneiros como Hoare e Dijkstra. No artigo, Hoare também menciona como as provas de corretude podem ajudar na documentação e portabilidade de programas.

A seção 6 termina o artigo falando do uso do método axiomático na definição formal de linguagens de programação. Dado que sejam estabelecidos os axiomas e regras de inferência da linguagem, eles servem de definição da própria linguagem: uma implementação só é válida se tornar válidos os axiomas e regras de inferência definidos. Ao mesmo tempo, os axiomas servem automaticamente como base para a prova de corretude da implementação. Hoare fala de Algol 60 e de como a definição formal da sua sintaxe ajudou na formulação de regras sintáticas coerentes, advogando a mesma vantagem para uma definição formal da semântica (tema antigo: simplicidade da definição formal da sintaxe versus complexidade na definição formal da semântica). A semântica axiomática, cuja pesquisa se aprofundou nos anos seguintes, anda meio em desuso, mas os princípios são sólidos.

Faz você pensar no que a computação poderia ser se mais atenção fosse dada às bases teóricas.

Idéias

Relendo o paper sobre Haskell#, e pensando na especificação estática do paralelismo, me perguntei: por que não codificar a informação de configuração no sistema de tipos ? Atualmente, é utilizada uma linguagem separada para isso, a HCL (Haskell Configuration Language), o que traz os problemas de casamento de impedância e coisa e tal. Uma solução integrada ao sistema de tipos poderia manter a especificação dinâmica, a separação das preocupações de coordenação e computação e ainda eliminar os problemas de impedância. Além de codificar os componentes e a configuração, é necessário codificar os skeletons também. Templates ? Meta-programação ? É preciso verificar que outras técnicas já foram tentadas (Eden, GpH, etc)...

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.

Curtas

• Computação interativa leva ao estudo da teoria dos jogos. von Neumann, John Nash, etc
• O mlton está avançando bastante; pode ser uma boa alternativa de um sistema ML prático, concorrendo com OCaml
• O PLT Scheme está com um sistema de módulos interessante, o PLaneT. PLT ficando cada vez melhor
• Não é muita novidade, mas saíram os resultados do ICFP Contest desse ano. Haskell na frente, OCaml no prêmio especial do juri.
  

Computação Interativa

Vários trabalhos de pesquisa, ultimamente, têm se concentrado no conceito de computação interativa: focalizar, na teoria da computabilidade, não mais o algoritmo como peça central, mas a interação. Isso torna os modelos clássicos (máquinas de Turing, lambda-calculus, etc) inadequados para descrever os sistemas computacionais atuais. A idéia é desenvolver novos fundamentos que levem em conta interação, distribuição, mobilidade e concorrência.

Um dos tipos de formalismo desenvolvido são as álgebras de processo, como o pi-calculus; assuntos que pretendo estudar em breve (os livros já estão aqui). A busca dos fundamentos para computação interativa me interessa muito, e é algo que eu posso relacionar com a minha pesquisa de mestrado.

A conferência Foundations of Interactive Computation é sobre isso. O call for papers apresenta alguma contextualização para os motivos dessa busca.

References for Beginners in Programming Language Theory

Thread no LtU. Vou observar se aparecem indicações interessantes (além das que já estão lá).

Hiato...

É, as coisas andam paradas por aqui mesmo. Prazo apertado no trabalho, um rapido desvio pelo mundo da criptografia e muito código Java (eca). Se tudo der certo, em duas semanas estarei livre disso e aí vai ser só Haskell e clusters.

Lambda the Ultimate

Lembrando que no LtU Imperative os modelos semânticos se baseiam apenas em:

1. expressões lambda
2. expressões condicionais
3. atribuição

Se tivermos avaliação em ordem normal, até mesmo as expressões condicionais podem ser modeladas usando expressões lambda. Assim, teríamos apenas a necessidade de 1 e 3. O problema é que, como notado no paper original sobre Scheme, a ordem normal de avaliação complica a implementação correta da recursividade final. Mas, se usarmos o estilo de passagem de continuações sempre, obtemos independência da ordem de avaliação específica, como observado por Reynolds e Steele & Sussman; assim podemos ter uma linguagem em ordem normal e com recursividade final, eliminando a necessidade de ter expressões condicionais como primitivas.

Agora acabei de reler essa parte no AIM-349 (o "Scheme: an Interpreter for Extended Lambda Calculus") e vi que esta observação também está lá. Enfim, é difícil ser original, ainda mais considerando que esses artigos têm em média 30 anos de idade.

Seria possível eliminar a atribuição, ficando apenas com expressões lambda para tudo ? Aparentemente não, até porque o lambda-calculus puro é livre de efeitos colaterais, e nós queremos modelar estruturas que apresentam efeitos colaterais. Será que não dá para colocar uma mônada aí no meio ? E mais, fazer isso sem passar para uma extensão do lambda-calculus puro ?

(Nota: se não me engano alguém já provou que ter continuações e atribuição em uma linguagem é equivalente a ter mônadas numa linguagem sem efeitos colaterais, mas qualquer conjunto menor é menos expressivo; depois vou procurar esse artigo)

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.

Mais Reflexões Recursivas

O fato de ser mais difícil implementar a recursividade final corretamente em linguagens imperativas, por causa do sequenciamento de instruções principalmente, deve explicar a falta deste aspecto em linguagens como C e Java. Também para explicar por que isso foi "descoberto" no âmbito da programação funcional. Mas hoje já se sabe como fazer isso em linguagens imperativas, então não deveria haver desculpas. Ou deveria ?

Enfim

Sobre a tail recursion no interpretador Scheme, a resposta é simples e engenhosa; está nas entrelinhas do interpretador. É só não salvar o estado na hora de avaliar (executar) uma combinação.

Mas não tem que voltar ? Nem sempre, só se a combinação for uma subcombinação de outra combinação. E aí o interpretador salva: antes de avaliar cada argumento de uma combinação, ele salva o estado, para restaurar quando a avaliação do argumento tiver sido terminada.

Ou seja, o controle de uma função para outra é simplesmente transferido (goto mesmo). Lembrando do artigo de Reynolds, isso é o interessante do estilo de passagem de continuações: uma função no CPS nunca retorna, apenas transferindo o controle para a próxima continuação.

Dá para ver que isso é possível em uma linguagem orientada a expressões como Scheme, sem sequenciamento de instruções e outras características imperativas. É preciso refletir como seria possível fazer isso em C, por exemplo (sim, eu sei que já foi feito).

Agora posso terminar o LtU Imperative.

Tail Recursion ?

Já estava quase terminando o Lambda: the Ultimate Imperative quando me veio uma dúvida à cabeça, sobre a implementação Scheme que é mostrada no artigo anterior: como são implementadas as tail calls (chamadas finais) ?

Eu não analisei a implementação apresentada a fundo, até porque é MacLisp, um dialeto de mais de 30 anos de idade. Mas agora fiquei curioso com isso.

Em uma olhada superficial, a função EVLIS é a responsável pela avaliação de combinações, então aparentemente é aí que o controle deve ser transferido. Mas como diferenciar quando salvar e quando não salvar um quadro de ativação (CLINK, na notação do artigo) ?

A transferência entre as funções que implementam o interpretador é por meio de tail calls forçadas, utilizando a variável do contador de programa (**PC**); mas ainda não percebi como isso se reflete nas funções da linguagem interpretada... bom, verificarei isso.

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.

Enquanto isso, na programação funcional...

Na programação funcional não existem valores parciais, então não dá para fazer o mesmo truque. Também seria estranho ver procedimentos em uma linguagem funcional. Mas ainda dá para conseguir recursividade final (já vi em algum lugar a tradução recursão de cauda ou algo similarmente horrendo) através de outra transformação. A idéia é utilizar uma convenção idiomática comum, através de acumuladores. Vejamos como isso fica em Scheme. A função mapl (map já existe em Scheme) é uma versão direta da função em Oz:

(define (mapl f l)

(if (null? l)

   ()

   (cons (f (car l)) (mapl f (cdr l)))))

Ela claramente não apresenta recursividade final. Agora vamos passar utilizar um acumulador como parâmetro adicional:

(define (mapla f l a)

(if (null? l)

    a

    (mapla f (cdr l)

           (cons (f (car l)) a))))

E voilà: tail recursion. Mas aqui temos um problema: a lista resultante está invertida com relação ao resultado esperado, pois a operação de construção de lista não é comutativa. Resolve-se isso adicionando uma chamada a reverse:

(define (mapla f l a)

(if (null? l)

    (reverse a)

    (mapla f (cdr l)

           (cons (f (car l)) a))))

Pode testar que dá o mesmo resultado (recomendo o DrScheme); como acumulador inicial usa-se a lista vazia, segundo a equação de equivalência (mapl f l) = (mapla f l ()). Pode-se criar uma função wrapper que faça isso automaticamente.

Eine Kleine Nachtmusik

Oz é uma linguagem estranha. Seus conceitos fundamentais são uma mistura de programação imperativa, funcional e lógica, além de programação concorrente e distribuída. Intrinsecamente multi-paradigma.

Terminei os dois primeiros capítulos do CTMCP e ainda fica um certo estranhamento, até porque no começo parece tanto com uma linguagem funcional. Mas tem unificação, valores parciais e outras coisas estranhas que parecem Prolog.

Para exemplificar, vamos começar com algum background: Oz é dividida em uma kernel language que abriga os conceitos fundamentais, e uma full language que inclui sintaxe extra e outras conveniências. A kernel language é simples e é nela que se define a semântica da linguagem; além disso, especifica-se formalmente como traduzir programas na full language para a kernel language, e assim é possível especificar a semântica de qualquer programa na linguagem completa.

Pois bem, a kernel language define procedimentos, e não funções, como conceitos primitivos. Funções são uma abstração sintática da linguagem completa, que são traduzidas para procedimentos na kernel language. Como exemplo, a função

fun {Times2 N}

  N * 2

end

é traduzida para o procedimento

proc {Times2 N ?R}

  R = N * 2

end

O ?R é um parâmetro de saída que é atribuído com o resultado de retorno do procedimento (se houver um). O que era funcional vira imperativo na kernel language. O que é realmente interessante é a forma como isso interage com valores parciais e estruturas de dados. Vamos definir uma função Map que aplica uma função F a cada elemento de uma lista L. O operador | é o construtor de lista (cons em Scheme/Lisp, :: em ML, : em Haskell); {F H} é uma chamada da função F com argumento H; case faz pattern matching. Logo após a função tem a tradução dela para a kernel language.

fun {Map F L}

  case L of H | T then {F H} | {Map F T}

  else nil end

end



proc {Map F L ?R}

  case L of H | T then

    local Rr in

      R = {F H} | Rr

      {Map F T Rr}

    end

  else nil end

end

Note-se aí a atribuição do resultado (R) a um valor parcial, pois Rr (o "resto" do resultado) ainda não possui valor. O efeito disso é transformar uma função que não é tail recursive em um procedimento que é. O programador ganha automaticamente os benefícios da recursão final (tradução tentativa para tail recursion), sem se preocupar com isso.

Estranho, mas interessante.

Outras relações

Ainda sobre o artigo de Reynolds, algumas observações adicionais.

O método de usar interpretadores meta-circulares na definição de linguagens de programação começa, como é conhecido, com John McCarthy e o artigo original sobre a linguagem Lisp. A mesma abordagem é utilizada em um dos capítulos do influente livro "Structure and Interpretation of Computer Programs" de Abelson e Sussman; o uso de interpretadores para explicar características de linguagens de programação também é a idéia central no livro Essentials of Programming Languages de Friedman, Wand e Haynes.

Steele e Sussman definem, em Scheme, um conceito similar ao escape de Reynolds no artigo Lambda, the Ultimate Imperative. Ambos são muito parecidos ao operador J de Peter Landin. A mesma idéia aparece no operador call-with-current-continuation, ou call/cc, das versões recentes da linguagem Scheme.

A notação utilizada, sendo influenciada pelos trabalhos de Landin, lembra uma forma primitiva da linguagem ML. O uso de referências como entidades explicitamente separadas dos outros tipos de variáveis também apareceu em ML.

A adaptação do interpretador para incluir atribuições de variáveis, com o estado sendo propagado por todas as funções, lembra o uso de mônadas na linguagem Haskell.


O artigo de follow-up "Definitional Interpreters Revisited" fala sobre essas relações também (ainda não tinha lido quando escrevi isso aqui).

Enfim, é fácil de ver o quanto esse artigo foi bem sucedido em reunir uma série de idéias fundamentais da área; e a abordagem de mostrar as idéias construtivamente, a partir de interpretadores para elas, foi a maior inovação dele.

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".

Paralelismo para todos

Sim, chips dual-core estão vindo de vez. E o futuro é quad-core; oito e até mesmo 16 núcleos num chip só estão sendo tentados. Paralelismo fundamental nas máquinas de todos, em poucos anos.

Veja-se, por exemplo, a cobertura do Intel Developer Forum deste ano.

O problema é que não adianta o quanto nossos chips são potentes, se o software não foi feito para aproveitar essas novas tecnologias. Normalmente estima-se em anos o tempo necessário para que uma parte significativa do software utilizado aproveite as inovações do hardware. É possível que isso ficaria mais fácil se tivéssemos tecnologias de criação de software mais adaptáveis ?

Outra coisa: concorrência e paralelismo vieram para ficar, desta vez. Qual o impacto que isso trará para as tecnologias de programação ? Será que linguagens e tecnologias mais apropriadas ao meio (erlang, por exemplo) serão utilizadas, em detrimento das que lidam muito mal com concorrência (java) ? Difícil de acreditar, mas tenhamos esperança...

OCaml e o eclipse

Fiz essa semana o primeiro release oficial do plugin para usar o Eclipse como uma IDE OCaml. Versão alfa e tal, ainda bem primitiva. Mas deu um alívio liberar isso e tirar uns dias de folga. Muito trabalho braçal, e ainda mais em Java. Agora vem as partes mais interessantes: modelo da linguagem, análise sintática, melhorar a análise de depedências, trabalhar com o interfaceamento entre a JVM e OCaml, etc...