Paradigmas de Programação

Segundo trimestre de 2009

Horário: 4ª 16-18, 6ª 14-16

Sala de aula: L 505 (4ª) / S 503 (6ª) (bloco B) NOTEM a diferença entre "S" e "L"! *** MUDOU!!!

Sala do professor: S 805 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

SOBRE A PROVA

Estudem os conceitos que vimos em aula: fechos, escopo de variáveis, mônadas, funções de alta ordem, macros, sincronização de processos! Releiam exemplos em Haskell e Scheme, e escrevam alguns programinhas em Scheme e haskell (se bem que em Haskell eu suponho que vocês já estejam fluentes, por causa do trabalho).

Novidades:

19/09 -- Conceitos finais
15/09 -- APRESENTAÇÕES DE TRABALHO ADIADAS (PARA SEXTA!)
14/09 -- Notas da prova
10/09 -- Comentários sobre a prova
04/09 -- Entrega de trabalho adiada; cronograma atualizado
03/09 -- Link para código do banco (Haskell e Common Lisp)
21/08 -- Link para tutorial de GLUT e OpenGL em Haskell (veja em ferramentas)
19/08 -- Sugestão de ferramenta (hlint)
18/08 -- Nova versão do labirinto.hs
02/08 -- Mais um tutorial de Haskell (Learn You a Haskell for Great Good)
02/08 -- Livro (How to Design Worlds) livre adicionado na bibliografia secundária
29/07 -- Lista 9 disponível
29/07 -- Código do gerador de labirintos disponível
28/07 -- Alguém produziu um cheatsheet para Haskell (um resumão; pode ser útil). Link adicionado.
08/07 -- Um livro de Scheme agora é livre (Simply Scheme)
01/07 -- Lista 8 disponível
19/06 -- Dois novos livros na biblioteca! (Dybvig e Hudak)
16/06 -- Lista 7 disponível
16/06 -- Lista 6 disponível
16/06 -- Indicação de tutorial curto sobre Scheme (SchemeFixnum)
11/06 -- Listas de exercícios 4 e 5 disponíveis
11/06 -- MUDANÇA: laboratório na quarta, teoria na sexta
02/06 -- Lista de exercícios 3 disponível

Ementa

Visão comparativa entre os paradigmas de programação. Paradigma funcional. Paradigma concorrente

Objetivo

Esta disciplina traz à atenção do aluno as diversas diferenças fundamentais entre grandes famílias de linguagens de programação, tanto em teoria como de forma prática. Esta visão tem efeitos importantes, nem sempre imediatamente perceptíveis: ao apreciar diversas técnicas de programação e mecanismos peculiares de linguagens de programação diferentes, o estudante expande seu leque de técnicas e rompe sua rigidez de concepção a respeito do que vem a ser programar. Além disso, há situações onde um paradigma se aplicará com mais sucesso do que outro. Pode-se sem dúvida afirmar que a programação em diferentes paradigmas auxilia na melhoria da qualidade da programação de forma geral.

Espera-se que o estudante se torne capaz de programar fluentemente em pelo menos uma linguagem dentre as escolhidas para exemplificar os diferentes paradigmas; que compreenda os fundamentos teóricos de cada paradigma de programação; que passe a conhecer diferentes mecanismos de funcionamento para as diferentes características de linguagens de programação (por exemplo passagem de parâmetros, vinculação de variáveis, tratamento de exceções e avaliação estrita ou preguiçosa); finalmente, que se torne capaz de utilizar seletivamente conceitos e técnicas de diferentes paradigmas e linguagens em outros, quando for conveniente.

Dinâmica do curso (IMPORTANTE!)

O curso aborda dois assuntos: um é "conceitos de linguagens de programação" e o outro é "programação em paradigmas diferentes".

Se tentássemos cobrir a parte teórica primeiro para depois iniciar o estudo dos paradigmas, acabaríamos tendo pouco tempo para que os novos conceitos e hábitos de programação se consolidassem. Por outro lado, precisaremos da teoria logo. Assim, intercalaremos aulas teóricas sobre linguagens de programação e aulas teóricas sobre programação funcional e concorrente. Usaremos principalmente Haskell, mas não apenas.

Passarei exercícios teóricos e de programação. Estes exercícios não "valem nota", mas recomendo muito fortemente que os façam, porque afetará muito o seu desempenho nas avaliações.

Avaliação

Há três notas:

P = prova
T = trabalho
~~T₂ = trabalho 2~~

Uma nota final será composta da seguinte forma:

~~N' = (P + 1.3 T₁ + 0.7 T₂)/3~~

N' = (P + 1.5 T)/2.5

Se P ≤ 4.0 OU T ≤ 4.0, então N = min(P,T). Caso contrário, N = N'. O conceito final na disciplina será dado por:

F, se N < 5
C, se N ≥ 5
B, se N ≥ 7
A, se N ≥ 9

Possíveis trabalhos

Diff inteligente, que descreva as mudanças de forma compreensível para humanos
Partes de um jogo tipo MUD
Classificador de imagens

Uma parte do jogo (um gerador de labirintos) foi feita em aula; a versão 0.4 está aqui.

O casador de padrões da última aula está aqui.

O banco está aqui, em Haskell, em Common Lisp e em Scheme.

Exercícios

Problemas (NÃO exercícios) 13 e 16 do capítulo 1 e problemas 17 e 18 do capítulo 3 do livro do Sebesta
Faça o exercício 2 do capítulo 2 e o exercício 6 do capítulo 3 do livro Sá/Silva
Faça os exercícios 2, 4--6, 11--13, 15--18 do Sá/Silva
Entenda como definir funções em Scheme (no livro do Dybvig, se bem que já vimos em sala), e construa alguns closures
Entenda como definir funções em clojure (tem um tutorial lá). Monte alguns exemplos de chamada de função com escopo dinâmico.
Uma lista para se acostumar um pouco com Scheme:
- Traduza o programa que lê a string e a imprime "em um quadro", que fizemos no laboratório, para Scheme. Use o tutorial SchemeFixnum, e se precisar o livro do Dybvig para tirar dúvidas quanto a funções para manipular strings.
- Implemente uma função que cacule a média de um vetor em Scheme (para qualquer tamanho de vetor). A função deve estar em umaclosure que se lembra do tamanho médio dos vetores passados para ela; dentro da mesma closure deve haver uma outra função que retorna a média do tamanho dos vetores.
Implemente em Haskell um jogo de vinte-e-um (também conhecido como Blackjack). O computador é a banca, e ai dando pares de cartas: um para o usuário, e um para si, até que alguém estoure ou o usuário diga que quer parar. Não precisa implementar todas as regras do jogo; é apenas um exercício de programação. :-)
Dicas:
- Guarde as cartas dos dois em listas. A cada jogada, as duas mãos (do jogador e da banca) recebem mais uma carta. Basta encaixar um novo elemento na lista: (novacarta : maodojogador)
- Use foldl para calcular quanto vale cada mão. Você terá que implementar uma função que dá o valor de cada carta, e fazer algo como "foldl valorcarta 0 mao", onde "valorcarta" é a função que dá o valor de cada carta.
- Faça pequenos pedaços do programa de cada vez. Sugestão: primeiro determinar como representar as cartas, depois a função que dá valor a elas, depois uma que sorteie uma carta do baralho, depois a lógica do jogo.
Faça os exercícios do capítulo 3 do "Real World Haskell"
Pegue o programa que monta labirintos e desenhe um grafo mostrando que funções chamam outras, e identifique no grafo as funções puras e impuras. Como comentei em aula, teria sido melhor se o gerador de números aleatóreos fosse inicializado na função main. O que mudaria se isso fosse feito? Tente implementar a mudança
Altere o programa que simula o banco:
- Implemente verificação por senha: primeiro um usuário loga em sua conta, depois realiza operações
- Implemente comunicação inter-bancos. Cada conta passará a ter um número de banco mais um número de conta, e um cliente pode transferir dinheiro de sua conta para a de alguém em outro banco.

Notas

   
          prova   trabalho     N  conceito
-------------------------------------------
Claudio     4.0        0.0   0.0         F
Fernando    9.5        9.5   9.5         A
Pierre      1.5        0.0   0.0         F
-------------------------------------------

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Candidatos a aulas reserva (se não forem usadas para repor aulas perdidas ou por algum outro motivo). Os itens marcados com (*) são os que eu acho mais interessantes:

Mais aulas de Lisp
(*) Programação concorrente usando Erlang (ou Termite e Scheme)
Prova de corretude de programas
(*) Programação Orientada a Aspectos
(*) Programação Orientada a Objetos usando Smalltalk ou CLOS
Programação baseada em Propagação de Restrições

Bibliografia e ferramentas

Ferramentas

IMPORTANTE: eu recomendo fortemente que vocês façam os trabalhos com as implementações abaixo, usando Linux. Se não fizerem, pelo menos testem periodicamente nestas implementações e em Linux, porque é o que eu usarei para avaliar os trabalhos.

Compilador/interpretador/ambiente Haskell, GHC. A respeito de Haskell (inclusive outras implmentações) veja http://haskell.org/.

O hlint dá sugestões de melhoria de código em Haskell. Ele gerará warnings quando encontrar nomes de variáveis "como_este" e não comoEste, mas você pode suprimir estes erros com "hlint -i "use camelCase" programa.hs".

Ambiente Common Lisp, SBCL. Há outras implementações boas; veja um survey de implementações de Dan Weinreb. Outros sites sobre Common Lisp incluem o da Associação de Usuários de Lisp (não tão interessante), o CLiki, o Common Lisp Directory, o agregador de blogs Planet Lisp e o lusófono Lisp-BR.
Interpretador ou compilador Scheme. Sugiro o Guile ou o PLT Scheme, mas há vários outros. Vale a pena dar uma olhada em schemers.org para entender um pouco melhor o mundo do Scheme e suas múltiplas implementações.
CHP, "Communicating Haskell Processes"
Alguém escreveu um tutorial sobre gráficos em openGL e GLUT, usando Haskell:
parte I
parte II

Bibliografia Principal

Tucker/Noonan Tucker & Noonan. "Linguagens de Programação" McGraw-Hill, 2009.
Sebesta Sebesta, R. W. "Conceitos de Linguagens de Programação" Bookman, 2003.
Melo Melo, A. C. V.; Soares, F. C. S. "Princípios de Linguagens de Programação". Thomson, 2003.
World O'Sullivan, B.; Goerzen, J.; Stewart, D. "Real World Haskell" O'Reilly, 2008. Ótima introdução ao Haskell; os exemplos são aplicações práticas e úteis de verdade. Disponível na web.
Seibel Seibel, P. "Practical Common Lisp" Excelente introdução à linguagem Common Lisp. Disponível online.
Dybvig Dybvig, K. "The Scheme Programming Language" MIT Press, 2003. Excelente introdução ao Scheme; também disponível em HTML.
SchemeFixnum Sitaram, D. "Teach Yourself Scheme in Fixnum Days" Introdução curta ao Scheme. Também em PDF
Newbern "All about monads" -- um excelente tutorial sobre mônadas.

Secundária

Haskell Cheatsheet
Learn You a Haskell for Great Good!, mais um tutorial de Haskell
How to Design Worlds, um livro muito interessante usando Scheme!
Hindley Hindley, J. R.; Seldin,J. P. "Lambda-Calculus and Combinators: An Introduction" Cambridge University Press, 2ed, 2008.
Sa Sá, C. S.; Silva, M. F. "Haskell: uma abordagem prática" Novatec, 2006. Para quem precisar de algum livro em Português sobre Haskell.
YAHT Daumé III, H. Yet Another Haskell Tutorial Um tutorial sobre Haskell; muito bem escrito.
Road Doets, K.; Eijck, J. "The Haskell Road to Logic, Maths and Programming" College Publications, 2004. Excelente livro; programação Haskell através de Matemática
SICP Abelman, H.; Sussman, G. J. "Structure and Interpretation of Computer Programs" MIT Press. Um excelente livro, usado em um curso introdutódio no MIT por muitos anos (deixou de ser usado no ano passado, mas não por qualquer problema com o livro ou a abordagem). O livro usa Scheme para ensinar muita coisa importante sobre programação. Este também pode ser lido em HTML
Felleisen Felleisen, M.; Findler, R. B.; Flatt, M.; Krishnamurti, S. "How to design programs" MIT Press, 2001. Também ensina a programar usando Scheme. Tem na biblioteca, mas também pode ser lido online
Roscoe Roscoe, A. W. "The Theory and Practice of Concurrency" Para quem quiser entrar de verdade na teoria de programação conorrente... Disponível na página do autor
CSP Hoare, T. "Communicating Sequential Processes" Um dos mais importantes trabalhos em programação concorente. Disponível aqui
Armstrong Armstrong, J. "Programming Erlang: Software for a Concurrent World" O'Reilly, 2007.
Pragmatics Scott, M. "Programming Language Pragmatics" Morgan Kaufmann, 2ed, 2005. Este é um livro que cobre muita coisa, para quem se interessar em procurar algo mais sobre linguagens.
OnLisp Graham, P. "On Lisp" Um livro quase apenas sobre metaprogramação em Common Lisp. Pegue no site do Paul Graham
Simply Harvey, B.; Wright, M. Simply Scheme: Introducing Computer Science MIT, 1999. Disponível online
ANSI Graham, P. "ANSI Common Lisp" Um livro muito bom sobre Common Lisp.
CLtL2 Steele Jr, G. Common Lisp: the language SEGUNDA edição. Uma referência excelente para todo tipo de dúvida a respeito de detalhes de Common Lisp. Não é um tutorial. (Adivinhem:) também está disponível online... Existe também uma página que explica as poucas diferenças entre a descrição deste livro e a versão final do padrão ANSI -- aqui!
CARM Harbison, S. P.; Steele, G. L. C: manual de referência Pode ser útil para quem quiser fazer interface Haskell/C (ou qualquer linguagem com C). Esta é a melhor referência que existe sobre a linguagem C (notem que eu disse referência, e não tutorial). Tem na biblioteca.

Outras coisas importantes

Termite Computação distribuída com Scheme. Lembra muito Erlang, mas tem coisas que Erlang não oferece (por exemplo, migração de processos) Muito interessante!
Keene Keene, S."Object-Oriented Programming in Common Lisp: a programmer's guide to CLOS" CLOS é o sistema de objetos da linguagem Common Lisp. Este livro mostra como CLOS é muito mais flexível e menos burocrático do que seus equivalentes de Java e C++. Recomendo para quem quer entender de verdade Orientação a Objetos.
MOP Kiczales, G.; De Rivieres, J.; Bobrow, D. G. "The art of the metaobject protocol" Como se não bastasse a flexibilidade do sistema de objetos de Common Lisp, há um protocolo de metaobjetos. Só leia este livro se já estiver familiarizado com CLOS.
Brodie Brodie, L. "Thinking Forth" Eu dificilmente recomendaria a linguagem Forth para qualquer projeto prático, mas ela pode ser útil para tornar mais abrangente sua visão do mundo da programação (sim, Chuck Moore está vivo e trabalhando! E ele ainda trabalha com Forth)
Lewis Lewis, S. "The Art and Science of Smalltalk" Smalltalk é completamente diferente do que você já tenha visto. Programação orientada a objetos pura, sem absolutamente nada de imperativo! Vale a pena também como um "eye-opener" (aliás, quem gosta de Ruby deveria conhecer um pouco de Smalltalk...)
Budd Budd, T. "A Little Smalltalk" Um livro genial. Tim Budd mostra o desenvolvimento de um mini-Smalltalk. Pode ajudar a entender de verdade orientação a objetos.
ML Paulson, L. "ML for the Working Programmer" Cambridge University Press, 2ed, 1996. para quem quiser aprender uma outra linguagem funcional, com uma filosofia diferente de Haskell.
OCaml Hickey, J. "An Introduction to Objective Caml". Este é Jason Hickey, e ele deixará o livro disponível em sua página até a eventual publicação por uma editora. Aproveitem, porque quase não há bons livros de OCaml!
Gordon Gordon, M. "Introduction to Functional Programming" Um tutorial razoável. Aborda inicialmente o λ-cálculo, depois passa para a linguagem ML. Esta segunda parte dá uma noção rápida de como funciona ML (para uma olhada rápida, se você não tem tempo de ler o livro do Paulson). Pegue na página do Mike Gordon, onde há também links para outros tutoriais de programação funcional.