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 Python, C++, e Pascal, mas não é necessário conhecer alguma 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 aparência de LISP. Mas 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.

Mão na massa

Queremos fazer uma atividade prática. A proposta é exercitar e modificar interpretadores já implementados, e implementar interpretadores em outras linguagens. Não acredito que seja possível entender mesmo como funciona um interpretador apenas assistindo exposições. Ao final, depende de cada participante colocar a mão na massa para que esta oficina seja, de fato, prática.

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 das 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 implementar um coletor de lixo. 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 tinha um coletor de lixo. 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.

coletor de lixo (garbage collector)

Sub-sistema de um interpretador ou ambiente de execução de uma linguagem de programação que faz o descarte automático de estruturas de dados que não podem mais ser acessadas pelo programa do usuário. Smalltalk, Java, Python são linguagens com coletores de lixo integrados ao seu ambiente de execução. Em Go, o coletor de lixo é parte do código gerado pelo compilador ao produzir um executável.

s-expression

A sintaxe de expressões da linguagem LISP, formada por parêntesis aninhados, símbolos separados por espaços, e operadores prefixos (e não infixos como na aritmética convencional). A fórmula de Pitágoras pode ser escrita assim em LISP: (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

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

PLAI

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

PLIBA

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

The Roots of Lisp

Paul Graham: "[...] given a handful of simple operators and a notation for functions, you can build a whole programming language." (blog post)