Chalk

Chalk is a symbolic algebra library. It provides a number of traits that define requirements for algebraic structures, as well as mechanisms for defining your own structures.

Chalk also has a many optional features that provide implementations of well-known algebraic objects conforming to these traits, such as polynomials, cyclic groups, and permutations groups.

Design

The main idea

Chalk's approach is a little different from what one might expect, and deserves some explanation. One might expect a trait like MulGroup for which you are required to implement the binary operator, an identity element, and an inversion operation. This approach however has a fatal flaw, which becomes evident when other traits are added.

We also want to support traits like MulMonoid, which has the binary operator and identity element (but no inversion). Moreover, we would like every group to automatically be a monoid. This could be done by adding a blanket implementation for [MulMonoid] constrained on the type implementing [MulGroup], like so:

# use chalk::MulMonoid;
# use chalk::MulGroup;
impl <G: MulGroup> MulMonoid for G {}

Unfortunately, this blanket implementation precludes any other implementation of [MulMonoid] whatsoever, making it a non-starter.

This particular problem can be solved by not letting users implement [MulGroup] at all. Rather, they are only allowed to implement [MulMonoid] and [Invertible], and then having a blanket implementation (the only implementation) of [MulGroup] for any type that implements both [MulMonoid] and [Invertible].

Of course, the same relationship betweeen [MulMonoid] and [MulSemigroup] will cause problems. Taking this approach to its logical conclusion, each trait gets a blanket implementation whenever each of its properties are satisfied. Users implement those properties directly.

Chalk provides mechanisms to simplify both the definition of these basic properties, as well as the "trait aliases" that provide nice names for aggregations of properties.

Safety

Chalk provides several marker traits such as [AddCommutative] which indicates that the algorithms and data structures may presume that + is commutative. It is not uncommon for such marker traits to be marked as unsafe, as the requirement that they advertise cannot be validated, and the behavior is assumed. Chalk, does not mark these traits as unsafe, for two primary reasons.

First, practically, most implementations of these traits are inside attribute macros, meaning users do not end up typing or seeing the unsafe keyword.

Secondly, these marker traits are not unsafe in any language-level sense. That is, while authors may assume that an [AddCommutative] type has commutative addition, it does not allow them to perform any behaviors that Rust deems as unsafe without again explicitly using that keyword. This does not make it a good idea to falsely advertise types with the wrong markers. It just means that doing so does not allow any language-level invariants to be broken invisibly.