algebraic-gen 0.1.0

//! Generates performant geometric products for any dimension of space.
//!
//! The crate provides a macro [`generate_geometric_product!`]. Given a function
//! identifier and a nonnegative integer literal, the macro generates a function
//! that computes the geometric product of two coefficient representations of
//! multivectors.
//!
//! For example, `generate_geometric_product!(my_product, 3)` generates the
//! following function:
//!
//! ```
//! pub fn my_product<A, B, T>(a: &A, b: &B) -> [T; 8]
//! where
//!     A: ::core::ops::Index<usize, Output = T>,
//!     B: ::core::ops::Index<usize, Output = T>,
//!     T: Copy +
//!         ::core::ops::Mul<Output = T> +
//!         ::core::ops::Add<Output = T> +
//!         ::core::ops::Sub<Output = T>,
//! {
//!     [
//!         a[0] * b[0] - a[1] * b[1] - a[2] * b[2] - a[3] * b[3] - a[4] * b[4] - a[5] * b[5] - a[6] * b[6] + a[7] * b[7],
//!         a[0] * b[1] + a[1] * b[0] + a[2] * b[3] - a[3] * b[2] + a[4] * b[5] - a[5] * b[4] - a[6] * b[7] - a[7] * b[6],
//!         a[0] * b[2] - a[1] * b[3] + a[2] * b[0] + a[3] * b[1] + a[4] * b[6] + a[5] * b[7] - a[6] * b[4] + a[7] * b[5],
//!         a[0] * b[3] + a[1] * b[2] - a[2] * b[1] + a[3] * b[0] - a[4] * b[7] + a[5] * b[6] - a[6] * b[5] - a[7] * b[4],
//!         a[0] * b[4] - a[1] * b[5] - a[2] * b[6] - a[3] * b[7] + a[4] * b[0] + a[5] * b[1] + a[6] * b[2] - a[7] * b[3],
//!         a[0] * b[5] + a[1] * b[4] + a[2] * b[7] - a[3] * b[6] - a[4] * b[1] + a[5] * b[0] + a[6] * b[3] + a[7] * b[2],
//!         a[0] * b[6] - a[1] * b[7] + a[2] * b[4] + a[3] * b[5] - a[4] * b[2] - a[5] * b[3] + a[6] * b[0] - a[7] * b[1],
//!         a[0] * b[7] + a[1] * b[6] - a[2] * b[5] + a[3] * b[4] + a[4] * b[3] - a[5] * b[2] + a[6] * b[1] + a[7] * b[0],
//!     ]
//! }
//! ```
//!
//! In this example, the implementation of the function will access `a` and `b`
//! at indices `0..8`. In the general case, it will access its arguments at
//! indices `0..1 << D` and return a value of type `[T; 1 << D]`.
//!
//! # Example
//!
//! The functions are straightforward to generate and use. Pass a (small)
//! nonnegative integer to the macro and it generates the product function.
//! (Check it out with `cargo expand`.)
//!
//! ```rust
//! use algebraic_gen::generate_geometric_product;
//!
//! generate_geometric_product!(my_product, 3);
//!
//! fn main() {
//!   let a: [f64; 8] = [1., 2., 3., 4., 5., 6., 7., 8.];
//!   let b: [f64; 8] = [8., 7., 6., 5., 4., 3., 2., 1.];
//!
//!   let c = my_product(&a, &b);
//!
//!   println!("The geometric product of {:?} and {:?} is {:?}", a, b, c);
//!
//!   assert_eq!(c, [-88.0, -18.0, 60.0, -18.0, 72.0, 102.0, -36.0, 114.0]);
//! }
//! ```
//!
//! # Geometric Algebra
//!
//! A [geometric algebra](https://en.wikipedia.org/wiki/Geometric_algebra) is defined with respect
//! to a given dimension `D` of space. In such an algebra, there exist objects
//! of different *degrees* from zero to `D` (inclusive). Objects of degree zero
//! are scalars, objects of degree one are vectors, and objects of degree two,
//! three, etc. are bivectors, trivectors, et cetera. These higher degree
//! objects are created by wedge product of vectors. Combining all vectors via
//! wedge product results a *pseudoscalar* of degree `D`. Objects of any degree
//! can be scaled and added to form *multivectors*.
//!
//! Importantly for this crate, any multivector can be represented uniquely as a
//! linear combination of elements of a chosen *base* with `2^D` different
//! objects, meaning that we can represent multivectors as arrays of floating
//! point numbers of that size. The return types `[T; 1]`, `[T; 2]`, `[T; 4]`,
//! `[T; 8]`, etc., of the functions generated by this crate are exactly those
//! representations of multivectors of geometric algebras of spaces with `0`,
//! `1`, `2`, `3`, etc. dimensions, respectively.
//!
//! The macro attaches documentation of the choice of base to the generated
//! function. Sticking to 3D for an example, the choice of base in this crate
//! is: one scalar (`S`), three vectors (`X`, `Y`, `Z`), three bivectors (`X∧Y`,
//! `X∧Z`, `Y∧X`), and one pseudoscalar (`X∧Y∧Z`). The generated
//! product interprets the 8-dimensional coefficient arrays as `[S, X, Y, X∧Y,
//! Z, X∧Z, Y∧Z, X∧Y∧Z]`. In the documentation attached to the respective
//! generated product functions, this is represented as `[[], [0], [1], [0,1],
//! [2], [0,2], [1,2], [0,1,2]]`.
//!
//! # On the Generation
//!
//! Maybe there is better way to get the products that doesn't use the
//! \'sledgehammer\' proc macro approach. The generation is not performant, but
//! we're talking build time.
//!
//! The generation logic is inspired by
//! [All Hail Geometric Algebra!](https://crypto.stanford.edu/~blynn/haskell/ga.html).
//!
//! Brief description of the how the macro works:
//! * Generates elements (base)
//!   * Product is simple concatenation here
//!   * Canonization with Bubblesort & a kind of duplication elimination
//! * Generates product sums
//!   * Expand terms
//!   * More products & canonization
//!   * Adding/Subtracting based on sign returned by canonization
//! * A bit of formatting
//!
//! More details in the source code:
//! [`algebra_generation.rs`](../src/algebraic_gen/algebra_generation.rs.html).

mod algebra_generation;
use algebra_generation::{generate_elements, generate_product_sums};
use core::str::FromStr;
use proc_macro::TokenStream;
use quote::quote;
use syn::{parse::Parse, parse_macro_input, Error, ExprArray};

fn generate_product_string(product_sums: &[Vec<(bool, usize, usize)>]) -> String {
    format!(
        "[{}]",
        product_sums
            .iter()
            .map(|sum| {
                sum.iter()
                    .enumerate()
                    .map(|(i, (n, a, b))| {
                        format!(
                            "{}a[{a}] * b[{b}]",
                            if i == 0 {
                                ""
                            } else if *n {
                                "- "
                            } else {
                                "+ "
                            },
                        )
                    })
                    .collect::<Vec<_>>()
                    .join(" ")
            })
            .collect::<Vec<_>>()
            .join(","),
    )
}

fn generate_base_string(elements: &[Vec<usize>]) -> String {
    let dimension = elements.len().trailing_zeros() as usize;
    elements.iter().enumerate().fold(
        "\n\n|Index|Outer Product|Type|\n|-|-|-|".to_string(),
        |bases, (i, element)| {
            format!(
                "{bases}\n|{}|{:?}|{}|",
                i,
                element,
                match element.len() {
                    0 => "Scalar".to_string(),
                    k if k == dimension => "Pseudoscalar".to_string(),
                    1 => "Vector".to_string(),
                    2 => "Bivector".to_string(),
                    3 => "Trivector".to_string(),
                    4 => "Quadvector".to_string(),
                    5 => "Quintvector".to_string(),
                    k => format!("{}-Vector", k),
                }
            )
        },
    )
}

struct MacroArgs {
    function_ident: syn::Ident,
    _comma: syn::token::Comma,
    dimension: syn::LitInt,
}

impl Parse for MacroArgs {
    fn parse(input: syn::parse::ParseStream) -> syn::Result<Self> {
        Ok(MacroArgs {
            function_ident: input.parse()?,
            _comma: input.parse()?,
            dimension: input.parse()?,
        })
    }
}

/// The one macro exported by this crate
#[proc_macro]
pub fn generate_geometric_product(input: TokenStream) -> TokenStream {
    let args = parse_macro_input!(input as MacroArgs);

    let dimension = match args.dimension.base10_parse::<usize>() {
        Ok(dimension) => dimension,
        Err(err) => {
            return Error::new_spanned(args.dimension, err)
                .to_compile_error()
                .into()
        }
    };

    let function_ident = args.function_ident;

    let elements = generate_elements(dimension);
    let product_sums = generate_product_sums(&elements);
    let product_string = generate_product_string(&product_sums);

    let array_length = elements.len();

    // this is the really crazy part, I don't know how to do it better
    // first put the array expression into a string, then parse it
    // and finally put it into a function via quote
    let product_stream = TokenStream::from_str(&product_string).unwrap();
    let product: ExprArray = syn::parse(product_stream).unwrap();

    let basis = generate_base_string(&elements);
    let dimension = format!("{}", dimension);
    let documentation = format!(
        "Calculates the geometric product for multivectors of {dimension}-dimensional space.
        The arrays are coefficient representations wrt. the following {array_length} basis
        elements.",
    );

    let gen = quote! {
        #[doc = #documentation]
        #[doc = #basis]
        pub fn #function_ident<A, B, T>(a: &A, b: &B) -> [T; #array_length]
        where
            A: ::core::ops::Index<usize, Output = T>,
            B: ::core::ops::Index<usize, Output = T>,
            T: Copy +
                ::core::ops::Mul<Output = T> +
                ::core::ops::Add<Output = T> +
                ::core::ops::Sub<Output = T>,
        {
            #product
        }
    };

    gen.into()
}