Breaking Free from Coherence: Context-Generic Programming in Rust

Introduction

Rust's trait system is one of its most powerful features, enabling highly polymorphic and reusable code through shared behaviors. However, the coherence rules and orphan restrictions have long been a source of frustration for Rust developers, limiting our ability to write truly generic trait implementations. This article explores Context-Generic Programming (CGP), a new modular programming paradigm that demonstrates how to work around these limitations while maintaining the benefits of Rust's trait system.

Understanding Rust Traits and Coherence

Before diving into CGP, it's essential to understand how Rust traits work and why coherence rules exist. Rust traits allow us to implement behaviors in an abstract way and use trait bounds with generics to work with any type that provides specific behavior. This creates a powerful interface that decouples code usage from implementation.

The Power of Generic Trait Implementations

One of Rust's key strengths is the ability to implement traits generically. For example, we can write a single implementation of the Display trait for a Person struct that works for any Name type, as long as Name itself implements Display. This generic implementation allows for highly reusable code without sacrificing type safety.

Dependency Injection Through Traits

Rust's trait system provides free dependency injection. When we implement Display for Person<Name>, we can require that Name implements Display through a where clause, without explicitly declaring that dependency elsewhere. This transitive dependency lookup is what makes Rust traits more powerful than interfaces in other languages.

The Coherence Problem

To ensure that trait lookups always resolve to a single, unique instance, Rust enforces two key rules:

1. No overlapping implementations: There cannot be two trait implementations that overlap when instantiated with some concrete type.
2. No orphan instances: A trait implementation can only be defined in a crate that owns either the type or the trait.

These rules, while necessary for soundness, create significant limitations for developers.

The Hash Table Problem

A classic example of coherence limitations is the hash table problem. Suppose we want to make it easy for any type to implement the Hash trait by creating a blanket implementation for any type that implements Display. We could format the value into a string using Display and then compute the hash based on that string. However, if we later try to implement Hash for a type like u32 that already implements Display, we would get a compiler error due to conflicting implementations.

Orphan Rules in Practice

The orphan rules prevent us from implementing traits for types we don't own. For example, if the serde crate defines the Serialize trait and another crate defines a Person struct, we cannot implement Serialize for Person in a third-party crate. This limitation is particularly frustrating when we want to add serialization support for types from external libraries.

Existing Approaches to Work Around Coherence

Several approaches have been developed to work around coherence restrictions:

Specialization

Rust's specialization feature, available in nightly builds, allows some form of overlapping implementations using the default keyword. However, specialization has remained unstable due to soundness concerns and doesn't fully solve the coherence problem. It also doesn't address orphan rules.

Explicit Parameters

The Serde remote pattern demonstrates how to work around orphan rules by defining proxy structs and using proc macros. While effective, this approach requires complex macros and doesn't generalize well to other use cases.

Introducing Provider Traits

A key insight in working around coherence is to move the Self type to an explicit generic parameter, creating what we call provider traits. Instead of implementing Serialize for a type directly, we implement a SerializeImpl provider trait where the target type becomes an explicit generic parameter.

Overlapping and Orphan Implementations

With provider traits, we can now write overlapping and orphan implementations without violating coherence rules. Since Rust's coherence rules only apply to the Self type of a trait implementation, we can define unique dummy structs as the Self type and write generic implementations that would otherwise be considered overlapping.

Higher-Order Providers

To handle nested dependencies, we can use higher-order providers where provider implementations accept other provider implementations as type parameters. This allows for composition of provider implementations while maintaining the ability to write generic code.

Context-Generic Programming (CGP)

Context-Generic Programming builds on provider traits to create a complete solution for writing context-generic trait implementations. The key ideas behind CGP are:

1. Provider traits for incoherent implementations: Enable overlapping implementations that are identified by unique provider types.
2. Explicit wiring step: Connect provider implementations to specific contexts through a wiring mechanism.

The cgp-serde Crate

To demonstrate CGP in practice, the cgp-serde crate provides a context-generic version of the Serialize trait called CanSerializeValue. This trait has the target value type specified as a generic parameter and accepts an additional context reference.

Component-Based Architecture

CGP uses a component-based architecture where:

• Consumer traits (like CanSerializeValue) are annotated with #[cgp_component]
• Provider traits are automatically generated with the Self type moved to an explicit generic parameter
• The #[cgp_impl] macro simplifies writing provider implementations
• Context types are defined and wired up using the delegate_components! macro

Type-Level Lookup Tables

CGP implements type-level lookup tables to resolve provider implementations at compile time. When using a consumer trait like CanSerializeValue on a context, the system performs a two-level lookup:

1. Find the component provider using the component name as a key
2. Find the specific implementation using the value type as a key

Practical Demonstration: Encrypted Messaging Library

A practical example of CGP's benefits is an encrypted messaging library. Without CGP, different applications using the library might need different serialization strategies for the same data types. For instance:

• Application A might need bytes serialized as hexadecimal strings and DateTime in RFC3339 format
• Application B might need base64 for bytes and Unix timestamps for DateTime

With cgp-serde, each application can define its own context type and wire up the specific serialization providers it needs, without modifying the core library code.

Benefits and New Possibilities

CGP enables several powerful patterns:

Meta-Framework Development

CGP can be used as a meta-framework to build other frameworks and domain-specific languages. By separating the definition of behaviors from their implementations, CGP enables highly modular and extensible systems.

Extensible Records and Variants

CGP extends Rust to support extensible records and variants, which can be used to solve the expression problem. This allows for more flexible data type definitions that can be extended in multiple dimensions.

Context-Aware Serialization

Beyond serialization, CGP enables context-aware implementations for various traits, allowing different contexts to provide different implementations of the same behavior.

Getting Started with CGP

To start using CGP:

1. Add the cgp crate as a dependency
2. Import the prelude in your code
3. Add the #[cgp_component] macro to traits you want to make context-generic
4. Use the #[cgp_impl] macro to write provider implementations
5. Define context types and wire up components using delegate_components!

Challenges and Considerations

While CGP provides powerful capabilities, it comes with some challenges:

Verbose Error Messages

Due to how the trait system is used, unsatisfied dependencies can result in very verbose and difficult-to-understand error messages. Large language models can help debug these issues in the short term.

Steep Learning Curve

Programming in CGP can feel like using a new language, with its own patterns and idioms. The learning curve is significant, especially for developers accustomed to traditional Rust trait usage.

Early Stage Development

CGP is still in early development, so community and ecosystem support may be limited. However, this also means there are many opportunities to contribute and shape the future of the paradigm.

Related Work and Inspiration

Context-Generic Programming builds on concepts from both functional and object-oriented programming. The Haskell presentation "Typeclasses vs the World" by Edward Kmett was a core inspiration for CGP, highlighting the limitations of traditional type classes and exploring alternative approaches.

Conclusion

Context-Generic Programming represents a significant advancement in how we can write generic code in Rust. By providing a way around coherence restrictions while maintaining the benefits of the trait system, CGP enables powerful new design patterns and use cases that were previously difficult or impossible to achieve.

The release of cgp-serde demonstrates that CGP can be used to create practical, backward-compatible libraries that provide enhanced capabilities. As the Rust ecosystem continues to evolve, paradigms like CGP will likely play an increasingly important role in solving complex software design challenges.

For developers interested in pushing the boundaries of what's possible with Rust traits, CGP offers an exciting new frontier to explore. While it requires a significant investment in learning and understanding, the capabilities it unlocks make it a valuable tool for building highly modular, extensible, and context-aware systems.