Programação funcional

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

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)

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

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,

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

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 )

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

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

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

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

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

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.

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.

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, ).

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

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

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

Expressão-S

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

lista (j b m) e o átomo a

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

Expressão-S

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

expressões-S entre parênteses

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

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

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

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)

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

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

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 ...)

Funções em LISP

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

– (* 3 7)

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

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?

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

Alguns Exemplos de Funções em LISP

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))

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)))

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

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)

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)

length sintaxe: (length <expr>)

Retorna o tamanho de uma lista

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

5

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

2

Predicados

atom sintaxe: (atom <expr>)

retorna true se <expr> for atomo;

nil, caso contrario

>(atom 3)

T

>(atom ‘carro)

T

>(atom ‘(a b))

nil

symbolp sintaxe: (symbolp <expr>)

retorna true se <expr> for simbolo

nil, caso contrario

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

NIL T

>(symbolp ‘aaa)

T

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

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)))

Condicional

(defun nummax (a b c)

(if (> a b)

(if (> a c) a c)

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

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

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)

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)

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

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)) ))

Do>(defun fatorial (n)

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

(n n (- n 1))

)

((zerop n) result) ;teste

)

)

FATORIAL

>(fatorial 4)

24

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

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

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)

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

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

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

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

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

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