 |
Cálculo de Programas - 2007/08
|
|
[ DI/UM ]
|
|---|
-
- 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
relativa a
um prático trabalho obrigatório a realizar por grupos de 2 alunos.
- Fórmula de avaliação:
a nota final nf será dada pela fórmula:
-
nf = p * 0.3 + t * 0.7
sujeita à condição:
- t >= 8.0
- Em qualquer altura: via correio electrónico pressionando aqui.
- Sujeito a marcação verbal pelo docente respectivo,
com um mínimo de uma semana de antecedência:
-
- 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.
Caso de estudo: algoritmos de ordenação.
-
Regras para codificação de estruturas de dados funcionais na
linguagem de programação C.
- 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.
- 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.
- 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.
- 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.
- Á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).
- 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.
- 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').
- 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.
- 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».
- 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.
- O enunciado do Trabalho Prático está disponível no
Material Pedagógico.
Quaisquer dúvidas ou dificuldades que surjam na utilização dos ficheiros disponibilizados
deverão ser comunicadas à equipa docente clicando aqui.
- O sistema para submissão do trabalho prático está on-line em
- nirvana.di.uminho.pt/labdotnet/Submit_LCC_CP_0708
Os alunos devem registar os respectivos grupos logo que possível,
e podem submeter versões provisórias do trabalho.
A data limite para a submissão da versão final é 4 de Julho.
- 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.
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
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.
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.
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.
- Em ficheiro zip
encontram-se,
até à data desta versão [2008.06.25] os ficheiros/directorias:
- ficheiro cpCalFun.pdf -
contendo tabela de leis de cálculo funcional (actualizado).
- 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.
- cp0708t*.* - ficheiros relevantes para a realização do trabalho prático
da disciplina (incluindo manual do xypic).
- 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.
- 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 -
apresentando a manipulação de listas do Haskell sob a forma de
catamorfismos.
- ficheiro Nat.hs -
apresentando 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.;
- ficheiro msdn02.pdf - contendo acetatos mostrados nas primeiras aulas.
- 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.
- 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 do exame da época especial:
- 23180 = R ;
38584 = F ;
41021 = 12 ;
43545 = F ;
47420 = 12
- Classificações à data da época de recurso:
- 23139 = F ; 23180 = D ; 30481 = R ; 30712 = F ; 30726 = F ; 30746 = R ; 30755 = R ; 31195 = R ; 33691 = F ; 33694 = F ; 33712 = F ; 35782 = 13 ; 35804 = F ; 35820 = F ; 35831 = F ; 35842 = 12 ; 35857 = F ; 36867 = F ; 38584 = R ; 38603 = F ; 39293 = F ; 39431 = F ; 41021 = R ; 41041 = F ; 42198 = R ; 42211 = F ; 43502 = F ; 43510 = 10 ; 43511 = F ; 43520 = F ; 43533 = F ; 43534 = F ; 43544 = 10 ; 43545 = F ; 44633 = R ; 46222 = R ; 47403 = F ; 47408 = F ; 47410 = F ; 47411 = 10 ; 47414 = 12 ; 47415 = F ; 47418 = 11 ; 47420 = R ; 47422 = F ; 47424 = F ; 47425 = F ; 47429 = F ; 48392 = R ; 48401 = F ; 48405 = 10 ; 48406 = R ; 48418 = F ; 50187 = F ; 50188 = D ; 50189 = 20 ; 50190 = F ; 50195 = F ; 50197 = F ; 50199 = F ; 50200 = D ; 50202 = F ; 50204 = F ; 50206 = 10 ; 51147 = F ; 51155 = F ; 51157 = F ; 51164 = F ; 51166 = F ; 51176 = F
Voltar à página principal de CP.
- Outras disciplinas
leccionadas pelo DIUM
J. Nuno Oliveira
2009-02-16