Linguagens de Programação II

Sumários

• 12 Setembro 2005.
  Apresentação da disciplina.
  Regras de avaliação da disciplina.

• 13 Setembro 2005.
  Expressividade de Linguagens de Programação. Completude Turing. Sintaxe e Semântica. Sintaxe abstracta e Sintaxe concreta. Interpretação versus compilação. Máquinas Virtuais.
  Definição indutiva de tipos de dados. Algoritmos recursivos sobre tipos de dados indutivos. Representação da sintaxe abstracta como tipo indutivo.

• 19 Setembro 2005.
  Conceito de semântica operacional composicional. Uma linguagem simples de expressões aritméticas (CALC): sintaxe abstracta. Algoritmo interpretador de CALC. Implementação simples usando uma linguagem OO (Java). Primeira introdução à máquina virtual CLR. Algoritmo compilador de CALC para CLR.

• 20 Setembro 2005.
  Literais e Identificadores. Declaração de identificadores; âmbito de uma declaração. Ocorrências livres, ligadas e ligantes de identificadores. Expressões abertas e fechadas. Construção fundamental decl id=E in E end.

  Uma linguagem simples de expressões aritméticas com declarações de identificadores locais (CALCI): sintaxe abstracta e semântica/interpretador de referência usando substituição sintáctica. Definição de ambiente. O tipo abstracto de dados "ambiente". Implementação imperativa de ambientes: primitivas Assoc, Find, BeginScope e EndScope. Algoritmo interpretador de CALCI baseado em ambiente.

• 26 de Setembro 2005.
  Linguagens Imperativas. Modelo de Memória. Ambiente versus Memória.

• 27 de Setembro 2005.
  Operações imperativas primitivas (cell, set e get). Aliasing. L-value e R-value. Tempo de vida versus ambito. Exemplos de representação de vários mecanismos de manipulação de estado (apontadores, referências, etc) usando as linguagem C e ML.

• 3 de Outubro 2005.
  Estrutura das linguagens imperativas. Linguagens da família Algol versus linguagens da família ML. Expressões e comandos.

• 4 de Outubro 2005.
  Algoritmo interpretador para uma linguagem imperativa (microML) da família ML usando o modelo Ambiente-Memória. Introdução à compilação usando a linguagem microML.

• 10 de Outubro 2005.
  Arquitectura sumária das máquinas de pilha. O ambiente e máquina virtual CLR: zonas de memória (stacks / heap) e representação interna de valores e objectos. Instruções básicas. Compilação da linguagem microML para CLR. Representação de valores em tempo de execução: constantes e células de memória.

• 11 de Outubro 2005.
  Compilação da linguagem microML para CLR (Continuação).

• 17 de Outubro 2005.
  Compilação da linguagem microML para CLR (Continuação).

• 18 de Outubro 2005.
  Motivação dos sistemas de tipos. Erros de execução. Verificação dinâmica de tipos. Motivação e limitações da análise estática.

• 24 de Outubro 2005.
  Sistema de Tipos para microML. Declarações de tipos e algoritmo de tipificação para microML.

• 25 de Outubro 2005.
  Algoritmo de tipificação para microML (continuação). Propriedades de correcçao garantidas pela tipificação: well-typed programs don't go wrong.

• 31 de Outubro 2005.
  Não houve aula (FMCO'05)

• 1 de Novembro 2005.
  Não houve aula (FMCO'05)

• 7 de Novembro 2005.
  Abstracção Funcional. Parametrização e Abstracção em linguagens de programação. Abstracção sintática. Equivalência alfa. Abstracções e declarações. Exemplos.

• 8 de Novembro 2005.
  Uma linguagem simples com abstracção funcional e procedimental (CALCF). Sintaxe abstracta. Algoritmo interpretador usando substituição sintáctica. A linguagem (cálculo) LAMBDA.

• 14 de Novembro 2005.
  Algoritmo interpretador para CALCF usando um ambiente: implementação ingénua. Regra dinâmica de resolução de nomes (dynamic scope).

• 15 de Novembro 2005.
  (2) Representação de valores funcionais usando fechos (closures). Implementação da resolução de nomes correcta (estática). Algoritmo interpretador de CALCF usando fechos. Pilha "esparguete".

• 21 de Novembro 2005.
  Exemplos de execução de programas com funções de ordem superior: análise da estrutura do ambiente. Simplificação para linguagens de tipo Pascal e C: pilha de registos de activação.

• 22 de Novembro 2005.
  (2) Definições recursivas. A linguagem RECF. Ambiente circular: implementação imperativa. Exemplos. Algoritmo interpretador de RECF. Variantes usando mecanismos de passagem de parâmetros diferentes: por valor, por nome. Suspensões (thunks) e avaliação preguiçosa.

• 28 de Novembro 2005.
  Tipos Funcionais. A linguagem LAMBDA tipificada. Algoritmo de tipificação. Sistemas de regras de tipificação. Sistema de tipos para LAMBDA. Correção da tipificação e garantias: terminação e incompletude Turing. Apresentação da última fase do trabalho prático.

• 29 de Novembro 2005.
  (2) A linguagem CORE. Sistema de tipos para a linguagem CORE (tipos básicos, tipos funcionais, e tipos de referência). Tipos produto (registos etiquetados). Objectos e Classes. Representação de objectos na linguagem CORE, usando fechos e registos.

• 5 de Dezembro 2005.
  Representação de objectos na linguagem CORE. Comparação com a representação optimizada usado em C++ e Java. Tipos para objectos e classes.

• 6 de Dezembro 2005.
  Tipos para objectos e classes (continuação). Subtipo e sistemas de tipos com subtipos. Algoritmos de tipificação para objectos. Covariância e Contravariância. Tipos recursivos: motivação usando tipos de objectos.

• 12 de Dezembro 2005.
  Não houve aula.

• 13 de Dezembro 2005.
  Esclarecimentos sobre o trabalho prático.

Sumários das aulas práticas:

Sumário da quarta aula prática de LP2 (dia 11 de Outubro)
Compilação da linguagem CALCI para CIL. Utilização da directiva
.locals init (int32 v_0)
para reservar um espaço de memória onde são guardados os valores associados aos identificadores.
stloc.0, ldloc.0
são as instruções para guardar o topo da pilha na variável 0, e para recuperar o valor […]

Sumário da terceira aula prática de LP2 (dias 4 e 12 de Outubro)
Extensão da linguagem de expressões para a utilização de identificadores e declarações. A expressão utilizada, pode ter declarações multiplas, e tem a seguinte forma:
decl x=1 y=x in x+y end
Explicação das alterações na análise sintática e semântica. slides disponíveis na página da cadeira.

Sumário da segunda aula prática de LP2 (dias 26, 27 e 28 de Setembro):
Conclusão do interpretador de expressões aritméticas, geração de código .NET a partir da AST (Abstract Syntax Tree). Foi utilizada a máquina virtual Mono para correr os programas em CIL produzidos.

Sumário da primeira aula prática de LP2 (dias 20 e 21 de Setembro):
Implementação de um interpretador de expressões aritméticas, geração da AST (Abstract Syntax Tree) correspondente e correspondente avaliação das expressões. Foi utilizado o gerador de analisadores sintácticos JavaCC.
Pergunta que ficou por responder na maioria dos grupos: porque é que a expressão 1-2-3 dá como resultado 2 e não -4.