Linguagens de programação funcional - Linguagens de … · Linguagens de programa˘c~ao funcional Linguagens de Programac~ao Marco A L Barbosa Este trabalho est a licenciado com

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

malbarbo.pro.br

http://creativecommons.org/licenses/by-sa/4.0/

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










4 / 53










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 h ≡ f ◦ g , h(x) ≡ f (g(x))




8 / 53

Funcoes matematicas

I Formas funcionais




I h ≡ f ◦ g , h(x) ≡ f (g(x))




8 / 53

Fundamentos das linguagens de programacaofuncionais


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









10 / 53









10 / 53


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


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


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


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










16 / 53










16 / 53



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


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


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


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


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


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


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


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


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


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


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


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


I Exemplo




fun fact(0) = 1


35 / 53

ML

I Controle de fluxo


I Exemplo




fun fact(0) = 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 Descreve a criacao de listas a partir de outras listasI Sintaxe [body | qualifiers]I Exemplos

[n * n * n | n <- [1..50]]


sort [] = []


++ [h] ++

sort [b | b <- t, b > h]

44 / 53

Haskell


I Descreve a criacao de listas a partir de outras listasI Sintaxe [body | qualifiers]I Exemplos

[n * n * n | n <- [1..50]]


sort [] = []


++ [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






programaI Exemplos

positives = [0..]

evens = [2, 4..]


member squares 16


45 / 53

Haskell






programaI Exemplos

positives = [0..]

evens = [2, 4..]


member squares 16


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


member [] n = False




member2 (h:xs) n


| h == n = True

| otherwise = False


46 / 53

Haskell


member [] n = False




member2 (h:xs) n


| h == n = True

| otherwise = False


46 / 53

Haskell


member [] n = False




member2 (h:xs) n


| h == n = True

| otherwise = False


46 / 53



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


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


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

Documents

Linguagens de programação funcional - Linguagens de … · Linguagens de programa˘c~ao funcional Linguagens de Programac~ao Marco A L Barbosa Este trabalho est a licenciado com