Os limites do type system do Rust

Recentemente, eu me apaixonei pelo Rust e tudo o que ele oferece: concorrência sem medo, abstrações de custo zero, etc. Mas algo muito poderoso também é o seu sistema de tipos. Rust implementa vários mecanismos no seu sistema de tipos como generics, traits, associated types, etc. Mas quando comecei a estudar Rust e o seu sistema de tipos, eu vivia me perguntando “o quão poderoso ou completo o sistema detipos do Rust realmente é?”, o que é uma boa pergunta, principalmente se você está acostumado com o sistema de tipos do Haskell, o que é o meu caso. Então, o objetivo desse texto é descobrir o quão poderoso o sistema de tipos do Rust é realmente por comparações com o sistema de tipos do Haskell. O foco deste tutorial será muito mais em funcionalidades/conceitos avançados, por motivos óbvios. Falaremos principalmente de GADTs e type families.

GADTs

Já sabemos que ambos Haskell e Rust possuem ADTs ou algebraic data types, que permite ao programador criar tipos utilizando as operações algébricas de soma e produto. Os ADTs são muito poderosos, mas possuem seus limites em relação à expressividade, granularidade e polimorfismo. Generalized algebraic data types, ou GADTs, são um recurso mais avançado que adiciona a capacidade de criar construtores de valores seguindo a sintaxe de assinaturas das funções. Um exemplo clássico é o tipo Maybe, em ADTs, poderíamos defini-lo deste modo:

data Maybe = Nothing | Just a

mas utilizando GADTs, podemos definir nosso tipo Maybe como:

{-# LANGUAGE GADTs #-}
data Maybe a where
  Nothing :: Maybe a
  Just  :: a -> Maybe a

Obs: precisamos utilizar uma extensão do compilador para usar GADTs.

De primeira mão, parece algo simples e até sem necessidade, mas veremos outro exemplo onde a vantagem dos GADTs fica aparente. Outro exemplo interessante são as expressões matemáticas e booleanas. Imagine que queremos definir um tipo chamado de Expr que define as expressões que podemos tratar:

data Expr a = IConst Int
        | BConst Bool
        | Add (Expr a) (Expr a)
        | Mul (Expr a) (Expr a)
        | And (Expr a) (Expr a)
        | Or  (Expr a) (Expr a)

Se você conhece um pouco mais de Haskell, perceberá que temos diversos problemas em relação à type safety neste exemplo. O parâmetro a não afeta em nada nossa definição de tipos, então podemos muito bem passar valores para And que não são booleanos, ou valores para Add que não são inteiros. Para elevarmos nossa segurança de tipos, podemos usar GADTs deste modo:

{-# LANGUAGE GADTs #-}
data Expr a where
  I   :: Int  -> Expr Int
  B   :: Bool -> Expr Bool
  Add :: Expr Int -> Expr Int -> Expr Int
  Mul :: Expr Int -> Expr Int -> Expr Int
  And :: Expr Bool -> Expr Bool -> Expr Bool
  Or  :: Expr Bool -> Expr Bool -> Expr Bool

Veja que com a sintaxe de definição de assinatura de funções que o GADTs proporciona, temos uma mais flexibilidade para definir nossas expressões de modo que conseguimos garantir maior type safety, já que agora podemos ver que Add apenas aceita Expr Int e and apenas Expr Bool.

Agora vamos para a parte interessante. Essa funcionalidade existe no Rust? Não, Rust não tem esta funcionalidade. Mas existem outros mecanismos que podem atingir o mesmo objetivo. Usaremos outros exemplos para demonstrar se Rust consegue atingir o mesmo nível de type safety dos GADTs do Haskell.

Para atingir nosso objetivo, utilizaremos três funcionalidades do Rust: traits, associated types e enums. Traits são praticamente idênticas às typeclasses no Haskell; Associated types é um mecanismo similar ao associated data types no Haskell, onde podemos associar a criação de um tipo à instanciação de um trait/typeclass; Enums são os tipos produtos do rust.

A seguir, você pode ver o código da implementação do nosso exemplo de Expr em Rust:

trait Expr {
    type Output;
    fn eval(&self) -> Self::Output;
}

enum ExprEnum<T> {
    LitInt(usize),
    LitBool(bool),
    Add(Box<dyn Expr<Output = usize>>, Box<dyn Expr<Output = usize>>),
    If(
        Box<dyn Expr<Output = bool>>,
        Box<dyn Expr<Output = T>>,
        Box<dyn Expr<Output = T>>,
    ),
}

impl Expr for ExprEnum<usize> {
    type Output = usize;
    fn eval(&self) -> Self::Output {
        match self {
            ExprEnum::LitInt(n) => *n,
            ExprEnum::LitBool(_) => panic!("Expected integer expression"),
            ExprEnum::Add(e1, e2) => e1.eval() + e2.eval(),
            ExprEnum::If(cond, true_branch, false_branch) => {
                if cond.eval() {
                    true_branch.eval()
                } else {
                    false_branch.eval()
                }
            }
        }
    }
}

impl Expr for ExprEnum<bool> {
    type Output = bool;
    fn eval(&self) -> Self::Output {
        match self {
            ExprEnum::LitInt(_) => panic!("Expected boolean expression"),
            ExprEnum::LitBool(b) => *b,
            ExprEnum::Add(_, _) => panic!("Expected boolean expression"),
            ExprEnum::If(_, _, _) => panic!("Expected boolean expression"),
        }
    }
}

Veja que criamos uma trait que tem um tipo associado chamado output e uma função chamada eval. Logo em seguida, criamos um enum que é bem similar ao nosso data Expr a, onde chamo o tipo paramétrico a como T, por ser a convenção do Rust. Essa implementação é interessante, mas não chega ao mesmo nível dos GADTs no Rust, pois, por mais que o sistema de tipos do Rust seja excelente, ele não é tão poderoso quanto do Haskell. Temos alguns problemas:

A keyword dyn: Na tentativa de remover funcionamento implícito no Rust, foi adicionado a keyword dyn. Essa keyword é utilizada para indicar que um certo trait utiliza dynamic dispatch na chamada dos métodos associados àquela trait. No dynamic dispatch, o método a ser chamado será determinado dinamicamente em tempo de execução ao invés de estaticamente no tempo de compilação. Isso é útil quando você tem uma mesma trait sendo implementada para diversos tipos concretos, como é o nosso caso, permitindo um comportamento polimórfico e uniforme. Chamamos isso também de trait object. Utilizo também o Box por forçar que um valor seja alocado no Heap, já que não sabemos o tamanho do nosso trait object em tempo de compilação.
Garantias ao nível de compilação: Como estamos simulando o funcionamento dos GADTs, não possuímos o mesmo nível de garantia em tempo de compilação. Em Haskell, GADTs são resolvidos ao nível de compilação, por exemplo, para criar uma função de eval basta fazer isso:

evalExpr :: Expr a -> a
evalExpr (I x)      = x
evalExpr (B b)      = b
evalExpr (Add l r)  = evalExpr l + evalExpr r
evalExpr (Mul l r)  = evalExpr l * evalExpr r
evalExpr (And l r)  = evalExpr l && evalExpr r
evalExpr (Or l r)   = evalExpr l || evalExpr r

E se eu tentar utilizar o eval incorretamente:

test = evalExpr (And (I 1) (B False))

Recebemos imediatamente um erro apontando a incompatibilidade de tipos ao nível de compilação:

1. • Couldn't match type ‘Int’ with ‘Bool’
    Expected: Expr Bool
    Actual: Expr Int
   • In the first argument of ‘And’, namely ‘(I 1)’
    In the first argument of ‘evalExpr’, namely ‘(And (I 1) (B False))’
    In the expression: evalExpr (And (I 1) (B False)) [-Wdeferred-type-errors]

mas se tentarmos fazer isso no Rust, por exemplo tentando somar um inteiro com um bool:

fn main() {
    let invalid_expr: ExprEnum<usize> = ExprEnum::Add(
        Box::new(ExprEnum::LitInt(1) as ExprEnum<usize>),
        Box::new(ExprEnum::LitBool(true) as ExprEnum<usize>),
    );

    println!("{}", invalid_expr.eval());
}

Não recebemos nenhum erro ao nível de compilação, mas se rodarmos essa função, teremos um panic em tempo de execução dizendo que temos mismatch de tipos.

Inferência de tipos: Rust não possui uma inferência de tipos tão poderosa quanto o Haskell. Veja que no exemplo anterior de rust, eu precisei explicitamente dizer quem era T em todo o momento e veja que mesmo eu tipando um LitBool como ExprEnum<usize>, o compilador também não consegue inferir que isso está errado. Podemos ver isso no exemplo a seguir, que nunca irá compilar porque o compilador não consegue inferir praticamente nada:

fn main() {
    let expr = ExprEnum::Add(Box::new(ExprEnum::LitInt(1)), Box::new(ExprEnum::LitInt(1)));
    println!("{}", expr.eval());
}

Todas essas desvantagens causam um efeito cascata que reduz a eficácia de tudo isso em diversos quesitos como pattern matching inferior ao Haskell, overhead ao nível de execução, falta de expressividade, etc.

No final das contas, o Rust possui mecanismos que emulam GADTs, mas infelizmente não consegue atingir o mesmo nível do GADTs em Haskell.

Type Families

Em Haskell, type families são um mecanismo poderoso para definir famílias de tipos que exibem comportamento paramétrico, permitindo a criação de código flexível e reutilizável. Em geral, type families servem como um meio de associar tipos a valores ou outros tipos de uma forma que permite computações e relações ao nível do tipo.

Ao contrário das typeclasses, que definem o comportamento de um conjunto de tipos por uma interface comum, as type families focam nas relações entre os próprios tipos. Assim, podemos definir mapeamentos de um tipo para outro com base em determinadas condições ou padrões, permitindo essencialmente a criação de funções personalizadas ao nível do tipo. As type families são particularmente úteis em cenários onde o polimorfismo tradicional é insuficiente, como quando se lida com estruturas de dados complexas ou quando é necessário criar mecanismos complexos ao nível de tipos. Uma boa analogia é que typeclasses nos oferece polimorfismo ad hoc enquanto type families nos oferece tipos ad hoc.

Utilizaremos um exemplo simples onde exploraremos uma função para escolher a técnica correta para cada instrumento musical:

{-# LANGUAGE TypeFamilies #-}

class Instrument instrument where
  data Technique instrument :: *
  pickTechnique :: instrument -> Technique instrument

data StringInstrument = Violin | Guitar | Cello deriving (Show)

instance Instrument StringInstrument where
  data Technique StringInstrument = Pluck | Bow deriving (Show)
  pickTechnique Violin = Bow
  pickTechnique Guitar = Pluck
  pickTechnique Cello = Bow

data WindInstrument = Flute | Saxophone | Trumpet deriving (Show)

instance Instrument WindInstrument where
  data Technique WindInstrument = Blow | Finger | Buzz deriving (Show)
  pickTechnique Flute = Blow
  pickTechnique Saxophone = Finger
  pickTechnique Trumpet = Buzz

main :: IO ()
main = do
  putStrLn "String instrument techniques:"
  putStrLn $ "Violin: " ++ show (pickTechnique Violin)
  putStrLn $ "Guitar: " ++ show (pickTechnique Guitar)
  putStrLn $ "Cello: " ++ show (pickTechnique Cello)

  putStrLn "\nWind instrument techniques:"
  putStrLn $ "Flute: " ++ show (pickTechnique Flute)
  putStrLn $ "Saxophone: " ++ show (pickTechnique Saxophone)
  putStrLn $ "Trumpet: " ++ show (pickTechnique Trumpet)

Definimos uma classe de tipo Instrument para os instrumentos musicais, que inclui uma família de tipo Technique que representa as técnicas de execução associadas a cada instrumento. Criamos instâncias da classe Instrumento para duas categorias de instrumentos: instrumentos de corda (StringInstrument) e instrumentos de sopro (WindInstrument).

Cada tipo de instrumento tem o seu próprio conjunto de técnicas de execução definidas na família de tipos Technique associada e com essa informação, implementamos a função pickTechnique para cada instrumento, que seleciona uma técnica de tocar com base no instrumento específico utilizando os type families para escolher o tipo correto que deve ser retornado por cada versão de pickTechnique.

trait Instrument {
    type Technique;
    fn pick_technique(&self) -> Self::Technique;
}

#[derive(Debug)]
enum StringInstrument {
    Violin,
    Guitar,
    Cello,
}

impl Instrument for StringInstrument {
    type Technique = StringTechnique;

    fn pick_technique(&self) -> Self::Technique {
        match self {
            StringInstrument::Violin => StringTechnique::Bow,
            StringInstrument::Guitar => StringTechnique::Pluck,
            StringInstrument::Cello => StringTechnique::Bow,
        }
    }
}

#[derive(Debug)]
enum WindInstrument {
    Flute,
    Saxophone,
    Trumpet,
}

impl Instrument for WindInstrument {
    type Technique = WindTechnique;

    fn pick_technique(&self) -> Self::Technique {
        match self {
            WindInstrument::Flute => WindTechnique::Blow,
            WindInstrument::Saxophone => WindTechnique::Finger,
            WindInstrument::Trumpet => WindTechnique::Buzz,
        }
    }
}

#[derive(Debug)]
enum StringTechnique {
    Pluck,
    Bow,
}

#[derive(Debug)]
enum WindTechnique {
    Blow,
    Finger,
    Buzz,
}

fn main() {
    println!("String instrument techniques:");
    let violin = StringInstrument::Violin;
    println!("Violin: {:?}", violin.pick_technique());
    let guitar = StringInstrument::Guitar;
    println!("Guitar: {:?}", guitar.pick_technique());
    let cello = StringInstrument::Cello;
    println!("Cello: {:?}", cello.pick_technique());

    println!("\nWind instrument techniques:");
    let flute = WindInstrument::Flute;
    println!("Flute: {:?}", flute.pick_technique());
    let saxophone = WindInstrument::Saxophone;
    println!("Saxophone: {:?}", saxophone.pick_technique());
    let trumpet = WindInstrument::Trumpet;
    println!("Trumpet: {:?}", trumpet.pick_technique());
}

Além de herdar todos os problemas que falamos na seção de GADTs, tentar implementar type families desse modo traz mais problemas. Ao contrário das type families de Haskell, que permitem operações ao nível do tipo e pattern matching, os associated types de Rust são estáticos e não podem efetuar as mesmas operações ao nível do tipo. Isto significa que Rust não pode expressar relações complexas entre tipos da mesma forma que Haskell pode. Tudo isso implica em uma implementação extremamente verbosa, menos expressiva e como generalidade reduzida.

Conclusão

Rust é uma linguagem incrível, com funcionalidades maravilhosas. Tem pessoas que não gostam, mas é inegável o impacto que o Rust causou no mundo da programação, principalmente com o seu foco em memory safety e concorrência. Mas obviamente possui suas desvantagens. O seu sistema de tipos é poderoso, mas carece de funcionalidades mais avançadas como type families e GADTs. Isso não torna a linguagem ruim, já que essas funcionalidades nunca foram um objetivo do Rust. Para um cara que curte Haskell, faz falta? Sim, mas para um programador Rust isso não é um fim do mundo.