Departamento de Informática (UM)

Cálculo de Programas

14309 [J305N1]

Licenciatura em Engenharia Informática [ENGINF]

S5

José Nuno Fonseca Oliveira

Objetivos

Esta disciplina tem por principal objectivo ensinar métodos que permitem uma abordagem composicional e escalável ao desenvolvimento de software, tendo por base a teoria algébrica da programação funcional. Sendo a construção de programas uma actividade essencialmete colectiva, há um trabalho de grupo (em Haskell) que complementa a componente teórica dos conteúdos, estes objecto de aulas teórico-práticas onde se resolvem exercícios de cálculo de programas funcionais.

Programa

1. Motivação. Teoria e método em programação. Cálculo e raciocínio sobre programas. Composicionalidade. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.
2. Programação funcional: motivação e história. Composição de funções. Noções de abstração e de isomorfismo. Iniciação à estruturação de dados. Combinadores básicos e propriedades estruturais (reflexão, fusão, absorção, cancelamento e functorialidade). Lei da troca.
3. Álgebra de um tipo de dados. Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo».
4. Recursividade polinomial. Caso de estudo: algoritmos de ordenação. Parametrização e polimorfismo. Inferência de tipos polimórficos e de «propriedades grátis».
5. Programação genérica. Functores de tipo. Introdução ao politipismo.
6. Programação funcional com efeitos. Mónades e sua teoria. Construção de programas monádicos. Exemplos: tratamento de erros, processamento de listas, computações probabilísticas e computações com estado. Referência ao mónade 'input/output'.

Bibliografia

J. N. Oliveira. Program Design by Calculation, 2008 (Chapters 2, 3 and 4). Draft of textbook in preparation, current version: October 2019. Available from http://www.di.uminho.pt/~jno/ps/pdbc.pdf . Informatics Department, University of Minho.

A. Cunha. Cálculo de Programas: notas teórico-práticas. Departamento de Informática, Universidade do Minho, 2005.

R. Bird and O. de Moor. Algebra of Programming. Series in Computer Science. Prentice-Hall International, 1997. C. A. R. Hoare, series editor. BGUM 510.5-B .

Resultados da aprendizagem

- Programação composicional: aprender a escrever programas complexos por composição de programas mais simples (princípio da composicionalidade).
- Programação construtiva: aprender a escrever programas funcionais com recurso a combinadores algébricos.
- Transformação de programas: recurso à algebra da programação para se obter eficiência sem sacrifício da correção.
- Arquitectura da programação: Análise, compreensão e catalogação de programas: recurso à (hilo-)factorização algorítmica como forma de se perceber a arquitectura dos algoritmos e sua taxonomia.
- Síntese de programas: cálculo de programas cíclicos a partir de definições indutivas da matemática.
- Programação funcional avançada: construir e raciocinar sobre programas funcionais com efeitos sob a forma de mónades.

Método de avaliação

A avaliação é feita com base numa prova individual sem consulta, com exame de recurso, e num trabalho de grupo a realizar fora das aulas e sujeito a uma prova oral (apresentação e demonstração do trabalho). Alunos do mesmo grupo poderão ter classificações diferentes conforme a sua prestação oral. O trabalho será realizado na linguagem Haskell.

Funcionamento

Turno: T 1; Docente: José Nuno Fonseca Oliveira; Dep.: DI; Horas: 30.
Turno: TP 1; Docente: Olga Maria Gomes Martins Pacheco; Dep.: DI; Horas: 30.
Turno: T 2; Docente: José Nuno Fonseca Oliveira; Dep.: DI; Horas: 30.
Turno: TP 2; Docente: José Nuno Fonseca Oliveira; Dep.: DI; Horas: 30.
Turno: TP 3; Docente: Olga Maria Gomes Martins Pacheco; Dep.: DI; Horas: 30.
Turno: TP 4; Docente: Daniel Rodrigues Pacheco Murta; Dep.: DI; Horas: 30.
Turno: TP 5; Docente: Daniel Rodrigues Pacheco Murta; Dep.: DI; Horas: 30.