| Designação | Código | Curso | Regime | Regente |
|---|
Cálculo de Programas | 14309 [8504P3] | Licenciatura em Ciências da Computação [CCOM] | S4 | 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: TP 2; Docente: Olga Maria Gomes Martins Pacheco; Dep.: DI; Horas: 30. |
Departamento de Informática (UM)