Programação Funcional em Haskell

Programação Funcional em Haskell

(Parte 1 de 9)

Programacao Funcional Usando Haskell

Francisco Vieira de Souza

• Licenciado em Matematica (1978) e Engenheiro Civil (1982) pela Universidade Federal do Piauı, Mestre (1994) e Doutor (2000) em Ciencia da Computacao pela Universidade Federal de Pernambuco.

• Professor do Departamento de Matematica (1986-1988), fundador (1987) e professor (desde 1987) do Departamento de Informatica e Estatıstica da Universidade Federal do Piauı.

Teresina-Pi Agosto de 2005

Copyright c©2005, Departamento de Informatica e Estatıstica,

Centro de Ciencias da Natureza, Universidade Federal do Piauı. Todos os direitos reservados.

A reproducao do todo ou parte deste trabalho somente sera permitida para fins educacionais e de pesquisa e com a expressa autorizacao do autor.

Copyright c©2005, Departamento de Informatica e Estatıstica,

Centro de Ciencias da Natureza, Universidade Federal do Piauı. All rights reserved.

Reproduction of all or part of this work only will be permitted for educational or research use andw ithe xpressedp ermission of the author.

Apresentacao

Esta Apostila representa a compilacao de varios topicos, desenvolvidos por pesquisadores de renome, no campo da programacao funcional. Ela tem como objetivo servir de guia aos profissionais de Informatica que desejam ter um conhecimento inicial sobre o paradigma funcional de forma geral e, em particular, sobre programacao usando Haskell. Ultimamente, Haskell tem se tornado a linguagem funcional padrao do discurso, ja existindo varios interpretadores e compiladores para ela, alem de varias ferramentas de analise de programas nela codificados (profiles).

Para atingir este objetivo, acreditamos que o estudo deva ser acompanhado de algum conhecimento, mesmo que mınimo, sobre a fundamentacao destas linguagens e da forma como elas sao implementadas. Este conhecimento proporciona ao leitor uma visao das principais caracterısticas e propriedades destas linguagens. Em particular, e importante entender porque as tecnicas utilizadas na compilacao das linguagens imperativas nao se mostraram adequadas na compilacao de linguagens funcionais.

Em 1978, John Backus advogou o paradigma funcional como o que oferecia a melhor solucao para a chamada “crise do software”. As linguagens funcionais sao apenas uma sintaxe mais comoda para o λ-calculo. David Turner [36] mostrou, em 1979, que a logica combinatorial poderia ser extendida de forma a possibilitar a implementacao eficiente de linguagens funcionais. Esse trabalho provocou uma corrida em direcao a pesquisa nesta area, gerando uma variedade de tecnicas de implementacao destas linguagens.

Dentre estas tecnicas, uma que tem sido adotada, com resultados promissores, e a utilizacao do λ-calculo como linguagem intermediaria entre a linguagem de alto nıvel e a linguagem de maquina. Os programas codificados em alguma linguagem funcional de alto nıvel sao traduzidos para programas em λ-calculo e destes para programas em linguagem de maquina. Neste caso, o λ-calculo desempenha um papel semelhante ao que a linguagem Assembly exerce, como linguagem de montagem, na compilacao de linguagens imperativas. Esta metodologia tem dado certo, uma vez que ja se conhecem tecnicas eficientes de traducao de programas em λ-calculo para programas executaveis, faltando apenas uma traducao eficiente de programas codificados em uma linguagem funcional de alto nıvel para programas em λ-calculo.

Esta Apostila tem inıcio em seu primeiro Capıtulo tratando das caracterısticas das linguagens funcionais, destacando suas vantagens em relacao as linguagens de outros paradigmas que utilizam atribuicoes destrutivas. Em seguida, ef eita umai ntroducao ao λ-calculo. Apesar do carater introdutorio, achamos ser suficiente para quem quer dar os primeiros passos em direcao a aprendizagem desta tecnica. Os Capıtulos subsequentes se referem todos a Programacao Funcional usando Haskell.

Por ser uma primeira tentativa, a Apostila contem erros e sua apresentacao didatico-pedagogica deve ser revista. Neste sentido, agradecemos crıticas construtivas que serao objeto de analise e reflexao e, por isto mesmo, muito bem-vindas.

Teresina-Pi, agosto de 2005. Francisco Vieira de Souza

Conteudo

Introducao viii

1.1 Introducao1
1.2 Historico12
1.3 Programacao com expressoes13
1.4 Independencia da ordem de avaliacao14
1.5 Transparencia referencial16
1.6 Interfaces manifestas18
1.7 Funcoes e expressoes aplicativas19
1.8 Definicao de funcoes20
1.9 Resumo25
2.1 Introducao27
2.2 λ-expressoes28
2.3 A sintaxe do λ-calculo29
2.3.1 Aplicacao de funcao e currificacao29
2.4 Funcoes e constantes pre-definidas30
2.5 λ-abstracoes30
2.6 A semantica operacional do λ-calculo31
2.6.1 Formalizacao das ocorrencias livres ou ligadas3
2.7 Combinadores3
2.8 Regras de conversoes entre λ-expressoes35
2.8.1 α-conversao35
2.8.2 η-conversao35
2.8.3 β-conversao35
2.8.4 Nomeacao36
2.8.5 Captura36
2.9 Conversao, reducao e abstracao37
2.10 Provando a conversibilidade38
2.12 Ordem de reducao39
2.13 Funcoes recursivas40
2.14 Resumo42
3.1 Introducao43
3.2 Primeiros passos4
3.2.1 O interpretador Hugs45
3.2.2 Identificadores em Haskell47
3.3 Funcoes em Haskell47
3.3.1 Construindo funcoes49
3.3.2 Avaliacao de funcoes em Haskell51
3.3.3 Casamento de padroes (patterns matching)51
3.4 Tipos de dados em Haskell52
3.4.1 Os tipos primitivos da linguagem52
3.4.2 Programando com numeros e strings59
3.4.3 Os tipos de dados estruturados de Haskell60
3.4.4 Escopo61
3.4.5 Calculos:62
3.4.6 Projeto de programas65
3.4.7 Provas de programas65
3.5 Resumo69

3 Programacao funcional em Haskell 43

4.1 Funcoes sobre listas72
4.1.1 O construtor de listas : (cons)72
4.1.2 Construindo funcoes sobre listas73
4.2 Pattern matching revisado75
4.3 Compreensoes e expressoes ZF (Zermelo-Fraenkel)78
4.4 Funcoes de alta ordem84
4.4.1 A funcao map85
4.4.2 Funcoes anonimas8
4.5 Polimorfismo90
4.5.1 Tipos variaveis91
4.5.2 O tipo mais geral91
4.6 Inducao estrutural92
4.7 Composicao de funcoes95
4.7.1 Composicao avancada96

4O tipo Lista 71 vi

4.8 Aplicacao parcial98
4.8.1 Secao de operadores9
4.8.2 Currificacao9
4.9 Melhorando o desempenho de uma implementacao103
4.9.1 O desempenho da funcao reverse103
4.9.2 O desempenho do quicsort104
4.10 Resumo106
5.1 Introducao109
5.2 Classes de tipos109
5.2.1 Fundamentacao das classes110
5.2.2 Funcoes que usam igualdade1
5.2.3 Assinaturas e instancias112
5.2.4 Classes derivadas112
5.2.5 As classes pre-definidas em Haskell113
5.3 Tipos algebricos115
5.3.1 Como se define um tipo algebrico?116
5.3.2 A forma geral117
5.3.3 Derivando instancias de classes118
5.3.4 Tipos recursivos118
5.3.5 Recursao mutua120
5.3.6 Tipos algebricos polimorficos121
5.4 Tratamento de erros124
5.4.1 Valores fictıcios124
5.4.2 Tipos de erros125
5.5 Provas sobre tipos algebricos127
5.6 Modulos em Haskell128
5.6.1 Cabecalho em Haskell129
5.6.2 Importacao de modulos129
5.6.3 O modulo main129
5.6.4 Controles de exportacao129
5.6.5 Controles de importacao130
5.7 Tipos abstratos de dados130
5.7.1 O tipo abstrato Pilha131
5.7.2 O tipo abstrato de dado Fila133
5.7.3 O tipo abstrato Set136
5.7.4 O tipo abstrato Tabela137

5 Tipos de dados complexos 109 vii

5.8.1 Expressoes ZF (revisadas)140
5.8.2 Dados sob demanda141
5.8.3 Listas infinitas141
5.9 Resumo142
6.1 Introducao145
6.2 Entrada e Saıda em Haskell146
6.2.1 Operacoes de entrada146
6.2.2 Operacoes de saıda147
6.2.3 A notacao do148
6.3 Arquivos, canais e descritores149
6.3.1 A necessidade dos descritores150
6.3.2 Canais150
6.4 Gerenciamento de excecoes150
6.5 Resumo151

6 Programacao com acoes em Haskell 145 Referencias Bibliograficas 152 viii

Introducao

”Functional languages privide a framework in which the crucial ideas of modern programming are presented in the clearest prossible way.” (Simon Thompson in [35])

Em 2004, Philip Wadler1 escreveu o artigo “Why no one uses functional languages”, onde ele comenta sobre a pouca utilizacao das linguagens funcionais na Industria e ambientes comerciais [37]. Para ele, dizer que ninguem usa linguagem funcional, e um exagero. As chamadas telefonicas no Parlamento Europeu sao roteadas por um programa escrito em Erlang, a linguagem funcional da Ericsson. A rede Cornell distribui CDs virtuais usando o sistema Esemble,e scrito em CAML e a Polygram vende CDs na Europa usando Natural Expert,d a Software AG.A s linguagens Erlang (w.erlang.se) e ML Works de Harlequin (w.harlequin.com) apresentam um extensivo ambiente de suporte ao usuario. Alem disso, as linguagens funcionais sao mais adequadas ac onstrucao de provadores de teoremas, incluindo o sistema HOL que foi utilizado na depuracao do projeto de multiprocessadores da linha HP 9000.

Ainda segundo Wadler, as linguagens funcionais produzem um codigo de maquina com uma melhoria de uma ordem de magnitude e, nem sempre, estes resultados sao mostrados. Normalmente, se mostram fatores de 4. Mesmo assim, um codigo que e quatro vezes menor, quatro vezes mais rapido de ser escrito ou quatro vezes mais facil de ser mantido nao pode ser jogado fora. Para ele, os principais fatores que influenciam na escolha de uma linguagem de programacao sao:

• Compatibilidade. Os sistemas nao sao mais construıdos monoliticamente, como eram no passado. Atualmente, eles sao escritos de forma modular. Os modulos sao construıdos por usuarios em tempos e locais possivelmente diferentes e sao ligados atraves de interfaces bem definidas. Muitas linguagens funcionais ja apresentam facilidades para a construcao de grandes softwares com formas bem adequadas de construcao de modulos e algumas linguagens funcionais ainda nao oferecem estas facilidades. E necessario acabar com o isolamento das linguagens funcionais e incorporar a elas facilidades para a comunicacao entre programas funcionais e programas codificados em outras linguagens pertencentes a outros paradigmas. A Industria da Computacao estac omecando a distribuir padroes como CORBA e COM para suportar a construcao de software a partir de componentes reutilizaveis. Atualmente, os programas em Haskell ja podem ser empacotados como um componente COM e qualquer componente COM pode ser chamado a partir de Haskell. Entre outras aplicacoes, isto permitiu que Haskell fosse utilizada como linguagem para a construcao do Internet Explorer,o browser da Microsoft.

• Bibliotecas. Muitos usuarios escolheram Tcl, atraıdos, principalmente, pela biblioteca grafica Tk. Muito pouco da atratividade de Java tem a ver com a linguagem em si,

1Philip Wadler trabalha nos grupos de ML e de Unix na Bell Labs. Ele e co-autor das linguagens Haskell e GJ. Alem de varios artigos publicados, ele tambem e co-editor da revista Journal of Functional Programming.

e sim com as bibliotecas associadas, usadas na construcao de graficos, banco de dados, interfaceamento, telefonia e servidores. Apesar de ainda nao existirem muitas bibliotecas graficas para as linguagens funcionais, muito esforco tem sido feito nesta direcao, nos ultimos tempos. Haskell tem Fudgets, Gadgets, Haggis e Hugs Tk. SML/NJ tem duas: eXene e SML Tk. Haskell e ML tem ambas um poderoso sistema de modulos que tornam suas bibliotecas faceis de serem construıdas.

• Portabilidade. Inegavelmente C e C++ tem sido preferidas em muitos projetos. No entanto, muito desta preferencia nao se deve ao fato de C gerar um codigo mais rapido que o codigo gerado pelas linguagens funcionais, apesar de, normalmente, se verificar esta diferenca de desempenho. Na realidade, esta preferencia se deve mais a portabilidade inegavel de C. Sabe-se que os pesquisadores em Lucent teriam preferido construir a linguagem PRL para Banco de Dados usando SML, mas escolheram C++, porque SML nao estava disponıvel no mainframe Amdahl, onde deveria ser utilizada. Por outro lado, as tecnicas de implementacao de linguagens utilizando maquinas abstratas tem se tornado muito atrativas para linguagens funcionais [21] e tambem para Java. Isto se deve muito ao fato de que escrever a maquina abstrata em C a torna muito mais facil de ser portada para uma grande variedade de arquiteturas.

• Disponibilidade. Alguns compiladores sao muito difıceis de serem instalados. Por exemplo, GHC (Glasgow Haskell Compiler) era considerado uma aventura por alguns usuarios que tentavam instala-lo. Ainda existem poucas linguagens funcionais comerciais e isto torna difıcil um codigo estavel e um suporte confiavel. Alem do mais, as linguagens funcionais estao em permanente desenvolvimento e, portanto, estao sempre em transformacoes.

• Empacotamento. Muitas linguagens funcionais seguem a tradicao de LISP, de sempre realizar suas implementacoes atraves do loop read-eval-print.A pesar da conveniencia, e essencial desenvolver habilidades para prover alguma forma de conversao de programas funcionais em programas de aplicacao standalone. Muitos sistemas ja oferecem isto, no entanto, incorporam o pacote de runtime completo a biblioteca e isto implica na exigencia de muita memoria.

• Ferramentas. Uma linguagem para ser utilizavel necessita de ferramentas para depuracao e profiler. Estas ferramentas sao faceis de serem construıdas para linguagens estritas, no entanto, sao muito difıceis de serem construıdas para linguagens lazy, onde a ordem de avaliacao nao e conhecida ap riori. Verifica-se uma excecao em Haskell, onde muitas ferramentas de profiler jae stao disponıveis.

• Treinamento. Para programadores imperativos e muito difıcil programar funcionalmente.

Uma solucao imperativa em aisf acil de ser entendida e de ser encontrada em livros ou artigos. Uma solucao funcional demora mais tempo para ser criada, apesar de muito mais elegante. Por este motivo, muitas linguagens funcionais atuais proveem um escape para o estilo imperativo. Isto pode ser verificado em ML que nao e considerada uma linguagem funcional pura, porque permite atribuicoes destrutivas. Haskell e uma linguagem funcional pura, mas consegue imitar as atribuicoes das linguagens imperativas utilizando uma teoria funcional complexa que eas emantica de acoes, implementadas atraves de monadas2.

• Popularidade. Se um gerente escolher uma linguagem funcional para ser utilizada em um projeto e este falhar, provavelmente ele sera crucificado. No entanto, se ele escolher C ou C++ e nao tiver sucesso, tem a seu favor o argumento de que o sucesso de C++ jaf oi verificado em inumeros casos e em varios locais.

2As emantica de acoes e um tema tratado no Capıtulo 6. Os monadas nao sao aqui tratados, uma vez que seu estudo requer, como pre-requsito, o conhecimento aprofundado sobre implementacao de linguagens funcionais.

• Desempenho. Hau ma decada atras, os desempenhos dos programas funcionais eram bem menores que os dos programas imperativos, mas isto tem mudado muito ultimamente. Hoje, os desempenhos de muitos programas funcionais sao melhores ou pelo menos estao em “pes de igualdade” com seus correspondentes em C. Isto depende da aplicacao. Java tem uma boa aceitacao e, no entanto, seu desempenho e muito inferior a C, na grande maioria das aplicacoes. Na realidade, existem linguagens com alto desempenho que nao sao muito utilizadas e existem linguagens com desempenho mediano com alta taxa de utilizacao. Desempenho e um fator importante, mas nao tem se caracterizado como um fator decisivo na escolha de uma linguagem.

Resumidamente, existem muitos fatores que desencorajam a escolha de linguagens funcionais como forma de se codificar programas. Para ser fortemente utilizada, uma linguagem deve suportar trabalho interativo, possuir bibliotecas extensas, ser altamente portavel, ter uma implementacao estavel e facil de ser instalada, ter depuradores e profilers, ser acompanhada de cursos de treinamentos e ja ter sido utilizada, com sucesso, em uma boa quantidade de projetos.

Para Wadler [37] todos estes requisitos jas ao perfeitamente atendidos por algumas linguagens funcionais, por exemplo Haskell. Para ele o que ainda existe e um preconceito injustificavel por parte de alguns programadores de outros paradigmas de programacao. No entanto, para a felicidade e consolo dos admiradores das linguagens funcionais, esta cultura tem se modificado, ed e forma rapida, ao longo dos ultimos anos.

A nosso ver, o que existe mesmo eaf altad e informacao e conhecimento do que realmente e programacao funcional e quais as suas vantagens e desvantagens em relacao a programacao em outros paradigmas. Esta Apostila tenta prover subsıdios para que seus usuarios possam iniciar um processo de discussao sobre o tema. Para desencadear este processo, e necessario comecar pelo entendimento da relacao entre a programacao funcional e a programacao estruturada.

Princıpios da programacao estruturada

Hoare enumerou seis princıpios fundamentais da estruturacao de programas [24]:

1. Transparencia de significado. Este princıpio afirma que o significado de uma expressao, como um todo, pode ser entendido em termos dos significados de suas sub-expressoes. Assim, o significado da expressao E+F depende simplesmente dos significados das subexpressoes E e F, independente das complicacoes de cada uma delas.

2. Transparencia de propositos. Textualmente, Hoare diz: “o proposito de cada parte consiste unicamente em sua contribuicao para o proposito do todo”. Assim, em E+F , ounico proposito de E e computar o numero que sera o operando esquerdo do operador “+”. Isto significa que seu proposito nao inclui qualquer efeito colateral.

3. Independencia das partes. Este princıpio apregoa que os significados de duas partes, nao sobrepostas, podem ser entendidos de forma completamente independente, ou seja, E pode ser entendida independentemente de F e vice versa. Isto acontece porque o resultado computado por um operador depende apenas dos valores de suas entradas.

(Parte 1 de 9)

Comentários