Paradigmas de Programação

Terceiro quadrimestre de 2012
Horários:

• Turma A1 noturno: 2^a (19:00-21:00) e 5^a (21:00-23:00)
• Turma A1 matutino: 2^a (08:00-10:00) e 4^a (10:00-12:00)

CONFIRA SEU CONCEITO

Veja se seu conceito está faltando no site!

Vista de prova

Para a turma do noturno, a vista de prova será hoje, no horário da aula, junto com a entrega do trabalho. As notas serão divulgadas no máximo hoje à tarde.

O pessoal do diurno pode ver a prova na sexta das 14 às 15.

Novidades:

10/04 -- Conceitos que estavam faltando já estão no site. CONFIRA se seu conceito está lá!
05/04 -- Conceitos após T. Se seu conceito está faltando me mande um email
04/04 -- Conceitos após P2 no site
04/04 -- Noturno: vista de prova (P2) HOJE!
26/03 -- Conceitos após P1
23/03 -- Prova II hipotética no site
22/03 -- Tópicos para P2 atualizados
05/02 -- Vários grupos (para o trabalho) adicionados à lista
28/02 -- Mais código para usar no trabalho
27/02 -- Código útil para fazer os trabalhos disponível (será atualizado com mais código depois...)
26/02 -- Grupos para o trabalho prático agora listados no site
19/02 -- Nova versão (131) das notas de aula
17/02 -- Seleção de tópicos das notas para leitura disponível
15/02 -- Nova versão (130) das notas de aula
07/02 -- Trabalho prático com descrições detalhadas
06/02 -- Nova versão (129) das notas de aula
05/02 -- Lista de tópicos para trabalho prático no site
29/01 -- Nova versão (128) das notas de aula
29/01 -- Instruções para instalar Emacs+Quack atualizadas [ NOVAMENTE INSTUÇÕES PARA WINDOWS! ]
25/01 -- Incluída data da prova da turma noturna
23/01 -- Instruções para instalar Emacs+Quack atualizadas
23/01 -- Data da prova definida para turma matutina
22/01 -- Nova versão (127) das notas de aula
18/01 -- Nova versão (126) das notas de aula disponível

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:

• Lisp Cycles
• Lisp

Ementa

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

Objetivo

Tradicionalmente, cursos de Ciência da Computação incluem uma disciplina obrigatória onde linguagens e suas características são comparadas. O objetivo nesse tipo de curso é construir 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.

Neste curso a abordagem terá forte componente prática: os conceitos serão exemplificados e construídos em uma linguagem de programação -- construiremos, a partir de um mínimo, diversas características de diferentes linguagens. Isto deverá dar ao aluno a experiência da programação em diversos paradigmas, além da prática da construção de diferentes funcionalidades e mecanismos para linguagens.

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
• Um trabalho prático, possivelmente entregue em partes

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.

Prova hipotética

Trabalho prático

Veja a lista de possíveis trabalhos.

Os grupos estão aqui.

Há código Scheme disponível para fazer o trabalho. Somente o xml.scm não tem documentação no próprio arquivo, mas você pode ver como usá-lo nas notas de aula (procure nas notas o gerador de XML e o gerador de SVG).

Conceitos

Aqui

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
     Programação em Lógica
     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
         Thread pools
     Passagem de mensagens:
         Passagem de mensagens síncrona e assíncrona

Datas das avaliações:

• P₁: [ matutino: 06/03 ... noturno: 07/03 ]
• P₂: [ matutino: 27/03 ... noturno: 28/03 ]
• Entrega do trabalho:

Bibliografia e ferramentas

Seleção de tópicos das notas de aula

Aqui há uma seleção dos tópicos importantes

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 decorrer do curso poderemos também usar o Gambit e algumas outras implementações (veja uma lista delas. As implementações Chibi, Guile, Gauche, SISC e Tinyscheme poderão nos interessar.. Veja instruções de instalação do Gambit.
• 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 -- não é o que uso -- posso não conseguir ajudar:
  • Eclipse
  • Schemeway (plugin Eclipse para desenvolvimento Scheme)
  • Veja como configurá-los em seu computador pessoal
  Ambas as escolhas (Emacs+Quack ou Eclipse+SchemeWay) funcionam tanto em Linux como em 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)
• 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.
• 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).

• Sebesta Sebesta, R. W. "Conceitos de Linguagens de Programação" Bookman, 2003.
• SchemeFixnum Sitaram, D. "Teach Yourself Scheme in Fixnum Days" Introdução curta ao Scheme. Também em PDF
• 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.