Crate chalk 

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:

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.

Traits

AbelianAddGroup

An “alias trait” representing abelian groups with the operator +. Equivalent to AddGroup+AddCommutative

AbelianMulGroup

An “alias trait” representing abelian groups with the operator *. Equivalent to AddGroup+AddCommutative

Absorption

Marker trait indicating that the type’s implementation of join (|) and meet (&) operations satisify the absorption law.

Add

AddAssociative

Marker trait indicating that the type’s implementation of addition is associative.

AddCommutative

Marker trait indicating that the type’s implementation of addition is commutative.

AddGroup

An “alias trait” representing groups with the operator +. Equivalent to AddMonoid and requiring implementations of std::ops::Neg and std::ops::Sub

AddIdentity

Represents types that have an additive identity. That is, the element e for which e + x == x + e == x, for any x of the type.

AddMonoid

An “alias trait” representing monoids with the operator +. Equivalent to AddSemigroup+AddIdentity

AddMulDistributive

Marker trait indicating that the type’s implementation of multiplication distributes over addition

AddSemigroup

An “alias trait” representing semigroups with the operator +. Equivalent to AddAssociative

Binary

CommutativeRing

An “alias trait” representing commutative rings. Equivalent to Ring+MulCommutative

Div

DivisionRing

An “alias trait” representing division rings. Equivalent to Ring+Div

Domain

Marker trait indicating that the ring’s multiplication can only produce zero-elements if one of the operands was zero.

Field

An “alias trait” representing fieds Equivalent to CommutativeRing+Div.

IntegralDomain

An “alias trait” representing integral domains. Equivalent to CommutativeRing+Domain

Invertible

Represents types that have a multiplicative inverse for all elements other than the additive identity, if one exists for the type.

Join

JoinAssociative

Marker trait indicating that the type’s implementation of join (|) is associative.

JoinCommutative

Marker trait indicating that the type’s implementation of join (|) is commutative.

JoinIdempotent

Marker trait indicating that the type’s implementation of join (|) is idempotent.

JoinSemilattice

An “alias trait” representing join-semilattices. Equivalent to JoinCommutative+JoinAssociative+JoinIdempotent.

Lattice

An “alias trait” representing lattices. Equivalent to MeetSemilattice+JoinSemilattice+Absorption.

Meet

MeetAssociative

Marker trait indicating that the type’s implementation of meet (&) is associative.

MeetCommutative

Marker trait indicating that the type’s implementation of meet (&) is commutative.

MeetIdempotent

Marker trait indicating that the type’s implementation of meet (&) is idempotent.

MeetSemilattice

An “alias trait” representing meet-semilattices. Equivalent to MeetCommutative+MeetAssociative+MeetIdempotent.

Mul

MulAssociative

Marker trait indicating that the type’s implementation of multiplication is associative.

MulCommutative

Marker trait indicating that the type’s implementation of multiplication is commutative.

MulGroup

An “alias trait” representing groups with the operator *. Equivalent to MulMonoid+Invertible

MulIdentity

Represents types that have an multiplicative identity. That is, the element e for which e * x == x * e == x, for any x of the type.

MulMonoid

An “alias trait” representing monoids with the operator *. Equivalent to MulSemigroup+MulIdentity

MulSemigroup

An “alias trait” representing semigroups with the operator *. Equivalent to MulAssociative

PartiallyInvertible

Represents types for which some elements may have multiplicative inverses.

Ring

An “alias trait” representing rings with a multiplicative identity. Equivalent to RingWithoutIdentity+MulIdentity

RingWithoutIdentity

An “alias trait” representing rings that may or may not have an identity (often called “rngs”). Equivalent to AbelianAddGroup+ MulSemigroup+AddMulDistributive.

Sub

Attribute Macros

chalk

An attribute macro that can be applied to types in order to simplify implementations of algebraic structures.