60
Programação Funcional

Programação funcional

Embed Size (px)

Citation preview

Page 1: Programação funcional

Programação Funcional

Page 2: Programação funcional

Paradigma de Programação Funcional

• Estuda-se paradigmas de programação comparando-se com o procedimental, pois– Foi o primeiro paradigma– É o mais difundido– Há algo com o qual comparar-se

Page 3: Programação funcional

paradigma de Programação Procedimental

• Sequência de comandos permite a transição de um estado da máquina a outro

• Estado da máquina– Conjunto de valores que define a

situação ou comportamento de um sistema

• Exemplo– Estado1, (1, 2); estado2, (1, -4)

Page 4: Programação funcional

paradigma de Programação Procedimental

• Transição de estado

σ 0→ σ1→ σ2→ .. .→σ nint fact(int n)

{ int x = 1; while (n > 0) { x = x * n; n = n - 1; } return x;}

Um programa C

Page 5: Programação funcional

paradigma de Programação Procedimental

Estado(n, x)

Comando Comentário

(6, 1) Estado inicial, (6, 6) x = 1 × 6 2o estado, (5, 6) n = 6 − 1 3o estado, (5, 30) x = 6 × 5 4o estado, (4, 30) n = 5 − 1 5o estado, (4, 120) x = 30 × 4 6o estado, (3, 120) n = 4 − 1 7o estado, (3, 360) x = 120 × 3 8o estado, (2, 360) n = 3 − 1 9o estado, (2, 720) x = 360 × 2 10o estado, (1, 720) n = 2 − 1 11o estado, (1, 720) x = 720 × 1 12o estado,

Page 6: Programação funcional

paradigma de Programação Procedimental

• O conceito de estado está vinculado, implicitamente, ao paradigma de programação procedimental

• Não possuindo significado explícito nos demais paradigmas

Page 7: Programação funcional

paradigma Funcional• Um programa é simplesmente uma

função, ou expressão, daí o nome• Sua execução significa a avaliação

dessa função• Comparando com o procedimental,

onde f é a função (programa)

σ n =f (σ 0 )

Page 8: Programação funcional

paradigma Funcional

• Exemplo– O mesmo problema do fatorial de n,

n!– Em linguagem funcional fatorial (n) = prod [1..n]

• Veja que não faz sentido algum o conceito de estado da máquina

Page 9: Programação funcional

paradigma Funcional

• Sob essa visão– Não há estados– Não há atribuições– Não há sequência de comandos– Não há repetições

• Mas há recursão e funções de alta ordem

Page 10: Programação funcional

paradigma Funcional

• Pode parecer impraticável uma linguagem sem– Variáveis– Atribuições– Sequência de comandos

• Como visto aqui, isso não é verdade

• Pelo contrário: facilita em muitos casos

Page 11: Programação funcional

A linguagem LISP

• Principais ideias que sustentam o paradigma de programação funcional, datam da década de 30– Cálculo Lâmbda: um formalismo

matemático criado por Alonzo Church

• A mais antiga implementação foi LISP, desenvolvida por McCarthy na segunda metade da década de 50

Page 12: Programação funcional

A linguagem LISP

• Vamos às suas principais características

• Tipos de dados– O átomo e a lista– É com apenas esses dois tipos de dados

que se constroem as expressões-S, as estruturas básicas de LISP

Page 13: Programação funcional

Exemplos de átomos

• atom– É um átomo, pois é um string de

caracteres que começa com a letra a.Nota: Em algumas implementações, escreve-se: (quote atom), ou 'atom.

• carnaval– É um átomo, pois é um string de

caracteres que começa com uma letra.

Page 14: Programação funcional

Exemplos de átomos• 1500

– É um átomo, pois é um string de caracteres que começa com um dígito.

• 150carnavais– É um átomo, pois é um string de

caracteres que começa com um dígito.• b

– É um átomo, pois é um string de 1 caracter começando com letra ou dígito.

Page 15: Programação funcional

Exemplos de átomos• *figueirense$

– É um átomo, pois é um string de caracteres que começa com uma letra, um dígito ou um caracter especial que não é abre parênteses, (, ou fecha parênteses, ).

• 6!– É um átomo, pois é um string de caracteres

que começa com uma letra, um dígito ou um caracter especial que não é abre parênteses, (, ou fecha parênteses, ).

Page 16: Programação funcional

Exemplos de listas• (atom)

– É uma lista: um átomo entre parênteses• (atom carnaval 1500)

– É uma lista: coleção de átomos entre parênteses.

• (atom carnaval) 1500– Não é uma lista: duas expressões-S que

não estão entre parênteses. A primeira é uma lista e a segunda é um átomo

Page 17: Programação funcional

Exemplos de listas

• ((atom carnaval) 1500)– É uma lista, pois as duas expressões-

S estão entre parênteses. A primeira é uma lista e a segunda é um átomo

Page 18: Programação funcional

Expressão-S (S-expresssion)

• jbma– É uma expressão-S, pois todo átomo é

uma expressão-S

• (j b m a)– É uma expressão-S, pois é toda lista é

uma expressão-S

• ((j b m) a)– É uma expressão-S, pois é uma lista

Page 19: Programação funcional

Expressão-S

• ((j b m) a)– Nessa lista há duas expressões-S. A

lista (j b m) e o átomo a

Page 20: Programação funcional

Expressão-S

• ( )– É uma lista, pois contém zero

expressões-S. Essa expressão-S especial é chamada de lista nula ou lista vazia, as vezes chamada, também, nil

• ( )– É um átomo, pois ( ) é ambos, uma lista

e um átomo

Page 21: Programação funcional

Expressão-S

• ( ( ) ( ) ( ) ( ) )– É uma lista, pois é uma coleção de

expressões-S entre parênteses

Page 22: Programação funcional

Representação de funções

• LISP– Processamento de listas– Representa funções através de listas– O nome da função é sempre o

primeiro elemento da lista

Page 23: Programação funcional

Função universal como interpretador LISP

• Na Teoria da Computação, é comum investigar funções universais

• Exemplo, a máquina universal de Turing– É uma máquina de Turing que pode

simular qualquer outra máquina de Turing que voce possa descrever

• McCarthy fez exatamente isso com LISP

Page 24: Programação funcional

Função universal como interpretador LISP

• Definiu uma função universal LISP– Que poderia interpretar qualquer outra

função LISP

• Em outras palavras– Escreveu um interpretador LISP, em LISP

• Como LISP manipula apenas listas– Escrever uma função universal iria

requerer desenvolver-se uma forma de representar programas LISP como estruturas de listas

Page 25: Programação funcional

Função universal como interpretador LISP

• Exemplof(x+y; u*z)

• Pode ser representada na forma de lista

(f (+ x y) (* u z))

• Em Algol, esse artifício era chamado de Expressão-M (M-Expression)

• Aqui, M significava metalangue (metalinguagem)

Page 26: Programação funcional

Função universal como interpretador LISP

• Em LISP, a expressão acima passou a ser chamada de Expressão-S (S-Expression)

• Em LISP, S siginificava simbolic language (linguagem simbólica)

• Nesse momento, um dos membros do grupo constatou que tinham em mãos, de fato, um interpretador

Page 27: Programação funcional

Função universal como interpretador LISP

• Traduziram a função universal para Assembly e a linkaram com as sub-rotinas de manuseio de listas

• E esse foi o primeiro sistema LISP• LISP tornou-se a principal

linguagem para IA, até os anos 70

Page 28: Programação funcional

Funções em LISP

• f(x,y), na notação usual matemática– (f x y)– Nome da função, f, como o primeiro

elemento e os demais elementos, x e y, representam os seus argumentos

• (nome-da-funcao arg1 arg2 ...)

Page 29: Programação funcional

Funções em LISP

• 3*7, usando-se a notação infixa • Em LISP, notação pré-fixa

– (* 3 7)

Page 30: Programação funcional

Funções em LISP• A origem do nome LISP

– LISt Processing (processamento de listas)– Exemplos de execução LISP

> (+ 3 4) ; operador adição

7 ; retorno da função

> (- 6 4) ; operador subtração

2 ; retorno da função

> (car '(6 4)) ; função car6 ; retorno da função

> (cdr '(6 4)) ; função cdr(4) ; retorno da função

Page 31: Programação funcional

Funções em LISP• Importante!! Toda vez que você fornece

uma lista, a executa, a menos que você o alerte para não o fazer

• Por exemplo, se você fornecer a lista (6 5 7) e a mandar executar, LISP irá retornar mensagem de erro– 6 não é uma função

• Como alertá-lo, então?

Page 32: Programação funcional

Funções em LISP• Em um dos exemplos acima,

solicitou-se a execução de > (car '(6 4))• Veja que a lista que é fornecida

como argumento da função car é precedida pelo símbolo “ ’ ”

• Esse é o alerta: proibido avaliar

Page 33: Programação funcional

Alguns Exemplos de Funções em LISP

Page 34: Programação funcional

Car / cdrLista = (moto onibus carro trator)

>(cdr ‘(moto onibus carro trator))

(onibus carro trator)

>(cdr ‘(onibus carro trator))

(carro trator)

>(car ‘(carro trator)

carro

>(car (cdr (cdr ‘(moto onibus carro trator)))

((moto onibus) (carro trator))

Page 35: Programação funcional

Car / cdr

>(cdr ‘((moto onibus) (carro trator)))

((carro trator))

>(car ‘((carro trator)))

(carro trator)

>(car ‘(carro trator))

carro

>(car(car(cdr ‘((moto onibus) (carro trator))))) (((moto) (onibus) (carro) (trator)))

Page 36: Programação funcional

Car / cdr

>(car ‘(((moto) (onibus) (carro) (trator)))) ((moto) (onibus) (carro) (trator))>(cdr ‘((moto) (onibus) (carro) (trator))) ((onibus) (carro) (trator))>(cdr ‘((onibus) (carro) (trator))) ((carro) (trator))>(car ‘((carro) (trator))) (carro)>(car ‘(carro)) carro

Page 37: Programação funcional

Exercicio

Escreva seqüências de cars e cdrs que pegam o símbolo pêra nas seguintes expressões:

(maçã laranja pêra uva)

((maçã laranja) (pêra uva))

(((maçã) (laranja) (pêra) (uva)))

(maçã (laranja) ((pêra)) (((uva))))

((((maçã))) ((laranja)) (pêra) uva)

((((maçã) laranja) pêra) uva)

Page 38: Programação funcional

butlast sintaxe: (bustlast <lista> [<n>])

retorna a copia dos elementos da lista, removendo os n finais

>(butlast ‘(a b c d e) 2)

(A B C)

>(butlast ‘(a b c d e) )

(A B C D)

Page 39: Programação funcional

length sintaxe: (length <expr>)

Retorna o tamanho de uma lista

>(length ‘(a b c d e))

5

>(length ‘((a b c) (d e)))

2

Page 40: Programação funcional

Predicados

Page 41: Programação funcional

atom sintaxe: (atom <expr>)

retorna true se <expr> for atomo;

nil, caso contrario

>(atom 3)

T

>(atom ‘carro)

T

>(atom ‘(a b))

nil

Page 42: Programação funcional

symbolp sintaxe: (symbolp <expr>)

retorna true se <expr> for simbolo

nil, caso contrario

>(symbolp 3) >(symbolp ‘())

NIL T

>(symbolp ‘aaa)

T

Page 43: Programação funcional

null sintaxe: (null <expr>)

retorna true se <expr> for lista vazia ou atomo “nil”

nil, caso contrário

>(null 3) >(null ‘())

nil T

>(null nil) >(null ‘(a b))

T nil

Page 44: Programação funcional

Condicional• if sintaxe: (if <texpr> <expr1> [<expr2>])

ex1: (if (> 3 2) 3 2)

Ex2: calculo da raiz de um numero

(defun raiz (x &optional n)

(if n (expt x (/ 1 n))

(sqrt x)))

Page 45: Programação funcional

Condicional

(defun nummax (a b c)

(if (> a b)

(if (> a c) a c)

(if (> b c) b c)))

Page 46: Programação funcional

Condicional - condSintaxe: (cond <par1> ...)>(defun abs (x) (cond ((< x 0) (* x -1)) ((> x 0) x) ) )

Page 47: Programação funcional

Condicional - case

Sintaxe: (case <expr> <case>..)>(defun areafig (name raio) (case name (circulo (* pi raio raio)) (esfera (* 4 pi raio raio)) (t 0)))AREAFIG>(areafig ‘esfera 2)

Page 48: Programação funcional

Let – atribui valores

Ex: obtencao do primeiro e do ultimo elemento de uma lista

>(defun primeiroultimo (Lista) (let ((primeiro (first Lista)) (ultimo (last Lista))) (cons primeiro ultimo)))PRIMEIROULTIMO

>(primeiroultimo ‘(Joao Paulo Ana))(Joao Ana)

Page 49: Programação funcional

Passagem de Parâmetros – parâmetros são locais

>(setq x 1)>(setq y 2)>(defun f1 (x y) (setq x y) (print x))F1>(f1 3 4)4>x1

>(setq x 3)>(setq y 7)>(defun f2 ()

(setq x y) (print x))F2>(f2)7>x7

Page 50: Programação funcional

Do

>(defun melevadon (m n) (do ((result 1) ;inicia

(expoente n) ;inicia

) ((zerop expoente) result) ;teste

(setf result (* m result)) ; corpo

(setf expoente (- expoente 1)) ))

Page 51: Programação funcional

Do>(defun fatorial (n)

( do ( (result 1 (* n result)) ;inicia/corpo

(n n (- n 1))

)

((zerop n) result) ;teste

)

)

FATORIAL

>(fatorial 4)

24

Page 52: Programação funcional

>(defun fatorial (n) (if (or (= n 1) (= n 0)) 1 (* n (fatorial (- n 1))) ) ) FATORIAL>(fatorial 4)24

Page 53: Programação funcional

>(defun quantos (L) (cond ((null L) 0) (T (+ 1 (quantos (cdr L)) ) ) ) )QUANTOS>(quantos ‘(5 4 9 29))4

Page 54: Programação funcional

Inversão de lista>(defun invertelista (lista-inicial)

(do (

( l lista-inicial (rest l)) ;inicia/corpo

(result nil (cons (first l) result))

)

((endp l) result) ; teste

)

)

INVERTELISTA

>(invertelista ‘(a b c d))

(d c b a)

Page 55: Programação funcional

Exercicios resolvidosFunção que soma todos os números de uma lista.

(defun somalista (x)

(if (null x) 0 (+ (car x) (somalista (cdr x)))))

SOMALISTA

> (somalista '(10 20 30))

60

> (somalista '(200 20 30))

250

Page 56: Programação funcional

Exercicios resolvidosFunção que recebe saldo atual e valor retirada. Retornar o

saldo final.

>Chamada da função: (retirada S V)

>Exemplo:(retirada 100 10)

> (defun retirada (S V) (- S V))

RETIRADA

> (retirada 100 5)

95

Page 57: Programação funcional

Exercicios resolvidosFaça uma função que receba saldo atual, limite e valor retirada. Retorne uma lista

contendo dois valores: o saldo final e um valor booleano (t ou nil) que indique se a retirada for possível. Chamada da função: (retirada S L V)

>Exemplo:(retirada 100 50 10) resulta em (50 t)

>Exemplo:(retirada 100 50 200) resulta em (100 nil)

>Exemplo:(retirada 100 50 150) resulta em (-50 nil)

> (defun retir (S L V)

(if (> (+ S L) V) (list T (- S V)) (list nil (- S V))))

RETIR

> (retir 100 50 149)

(T -49)

> (retir 100 50 151)

(NIL -51)

> (retirada 100 10)

90

Page 58: Programação funcional

Exercicios resolvidosFunção que receba uma lista na seguinte forma:

( (<pessoa> ( <horas> <valor hora> ) ) ... )

e imprime o salario de todas as pessoas que será (4.5 * horas * valor hora).

Exemplo da lista:

>Chamada da função: (salarios L).

>Exemplo: (salario ( (joao (40 10)) (maria (20 50)) (pedro (30 25))))

> (defun salario (x)

(if (null x) 0

((salario (cdr x)) (print (* 4.5 (* (car(cdr(car x))) (cdr(cdr(car x))))))))

)

SALARIO

Page 59: Programação funcional

Outras Linguagens FuncionaisLISP 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

Page 60: Programação funcional

ResumoFunçõ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

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