Programação Funcional em Haskell

Programação Funcional em Haskell

(Parte 3 de 9)

Esta Apostila

Esta Apostila e composta desta Introducao e 6 (seis) Capıtulos. Nesta Introducao, e colocada, de forma resumida, a importancia das linguagens funcionais e a necessidade de estudar o λcalculo e justificar sua escolha como a linguagem intermediaria entre as linguagens funcionais e as linguagens de maquina. E necessario saber que as linguagens funcionais sao importantes porque aumentam a modularidade dos sistemas atraves das funcoes de alto nıvel e do mecanismo de avaliacao preguicosa.

OC apıtulo 1 ed edicado a fundamentacao das linguagens funcionais, abordando as principais diferencas entre elas e as linguagens de outros paradigmas. O mundo das linguagens de programacao e dividido entre o mundo das expressoes e o mundo das atribuicoes, evidenciando as vantagens do primeiro mundo em relacao ao segundo.

No Capıtulo 2, e introduzido o λ-calculo, sua evolucao historica e como ele e usado nos dias atuais. A teoria e colocada de maneira simples e introdutoria, dado o objetivo da Apostila.

No Capıtulo 3, inicia-se a programacao em Haskell. Sao mostrados seus construtores e uma serie de exemplos, analisando como as funcoes podem ser construıdas em Haskell. Sao mostrados os tipos de dados primitivos adotados em Haskell e os tipos estruturados mais simples que sao as tuplas. No Capıtulo, tambem sao mostrados os esquemas de provas de programas, juntamente com varios exercıcios, resolvidos ou propostos.

OC apıtulo 4 ed edicadoa listas em Haskell. Este Capıtulo se torna necessario, dada a importancia que este tipo de dado tem nas linguagens funcionais. Neste Capıtulo, sao mostradas as compreensoes ou expressoes ZF e tambem e mostrada a composicao de funcoes como uma caracterıstica apenas das linguagens funcionais, usada na construcao de funcoes. Um tema importanteeq ue e discutido neste Capıtulo se refere as formas de provas da corretude de programas em Haskell, usando inducao estrutural sobre listas. No Capıtulo sao mostrados variose xemplosr esolvidose ,a o final, sao colocados varios exercıcios a apreciacao do leitor.

No Capıtulo 5, sao mostradas as type class, como formas de incluir um determinado tipo de dados em em uma classe de tipos que tenham funcoes em comum, dando origem a sobrecarga como forma de polimorfismo. Tambem sao mostrados os tipos de dados algebricos, o sistema de modulos adotado em Haskell, os tipos de dados abstratos e o tratamento de excecoes. O Capıtulo terminac om umar evisao sobre o sistema de avaliacao lazy, notadamente na construcao de listas potencialmente infinitas.

OC apıtulo 6 ed edicado as operacoes dee ntrada es aıda em Haskell, evidenciado o uso de arquivos ou dispositivos como saıda ou como entrada. Este processo em Haskell ef eito atraves do mecanismo de “acoes”, cuja semantica representa o conteudo principal do Capıtulo.

A Apostila termina com as principais referencias bibliograficas consultadas durante s sua elaboracao.

Capıtulo 1 Programacao Funcional

”We can now see that in a lazy implementation based on suspensions, we can treat every function in the same way.

Indeed, all functions are treated as potentially non-strict and their argument is automatically suspended.

Later, is and when it is needed, it will be unsuspended (strictly evaluated).” (Antony D. T. Davie in [7])

1.1 Introducao

A programacao funcional teve inıcio antes da invencao dos computadores eletronicos. No inıcio do seculo X, muitos matematicos estavam preocupados com a fundamentacao matematica, em particular, queriam saber mais sobre os conjuntos infinitos. Muito desta preocupacao aconteceu por causa do surgimento, no final do seculo XIX, de uma teoria que afirmava a existencia de varias ordens de infinitos, desenvolvida por George Cantor (1845-1918) [24]. Muitos matematicos, como Leopold Kronecker (1823-1891), questionaram a existencia destes objetos e condenaram a teoria de Cantor como pura “enrolacao”. Estes matematicos defendiam que um objeto matematico so poderia existir se, pelo menos em princıpio, pudesse ser construıdo. Por este motivo, eles ficaram conhecidos como “construtivistas”.

Mas o que significa dizer que um numero, ou outro objeto matematico, seja construtıvel?

Esta ideia foi desenvolvida lentamente, ao longo de muitos anos. Guiseppe Peano (1858-1932), um matematico, logico e linguista, escreveu “Formulaire de Mathematique” (1894-1908), onde mostrou como os numeros naturais poderiam ser construıdos atraves de finitas aplicacoes da funcao sucessor.C omecando em 1923, Thoralf Skolen (1887-1963) mostrou que quase tudo da teoria dos numeros naturais poderia ser desenvolvido construtivamente pelo uso intensivo de definicoes recursivas, como as de Peano. Para evitar apelos questionaveis sobre o infinito, pareceu razoavel chamar um objeto de construtıvel se ele pudesse ser construıdo em um numero finito de passos, cada um deles requerendo apenas uma quantidade finita de esforco. Assim, nas primeiras decadas do seculo X, ja existia consideravel experiencia sobre as definicoes recursivas de funcoes sobre os numeros naturais.

A cardinalidade (quantidade de elementos) dos conjuntos finitos era facil de ser conhecida, uma vez que era necessario apenas contar seus elementos. Ja para os conjuntos infinitos, esta tecnica nao podia ser aplicada. Inicialmente, era necessario definir o que era realmente um conjunto infinito. Foi definido que um conjunto era infinito se fosse possıvel construir uma correspondencia biunıvoca entre ele e um subconjunto proprio dele mesmo. Foram definidos os conjuntos infinitos enumeraveis, que foram caracterizados pelos conjuntos infinitos para os quais fosse possıvel construir uma correspondencia biunıvocac om oc onjuntod os numeros naturais, N. Assim, todos os conjuntos infinitos enumeraveis tinham a mesma cardinalidade, que foi definida por ℵ01. Assim, a cardinalidade do conjunto dos numeros inteiros, Z,t ambem e ℵ0,u ma vez que ep ossıvel construir uma correspondencia biunıvoca entre Z e N. Os conjuntos infinitos com os quais nao fosse possıvel estabelecer uma correspondencia biunıvoca entre eles e N, foram chamados de infinitos nao enumeraveis. A cardinalidade do conjuntos dos numeros reais, R, que e infinito nao enumeravel, e2 ℵ0.

1.2 Historico

Na decada de 1930, existiram muitas tentativas de formalizacao do construtivismo, procurando caracterizar o que era camputabilidade efetiva, ou seja, procurava-se saber o que realmente podia ser computado. Uma das mais famosas tentativas foi a definicao de Turing sobre uma classe de maquinas abstratas, que ficaram conhecidas como “maquinas de Turing”, que realizavam operacoes de leitura e escritas sobre uma fita de tamanho finito. Outra tecnica, baseada mais diretamente nos trabalhos de Skolen e Peano, consistia no uso de “f uncoes recursivas gerais”, devida a Godel. Uma outra tecnica, com implicacao importante na programacao funcional, foi ac riacao do λ-calculo, desenvolvido por Church e Kleene, no inıcio da decada de 1930. Outra nocao de computabilidade, conhecida como “Algoritmos de Markov”,t ambem foi desenvolvida nesta mesma epoca. O que ei mportante e que todas estas nocoes de computabilidade foram provadas serem equivalentes. Esta equivalencia levou Church, em 1936, a propor o que ficou conhecida como a Tese de Church2, onde ele afirmava que “uma funcao era computavel se ela fosse primitiva recursiva” [5].

Isto significa que, jan a decada anterior ad ecada da invencao do computador eletronico, muitos matematicos e logicos ja haviam investigado, com profundidade, a computabilidade de funcoes e identificado a classe das funcoes computaveis como a classe das funcoes primitivas recursivas.

Op roximo invento importante na historia da programacao funcional foi a publicacao de John

McCarthy, em 1960, sobre LISP. Em 1958, ele investigava o uso de operacoes sobre listas ligadas para implementar um programa de diferenciacao simbolica. Como a diferenciacao e um processo recursivo, McCarthy sentiu-se atraıdo a usar funcoes recursivas e, alem disso, ele tambem achou conveniente passar funcoes como argumentos para outras funcoes. McCarthy verificou que o λ-calculo provia uma notacao muito conveniente para estes propositos e, por isto mesmo, ele resolveu usar a notacao de Church em sua programacao.

Em 1958, foi iniciado um projeto no MIT com o objetivo de construir uma linguagem de programacao que incorporasse estas ideias. O resultado ficou conhecido como LISP 1, que foi descrita por McCarthy, em 1960, em seu artigo “Recursive Functions of Symbolic Expressions and Their Computation by Machine” [24]. Este artigo mostrou como varios programas complexos podiam ser expressos por funcoes puras operando sobre estruturas de listas. Este fato e caracterizado, por alguns pesquisadores, como o marco inicial da programacao funcional.

No final da decada de 1960 e inıcio da decada de 1970, um grande numero de cientistas da Computacao comecaram a investigar a programacao com funcoes puras, chamada de “programacao aplicativa”,u ma vez que a operacao central consistia na aplicacao de uma funcao a seu argumento. Em particular, Peter Landin (1964, 1965 e 1966) desenvolveu muitas das ideias centrais para o uso, notacao e implementacao das linguagens de programacao aplicativas, sendo importante destacar sua tentativa de traduzir a definicao de uma linguagem nao funcional, Algol

1ℵ e uma letra do alfabeto arabe, conhecida por Aleph. 2Na realidade, nao se trata de uma tese, uma vez que ela nunca foi provada. No entanto, nunca foi exibido um contra-exemplo, mostrando que esta conjectura esteja errada.

60, para o λ-calculo. Baseados neste estudo, Strachey e Scott construiram um metodo de definicao da semantica de linguagens de programacao, conhecido como “semantica denotacional”. Em essencia, a semantica denotacional define o significado de um programa, em termos de um programa funcional equivalente.

No entanto, a programacao aplicativa, que havia sido investigada por um reduzido numero de pesquisadores nos anos de 1960 e 1970, passou a receber uma atencao bem maior apos 1978, quando John Backus, o principal criador do FORTRAN, publicou um paper onde fez severas crıticas as linguagens de programacao convencionais, sugerindo a criacao de um novo paradigma de programacao. Ele propos o paradigma chamado de “programacao funcional” que, em essencia, e a programacao aplicativa com enfase no uso de funcionais, que sao funcoes que operam sobre outras funcoes. Muitos dos funcionais de Backus foram inspirados pela linguagem APL, uma linguagem imperativa, projetada na decada de 1960, que provia operadores poderosos, sem atribuicao, sobre estruturas de dados. A partir desta publicacao, o numero de pesquisadores na area de linguagens de programacao funcional tem aumentado significativamente.

1.3 Programacao com expressoes

Para MacLennan [24] qualquer linguagem de programacao se divide em dois mundos, a saber: o mundo das expressoes (aritmeticas, relacionais, booleanas, etc.) e o mundo das atribuicoes. No primeiro caso, o unico objetivo e encontrar o valor de uma expressao atraves de um processo de “avaliacao”.J a no segundo caso, o mundo das atribuicoes e dividido em dois tipos. O primeiro altera o controle do fluxo de um programa, usando comandos de selecao, como if, for, while, repeat, goto e chamadas a procedimentos. O segundo tipo de atribuicao altera o estado da memoria (principal ou secundaria) do computador. Nos dois tipos, a palavra chave e alterar alguma coisa; no primeiro tipo, altera o fluxo de controle e, no segundo, altera o estado da maquina.

No mundo das atribuicoes, a ordem em que as coisas sao feitas tem importancia fundamental. Por exemplo, e sequencia i = i +1 ; a = a ∗ i; tem um efeito diferente da sequencia, a seguir, onde a ordem ei nvertida. a = a ∗ i; i = i +1 ;

Analisemos agora a expressao z =( 2 ∗ a ∗ y + b) ∗ (2∗ a ∗ y +c). A expressao do lado direito do sinal de atribuicao contem uma sub-expressao em comum (2 ∗ a ∗ y) e qualquer compilador, com um mınimo de otimizacao, transformaria este fragmento de codigo, na seguinte forma:

No mundo das expressoes, e seguro promover esta otimizacao porque qualquer sub-expressao, no caso 2∗a∗y, sempre tem o mesmo valor. Analisemos agora, uma situacao similar no mundo das atribuicoes.

onde tambem verificamos uma sub-expressao em comum (2 ∗ a ∗ y). Se for realizada a mesma fatoracao anterior, teremos:

Esta otimizacao altera o valor da variavel z, porque os valores de y sao diferentes nas duas ocorrencias da sub-expressao 2*a*y. Portanto, nao ep ossıvel realizar esta otimizacao. Apesar da analise sobre a existencia, ou nao, de dependencia entre sub-expressoes poder ser feita por um compilador, isto requer tecnicas sofisticadas de analise de dependencias no fluxo. Tais analises, normalmente sao caras para serem realizadas e difıceis de serem implementadas corretamente. De forma resumida, ef acil e seguro realizar estas otimizacoes nas expressoes e difıcil de serem feitas no mundo das atribuicoes. Fica clara a vantagem das expressoes sobre as atribuicoes. O proposito da programacao funcional e extender as vantagens das expressoes para as linguagens de programacao.

1.4 Independenciad ao rdem de avaliacao

Para entender as vantagens do mundo das expressoes e as fontes de suas propriedades, en ecessario investigar a ordem de avaliacao nas expressoes aritmeticas. Avaliar alguma coisa significa encontrar seu valor. Assim, podemos avaliar a expressao aritmetica ‘5 ∗ 4 + 3’ encontrando seu valor que, no caso, e 23.

Podemos tambem avaliar a expressao (3ax + b)(3ax + c)? A resposta en ao; a menos que sejam conhecidos os valores de a, b, c e x. O valor desta expressao e dependente de um contexto onde ela seja avaliada. Para isto, vamos avaliar esta expressao em um contexto em que a =2 , b =3 , c = −2e x = 3. Esta avaliacao pode ser iniciada em varios pontos. Por motivo de regularidade, ela sera feita da esquerda para a direita, lembrando, no entanto, que ela tambem pode ser realizada da direita para a esquerda. Colocando todos os operadores de forma explıcita, a expressao se transforma em:

Para se realizar a primeira operacao, a multiplicacao 3 ∗ a,e necesario saber o valor de a que, neste contexto, e 2. Substituindo este valor na expressao, ela se torna

Agora pode-se dar prosseguimento ao processo de avaliacao, substituindo a expressao por uma nova expressao:

As equencia completa de todos os passos realizados no processo de avaliacao e mostrada a seguir, onde a flexa dupla (⇒) significa a transformacao de expressoes.

Figura 1.1: Arvore representativa da expressao (3ax+b)(3ax+c).

Figura 1.2: Representacao do processo de avaliacao.

Observe que se a avaliacao tivesse sido iniciada pelo operando da direita do operador de multiplicacao, ‘∗’, o resultado seria exatamente o mesmo, ou seja, qualquer ordem de avaliacao produziria o mesmo resultado, 336. Isto ocorre porque, na avaliacao de uma expressao pura3, a avaliacao de uma sub-expressao nao afeta o valor de qualquer outra sub-expressao, uma vez que nao existe qualquer dependencia entre elas. Na realidade, ep ossıvel realizar as avaliacoes destas sub-expressoes de forma concorrente. Ef acil entender esta independencia da ordem de avaliacao, utilizando uma arvore de avaliacao, conforme pode ser visualizado na Figura 1.1, onde as variaveis ficam nas folhas e as operacoes nos nos internos.

Nesta estrutura, cada operacao em um no depende apenas das operacoes dos nos abaixo dele na arvore. A avaliacao de uma sub-arvore afeta apenas a parte da arvore acima desta sub-arvore, ou seja, nao afeta as sub-arvores que estejam a sua esquerda ou a sua direita. O processo de avaliacao e iniciado com a colocacao de alguns valores nas folhas. Os nos internos sao avaliados em qualquer ordem, sob demanda, podendo ate mesmo serem avaliados em paralelo. Cada operacao depende apenas de suas entradas que sao os valores dos nos filhos. Este processo de avaliacao pode ser visto graficamente na Figura 1.2.

A avaliacao de um no consiste na “decoracao” de cada no interno com o valor resultante da avaliacao dos nos abaixo dele. O processo de avaliacao terminaq uando ar aiz daarvore for decorada com o valor da expressao completa. Istop ode ser viston aarvore da Figura 1.3.

3Uma expressao e dita pura quando nao realiza qualquer operacao de atribuicao, explıcita ou implıcita. 15

Figura 1.3: Estado da arvore apos a avaliacao total da expressao.

Como afirmado anteriormente, diversos processos podem acontecer em paralelo, na decoracao da arvore, desde que seja observada a estrutura de arvore. Isto significa que sempre se chega ao mesmo valor.

Esta propriedade verificada nas expressoes puras, ou seja, a independencia da ordem de avaliacao, e chamada de “propriedade de Church-Rosser”. Ela permite a construcao de compiladores capazes de escolher a ordem de avaliacao que faca o melhor uso dos recursos da maquina. A possibilidade de que a avaliacao seja realizada em paralelo, implica na possibilidade de utilizacao de multiprocessadores de forma bastante natural.

(Parte 3 de 9)

Comentários