Paradigma declarativo
As linguagens funcionais, tal como as linguagens lógicas,
pertencem à classe das linguagens declarativas. Estas,
contrariamente às linguagens imperativas, englobam numa só as
noções de programa e de especificação: um programa é uma
especificação executável.
Um programa escrito numa linguagem lógica consiste na descrição
de relações entre valores através de um conjunto de asserções
lógicas (afirmações e interrogações), sendo as respostas
automaticamente derivadas.
Um programa escrito numa linguagem funcional consiste na
descrição de valores através de expressões, as quais são
automaticamente avaliadas.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
1
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções
Informalmente, uma função é uma correspondência entre valores
de um domínio (argumento) e de um codomínio (resultado) que
associa no máximo um resultado a cada um dos argumentos.
Representa-se da seguinte forma
f: A  B
em que f é o nome da função, A é o seu domínio e B o seu
codomínio.
dobro: int  int
par: int  boolean
or: boolean  boolean
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
dobro(n) = 2 * n ou dobro(n) = n + n
par(n) = ((n mod 2) = 0)
or(b, false) = b, or(b, true) = true
2
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções
Uma função pode ser definida:
intensionalmente: através de uma regra (algoritmo).
extensionalmente: por um conjunto de pares, (argumento, resultado)
usualmente infinito – chamado grafo da função.
Grafo da função dobro
(3,6), (2,4), (1,2), (0,0), (-1, -2) e por aí adiante...
Duas funções são iguais se têm os mesmos domínio e codomínio e se dão o
mesmo resultado quando aplicadas ao mesmo argumento, ainda que sejam
calculadas por regras diferentes – princípio da extensionalidade. Este facto
permite-nos abstrair da forma como o resultado é calculado.
Duas funções iguais
dobro_1 (n) = 2 * n
dobro_2 (n) = n + n
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
3
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções
As funções podem ser totais ou parciais consoante estão
definidas para todo o valor do seu domínio ou não (domínio vs.
conjunto de partida). As funções parciais são, como as totais,
bastante comuns.
No entanto é também comum as linguagens funcionais terem
mecanismos que protegem a possibilidade de uma função parcial
ser aplicada a um valor não pertencente ao seu conjunto de partida
(nomeadamente excepções).
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
4
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções
Funções com múltiplos argumentos correspondem a situações em
que o domínio A é um produto cartesiano ( A = A1 x A2 x ... x An).
Representam-se da seguinte forma
f: (A1 x A2 x ... x An)  B
em que f é o nome da função, A1 x A2 x ... x An é o produto
cartesiano que representa o seu domínio (a função tem n
argumentos) e B é o codomínio.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
5
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções
Na realidade, uma função em ML tem sempre um único argumento.
No entanto esse argumento pode ser um tuplo, simulando uma
função que recebe vários argumentos.
A soma de dois inteiros 2 + 5 (forma infixa) representa a função de adição
aplicada ao par (2,5).
Como tal essa função tem apenas um argumento (1 par) e pode ser
representada por +: (int x int)  int
Mas, tal como foi mencionado acima, esse par (2 elementos) simula uma
função que recebe 2 argumentos.
Muitas vezes, por abuso de linguagem, dizemos que a função + recebe
dois inteiros e retorna um inteiro. Na realidade deveriamos dizer que
recebe um par de inteiros e retorna um inteiro.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
6
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Expressões
Para descrever a aplicação de uma função f a um argumento a
podemos usar
fa
ou
f (a)
Podemos ainda combinar várias funções através da composição.
Ou seja, podemos dar o resultado de uma certa função como
argumento a outra função
g (f a) ou g(f (a))
A função
produtopar(x, y) = par(x * y)
combina as funções par e *
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
7
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Transparência Referencial
Qualquer composição de funções descrita por uma expressão é
garantidamente uma função.
A essência da programação funcional é que todos os valores
produzidos em sub-cálculos são comunicados a outras partes do
programa apenas através da aplicação de funções (i.e., como
argumentos e resultados de funções). Isto contrasta com o
mecanismo usado nas linguagens imperativas onde, por vezes, são
utilizadas variáveis globais (que são alteradas e consultadas ao
longo do programa).
Isto leva-nos a uma característica da programação funcional que
diz que o valor retornado por uma função é determinado
exclusivamente pelo valor dos argumentos fornecidos –
transparência referencial.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
8
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Tipos
Os tipos classificam os valores em
inteiros, reais, booleanos, ...
produto cartesiano de A e B (A x B),
funções com domínio A e codomínio B (A  B)
Síntese / verificação automática de tipos
é muito importante do ponto de vista da programação
pois permite detectar precocemente certos erros
o sistema tenta atribuir um tipo a cada sub-expressão de
uma expressão E tendo em conta a forma como estas
sub-expressões são usadas, e com estes tipos constrói
os tipos de E.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
9
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Tipos
Porquê?
Permitem a geração de código mais eficiente e a utilização de
espaço de forma mais eficaz
Permitem detectar muitos erros de programação antes da
execução
São uma forma de documentar o código, para outros
programadores
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
10
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Mecanismo de Tipificação
Fortemente tipificado, são impostas regras estritas no uso
dos tipos, sem que sejam permitidas excepções.
Fracamente tipificado, são impostas regras estritas no uso
dos tipos, no entanto são permitidas excepções bem definidas.
Tipificação estática, acontece durante a compilação
Tipificação dinâmica, acontece durante a execução
O ML é uma linguagem fortemente tipificada com tipificação
estática. No entanto tem uma característica, o polimorfismo, que
lhe garante algumas vantagens da tipificação dinâmica e fraca.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
11
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definições
Definir um valor consiste em associar um nome e uma expressão
ao valor a definir.
Definir uma função consiste em associar um nome, um parâmetro
e uma regra à função a definir.
Em qualquer dos casos, os nomes definidos podem
subsequentemente ser utilizados noutras expressões.
Uma expressão, conjuntamente com as definições nela
envolvidas constitui um programa ML.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
12
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definição de Valores
Na definição de valores a palavra chave utilizada é val. A esta
seguem-se o nome do valor a definir, o símbolo “=“ e a expressão
cujo valor fica associado ao nome.
val codeof0 = ord “0”
val codeof9 = codeof0 + 9
val thepair = (size “blabla”, size “”)
val codeof0 = 0
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
13
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definição de Valores
O âmbito de um nome introduzido por uma definição de valor
(contexto textual em que ele é reconhecido) é a colecção das
definições subsequentes.
Assim, codeof0 é um nome a que está associado o valor 48 (valor
da expressão ord “0”, ou seja o código ASCII do caracter “0”).
Este nome pode ser utilizado nas definições que se lhe seguem.
Mais concretamente, nas expressões usadas nessas definições.
Por exemplo, para definir codeof9, usou-se o nome codeof0 na
expressão que o define.
O nome codeof0 aparece redefinido mais à frente: o novo valor
associado a este nome será 0. Portanto afectará de forma
diferente, as expressões que se sigam a esta redefinição.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
14
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definição de Funções
Na definição de funções a palavra chave utilizada é fun. A esta
seguem-se o nome da função, o parâmetro, o símbolo “=“ e a
regra. Um parâmetro é um nome temporário que está no lugar de
um argumento arbitrário ao qual a função pode ser aplicada (e
por isso é muitas vezes chamado de variável).
A regra é uma expressão que relaciona o parâmetro com o
resultado.
fun dobro x = x + x
fun triplo x = 3 * x
fun seisvezes x = dobro (triplo x)
fun par x = ((x mod 2) = 0)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
15
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definição de Funções
Nas funções binárias o parâmetro pode ser um tuplo de variáveis
(m,n). O resultado pode ser também um tuplo.
fun sumbetween(m,n) = ((m+n) * (abs(m-n) + 1)) div 2
fun sumdif(m,n) = (m+n, abs(m-n))
fun primeiro(m,n) = m
fun segundo(m, n) = n
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
16
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Expressões
Para escrever funções podemos usar expressões da forma
fn x  E
parâmetro formal
Funções anónimas
corpo
onde E é uma expressão (esta notação deriva do cálculo-, tal
como foi desenvolvido por A. Church em 1941 para estudar a
computação como funções) e fn é a abreviatura para function.
Por exemplo, para a função dobro teríamos:
fn x  x + x
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
17
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definições
Repare-se que até ao momento a única diferença que se pode
verificar entre a definição de uma função e a definição de um
valor é, além da palavra chave, a existência do parâmetro. No
entanto, é também possível introduzir a definição de uma função
através da palavra val, usando a palavra chave fn mencionada
anteriormente.
val dobro = fn x  x + x
val seisvezes = fn x  dobro (triplo x)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
18
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definições
Na definição de funções não se torna necessário dizer qual o tipo
do parâmetro nem do resultado, pois estes são verificados e
determinados automaticamente pelo ‘type checker’ do ML. Assim,
na definição da função dobro, o ‘type checker’ consegue
determinar que o parâmetro x é do tipo inteiro e o resultado
também, dado que o tipo da função + é (int x int)  int
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
19
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Avaliação de Expressões
Na aplicação de funções, pode-se substituir o parâmetro por uma
expressão (argumento) do tipo apropriado. A expressão dada
como argumento é avaliada e só então a função é aplicada,
fazendo a expansão através do uso da regra.
A avaliação de expressões é feita da forma ilustrada no seguinte
exemplo:
seisvezes(1+1) = seisvezes(2) = dobro(triplo 2) = dobro(3*2) = dobro 6 = 6 + 6 = 12
Note-se que a aplicação de funções a argumentos poderia ser
feita pela ordem inversa, i.e., primeiro usar-se-ia a regra para
fazer a expansão e só então se avaliaria o argumento. O
resultado final seria o mesmo.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
20
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Expressões condicionais
As expressões condicionais permitem definir funções por análise
de casos
if E then E1 else E2
onde E é uma expressão de tipo booleano e E1 e E2 são
expressões com o mesmo tipo.
Esta construção pode ser vista como uma função cujos
parâmetros são E, E1 e E2 e cujo resultado é uma expressão (do
mesmo tipo que E1 e E2). Assim para quaisquer expressões E1 e
E2 de um mesmo tipo, tem-se que:
if true then E1 else E2 = E1
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
e
21
if false then E1 else E2 = E2
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Expressões condicionais
No lugar de E1 e E2 podem também estar construções if-thenelse, sendo portanto possível encadear tais expressões.
fun minmaxpair(m,n) = if m<n then (m,n) else (n,m)
fun maxpair anypair = segundo(minmaxpair(anypair))
Note-se que, na definição da função binária maxpair, o parâmetro
não é um tuplo da forma (m,n) como em casos anteriores, pois
não é necessário fazer referências às componentes. No entanto o
‘type checker’ sabe determinar o tipo do parâmetro dada a
natureza desta expressão, pois minmaxpair requer como
parâmetro um par de inteiros.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
22
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Emparelhamento de Padrões
Em certas situações é possível definir funções por análise de
casos usando, em alternativa às expressões condicionais o
emparelhamento de padrões (pattern matching). Nesta situação
são especificados vários casos para uma função consoante o
padrão a que obedece o argumento.
Quando a função é aplicada, para determinar qual o caso que
deve ser usado, o valor do argumento tem que ser emparelhado
com os padrões dos argumentos na definição.
fun negation true = false
| negation false = true
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
23
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Emparelhamento de Padrões
fun or(true, b) = true
| or(false, b) = b
Os padrões devem ser exaustivos, sob pena da função ficar indefinida
nalguns pontos do seu domínio. Pode haver, no entanto, intersecção de
padrões. Nesse caso a ambiguidade é resolvida da seguinte forma: é
seleccionado o primeiro padrão da lista que coincida com o argumento.
Além disso, em cada padrão, não pode haver repetição de variáveis,
uma vez que tal obrigaria à existência do teste de igualdade para o
respectivo tipo de dados. Ou seja, a seguinte definição é incorrecta:
fun xor (b, b) = false
| xor (a, b) = true
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
24
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definições recursivas e Funções parciais
Numa definição recursiva (fun) o nome a definir aparece na
expressão que o define.
fun potencia(b, e) = if e=0 then 1 else b*potencia(b, e-1)
Note-se que a avaliação de potencia(5, ~1) não termina. Na
realidade a função não se encontra definida em todo o seu
domínio: int x int. Como já foi referido é chamada uma função
parcial.
O mesmo se passa com a função div. O problema pode ser
solucionado usando um valor por omissão
fun safediv (m, 0) = ~1000
|
safediv (m, n) = m div n
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
25
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Definições recursivas e Funções parciais
No entanto, uma solução preferível consiste em assumir a
existência de uma função error que aborta a avaliação da
expressão e escreve uma mensagem de erro nos casos
indefinidos.
fun potencia(b,e) = if e<0 then error “potencia indefinida para
expoentes negativos”
else
if e=0 then 1 else b*potencia(b, e-1)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
26
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Exercícios
Avalie potencia(1+1, 3) usando definição recursiva
apresentada.
potencia(1+1, 3)  potencia(2, 3) 
if 3 = 0 then 1 else 2*potencia(2, 3-1) 
if false then 1 else 2*potencia(2, 2) 
2*potencia(2, 2)  2*(if 2 = 0 then 1 else potencia(2, 2-1) 
2*(if false then 1 else 2*potencia(2, 1)) 
2*(2*potencia(2, 1))  2*(2*(if 1 = 0 then 1 else 2*potencia(2, 1-1))) 
2*(2*(if false then 1 else 2*potencia(2, 0))) 
2*(2*(2*potencia(2, 0))) 
2*(2*(2*(if 0 = 0 then 1 else 2*potencia(2, 0-1)))) 
2*(2*(2*(if true then 1 else 2*potencia(2, ~1)))) 
2*(2*(2*1))  2*(2*2)  2 * 4  8
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
27
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)