Haskell (linguagem de programação)

Haskell
Paradigma	funcional, não rígida, modular
Surgido em	1990
Criado por	Simon Peyton-Jones, Paul Hudak, Philip Wadler, et al.
Estilo de tipagem	forte, estática, inferida
Principais implementações	GHC, Hugs, nhc
Dialetos:	Helium, O'Haskell, Template Haskell, PolyP
Influenciada por	Miranda, ML
Influenciou	C♯, Cat, Clojure, F♯, Python, Scala

Haskell é uma linguagem de programação puramente funcional, de propósito geral, nomeada em homenagem ao lógico Haskell Curry. Como uma linguagem funcional, a estrutura de controle primária é a função; a linguagem é baseada nas observações de Haskell Curry e seus descendentes intelectuais. Seu último padrão semi-oficial é o Haskell 98, destinado a especificar uma versão mínima e portável da linguagem para o ensino e como base para futuras extensões.

História

O conceito de avaliação preguiçosa já estava difundido no meio acadêmico desde o final da década de 1970. Esforços nessa área incluíam técnicas de redução de grafo e a possibilidade de uma mudança radical na arquitetura de von Neumann. Após o lançamento de Miranda em 1985, diversas outras linguagens funcionais de semântica não rígida proliferaram, como Lazy ML, Orwell, Alfl, Id, Clean, Ponder e Daisy (um dialeto de Lisp). Mesmo após dois anos, Miranda ainda era a mais usada, mas não estava em domínio público.

Em setembro 1987 foi realizada uma conferência Functional Programming Languages and Computer Architecture (FPCA '87), em Oregon, o consenso foi a criação de um comitê com o objetivo de construir um padrão aberto para tais linguagens. Isso consolidaria as linguagens existentes, servindo como base para pesquisas futuras no desenvolvimento de linguagens. A primeira reunião do comitê foi realizada em janeiro de 1988, e algumas das metas da linguagem foram discutidas. A linguagem deveria ser de fácil ensino, deveria ser completamente descrita através de uma sintaxe e semântica formal, deveria estar disponível livremente.

A primeira versão de Haskell foi definida em 1 de abril de 1990. Seguiu-se a versão 1.1 em agosto de ano seguinte, a versão 1.2 em março de 1992, a versão 1.3 em maio de 1996 e a versão 1.4 em abril de 1997. Esforços posteriores culminaram no Haskell 98, publicado em janeiro de 1999 e que especifica uma versão mínima, estável e portável da linguagem e a biblioteca para ensino. Esse padrão sofreu uma revisão em janeiro de 2003.

A linguagem continua evoluindo, sendo as implementações Hugs e GHC consideradas os padrões de facto. A partir de 2006 começou o processo de definição de um sucessor do padrão 98, conhecido informalmente por Haskell′ ("Haskell Prime").

Características

Características do Haskell incluem o suporte a funções recursivas e tipos de dados, casamento de padrões, list comprehensions, guard statements e avaliação preguiçosa, esta, um elo em comum entre os diversos grupos de desenvolvimento da linguagem. A combinação destas características pode fazer com que a construção de funções que seriam complexas em uma linguagem procedimental de programação tornem-se uma tarefa quase trivial em Haskell. Segundo dados de 2002, é a linguagem funcional sobre a qual mais pesquisa está sendo realizada. Muitas variantes tem sido desenvolvidas: versões paralelizáveis do MIT e Glasgow, ambas chamadas Parallel Haskell, outras versões paralelas e distribuídas chamadas Distributed Haskell (anteriormente Goffin) e Eden, uma versão chamada Eager Haskell e várias versões orientadas a objetos: Haskell++, O'Haskell e Mondrian.

Uma versão educacional do Haskell chamada Gofer foi desenvolvida por Mark Jones. Ela é oferecida pelo HUGS. Existe também uma versão do Haskell que permite orientação a aspectos (POA), chamada AspectH.

Sintaxe

Em Haskell existem apenas funções, e todas as funções são unárias. O que, em outras linguagens de programação seriam funções binárias, ternárias, etc, em Haskell são funções cujo valor de retorno são outras funções - o que se chama currying, termo derivado de Haskell Curry.

Uma função que, dados dois números, retorna sua soma poderia ser declarada como:

soma x y =x+y

O que parece ser uma função binária é, logicamente, uma função unária (soma, cuja entrada é x) que retorna outra função. Em outras palavras, soma x é a função unária que, dado y retorna x + y, e soma é a função unária que, dado x, retorna x +.

Em Haskell não existem variáveis globais, apenas funções e variáveis locais, definidas dentro do escopo de cada função.

Também não há estruturas de loop, ou instruções do tipo goto.

O if é implementado através de |, que significa a restrição do domínio do argumento da função.

O exemplo abaixo mostra uma implementação do fatorial que usa a recursividade e o if:

fat 0 = 1
fat n | n > 0 = n*fat(n-1)

Em palavras: a primeira linha diz que o fatorial de zero é um; a segunda linha diz que o fatorial de um número n qualquer, desde que n seja maior que zero, pode ser calculado a partir do fatorial de (n-1). Esta implementação não é eficiente, mas serve como exemplo didático.

Listas

Há duas funcionalidades importantes para a construção de listas. A primeira é a list comprehension, que permite construir listas sob forma de conjuntos. Por exemplo, o código [ x | x <- [0..], x^2>3 ] cria uma lista de elementos x a partir do gerador <- [0..] (o conjunto dos números naturais), que atendam o predicado x^2>3 (o símbolo <- representa o pertence, $\in \,$, da teoria dos conjuntos). Pode-se combinar geradores numa mesma list comprehension.

A segunda funcionalidade é a sequência aritmética, que permite construir listas sob forma de intervalos. Por exemplo, o código [2..10] cria uma lista de inteiros de 2 a 10. Pode-se omitir o fim do intervalo; [2..] gera uma lista infinita de inteiros a partir de 2.

Há três funções primordiais sobre listas em Haskell, das quais outras funções podem ser combinadas. A primeira é foldl, que adiciona um operador dado entre cada elemento da lista, retornando o resultado da expressão gerada. Para concatenar uma lista de cadeias de caracteres cadeia = ["Uma", " ", "cadeia"] pode-se usar foldr1 (++) cadeia. A segunda é map, que executa uma função a todos os elementos da lista, retornando uma nova lista. A terceira é filter, que filtra a lista a partir de um predicado.

Tipos de dado

A tipagem de Haskell é forte. Cada expressão possui um tipo, e é possível obtê-lo em tempo de compilação através de inferência de tipo. Os tipos básicos da linguagem incluem:

Tipo de dado	Descrição	Classes	Exemplo da sintaxe
Bool	Enumeração de valores booleanos, que permitem certas operações lógicas, como conjunção (&&), disjunção (||) e negação (not).	Read, Show, Eq, Ord, Enum, Bounded	True False
Char	Enumeração de caracteres 16-bit, Unicode. A faixa dos primeiro 128 caracteres é idêntica ao ASCII.	Read, Show, Eq, Ord, Enum, and Bounded	'a'
Double	Ponto flutuante com maior intervalo e precisão que Float	RealFloat
Either		Eq, Ord, Read, Show
Float	Ponto flutuante	RealFloat	6553.612 321.6e-3
IO	Tipo abstrato para operações de E/S, como putStr, print, getChar, getLine e readIO.	Monad, Functor
IOError	Tipo abstrato para erros nas operações de E/S com IO.	Show, Eq
Int	Inteiro que cobre, pelo menos, o intervalo de valores [-2^29, 2^29 - 1].	Integral	123
Integer	Inteiro de precisão ilimitada, com as mesmas funções e operadores de Int	Integral	123
Maybe	Lida com valores opcionais ou ilegais sem terminar o programa e sem usar o IOError de IO.	Eq, Ord, Read, Show
Ordering		Eq, Ord, Bounded, Enum, Read, Show
String	Cadeia de caracteres, representada sob forma de lista de Char. A sintaxe tanto pode ser de lista quanto a abreviação, entre aspas.		"Texto" ['T','e','x','t','o']
Tuplas	Tipo de dado algébrico de definição de registros heterogêneos, tuplas. A quantidade máxima de elementos depende da implementação, mas a quantidade mínima de quinze elementos é sempre garantida.	Eq, Ord, Bounded, Read, Show	('A',11,True)
Listas	Tipo de dado algébrico de definição de registros homogêneos listas. Entre os operadores disponíveis encontra-se !!, que retorna o n-ésimo elemento da lista, e ++, que concatena duas listas distintas de mesmo tipo. Relacionado a concatenação, há o operador :, que adiciona um elemento no topo de uma lista.	Eq, Ord	[1,2,3,4] [1..4] (1:(2:(3:(4:[]))))

A linguagem ainda define diversas classes padrão:

Tipo de dado	Descrição	Prove
Bounded	Delimita um tipo de dado
Enum	Prove operações em tipo sequencialmente ordenados.	succ, pred, toEnum, enumFrom
Eq	Prove operadores de igualdade.	==, /=
Floating
Fractional
Functor	Usado por tipos que podem ser mapeados.
Integral
Ord	Prove operadores de ordenação.	⇐, <, >=, >
Monad	Prove operações sobre mônadas.
MonadPlus
Num
Read
Real
RealFloat
RealFrac
Show

Operadores

Além dos operadores específicos de certos tipos de dado supracitados, vale notar também alguns outros. O operador . realiza a composição de funções. Por exemplo, a expressão ((2+).(3*).(4-)) 2 retorna 8, e significa $((4-2)*3)+2$.

A potenciação pode ser feita através do operador **. Entretanto estão disponíveis também duas versões mais eficientes. Para ^^, o expoente deve ser um inteiro; para ^, o expoente deve ser um inteiro não negativo.

Aplicações

Os pontos fortes da linguagem Haskell têm sido bem aplicados em alguns projetos. É cada vez mais utilizada em aplicações comerciais. O compilador e interpretador Pugs criado por Audrey Tang é uma versão completa da linguagem Perl 6. Darcs é um sistema de controle de versões baseado em mudanças (change-based) com várias características inovadoras. A Linspire GNU / Linux escolheu Haskell para desenvolvimento das ferramentas do sistema . Xmonad é um gerenciador de janelas "tile-based" para o X Window System escrito inteiramente em Haskell. Bluespec SystemVerilog é uma linguagem feita como uma extensão do Haskell.

Exemplos

O difundido caso do Programa Olá Mundo pode ser exemplificado em Haskell da seguinte forma:

olamundo :: IO()
olamundo = putStrLn "Olá, Mundo!"

A clássica definição da função fatorial:

fatorial :: Integer -> Integer
fatorial 0 = 1
fatorial n | n > 0 = n * fatorial (n-1)

Ou em uma linha:

fatorial n = if n > 0 then n * fatorial (n-1) else 1

Este artigo descreve o fatorial como uma função recursiva, terminando com um caso que serve como base. É semelhante ao encontrado nas descrições de fatoriais em livros didáticos de matemática. Grande parte do código Haskell é semelhante ao padrão da notação matemática na potencialidade expressiva e na sintaxe. A primeira linha da função fatorial descreve os tipos desta função; embora seja opcional, é considerado bom estilo incluí-la. Ela pode ser lida como a função fatorial (fatorial) tem tipo (::) inteiro para inteiro (Integer -> Integer). Ou seja, ele tem um inteiro como um argumento e retorna outro inteiro. O tipo de uma definição é inferido automaticamente se o programador não forneceu uma notação de tipo.

A segunda linha depende de um casamento de padrões (pattern matching), uma característica importante do Haskell. Note que os parâmetros da função são separados por parênteses e não por espaços. Quando o argumento da função é 0 (zero) será devolvido o inteiro 1 (um). Para todos os outros casos, a terceira linha é tentada. Esta é a recursividade, e executa a função novamente até que um caso que sirva como base seja atingido.

Um "guard" protege a terceira linha de números negativos, sendo que um fatorial não permite números negativos, indefinido-o. Sem um "guard" essa função seria recursiva "fatorando" todos os números negativos, sem nunca chegar à base 0. Se um inteiro negativo é passado para o fatorial funcionar como um argumento, o programa irá falhar com um erro "runtime". De último caso, poderia ser tratada esta condição de erro e imprimir uma mensagem de erro adequada em seu lugar.

A descrição acima é parecida com as descrições matemática, tais como definições de uma função $f=g\circ h$ e não como uma atribuição de um valor numérico para uma variável.

Uma outra definição da função fatorial (usando uma notação de lista em Haskell e a função padrão product):

fatorial n = product [1..n]

A mesma função mas agora no estilo point-free. Repare-se que os argumentos desaparecem (o ponto significa composição de funções):

fatorial = product . enumFromTo 1

Uma implementação da função que retorna o n-ésimo termo na seqüência de Fibonacci:

fib 0 = 0 
fib 1 = 1 
fib n = fib (n - 2) + fib (n - 1)

Uma função que retorna uma lista dos números de Fibonacci:

fibs@(_:rest) = 0 : 1 : (zipWith (+) fibs rest)

A função anterior cria uma lista infinita, que é possível graças a avaliação preguiçosa. Poderia-se implementar fib como:

fib n = fibs !! n

O algoritmo quicksort pode ser elegantemente escrito em Haskell:

qsort []    = []
qsort (h:t) = qsort menores_que_h ++ [h] ++ qsort maiores_que_h
   where
      menores_que_h   = [x | x <- t, x < h]
      maiores_que_h   = [x | x <- t, x >= h]

Uma forma mais compacta desse mesmo algoritmo seria:

quicksort [] = []
quicksort (s:xs) = quicksort [x|x <- xs,x < s] ++ [s] ++ quicksort [x|x <- xs,x >= s]

Nota: Por causa das excessivas cópias e concatenações de listas, este código pode ser lento.

Aqui tem um exemplo de Números Perfeitos:

divisor x d | mod(x d)==0=n
            | otherwise=0

soma_d _  1 =1
soma_d 1 _ =1
soma_d n x = divisor(n x)+soma_d(n-1 x)

NP 0 _ = []
NP n x |soma_d(x/2 x)== x=(x:NP(n-1  x+1)
       |otherwise=NP(n x+1)

Implementações

As seguintes implementações estão totalmente, ou quase, de acordo com o padrão Haskell 98. Todas são distribuídas sob licenças código aberto.

• GHC. O Glasgow Haskell Compiler gera código nativo de diferentes arquitecturas e pode também gerar código C. Ele é provavelmente o mais popular compilador Haskell, e algumas bibliotecas (como bindings para OpenGL) funcionam apenas com ele.
• Hugs é um interpretador de bytecode. Oferece rápida compilação dos programas e razoável velocidade de execução. Também dispõe de uma simples biblioteca gráfica. Hugs é ideal para pessoas que estão aprendendo os básicos de Haskell. É a mais portável e leve das implementações de Haskell.
• nhc98 é outro compilador que gera bytecode. O bytecode resultante executa significativamente mais rápido do que o equivalente do Hugs. Nhc98 foca na minimização do uso de memória, e é uma boa escolha para máquinas velhas/lentas.
• HBC é outro compilador Haskell para código nativo. Seu desenvolvimento não está ativo, mas ele é funcional.
• Helium é um novo dialecto do Haskell. O foco é na facilidade de aprendizado. Actualmente carece de typeclasses, tornando-o incompatível com muitos programas Haskell.

Leitura adicional

• Página do livro: Haskell: Uma Abordagem Prática, um livro de nível introdutório a médio sobre a linguagem Haskell, com uma apresentação crescente as principais características da linguagem.

Referências bibliográficas

• Naomi Hamilton (19 de setembro de 2008). «The A-Z of Programming Languages: Haskell» (em inglês). Computerworld. Consultado em 29 de setembro de 2008 
• Paul Hudak, John Hughes, Simon Peyton Jones, Philip Wadler (16 de abril de 2007). «A History of Haskell: Being Lazy With Class» (PDF) (em inglês). Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III). Consultado em 29 de setembro de 2008  !CS1 manut: Nomes múltiplos: lista de autores (link)
• André Rauber Du Bois. «Programação Funcional com a Linguagem Haskell» (PDF) (em inglês). Universidade de Heriot-Watt. Consultado em 30 de setembro de 2008 
• «The Haskell 98 Report: Predefined Types and Classes» (em inglês). Sítio oficial. Dezembro de 2002. Consultado em 30 de setembro de 2008 

Ver também

• Wikilivros

• Programação funcional

Ligações externas

• Sítio oficial (em inglês)
• «Introdução ao Haskell 98» (PDF) (em inglês) 
• «Outros exemplos de códigos em Haskell» (em inglês) 
• «Tutorial, em http://www.lisperati.com/haskell/» (em inglês)