Turing Clube/Oficina de Linguagens de Programação

Vamos estudar o funcionamento de linguagens de programação e praticar a construção de interpretadores e compiladores, desde o início.

Pré-requisitos

O único pré-requisito para participar é saber programar. Os exemplos serão apresentados em Pascal, C++, e Python, mas não é necessário conhecer nenhuma dessas linguagens especificamente.

Encontros

1º encontro

6ª-feira, 23/nov/2018, 19:30 a 22:30.

Estratégia

Nesta oficina vamos seguir a pedagogia introduzida por Samuel Kamin em seu livro PLIBA. Em vez de partir direto para a construção de um compilador, Kamin começa por interpretadores, que são mais fáceis de implementar. Em 8 capítulos, Kamin apresenta 8 interpretadores que implementam características fundamentais de linguagens procedurais, funcionais, orientadas a objeto, e lógicas.

As principais estratégias de Kamin são:

• Foco na simplicidade: os interpretadores foram escritos para serem fáceis de ler e modificar, e sempre usam a sintaxe de s-expressions. O gerenciamento de memória fica para o final do livro.
• Foco na semântica: reduzindo todas as linguagens implementadas à sintaxe de s-expressions, as características essenciais das linguagens ficam mais evidentes. Por exemplo o capítulo 7 apresenta um interpretador de um sub-conjunto de Smalltalk com sintaxe de LISP. O que importa é que este interpretador permite criar programas organizados na forma de classes e métodos, ilustrando encapsulamento, polimorfismo, e herança.

Outro livros que segue abordagens semelhantes é PLAI. Porém os interpretadores em PLAI são escritos em um dialeto de Racket com uso intensivo de macros, o que torna seu funcionamento difícil de entender.

Estrutura do PLIBA

Os capítulos de 1 a 8 implementam interpretadores para linguagens inspiradas nas seguintes linguagens:

1	Pascal	Declarações de funções separadas do corpo principal do programa. Closures são desnecessárias (como em C).
2	Lisp	Declarações de funções no corpo do programa. Não há closures porque o escopo é dinâmico.
3	APL	Manipulação de estruturas de dados agregadas.
4	Scheme	Funções anônimas e escopo léxico obrigam a implementação de closures.
5	SASL	Lazy evaluation: o interpretador adia até o último momento possível a computação das expressões (como em Haskell).
6	CLU	Abstração de dados através de encapsulamento e funções (ou "métodos") agrupadas em clusters (como tipos em Go).
7	Smalltalk	Polimorfismo através da sobrecarga de métodos; herança.
8	Prolog	Programação através de cláusulas de Horn, uma forma de lógica de predicados de primeira ordem.

Além da apresentação de cada linguagem através de exemplos, bem como seu interpretador, os capítulos acima trazem exercícios para praticar a própria linguagem tema do capítulo, e para modificar o interpretador implementando novos recursos.

O capítulo 9, Compilation apresenta a teoria de geração de código de máquina a partir da linguagens do capítulo 1 e 4 (Scheme), tendo como alvo uma linguagem de máquina hipotética.

O capítulo 10, Memory Management, aborda algumas estratégias para a coleta de lixo -- descarte de estruturas de dados que não serão mais usadas. Os interpretadores básicos não têm esse recurso, o que significa que ao longo da execução do programa o uso de memória só cresce, nunca diminui. Isso não afeta a semântica de cada linguagem, pois o reuso de memória pode ser considerado uma otimização. O interpretador original de LISP escrito por John McCarthy também não gerenciava a memória. O capítulo 10 apresenta as mudanças no interpretador LISP do capítulo 2 para fazer coleta de lixo.

Código dos intrepretadores

Os interpretadores do PLIBA são implementados em Pascal. Na parte prática dessa oficina, vamos trabalhar com interpretadores em Python ou Go. As pessoas participantes serão encorajadas a reescrever os interpretadores em suas linguagens favoritas.

Interpretadores para o PLIBA escritos em Pascal, C e C++ podem ser encontrados na organização pliba no Github.

Referências

PLIBA

S. Kamin, Programming Languages: An Interpreter-Based Approach, (Reading, Mass.: Addison-Wesley, 1990).

PLAI

S. Krishnamurthi, Programming Languages: Application and Interpretation, (self-published online)