Type-level programming com traits e associated types

1. Fundamentos do Type-level Programming em Rust

Programação em nível de tipo (type-level programming) é uma técnica onde computações são realizadas durante a compilação, usando o sistema de tipos como motor de execução. Diferente da programação em nível de valor, que opera sobre dados em tempo de execução, a programação em nível de tipo manipula tipos como se fossem valores, permitindo que invariantes sejam verificados estaticamente.

Em Rust, traits funcionam como interfaces de tipo e, quando combinados com associated types, tornam-se funções em nível de tipo. Um trait pode ser visto como uma função que mapeia tipos de entrada para tipos de saída:

trait TypeFunction {
    type Output;
}

// "Função" que adiciona um wrapper Option
struct WrapOption;
impl<T> TypeFunction for WrapOption {
    type Output = Option<T>;
}

Associated types permitem definir tipos dependentes dentro de traits, criando relações entre tipos que o compilador pode verificar.

2. Type-level Computations com Traits e Tipos Associados

Vamos implementar operações aritméticas em nível de tipo usando unit structs como representações de valores:

struct Zero;
struct Succ<T>(std::marker::PhantomData<T>);

// Soma em nível de tipo
trait Add<Rhs> {
    type Result;
}

impl<Rhs> Add<Rhs> for Zero {
    type Result = Rhs;
}

impl<T, Rhs> Add<Rhs> for Succ<T>
where
    T: Add<Rhs>,
{
    type Result = Succ<<T as Add<Rhs>>::Result>;
}

O encadeamento de traits permite computações complexas. Cada implementação recursiva reduz o problema até o caso base.

3. Type-level Booleans e Condicionais

Definimos tipos booleanos como marcadores:

struct True;
struct False;

trait Bool {}
impl Bool for True {}
impl Bool for False {}

// Condicional em nível de tipo
trait If<Cond, Then, Else> {
    type Output;
}

impl<Then, Else> If<True, Then, Else> for () {
    type Output = Then;
}

impl<Then, Else> If<False, Then, Else> for () {
    type Output = Else;
}

Isso permite selecionar implementações baseadas em tipos booleanos, criando branching em nível de tipo sem execução em tempo real.

4. Type-level Lists e Estruturas de Dados

Listas heterogêneas (HList) podem ser representadas com tipos aninhados:

struct Nil;
struct Cons<H, T>(std::marker::PhantomData<(H, T)>);

// Push: adiciona elemento no início
trait Push<New> {
    type Result;
}

impl<New> Push<New> for Nil {
    type Result = Cons<New, Nil>;
}

impl<H, T, New> Push<New> for Cons<H, T>
where
    T: Push<New>,
{
    type Result = Cons<H, <T as Push<New>>::Result>;
}

// Get: acessa elemento por índice (simplificado)
trait Get<Index> {
    type Output;
}

impl<H, T> Get<Zero> for Cons<H, T> {
    type Output = H;
}

impl<H, T, Index> Get<Succ<Index>> for Cons<H, T>
where
    T: Get<Index>,
{
    type Output = <T as Get<Index>>::Output;
}

Traits recursivos permitem iteração e transformação em nível de tipo, similar a funções de ordem superior em Haskell.

5. Type-level Integers e Aritmética

Usando codificação de Peano, implementamos números naturais como tipos:

struct Zero;
struct Succ<T>(std::marker::PhantomData<T>);

// Multiplicação
trait Mul<Rhs> {
    type Result;
}

impl<Rhs> Mul<Rhs> for Zero {
    type Result = Zero;
}

impl<T, Rhs> Mul<Rhs> for Succ<T>
where
    T: Mul<Rhs>,
    Rhs: Add<<T as Mul<Rhs>>::Result>,
{
    type Result = <Rhs as Add<<T as Mul<Rhs>>::Result>>::Result;
}

// Comparação
trait IsLessThan<Rhs> {
    type Result;
}

impl<Rhs> IsLessThan<Rhs> for Zero {
    type Result = True; // 0 < qualquer coisa positiva
}

impl<T> IsLessThan<Zero> for Succ<T> {
    type Result = False;
}

impl<T, Rhs> IsLessThan<Succ<Rhs>> for Succ<T>
where
    T: IsLessThan<Rhs>,
{
    type Result = <T as IsLessThan<Rhs>>::Result;
}

A conversão para constantes em tempo de compilação pode ser feita com const genéricos (Rust 1.51+).

6. Type-level State Machines e Tipos Fantasma

PhantomData e tipos marcadores codificam estados, garantindo transições corretas em tempo de compilação:

use std::marker::PhantomData;

// Estados de uma conexão HTTP
struct Disconnected;
struct Connected;
struct Authenticated;

// Trait de transição
trait Transition<From, To> {
    fn transition(self) -> Connection<To>;
}

struct Connection<State> {
    state: PhantomData<State>,
}

impl Connection<Disconnected> {
    fn new() -> Self {
        Connection { state: PhantomData }
    }
}

impl Transition<Disconnected, Connected> for Connection<Disconnected> {
    fn transition(self) -> Connection<Connected> {
        println!("Conectando...");
        Connection { state: PhantomData }
    }
}

impl Transition<Connected, Authenticated> for Connection<Connected> {
    fn transition(self) -> Connection<Authenticated> {
        println!("Autenticando...");
        Connection { state: PhantomData }
    }
}

// Uso: o compilador impede transições inválidas
fn main() {
    let conn = Connection::<Disconnected>::new();
    let conn = conn.transition(); // Disconnected -> Connected
    let conn = conn.transition(); // Connected -> Authenticated
    // conn.transition(); // Erro! Não há transição de Authenticated para outro estado
}

Isso valida protocolos como HTTP ou conexões de banco estaticamente.

7. Type-level Constraints e Prova de Teoremas

Podemos codificar provas de igualdade de tipos:

use std::marker::PhantomData;

// Prova de que A == B
struct TypeEq<A, B>(PhantomData<(A, B)>);

// Reflexividade
impl<T> TypeEq<T, T> {
    fn new() -> Self {
        TypeEq(PhantomData)
    }
}

// Garantindo que um vetor não está vazio
struct NonEmptyVec<T>(Vec<T>);

impl<T> NonEmptyVec<T> {
    fn new(first: T) -> Self {
        NonEmptyVec(vec![first])
    }

    fn push(&mut self, item: T) {
        self.0.push(item);
    }
}

// Função segura que só aceita vetores não vazios
fn first<T>(vec: NonEmptyVec<T>) -> &T {
    &vec.0[0] // Seguro: garantido por tipo
}

PhantomData carrega provas em estruturas sem custo em tempo de execução.

8. Limitações e Boas Práticas

Type-level programming em Rust tem limitações significativas:

  • Complexidade de compilação: Recursão profunda em tipos pode estourar limites do compilador
  • Mensagens de erro obscuras: Erros em tipos complexos são difíceis de interpretar
  • Curva de aprendizado íngreme: Exige conhecimento avançado do sistema de tipos

Quando evitar:
- Soluções simples em tempo de execução são suficientes
- O time não tem experiência com programação em nível de tipo
- O código precisa ser mantido por desenvolvedores menos experientes

Alternativas modernas:
- Const genéricos (Rust 1.51+): Para constantes numéricas em tipos
- GATs (Generic Associated Types, Rust 1.65+): Para abstrações mais flexíveis
- Macros: macro_rules! ou macros proc para geração de código
- Traits com métodos associados: Para polimorfismo sem type-level programming

// Alternativa com const genéricos
struct Array<T, const N: usize>([T; N]);

impl<T, const N: usize> Array<T, N> {
    fn sum(&self) -> T
    where
        T: std::ops::Add<Output = T> + Copy + Default,
    {
        self.0.iter().fold(T::default(), |a, b| a + *b)
    }
}

Type-level programming é uma ferramenta poderosa para garantir invariantes em tempo de compilação, mas deve ser usada com moderação. Para a maioria dos casos, const genéricos e GATs oferecem soluções mais práticas e legíveis.

Referências