Está é a página da disciplina "Semântica de Linguagens de Programação" (turma 2853 de "Tópicos em Programação"), do professor Fabio Mascarenhas, para o semestre de 2011.2. As aulas da disciplina são às sextas, das 09:00 (pontualmente!) às 12:00, no LAB II do DCC.
Esse curso pretende mostrar os conceitos de linguagens de programação através da implementação de interpretadores para pequenas linguagens que ilustram cada conceito, e como mudanças simples na implementação dos interpretadores têm implicações profundas no comportamento dos programas. Mesmo a semântica de linguagens tão simples como expressões aritméticas tem vários graus de liberdade. Ao final do curso o aluno terá aprendido como várias escolhas do projeto de uma linguagem influenciam o comportamento dos programas nessa linguagem, e terá sido exposto ao mecanismo por trás dos principais paradigmas de linguagens de programação.
Por ser focado em implementação de interpretadores esse curso envolverá bastante programação, e espera-se que o aluno tenha alguma desenvoltura em programação. A linguagem usada em quase todo curso será Racket, um dialeto de Scheme (mais especificamente a IDE DrRacket), mas não é necessário conhecimento prévio nesse linguagem. A escolha de Scheme é pela sua facilidade na escrita de interpretadores, mas os conceitos aprendidos na aula poderão ser aplicados em qualquer linguagem.
Esse é um curso eletivo, então eu assumo que todo aluno matriculado tem interesse na disciplina, e portanto a presença é obrigatória. A maior parte das aulas possui um encadeamento lógico com as aulas antes e depois dela, e faltas são muito prejudiciais ao entendimento do assunto.
Além da presença, também passarei exercícios individuais de uma semana para outra, e esses exercícios podem ser revisados em sala. Eles serão avaliados por esforço e corretude.
O livro texto da disciplina é o "Programming Languages: Application and Interpretation" (PLAI), de Shriram Krishnamurthi. O autor o disponibilizou online em formato PDF nessa página.
Introdução, Aritmética,
with, funções de primeira ordem (PLAI caps. 1 a
4). Veja os slides.
Interpretadores (pequenas variantes em comentários no próprio código):
with (WAE)Como dever de casa, estude a referência
rápida de Racket e então adicione ao interpretador F1WAE a
expressão if0, com sintaxe {if0 <F1WAE>
<F1WAE> <F1WAE>}. Você deve: estender o tipo F1WAE
com o novo tipo de nó; estender a função parse para
transformar a sintaxe acima em um nó do novo tipo; estender a função
subst para efetuar a substituição nas subexpressões dessa
expressão; estender interp para interpretar a
expressão. Para interpretar if0 o interpretador deve
avaliar a primeira subexpressão, e se o resultado dela for 0 avaliar a
segunda expressão; se for diferente de 0 ele deve avaliar a terceira expressão.
Casos de teste para if0:
(test (interp (parse '{if0 0 1 2})
(list))
1)
(test (interp (parse '{if0 1 1 2})
(list))
2)
(test (interp (parse '{if0 {f 5} 1 2})
(list (fundef 'f 'x (parse '{- x 5}))))
1)
Prepare o dever de casa como um arquivo f1wae-if0.rkt
contendo o interpretador modificado, e traga na próxima aula
(19/08/2011). Qualquer dúvida me mande um email, que
responderei prontamente!
Ambientes e F1WAE usando ambientes (PLAI cap. 5), identificadores como posições no ambiente (índices de De Brujin) (PLAI seção 3.5), funções de primeira classe via substituição (PLAI cap. 6 até 6.3). Veja os slides.
Interpretadores:
clos) (FWAE)Como dever de casa, remova a cláusula with do
interpretador FWAE, tanto da AST, quanto das funções de
substituição/interpretação. O parser ainda deve tratar expressões
with gerando uma aplicação de função que tenha o mesmo efeito:
{with {<name> <exp>} <body>} =>
{{fun {<name>} <body>} <exp>}
Prepare o dever de casa como um arquivo fae.rkt
contendo o interpretador modificado, e traga na próxima aula
(26/08/2011).
Funções de primeira classe via ambientes (PLAI cap. 6 de 6.4 em diante), recursão (capítulos 9 e 10, seção 22.4 do capítulo 22). Veja os slides.
Interpretadores:
Recursão: definindo fix como uma função de
CFAE. Currying como açúcar sintático para funções de múltiplos
parâmetros em CFAE. Pares e listas em CFAE e programação funcional
usando maps e folds. Introdução a IMP, uma linguagem imperativa
simples. Veja os slides.
Interpretadores:
Como dever de casa faça as seguintes tarefas:
Introduza o seguinte açúcar sintático na versão de CFAE acima:
{+ e1 e2 e3...} = {+ {+ {+ e1 e2} e3} ...}
A soma deve ser associativa à esquerda, como a aplicação (dica: use foldl como no parsing de aplicação). Implemente esse açúcar sintático para as operações + e -, depois implemente operações * e / nos mesmos moldes.
if0 por uma if que
funciona como o if de C (0 é falso, qualquer outro valor
é verdadeiro). Defina primitivas = e < para comparação de
números.MAP para usar if ao
invés de if0, e defina as funções FOLDR e FOLDL
nos moldes de suas versões Scheme.Continuando com IMP, uma linguagem imperativa
simples. Interpretador funcional para IMP. Interpretador para IMP
usando células (boxes). IMP com escopo local via
with: WIMP. Interpretador para WIMP usando
células. Interpretador funcional para WIMP: ambientes
vs. memória. Locais como valores de primeira classe: PWIMP.
Interpretadores:
Locais como valores de primeira classe: PWIMP. Aritmética de endereços e arrays. Funções de primeira ordem imperativas: F1PWIMP.
Interpretadores:
Computações imperativas como valores e composição de computações:
unit e bind. Reestruturação de F1PWIMP para
usar composição de computações. Uso de um vetor imperativo como
memória de F1PWIMP. Açúcar sintático para bind:
mdo. Mudando ret para sair da função
atual.
Interpretadores:
Como exercício de casa modifique F1PWIMP para poder ter funções com
múltiplos parâmetros. Isso compreende quatro partes: modificar os nós
app e capp da árvore sintática para operar
em listas de argumentos ao invés de só um argumento (tipo
PIAE? para list?); modificar o parser de
expressões e comandos; modificar o tipo FunDef para ter
uma lista de parâmetros; modificar a interpretação das aplicações nos
interpretadores para avaliar os argumentos e associar seus valores aos
nomes.
A quarta tarefa é a mais difícil, uma dica para ela é
definir uma função auxiliar allocn que aloca um espaço
contíguo na pilha, retornando o endereço do início do espaço alocado:
(define (allocn n)
(mdo (free <- (mget 0))
(mset 0 (+ free n))
(unit free)))
Uma outra função auxiliar gera um ambiente a partir de uma lista de variáveis e um endereço inicial:
(define (make-env init-env vars base)
(if (null? vars)
init-env
(env-entry (first vars)
base
(make-env init-env (rest vars) (+ base 1)))))
Também pode-se fazer um foldr para produzir a
computação que avalia e empilha os argumentos e depois chama a
função:
(foldr (lambda (arg loc/comp)
(list (- 1 (first loc/comp))
(mdo (varg <- (interp-exp arg funs env))
(mset (first loc/comp) varg)
(second loc/comp))))
(list (+ base (- (length args) 1)) ; endereço do último argumento
(interp-cmd body (make-env (env-empty) vars base)))
args)
O segundo elemento do resultado desse fold é a computação que avalia e empilha os argumentos, depois executa a função. Agora é juntar as peças! Vocês terão duas semanas para pensar bem no assunto.
Funções de primeira classe em uma linguagem imperativa. Interação
de closures com a pilha. Unificando as linguagens funcional e
imperativa: FIMP. Usando computações com escape não-local para
representar return e tratamento de exceções.
Interpretadores:
A aritmética de endereços permitida por deref
é poderosa mas bastante perigosa na prática (vide os problemas
de segurança da linguagem C). Modifique o interpretador FIMP com
exceções para restringir deref para funcionar apenas em
valores do tipo endereço e não qualquer número. A primitiva
ref também deverá ser modificada para retornar
valores desse tipo. Naturalmente vocês precisarão de um novo caso na
definição de Value. Teste seu interpretador com exemplos
que não usam aritmética de endereços, que devem continuar
funcionando, e com exemplos que usam, que devem causar erros.
Avaliação preguiçosa e sua interação com características imperativas.
Interpretadores:
Adicione funções lazy a FIMP com uma nova forma sintática lfun. Você
vai precisar criar um novo valor closl para uma closure
de uma função lazy para poder implementar o comportamento correto em
app, além do valor expV do
interpretador FIMP/L. Reutilize force e
delay de FIMP/L. Teste com esse programa que deve mostrar
a sequência de Fibonacci:
(eval '{do {set pair {lfun {x y}
{fun {z}
{if z y x}}}}
{set zipWith {fun {op l1 l2}
{pair {op {l1 0} {l2 0}}
{zipWith op {l1 1} {l2 1}}}}}
{set fibs {pair 1
{pair 1
{zipWith {fun {x y} {+ x y}}
fibs {fibs 1}}}}}
{set l fibs}
{set x 10}
{while x
{print {l 0}}
{set x {- x 1}}
{set l {l 1}}}} '(pair zipWith fibs l x))
Orientação a objetos simples: objetos, classes, mensagens. Um interpretador para uma linguagem OO dinâmica simples. Paralelos entre objetos e funções de primeira classe. Contrastando objetos e tipos abstratos de dados.
Interpretadores:
Noções básicas de verificação de tipos para linguagens
funcionais. Julgamentos de tipos e árvores de verificação. Implementando
um verificador de tipos para CFAE. Limitações da verificação de tipos:
tipando fix e tipos recursivos.
Interpretadores:
A tipagem dos pares de TCFAE não permite expressar listas usando
pares pelo mesmo motivo que não podemos expressar coisas {{fun
{x} {x x}} {fun {x} {x x}} e a implementação de
fix na própria CFAE mostrada aqui. O exercício final é alterar a
verificação de tipos dos pares para transformá-los em listas.
Substitua o tipo (pairT t1 t2) que denota um par de um
elemento de tipo t1 e um elemento de tipo
t2 pelo tipo (listT t) que irá denotar uma
lista de elementos de tipo t. A tipagem do termo
{pair e1 e2} agora deverá verificar que o tipo de
e1 é t e o tipo de e2
é (listT t) para concluir que o tipo de
{pair e1 e2} é (listT t). A tipagem
de {first e} deverá verificar que e tem o
tipo (listT t) para concluir que {first e}
tem tipo t, e a tipagem de {rest e} deverá verificar que e tem o
tipo (listT t) para concluir que {rest e}
tem tipo (listT t). Finalmente, a tipagem de
if0 também deverá aceitar uma expressão de tipo
(listT t) na condição.
A linguagem precisará de um novo termo {nil t} para
indicar uma lista vazia de tipo (listT t). Faça extensões
no parser (use a função parse-type no parse de
nil), no verificador de tipos e no interpretador para incluir
esse termo. Teste seu interpretador com as funções map e
flatten definidas no final do arquivo com a implementação de TCFAE.
Podem entrar em contato pelo meu email que responderei assim que possível.