Paradigmas de Programação

Terceiro quadrimestre de 2010
Horário: 2^a (19:00-21:00) e 5^a (21:00-23:00)
Sala de aula: 306 (2^a) e L502 (5^a)
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Monitoria

A monitoria foi cancelada

Novidades:

21/12 -- Nova versão das notas de aula (v.109)
20/12 -- Nova versão das notas de aula (v.108)
19/12 -- Conceitos após o trabalho 2
15/12 -- Nova versão das notas de aula (v.107)
14/12 -- Conceitos após a prova 2
13/12 -- Nova versão das notas de aula (v.106)
12/12 -- Nova versão das notas de aula (v.105)
12/12 -- Nova versão das notas de aula (v.104)
11/12 -- Mais um exemplo de questão de prova (junto com as notas de aula)
04/12 -- Nova versão das notas de aula (v.103)
03/12 -- syn.scm e stm.scm disponíveis
02/12 -- Nova versão das notas de aula (v.102)
01/12 -- Vencedor do Google AI Challenge 2010: um programa Common Lisp!
30/11 -- Nova versão das notas de aula (v.101)
29/11 -- Nova versão das notas de aula (v.100)
29/11 -- Tres livros incluídos na bibliografia (havia esquecido: Andres, Lea e Bloch)
25/11 -- Nova versão das notas de aula (v.99)
25/11 -- Conceitos após o trabalho 1
24/11 -- Nova versão das notas de aula (v.98)
23/11 -- Código do pool de threads e servidor HTTP disponíveis
23/11 -- Nova versão das notas de aula (v.97)
21/11 -- Nova versão das notas de aula (v.96)
20/11 -- Nova versão das notas de aula (v.95)
18/11 -- Nova versão das notas de aula (v.94)
16/11 -- Nova versão das notas de aula (v.93)
15/11 -- Nova versão das notas de aula (v.92)
15/11 -- Nova versão das notas de aula (v.91)
14/11 -- Nova versão das notas de aula (v.90)
11/11 -- Entrega da T1 adiada para 18/nov
10/11 -- Aula de 11/11 cancelada
10/11 -- Monitoria cancelada
08/11 -- Nova versão das notas de aula (v.89)
07/11 -- Nova versão das notas de aula (v.88)
07/11 -- Nova versão das notas de aula (v.87)
06/11 -- Nova versão das notas de aula (v.86)
05/11 -- Conceitos após a P1 disponíveis
05/11 -- Nova versão das notas de aula (v.85)
28/10 -- Nova versão das notas de aula (v.84)
27/10 -- Nova versão das notas de aula (v.83)
26/10 -- Nova versão do tutorial de FFI do Chicken (v.0.0004)
23/10 -- Nova versão das notas de aula (v.82)
21/10 -- Nova versão das notas de aula (v.81)
20/10 -- Nova versão das notas de aula (v.80)
20/10 -- Nova versão das notas de aula (v.79)
20/10 -- metacircular.scm disponível
19/10 -- aula-macros.scm disponível
19/10 -- Nova versão das notas de aula (v.78)
19/10 -- Subsídios para T1: como usar threads e ouvir em portas TCP 
         (no link das notas de aula)
19/10 -- Exemplo de prova disponível
18/10 -- Nova versão das notas de aula (v.77)
18/10 -- aula-continuacoes.scm disponível
17/10 -- aula-estado.scm disponível
16/10 -- Nova versão das notas de aula (v.76)
15/10 -- Nova versão das notas de aula (v.75)
14/10 -- Nova versão das notas de aula (v.74)
12/10 -- Alguns dos programas usados nas aulas estão disponíveis
11/10 -- Nova versão das notas de aula (v.73)
09/10 -- Nova versão das notas de aula (v.72)
08/10 -- Nova versão das notas de aula (v.71)
07/10 -- Descrições dos trabalhos
05/10 -- Horário de monitoria
03/10 -- Nova versão das notas de aula (v.70)
02/10 -- Nova versão das notas de aula (v.69)
29/09 -- Nova versão das notas de aula (v.68)
28/09 -- Nova versão das notas de aula (v.67)
27/09 -- Nova versão das notas de aula (v.66)
25/09 -- Nova versão das notas de aula (v.65)
25/09 -- Nova versão das notas de aula (v.64)
24/09 -- Nova versão das notas de aula (v.63)
23/09 -- Datas de provas e trabalhos marcadas
23/09 -- Nova versão das notas de aula (v.62)
23/09 -- Nova versão das notas de aula (v.61)
23/09 -- Nova versão das notas de aula (v.60)
22/09 -- Nova versão das notas de aula (v.59)
22/09 -- Nova versão das notas de aula (v.58)
21/09 -- Nova versão das notas de aula (v.57)
21/09 -- Nova versão das notas de aula (v.56)
21/09 -- Nova versão das notas de aula (v.55)
20/09 -- Nova versão das notas de aula (v.54)
20/09 -- Nova versão das notas de aula (v.53)
20/09 -- Nova versão das notas de aula (v.52)
19/09 -- Nova versão das notas de aula (v.51)
19/09 -- Nova versão das notas de aula (v.50)
18/09 -- Nova versão das notas de aula (v.49)
18/09 -- Nova versão das notas de aula (v.48)
18/09 -- Nova versão das notas de aula (v.47)
18/09 -- Nova versão das notas de aula (v.46)
17/09 -- Nova versão das notas de aula (v.45)
17/09 -- Nova versão das notas de aula (v.44)
17/09 -- Figuras do tutorial do Eclipse consertadas
17/09 -- Nova versão das notas de aula (v.43)
16/09 -- Nova versão das notas de aula (v.42)
16/09 -- Nova versão das notas de aula (v.41)
16/09 -- Pequenas modificações no tutorial de interface Scheme/C
16/09 -- Atualização nas instruções de instalação do Chicken para Windows
15/09 -- Nova versão das notas de aula (v.40)
14/09 -- Nova versão das notas de aula (v.39)
14/09 -- Nova versão das notas de aula (v.38)

Notas de aula

Não deixe de verificar periodicamente as notas de aula!

Curiosidades e coisas relacionadas

Estes quadrinhos dão uma idéia de como programadores Lisp vêem sua linguagem:

O vencedor do desafio de IA do Google em 2010 é Gábor Melis, com um programa feito em Common Lisp. Veja o ranking!

A empresa americana ITA, especialista em informação sobre vôos, foi adquirida pelo Google. A ITA mantém um sistema grande e complexo escrito em Common Lisp; é um exemplo de história de sucesso de uma empresa que se manteve fora da "monocultura Java".

O App Inventor para o Android tem código Scheme! (Kawa):

"The compiler that translates the visual blocks language for implementation on Android uses the Kawa Language Framework and Kawa's dialect of the Scheme programming language, developed by Per Bothner and distributed as part of the Gnu Operating System by the Free Software Foundation."

Ementa

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

Objetivo

Queremos que o aluno construa uma compreensão das linguagens de programação a partir de suas diferentes características e da maneira como estas características interagem.

O curso deverá trazer à 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 nas linguagens 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); que se torne capaz de utilizar seletivamente conceitos e técnicas de diferentes paradigmas e linguagens em outros, quando for conveniente; e finalmente, que comreenda minimamente como linguagens de programação são projetadas, capacitando-se a desenvolver de maneira coerente e eficaz linguagens de domínio limitado.

Avaliação

O conceito final da disciplina poderá ser:

F - Reprovado. O aluno deve cursar novamente a disciplina.
C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

A avaliação ser composta de:

Duas provas, P₁ e P₂;
Dois trabalhos, T₁ e T₂.

A avaliação final de cada aluno não será o resultado de alguma "conta" feita a partir dos valores das três avaliações. O resultado de cada avaliação reflete o desempenho do aluno em todo o curso até aquele instante, e não é apenas uma "nota isolada". Isso significa que cada avaliação leva em conta também o resultado das avaliações anteriores. De maneira simples, cada avaliação mostra qual seria o conceito final do aluno se o curso terminasse naquele instante.

Não há "prova substitutiva", porque tal conceito não faz sentido no sistema de avaliação descrito acima.

Trabalho I

As descrições dos trabalhos estão aqui:

Trabalho II

Conceitos

A coluna T1? indica se o trabalho 1 foi entregue (um "X" significa atraso, um "*" significa entregue no prazo).

RA        após P1  T1?  após T1  após P2  após T2
-------------------------------------------
11102108        C   X         F		F   F
11033909        A   *	      B		A   A
11078407        F
11014007
11037708        C   *         B		B   C
11026006        
11014507
11076508        F
11043008        F   *         C		F   F
11068807        F
11103908        C   *         B		B   C
11105408        F   *         C	
11106808        B
11031807        F
11056408        F
11079208        B   *         C		F   C
11114808        F   *         F		F   F
11022409        A   *         B		B   A
11090608
-------------------------------------------

Programa aproximado

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

 I - PROGRAMAÇÃO FUNCIONAL EM SCHEME
     Elementos básicos de Scheme
     Procedimentos
     Variáveis: ambientes, extensão e escopo
     Sistemas de tipos (estático/dinâmico; seguro/inseguro)
     Listas e vetores
     Fechos
     (POO com fechos)
     Metaprogramação
     Avaliação preguiçosa
     Streams (aplicação de av. preguiçosa)
     Continuações
     Aplicações de continuações: escape, multitarefa, backtracking, exceções
     Modelos de gerenciamento de memória; coleta de lixo
II - PROGRAMAÇÃO CONCORRENTE
     Processos, threads e formas de concorrência
     Problemas inerentes à programação concorrente
     Memória compartilhada:
         Semáforos
         Monitores
         Memória Transacional
     Passagem de mensagens:
         Passagem de mensagens síncrona e assíncrona

Datas das avaliações:

P₁: 04/11
P₂: 13/12
Entrega de T₁: 12/11
Entrega de T₂: 16/12

Bibliografia e ferramentas

Ferramentas

Usaremos no curso

Interpretador ou compilador Scheme. Usaremos o Chicken Scheme. O Chicken roda em várias plataformas, inclusive Linux, MacOS, *BSD e Windows.
Veja como instalá-lo em seu computador pessoal, e veja também no site do Chicken o manual e a documentação das extensões (aliás, tem um Wiki lá).
No final do curso, usaremos o Gambit e o Termite. Veja instruções de instalação
Ambiente de desenvolvimento: pode-se usar duas combinações:
Emacs+Quack:
- Emacs, que sem dúvida já está empacotado para a sua distribuição Linux. O Emacs também funciona muito bem no Windows; pegue o binário para Windows aqui. Há muitas informações no Emacs Wiki -- em particular, na seção em Português há um texto para iniciantes.
  Se quiser aprender um pouco de Emacs Lisp, estou fazendo um tutorial em Portugues (ainda em andamento -- está incompleto!).
- Quack, um ambiente de rogramação Scheme para o Emacs
- Veja como configurá-los em seu computador pessoal
Eclipse+SchemeWay:
- Eclipse
- Schemeway (plugin Eclipse para desenvolvimento Scheme)
- Veja como configurá-los em seu computador pessoal
Ambas as escolhas (Emacs+Quack ou Eclipse+SchemeWay) funcionam bem tanto no Linux como no Windows.

Interessante, mas não essencial para o curso

Há algumas implementações de Scheme muito pequenas. Por exemplo, o TinyScheme é um interpretador Scheme (R⁵RS, mas as macros não são padrão, e são não-higiênicas) feito em 4500 linhas de C (mais umas 450 de Scheme). O binário ocupa 139k em disco (e a biblioteca 155k). Para levar e compilar onde for necessário.
O Scheme 9 from Empty Space é outra implementação bastante pequena, que pode inclusive ser usada no seu roteador sem fio!
Distel é um pacote que traz idéias do actor model (mais exatamente de Erlang) para o Emacs Lisp, e permite a integração de código elisp com Erlang.
Tehila é um 3d engine escrito para o Chicken Scheme. Ainda está em fase inicial, mas já é possível rodar alguns exemplos (é interessante para aprender a usar OpenGL em Scheme).
O Schemix (o fonte fica no Savannah, no CVS) era um interpretador Scheme que funcionava dentro do kernel do Linux:
```
$ echo "(+ 1 2 3)" > /dev/schemix
$ cat /dev/schemix
6
```
Infelizmente, o desenvolvimento foi descontinuado.

Bibliografia Principal

NotasDeAula Notas de aula ⇐ IMPORTANTE! (Serão atualizadas periodicamente)
Sebesta Sebesta, R. W. "Conceitos de Linguagens de Programação" Bookman, 2003.
Andrews Andrews, G. "Foundations of Multithreaded, Parallel, and Distributed Programming" Addison Wesley, 2000.
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
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
Lea Lea, Doug. Concurrent Programming in Java™: Design Principles and Patterns, Second Edition Addison-Wesley, 1999
Bloch Bloch, J. Effective Java Addison-Wesley, 2008. (Vejam a parte sobre Concorrência)

Secundária

A bibliografia secundária contém obras que, embora relacionadas ao curso, não são diretamente usadas (ou são de difícil obtenção).

Tucker/Noonan Tucker & Noonan. "Linguagens de Programação" McGraw-Hill, 2009.
Melo Melo, A. C. V.; Soares, F. C. S. "Princípios de Linguagens de Programação". Thomson, 2003.
Seibel Seibel, P. "Practical Common Lisp" Excelente introdução à linguagem Common Lisp. Disponível online.
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.
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
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.
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.
Semaphores Allen B. Downey The Litle Book of Semaphores: The Ins and Outs of Concurrency Control and Common Mistakes Disponível online
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
CARM Harbison, S. P.; Steele, G. L. C: manual de referência Pode ser útil para quem quiser fazer interface Scheme/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

Aqui há outras coisas para quem se interessar (incluem-se aqui outros paradigmas, e não apenas o funcional).

Haskell Cheatsheet
Learn You a Haskell for Great Good!, mais um tutorial de Haskell
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.
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!
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.