Linguagens de programacao funcional
Linguagens de Programacao
Marco A L Barbosa
cbaEste trabalho esta licenciado com uma Licenca Creative Commons - Atribuicao-CompartilhaIgual 4.0 Internacional.
http://github.com/malbarbo/na-lp-copl
ConteudoIntroducao
Funcoes matematicas
Fundamentos das linguagens de programacao funcionais
A primeira linguagem de programacao funcional: Lisp
Introducao ao Scheme
Common Lisp
ML
Haskell
Aplicacoes das linguagens funcionais
Comparacao entre as linguagens funcionais e imperativas
Referencias
Introducao
IntroducaoI O projeto das linguagens imperativas e baseado na arquitetura
de von NeumannI Eficiencia e a preocupacao primaria, ao inves da adequacao da
linguagem para o desenvolvimento de softwareI As linguagens imperativas podem ser vistas como uma
sucessao de melhorias ao modelo basico (Fortran 1)
I O projeto das linguagens funcionais e baseado em funcoesmatematicas
I Uma base teorica solidaI Sem preocupacao com a arquitetura da maquina
I O interesse pelo paradigma de programacao funcional cresceuapos o discurso do John Backus quando ele recebeu o ACMTuring Award em 1977
I Os programas escritos em linguagens de programacaopuramente funcionais sao mais legıveis, mais confiaveis, e temmais chances de estarem corretos
I O significado das expressoes sao independentes do contexto
4 / 53
IntroducaoI O projeto das linguagens imperativas e baseado na arquitetura
de von NeumannI Eficiencia e a preocupacao primaria, ao inves da adequacao da
linguagem para o desenvolvimento de softwareI As linguagens imperativas podem ser vistas como uma
sucessao de melhorias ao modelo basico (Fortran 1)
I O projeto das linguagens funcionais e baseado em funcoesmatematicas
I Uma base teorica solidaI Sem preocupacao com a arquitetura da maquina
I O interesse pelo paradigma de programacao funcional cresceuapos o discurso do John Backus quando ele recebeu o ACMTuring Award em 1977
I Os programas escritos em linguagens de programacaopuramente funcionais sao mais legıveis, mais confiaveis, e temmais chances de estarem corretos
I O significado das expressoes sao independentes do contexto
4 / 53
IntroducaoI O projeto das linguagens imperativas e baseado na arquitetura
de von NeumannI Eficiencia e a preocupacao primaria, ao inves da adequacao da
linguagem para o desenvolvimento de softwareI As linguagens imperativas podem ser vistas como uma
sucessao de melhorias ao modelo basico (Fortran 1)
I O projeto das linguagens funcionais e baseado em funcoesmatematicas
I Uma base teorica solidaI Sem preocupacao com a arquitetura da maquina
I O interesse pelo paradigma de programacao funcional cresceuapos o discurso do John Backus quando ele recebeu o ACMTuring Award em 1977
I Os programas escritos em linguagens de programacaopuramente funcionais sao mais legıveis, mais confiaveis, e temmais chances de estarem corretos
I O significado das expressoes sao independentes do contexto
4 / 53
Funcoes matematicas
Funcoes matematicas
I Uma funcao matematica e um mapeamento dos membros deum conjunto, chamado de conjunto domınio, para outro, oconjunto imagem
I Note que os conjuntos podem ser o produto cartesiano dediversos outros conjuntos
I A ordem de avaliacao das expressoes de uma funcao econtrolada por recursao e por expressoes condicionais, naopela sequencia ou pela repeticao interativa (comum naslinguagens imperativas)
I Uma funcao matematica sempre define o mesmo valor, paraos mesmos argumentos
6 / 53
Funcoes matematicas
I Funcoes simples
I Definicao de funcao: cubo(x) ≡ x ∗ x ∗ xI Aplicacao de funcao: cubo(8)
I As vezes e conveniente separar a atividade de definir umafuncao e a atividade de nomear uma funcao
I Notacao lambda (Alonzo Church 1941)I Definicao: λ(x)x ∗ x ∗ xI Aplicacao: (λ(x)x ∗ x ∗ x)(2)
7 / 53
Funcoes matematicas
I Funcoes simples
I Definicao de funcao: cubo(x) ≡ x ∗ x ∗ xI Aplicacao de funcao: cubo(8)
I As vezes e conveniente separar a atividade de definir umafuncao e a atividade de nomear uma funcao
I Notacao lambda (Alonzo Church 1941)I Definicao: λ(x)x ∗ x ∗ xI Aplicacao: (λ(x)x ∗ x ∗ x)(2)
7 / 53
Funcoes matematicas
I Formas funcionais
I Uma funcao de alta ordem, ou forma funcional, e aquela quetoma funcoes como parametro, produz uma funcao comoresultado, ou ambos
I Composicao de funcoes
I Toma duas funcoes como parametro e define uma funcao cujoo valor e a primeira funcao aplicada ao resultado da segunda
I h ≡ f ◦ g , h(x) ≡ f (g(x))
I Aplicar a tudo (Apply to all)
I Toma uma funcao como parametro e resulta em uma lista devalores aplicando a funcao dada a cada elemento da lista deparametros
I Forma: αI h(x) ≡ x ∗ xI α(h, (2, 3, 4)) resulta (4, 9, 16)
8 / 53
Funcoes matematicas
I Formas funcionais
I Uma funcao de alta ordem, ou forma funcional, e aquela quetoma funcoes como parametro, produz uma funcao comoresultado, ou ambos
I Composicao de funcoes
I Toma duas funcoes como parametro e define uma funcao cujoo valor e a primeira funcao aplicada ao resultado da segunda
I h ≡ f ◦ g , h(x) ≡ f (g(x))
I Aplicar a tudo (Apply to all)
I Toma uma funcao como parametro e resulta em uma lista devalores aplicando a funcao dada a cada elemento da lista deparametros
I Forma: αI h(x) ≡ x ∗ xI α(h, (2, 3, 4)) resulta (4, 9, 16)
8 / 53
Funcoes matematicas
I Formas funcionais
I Uma funcao de alta ordem, ou forma funcional, e aquela quetoma funcoes como parametro, produz uma funcao comoresultado, ou ambos
I Composicao de funcoes
I Toma duas funcoes como parametro e define uma funcao cujoo valor e a primeira funcao aplicada ao resultado da segunda
I h ≡ f ◦ g , h(x) ≡ f (g(x))
I Aplicar a tudo (Apply to all)
I Toma uma funcao como parametro e resulta em uma lista devalores aplicando a funcao dada a cada elemento da lista deparametros
I Forma: αI h(x) ≡ x ∗ xI α(h, (2, 3, 4)) resulta (4, 9, 16)
8 / 53
Fundamentos das linguagens de programacaofuncionais
Fundamentos das linguagens de programacao funcionais
I O objetivo do projeto de uma LPF e imitar ao maximo asfuncoes matematicas
I O processo basico de computacao em uma LPF efundamentalmente diferente do processo em uma linguagemimperativa
I Em uma linguagem imperativa, as operacoes sao realizadas eos resultados sao armazenados em variaveis para uso posterior
I Nas LFP, variaveis nao sao necessarias, assim como namatematica
I Nas LFP, a avaliacao de uma funcao sempre produz o mesmoresultado se os mesmos parametros forem dados (transparenciareferencial)
I Repeticao e especificada com recursaoI Programas consistem em definicoes de funcoes e especificacao
de aplicacoes de funcoesI A execucao consistem na avaliacao das aplicacoes das funcoes
10 / 53
Fundamentos das linguagens de programacao funcionais
I O objetivo do projeto de uma LPF e imitar ao maximo asfuncoes matematicas
I O processo basico de computacao em uma LPF efundamentalmente diferente do processo em uma linguagemimperativa
I Em uma linguagem imperativa, as operacoes sao realizadas eos resultados sao armazenados em variaveis para uso posterior
I Nas LFP, variaveis nao sao necessarias, assim como namatematica
I Nas LFP, a avaliacao de uma funcao sempre produz o mesmoresultado se os mesmos parametros forem dados (transparenciareferencial)
I Repeticao e especificada com recursaoI Programas consistem em definicoes de funcoes e especificacao
de aplicacoes de funcoesI A execucao consistem na avaliacao das aplicacoes das funcoes
10 / 53
Fundamentos das linguagens de programacao funcionais
I O objetivo do projeto de uma LPF e imitar ao maximo asfuncoes matematicas
I O processo basico de computacao em uma LPF efundamentalmente diferente do processo em uma linguagemimperativa
I Em uma linguagem imperativa, as operacoes sao realizadas eos resultados sao armazenados em variaveis para uso posterior
I Nas LFP, variaveis nao sao necessarias, assim como namatematica
I Nas LFP, a avaliacao de uma funcao sempre produz o mesmoresultado se os mesmos parametros forem dados (transparenciareferencial)
I Repeticao e especificada com recursaoI Programas consistem em definicoes de funcoes e especificacao
de aplicacoes de funcoesI A execucao consistem na avaliacao das aplicacoes das funcoes
10 / 53
Fundamentos das linguagens de programacao funcionais
I Uma LPF deve prover
I Um conjunto de funcoes primitivasI Um conjunto de formas funcionaisI Um operador de aplicacao de funcaoI E algumas estruturas para representar dados
I Em geral as LPF sao implementadas com interpretadores, maselas tambem podem ser compiladas
I As linguagens imperativas em geral oferecem suporte limitadoa programacao funcional
I Nao oferecem muitas formas funcionais (ex: retorno de funcao)I Permitem efeitos colaterais
11 / 53
A primeira linguagem de programacaofuncional: Lisp
A primeira linguagem de programacao funcional: Lisp
I Lisp (LISt Processing) foi criada por John McCarthy em 1958
I E a segunda linguagem de programacao de alto nıvel maisantiga ainda em uso
I Existem muitos dialetos: Common Lisp, Scheme, Clojure
13 / 53
A primeira linguagem de programacao funcional: Lisp
I Tipo de dados
I Atomos: sımbolos (identificadores) ou literais numericosI Listas
I Listas sao especificadas delimitando os seus elementos comparenteses
I (A B C D)I (A (B C) D (E (F G)))I Em geral, as listas sao armazenadas internamente como listas
ligada simples
14 / 53
A primeira linguagem de programacao funcional: Lisp
15 / 53
A primeira linguagem de programacao funcional: LispI A notacao lambda e usada para especificar funcoes e definicao
de funcoesI (function name (lambda (arg1 . . . argn) expression))
I A aplicacao de funcoes e os dados tem a mesma formaI Se a lista (A B C) e interpretada como dado ela e uma lista
simples de tres atomosI Se a lista e interpretada como aplicacao de funcao, ela significa
que a funcao nomeada A e aplicada aos parametros A e B
I Lisp foi a primeira linguagem homoiconicaI O primeiro interpretador Lisp apareceu como uma
demonstracao da capacidade universal de computacao danotacao
I Stephen Russell e Daniel EdwardsI Implementacao da funcao eval
I A notacao usada pelo Lisp e chamada de expressoes s(symbolic expressions)
16 / 53
A primeira linguagem de programacao funcional: LispI A notacao lambda e usada para especificar funcoes e definicao
de funcoesI (function name (lambda (arg1 . . . argn) expression))
I A aplicacao de funcoes e os dados tem a mesma formaI Se a lista (A B C) e interpretada como dado ela e uma lista
simples de tres atomosI Se a lista e interpretada como aplicacao de funcao, ela significa
que a funcao nomeada A e aplicada aos parametros A e B
I Lisp foi a primeira linguagem homoiconicaI O primeiro interpretador Lisp apareceu como uma
demonstracao da capacidade universal de computacao danotacao
I Stephen Russell e Daniel EdwardsI Implementacao da funcao eval
I A notacao usada pelo Lisp e chamada de expressoes s(symbolic expressions)
16 / 53
A primeira linguagem de programacao funcional: LispI A notacao lambda e usada para especificar funcoes e definicao
de funcoesI (function name (lambda (arg1 . . . argn) expression))
I A aplicacao de funcoes e os dados tem a mesma formaI Se a lista (A B C) e interpretada como dado ela e uma lista
simples de tres atomosI Se a lista e interpretada como aplicacao de funcao, ela significa
que a funcao nomeada A e aplicada aos parametros A e B
I Lisp foi a primeira linguagem homoiconicaI O primeiro interpretador Lisp apareceu como uma
demonstracao da capacidade universal de computacao danotacao
I Stephen Russell e Daniel EdwardsI Implementacao da funcao eval
I A notacao usada pelo Lisp e chamada de expressoes s(symbolic expressions)
16 / 53
Introducao ao Scheme
Introducao ao Scheme
I Criada em meados de 1970 por Gerald Sussman e Guy Steele,projetada uma versao para ser limpa, moderna e simples deLisp
I Usa apenas escopo estatico
I Funcao sao entidades de primeira classe
18 / 53
Introducao ao Scheme
I Avaliacao de aplicacao de funcoes
I Os parametros sao avaliados, em nenhuma ordem particularI Os valores dos parametros sao substituıdos no corpo da funcaoI O corpo da funcao e avaliadaI O valor da ultima expressao no corpo da funcao e o resultado
I Exemplo
I (* (- 5 3) (/ 8 2))I (* 2 (/ 8 2))I (* 2 4)I 8
19 / 53
Introducao ao Scheme
I Funcoes numericas
I Aritmetica: +, -, *, /, abs, quotient, remainder,
modulo, gcd, lcm, expt, sqrtI Aproximacao: floor, ceiling, truncate, roundI Desigualdades: <, <=, >, >=I Outros: zero?, negative?, positive? odd? even?I Maximo e mınimo: max, minI Trigonometria: sin, cos, tan, asin, acos, atanI Exponencial: exp, log
20 / 53
Introducao ao Scheme
I Formas especiais
(define symbol expression)
(lambda (parameters) expression)
(define (function-name parameters) expression)
(if predicate then-expression else-expression)
(cond
(predicate1 expression1)
(predicate2 expression2)
...
(predicaten expressionn)
[(else expression)]
)
21 / 53
Introducao ao Scheme
I Formas especiais
I (quote expression)
> (quote a)
a
> (quote (a b c))
(a b c)
> ’(+ 2 3)
(+ 2 3)
I (let ((id exp)+) exp)
> (let ((a 10) (b 20)) (+ a b))
30
I let*, letrec
22 / 53
Introducao ao Scheme
I Listas
I car: retorna o primeiro elemento de uma lista
> (car ’(a b c))
’a
> (car ’((a b) c d))
’(a b)
> (car ’a)
erro
> (car ’(a))
’a
> (car ’())
erro
23 / 53
Introducao ao Scheme
I Listas
I cdr: retorna a lista sem o primeiro elemento
> (cdr ’(a b c))
’(b c)
> (cdr ’((a b) c d))
’(c d)
> (cdr ’a)
erro
> (cdr ’(a))
’()
> (cr ’())
erro
24 / 53
Introducao ao Scheme
I Listas
I cons: insere o primeiro parametro como car do segundoparametro
> (cons ’a ’())
’(a)
> (cons ’a ’(b c))
’(a b c)
> (cons ’() ’(a b))
’(() a b)
> (cons ’(a b) ’(c d))
’((a b) c d)
> (cons ’a ’b)
’(a . b)
I list: constroi uma lista a partir dos parametros
> (list ’a ’b ’c)
’(a b c)
25 / 53
Introducao ao Scheme
I Funcoes predicados para listas
I eq?: recebe dois parametros e faz uma comparacao rasa, istoe, verifica se os dois parametros referem-se ao mesmo objeto
I eqv?: semelhante ao eq?, mas para numeros e caracteres acomparacao e pelo conteudo, nao pela referencia
I equal?: para os tipos definidos pelo Racket (lista, string, etc),faz comparacao profunda, ou seja, verifica recursivamente se oconteudo e o mesmo
I list?: retorna #t se o parametro e uma listaI null?: retorna #t se o parametro e uma lista vazia
26 / 53
Introducao ao Scheme
I Recursao em cauda
I Uma funcao recursiva em cauda e aquela em que a chamadarecursiva e a ultima operacao na funcao
I Este tipo de funcao pode ser traduzida pelo compilador emuma iteracao, resultando em uma execucao mais rapida
I As vezes e interessante transformar uma funcao recursiva emuma funcao recursiva em cauda
(define (fat-helper n partial)
(if (= n 0)
partial
(fat-helper (- n 1) (* n partial))))
(define (fat n)
(fat-helper n 1))
27 / 53
Introducao ao Scheme
I Exemplos
I Testar se um elemento e membro de uma listaI Calcular o tamanho de uma listaI Calcular a soma dos elementos de uma listaI Calcular o produto dos elementos de uma listaI Reversao de listaI Testar se duas listas sao iguaisI Concatenacao de duas listasI Intersecao de duas listasI Ordenacao (quicksort)I Etc
28 / 53
Introducao ao Scheme
I Formas funcionais
I foldl, foldrI mapI filter
I Outras funcoes
I evalI apply
29 / 53
Common Lisp
Common Lisp
I Foi criado para combinar caracterısticas de diversos dialetosde Lisp
I E uma linguagem grande e complexa (oposto do Scheme)
I Caracterısticas
I Permite escopo estatico e dinamicoI Muito tipos de dados e estruturasI Sistema poderoso de entrada e saıdaI Pacotes (para modularizacao)
I Common Lisp foi criado para ser uma linguagem comercial
I Scheme e mais usado para o ensino
31 / 53
ML
ML
I Criada por Robert Miler (e outros) no inıcio dos anos 70
I Fortemente tipada
I Sintaxe semelhante as linguagens imperativas
I Inclui tratamento de excecao, modulos (para criar tiposabstratos de dados) e listas
33 / 53
ML
I Declaracao de funcao
fun nome_da_func~ao(parametros) = corpo_da_func~ao;
fun square(x : int) = x * x
fun square(x : int) : int = x * x
fun square(x) = x * x
I Funcoes que usam aritmetica nao podem ser polimorficas
I Funcoes que usam apenas operacoes de listas, =, <> , eoperacoes de tuplas, podem ser polimorficas
I Funcoes definidas pelo usuario nao podem ser sobrecarregadas
34 / 53
ML
I Controle de fluxo
if express~ao then express~ao_then else express~ao_else
I Exemplo
fun fact(n : int): int = if n = 0 then 1
else n * fact(n - 1);
I Multiplas definicoes de uma funcao podem ser escritas usandocasamento de padrao nos parametros
fun fact(0) = 1
| fact(n : int): int = n * fact(n - 1);
35 / 53
ML
I Controle de fluxo
if express~ao then express~ao_then else express~ao_else
I Exemplo
fun fact(n : int): int = if n = 0 then 1
else n * fact(n - 1);
I Multiplas definicoes de uma funcao podem ser escritas usandocasamento de padrao nos parametros
fun fact(0) = 1
| fact(n : int): int = n * fact(n - 1);
35 / 53
ML
I Controle de fluxo
if express~ao then express~ao_then else express~ao_else
I Exemplo
fun fact(n : int): int = if n = 0 then 1
else n * fact(n - 1);
I Multiplas definicoes de uma funcao podem ser escritas usandocasamento de padrao nos parametros
fun fact(0) = 1
| fact(n : int): int = n * fact(n - 1);
35 / 53
ML
I Listas
I Listas literais sao especificadas com colchetes: [5, 7, 9]I Lista vazia, [] ou nillI Todos os elementos da lista precisam ser do mesmo tipoI A operacao cons e o operador binario ::I 3 :: [5, 7, 9] resulta em [3, 5, 7, 9]I car e a funcao unaria hd (head)I cdr e a funcao unaria tl (tail)I As funcoes hd e tl sao menos usados do que em Lisp, porque
as funcoes podem ser definidas com padroes
I Exemplos
fun lenght([]) = 0
| lenght(h :: t) = 1 + lenght(t);
fun append([], list2) = list2
| append(h :: t, list2) = h :: append(t, list2);
36 / 53
ML
I Listas
I Listas literais sao especificadas com colchetes: [5, 7, 9]I Lista vazia, [] ou nillI Todos os elementos da lista precisam ser do mesmo tipoI A operacao cons e o operador binario ::I 3 :: [5, 7, 9] resulta em [3, 5, 7, 9]I car e a funcao unaria hd (head)I cdr e a funcao unaria tl (tail)I As funcoes hd e tl sao menos usados do que em Lisp, porque
as funcoes podem ser definidas com padroesI Exemplos
fun lenght([]) = 0
| lenght(h :: t) = 1 + lenght(t);
fun append([], list2) = list2
| append(h :: t, list2) = h :: append(t, list2);
36 / 53
ML
I Declaracao de nomes
I A instrucao val vincula um nome a um valorI val distance = time * speed;I Usado na clausula let
let
val pi = 3.14159
in
pi * radius * radius
end;
37 / 53
ML
I ML tem tido um impacto significativo na evolucao daslinguagens de programacao
I Foi uma das linguagens mais estudas em pesquisas
I Originou diversas outras linguagens
I OcamlI F#
I Influenciou
I MirandaI HaskellI Scala
38 / 53
Haskell
Haskell
I Similar a ML: sintaxe parecida, escopo estatico, fortementetipada, e usa o mesmo metodo de inferencia de tipo
I Duas caracterısticas que a diferenciam de ML
I As funcoes Haskell podem ser polimorficasI Usa avaliacao nao estrita
40 / 53
Haskell
I Exemplos de funcoes
fact 0 = 1
fact n = n * fact (n - 1)
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
41 / 53
Haskell
I Guardas podem ser adicionadas as funcoes (expressoescondicionais)
fact n
| n == 0 = 1
| n > 0 = n * fact(n - 1)
sub n
| n < 10 = 0
| n > 100 = 2
| otherwise = 1
I Exemplo de funcao polimorfica
square x = x * x
42 / 53
Haskell
I Guardas podem ser adicionadas as funcoes (expressoescondicionais)
fact n
| n == 0 = 1
| n > 0 = n * fact(n - 1)
sub n
| n < 10 = 0
| n > 100 = 2
| otherwise = 1
I Exemplo de funcao polimorfica
square x = x * x
42 / 53
Haskell
I Listas
I Especificadas com colchetesI Concatenacao ++I Cons infixo :I Serie aritmetica ..
I Exemplos
# 5:[2, 7, 9]
[5, 2, 7, 9]
# [1, 3..11]
[1, 3, 5, 7, 9, 11]
# [1, 3, 5] ++ [2, 4, 6]
[1, 3, 5, 2, 4, 6]
product [] = 1
product (a:x) = a * product x
fact n = product [1 .. n]
43 / 53
Haskell
I Listas
I Especificadas com colchetesI Concatenacao ++I Cons infixo :I Serie aritmetica ..I Exemplos
# 5:[2, 7, 9]
[5, 2, 7, 9]
# [1, 3..11]
[1, 3, 5, 7, 9, 11]
# [1, 3, 5] ++ [2, 4, 6]
[1, 3, 5, 2, 4, 6]
product [] = 1
product (a:x) = a * product x
fact n = product [1 .. n]
43 / 53
Haskell
I List comprehentions
I Descreve a criacao de listas a partir de outras listasI Sintaxe [body | qualifiers]
I Exemplos
[n * n * n | n <- [1..50]]
factors n = [i | i <- [1..n ‘div‘ 2], n ‘mod‘ i==0]
sort [] = []
sort (h:t) = sort [b | b <- t, b <= h]
++ [h] ++
sort [b | b <- t, b > h]
44 / 53
Haskell
I List comprehentions
I Descreve a criacao de listas a partir de outras listasI Sintaxe [body | qualifiers]I Exemplos
[n * n * n | n <- [1..50]]
factors n = [i | i <- [1..n ‘div‘ 2], n ‘mod‘ i==0]
sort [] = []
sort (h:t) = sort [b | b <- t, b <= h]
++ [h] ++
sort [b | b <- t, b > h]
44 / 53
Haskell
I List comprehentions
I Descreve a criacao de listas a partir de outras listasI Sintaxe [body | qualifiers]I Exemplos
[n * n * n | n <- [1..50]]
factors n = [i | i <- [1..n ‘div‘ 2], n ‘mod‘ i==0]
sort [] = []
sort (h:t) = sort [b | b <- t, b <= h]
++ [h] ++
sort [b | b <- t, b > h]
44 / 53
Haskell
I Avaliacao atrasada
I Uma linguagem e estrita se ela requer que todos os parametroreais sejam completamente avaliados
I Uma linguagem e nao estrita se nao tem este requisitoI Uma forma de avaliacao utilizada pelas linguagens nao estritas
e a avaliacao atrasadaI Na avaliacao atrasada, uma expressao so e avaliada se e
quando seu valor for necessarioI Dificulta pensar sobre a quantidade de recursos usados pelo
programaI Exemplos
positives = [0..]
evens = [2, 4..]
squares = [n * n | n <- positives]
member squares 16
I Como implementar a a funcao member?
45 / 53
Haskell
I Avaliacao atrasada
I Uma linguagem e estrita se ela requer que todos os parametroreais sejam completamente avaliados
I Uma linguagem e nao estrita se nao tem este requisitoI Uma forma de avaliacao utilizada pelas linguagens nao estritas
e a avaliacao atrasadaI Na avaliacao atrasada, uma expressao so e avaliada se e
quando seu valor for necessarioI Dificulta pensar sobre a quantidade de recursos usados pelo
programaI Exemplos
positives = [0..]
evens = [2, 4..]
squares = [n * n | n <- positives]
member squares 16
I Como implementar a a funcao member?
45 / 53
Haskell
I Avaliacao atrasada
I Uma linguagem e estrita se ela requer que todos os parametroreais sejam completamente avaliados
I Uma linguagem e nao estrita se nao tem este requisitoI Uma forma de avaliacao utilizada pelas linguagens nao estritas
e a avaliacao atrasadaI Na avaliacao atrasada, uma expressao so e avaliada se e
quando seu valor for necessarioI Dificulta pensar sobre a quantidade de recursos usados pelo
programaI Exemplos
positives = [0..]
evens = [2, 4..]
squares = [n * n | n <- positives]
member squares 16
I Como implementar a a funcao member?
45 / 53
Haskell
I Definicao da funcao member
member [] n = False
member (h:xs) n = (h == n) || member xs n
I Problema: esta definicao pode gerar um laco infinito!
member2 [] n = False
member2 (h:xs) n
| h < n = member2 xs n
| h == n = True
| otherwise = False
I Esta versao funciona corretamente
46 / 53
Haskell
I Definicao da funcao member
member [] n = False
member (h:xs) n = (h == n) || member xs n
I Problema: esta definicao pode gerar um laco infinito!
member2 [] n = False
member2 (h:xs) n
| h < n = member2 xs n
| h == n = True
| otherwise = False
I Esta versao funciona corretamente
46 / 53
Haskell
I Definicao da funcao member
member [] n = False
member (h:xs) n = (h == n) || member xs n
I Problema: esta definicao pode gerar um laco infinito!
member2 [] n = False
member2 (h:xs) n
| h < n = member2 xs n
| h == n = True
| otherwise = False
I Esta versao funciona corretamente
46 / 53
Haskell
I Definicao da funcao member
member [] n = False
member (h:xs) n = (h == n) || member xs n
I Problema: esta definicao pode gerar um laco infinito!
member2 [] n = False
member2 (h:xs) n
| h < n = member2 xs n
| h == n = True
| otherwise = False
I Esta versao funciona corretamente
46 / 53
Aplicacoes das linguagens funcionais
Aplicacoes das linguagens funcionais
I Lisp e usado em programas de inteligencia artifical e comouma linguagem de extensao
I Lisp: emacs, macsyma (maxima), AutoCAD
I Scheme e utilizado para o ensino de programacao funcional
I Haskell: darcs, pugs
I Outras linguagens: Clojure, Erlang, Scala
48 / 53
Comparacao entre as linguagens funcionais eimperativas
Comparacao entre as linguagens funcionais e imperativas
I Linguagens imperativas
I Execucao eficiente (nem sempre)I Semantica complexaI Sintaxe complexaI Concorrencia e projetada pelo programador
I Linguagens funcionais
I Execucao ineficiente (nem sempre)I Semantica simplesI Sintaxe simplesI Os programas podem automaticamente serem feitos
concorrentes
50 / 53
Comparacao entre as linguagens funcionais e imperativas
int sum_cubes(int n) {int sum = 0;
for (int i = 1; i <= i; i++) {sum += i * i * i
}return sum
}
sum_cubes n = sum (map (^3) [1..n])
51 / 53
Referencias
Referencias
I Robert Sebesta, Concepts of programming languages, 9a
edicao. Capıtulo 15.
53 / 53