Paradigmas de Linguagens de Programação - Aula 4

Prévia do material em texto

Paradigmas de Linguagens de Programação
Programação Funcional com linguagem Scheme
PPGCOMP – UNIFACS
Prof. Sergio Martins Fernandes
sergio.fernandes@unifacs.br
71 99958-0897
Tópicos
• Introdução
• Funções matemáticas
• Fundamentos das linguagens de programação funcional 
• A primeira linguagem de programação funcional: LISP
• Uma introdução a Scheme
• Aplicações de linguagens funcionais
• Uma comparação entre linguagens funcionais e imperativas
Introdução
• O projeto das linguagens imperativas é baseado diretamente na 
arquitetura de computadores von Neumann
– Eficiência	é	a	principal	preocupação,	em	vez	da	adequação	da	linguagem	para	
desenvolvimento	de	software
• O projeto das linguagens funcionais é baseado em funções 
matemáticas
– Uma	sólida	base	teórica,	também	próxima	do	usuário,	mas	relativamente	
despreocupada	com	a	arquitetura	das	máquinas	em	que	os	programas	serão	
executados
Paradigma funcional versus imperativo
• John Backus, criador do Fortran e de uma linguagem funcional 
– Linguagens	funcionais	são	superiores	às	imperativas,	porque
• São	mais	fáceis	de	entender	durante	e	após	o	desenvolvimento
– Porque	cada	função	pode	ser	compreendida	independentemente	do	contexto
» Não	há	estado,	efeitos	colaterais	da	execução	de	funções
• Característica fundamental do paradigma imperativo
– Linguagens	tem	estado,	representado	pelas	variáveis	do	programa
– Autor	do	programa	e	leitores	devem	entender	os	usos	das	variáveis	e	como	o	
estado	do	programa	muda	ao	longo	da	execução
• Num	programa	complexo,	isso	pode	ser	muito	desafiador
• Linguagens funcionais não têm variáveis nem, 
consequentemente, estado
Algumas linguagens funcionais
• LISP
– Começou	como	uma	linguagem	puramente	funcional
– Ao	longo	dos	anos,	adquiriu	características	imperativas	que	aumentaram	a	eficiência	de	sua	
execução
– Única	linguagem	funcional	que	atingiu	maior	número	de	usuários
– Usada	para
• Representação	de	conhecimento
• Aprendizado	por	máquinas
• Modelagem	da	fala
• COMMON LISP
– Amálgama	de	vários	dialetos	de	LISP	criados	nos	anos	80
• SCHEME
– Pequeno	dialeto	de	LISP,	usada	para	ensino	de	programação	funcional
• ML, Haskell, OCaml, e F#
– Linguagens	funcionais	tipadas
– Geraram	significativa	expansão	das	áreas	em	que	programação	funcional	é	utilizada
• Processamento	de	BDs,	modelagem	financeira,	análise	estatística,	bio informática
Funções matemáticas
• Uma função matemática é um 
mapeamento de membros de um 
conjunto, chamado de conjunto 
domínio, para outro conjunto, 
chamado de conjunto imagem
• O mapeamento é descrito por uma 
expressão ou por uma tabela
• A função aplicada a um elemento 
do conjunto domínio, passado 
como parâmetro para a função, e 
produz um elemento do conjunto 
imagem
Funções matemáticas
• O conjunto domínio pode ser obtido pelo cruzamento de diversos 
conjuntos
• Neste caso haverá vários parâmetros
• Como não têm efeitos colaterais nem dependem de parâmetros 
externos, sempre mapeiam um determinado elemento do conjunto 
domínio no mesmo elemento do conjunto imagem
Funções simples
• Como definir uma função:
– Nome	da	função
– Seguido	de	uma	lista	de	parâmetros	entre	parêntesis
– Seguido	da	expressão	de	mapeamento
– Exemplo:
Cubo(x) = x * x * x
– O	parâmetro	x		representa	qualquer	membro	do	conjunto	domínio,	mas	é	fixo	e	
representa	um	elemento	específico	durante	a	avaliação	da	expressão	da	função.	
– Exemplo
Cubo (2) = 2 * 2 * 2 = 8
Expressões lambda
• Teoria de funções separa o trabalho de definir a função do trabalho de 
nomeá-la
• Uma expressão lambda especifica o parâmetro e o mapeamento de 
uma função com a seguinte forma
l(x) x * x * x
para a função cubo (x) = x * x * x
• Expressões lambda descrevem funções sem nome
• São aplicadas aos parâmetros colocando-se os parâmetros depois da 
expressão
por exemplo, (l(x) x * x * x)(2)
que resulta no valor 8
• Expressões lambda, como outras definições de função, podem ter mais 
de um parâmetro
Formas funcionais
• Uma função de ordem superior, ou forma funcional, é uma 
função que recebe funções como parâmetros ou uma que leva a 
uma função como resultado, ou ambos
Composição de funções
• É uma forma funcional que tem duas ou mais funções como 
parâmetros ou leva a uma função cujo valor é o primeiro 
parâmetro de função real aplicado ao resultado do segundo
Forma: h º f ° g
que significa h (x) º f ( g ( x))
Para f (x) º x + 2 e g (x) º 3 * x,
h º f ° g resulta (3 * x)+ 2
Aplicar-para-todos
• É uma forma funcional que recebe uma única função como um 
parâmetro e produz uma lista de valores obtidos pela aplicação da 
função de cada elemento de uma lista de parâmetros
Forma: a
Para h (x) º x * x
a( h, (2, 3, 4)) resulta (4, 9, 16)
Fundamentos das linguagens de 
programação funcional
• O objetivo do projeto de uma linguagem de programação 
funcional é mimetizar funções matemáticas ao máximo possível
• A abordagem para a solução de problemas é fundamentalmente 
diferente de abordagens usadas com linguagens imperativas
– Em uma linguagem imperativa, as operações são realizadas e os 
resultados são armazenados em variáveis para uso posterior
– Gestão das variáveis é uma preocupação constante e uma fonte de 
complexidade para a programação imperativa
• Em uma linguagem de programação funcional, variáveis não são 
necessárias, e não há comandos de atribuição
Fundamentos das linguagens de 
programação funcional (continuação)
• Por não ter variáveis, construções iterativas não são possíveis 
nas linguagens funcionais
– Pois	as	iterações	são	controladas	por	variáveis
• Repetições devem ser especificadas com recursão, em vez de 
iterações
• Programas são definições de funções e especificações de 
aplicações de funções
• Execuções de programas consistem em avaliar aplicações de 
funções
• Como não há variáveis, a execução de um programa puramente 
funcional não tem estado
Fundamentos das linguagens de 
programação funcional (continuação)
• Transparência referencial – Em uma linguagem de programação 
funcional, a avaliação de uma função sempre produz o mesmo 
resultado, dados os mesmos parâmetros
Linguagem LISP
• Desenvolvida por John McCarthy no MIT em 1959
• Estudar programação funcional via LISP é o mesmo que estudar 
programação imperativa usando FORTRAN
• LISP evoluiu ao longo de meio século, mas não representa os 
conceitos mais recentes de programação funcional
• Exceto a primeira versão, todos os dialetos de LISP incluem 
recursos imperativos, tais como variáveis, comandos de 
atribuição, e iterações
• Apesar disso tudo, os descendentes do LISP original representam 
conceitos bem fundamentados de programação funcional
Tipos de dados e estruturas LISP
• Tipos de objetos de dados: originalmente, apenas átomos e listas
• Lista: coleção de sublistas e/ou átomos, entre parênteses
por exemplo, 
(a b c d)- lista simples
(a (b c) d (e (f g)))– listas aninhadas
lista de 4 elementos: o primeiro é o átomo a, o segundo é a 
sub-lista (b c), o terceiro é o átomo d, e o quarto é a sublista(e 
(f g))
• Originalmente, LISP era desprovida de tipos
• Internamente, as listas são armazenadas como estruturas de lista 
encadeadas, nas quais cada nó possui dois ponteiros e 
representa um elemento
Representação interna de listas em LISP
Interpretador LISP
• A notação lambda é usada para especificar funções e definições 
de funções, mas modificada para permitir nomear funções
por exemplo, se a lista (a b c) é interpretada como dados, é uma simples 
lista de três átomos, a, b e c
Se é interpretada como uma aplicação de função,
significa que a função chamada A é aplicada aos 
dois parâmetros, b e c
Linguagem Scheme
• Scheme é a linguagem que utlizaremos para praticaro paradigma 
funconal, porque:
– É	relativamente	simples
– É	popular	no	ambiente	acadêmico	
– Interpretadores	Scheme	livres	de	custo	são	amplamente	disponíveis
• Apenas será coberta uma pequena parte da linguagem Scheme
– Que	não	inclui	nenhum	recurso	imperativo	da	linguagem
• Aqui será apresentada a versão 4 da linguagem Scheme
Origens de Scheme
• Scheme é um dialeto de LISP que emergiu no meio dos anos 1970, 
projetado para ser mais claro, moderno e simples do que outros dialetos 
de LISP
• Usa apenas escopo estático
• Funções são entidades de primeira classe
– Eles podem ser 
• Valores de expressões
• Elementos de listas
• Passadas como parâmetros
• Retornadas de funções
• Linguagem não tipada, com sintaxe simples
• Código Scheme precisa de poucas modificações para ser transformado 
em LISP
O intepretador Scheme
• Em modo interativo, é um loop infinito de leitura-avaliação-
impressão
• Valores literais são avaliados para eles próprios
• Os parâmetros são avaliados, em nenhuma ordem especial
• Os valores dos parâmetros são substituídos no corpo da função
• O corpo da função é avaliado
• O valor da última expressão no corpo é o valor da função
Funções numéricas primitivas
• Aritmética: +, -, *, /, ABS, SQRT, REMAINDER, MIN, 
MAX
exemplo
Expressão valor
42 42
(* 3 7) 21
(+ 5 7 8) 20
(− 5 6) −1
(− 15 7 2) 6
(− 24 (* 4 3)) 12
Funções numéricas primitivas
• Outras funções:
– MODULO,	ROUND,	MAX,	MIN,	LOG,	SIN,	and SQRT.
• Usa-se letras minúsculas para todas as palavras reservadas e 
funções pré-definidas
– ISSO	DEPENDE	DO	INTERPRETADOR
• Se uma função requer um número fixo de parâmetros, e um 
número distinto desse for fornecido, haverá uma mensagem de 
erro
Definição de função
• Em Scheme, um programa é uma coleção de definições de 
funções. 
• Consequentemente, saber definir essas funções é pré-requisito 
para escrever mesmo os programas mais simples
Definição de função: lambda
• Em Scheme, uma função sem nome inclui a palavra Lambda, e é 
denominada expressão lambda
• Expressões lambda
– Usadas	para	definir	funções	não	nomeadas
– Forma é baseada na notação l
– Utilizam a palavra chave lambda 
por exemplo, (LAMBDA (x) (* x x)
x é chamada de variável vinculada
Definição de função: lambda
• Expressões lambda podem ser aplicadas da mesma maneira que 
as funções nomeadas, ao colocá-las no início de uma lista que 
contenha os parâmetros reais
por exemplo, ((lambda (x) (* x x)) 7)
• No exemplo acima, x é a variável vinculada. Durante a avaliação 
da função, x é vinculada à constante 7
• Expressões lambda podem ter quaisquer número de parâmetros, como no 
exemplo a seguir:
((lambda(a b c x) (+ (* a x x) (* b x) c)) 1 2 3 4)
Nomes em Scheme
• Nomes em Scheme podem consistir de letras, dígitos e caracteres 
especiais, exceto parêntesis
• Não há distinção entre maiúsculos e minúsculos
– Depende	do	interpretador
• Nos	intepretadores que	usamos,	usar	nomes	minúsculos	para	as	funções
• Não devem começar com um dígito
Função de forma especial: define
• A função de forma especial define em Scheme serve a duas 
necessidades fundamentais:
1. Vincular um nome a um valor
por exemplo, (define pi 3.141593)
(define two_pi (* 2 pi))
2. Vincular um nome a uma expressão lambda
por exemplo, (define (square x) (* x x))
(square 5)
– O processo de avaliação para define é diferente! O primeiro parâmetro 
nunca é avaliado. O segundo parâmetro é avaliado e vinculado ao 
primeiro parâmetro. 
Função de forma especial: define
(define pi 3.14159)
(define two_pi (* 2 pi))
• Se as duas expressões acima foram digitadas num interpretador Scheme, e 
depois PI for digitado, será exibido o valor 3.14159
• Caso o valor two_pi seja digitado, será exibido o valor 6.28318
Funções de predicado numéricas
• Uma função de predicado é aquela que retorna uma valor booleano 
((verdadeiro ou falso).
• #T é verdadeiro (true) e #F é falso (false) (às vezes, (), que é uma lista vazia, é 
usado para falso)
• Scheme inclui uma coleção de funções predicado para valores numéricos. 
Algumas delas abaixo
Função Significado
= Igual
(not (= x y)) Náo igual
> Maior que
< Menor que
>= Maior que ou igual a
<= Menor que ou igual a
even? Número é par?
odd? Número é ímpar?
zero? Valor é zero?
Funções de predicado numéricas
• Quando uma lista é interpretada como um booleano, qualquer 
lista vazia é avaliada como falso, e qualquer lista não vazia é 
avaliada como verdadeiro.
Controle de fluxo: if
• A chamada ao seletor de dois caminhos de Scheme, IF, tem a 
forma
(if predicado expressão_então expressão_senão)
por exemplo, 
(if (not (= count 0))
(/ sum count)
0)
Outro exemplo:
(define (factorial n)
(if (<= n 1)
1
(* n (factorial (− n 1)))
))
Controle de fluxo: cond
• O seletor multiplo de Scheme é uma forma especial chamada 
COND
Forma geral:
(COND
(predicado_1 expressão1)
(predicado_2 expressão2)
...
(predicado_n expressão_n)
[(ELSE expressão)]
)
• Retorna o valor da última expressão no primeiro par cujo 
predicado avaliar para true
• Os colchetes indicam que a cláusula ELSE é opcional
Exemplo de cond
(define (compare x y)
(cond
((> x y) “x é maior que y”)
((< x y) “y é maior que x”)
(else “x ey são iguais”)
)
)
Funções de lista
• Um dos usos mais frequentes de linguagens baseadas em LISP é 
o processamento de listas
• Programas SCHEME são interpretados pela função EVAL, que é 
uma função para aplicação de funções
• Quando aplicada a uma função primitiva, EVAL avalia os 
parâmetros da referida função
– Essa	ação	é	necessária	se	os	parâmetros	da	função	forem	eles	próprios	funções
– Se,	por	outro	lado,	um	parâmetro	for	um	elemento	de	dados,	ele	não	deve	ser	
avaliado
– Para	evitar	avaliar	um	parâmetro,	ele	é	atribuído	à	função	QUOTE
– QUOTE	é	necessária	porque,	nas	linguagens	derivadas	de	LISP,	dados	e	código	
têm	a	mesma	forma
(próximo	slide)
Funções de lista: quote
• quote – um parâmetro é passado à função, que simplesmente o 
retorna sem modificações 
– quote é necessário por que o interpretador de scheme, chamado eval, 
sempre avalia parâmetros para aplicações de funções antes de aplicar a 
função. quote é usado para evitar a avaliação de parâmetros quando 
não é apropriado
(quote a) returns a
(quote (a b c)) returns (a b c)
– quote pode ser abreviada precedendo a expressão a ser citada por um 
apóstrofo
'(a b) é equivalente a (quote (a b))
Funções de lista: cons e list
• cons é um construtor de lista primitivo. Ele constrói uma lista a 
partir de seus dois argumentos, o primeiro deles pode ser um 
átomo ou uma lista; o segundo é normalmente uma lista. 
por exemplo, (cons 'A '(B C)) retorna (A B C)
• list é uma função que constrói uma lista a partir de um número 
variável de parâmetros
Funções de lista: cons e list
• Exemplo de funções cons e list
(cons 'a '()) retorna (a)
(cons 'a '(b c)) retorna (a b c)
(cons '() '(a b)) retorna (() a b)
(cons '(a b) '(c d)) retorna ((a b) c d)
(list 'apple 'orange 'grape) retorna (apple orange grape)
Funções de lista: car e cdr
• car retorna o primeiro elemento de uma dada lista de parâmetros
por exemplo, (car '(a b c)) retorna a
(car '((a b) c d)) retorna (a b)
• cdr retorna o restante de uma dada lista após seu car ter sido 
removido
por exemplo, (cdr '(a b c)) retorna (b c)
(cdr '((a b) c d)) retorna (c d)
Funções de lista: car e cdr
• Exemplos de CAR e CDR
(car '(a b c)) retorna a
(car '((a b) c d)) retorna (a b)
(car 'a) gera um erro porque a não é uma lista
(car '(a)) retorna a
(car '()) gera um erro
(cdr '(a b c)) retorna (b c)
(cdr '((a b) c d)) retorna (c d)
(cdr 'a) gera um erro
(cdr '(a)) retorna ()
(cdr '()) é um erro
Funções de lista: car e cdr
• Schemetem variações e combinações dessas duas funções, que são denominadas por
composições das letras A e D no nome da função
• Exemplo:
(caar x)	é	equivalente	a	(car(car x))
(cadr x)	é	equivalente	a	(car (cdr x))
(caddar x)	é	equivalente	a	(car (cdr (cdr (car x))))
(caddar '((a	b (c)	d)	e))	=
(car (cdr (cdr (car '((a	b	(c)	d)	e)))))	=
(car (cdr (cdr '(a	b	(c)	d))))	=
(car (cdr '(b	(c)	d)))	=
(car	'((c)	d))	=
(c)
Funções de predicado de listas e átomos simbólicos
• Scheme tem três funções de predicado fundamentais para átomos e listas 
simbólicos
eq?
null?
list?
Funções de predicado: eq?
• eq? recebe dois átomos simbólicos como parâmetros; retorna #T se 
ambos os parâmetros forem átomos e ambos forem o mesmo; caso 
contrário, retorna #F
por exemplo, (eq? 'A 'A) retorna #T
(eq? 'A 'B) retorna #F
– Nota que, se EQ? é chamada com lista de parâmetros, o resultado não é 
confiável
– eq? também não funciona para átomos numéricos
(eq? 'a 'a) retorna #t
(eq? 'a 'b) retorna #f
(eq? 'a '(a b)) retorna #f
(eq? '(a b) '(a b)) retorna #f ou #t
(eq? 3.4 (+ 3 0.4)) retorna #f ou #t
Funções de predicado: list? e null?
• list? retorna #t se seu único parâmetro é uma lista; caso contrário, 
retorna #f
(list? '(x y)) retorna #t
(list? 'x) retorna #f
(list? '()) retorna #t
• null? testa seu parâmetro para determinar se ela é a lista vazia e 
retorna #t caso seja
– note que null? retorna #t se o parâmetro é ()
(null? '(a b)) retorna #f
(null? '()) retorna #t
(null? 'a) retorna #f
(null? '(())) retorna #f
Exemplos de funções em Scheme: member
• member pega um átomo e uma lista simples; retorna #T se o 
átomo estiver na lista
(define (member atomo lista)
(cond
((null? lista) #F)
((eq? atomo (car lista)) #T)
(else (member atomo (cdr lista)))
))
Usando a função
(member 'B '(A B C)) retorna #T
(member 'B '(A C D E)) retorna #F
Exemplos de funções Scheme: equalsimp
• equalsimp é uma função de predicados para comparar listas 
simples; retorna #T se as duas listas são iguais
(define (equalsimp lis1 lis2)
(cond
((null? lis1) (null? lis2))
((null? lis2) #f)
((eq? (car lis1) (car lis2))
(equalsimp(cdr lis1)(cdr lis2)))
(else #f)
))
Exemplos de funções em Scheme: equal
• equal funciona em qualquer par de expressões, não apenas 
listas
(define (equal lis1 lis2)
(cond
((not (list? lis1))(eq? lis1 lis2))
((not (list? lis2)) #f)
((null? lis1) (null? lis2))
((null? lis2) #f)
((equal (car lis1) (car lis2))
(equal (cdr lis1) (cdr lis2)))
(else #f)
))
Exemplos de funções em Scheme: append
• append pega duas listas como parâmetros; retorna a primeira 
com os elementos da segunda no final
(define (append lis1 lis2)
(cond
((null? lis1) lis2)
(else (cons (car lis1)
(append (cdr lis1) lis2)))
))
Formas funcionais
• Uma forma funcional é a implementação em LISP e seus dialetos 
do conceito matemático de forma funcional, já apresentado aqui
• Scheme permite a aplicação de duas formas funcionais
– Composição	funcional
– Aplicar-para-todos
Formas funcionais – composição
• Exemplo de composição em Scheme
(define (g x) (* 3 x))
(define (f x) (+ 2 x))
• A forma funcional de f e g pode ser escrita como
(define (h x) (+ 2 (* 3 x)))
• Em Scheme, a função de composição funcional compose pode ser escrita da 
seguinte forma:
(define (compose f g) (lambda (x)(f (g x))))
• A aplicação da função composta seria
((compose f g) 5)
Formas funcionais – composição
• Outro exemplo
(define (compose car cdr) (lambda (x) (car (cdr x))))
• Um exemplo de aplicação da função composta seria
((compose car cdr) '((a b) c d))
• Cujo resultado é c
Formas funcionais – aplicar-a-todos
• Aplicar-a-todos – uma forma em Scheme é map
– Aplica uma função dada a todos os elementos de uma lista
(DEFINE (map fun lis)
(COND
((NULL? lis) ())
(ELSE (CONS (fun (CAR lis))
(map fun (CDR lis))))
))
• Um exemplo de aplicação de map é:
(map (LAMBDA (num) (* num num num)) '(3 4 2 6))
• E o resultado seria (27 64 8 216)
Funções que constroem código
• É possível, em Scheme, definir uma função que cria código 
Scheme e solicita a sua interpretação
• Isso é possível com a função eval
Somando uma lista de números
((define (adder lis)
(cond
((null? lis) 0)
(else (eval (cons '+ lis)))
))
• O parâmetro é uma lista de números a ser adicionada; adder
insere um operador + e avalia a lista resultante
– Use cons para inserir o átomo + na lista de números
– Note que o nome da função + é colocado com uma aspa para prevenir 
que eval o avaliasse
– Submeta a nova lista a eval para avaliação
COMMON LISP
• Uma combinação de diversos recursos de dialetos populares de 
LISP dos anos 1980
• Linguagem grande e complexa, o oposto de Scheme
• Recursos incluem:
– registros 
– matrizes 
– números complexos
– cadeias de caracteres
– operações de entrata e saída poderosas
– pacotes para controle de acesso
ML
• Uma linguagem de programação funcional com escopo estático, 
que se difere de LISP e seus dialetos, incluindo Scheme, de 
maneiras significativas
• Usa declarações de tipo, mas também inferências de tipos para 
determinar os tipos de variáveis não declaradas
• É fortemente tipada (Scheme é essencialmente desprovida de 
tipos)
• Inclui tratamento de exceções e um recurso de módulo para 
implementar tipos de dados abstratos
• Inclui listas e operações de listas
ML
• Forma das declarações de funções:
fun nome_da_função (parâmetros_formais) = 
expressão_corpo_da_função;
por exemplo, fun cube (x : int) = x * x * x;
– O tipo do valor de retorno pode ser especificado após a lista de 
parâmetros, como em
fun cube (x) : int = x * x * x;
– O tipo do valor de retorno não precisa ser explicitamente especificado
– Funções definidas pelo usuário sobrecarregadas não são permitidas; se 
quisermos uma função cube para valores de tipo real, precisamos defini-
la com outro nome
ML
• Seleção em ML
if expressão then expressão_então
else expressão_senão
onde a primeira expressão deve avaliar para um valor booleano
• Usando casamento de padrões, a função fatorial poderia ser 
escrita como 
fun fact(0) = 1
| fact(n : int) : int = 
n * fact(n – 1)
ML
• Listas
Listas são especificadas entre colchetes
[3, 5, 7]
[] é uma lista vazia
CONS é um operador infixo binário, ::
4 :: [3, 5, 7], que avalia para [4, 3, 5, 7]
CAR é o operador unário hd
CDR é o operador unário tl
fun length([]) = 0
| length(h :: t) = 1 + length(t);
fun append([], lis2) = lis2
| append(h :: t, lis2) = h :: append(t, lis2);
ML
• A sentença val vincula um nome a um valor (similar a DEFINE
em Scheme)
val distance = time * speed;
– Assim como DEFINE, val é completamente diferente de uma sentença de 
atribuição em uma linguagem imperativa
Haskell
• Similar a ML (usa uma sintaxe similar, tem escopo estático, é 
fortemente tipada e usa o mesmo método de inferência)
• Diferente de ML (e outras linguagens funcionais) no que é 
puramente funcional
Diferenças de sintaxe
fact 0 = 1
fact n = n * fact (n – 1)
fib 0 = 1
fib 1 = 1
fib (n + 2) = fib (n + 1) + fib n
Listas
• Notação de lista: coloca os elementos entre colchetes
por exemplo, directions = ["north", 
"south", "east", "west"]
• Comprimento: #
por exemplo, #directions é 4
• Séries aritméticas com o operador .. 
por exemplo, [2, 4..10] is [2, 4, 6, 8, 10]
• Concatenação é com ++
por exemplo, [1, 3] ++ [5, 7] resulta [1, 3, 5, 7]
• CONS, CAR, CDR com o operador dois pontos (como em 
Prolog)
por exemplo, 1:[3, 5, 7] resulta [1, 3, 5, 7]
Função fatorial
product [] = 1
product (a:x) = a * product x
fact n = product [1..n]
Aplicações das linguagens funcionais
• APL é usada para programas “descartáveis”
•LISP é usada para inteligência artificial
– Representação do conhecimento
– Aprendizado de máquina
– Processamento de linguagem natural
– Modelo de fala e visão
• Scheme é usada para ensinar programação introdutória em 
algumas universidades
Exercício 
O Que faz a função abaixo?
(define (y s lis)
(cond
((null? lis) '() )
((equal? s (car lis)) lis)
(else (y s (cdr lis)))
))
Exercício 
O Que faz a função abaixo?
(DEFINE (d atm lst)
(COND
((NULL? lst) '())
((EQ? atm (CAR lst)) (d atm (CDR lst)))
(ELSE (CONS (CAR lst) (d atm (CDR lst)))
))
)
Exercício 
O Que faz a função abaixo?
(DEFINE (r lis)
(COND 
((NULL? lis) '())
(ELSE (APPEND (r (CDR lis)) (CONS (CAR lis) '() )))
))
Comparando linguagens funcionais 
e imperativas
• Linguagens imperativas:
– Execução eficiente
– Semântica complexa
– Sintaxe complexa
– Concorrência é projetada pelo programador
• Linguagens funcionais:
– Semântica simples
– Sintaxe simples
– Execução ineficiente
– Programas podem ter concorrência automaticamente
Resumo
• Funções matemáticas são mapeamentos nomeados ou não nomeados que usam 
apenas expressões condicionais e recursão para controlar suas avaliações
• LISP iniciou como uma linguagem puramente funcional, mas logo teve adicionados 
recursos de linguagens imperativas
• Scheme é um dialeto relativamente simples de LISP que usa exclusivamente 
escopo estático
• COMMON LISP é uma grande linguagem baseada em LISP
• ML é uma linguagem de programação funcional de escopo estático e fortemente tipada
que usa uma sintaxe que é mais fortemente relacionada à de uma linguagem imperativa 
do que à de LISP
• Haskell é similar a ML, exceto que todas as expressões em Haskell são avaliadas 
usando um método preguiçoso, que permite que os programas lidem com listas infinitas
• Apesar de poderem existir vantagens nas linguagens funcionais puras sobre as 
imperativas, sua velocidade de execução mais lenta em máquinas von Neumann 
preveniu que fossem consideradas por muitos como substitutas das imperativas