Informações
• Linguagens de Programação 2
Programação Funcional
Sérgio Soares
[email protected]
– Paradigma de Programação Funcional
•
•
•
•
Carga Horária: 60h
Horário: 2as e 6as das 10h30 as 12h10
Local: 2as no LIP4 e 6as no LIP1
Grupo
– http://groups.yahoo.com/group/lp2_poli
O que é Programação Funcional?
• Programação com alto nível de abstração
• Soluções elegantes, concisas e poderosas
• Funções: computam um resultado que
depende apenas dos valores das entradas
• Forte fundamentação teórica, o que permite
mais facilmente provas de propriedades
sobre os programas
Conceitos importantes
•
•
•
•
•
Sistema de tipos fortes
Uso extensivo de recursão
Polimorfismo e funções de alta ordem
Tipos de dados algébricos
Coleta de lixo (Garbage Collection)
Por que um curso de
programação funcional?
• Dá uma visão clara de conceitos
fundamentais da computação moderna:
– abstração (em uma função)
– abstração de dados (tipos abstratos de dados)
– genericidade, polimorfismo, overloading
Objetivos da programação
funcional
• Programação com um alto nível de
abstração, possibilitando:
– alta produtividade
– programas mais concisos
– programas mais fáceis de entender
– menos erros
– provas de propriedades sobre programas
Uso prático
• Programas com milhares de linhas de código:
compiladores, provadores de teoremas etc.
• Ericsson utiliza Erlang, uma linguagem
funcional concorrente, para programação de
switches de redes/telecomunicações, com
excelentes resultados.
• Possibilidade de integração com partes de
programas escritos em outras linguagens.
O curso
• A ênfase do curso é em conceitos
• Uso de Haskell
– Haskell é um ferramenta prática de apoio, mas
não o objetivo central
Ambiente a ser utilizado no curso
• Linguagem de programação: Haskell
• Interpretador Hugs: disponível para Windows
e Unix, gratuito
• Compilador GHC também está disponível
gratuitamente para Windows e Unix
Bibliografia
• Livro adotado:
– Haskell – The Craft of Functional Programming.
Simon Thompson. Addison-Wesley, 1996.
– http://www.uck.ac.uk/computer_science/Haskell_craft/
• Referências auxiliares
– Introduction to functional programming. R. Bird
and P. Wadler. Prentice Hall, 1988.
– http://www.lpac.ac.uk/SEL-HPC/Articles/FuncArchive.html
– http://www.haskell.org
Avaliação
• 2 exames escritos cobrindo o conteúdo da matéria
Histórico
Máquina
de Turing
Linguagens de
programação
imperativa
Lambda
Cálculo
Linguagens de
programação
funcional
• ??????? Seminário ??????????
• Trabalho de Implementação
• Exame final com toda a matéria
Histórico
• Anos 70
– Linguagens funcionais foram vistas como uma
forma de transpor a "crise de software", onde
grandes projetos de software falhavam porque
as ferramentas de programação eram
impróprias para estes objetivos específicos.
– “Can Programming Be Liberated From the
Von Neumann Style ? A Functional Style and
Its Algebra of Programs”, John Backus, 1978
CACM Turing Award Lecture
Programação Funcional
• Leva essa idéia ao extremo
– Sua sintaxe encoraja uma visão totalmente
modular do fluxo do programa
– Reutilização do código previamente escrito
(funções) para construir programas cada vez mais
complexos
– Geralmente não há um identificador (por exemplo
a função main( ) de C e Java) para indicar o ponto
onde a execução do programa inicia
Programação Funcional
• Todos os subprogramas são vistos como
funções
– Eles recebem argumentos e retornam soluções
simples.
– Relação explícita e precisa entre E/S
– A solução retornada é baseada inteiramente na
entrada
– O tempo em que uma função é chamada é
irrelevante
Programação Funcional
• Baseia-se na idéia de calcular
– Define-se as funções a serem usadas e o
processador para a linguagem calculará o valor
das expressões que usam estas funções
– Um programa funcional (ou script em Haskell)
consiste de um conjunto de definições de
funções/valores e uma expressão a ser
processada
Modelo Computacional
Mapeamento (função) de valores de entrada em valores
de saída
Entrada
Programa
Saída
Ausência de estado e comandos (atribuição + controle)
Relação clara e explícita entre entrada e saída
Características Gerais
• Estilo declarativo
– Não há o conceito de estado nem comandos
como atribuição
• Composição e decomposição suportados
Modularidade
• Programas manipulados como uma
expressão matemática
Prova e transformação de programas
Programação Funcional
Programação Funcional
Visão Crítica
Visão Crítica
• Vantagens
– Manipulação mais simples de programas
• Legibilidade
• Modularidade
– Prova de propriedades
• Problemas
– “O mundo não é funcional!”
– Implementações ineficientes
– Mecanismos primitivos de E/S e formatação
• Interface
addD a b = 2 * (a + b) = 2 * (b + a) = addD b a
– Semântica
– Transformação
– Concorrência explorada de forma natural
Notação: Programação baseada
em definições
Definição de Funções
answer :: Int
answer = 42
square :: Int -> Int
square x = x * x
greater :: Bool
greater = (answer > 71)
allEqual :: Int -> Int -> Int -> Bool
allEqual n m p = (n == m) && (m == p)
yes :: Bool
yes = True
Avaliando Expressões
• Encontrar o valor de uma expressão
• Usar definições das funções
addD :: Int -> Int -> Int
addD a b = 2 * (a+b)
addD 2 (addD 3 4)
= 2 * (2 + (addD 3 4))
= 2 * (2 + 2 * (3 + 4))
= 32
maxi :: Int -> Int -> Int
maxi n m | n >= m
= n
| otherwise = m
Prova de propriedades
• Exemplo:
addD a b = 2 * (a+b)
= 2 * (b+a) = addD b a
• Válida para quaisquer argumentos a e b
• Não seria válida em linguagens imperativas,
com variáveis globais.
Em uma linguagem imperativa...
Em um sistema de controle de vendas:
• suponha vendas semanais dadas pela função
int b = 1;
...
int f (int x) {
b = x;
return (5)
}
vendas :: Int -> Int
• total de vendas da semana 0 à semana n?
vendas 0 + vendas 1 + ... + vendas (n-1) + vendas n
totalVendas :: Int -> Int
totalVendas n
| n == 0
= vendas 0
| otherwise = totalVendas (n-1) + vendas n
addD (f 3) b == addD b (f 3) ?
Recursão
• Definir caso base, i.e. valor para fun
• Definir o valor para
fun
usando o valor de
fun
Este é o caso recursivo.
Casamento de Padrões
0
n
(n-1)
maxVendas :: Int -> Int
maxVendas n
| n == 0
= vendas 0
| otherwise = maxi (maxVendas (n-1))
(vendas n)
Casamento de Padrões
myNot :: Bool -> Bool
myNot True = False
myNot False = True
myOr :: Bool -> Bool -> Bool
myOr True x = True
myOr False x = x
myAnd :: Bool -> Bool -> Bool
myAnd False x = False
myAnd True x = x
Exemplo
• Permite usar padrões no lugar de variáveis, na
definição de funções:
maxVendas :: Int -> Int
maxVendas 0 = vendas 0
maxVendas n = maxi (maxVendas (n-1))
(vendas n)
totalVendas :: Int -> Int
totalVendas 0 = vendas 0
totalVendas n = totalVendas (n-1) +
vendas n
Regras para Padrões
• Todos os padrões (esquerda) devem ter
tipos compatíveis
• Os casos devem ser exaustivos
– não é obrigatório Î funções parciais
• Não deve haver ambiguidade
– Ordem dos padrões usada para resolver
conflitos
Notação
•
•
•
•
Notação
•f n + 1
• f (n + 1)
Maiúsculas: Tipos e Construtores
Minúsculas: funções e argumentos
case sensitive
comentários:
--isso é um comentario de uma linha
{- comentario de varias linhas... -}
•2 + 3
• (+) 3 2
• maxi 2 4
• 2 ‘maxi‘ 4
Exercícios
Erros comuns
square x =
*x
• Defina as seguintes funções:
x
answer = 42; newline = ’\n’
--OK
– fatorial fat :: Int -> Int
– compara se quatro números são iguais
all4Equal :: Int -> Int -> Int -> Int -> Bool
funny x = x +
1
Error! Unexpected ’;’
usando allEqual
– retorna quantos parâmetros são iguais
– all4Equal
howManyEqual :: Int -> Int -> Int -> Int
Funny x = x+1
Error! Undefined constructor ’Funny’
Definições Locais
sumSquares :: Int -> Int -> Int
sumSquares x y = sqX + sqY
where sqX = x * x
sqY = y * y
Definições Locais
maxThreeOccurs :: Int -> Int -> Int -> (Int,Int)
maxThreeOccurs m n p = (mx, eqCount)
where mx = maxiThree m n p
eqCount = equalCount mx m n p
...
sumSquares x y = sq x + sq y
where sq z = z * z
sumSquares x y = let sqX = x * x
sqY = y * y
in sqX + sqY
• let definições in expressão
• definições where definições
Exercícios
• Defina uma função que dado um valor
inteiro s e um número de semanas n,
retorna quantas semanas de 0 a n tiveram
venda igual a s.
Considerações Gerais
• Operações e variáveis
– Em linguagens imperativas, as operações são
executadas e os resultados armazenados em
variáveis para uso posterior
– O gerenciamento de variáveis é uma
preocupação constante e uma fonte de
complexidade para linguagens imperativas
Considerações Gerais
• Transparência Referencial
– Uma expressão pode ser sempre substituída
pelo seu valor (ou por outra expressão que
denote o mesmo valor)
• Composicionalidade
– Valor obtido a partir dos valores dos subcomponentes
Considerações Gerais
• Uma expressão sempre denota um único
valor
• Expressões podem conter variáveis
– variáveis não mudam de valor!
– Não há efeito colateral de qualquer espécie
Considerações Gerais
• Operações e variáveis
– Variáveis não são necessárias em linguagens
fucionais, como é o caso da matemática
– Em linguagens funcionais, a avaliação de uma
função sempre produz o mesmo resultado
quando fornecidos os mesmos parâmetros
• Transparência referencial