Cálculo de Programas

Objetivos

Programação composicional: aprender a escrever programas complexos por composição de programas mais simples (princípio da composicionalidade).
Programação construtiva: aprender a escrever programas funcionais com recurso a combinadores algébricos.
Transformação de programas: recurso à algebra da programação para se obter eficiência sem sacrifício da correcção.
Arquitectura da programação: Análise, compreensão e catalogação de programas: recurso à factorização algorítmica (hilomorfismos) como forma de se perceber a arquitectura dos algoritmos e sua taxonomia.
Síntese de programas: cálculo de ciclos-for a partir de definições indutivas da matemática.
Programação funcional avançada: construir e raciocinar sobre programas funcionais com efeitos sob a forma de mónades.

Motivação.Teoria e método em programação.Cálculo e raciocínio sobre programas.Composicionalidade.Combinadores de programas.Modularidade e reutilização. «Pacotes» de programação
Programação funcional: motivação e história.Composição de funções.Noções de abstração e de isomorfismo.Iniciação à estruturação de dados.Combinadores básicos e propriedades estruturais (reflexão, fusão, absorção, cancelamento e de functorialidade)
Álgebra de um tipo de dados.Lei da troca.Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo»
Recursividade polinomial.Caso de estudo:algoritmos de ordenação.Parametrização e polimorfismo. Inferência de tipos polimórficos
Programação genérica.Functores de tipo.Introdução ao politipismo
Programação funcional com efeitos Mónades e sua teoria.Construção de programas monádicos.Exemplos:tratamento de erros,processamento de listas,computações probabilísticas e computações com estado.Referência ao mónade ‘input/output’

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://www4.di.uminho.pt/~jno/ps/pdbc.pdf. Informatics Department, University of Minho.
A. Cunha. Cálculo de Programas: notas teórico-práticas. Departamento de Informá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