Disciplina: Linguagens de Programação II (CK044)
Professora: Ana Teresa de Castro Martins (ana@lia.ufc.br )
Créditos: 6
Carga Horária: 90 h/a
Graduação: (UFC, 92.1, 92.2, 97.2, 98.2)

Ementa: Contexto Histórico do Paradigma Declarativo e Funcional, Interpretação Lógica e Algorítmica dos Programas Declarativos, Lambda Calculus, Recursividade, Polimorfismo, Inferência de Tipos, Prova e Transformação de Programas, Aplicações.

1. Reconhecer as características essenciais dos paradigmas declarativo e funcional e compará-las às características dos paradigmas imperativo e orientado a objetos;
2. Saber programar em PROLOG e ML para resolver problemas com característica de busca exponencial (problemas da área de Inteligência Artificial) ;
3. Ser capaz de projetar uma linguagem de programação em lógica e funcional

1. Introdução:
    1.1 Contexto Histórico: prova automática de teoremas
    1.2 Exemplo de um Programa em Lógica:
          1.2.1 Fatos Universais
          1.2.2 Regras
          1.2.3 Consultas Existenciais
    1.3 Principais características
          1.3.1 Recursividade
          1.3.2 Retrocesso
          1.3.3 Unificação
          1.3.4  Negação por Falha

2. Interpretação Lógica
   2.1 Definição da Linguagem:
         2.1.1 Alfabeto
         2.1.2 Termos
         2.1.3 Fórmulas (fórmulas atômicas)
         2.1.4 Cláusulas (cláusulas de Horn)
   2.2 Interpretação Semântica:
         2.2.1 Universo de Herbrand
         2.2.2 Interpretação
         2.2.3 Satisfação
         2.2.4 Conseqüência Semântica
   2.3 Interpretação Sintática:
         2.3.1 Substituição
         2.3.2 Unificação
         2.3 3 Resolução
         2.3.4 Conseqüência Sintática

3. Interpretação Algorítmica
    3.1 Árvore de Pesquisa:
          3.1.1 Ordem das Cláusulas
          3.1.2 Ordem dos Objetivos
    3.2 Unificação
    3.3 Terminação
    3.4 Retrocesso

4. Recursividade
    4.1 Aritmética
    4.2 Listas
    4.3 Grafos e Árvores
          4.3.1 Busca em Profundidade
          4.3.2 Busca em Amplitude
          4.3.3 Busca Best-First
    4.4 Ordenação

5. Predicados Extra-lógicos
    5.1 Controlando o Retrocesso: Cut ( ! )
    5.2 Negação por Falha: Not
    5.3 Fail
    5.4 Repeat
    5.5 Entrada / Saída
    5.6 Funções que alteram a memória
    5.7 Definição de operadores
    5.8 Sistema de Depuração em Prolog
    5.9 Melhorando a Eficiência

6. Aplicações
    6.1 Jogos
    6.2 Sistemas Especialistas
    6.3 Aprendizado de Máquina

2^a. Parte: Paradigma Funcional

1. Introdução:
    1.1 Contexto Histórico: definição de função computável
    1.2 Características Funcionais:
          1.2.1 Expressões (versus comandos)
          1.2.2 Funções
          1.2 3 Recursão
          1.2 4 Casamento de Padrões
          1.2 5 Checagem de tipos polimórficos
          1.2.6 Funções de alta ordem
          1.2 7 Estrutura de dados infinita

2. Lambda Calculus
    2.1 Definição da Linguagem:
          2.1.1 Alfabeto
          2.1.2 Expressões Lambda
    2.2 Axiomas e Regras de Inferência
    2.3 Regras de Substituição
    2.4 Estratégias de Redução: alpha, beta, eta
    2.5 Formas Normais: teoremas de Church-Rosser
    2.6 O Lambda Calculus como uma linguagem de programação
          2.6.1 Estrutura de Dados
          2.6.2 Definições Recursivas

3. ML Padrão
    3.1 Valores
    3.2 Tipos de Dados
          3.2.1 Tipos Básicos
          3.2.2 Tipos Compostos
    3.3 Avaliação lazy e por valor
    3.4 Polimorfismo: Inferência e Checagem de Tipos

4. Tipos Recursivos
    4.1 Listas
         4.1.1 funções polimórficas
         4.1.2 aritmética polimórfica
    4.2 Árvores
         4.2.1 declarações de tipos de dados
         4.2.2 exceções
         4.2.3 árvores binárias

5. Funções como valores e tipo de dados infinitos

6. Raciocinando sobre programas
    6.1 Indução Estrutural e Geral
    6.2 Especificação e Verificação

7. Tipo Abstrato de Dados e Functores

Interpretadores: Arity Prolog (para Windows 3.0) e SWI-Prolog (para Windows 5.0); Moscow ML.

Bibliografia Básica: ( paradigma declarativo)
1. Bratko, I. PROLOG, Programming for Artificial Intelligence, 2nd ed., Addison-Wesley, Harlow, 1990.
2. Sterling, L. and Shapiro, E. The Art of Prolog. Cambridge, MIT Press, 1986
3. Vidart, J. and Tasistro, A Programación Lógica y Funcional. Curitiba, III EBAI, 1988.
4. Kelly, J. The Essence of Logic. London, Prentice Hall, 1997
5. Shoham, Y. Artificial Intelligence Techniques in Prolog. San Francisco, Morgan Kaufmann, 1994.

Bibliografia Complementar: ( paradigma declarativo)
1. Chang, C. and Lee, R.C. Symbolic Logic and Mechanical Theorem Proving. New York, Academic Press, 1973.
2. Casanova, M.A et al. Programação em Lógica e a Linguagem Prolog. São Paulo, Edgard Blucher, 1987.
3. Apt, K.R. From Logic Programming to Prolog. London, Prentice Hall, 1997.
4. Rowe, N. C. Artificial Intelligence through Prolog. London, Prentice Hall, 1988.

Bibliografia Básica: ( paradigma funcional)
1. Paulson, L.C. ML for the working programmer. 2nd edition, Cambridge University Press, 1996.
2. Vidart, J. and Tasistro, A Programación Lógica y Funcional. Curitiba, III EBAI, 1988.

Bibliografia Complementar: ( paradigma funcional)
1. Barendregt, H.P. The Lambda Calculus: its syntax and semantics. North-Holland, Amsterdam, 1984
2. Bird, R. and Wadler, P. Introduction to Functional Programming. New York, Prentice Hall, 1988.
3. Harper, R. Introduction to Standard ML. Edinburgh, Computation Science Department, 1993.
4.Harper, R., Milner, R. and Tofte, M. The Definition of Standard ML (version 3). Edinburgh, Computation Science Department, 1989.
5. Thompson, S. Haskell, The Craft of Functional Programming. Harlow, Addison-Wesley, 1996.