Turing Clube/Oficina de Linguagens de Programação

Vamos estudar o funcionamento de linguagens de programação praticando a construção de interpretadores desde o início.

Exemplo de código que vamos estudar, modificar e melhorar: função recursiva que avalia s-expressions aritméticas (* 7 6) → 42. (código-fonte)

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 em 2019

1º encontro

2ª-feira, 28/jan/2019, 19:30 a 22:30. Estudamos os exemplos de SimpleCalc até SubPascal do repositório kaminpy, e conversamos sobre computabilidade, história do Lisp etc.

Vídeos:

• parte 1 (16'09"): Um pouco (demais) de história e contexto.
• parte 2 (19'26"): Explorando SimpleCalc no Jupyter Notebook.
• parte 3 (19'22"): Analisando SimpleCalc no VS Code com Python Preview.
• parte 4 (22'38"): Estudando Calculator com parser que produz AST (Abstract Syntax Tree).
• parte 5 (21'56"): Entendendo Calculator a partir dos testes com pytest.
• parte 6 (32'37"): Apresentando SubPascal, nosso primeiro interpretador Turing-completo.

2º encontro

2ª-feira, 11/fev/2019, 19:30 a 22:30. Fizemos exercícios para explorar SubPascal e seu interpretador.

• PLIBA/Exercício 1.4.1.1: Função sigma para somar séries de inteiros, implementada em SubPascal em versões recursiva e iterativa.
• PLIBA/Exercício 1.4.2.9: Implementar comando for no interpretador, com a sintaxe (for var_name start_expr end_expr block_expr).

3º encontro

2ª-feira, 25/fev/2019, 19:30 a 22:30: Estudo detalhado do código dos interpretadores de SubPascal.

;4º encontro :2ª-feira, 11/mar/2019, 19:30 a 22:30.

Encontros passados

1º encontro

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

2º encontro

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

3º encontro

6ª-feira, 07/dez/2018, 19:30 a 22:30. (excepcionalmente com Ian Fernandez)

4º encontro

6ª-feira, 14/dez/2018, 19:30 a 22:30.

5º encontro

6ª-feira, 21/dez/2018, 19:30 a 22:30
Melhores momentos: recapitulando o que foi feito, apresentando o interpretador completo de SubPascal

Estratégia

The idea of this book is to learn about programming languages both by programming in them and by studying interpreters for them.
-- Samuel Kamin, in PLIBA, p. 1

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 dos capítulos do livro Programming Languages: an Interpreter-Based Approach (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.

ambiente (environment)

Em teoria de linguagens de programação, ambiente é uma estrutura de dados que associa identificadores de variáveis a valores. A implementação de uma linguagem com suporte a variáveis precisa ter pelo menos um ambiente global. Linguagens que implementam funções normalmente criam um ambiente local ao executar cada função. Além desses ambientes global e local, linguagens que permitem funções definidas dentro de outras também podem implementar closures. Dicionários e listas associativas são formas comuns de implementar ambientes.

ambiente de execução (runtime environment)

Sistema de suporte que permite a execução de programas em linguagens que não tem compiladores para gerar código de máquina nativo. O ambiente de execução de linguagens interpretadas, como Python e Ruby, inclui o interpretador e a biblioteca-padrão da linguagem. Certas linguagens compiladas como Java, Closure e Kotlin dependem da máquina virtual Java (JVM) para executar seus binários.

aridade (arity)

Número de argumentos que uma função aceita. Por exemplo, em Python a função abs(n) tem aridade 1, mas divmod(a, b) tem aridade 2.

closure

Estrutura formada por uma função e um ambiente com variáveis necessários para a execução da função, mas não definidas no corpo da função -- chamadas variáveis livres ou não-locais. Uma linguagem só precisa implementar o mecanismo de closure se ela permite a definição de uma função dentro de outra, e permite que a função externa devolva a função interna como resultado. C e Pascal não precisam de closures; Scheme e Python precisam.

coletor de lixo (garbage collector)

Sub-sistema de 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.

github/ramalho/hoc

Código e explicações em PT-BR sobre yacc e a mini-linguagem hoc, do livro The Unix Programming Environment de Brian W. Kernighan e Rob Pike.

lis.py

Peter 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: "(John McCarthy) showed how, given a handful of simple operators and a notation for functions, you can build a whole programming language." (blog post)

History of Lisp

John McCarthy; The history of LISP according to McCarthy's memory in 1978, presented at the ACM SIGPLAN History of Programming Languages Conference.