Sobre o título deste blog

fevereiro 26, 2011

Geralmente todo blogueiro possui algum motivo especial para a escolha do título de seu blog. Eu não poderia ser escapar a esta regra.

Neste blog, além de discorrer sobre assuntos diversos, prentendo publicar textos sobre lógica e programação funcional. Então porque o título “Esta frase é falsa”?

Este consiste de um conhecido paradoxo da lógica, que apesar de sua simplicidade, mostra os “diabos” que residem nos cantos obscuros da matemática.

Se a proposição “esta frase é falsa” for verdadeira, temos que ela será falsa, já que a proposição afirma que ela própria é falsa. Por sua vez se a considerarmos falsa, temos que ela será verdadeira, pois ela própria afirma que é falsa, sendo assim só pode ser verdadeira.

 

Anúncios

O que já li este ano – parte 1

fevereiro 4, 2011

Como disse em um post anterior, este ano pretendo ler mais. Até o presente momento já li dois livros, que sinceramente me decepcionaram. O primeiro destes é o clássico O médico e o monstro de Robert Louis Stevenson e  o segundo Deus : um delírio de Richard Dawkins.

O médico e o mostro conta a famosa história sobre o Dr. Jekill e sua outra “personalidade”, Mr. Hyde. Sem dúvida o livro é bom, porém quando comparado a Drácula de Bram Stoker ou Frankstein de Mary Sheley, permitam-me, esta história chega a ser infantil. No geral, é um livro bom, e vale a leitura. Porém eu esperava mais.

Deus: Um delírio de Richard Dawkins chega a ser entediante. Acredito que o problema deste livro é que o autor repete demasiadamente os seus argumentos para mostrar porquê é muito improvável que deus exista. Neste caso, acho que o livro chega a ser um pouco cansativo devido a esta repetição. Porém, gostaria de recomendar este livro para pessoas que ainda possuem algum tipo de dúvida quanto a inexistência de deus e que buscam explicações lógicas para isto.

Agora que relatei os dois livros lidos até o presente momento, o próximo da lista é O Evangelho Segundo Jesus Cristo de José Saramago.

Homenagem…

janeiro 30, 2011

Este ano fui escolhido como paraninfo da turma de Sistemas de Informação. Nesta última sexta-feira, ocorreu a cerimônia de colação de grau no anfiteatro de uma escola em minha cidade. Como de praxe, todo paraninfo deve elaborar um discurso. Segue na íntegra o texto lido na cerimônia:

 

Magnífico Reitor da Universidade Federal de Ouro Preto,

Excelentíssimo Diretor do ICEA,

Excelentíssimo Chefe do DECEA,

Demais membros da mesa diretora,

Senhoras e Senhores,

 

Meus distintos alunos,

 

Primeiramente, gostaria de agradecer-lhes por este momento. É uma grande honra ser escolhido por esta turma tão especial de bacharéis, como paraninfo.

Hoje vocês se formam. Diferentemente do que ocorria no passado, hoje não formam-se prontos. Nunca estarão enquanto vivos. Os tempos têm mudado e ainda mais no caminho escolhido, o caminho da tecnologia, não há espaço para sermos competentes, apenas para estarmos momentaneamente nesta condição. Por isto atentem para o aprendizado contínuo que será a marca de suas carreiras bem sucedidas.

Mas nesta mensagem, pretendo fugir do tema “formação profissional”. A honraria que me concedem me instiga a compartilhar com vocês mais do que algum conselho sobre carreira. Se permitem dar algum conselho, este é, citando o filósofo Nietzsche, “Torna-te quem tu és”. O que há em vocês é mais complexo que qualquer algoritmo, linguagem de programação ou protocolo de rede. Invistam em conhecer a vocês mesmos pelo menos o mesmo tempo que dedicam aos estudos de linguagens, estruturas de dados ou protocolos de redes. Só depois de descobrirem quem são vocês, poderão construir algo, pois é a vocês mesmos que estarão construindo enquanto estiverem esculpindo suas obras.

Finalmente, deixem-me compartilhar uma pequena e talvez já conhecida história: dois colegas saem do trabalho para almoçar. Cai um temporal e ambos se molham. Ao chegar ao trabalho, um explica ao patrão: saímos para almoçar, caiu um temporal e nos molhamos. O empresário balança a cabeça e decepciona-se. Mas o segundo conta a sua versão: saímos para almoçar, eu esqueci o guarda-chuva, caiu um temporal e nos molhamos. Agora o empreendedor sabe que tem alguém com quem contar, pois no momento em que trazemos para nós a responsabilidade, daí somos potentes para mudar o futuro. O primeiro funcionário sempre dependerá do humor da estação para ficar seco, o segundo toma as rédeas da vida para si e sabe que pode por seu próprio talento e ação modificar o resultado, pois se ele foi o culpado por estar molhado, pode decidir estar seco amanhã. Assumam, pois, suas escolhas. Ao final perceberão que são resultado destas.

Muito obrigado e boa sorte na carreira de sucesso que os aguarda.

 

Um novo ano começou…

janeiro 8, 2011

Como havia muito tempo que não postava nada, resolvi estreiar o novo ano com um post de “resoluções” para 2011. No ano de 2010, não tive tempo para ler bons livros, o que pretendo corrigir este ano. A seguir estão listados alguns dos livros que pretendo ler. Ao final de 2011, pretendo fazer um “balanço” do que consegui cumprir de minhas resoluções.

1 – Deus, Um Delírio de Richard Dawkins.

Neste livro Dawkins, renomado Zoólogo inglês apresenta argumentos contudentes para explicar o porquê é muito improvável que deus exista. Dawkins usa seu conceito de memes (idéias que agem como os genes) e o darwinismo para propor explicações à tendência da humanidade de acreditar num ser superior. E desmonta um a um, com base na teoria das probabilidades e da evolução das espécies, os argumentos que defendem a existência de deus, dedicando especial atenção ao design inteligente, tentativa criacionista de harmonizar ciência e religião.

2 – O Evangelho Segundo Jesus Cristo de José Saramago.

Apesar de já possuir este livro há algum tempo, ainda não tive tempo de lê-lo. Neste livro, Saramago apresenta uma versão do evangelho apresentando um Jesus Cristo mais humano e menos místico.

3 – O guia do Mochileiro das Galáxias, O Restaurante no Fim do Universo e O Universo a Vida e Tudo Mais de Douglas Adams

Clássicos absolutos da ficção científica! Já ouvi falar muito destes livros e sempre tive vontade de lê-los, mas como sempre faltou tempo… Espero que este ano consiga arranjar tempo para boas risadas. 42! rs

4 – A Razão Áurea: A História de \phi um número supreendente de Mário Lívio.

Em Razão Áurea, o astrofísico e matemático Mario Livio, esclarece as origens das ocorrências da razão áurea na natureza e seus usos na arquitetura, na pintura e na música. Aplicações deste número são frequentes em cursos de matemática discreta, por isso meu interesse em lê-lo.

5 – Incompletude: A Prova e o Paradoxo de Kurt Godel de Rebecca Goldstein

O famoso teorema da incompletude de Godel é uma das descobertas científicas mais importantes do século passado e até o presente momento, não conheço nenhuma apresentação deste simples e acessível para cursos de graduação ou para leigos em geral. Quero ler este livro, que segundo críticas, preenche esta lacuna sendo acessível a pessoas com pouco ou nenhum conhecimento de lógica formal.

6 – Interactive Theorem Proving and Program Development: The Coq’Art – The Calculus of Inductive Constructions de Yves Bertot e Pierre Casterán

Este livro é o único publicado sobre o assistente de provas Coq. Além de apresentar exemplos práticos de uso desta ferramenta, são apresentados os fundamentos lógicos desta. Sem dúvida, leitura importantíssima!

Dependências Funcionais

junho 21, 2010

Nesta série de posts, apresentarei os fundamentos de dependências funcionais e sua aplicação ao processo de especialização de tipos na linguagem Haskell. Dependências funcionais foram originalmente introduzidas há anos no estudo de bancos de dados relacionais [1]. Antes de apresentarmos a aplicação de dependências funcionais para a verificação / inferência de tipos, será feita uma breve revisão destes conceitos sob o enfoque da teoria de bancos de dados relacionais.

1 – Relações e Bancos de Dados Relacionais.

Um banco de dados relacional pode ser descrito como um conjunto de relações, onde cada uma destas pode ser vista como uma tabela com zero ou mais tuplas. A seguinte tabela, por exemplo, representa dados de uma consulta que representa os resultados de um questionário hipotético realizado com funcionários de uma empresa.

Nome Bairro Transporte
Alice Harbortown Automóvel
Alice Harbortown A pé
Bob Hillville Bicicleta
Bob Hillville Ônibus
Bob Hillville Automóvel
Carol Hubford Ônibus
David Hubford Trem

Esta tabela possui três colunas (campos) e sete tuplas (registros). Cada registro pode ser descrito por uma tupla (e,b,t) onde e é o nome de um empregado, b é um bairro e t é um meio de transporte. De maneira mais geral, um banco de dados pode ser descrito por um esquema que atribui um nome para cada tabela e também um nome (e possivelmente um tipo) para cada coluna.

Mais formalmente, uma tabela T é uma relação sobre uma família indexada de conjuntos \{D_{i}\}_{i\in I}, onde I é um conjunto de índices (i.e. conjunto de nomes de colunas) e D_{i} é o tipo dos valores da coluna i. Na tabela de exemplo apresentada anterioremente, o conjunto de índices  seria I=\{Nome, Bairro, Transporte \}. Os elementos desta tabela são tuplas, onde cada uma destas é uma família indexada de valores \{t_{i}\}_{i\in I} tal que t_{i}\in D_{i} para cada i\in I. Note que, se I=\{1,...,n\}, então (t_{1},t_{2},...,t_{n})\in D_{1}\times D_{2}\times ...\times D_{n}. Se i \in I, então escrevemos t_{i} para o i-ésimo componente de t. Similarmente, se X\subseteq I, então t_{X}  representa a projeção da tupla $t$ sobre as colunas c_{i}\in X.

2 – Dependências Funcionais

Um esquema de banco de dados irá tipicamente impor certas restrições de integridade para caracterizar a estrutura da informação que é permitida em tabelas do banco. Na tabela de exemplo apresentada anteriormente, é razoável assumir que cada funcionário resida em somente um bairro, isto é, na tabela acima um funcionário deverá estar associado a somente um bairro. Tal restrição é capturada através de uma dependência funcional, representada como \{ Nome \}\rightsquigarrow\{Bairro\}, que garante que dois registros do mesmo empregado devem ter o mesmo bairro associado. Todavia, não existe dependência similar entre os campos Nome e Transporte, uma vez que alguns funcionários utilizam mais de um meio de transporte. É tarefa do SGDB garantir que dependências são mantidas a medida que registros são incluídos ou atualizados. Como exemplo, considere a situação em que o funcionário David se mudasse do bairro Hubford para o bairro Hillville. Neste caso teríamos que a tupla t_{1}=(David, Hubford, Trem) deveria ser alterada para t_{2}=(David, Hillville, Trem), o que não violaria a dependência \{ Nome \}\rightsquigarrow\{Bairro\}. Mas, não poderíamos simplesmente incluir o registro t_{2}, uma vez que esta inclusão não atenderia a restrição especificada por \{ Nome \}\rightsquigarrow\{Bairro\}.

2.1 – Formalizando Dependências Funcionais

Formalmente, se T é uma tabela indexada por um conjunto I, então uma dependência funcional é um par X \rightsquigarrow Y, X determina Y, onde tanto X quanto Y são subconjuntos de I. Se X, Y são conjuntos de elementos conhecidos, isto é X=\{x_{1},x_{2},...,x_{n}\} e Y=\{y_{1},y_{2},...,y_{m}\}, podemos escrever a dependência X \rightsquigarrow Y como x_{1},x_{2},...,x_{n}\rightsquigarrow y_{1},y_{2},...,y_{m}. Se a tabela T satisfaz a dependência X \rightsquigarrow Y, então toda tupla em Y é unicamente determinada pelos valores correspondentes daquela tupla em X. Esta noção pode ser formalizada da seguinte maneira:

T\models X\rightsquigarrow Y \Leftrightarrow \forall t,s \in T. (t_{x} = s_{x})\Rightarrow (t_{y} = s_{y})

A relação T\models X\rightsquigarrow Y pode ser entendida como: “a tabela T satisfaz a dependência X\rightsquigarrow Y“. Uma extensão útil para esta notação é quando consideramos um conjunto de dependências:

T\models F \Leftrightarrow \forall (X \rightsquigarrow Y) \in F. T\models X\rightsquigarrow Y

Outra maneira de entender as dependências funcionais é por meio de regras de inferência para reflexividade, transitividade e acréscimo:

\frac{Y\subseteq X}{X\rightsquigarrow Y}

\frac{X\rightsquigarrow Y\,\,\,\, Y\rightsquigarrow Z}{X\rightsquigarrow Z}

\frac{X\rightsquigarrow Y}{X\cup Z\rightsquigarrow Y\cup Z}

Estas regras são frequentemente denominadas de axiomas de Armstrong, uma vez que William Armstrong[2] foi o primeiro a mostrar que estas são corretas e completas. Estas regras também podem ser estendidas para um conjunto de dependências; dizemos que F_{1}\vdash F_{2} se todas as dependências de F_{2} podem ser deduzidas a partir das dependências de F_{1}. Se F_{1}\vdash F_{2} e F_{2}\vdash F_{1} então os conjuntos de dependências F_{1} e F_{2} são equivalentes e podemos nos referir a uma destes como sendo a cobertura do outro conjunto de regras.

O fecho, J_{F}^{+}, de um conjunto J\subseteq I com respeito a um conjunto de dependências funcionais F é o menor conjunto tal que:

  • J\subseteq J_{F}^{+}
  • Se X\rightsquigarrow Y\in F, e X\subseteq J_{F}^{+}, então Y\subseteq J_{F}^{+}.

Intuitivamente, o fecho J_{F}^{+} é apenas o conjunto de índices que são unicamente determinados, seja direta ou indiretamente, pelos índices em J e as dependências em F.

Conclusão

Dependências funcionais são um conceito consolidado da teoria de bancos de dados relacionais. Neste post foi apresentado uma breve introdução aos principais conceitos relacionados a teoria de bancos de dados relacionais. Nos próximos posts será apresentada a aplicação destes conceitos para verificação / inferência de tipos na linguagem Haskell.

Referências

1 – E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6): 377-387, 1970.

2 – W.W. Armstrong. Dependency structures of data base relationships. In IFIP Congress, 580-583, 1974.

The Expression Problem

abril 25, 2010

Philip Wadler apresentou em [1] o chamado “The Expression Problem” que pode ser enunciado da seguinte maneira:

O objetivo é definir um tipo de dados por casos, onde pode-se adicionar novos casos ao tipo de dados e novas funções sobre este tipo, sem recompilar código existente e garantindo que erros de tipo sejam sempre encontrados.

Além de enunciá-lo, Wadler apresentou uma solução para este em GJ (antiga versão experimental de Java com suporte a polimorfismo paramétrico).

Algumas soluções já foram propostas e publicadas para este problema, como por exemplo em [2]. Porém, a solução mais elegante, que conheço, para este problema é a apresentada em [3]. Swierstra apresenta como estender tipos de dados com novos casos (construtores de dados) e novas funcionalidades. Para isso, cada tipo de dados é representado com um coproduto dos diferentes construtores de dados que formam este tipo e funcionalidades, por sua vez, são implementadas utilizando funções sobrecarregadas (classes de tipos e instâncias em Haskell).

Como o problema de estender tipos de dados e funcionalidades sem recompilar código existente é recorrente no desenvolvimento de software, é útil saber como pode-se obter uma solução elegante para isto utilizando Haskell. A solução utiliza algumas extensões presentes no compilador GHC, são elas:

* TypeOperators
* MultiParamTypeClasses
* FlexibleInstances
* FlexibleContexts
* IncoherentInstances
* UndecidableInstances

A seguir apresento um pequeno avaliador de expressões aritméticas onde pode-se estender tanto a sintaxe das expressões avaliadas quanto o conjunto de operações aplicadas sobre estas expressões.

1 – Avaliando Expressões Aritméticas.

1.1 – Definindo Expressões

O primeiro passo é representar o tipo de expressões de maneira que este possa ser parametrizado pelos construtores de dados que podem ser acrescentados a este. Para isso, representaremos uma expressão aritmética pelo tipo Expr, apresentado a seguir:

data Expr f = In { out :: f (Expr f) }

Observe que o tipo de dados Expr, é parametrizado por uma variável de tipo de kind \star\rightarrow\star. A função principal do tipo Expr é ser um operador de ponto fixo dos construtores que parametrizarão este tipo de dados. Até o presente momento nenhum construtor de dados que represente algum tipo de expressão aritmética foi definido. O único construtor de dados definido para o tipo Expr é:

In :: f (Expr f) \rightarrow Expr f

Que não representa nenhuma expressão aritmética. Então como definimos expressões que envolvam adição, multiplicação, subtração, etc.? Para alcançar os objetivos de definir novos construtores de dados sem a necessidade de alterar código existente, temos que representar construtores de dados como novos tipos de dados que representam os diferentes construtores para expressões aritméticas. Como exemplo, considere as seguintes declarações que representam respectivamente valores inteiros e a soma de duas expressões quaisquer:

data Val e = Val Int

data Add e = Add e e

Com isso, temos que uma expressão formada exclusivamente por valores inteiros pode possuir o seguinte tipo:

type IntExpr = Expr Val

Expressões que o tipo IntExpr são da forma In (Val x) para qualquer número inteiro x. O tipo de dados Val não utiliza em seu construtor seu parâmetro e, uma vez que, valores inteiros são expressões que não possuem um componente recursivo (isto é, não possuem outras expressões como descendentes em uma árvore).

Por sua vez, o tipo Add utiliza seu parâmetro de tipo para representar que a operação de adição recebe como argumento duas expressões de tipo e.

Tipos de dados que representam constantes inteiras ou adições não são interessantes isoladamente. Para combinar estes novos tipos, devemos introduzir um tipo de dados que representa um coproduto de construtores de tipos (similar ao tipo Either que é um coproduto que opera sobre valores). A definição seguinte, mostra como declarar um tipo de dados para o coproduto de dois construtores de tipos que associa à direita:

data (f :+: g) e = Inl (f e) | Inr (g e)

infixr 6 :+:

Expressões que possuem o tipo Expr (Val :+: Add) são ou um valor inteiro ou a soma de duas outras expressões. Porém, esta técnica torna a tarefa de escrever uma expressão que representa a soma 33 + 77 extremamente tediosa, como pode ser observado pelo trecho de código que representa a soma anterior:

dummyExpr :: Expr (Val :+: Add)

dummyExpr = In (Inr (Add (In (In (Val 33))) (In (In (Val 77)))))

Evidentemente não é isso que desejamos. Nosso próximo passo será criar uma maneira simples para definir expressões.

1.2 – Definindo Expressões mais Facilmente

Vimos que a definição de expressões utilizando coprodutos é extremamente longa, mesmo para expressões simples. Para contornar esta situação, precisamos definir uma maneira para injetar automaticamente valores em coprodutos. Esta tarefa será realizada por funções que farão o papel de construtores de dados. No nosso exemplo, teríamos uma função para a criação de valores e uma para a adição:

val :: Int \rightarrow Expr Val

val = In . Val

infixl 6 <+>

(<+>) :: Expr Add \rightarrow Expr Add \rightarrow Expr Add

x <+> y = In (Add x y)

Com essas definições podemos tentar reescrever a soma 33 + 77:

val 33 <+> val 77

O que aparentemente está perfeito. Porém, ao tentarmos definir tal expressão obtemos um erro de tipo. Para entender o porquê, basta verificar o tipo das funções utilizadas:

  • val :: Int \rightarrow Expr Val
  • (<+>) :: Expr Add \rightarrow Expr Add \rightarrow Expr Add

Veja que a função <+> espera como argumentos duas expressões de tipo Expr Add, isto é, expressões que possuam sub-expressões formadas apenas por adições. Para solucionar este problema, [3] propõe a generalização dos tipos destas definições para:

(<+>) :: (Add :<: f ) \Rightarrow Expr f \rightarrow Expr f \rightarrow Expr f

val :: (Val :<: f ) \Rightarrow Int \rightarrow Expr f

Onde a restrição de tipo Val :<: f representa que podemos injetar um valor em um coproduto f. Para permitir que estas “injeções” (não consegui pensar numa tradução melhor para injections) sejam feitas automaticamente, definiremos uma classe de tipos e algumas instâncias que realizarão este trabalho. A definição destas é apresentada abaixo:

class (Functor sub, Functor sup) \Rightarrow (:<:) sub sup where
+++ inj :: sub a \rightarrow sup a

instance (Functor f, Functor g) \Rightarrow (:<:) f f where
+++ inj = id

instance (Functor f, Functor g) \Rightarrow (:<:) f (f :+: g) where
+++ inj = Inl

instance (Functor f, Functor g,
++++++Functor h, (:<:) f g)
++++++ \Rightarrow (:<:) f (h :+: g) where
++++++++++ inj = Inr . inj

A classe de tipos (:<:) sub sup possui somente uma função: inj :: sub a \rightarrow sup a, que injeta um valor de tipo sub a em um coproduto de tipo sup a. A primeira instância mostra que a relação entre construtores de tipos definida pela classe (:<:) é reflexiva. A segunda explica como injetar um valor de tipo f a em um valor de tipo (f :+: g) a. A última instância mostra que se podemos injetar um valor de tipo f a em um valor de tipo g a então podemos injetá-lo em um valor de tipo (h :+: g) a, independente do construtor de tipos h envolvido.

Com estas instâncias em mãos, podemos definir as seguintes funções que farão o papel de construtores de dados para constantes e adição.

inject :: (g :<: f) \Rightarrow g (Expr f) \rightarrow Expr f

inject = In . inj

val :: (Val :<: f ) \Rightarrow Int \rightarrow Expr f

val = inject . Val

(<+>) :: (Add :<: f ) \Rightarrow Expr f \rightarrowExpr f \rightarrow Expr f

x <+> y = inject (Add x y)

Como o leitor atento deve ter percebido, os tipos Add, Val e (:+:) precisam possuir instâncias da classe Functor. Essas instâncias são auto-explicativas:

instance Functor Val where
+++ fmap f (Val x) = f x

instance Functor Add where
+++ fmap f (Add e1 e2) = Add (f e1) (f e2)

instance (Functor f, Functor g) \Rightarrow Functor (f :+: g) where
+++ fmap f (Inl e1) = Inl (fmap f e1)
+++ fmap f (Inr e2) = Inr (fmap f e2)

Agora podemos escrever expressões mais facilmente:

x :: Expr (Add :+: Val)

x = val 33 <+> val 77

Note a presença da anotação de tipo para o valor x. Somente com esta anotação o compilador será capaz de identificar qual instância será executada para realizar a injeção de valores corretamente.

1.3 – Definindo Operações sobre Expressões

Até agora escrevemos uma grande quantidade de código somente para definir expressões mais facilmente usando coprodutos. Mas nada foi dito sobre como codificar operações sobre estas expressões. Antes de definir uma primeira operação, vamos definir um fold sobre uma expressão de tipo Expr f:

foldExpr :: Functor f \Rightarrow (f a \rightarrow a) \rightarrow Expr f \rightarrow a

foldExpr f = f . fmap (foldExpr f) . out

Um fold é um operador que representa o caminhamento recursivo pela estrutura de um tipo. Folds são parametrizados por uma álgebra, que determina como valores produzidos por diferentes construtores de dados são utilizados para formar o resultado final em cada passo do caminhamento recursivo por toda a estrutura da expressão[4][5]. Como uma álgebra define como é feito o processamento em cada nível de um valor, devemos implementar operações sobre nossos tipos como álgebras, isto é, todas as operações devem ter um tipo que é instância de f a \rightarrow a.

Como um primeiro exemplo de operação, considere a seguinte álgebra para avaliação de expressões:

class Functor f \Rightarrow Eval f where

+++evalAlgebra :: f Int \rightarrow Int

e as suas instâncias para os tipos Val e Add:

instance Eval Val where

+++evalAlgebra (Val x) = x

instance Eval Add where

+++evalAlgebra (Add e1 e2) = x + y

Observe que a implementação das álgebras para valores inteiros e adição é idêntica a uma implementação tradicional de um avaliador de expressões aritméticas. Porém, como nossas expressões são formadas pelo coproduto de tipos, temos que definir esta mesma álgebra para coprodutos:

instance (Eval f, Eval g) \Rightarrow Eval (f :+: g) where

+++evalAlgebra (Inl x) = evalAlgebra x

+++evalAlgebra (Inr x) = evalAlgebra x

Agora que possuímos todo o armamento necessário, podemos finalmente implementar a avaliação de expressões, usando o fold e a álgebra:

eval :: Eval f \Rightarrow Expr f \rightarrow Int

eval = foldExpr evalAlgebra

Usando a função eval podemos avaliar a soma definida anteriormente:

Main\rangle eval x

110

O leitor deve estar se perguntando: Qual a vantagem de tanta complicação para avaliar expressões aritméticas? Até o presente momento, codificamos uma grande quantidade de código para implementar um simples avaliador de expressões aritméticas que poderia ter sido implementado da seguinte maneira:

data Expr = Val Int | Add Expr Expr

eval :: Expr \rightarrow Int

eval (Val x) = x

eval(Add e1 e2) = eval e1 + eval e2

Mas nosso trabalho será recompensado pela extensibilidade de nosso código, que permitirá a inclusão de novas operações à nossa linguagem de expressões sem alterar nenhuma linha de código.

1.4 – Estendendo o Avaliador de Expressões

Suponha que desejamos que nosso avaliador de expressões também seja capaz de realizar subtração, multiplicação e divisão. Como podemos fazer isso? Primeiramente, devemos definir novos tipos de dados e suas correspondentes instâncias da classe Functor:

data Mult e = Mult e e

instance Functor Mult where

+++fmap f (Mult e1 e2) = Mult (f e1) (f e2)

data Sub e = Sub e e

instance Functor Sub where

+++fmap f (Sub e1 e2) = Sub (f e1) (f e2)

data Div e = Div e e

instance Functor Div where

+++fmap f (Div e1 e2) = Div (f e1) (f e2)

Agora basta definir, para cada nova operação, a álgebra que fará a avaliação deste tipo de expressão e uma função que será utilizada para construir valores deste tipo:

instance Eval Mult where
+++evalAlgebra(Mult e1 e2) = e1 * e2

infixl <*> 7

(<*>) :: (Mult :<: f ) \Rightarrow Expr f \rightarrow Expr f \rightarrow Expr f
e1 <*> e2 = inject (Mult e1 e2)

O código da álgebra de avaliação e da função para construir valores para subtração e divisão é tão simples e direto quanto o da multiplicação. Veja que a inclusão de uma nova operação em nossa linguagem não exigiu que alterássemos nada na implementação anterior! Nosso trabalho está começando a dar resultados…

Agora que já foi apresentado como estender a sintaxe de nossa linguagem de expressões aritméticas, veremos como introduzir uma nova operação sobre esta linguagem. Considere agora a tarefa de realizar o pretty-printting de uma expressão. A classe de tipos Render destina-se a esta tarefa:

class Render f where

+++render :: Render g \Rightarrow f (Expr f) \rightarrow String

Supondo a existência de instâncias para cada um dos tipos de expressões que já definimos, podemos implementar uma função para o pretty-printting de expressões como:

pretty :: Render f \Rightarrow Expr f \rightarrow String

pretty = render . out

A implementação das instâncias da classe Render são diretas:

instance Render Val where

+++render (Val x) = show x

instance Render Add where

+++render (Add x y) = “(” ++ pretty x ++ ” + ” ++ pretty y ++ “)”

instance Render Mult where

+++render (Mult x y) = “(” ++ pretty x ++ ” * ” ++ pretty y ++ “)”

instance (Render f, Render g ) \Rightarrow Render (f :+: g ) where

+++render (Inl x) = render x

+++render (Inr x) = render x

Com isso, podemos realizar o pretty-printting de expressões:

Main\rangle pretty x

“(33 + 77)”

Com isso, podemos observar como estender código existente, sem modificá-lo, com novas funcionalidades e construtores de dados. Data Types a la Carte, constitui um exemplo interessante de como o sistema de tipos de Haskell é expressivo e pode ser utilizado para produzir software extensível.

Referências
1 – Wadler, Philip (1999). The expression problem. http://www.daimi.au.dk/~madst/tool/papers/expression.txt

2 – Blume, Mathias; Acar, Umut A.; Chae, Wonseok (2006). Extensible programming with first class cases. Proceedings of ICFP 2006.

3 – Swierstra, Wouter (2008). Data Types a la carte. Journal of Functional Programming – 18.

4 – Hutton, Graham (1993). A tutorial on the universality and expressiveness of fold. Journal of Functional Programming.

5 – Lammel, Ralf; Visser, Joost; Kort Jan. Dealing with Large Bananas.