Experimenting with generics in Rust: little library for Bezier curves - part 1

Not so long time ago, I decided to look into one aspect of Rust programming language that is of a certain personal interest for me --- generic programming. Generic (or template) programming is one of my favorite paradigms in modern C++, and it was certainly worth trying how it is currently supported in a shiny "new" language such as Rust. I actually liked what I found out there. After struggling a little with Rust's strict type system, I even started to appreciate its philosophy of being explicit.

This post is an attempt to document some of my experiments with generics in Rust. As time goes by, I found that it is quite handy to leave some traces and artefacts so that there is a place go back after some time. This post is basically written to my future self and maybe for someone who finds it useful.

Code, examples, tests, and some other documentation for this post can be in the repo.

Tiny generic numeric library: requirements

The best way of learning is by doing, and there is no other way... So let's try write a tiny numeric library which nevertheless can be helpful elsewhere. The truth is that I have a similar library in C++ which I used quite a lot, so this would be a good test for Rust.

The requirements are as follows: write a library to manipulate a generic Bezier curve (or a polynomial in the Bernstein basis if you prefer it this way).

• The control polygon of the Bezier curve should be of a generic type T which supports usual vector-space operations: it should support f32/f64, complex numbers, and vectors (in linear algebra sense).

• The curve should be parameterized with a parameter of a generic type U, which should support f32/f64, rationals, and maybe arbitrary-precision floats.

• The library should use stack memory allocation (no memory allocations on the heap), which means that the size of the control polygon is a compile-time constant N.

• The library should implement usual vector space operations on the control polygon, eval(u) method to get the point on the curve of type T at the parameter value u of type U, diff()/integ() method to get new instance of the curve which is the derivative/integral of the current curve at every point, and multiplication of two polynomials of different degrees. The last three methods are especially problematic because they should return an instance of a different size: N-1, N + 1, or N + M in general.

So these are all the requirement for now. Let's try it...

Generic Bezier curves: design considerations

The first thing I stumbled upon while tying to implement these requirements was the lack of support for generic constant expressions in Rust, which I briefly summarized in my previous post.

In general, it is a known problem, and since I don't expect this example to ever reach a productionable stage, I decided to go with Rust nightly and use a highly experimental generic_const_exprs feature.

#![allow(incomplete_features)]
#![feature(generic_const_exprs)]

And I compile it with rustc 1.80.0-nightly (d84b90375 2024-05-19).

Second difficulty for designing generics is Rust's explicit type system, which does very little for you if you want automatic type promotions and conversions. This is actually a feature not a bug, and part of Rust's philosophy of being explicit. It helps to ensure that the program is correct, but makes life harder...

For example, I want to store coefficients internally in the array of type [T; N], where N is constant type parameter. In Rust, N must be of the platform-dependent pointer-size type usize, and there is a little you can do to convert usize to other types using core language. This is of course for safety reasons, but in a generic environment, in conjunction with direct prohibition for implementing external traits for standard types, I either have to implement conversion manually, or rely on third party crates such as conv for example.

There is also an interesting crate generic-array but we are not going this path here.

After experimenting a little bit with different dependencies, I decided to depend on num crate, that exposes some new types for e.g. rationals and complex numbers, and also has extended type conversions in num::cast including handy FromPrimitive trait.

[dependencies]
num = "0.4.3"

Finally, let me introduce our type for a generic Bezier curve.

pub struct Bernstein<T, U, const N: usize> {
    coef: [T; N],
    segm: (U, U),
}

We have two generic types: T for control polygon, and U for the curve parameter (which I decided to make a part of the type), and one constant generic parameter for the size of the control polygon (the order of the curve is N - 1, i.e. a cubic Bezier has N = 4 control points).

The fields are private because the interval where Bezier curve is defined will be defaulted to (0, 1). Reason? It is hard to introduces anything that includes testing for equality or ordering in a numeric generic environment, because when it boils down to floating point math... well, you know.

Let's provide a simple accessors to get-set our type, and I leave it at this primitive level for now. Here, the type U is bounded by num::Num trait which includes convenient U::one() and U::zero() to set the default interval.

impl<T, U, const N: usize> Bernstein<T, U, N> where
    U: Num,
{

    /// Create new instance of a Bernstein polynomial from an array of
    /// coefficients in the Bernstein basis over the default interval (0, 1).
    pub fn new(coef: [T; N]) -> Bernstein<T, U, N> {
        Bernstein {
            coef: coef,
            segm: (U::zero(), U::one()),
        }
    }

    /// Return an array of coefficients for a polynomial in the Bernstein basis.
    pub fn coef(&self) -> &[T; N] {
        &self.coef
    }

}

Now, I have all the prerequisites for the next steps. It is possible to create an instance of the Bezier curve like this.

let p0 = Rational64::new(1, 5);
let p1 = Rational64::new(-3, 7);
let p2 = Rational64::new(4, 13);
let p3 = Rational64::new(-11, 17);

let c: Bernstein<Rational64, Rational64, 4> = Bernstein::new([p0, p1, p2, p3]);

Here, I specify the control polygon that has four rational control points, and rationals are also used for the curve parameterization on the interval (0, 1). The syntax is quite terse for my taste because the type is not automatically deduced from ::new(), and I have to spell out it explicitly in Bernstein<Rational64, Rational64, 4> but it's okay.

Next steps...

The next will be to implement a bunch of methods to evaluate the curve at a given point, generic differentiation and integration. The last two require generic_const_exprs, and that is where experimental features kick in.