Métodos de Programação I - 2001/02
[ DI/UM ]

[ Equipa docente | Horário | Regime de Avaliação | Atendimento | Sumários |
Programa Resumido | Programa Detalhado
Trabalhos Práticos | Material Pedagógico | FAQs | Bibliografia de Apoio | Provas de Avaliação | Notas Finais ]

  Equipa docente

• Teóricas -- J.N. Oliveira (406006)
• Teórico-práticas -- J.B. Barros (406024), J.S. Pinto (406069) e M.J. Frade (406054)

  Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	2.ª-feira	18h00-20h00	TP(1)	CP2-307	LESI	J.B. Barros
2	3.ª-feira	08h00-10h00	TP(2)	CP3-404	LESI	M.J. Frade
3	3.ª-feira	10h00-12h00	TP(3)	CP3-403	LESI	M.J. Frade
4	3.ª-feira	16h00-17h00	T	CP1-A3	LESI+LMCC	J.N. Oliveira
5	5.ª-feira	11h00-12h00	T	2.A102	LMCC+LESI	J.N. Oliveira
6	5.ª-feira	16h00-18h00	TP(1)	CP1-104	LMCC	J.S. Pinto
7	5.ª-feira	18h00-20h00	TP(4)	CP2-304	LESI	J.S. Pinto
8	5.ª-feira	18h00-20h00	TP(2)	CP1-104	LMCC	J.B. Barros

  Regime de Avaliação

• Componentes:
  • t = informação teórica por prova escrita sem consulta de acordo com regulamentação interna em vigor (épocas normal, de recurso ou especial)
  • p = informação prática calculada como a média da informação relativa a:
    • 3 trabalhos práticos propostos para realização em grupo; cada trabalho, acompanhado dum relatório sucinto, será discutido em frente ao computador com cada grupo.

• Fórmula de avaliação: a nota final nf será dada pela fórmula:

  nf = if p < 9.5 then (if t > 16 then 16 else t) else p * 0.4 + t* 0.6

  sujeita à condição:

  t >= (if (p >= 9.5) then 8.0 else 9.5)

  Atendimento

• Em qualquer altura: via email (jno@di.uminho.pt), devendo ser colocando no assunto o `string' MP-I/0102; toda a resposta que tenha interesse geral será aqui afixada na secção de `FAQ's.
• Sujeito a marcação verbal pelo docente respectivo, com um mínimo de uma semana de antecedência:

  Dia	Hora	Cursos	Docente
  2.ª-feira	10h00-12h00	LMCC+LESI	J.B. Barros
  3.ª-feira	09h00-12h00	LMCC+LESI	J.B. Barros
  3.ª-feira	16h00-18h00	LESI	M.J. Frade
  3.ª-feira	17h00-18h00	LESI+LMCC	J.N. Oliveira
  5.ª-feira	11h00-13h00	LESI+LMCC	J.S. Pinto

  Sumários

• Aulas Teóricas
• Aulas Práticas

  Programa Resumido

• Motivação. Teoria e método em programação. 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.

• Inferência de tipos segundo o método Hindley-Milner.

• Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo». Recursividade polinomial. Caso de estudo: algoritmos de ordenação.

• Parametrização e polimorfismo. Programação genérica. Functores de tipo. Introdução ao politipismo.

• Programação modular.

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

  Programa Detalhado

1. Teoria e método em programação. Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programaçã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.

3. Estudo dos combinadores elementares de programas funcionais

   A composição f ·g como combinador elementar de funções. Associatividade da composição. Função identidade id. Estudo dos combinadores elementares de programas funcionais (cont.): Polimorfismo da função identidade. A propriedade f ·id = id ·f = f e seu diagramas comutativo. Notação funcional com ou sem variáveis.

   O combinador <f,g> e o produto A * B (analogia com «struct» em C) e suas projecções. Propriedade de cancelamento- * . O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções. Propriedades universais de <f,g> e de [f,g] e suas derivadas (cancelamento, reflexão e fusão). Os combinadores f * g e f + g . Propriedades de absorção. Propriedades functoriais.

   Apresentação da extensão Mpi.hs ao Prelude.hs do Hugs 98.

   Lei da troca. Diagrama da lei da troca. Exemplo: undistr.

4. Isomorfismo entre tipos de dados Invertibilidade à esquerda e à direita. Funções sobrejectivas (com inversa à direita) e funções injectivas (com inversa à esquerda). Funções bijectivas ou isomorfismos. O isomorfismo A * B =B * A (swap). Outros isomorfismos célebres envolvendo produtos e coprodutos (assocr etc).

   Predicados e guardas. Condicional de McCarthy. Lei da fusão do condicional de McCarthy.

   Tipos elementares genéricos: 0 , 1 e 2 (resp. Void, () e Bool em HASKELL). Segmentos iniciais e tipos enumerados.

   Funções constantes. O combinador c . Propriedades. Polimorfismo da função constante: c = c ·f.

5. Estudo dos combinadores avançados de programas funcionais

   Funções de ordem superior. Noção de espaço funcional. O combinador curry f e o operador ap. A exponencial B^A e seus isomorfismos (eg. curry, split, either etc). As funções ! : A ->1 e ? : 0 ->A .

   Propriedade universal de curry f e cancelamento da exponencial.

   As propriedades de fusão e reflexão da exponencial como consequência da propriedade universal de curry f . A construção f^A e a propriedade de absorção.

   Produtos e coprodutos n -ários ( n>=0 ).

6. Introdução aos tipos de dados recursivos a partir de uma analogia com a programação imperativa

   O conceito de «apontador» 1 + A (Maybe a em HASKELL). Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A * L .

7. Tipos indutivos de dados e seus ccombinadores

   Declaração de tipos de dados em HASKELL. Sua relação com o coproduto. Álgebra e co-álgebra do tipo indutivo definido pela equação L =1 + A * L . Isomorfismo. Introdução à observação de tipos indutivos usando como exemplo listas de inteiros: data L = Nil | Cons (Int,L) .

   Conceitos de catamorfismo e anamorfismo usando o tipo de dados exemplo listas de inteiros: data L = Nil | Cons (Int,L) . Conceito de hilomorfismo usando o tipo de dados exemplo listas de inteiros - data L = Nil | Cons (Int,L) . O factorial visto como um hilomorfismo. Cálculo de programas: eliminação da estrutura de dados intermédia de um hilomorfismo.

   Apresentação do módulo RList.hs: o algoritmo de ordenação por inserção simples como hilomorfismo sobre a estrutura RList a.

   Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a)). Apresentação do módulo BTree.hs. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort (`quick sort').

8. Introdução à parametrização e ao polimorfismo.

   Formulação de map (em [a]) e de fmap em RList como catamorfismos. Propriedades:

   fmap id = id
   fmap (f . g) = (fmap f) . (fmap g)

   Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Exemplos: functor indentidade, functor constante e a exponencial. Propriedades naturais.

   Noção de bi-functor. Propriedades. Bi-functores em HASKELL: a class BiFunctor e o operador bmap. Exemplos: functor produto e coproduto.

9. Politipismo ou programação genérica

   Definição genérica de um tipo indutivo de dados. Parametrização. Noção de functor de base. maps são 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)).

   Polimorfismo versus politipismo. Programação dita «genérica». Propriedade universal de um catamorfismo cata (f) do tipo genérico t a =b(a,t a) e suas derivadas: cancelamento-cata. Derivação das leis genéricas de reflexão-cata e de fusão-cata. Exemplos de aplicação. Derivação da lei genérica de absorção-cata.

   Noção de functor polinomial. Forma canónica de um functor polinomial. Lei do binómio de Newton. Noção de tipo de dados indutivo polinomial. t a1...an =b(a1,...,an,ta1...an) . Generalização da triologia cata-ana-hilo à indução polinomial.

10. Exemplos de aplicação

    Triologia cata-ana-hilo associada ao tipo BTree - exemplos célebres: os catamorfismos de travessia (in/pre/pós-ordem). 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').

11. Introdução ao conceito de mónada:

    Motivação e definição formal. Operadores de composição, multiplicação e aplicação monádica (`bind'). Extensão monádica de uma função. Propriedades. Mónadas em HASKELL: a class Monad e os operadores return, (»=), » e fail. Exemplos de mónadas: excepções, listas e funcionalidade de entrada/saída.

12. Síntese final. Quadro sinóptico classificativo dos algoritmos analisados e estudados ao longo da disciplina:

    Classe B(A,X) B(A,C,X) Travessias Ordenação Factorial Outros

    RList 1 + A × X iSort fac sq

    LList 1 + X × A

    BTree 1 + A × X² in/pré/pós qSort hanoi

    LTree A + X² flatten mSort dfac fib

    FTree C + A × X²

  Trabalhos Práticos

• Trabalho prático Nr. 1 (prazo de entrega: 01.10.31)
• Trabalho prático Nr. 2 (prazo de entrega: 01.12.03)
• Trabalho prático Nr. 3 (prazo de entrega: 02.01.04)

  Material Pedagógico

No ficheiro mpi0102mp.zip encontram-se, até ao momento [data desta versão: 01.12.20]:

ficheiro README.txt - informação sobre versões, etc.

os ficheiros mpi0102t3.* necessários à execução do 3.º trabalho prático.

os ficheiros mpi0102t2.* (+ MonadicPComb.hs) necessários à execução do 2.º trabalho prático.

os ficheiros mpi0102t1.* necessários à execução do 1.º trabalho prático.

ficheiro mpiCalFun.pdf - contendo tabela de leis de cálculo funcional - agora com leis sobre mónadas.

os seguintes módulos de extensão ao Prelude.hs do Hugs 98 que são relevantes para esta disciplina:

-

Mpi.hs - contendo as construções base da notação adoptada, e.g. ><, -|- etc.;

-

RList.hs - contendo os cata/ana/hilo-morfismos do tipo de dados listas à direita - data RList a = Nil | Cons (a, RList a) , e aplicações suas (e.g. factorial, `insertion sort', etc);

-

BTree.hs - contendo os cata/ana/hilo-morfismos 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);

-

demoBTree.hs - contendo material auxiliar para a visualização em HTML da estrutura de dados intermédia dos hilomorfismos qSort e hanoi do módulo anterior. Experimentar qSort_in_html [6,3,9,1,7,18] e hanoi_run_in_html 7, por exemplo. Encontrar-se-á a visualização no ficheiro /tmp/_.html;

-

LTree.hs - contendo os cata/ana/hilo-morfismos 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);

-

demoLTree.hs - contendo material auxiliar para a visualização em HTML da estrutura de dados intermédia dos hilomorfismos mSort, dfac e fib do módulo anterior;

-

Exp.hs - auxiliar a demoBTree.hs e demoLTree.hs;

  FAQs

Carregar aqui para obter respostas às dúvidas mais frequentes da disciplina.

  Bibliografia de Apoio

Bir98

R. Bird.
Introduction to Functional Programming Using Haskell .
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.

Ol99a

J.N. Oliveira.
An Introduction to Pointfree Programming.
37p., Departamento de Informática, Universidade do Minho, 1999.

Ol99b

J.N. Oliveira.
Recursion in the Pointfree Style.
33p., Departamento de Informática, Universidade do Minho, 1999.

Ol01a

J.N. Oliveira.
A Quick Look at Monads, 2001.
Departamento de Informática, Universidade do Minho. Chapter of book in preparation.

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

Época	Chamada	Data	Hora	Salas	Inscritos	Prova
Normal	1.ª	5.ª-feira, 17 de Janeiro 2002	09h30	2201 a 2210	162 + 48	pdf
Normal	2.ª	3.ª-feira, 5 de Fevereiro 2002	14h30	2201 a 2207	142 + 50	pdf
Recurso	-	2.ª-feira, 16 de Setembro 2002	14h30	2201 a 2204	156 + 57	pdf
	-	2.ª-feira, 18 de Novembro 2002	17h00	2306	20+3	pdf

  Notas Finais

• Omitem-se os alunos não-avaliados.
• As pautas estão ordenadas por CoDisc (código de disciplina) e Nome dos alunos.

[ Informação removida (RGPD artigo 17º) ] Voltar à página principal de MP-I. Outras disciplinas leccionadas pelo DIUM