®
Tópicos Avançados em Linguagens Computacionais – IF724
ML
OCAML
FSHARP
Leandro Mitsuo
Rodrigo Lumack
[email protected]
[email protected]
Professor: André Santos
Linguagens Funcionais
• Programação Funcional
– Ênfase na avaliação de expressões
– Expressões são formadas por funções
que combinam valores básicos
– Funções podem ou não ter argumentos
e um simples valor de retorno
• Funções podem ser nomeadas ou
anônimas (lambda)
Linguagens Funcionais
Vantagens
• Maior concisão
• Maior elegância (facilidade de
compreensão)
• Ausência de “core dumps”
– É impossível tratar um inteiro como um
ponteiro ou haver referências nulas
• Reuso de código (através de polimorfismo)
• Alta abstração e modularização
– Funções de alta ordem
• Gerenciamento automático de memória
Linguagens Funcionais
Desvantagens
• Bibliotecas com recursos limitados
• Incompatibilidade com outras tecnologias
• Instalação de compiladores e
interpretadores complicada
• Pouco difundidas
• Não podem ser utilizadas em sistemas
onde a performance é crítica
História das Linguagens Funcionais
•
•
•
•
Primeira linguagem de programação funcional: Lambda
Calculus
– Não foi projetada para ser executada por um
computador
– Desenvolvida por Alonzo Church na década de 30
LISP
– Desenvolvida por John McCarthy no MIT na década
de 50
SCHEME
– Tentativa de simplificar LISP
ML
– Desenvolvida na década de 70 na Universidade de
Edimburgo por Robin Milner
História das Linguagens Funcionais
• Miranda
– Anos 70 em Kent
• Haskell
– Anos 80
• Outras
– SML, SML/NJ, MOSML, CAML, CAML
Light, OCAML, FSharp
ML – Meta Language
Características
• Influenciou o desenvolvimento de Haskell, Cyclone,
Nemerle, OCAML
• Estaticamente Tipada
• Fortemente Tipada
• Inferência de tipo
– fun fac : (int -> int) 0 = 1
– | fac n = n * fac (n-1);
– : (int -> int) é opcional
• fun fac 0 = 1
• | fac n = n * fac(n-1);
ML – Meta Language
Características
• Suporte a valores estruturados: tuplas,
listas, árvores
• Exemplos de tuplas
– val pair = (1,"abc");
• val pair = (1,"abc") : int * string
– val triple = (1,true,1.0);
• val triple = (1,true,1.0) : int * bool *
real
ML – Meta Language
Características
• Exemplos de Listas
– val l = [1,2,3];
• val l = [1,2,3] : int list
– Operações sobre a lista
• hd l;
– val it = 1 : int
• tl l;
– val it = [2,3] : int list
• tl(tl(tl l));
– val it = [] : int list
ML – Meta Language
Características
• Exemplo de árvores
• Declarando o tipo árvore binária
– datatype ’a bintr = LEAF of ’a
| NODE of ’a bintr*’a bintr;
• Criando uma árvore binária
– val tree = NODE (NODE(LEAF 1,LEAF
4),LEAF 7);
ML – Meta Language
Características
• Funções de alta ordem
• Exemplo
– Declaração de um map
• fun map f [] = []
| map f (h::t) = (f h)::(map f t);
– Utilizando o map
• map (fn x=> x+1) [1,2,3];
– val it = [2,3,4] : int list
• map (fn x=> [x]) [1,2,3];
– val it = [[1],[2],[3]] : int list list
ML – Meta Language
Características
• Polimorfismo paramétrico
• Exemplo
– fun mklist x = [x];
• val mklist = fn : ’a -> ’a list
– mklist 1;
• val it = [1] : int list
– mklist (mklist 1);
• val it = [[1]] : int list list
– mklist (mklist “a”);
• val it = [[“a”]] : string list list
ML – Meta Language
Outras Características
• Chamada por valor (call-by-value
evaluation)
• Gerenciamento de memória automático :
Garbage Collection
• Tipos de dados algébricos
• Casamento de padrões
• Utiliza eager evaluation: ganha memória e
velocidade, mas não pode usar listas
infinitas
ML – Meta Language
Características Imperativas
• Referências
– São como ponteiros em C e C++
• Exemplos:
– Ponteiro para inteiro
– val iRef = ref 7;
• val iRef = ref 7 : int ref
– Ponteiro para função
– fun id x = x;
• val id = fn : ‘a -> ‘a
– val fRef = ref id;
• val fRef = ref fn : ‘a -> ‘a ref
ML – Meta Language
Características Imperativas
•
•
Arrays
– Coleções de dados homogêneos fortemente tipados
– Podem ser atualizados
Exemplos
– A partir de uma lista
• val l = [3, 5, 1];
– val l = [3,5,1] : int list
• val a = Array.fromList l;
– val a = [|3,5,1|] : int array
– Especificando o tamanho e um valor default
• Array.array (3, “jaca");
– val it = [|“jaca"," jaca "," jaca"|] : string array
– A partir de uma função
• Array.tabulate (4, fn x => x + 2);
– val it = [|2,3,4,5|] : int array
ML – Meta Language
Características Imperativas
• Vetores
– São como arrays, mas não podem ser
atualizados e fornecem acesso aleatório
• Exemplos
– A partir de uma lista
• Vector.fromList ["alpha", "beta", "gamma",
"delta"];
– val it = #["alpha","beta","gamma","delta"] :
string vector
– A partir de um array
• val a = Array.tabulate (4, fn x => x + 2);
– val a = [|2,3,4,5|] : int array
• val v = Array.extract (a, 1, SOME(2));
– val v = #[3,4] : int vector
ML – Meta Language
Características Imperativas
• Exceções
• Exemplo
– fun illustrate1 i = if i > 0 then i - 1 else raise
Example;
• val illustrate1 = fn : int -> int
– fun ill2 j = illustrate1 j handle Example => (print
"Example raised!\n"; 0);
• val ill2 = fn : int -> int
– ill2 17;
• val it = 16 : int
– ill2 0;
• Example raised!
• val it = 0 : int
ML – Meta Language
Uso
•
•
•
•
•
•
Compiladores
Analisadores
Provadores de teorema
Bio-Informática
Sistemas Financeiros
Aplicações com banco de dados
genealógicos
• Programas cliente/servidor
OCAML – Objective CAML
•
•
•
•
•
Desenvolvida por Xavier Leroy, Jérôme Vouillon, Damien
Doligez e Didier Rémy em 1996
Open Source mantida pelo INRIA (licença LGPL)
Derivada de ML herdando suas principais características
– Fortemente tipada
– Estaticamente tipada
– Inferência de tipos
Multi-paradigma
– Funcional
– Imperativo
– Orientação a objeto
Dá ênfase em performance
– Compilador gera código otimizado
– Segundo Xavier Leroy, alcança 50% da performance
de um código C
OCAML – Objective CAML
• O compilador gera código nativo para as
plataformas:
– Windows, Unix e Mac OS X
• Excelente portabilidade
– IA32, AMD64, PowerPC, Sparc, IA64,
Alpha, HP/PA, MIPS e StrongARM
• Possibilidade de uso de Multithread
– Porém o Garbage Collector não foi
projetado para dar suporte a
concorrência
OCAML – Objective CAML
•
Exemplo
– Declarando Classe
#class point =
object
val mutable x = 0
method get_x = x
method move d = x <- x + d
end;;
OCAML – Objective CAML
• Exemplo
– Instanciando
#let p = new point;;
– Invocando Métodos
#p#get_x;;
- : int = 0
#p#move 3;;
- : unit = ()
#p#get_x;;
- : int = 3
OCAML – Objective CAML
Aplicações
• Uso Comercial
– Slam Project da Microsoft
• Técnicas de análise estática para
encontrar bugs em device drivers
– Software financeiro da LexiFi
– Med-Sumo
• Sistema de bio-informática distribuído
pela empresa Medit
– Merjis Ltd é uma empresa especializada
em web marketing que possui diversas
ferramentas de uso interno
desenvolvidas em OCAML
OCAML – Objective CAML
Aplicações
• Utilitários
– MLDonkey
• Programa p2p
– Unison
• Sincronizador de arquivos
– Texvc
• Um compilador TeX
• Educacionais
– GeoProof
• Software de geometria
– MinCaml
• Pequeno tutorial de compilador
OCAML – Objective CAML
Aplicações
• Engenharia
– Confluence
• Gera lógica digital para FPGA ou
código C para softwares de tempo
real
• Entretenimento
– Desenvolvimento de jogos simples
• Gerador de labirinto 2D
• Solucionador de Sudoku
• Dominó
– Simulador de gravidade
OCAML – Objective CAML
Aplicações
• Ciência
– Provador de teoremas HOL
– Sistema de gerenciamento de provas
formais
– Orpie
• Uma calculadora para console
FSharp
• Combinação da eficiência, scripting,
sistema de tipos forte e produtividade de
ML com a estabilidade, bibliotecas,
compatibilidade (cross-language) e
ferramentas de .NET
• Multi-paradigma
– Funcional
– Orientada a objetos
FSharp
• Fornece a combinação de:
– Scripting interativo (como Python)
– A base para ambientes de visualização de dados
interativos (como o MatLab)
– Sistema de tipos forte e inferência de tipos (de
ML)
– Alta performance (de C#)
– Fácil acesso às bibliotecas da .NET e
ferramentas de banco de dados
– Baseada em simplicidade (como Scheme)
– Integração com o Visual Studio
– A velocidade de execução de código nativo da
plataforma .NET
FSharp
• É uma variante de ML
• Compartilha o núcleo da linguagem com
OCaml
• Ao contrário de outras linguagens de script,
F# roda na mesma (ou quase mesma)
velocidade de C# ou C++
– Performance através de sistema de tipos
forte
FSharp
• C# e F# podem se chamar diretamente
– F# tem acesso imediato à API da plataforma
.NET, incluindo, por exemplo, WinForms e
DirectX
– Bibliotecas desenvolvidas em F# podem ser
utilizadas por outras linguagens .NET
• F# também é compatível Caml
– Poucas mudanças de pré-compilação são
necessárias
– Facilita porting de código escrito em Caml para
.NET
FSharp
Objetivos
•
•
Resolver os 7 grandes problemas que levam ao desuso
de linguagens funcionais
– Bibliotecas
• Acesso às bibliotecas .Net sem necessidade de
wrappers
– Portabilidade
• Através de .NET
– Disponibilidade
– Pacotes
• Assemblies de .NET provêm mecanismo de
pacotes
– Ferramentas
• Integração com o Visual Studio
– Treinamento
– Popularidade
Projeto similar ao OCaml
FSharp
Áreas de Aplicação
• Programação orientada à Matemática
• Desenvolvimento de aplicações científicas
e de engenharia
• Implementação de análises simbólicas
sofisticadas
– Verificação de hardware
– Verificação de software
– Otimização
– Aprendizagem de máquina
– Desenvolvimento de compiladores
F# within .NET
CLR GC,
JIT, NGEN etc.
C#
Profilers,
Optimizers etc.
VB
ML
F#
Debuggers
System.Windows.Forms
Avalon etc.
System.I/O
System.Net etc.
Sockets etc.
ASP.NET
F# as a Language
Powerful, simple programming language
Core
ML
Core
ML
“OCaml-Objects”
OCaml
Modules-asvalues
+ tools
.NET API
Access
F#
Other
extensions
+ tools
FSharp
Observações
• F# é:
– Excelente para utilizar bibliotecas .NET
– Excelente para escrever bibliotecas ML
– OK em tornar bibliotecas ML usáveis por .NET
• O objetivo é escrever programas que:
– Utilizam componentes .NET
– Necessitam de processamento simbólico
– Utilizam componentes escritos em C#
F#, the CLR & .NET Generics
VB
VC++
Dá suporte a generics
e polimorfismo
C#
...
F#
F# trabalha com ou sem
generics
MS-IL
Common Language Runtime
Loader
Verifier
GC
Native
Code
JIT
...
F# v1.0
• O núcleo e o compilador da linguagem
estão estáveis
• É utilizado internamente pela Microsoft
• Integração com o Visual Studio 2005 Beta 1
• Compatibilidade com biblioteca ML