U.Minho Cálculo de Programas - 2007/08
[ DI/UM ]

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

  Equipa docente

  Sumários

  Horário

Ref Dia Hora Tipo Sala Cursos Docente
1 2.-feira 15h00-16h00 T CP2 111 LCC J.N. Oliveira
2 2.-feira 16h00-17h00 TP(1) CP2 111 LCC J.N. Oliveira
3 2.-feira 17h00-19h00 P(1) CP2 111 LCC J.N. Oliveira
4 4.-feira 10h00-11h00 TP(2) CP1 311 LCC O.M. Pacheco
5 4.-feira 11h00-13h00 P(2) CP1 311 LCC O.M. Pacheco
6 6.-feira 12h00-13h00 T CP1 A 2 LCC J.N. Oliveira

  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. Modularidade e reutilização. «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. 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. Propriedade universal da exponenciação B^A . Leis da exponenciação (cancelamento, reflexão e fusão).

  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. Regras para codificação de estruturas de dados funcionais na linguagem de programação C.

  6. Programação com tipos de dados indutivos. Tipos de dados recursivos vistos como equações. 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: os hilomorfismos dfac (duplo factorial) e fib (série de Fibonacci). 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.
            Apresentação do mónade de IO e do mónade de estado. Noção de autómato (determinístico). Função de transição de estado e sua codificação. Exemplo: autómato de gestão de uma agenda de telemóvel.
            O mónade de (transição de) estado e sua utilização para modelar a transição de estado de um autómato,
            Exemplo: computações com estado e IO: modelo típico de um autómato determinístico interactivo.
            Projecto de software «por camadas»: a camada puramente funcional, a camada reactiva e a camada interactiva. Exemplo de aplicação: serviço de gestão de listas de chamadas num telemóvel.

  Trabalho Prático

  FAQs

  1. Questão -- No exercício 2 é para usar a biblioteca Nat.hs?
    Resposta: Sim, uma vez que trata de funções definidas indutivamente sobre números naturais.

  2. Questão -- A proposta que é feita no exercício 8 para o isomorfismo inPTree sugere os uso de triplos. Como vamos usar o combinador >< de Cp.hs neste caso?
    Resposta: Basta converter o triplo num par aninhado, por exemplo fazendo

    inPTree :: ((a, b), (Maybe (PTree a b), Maybe (PTree a b))) -> PTree a b

  3. Questão -- Não conseguimos processar o ficheiro cp0708t.lhs porque o LaTeX envia uma mensagem de erro com o seguinte conteúdo:
    	LaTeX Error: File `isolatin1.sty' not found.
    
    	Type X to quit or <RETURN> to proceed,
    or enter new name. (Default extension: sty)
    	Enter file name:
    
    Resposta: Esse ficheiro é standard nas distribuições do LaTeX. De qualquer forma, basta procurarem isolatin1.sty no Google e encontrá-lo-ão de imediato em muitos locais. Gravem-no na mesma directoria onde está o trabalho.

  4. Questão -- Há um erro no enunciado do exercício 8: na árvore genealógica apresentada falta o pai de Mary, Jules.
    Resposta: Correcto. Já está corrigido na versão actualizada que entretanto foi colocada no Material Pedagógico.

  5. Questão -- O ficheiro Cp.hs não é processado nem pelo Hugs nem pelo GHCi devolvendo o seguinte erro:
    	cp.hs:149:0:
    	Too many parameters for class `MT'
    (Use -XMultiParamTypeClasses to allow multi-parameter classes)
    	In the class declaration for `MT'
    	Failed, modules loaded: none.
    
    Resposta: Vejam a nota de rodapé 2 na pág. 3 do enunciado.

  Material Pedagógico

Em ficheiro zip encontram-se, até à data desta versão [2008.06.25] os ficheiros/directorias:
orangeball.gif
ficheiro cpCalFun.pdf - contendo tabela de leis de cálculo funcional (actualizado).
orangeball.gif
Os ficheiros mobile.hs, examples_St.hs, St.hs e SMT.hs apresentados em aulas teóricas sobre mónades e transformadores de mónades.
orangeball.gif
cp0708t*.* - ficheiros relevantes para a realização do trabalho prático da disciplina (incluindo manual do xypic).
orangeball.gif
demos.hs - contendo material auxiliar para a visualização em HTML 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.
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 - apresentando a manipulação de listas do Haskell sob a forma de catamorfismos.
orangeball.gif
ficheiro Nat.hs - apresentando 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
ficheiro msdn02.pdf - contendo acetatos mostrados nas primeiras aulas.

  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 25-Jun 14h00-16h00 Salas 2209 e 2210 - pdf
Recurso 14-Jul 14h00-16h00 1303, 1304 - pdf
Especial 22-Set 09h30-11h30 2305 - pdf

  Classificações


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


J. Nuno Oliveira 2009-02-16