Aula_07_-_Linguagem_Funcional

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Clique para editar o estilo do título mestre
Clique para editar o estilo do subtítulo mestre
*
*
*
Cap 04 - Linguagem Funcional
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Linguagem Funcional
Principal conceito de programação: a abordagem das estruturas de dados (“objetos”) do programa fonte como funções matemáticas.
As funções podem ser: passadas como argumentos; retornadas como resultado; guardadas como valores de variáveis; definidas recursivamente; utilizadas como veículos de modularização.
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Programação funcional
A programação funcional é um estilo - paradigma - de programação que
 enfatiza a avaliação de expressões
 não utiliza comandos e algoritmos (seqüência de comandos)
não utiliza variáveis e atribuições (transparência referencial) 
exige bastante disciplina de programação
produz programas que podem ser mais facilmente verificados
Uma notação para se ler, escrever e executar computações.
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
LPF -Linguagens de Programação Funcionais
Objetivo: assemelhar-se ao máximo possível a funções matemáticas
Em uma LPF, a avaliação de uma função sempre produz o mesmo resultado a partir dos mesmos parâmetros
independente de contexto e execuções anteriores
transparência referencial: não existe o conceito de referência a variável
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Linguagens imperativas: baseadas em alterações de variáveis
	Ex: f := (x + y) / (a - b) 		Variáveis
						x, y, a, b, f
						
Linguagens funcionais: não utilizam variáveis e comandos de atribuição
É feita uma associação nome  valor e não uma atribuição
A cada associação, um novo identificador é criado (sem relação com outros de mesmo nome)
Exemplo ML: variáveis são similares a constantes em PASCAL
 val x = 17		val x = 17 : int
 val x = true		val x = true : bool
 val z = x		val z = true : bool
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Fundamentos de LPF : computações
O processo básico de computação de uma LPF é fundamentalmente diferente de uma LPI
em uma LPI as operações consistem de transformações sobre valores armazenados em variáveis (atribuição)
em uma LPI, o controle de variáveis e seus valores é uma preocupação constante e fonte de complexidade (depuração)
em uma LPF, assim como em matemática, variáveis não são necessárias (somente valores e resultados)
em uma LPF não existem comandos de controle de fluxo de execução
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Abstração de função
Exemplo em Pascal
function pot (x:real;n:integer): real;
 begin (* supor n>0 *)
 if n=1	then 
 pot := x
 else 
	 pot := x * pot(x, n-1) 
end;
Exemplo em ML
fun pot (x:real, n:int) =
	if n = 1 then x
	else x * pot(x, n-1);
Simples e concisa
Nome da função: significado único 
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Imperativo x Funcional: resumo
Modelo imperativo
Projeto baseado diretamente na arquitetura de von Neumann
células de memória
seqüência de execução de ações
Preocupação com eficiência
Linguagens de uso geral, sem preocupação com desenvolvimento de software em domínios específicos
Modelo Funcional
Projeto baseado em funções matemáticas
Forte embasamento teórico
cálculo Lambda
Existe preocupação com eficiência de execução 
forma de avaliação tardia
paralelismo
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Imperativo x Funcional: resumo
Modelo imperativo
programa: seqüência de comandos que transformam variáveis
base: variáveis, comandos, procedures
execução: conceito de seqüência
variáveis: mudanças de estado, alteração por atribuição
estado: implícito, modificado por atribuições
componentes de primeira classe: variáveis
Modelo Funcional
programa: é uma função composta por funções mais simples
base: expressões, funções
execução: baseada em recursividade
nomes identificam valores permanentes (const), transparência referencial 
estado: explícito, modificado por funções
componentes de primeira classe: funções
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Sobre ML
ML denomina uma família de linguagens de programação funcionais : ML, SML, SML/NJ, CAML, EML, e outras
http://www.cl.cam.ac.uk/users/lcp/MLbook/general.html
O nome ML provém originalmente de Meta-Language
Padronizada como SML em 1990, revisada em 1997: SML'97 
ML é uma linguagem declarativa e não uma linguagem procedural
A ausência da semântica de VonNeumann torna as linguagens funcionais desafiadoras para programadores
Programas funcionais são muito mais adequados para análise formal e provas de correção
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
ML: arquivos e bibliotecas
ML oferece suporte para arquivos e entrada saída em redes
Todos os sistemas SML compartilham uma mesma biblioteca de funções e módulos: a SML Basis Library. 
A biblioteca básica fornece várias formas de tratamento de dados, E/S, e funções de interface com SO
Possui um sofisticado sistema de tipos, incluindo tipos genéricos e oferece suporte a polimorfismo
A implementação para a plataforma .NET oferece interoperabilidade com programas escritos em outras linguagens de programação e compartilhamento de bibliotecas 
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
ML: mais características
ML é uma linguagem funcional pura, no sentido de:
não é permitido atribuição à memória
o programador declara funções e faz referência a valores
Oferece o suporte para:
recursividade, tipagem forte, com inferência de tipos
variedade de tipos de dados
facilidades para construir agregados e tipos funcionais
vinculação tardia, composição de funções, tratamento de exceções
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Função fatorial: ML
(* Exemplo de função fatorial: ML *)
fun fat n = if n=0 then 1 else n* fat(n-1)
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Programação em ML
Núcleo básico
Tipos primitivos
Operações
Formas funcionais: como definir e usar funções
Definição de novos tipos de dados
Biblioteca de funções básicas e em unidades. Avaliar: help “lib”;
Módulos
Mecanismos para estruturar programas em unidades
Exemplo: signature REGEXP = sig ............ end 
Mecanismos de herança: inclusão e especialização
Unidades (Units): podem ser carregadas em uma sessão interativa por: load "U"; sendo U o nome da unidade
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
ML x Tipos
ML é uma linguagem fortemente tipada
 Cada expressão possui um tipo, determinado pelo compilador
 Não é feita conversão implícita de tipos
- 3.0 + 2.0;			 > 5.0 : real
- 3.0 + 2; 
> Type clash: expression of type int cannot have type real
Conversão explícita		
- (3.0 + 2.0) = real (3 + 2)	 	> true : bool 	
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tipos básicos de ML: simples
Os tipos primitivos disponíveis são: inteiros (int), reais (real), lógicos (bool) e strings (string). 
Os operadores aritméticos são os usualmente encontrados em linguagens de programação: +, -, *, /, div e mod. 
Os operadores relacionais são representados por: >, >=, <, <=, = e <>
Exemplos
- 5 + 3 div 2; > val it = 6 : int
- "torta"; > val it = "torta" : string
- #"A"; > val it = #"A" : char
- true; > val it = true : bool
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tipos básicos de ML: compostos
Os tipos compostos são representados por tuplas, com elementos entre ( ), listas, com elementos entre [ ] e registros, com elementos entre { } 
Listas são formadas por elementos de mesmo tipo, enquanto que tuplas e registros admitem componentes de diferentes tipos
Exemplos
- (2,"Maria"); > val it = (2, "Maria") : int * string
- (true, 4.55, "s"); > val it = (true, 4.55, "s") : bool * real * string
- (("gato",3), false); > val it = (("gato", 3), false) : (string * int) * bool
- [1,2,3]; > val it = [1, 2, 3] : int list
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Módulos: bibliotecas
Os tipos primitivos podem ser usados sem qualificação e são associados a um conjunto de operações básicas e funções
Outras funções e outros tipos (como String, Date) são definidos em bibliotecas, com suas próprias operações
Exemplo
- load "Math"; > val it = ( ) : unit
- Math.pi; > val it = 3.14159265359 : real
- Math.sqrt(2.0); > val it = 1.41421356237 : real
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Associações (bindings)
Associações de valores
Associações de nomes
- val y=(10,"gato");
> val y = (10, "gato") : int * string
- val (prim,seg)=y;
> val prim = 10 : int
 val seg = "gato" : string
- val bb=true orelse false;
> val bb = true : bool
- val cc= bb andalso true;
- val pi=Math.pi;
> val pi = 3.14159265359 : real
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Funções
Definição de função
inferência de tipo
Assinatura de função
interpretador fornece
Utilização de função
transparência referencial
- fun inc n=n+1; > val inc = fn : int -> int
- fun incr n= n+ 1.0; > val incr = fn : real -> real
- val n=10; > val n = 10 : int
- inc n; > val it = 11 : int
- n; > val it = 10 : int
- size; > val it = fn : string -> int
- inc (trunc(incr 20.0));> val it = 22 : int
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Funções e parâmetros
Todas as funções são aplicadas sobre um único argumento: tipo de dado simples ou composto, ou uma função 
- fun maior(a,b)=if a>b then a else b;
> val maior = fn : int * int -> int
- maior(3,4);
> val it = 4 : int
- max (maior(3,4)) 5;
> val it = 5 : int
(* diferente assinatura *)
- fun max a b = if a>b then a else b;
> val max = fn : int -> int -> int
- max 3 4;
> val it = 4 : int
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tuplas como resultado
Tuplas pode ser usadas para retornar valores
- fun devolvedupla(x:int)=(x+10,x+20);
> val devolvedupla = fn : int -> int * int
- devolvedupla 2; 		> val it = (12, 22) : int * int
- val (a, b)= devolvedupla 5; 	> val a = 15 : int val b = 25 : int
- fun compara t1 t2 = t1 = t2; > val ''a compara = fn : ''a -> ''a -> bool
- compara (10, true) (5*2, 3=3); > val it = true : bool
Tuplas e funções booleanas
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tipos de parâmetro e de resultado
Argumentos com tipo
- fun maior (a:int, b:int) = if a>b then a else b;	
> val maior= fn: int * int -> int
Tipo de resultado
- fun mais (x, y) :int = x + y;	
> val mais: fn : int * int -> int
Inferência de tipos de argumentos e resultado (/)
- fun divider (x, y) = x / y; 
> val divider: fn : real * real -> real
Tipo genérico ´t
- fun qq(a,b)=(a,b);
> val ('a, 'b) qq = fn : 'a * 'b -> 'a * 'b
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Recursividade e parâmetros constantes
Recursividade
Sobrecarga
Outro exemplo 
com recursividade 
dupla
- fun fat n= if n<=1 then 1 else n*fat(n-1);
> val fat = fn : int -> int
- fun fat 0=1| fat 1= 1|fat n = n*fat(n-1);
> val fat = fn : int -> int
- fun fib 0 = 1 | fib 1=1
		 | fib n = fib(n-1) + fib(n-2);
> val fib = fn : int -> int
- fib 20;
> val it = 10946 : int
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Exemplo de simulação do comando Case
val dia = fn 0 => ”Segunda"
 | 1 => ”Terça"
 | 2 => ”Quarta"
 | 3 => ”Quinta"
 | 4 => ”Sexta"
 | 5 => ”Sabado"
 | _ => ”Domingo";
val dia = fn : int -> string
dia 3;
val it = ”Quinta" : string
dia 6;
val it = ”Domingo" : string
dia 7;
val it = ”Domingo" : string
_ denota qualquer valor
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Formas funcionais: mais alta ordem
Uma forma funcional ou função de mais alta ordem é aquela que usa funções como parâmetros ou fornece uma função como resultado, ou ambas
Composição de funções: 
forma funcional que usa duas funções como argumentos e cujo resultado é obtido pela aplicação da primeira função sobre o resultado da segunda função
Notação: h  f  g 
Exemplo: Para f (x)  x * x e g (x)  x + 3, 
h (5)  f ( g ( x)) resulta em 64
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Composição: exemplo em ML
- fun f(x)=x*x;
> val f = fn : int -> int
- fun g(x)=x+3;
> val g = fn : int -> int
- fun h f x = f(g(x));
> val 'a h = fn : (int -> 'a) -> int -> 'a
- h f 5;
> val it = 64 : int
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Formas Funcionais
Construção: forma funcional que usa uma lista de funções como parâmetros e fornece uma lista de resultados obtidos pela aplicação de cada uma das funções a um dado parâmetro. Notação [ f, g]
Exemplo: Para f (x)  x * x * x e g (x)  x + 3, [f, g] (4) resulta em (64, 7)
- fun comp f1 f2 n= (f1 n, f2 n);
> val ('a, 'b, 'c) comp = fn : ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c
- comp f g 4;
> val it = (64, 7) : int * int
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Formas funcionais:aplicação geral
Aplicação geral (apply-to-all): forma funcional que usa uma única função como parâmetro e fornece uma lista de valores obtidos pela aplicação da função dada a cada elemento da lista de parâmetros. Notação: 
Exemplo: Para h (x)  x * x * x,  ( h, (3, 2, 4)) resulta em (27, 8, 64)
(* exemplo em ML *)
- fun x2 nil=nil | x2(hd::tt) = (hd*2)::(x2 tt);
> val x2 = fn : int list -> int list
- x2[2,3,4];
> val it = [4, 6, 8] : int list
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Escopo de declarações
Escopo usual: uma sessão
Delimitação de escopo: let <decl> in <expr> end
- val m=5.6;
- val m = 5.6 : real
- let val m = 3
 val n = m * m
in
 m * n
end;
> val it = 27 : int
- m;
> val it = 5.6 : real
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Listas e funções
Listas podem ser construídas e retornadas
- fun lista li ls= if li>ls then nil else li::lista (li+1) ls;
> val lista = fn : int -> int -> int list
- lista 2 10;
> val it = [2, 3, 4, 5, 6, 7, 8, 9, 10] : int list
- fun somalista nil = 0 
	| somalista (hd :: tl) = hd + somalista (tl);	
> val somalista = fn: int list -> int
- somalista [ 1, 2, 3];			> val it = 6 : int
Listas podem ser recebidas como argumento
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Listas e Tuplas
Criando
uma lista de Tuplas
val romano = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")] 
(* função auxiliar: compara elemento da tupla *)
- fun achei ((a,b), c) = b=c;
> val ('a, ''b) achei = fn : ('a * ''b) * ''b -> bool
- fun busca nil nome = (0,nome) (* tupla *)
 | busca (hd::tl) nome = if achei(hd,nome) 
	then hd (* tupla*)
	else busca tl nome;
> val ''a busca = fn : (int * ''a) list -> ''a -> int * ''a
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Listas e funções
Função que recebe uma lista como argumento e retorna um inteiro
Função que recebe uma tupla de listas como argumento e retorna uma lista (tipo genérico)
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tipos definidos pelo usuário: exemplo de uso
Exemplo de uso
Definição do tipo
 datatype shape = point | circle of real |
 box of (real*real)
 New type names: =shape
 datatype shape =
 (shape,
 {con box : (real * real) -> shape,
 con circle : real -> shape,
 con point : shape})
 con box = fn : (real * real) -> shape
 con circle = fn : real -> shape
 con point = point : shape
load "Math";
val it = () : unit
fun area (point) = 0.0 
	| area (circle r) = Math.pi * Math.sqr(r)
 | area (box (b,h)) = b*h;
val area = fn : shape -> real
area(point);
val it = 0.0 : real
area(circle 3.0);
val it = 5.44139349655 : real
area(box(2.0,3.0));
val it = 6.0 : real
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG
*
*
*
Tratamento de exceções em ML
Exemplo: exceção do sistema
- 3 div 0;		 > Uncaught exception: Div
Exemplo: exceção definida pelo usuário
- exception Factorial;	 > exn Fatorial = Fatorial : exn
- fun checked_factorial n = if n = 0 then fact n else raise Factorial;
> val checked_factorial = fn : int -> int
Exemplo de teste
- val cf=checked_factorial;	 	> val cf = fn : int -> int
- cf 4;				> val it = 24 : int
- cf ~4;				> Uncaught exception: Factorial
Exemplo de tratador
 handle Factorial => print "Out of range.\n";
Prof. Débora Pereira Coura e Marcos Vinícius da Silva - Linguagem de Programação - UnilesteMG