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 do PLIBA 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 é a semântica: este interpretador permite criar programas organizados na forma de classes e métodos, demonstrando encapsulamento, polimorfismo, e herança.

Outro livro que segue abordagens semelhante é 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 sem um estudo prévio de Racket. O funcionamento dos interpretadores de PLIBA está ao alcance de qualquer pessoa que entenda uma linguagem de programação procedural.

Estrutura do PLIBA

Estrutura de pré-requisitos 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 (como em JavaScript).
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 (como em Java, Python, Ruby, C#, PHP, etc.).
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. 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.

Glossário

Durante a oficina, vamos juntar aqui os termos específicos que passaremos a usar.

s-expression

A sintaxe de expressões da linguagem LISP, formada por parêntesis aninhados e símbolos separados apenas por espaços. A fórmula de Pitágoras pode ser escrita assim em uma linguagem hipotética que use a sintaxe de s-expressions: (sqrt (+ (* a a) (* b b))).

Referências

github/pliba

Organização no Github com repositórios de código relevantes para essa oficina.

lis.py

P. Norvig, (How to Write a (Lisp) Interpreter (in Python)), (blog post)

PLAI

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

PLIBA

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