Paradigmas de Programação

Segundo quadrimestre de 2010
Horário: 3^a (14:00-16:00) e 5^a (16:00-18:00)
Sala de aula: L502 (3^a) S502 (5^a) (não confunda L com S!)
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Prova II

Para ver a prova II, apareça na segunda que antes das 16:00.

Novidades:

24/08 -- Conceitos finais disponíveis
22/08 -- Link para pool.scm
20/08 -- Conceitos após T2 disponíveis (agora falta o trabalho II)
18/08 -- Notas de aula atualizadas (v.27)
15/08 -- Notas de aula atualizadas (v.26)
14/08 -- Notas de aula atualizadas (v.25)
13/08 -- Notas de aula atualizadas (v.24)
08/08 -- Conceitos após T1 disponíveis
08/08 -- Notas de aula atualizadas (v.23)
03/08 -- Interpretador metacircular disponível (COM suporte a fechos)
30/07 -- Notas de aula atualizadas (v.22)
30/07 -- Especificação do trabalho II/web server
29/07 -- Notas de aula atualizadas (v.21)
29/07 -- Notas de aula atualizadas (v.20)
29/07 -- Notas de aula atualizadas (v.19)
29/07 -- Web com pool de threads consertado (estava errado);
         agora também usa fechos, e o pool está separado do resto
27/07 -- Instrucoes de instalacao do Gambit e Termite atualizadas
         (faltava dizer que precisa configurar o PATH)
27/07 -- Conceitos da P1
27/07 -- Notas de aula atualizadas (v.18, somente mudanças estéticas)
26/07 -- Outro programa exemplo: servidor web com pool de threads (de brinquedo); 
         (144 linhas de Scheme, sem contar queue.scm e semaforo.scm)
25/07 -- Um programinha de exemplo para a próxima aula (http-termite)
24/07 -- Instruções de instalação para Gambit e Termite
24/07 -- Notas de aula atualizadas (v.17)
24/07 -- Descrição PRÉVIA do T2 disponível
23/07 -- T1 adiado para próxima terça 27/07
23/07 -- OpenAL funciona sim! (Mudei instruções no wiki do Chicken)
           (Faltava (require-extension al alc) antes de usar.)
22/07 -- Notas de aula atualizadas (v.16)
21/07 -- Mais programas da próxima aula disponíveis (o servidor web)
19/07 -- Notas de aula atualizadas (v.15)
16/07 -- Exemplo de prova
15/07 -- Notas de aula atualizadas (v.14)
14/07 -- Notas de aula atualizadas (v.13)
14/07 -- Tutorial sobre FFI no Chicken atualizado
14/07 -- Google Android rodando código Scheme -- feito pelo Google!
11/07 -- Notas de aula atualizadas (v.12)
10/07 -- Notas de aula atualizadas (v.11)
10/07 -- Notas de aula atualizadas (v.10)
09/07 -- Notas de aula atualizadas (v.9)
08/07 -- Versão 16 do tutorial de Emacs Lisp (não diretamente relacionado ao curso)
08/07 -- Programas da aula 10 (teórica) sobre semáforos disponíveis
04/07 -- Notas de aula atualizadas (v.8)
02/07 -- Parte dos programas da aula 09 (antes da aula!)
02/07 -- Notas de aula atualizadas (v.7)
02/07 -- Notícia: Google decide comprar ITA
29/07 -- Programas da aula 08 disponíveis
27/07 -- Quinta lista de exercícios
27/07 -- Arquivo de subsídios para T1 agora fala um pouco mais de TCP
27/07 -- Notas de aula atualizadas (v.6)
26/07 -- Quarta lista de exercícios
25/07 -- Instruções para fazer interface Scheme/C
24/07 -- Programas da aula 07 disponíveis
23/07 -- Notas de aula atualizadas (v.5)
21/07 -- Notas de aula atualizadas (v.4)
18/06 -- Programas da aula 06 (a *próxima* aula) disponíveis
18/06 -- Notas de aula atualizadas (v.3)
17/06 -- Programas da aula 05 disponíveis
17/06 -- Link para quadrinhos (XKCD), sobre Lisp
14/06 -- Notas de aula atualizadas (v.2)
14/06 -- Terceira lista revisada
12/06 -- Notas de aula (macros v.1) disponíveis
12/06 -- Notas de aula (primeira parte v.1) disponíveis!
11/06 -- Terceira lista de exercícios
11/06 -- aula04.scm revisado
10/06 -- Especificação do T1 pronta
10/06 -- Arquivo .scm com explicações e exemplos de TCP/threads/arquivos em Scheme para o trabalho
10/06 -- Programas da aula 04 disponíveis
10/06 -- aula03.scm tinha um erro em "faz-contador". Corrigido.
10/06 -- Data da P1 estava errada no site; corrigida
08/06 -- Programas da aula 02 (parte apenas) disponíveis (link notas de aula)
08/06 -- Programas da aula 03 disponíveis (no link para notas de aula)
08/06 -- Datas de provas e trabalhos definidas
02/06 -- Instruções de instalação do Chicken simplificadas. Me avisem se não funcionar!
02/06 -- Link para o unit tester do Chibi Scheme
02/06 -- Segunda lista de exercícios
28/05 -- Primeira lista de exercícios
25/05 -- Início do curso

Curiosidades e coisas relacionadas

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

• Lisp Cycles
• Lisp

A empresa americana ITA, especialista em informação sobre vôos, pode ser 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

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 Scheme, 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

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.

Veja alguns exemplo de questões de prova.

Trabalho I

Você pode escolher usar outro Scheme (recomendo Bigloo, Chibi, Guile, Gambit e Gauche -- ou SISC para quem faz questão de rodar sobre JVM) no primeiro trabalho, mas talvez eu não consiga ajudar tanto quando posso ajudar com o Chicken. (update: Chibi não, porque não tem ainda suporte a threads!)

O trabalho I é a implementação de um mundo virtual. Veja algumas coisas necessárias para fazer o trabalho.

Os programas não devem apenas "funcionar"; devem ser desenvolvidos no espírito de Programação Funcional. Algumas das coisas que vocês devem se lembrar:

• Use funções de alta ordem, mas não sem necessidade;
• Faça funções pequenas e simples. Inclua comentários no começo de cada função dizendo o que ela faz, e o que cada parâmetro significa;
• Não crie macros para usar estruturas de controle imperativas como for, while etc;
• Se houver oportunidade para usar macros e fechos, use -- mas não force seu uso;
• Evite modificar variáveis (usando set! e procedimentos que modificam seus argumentos) -- só o faça se realmente for necessário;
• Teste cada função isoladamente (se possível faça testes unitários - para algumas pode ser mais difícil se fazem conexão via rede etc). Use seu testador, feito na lista de exercícios (ou algum outro). Veja alguns testes do Chibi Scheme: o programinha de testes unitários dele é muito pequeno, mas resolve o problema.

Trabalho II

O trabalho II deve ser feito usando o Gambit Scheme.

Esta ainda NÃO é a descrição "oficial" do Trabalho II. Ainda preciso deixar arquivos com pedaços de programas para vocês usarem -- mas aí já dá para ter uma idéia de como será. Estes trabalhos não são difíceis.

O trabalho deve ser um dentre:

• Traduzir o mundo virtual do trabalho I para o Gambit (há algumas diferenças com relação ao Chicken), e mudar de threads tradicionais para o Termite Scheme. Deve haver ao menos tres atores;
• Melhorar um web server que usa o Termite Scheme. Veja a especificação do trabalho
• Implementar um simulador de autômatos celulares usando o modelo actor (partes do autômato podem ficar em máquinas diferentes);
• Faça o exercício das notas de aula, do Capítulo sobre passagem de mensagens, que pede para implementar o algoritmo de Strassen (itens b, f);
• (Para quem conhece um pouco de redes neurais) Escreva um processo usando o Termite Scheme que funcione como um neurônio. Ele deve processar as seguintes mensagens:
  • set-output, que determina para onde irá a saída
  • add-input, que adiciona mais uma entrada (o pid de um processo que poderá enviar dados)
  • process-input, que aceita um valor de uma entrada
  • erro, uma mensagem vinda do pid do processo de saída, que diz qual foi o erro e pede para ajustar os pesos
  Treine uma rede neural simples com uma coleção de neurônios como estes, usando algum conjunto de dados que você conheça. Você pode, depois, criar N nós do Termite, um em cada host, e dividir os neurônios em N grupos diferentes (basta usar migrate-proxy em grupos de processos; o resto é transparente).

Exercícios

1. Lista de exercícios 01. Para aplicar uma função fun com uma lista de argumentos args, use "(apply fun args)". Por exemplo,

         > (apply + '(1 1 2))
         4
       

   Se quiser conhecer um outro sistema de testes unitários em Scheme, veja o do Chibi Scheme naquele arquivo, da linha 5 até a 35). Ele usa macros, por isso pode ser um pouco estranho de entender por enquanto, mas a idéia é parecida com o que foi pedido no exercício.
2. Lista de exercícios 02. Para aprender rapidamente sobre o case, mencionado em um dos exercícios, este blog post pode ajudar. O site com 99 exercícios mencionado na lista é este: 99 problemas para quem está aprendendo Lisp. Alguns problemas tem um link para resposta em Common Lisp (mas faça sua versão em Scheme); não formate seu código como aquele, fechando parênteses como se fossem chaves em C/Java! Faça como temos feito em sala de aula.
3. Lista de exercícios 03. Não precisa usar make-circular no exercício 4.
4. Lista de exercícios 04.
5. Lista de exercícios 05. Na verdade implementar quote como macro não é tão fácil...

Conceitos

LEMBREM-SE: estes conceitos só mostram como vocês estão no curso até agora; o conceito final levará em conta todas as atividades e avaliações, e a evolução de cada um no curso!

   
RA        P1   após T1  após P2  após T2
11023206   C         C        C        B
11002206   B         C        C        C
11005607   B         B        B        B
11119208   B         A        B        A
11070307   C         C        F        F
11035906   B         B        B        B
11051208   A         A        A        A
11109708   F         C        C        C
11140208   C         B        C        C
11050008   F         C        B        B

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
     (FFI)
     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
     Memória Distribuída:
         Passagem de mensagens síncrona: CSP
         Passagem de mensagens assíncrona: Actor model

Datas das avaliações:

• P₁: 15/07 20/07
• P₂: 19/08
• Entrega de T₁: 22/07 27/07
• Entrega de T₂: 23/08

Bibliografia e ferramentas

Links

• Lisp-BR, o site da comunidade brasileira de Lisp (inclusive Scheme)
• schemers.org, um site onde concentram-se links para as principais fontes de informação sobre Scheme
• SRFI
• Scheme Cookbook
• Planet Scheme, um agregador de blogs

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.
• 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
• 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

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
• 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.