Archive for abril \25\UTC 2010

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.