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

 Novo  Classificações finais: ver tinynew.gifsecçã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
tinynew.gif Provas de Avaliação | tinynew.gif Classificações ]

  Equipa docente

  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

  Atendimento

  Programa Resumido

  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:
orangeball.gif
ficheiro _exp.pdf útil para a realização do exercício 6 do trabalho prático.
orangeball.gif
ficheiros cp0809t.* relevantes para a realização do trabalho prático da disciplina. Começar por ler cp0809t.pdf.
orangeball.gif
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.
orangeball.gif
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);
orangeball.gif
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);
orangeball.gif
Exp.hs e HugsList.hs - auxiliares a demos.hs;
orangeball.gif
ficheiro List.hs - possibilitando a manipulação de listas do Haskell sob a forma de catamorfismos, anamorfismos, etc.
orangeball.gif
ficheiro Nat.hs - possibilitando a manipulação de números naturais em Haskell sob a forma de catamorfismos.
orangeball.gif
Cp.hs - contendo os combinadores de base da notação adoptada, e.g. split, ><, -|- etc.;
orangeball.gif
_ms.pdf - contendo os apontamentos manuscritos sobre algoritmo de Hindley-Milner;
orangeball.gif
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 - tinynew.gif pdf

  Classificações


Voltar à página principal de CP.
Outras disciplinas leccionadas pelo DIUM


J. Nuno Oliveira 2009-07-28