Cálculo de Programas - 2008/09
[ DI/UM ]

Novo	Classificações finais: ver secção respectiva.

[ Contacto | Página principal
Equipa docente | Horário | Regime de Avaliação | Atendimento
Sumários | Programa Resumido | Programa Detalhado
Trabalho Prático | Wiki | Material Pedagógico
Bibliografia essencial | Bibliografia complementar
Provas de Avaliação | Classificações ]

Equipa docente

• Teóricas: J.N. Oliveira (406006)
• Teórico-práticas e práticas: J.N. Oliveira (406006) (com o apoio de Hugo Macedo)

Sumários

Disponíveis em PDF

Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	4.�-feira	11h00-12h00	T	CP2 111	LCC	J.N. Oliveira
2	4.�-feira	12h00-13h00	T	CP2 111	LCC	J.N. Oliveira
3	6.�-feira	14h00-15h00	TP	CP2 111	LCC	J.N. Oliveira+Hugo Macedo
4	6.�-feira	15h00-17h00	P	CP2 111	LCC	J.N. Oliveira+Hugo Macedo

Regime de Avaliação

• t = informação teórica por prova escrita sem consulta de acordo com regulamentação interna em vigor (épocas normal, de recurso ou especial) -- 60% (nota mínima: 8)
• p1 = informação prática relativa a um prático trabalho obrigatório a realizar por grupos de 2 alunos -- 30%
• p2 = componente de avaliação contínua relativa à resposta dos alunos aos desafios e sugestões de estudo que vão sendo propostos no Wiki da disciplina -- 10%

Atendimento

• Em qualquer altura: via correio electrónico pressionando aqui (J.N. Oliveira) ou aqui (Hugo Macedo).
• Sujeito a marcação verbal junto do docente responsável pela disciplina, com um mínimo de uma semana de antecedência:

  Dia	Hora	Cursos	Docente
  2.�-feira	08h30-11h00	LCC	J.N. Oliveira

Programa Resumido

• 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.

• Programação funcional: sua motivação e antecendentes históricos. Composição de funções. Noções de abstracção e de isomorfismo.

• Iniciação à estruturação de dados. Combinadores básicos e suas propriedades estruturais (reflexão, fusão, absorção, cancelamento e de functorialidade). Álgebra de um tipo de dados. Lei da troca.

• Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo». Recursividade polinomial. Lei de recursividade múltipla e suas aplicações na construção de algoritmos eficientes (eg. iterativas). Caso de estudo: implementação do cálculo de séries de Taylor por algoritmos iterativos.

• Parametrização e polimorfismo. Inferência de tipos polimórficos segundo o método Hindley-Milner. Programação genérica. Functores de tipo. Introdução ao politipismo.

• Programação modular.

• Programação funcional com mónades. `Input/output'. Excepções.

Programa Detalhado

1. Teoria e método em programação. Arquitectura do «software». Composicionalidade. Interfaces. Combinadores de programas. «Pacotes» de programação. Análise de requisitos e sua captação funcional. Exemplo: gestão de listas de chamadas num telemóvel. Concepção composicional e reutilização.

2. Introdução à Programação funcional. Conceito de função. A função como contrato. Diagramas de blocos. Domínio e codomínio de uma função. Igualdade extensional. Diagramas funcionais. Setas f : A -> B. Notação funcional com ou sem variáveis.

3. Combinadores de programas funcionais. A composição f ·g como combinador elementar de funções. Associatividade da composição: Função identidade id. O polimorfismo de id e a propriedade f ·id = id ·f = f e seu diagramas comutativo.
           O combinador <f,g> e o produto A � B (analogia com «struct» em C) e suas projecções. O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções.
           Os combinadores f � g e f + g .
           Noção de isomorfismo entre tipos de dados. Funções bijectivas ou isomorfismos. Função inversa. Predicados e guardas. Condicional de McCarthy.

4. Álgebra da programação funcional. Propriedades universais. Propriedades de reflexão. Propriedades de cancelamento e fusão. Lei da troca. Propriedades de absorção e propriedades functoriais. Leis de fusão do condicional de McCarthy.

5. Programação funcional em HASKELL e sua comparação com C. Costumização de produtos e coprodutos em HASKELL. Álgebras e coálgebras de tipos de dados. O conceito de «apontador» 1 + A (Maybe a em HASKELL). Funções parciais.

6. Programação com tipos de dados indutivos. Tipos de dados recursivos vistos como equações. Os número naturais e a equação N =1 + � N . As listas ligadas e a equação L =1 + A � L .
           Apresentação do módulo List.hs. Estudo da triologia cata-ana-hilo associada ao tipo List. O algoritmo de cálculo do quadrado de um número visto como hilomorfismo sobre a estrutura List a. O algoritmo de ordenação por inserção simples visto como hilomorfismo sobre a estrutura List a.
           Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort (`quick sort').
           Estudo da triologia cata-ana-hilo associada ao tipo LTree. Exemplos: o hilomorfismo fib (série de Fibonacci) e o hilomorfismo mSort (`merge sort').

7. Definição genérica de um tipo indutivo de dados. Noção de functor de base. Operadores fmap vs catamorfismos: Politipismo da definição t a =b(a,t a) de um tipo indutivo genérico paramétrico. Noção de functor de tipo e sua formulação genérica como o catamorfismo t f =cata (in ·b(f,id)).
           Propriedade universal de um catamorfismo cata (f) do tipo genérico t a =b(a,t a) e suas derivadas: cancelamento-cata e reflexão-cata.

8. Classificação algorítmica. Quadro sinóptico dos principais algoritmos analisados e estudados ao longo da disciplina. Polimorfismo versus politipismo. Programação dita «genérica».

9. Programação funcional monádica. Motivação: funções parciais e sua composição. Manipulação de erros e mecanismos de excepção («exception handling»). Funções monádicas envolvendo listas.
           Mónadas versus functores. Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Regra geral para a composição monádica.
           Definição formal de mónade. Composição e sua unidade. Multiplicação e suas propriedades.
           Exemplos: listas e Maybe. Mónadas em HASKELL: a class Monad e os operadores return, (»=) e ». A notação do. Introdução à notação em compreensão. A definição fmap f x = do { a <- x ; return (f a) } e sua generalização à promoção monádica de operações n-árias.

Trabalho Prático

Ver Material Pedagógico.

Material Pedagógico

Em ficheiro zip encontram-se, até à data desta versão [2009.06.27] os ficheiros/directorias:

ficheiro _exp.pdf útil para a realização do exercício 6 do trabalho prático.

ficheiros cp0809t.* relevantes para a realização do trabalho prático da disciplina. Começar por ler cp0809t.pdf.

ficheiro demos.hs - contendo

1. material auxiliar para a visualização em da estrutura de dados virtual (intermédia) dos hilomorfismos qSort, hanoi, mSort etc das bibliotecas BTree.hs e LTree.hs. Experimente qSort_vtree [6,3,9,1,7,18] e hanoi_vtree (True, 7), por exemplo. Encontrará a visualização no ficheiro _.html da directoria corrente.
2. o estudo da função fib feito nas aulas teorico-práticas, com recurso à biblioteca System.Time.

LTree.hs - contendo os cata/ana/hilomorfismos do tipo de dados árvores binárias de folhas - LTree a = Leaf a | Split (LTree a, LTree a) e aplicações suas (e.g. duplo factorial, `merge-sort', Fibonacci etc);

BTree.hs - contendo os cata/ana/hilomorfismos do tipo de dados árvores binárias - data BTree a = Empty | Node(a, (BTree a, BTree a)), e aplicações suas (e.g. torres de Hanói, `quick-sort', etc);

Exp.hs e HugsList.hs - auxiliares a demos.hs;

ficheiro List.hs - possibilitando a manipulação de listas do Haskell sob a forma de catamorfismos, anamorfismos, etc.

ficheiro Nat.hs - possibilitando a manipulação de números naturais em Haskell sob a forma de catamorfismos.

Cp.hs - contendo os combinadores de base da notação adoptada, e.g. split, ><, -|- etc.;

_ms.pdf - contendo os apontamentos manuscritos sobre algoritmo de Hindley-Milner;

ficheiro cpCalFun.pdf - contendo tabela de leis de cálculo funcional.

Bibliografia essencial

Ol05

J.N. Oliveira.
Program Design by Calculation . Chapters 2, 3 and 4 of draft textbook in preparation.
Departamento de Informática, Universidade do Minho, 2005. (Updated 2008)

Bibliografia complementar

Bir98

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

Bir98

R. Bird.
Introduction to Functional Programming
Series in Computer Science. Prentice-Hall International, 2nd edition, 1998.
C. A. R. Hoare, series editor.

Hu00

P. Hudak.
The Haskell School of Expression - Learning Functional Programming Through Multimedia .
Cambridge University Press, 1st edition, 2000.
ISBN 0-521-64408-9.

VB00

J.M. Valença and J.B. Barros.
Fundamentos da Computação II: Programação funcional.
Universidade Aberta, 2000.
ISBN 972-674-318-4, 234 p.

Provas de Avaliação

Calendário:

Época	Data	Hora	Salas	Inscritos	Prova
Normal	29-Jun	16h00-18h00	Sala 2203	-	pdf
Recurso	17-Jul	14h00-16h00	Sala 1201	-	pdf

Classificações

• Classificações finais:

  23180 = 14; 25364 = F; 28162 = F; 30481 = 10; 30712 = 10; 30726 = F; 30746 = F; 30755 = 15; 31195 = F; 33691 = F; 33694 = F; 33712 = R; 35820 = F; 35857 = F; 38584 = 10; 39293 = F; 40995 = F; 41041 = 12; 42198 = R; 42211 = F; 43502 = 11; 43533 = F; 43534 = F; 43538 = F; 43545 = 13; 44633 = 12; 46222 = 16; 47401 = R; 47403 = F; 47408 = 15; 47410 = F; 47415 = 13; 47422 = R; 47424 = F; 47425 = F; 47429 = F; 48392 = 10; 48401 = F; 48406 = 10; 48408 = F; 48410 = F; 48418 = 14; 50187 = F; 50188 = 13; 50190 = F; 50192 = F; 50195 = R; 50197 = R; 50199 = F; 50200 = 10; 50201 = F; 50202 = 10; 50204 = 13; 51142 = F; 51150 = F; 51152 = F; 51155 = 13; 51157 = 14; 51163 = F; 51164 = 13; 51166 = 17; 51176 = 14; 51177 = F; 51178 = F; 52818 = F; 52853 = R; 52856 = 17; 54052 = F; 54056 = F; 54058 = F; 54073 = F.

Outras disciplinas leccionadas pelo DIUM