Rodrigo Kumpera Weblog

Outro dia uma discussão me levou a pensar se era possível implementar Haskell em cima de uma VM tradicional, tal qual JVM ou CLR, de forma eficiente. Em termos dos mecanismos que a VM precisa suportar de forma eficiente os principais são tail call, thunking, type classes e algebraic types. Nesse artigo vou apenas discutir um deles, type classes.

Uma type class para os acostumados com OO pode ser vista como uma interface cuja implementações são externas aos tipos que estão atrelados. Um exemplo bem simples é Eq, que permite compar objetos do mesmo tipo:

class Eq a where
    (==), (/=) :: a -> a -> Bool
    x /= y = not (x == y)
    x == y = not (x /= y)

Para nos não iniciado em Haskell, linha um define a classe Eq e diz que ela possui um parâmetro polimófico; linha 2 diz que Eq tem 2 funções, “==” e “/=” cuja assinatura são dois valores do tipo ‘a’ e retorna um booleano; por fim, linhas 3 e 4 são implementações padrão das funções. Seria o equivalente, em pseudo-C#, ao seguinte:

interface Eq<T> {
   bool operator== (T a, T b) { return !(a != b); }
   bool operator!= (T a, T b) { return !(a == b); }
}

Uma das vantagens de type classes no Haskell é que elas podem fornecer implementações padrão para alguns de seus métodos. Bom, agora que temos Eq definida, para dizer que Listas a implementa usamos algo como:

instance Eq a => Eq [a] where
    [] == [] = True
    (x:xs) == (y:ys) = x==y && xs==ys
    _ == _ = False

Aqui vemos uma das melhores características do Haskell é explorada, que é pattern matching – e isso também é assunto para outro artigo. Como pode se notar, uma implementação de uma dada type class não está embutida na definição do tipo em questão, ou seja, não podemos interfaces como a CLR ou a JVM suportam.

A idéia é representar type classes de forma semelhante a como o ghc faz, usando dictionary passing[1], que é bem simples de entender e implementar. Para cada type class que uma função recebe nos seus parâmetros, passamos junto um objeto que representa as operações em questão. Em C# teríamos:

interface Eq<T> {
    bool op_eq (T a, T b);
    bool op_neq (T a, T b);
}
 
class Eq_Int : Eq<int> {
    public bool op_eq (int a, int b) { return a == b; }
    public bool op_eq (int a, int b) { return a != b; }
}
 
int Fun<T> (Eq<T> dict, T a, T b) {
    if (dict.op_eq (a, b))
        return 1;
    return 0;
}

Existe alguns problemas aqui, primeiro que estamos passando um parâmetro extra e segundo que não é possível eliminar a verificar por null pointer caso op_eq seja inlined. A solução é razoavelmente simples no caso do C#:

struct Eq_Int : Eq<int> {
    public bool op_eq (int a, int b) { return a == b; }
    public bool op_neq (int a, int b) { return a != b; }
}
 
int Fun<T, TD> (T a, T b) where TD: Eq<T> {
    if (default (TD).op_eq (a, b))
        return 1;
    return 0;
}

A grande mudança aqui é tornar a instância da typeclass um valuetype e construir um valor default para satisfazer o compilador. É uma pena que não podemos simplesmente chamar um método estático e TD, o que é uma limitação boba da CLR. Essa solução não é possível na JVM devido a inexistência de valuetypes e generics.

E quanto a performance dessa solução? Bom, no caso do mono, o JIT’er reconhece as chamadas como não virtuais e é capaz de fazer inline de forma bem agressiva – exatamente como desejado. Eu pensei em fazer um comparativo dessa solução com o equivalente em Java, mostrando como a CLR permite codificar tipos muito mais ricos e interessantes que a JVM – e como isso se traduz em performance. Mas realmente não estou afim de criar motivo para um flamewar por parte dos javeiros de plantão.

[1]Esse é o paper original que descreve type classes e a técnica utilizada: http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps.gz