Implementação de linguagens 2020

Disciplina lecionada em conjunto com e Prof. Ricardo Rocha.

Módulo sobre linguagens funcionais

Definição de uma linguagem funcional mínima (Fun) como extensão do cálculo-lambda. Semântica operacional baseada em substituições e ambientes. Noção de "closure". A máquina SECD: arquitetura geral, instruções de máquina virtual e transições de estado. Extensões para estruturas de dados: pares, listas e records. Implementação de um compilador da linguagem Fun e compilador para SECD em Haskell e interpretador da máquina virtual em linguagem C.

Noção de semântica estrita e não-estrita. Redução call-by-value, call-by-name e call-by-need. Implementação de estratégia call-by-need usando redução de grafos. Tradução do cálculo-lambda em combinadores SKI e supercombinadores. Arquitetura da G-machine. Arquitetura da máquina STG.

Temas para trabalhos

Já estão disponíveis os temas para trabalhos deste módulo. Por favor comuniquem a vossa opção até ao 16 de maio.

Nota: por favor contactem-me se tiverem dificuldade de acesso a alguma da bibliografia recomendada.

Slides das aulas

• Aula 1: Apresentação slides-1.pdf
• Aula 2: O cálculo-lambda slides-2.pdf
• Aula 3: A linguagem Fun slides-3.pdf
• Aula 4: A máquina SECD slides-4.pdf
• Aula 4b: Implementação da SECD em baixo nível
• Aula 5: Estruturas de dados slides-5.pdf
• Aula 6: Redução de grafos slides-6.pdf. Video de uma "talk" no YouTube: An Introduction to Combinator Compilers and Graph Reduction Machines
• Aula 7: A G-machine slides-7.pdf
• Aula 7: A máquina STG slides-8.pdf
• Aula 8: Implementação da STG slides-9.pdf
• Aula 9: Performance de programas em Haskell performance.html

Programas

• Intepretador/compilador de expressões: Expr.hs
• Linguagem Fun: Fun.hs, Examples.hs
• Interpretadores da Fun: Eval1.hs, Eval2.hs, Eval3.hs
• Máquina SECD: interpretador/compilador: SECD1.hs; compilador para "bytecode": SECD2.hs; interpretador em C: secd.c; secd.h
• Tradução de cálculo-lambda para combinadores SKI: CL.hs

Bibliografia

1. Foundations of Functional Programming, notas de um curso de Lawrence C. Paulson, Computer Laboratory, University of Cambrige. Página principal, cópia local PDF.
2. Functional Programming: Application and Implementation, Peter Henderson, Prentice-Hall International. O capítulo 6 tem uma boa descrição da máquina SECD.
3. The Implementation of Functional Programming Languages, Simon Peyton Jones, Prentice-Hall International. Copia local aqui.
4. The implementation of the Gofer functional programming system, Mark P.~Jones, Yale University. Research report YALEY/DCS/RR-1030, Maio 1994.
5. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine, Simon L. Peyton Jones, Journal of Functional Programming. Disponivel em PDF.

Exames anteriores

Exame 2011, Recurso 2011.