Diário de Bordo

MAC0316/MAC5754 - Primeiro Semestre de 2011

Prof. Francisco Reverbel

Março

Abril

Maio

Junho

Esta página estará em permanente construção até o final do semestre...

Março

1 de março (aula 1):
- Apresentação da disciplina.
- Motivação para o estudo de programação funcional.
- Introdução à linguagem Scheme (TYS, capítulos 1 e 2, até 2.1.4).
4 de março (aula 2):
- Continuação do material sobre Scheme:
  - Tipos de dados (TYS, de 2.1.4 até o final do capítulo 2).
  - Formas e funções (TYS, capítulo 3).
    - Também vimos que (define (func params ...) body) é o mesmo que (define func (lambda (params ...) body)) (isso não está no TYS).
  - Formas condicionais (TYS, capítulo 4 , exceto 4.1).
  - Escopo dos parâmetros de funções (TYS, parte inicial do capítulo 5 - paramos antes de 5.1).
  - Recursão (TYS, parte inicial do capítulo 6 - paramos antes de 6.1).
11 de março (aula 3):
- Variáveis locais:
  - Uso da forma define dentro de funções. Exemplo: função hanoi contendo uma função local r-hanoi.
  - Variáveis locais introduzidas pela forma let (TYS, seção 5.1). Exemplo: versão melhorada da função hanoi.
  - Abreviação conveniente para lets aninhados: a forma let* (TYS, seção 5.1).
- As duas implementações da função hanoi vistas em classe não são puramente funcionais, pois elas têm um efeito colateral: a apresentação da solução na tela. Uma versão funcional pura devolveria a solução, sem apresentá-la na tela.
- Funções de ordem superior (higher-order functions): funções que recebem funções como parâmetros ou que devolvem funções como valores.
  - Exemplo: a função map (TYS, seção 6.4).
  - Implementação da função map.
- Recursão de cauda (tail recursion).
  - Duas implementações da função fatorial: uma (já vista numa aula anterior) com recursão que não é de cauda, outra com recursão de cauda. A primeira consome um espaço adicional que é proporcional a n. A segunda não consome espaço adicional, pois Scheme implementa a otimização conhecida como tail call optimization (TCO).
  - Duas implementações da função map: uma com recursão que não é de cauda, outra com recursão de cauda.
15 de março (aula 4):
- Scheme padrão (R5RS e R6RS), Racket (PLT Scheme) e PLAI Scheme. Formas específicas do PLAI Scheme: define-type, type-case e test.
- Modelamento de linguagens (capítulo 1 do PLAI):
  - Sintaxe concreta, BNF.
  - Sintaxe abstrata, árvore sintática.
  - Analisador sintático (parser)
  - Estudo de caso: a linguagem AE (arithmetic expressions).
18 de março (aula 5):
- Interpretador para a linguagem AE (capítulo 2 do PLAI).
- Substituição (capítulo 3 do PLAI):
  - A linguagem WAE.
  - Definições:
    - instância vinculante (binding instance) de um identificador;
    - escopo (scope) de uma instância vinculante;
    - instância vinculada (bound instance);
    - instância livre (free instance).
  - Definição precisa de substituição.
  - Função subst para a linguagem WAE.
  - Interpretador para a linguagem WAE.
22 de março (aula 6):
- Tópicos finais do capítulo sobre substituição (capítulo 3 do PLAI, seções 3.4 e 3.5):
  - Substituição com avaliação ávida (eager) e substituição com avaliação preguiçosa (lazy).
  - Coordenadas estáticas de distância (índices de Nicolaas de Bruijn)
- Introdução a funções (capítulo 4 do PLAI):
  - A linguagem F1WAE e a estrutura FunDef.
  - Tópico auxiliar: a forma local do Racket.
  - Interpretador para a linguagem F1WAE.
  - Escopo da substituição e escopo das definições de funções.
25 de março (aula 7):
- Substituição postergada, escopo estático e escopo dinâmico (capítulo 5 do PLAI).
29 de março (aula 8):
- Primeira prova: enunciado, solução, solução com casos de teste nas três primeiras questões, casos de teste da questão 4.

Abril

1 de abril (aula 9):
- Funções de primeira classe (capítulo 6 do PLAI, até a seção 6.3):
  - Funções de primeira ordem, funções de ordem superior e funções de primeira classe.
  - A linguagem FWAE.
  - Interpretador para a linguagem FWAE baseado em substituição explícita.
  - A linguagem FAE, na qual a forma with é "acúcar sintático" para uma chamada a uma função anônima de primeira classe.
5 de abril (aula 10):
- Funções de primeira classe - continuação (capítulo 6 do PLAI, seções 6.4 a 6.7):
  - Interpretador para a linguagem FAE baseado em substituição postergada.
  - O conceito de fechamento (closure).
  - Exemplos que mostram a importância do escopo estático e de fechamentos.
  - O conceito de ambiente (environment).
8 de abril (aula 11):
- Avaliação preguiçosa na presença de funções (seção 6.6 do PLAI).
- Laziness (capítulo 7 do PLAI, até o início da seção 7.1.4):
  - Introdução à linguagem Haskell.
  - Haskell: listas, tipos polimórficos e inferência de tipos.
  - Avaliação preguiçosa em Haskell (apenas começamos este assunto).
- Leitura complementar: "Learn You a Haskell for Great Good!", um ótimo tutorial de Haskell.
12 de abril (aula 12):
- Laziness (capítulo 7 do PLAI, de 7.1.4 ao final do capítulo):
  - Avaliação preguiçosa em Haskell.
  - Interpretador para a linguagem WAE escrito em Haskell.
  - Avaliação preguiçosa na linguagem da shell (bash).
- Leitura complementar: "Learn You a Haskell for Great Good!", um ótimo tutorial de Haskell.
15 de abril (aula 13):
- Implementação de uma linguagem com avaliação preguiçosa (capítulo 8 do PLAI, até 8.2):
  - A linguagem CFAE/L (CFAE com laziness).
  - O conceito de fechamento de expressão (expression closure).
  - Interpretador para a linguagem CFAE/L.
  - Outro interpretador para a linguagem CFAE/L, este com caching.
26 de abril (aula 14):
- Tópicos finais sobre avaliação preguiçosa (capítulo 8 do PLAI, seções 8.3 e 8.4):
  - Caching, transparência referencial, memoization.
  - Independência entre o regime de substituição (substituição explícita ou substituição postergada) e o de avaliação (avaliação ávida ou avaliação preguiçosa)
  - Independência entre escopo (estático ou dinâmico) e regime de avaliação (avaliação ávida ou avaliação preguiçosa).
- Recursão (capítulo 9 do PLAI):
  - A forma rec e a linguagem RCFAE.
  - Ambientes para recursão (ambientes cíclicos).
29 de abril (aula 15):
- Implementação de recursão (capítulo 10 do PLAI):
  - Interpretador para a linguagem RCFAE.
- Outras formas de representar ambientes e funções de primeira classe (capítulo 11 do PLAI, até 11.2):
  - Representação dos ambientes da linguagem FAE como funções de Scheme.

Maio

3 de maio (aula 16):
- Outras formas de representar ambientes e funções de primeira classe (continuação do capítulo 11 do PLAI):
  - Representação das funções da linguagem FAE como funções de Scheme.
  - Classificação dos interpretadores: interpretadores sintáticos e meta interpretadores. Interpretadores meta circulares.
  - Interpretadores meta circulares. Interpretador meta circular para a linguagem FAE.
  - Tópico para estudo individual: Representação funcional de ambientes recursivos (seção 11.5 do PLAI).
- Estado e estruturas de dados mutáveis (capítulos 12 e 13 do PLAI, até 13.1):
  - Boxes e a linguagem BCFAE.
6 de maio (aula 17):
- Estado e estruturas de dados mutáveis (continuação do capítulo 13 do PLAI, até a página 127):
  - Modelo da memória como um repositório dinâmico: o armazém (store).
  - Avaliação de expressões BCFAE. O emprego dos repositórios estático (ambiente) e dinâmico (armazém).
  - Interpretador para a linguagem BCFAE: interpretação de num, id, fun, if0, add e app.
  - Uso de passagem explícita de estado (store-passing style) por esse interpretador.
10 de maio (aula 18):
- Estado e estruturas de dados mutáveis (continuação do capítulo 13 do PLAI, da página 128 ao final do capítulo):
  - Interpretador para a linguagem BCFAE: interpretação de seqn, newbox, setbox e openbox.
  - Escopo léxico versus extensão dinâmica.
- Variáveis (capítulo 14 do PLAI, até 14.1):
  - Implementação de variáveis. Interpretador para a linguagem VCFAE.
13 de maio (aula 19):
- Variáveis (continuação do capítulo 14 do PLAI, de 14.2 ao final do capítulo):
  - Variáveis e chamadas de funções: passagem por valor (call by value) passagem por referência (call by reference).
  - Interpretador para a linguagem RVCFAE.
  - Passagem de parâmetros por referência: avaliação crítica.
17 de maio (aula 20):
- Segunda prova: enunciado, solução.
20 de maio (aula 21):
- Introdução a continuações (capítulos 15, 16 e 17 do PLAI, até 17.1):
  - Alguns problemas com aplicações Web.
  - Estrutura de aplicações Web.
  - Transformação de um programa interativo para adaptá-lo ao Web.
  - Transformação de uma função recursiva.
31 de maio (aula 22):
- Continuações (capítulo 17 do PLAI, de 17.2 a 17.6):
  - Transformação envolvendo mais de uma função.
  - Transformação de funções com estado.
  - Transformação de funções de ordem superior.

Junho

3 de junho (aula 23):
- Transformação de um programa para CPS (capítulo 18 do PLAI):
  - O estilo de passagem de continuações (continuation-passing style, ou CPS).
  - Visão informal da transformação de um programa para CPS.
  - Transformação automatizada para CPS.
- Suporte para continuações em Scheme (capítulo 19 do PLAI, até 19.1):
  - Captura de continuações: as formas call/cc e let/cc.
7 de junho (aula 24):
- Suporte para continuações em Scheme (seção 13.1 do TYS e capítulo 19 do PLAI, a partir de 19.2):
  - Continuações Scheme são procedimentos escapadores (escapers).
  - Aplicação: fluxos de controle anormais (exceções).
    - Leia esta mensagem.
  - Aplicação: programação de aplicações Web.
  - Aplicação: produtores e consumidores.
- Leitura recomendada: seções 19.5 e 19.6 do PLAI, cujo conteúdo foi tocado muito rapidamente em aula.
10 de junho (aula 25):
- Implementação de continuações (capítulo 20 do PLAI):
  - Nova implementação do interpretador para a linguagem CFAE: esta versão usa a representação procedural de funções e é escrita em CPS.
  - A linguagem KCFAE.
  - Interpretador para a linguagem KCFAE.
14 de junho (aula 26):
- Quão pequena pode ser uma linguagem de programação? (capítulo 22 do PLAI, até a página 227):
  - Visão informal do cálculo lambda.
    - Representação de pares e listas.
    - Representação das constantes booleanas e da forma condicional.
    - Representação dos números naturais (Church numerals). Aritmética dos naturais.
  - Funções recursivas em nossa linguagem minimal.
17 de junho (aula 27):
- O combinador Y (capítulo 22 do PLAI, seção 22.4).
21 de junho (aula 28):
- Terceira prova.
28 de junho (aula 29):
- Prova substitutiva.

Last modified: Tue Jul 19 22:24:49 BRT 2011
Francisco Reverbel
reverbel at ime.usp.br