brendanzab / algebra

Abstract algebra for Rust (still very much a WIP!)
Apache License 2.0
60 stars 9 forks source link

Wrapper struct for ops are annoying to use. #35

Open sebcrozet opened 8 years ago

sebcrozet commented 8 years ago

The solution we chose for #18 is to parametrize traits over the operator symbol (which is identified using structs). Thus we don't have MagmaAdditive nor MagmaMultiplicative traits. The down side is that we cannot use operator overloading without first wrapping our values into a struct so that we can "see" them as part of a Magma<Additive> or Magma<Multiplicative>.

Thus something like this, for elements of a field:

(a + b) * c

has to become something like that:

Wm((Wa(a) + Wa(b))) * Wm(c)

where Wm and Wa are wrappers to access the addition and multiplication operations.

There are very common places where wrapper structs could be avoided because we already know that, e.g., a type implements Magma<Additive> iff. it implements Add<...> because of default implementations like that one. What I propose here is, for example, to modify the ring trait from this:

pub trait RingApprox
    : GroupAbelianApprox<Additive>
    + MonoidApprox<Multiplicative>
{ }

to that:

pub trait RingApprox
    : GroupAbelianApprox<Additive>
    + MonoidApprox<Multiplicative>
    + Add<Self, Output = Self>  // Addition operator.
    + Sub<Self, Output = Self>  // Additive divisibility.
    + Neg<Output = Self>          // Additive inverse.
    + Mul<Self, Output = Self>  // Multiplication operator. 
{ }

Because RingApprox explicitly depends on the Additive and Multiplicative operators, it is fine to add the other operator-overloading-related constraints because we know they have been implemented as well because of our default implementations of the respective magmas. This trick may be applied to any trait that explicitly mention Additive and Multiplicative on their constraints.

WaDelma commented 8 years ago

This would close the door of using specialization to implement Magma<Additive> for stuff that doesn't implement Add

sebcrozet commented 8 years ago

Good point, I forgot that specialization will exist on Rust in the future.This means that our default implementations for T can no longer be assumed to be the only ones.

Still, I wonder if there is a nice way to get rid of those wrapper structs. Now I understand better why the discussion of #18 was so extensive!

WaDelma commented 8 years ago

One way to make usage easier would be to create macro that would automatically wrap stuff or associate ZSTs with symbols. Not sure how hard that would be though.

WaDelma commented 8 years ago

Here is POC of the operation association macro I was talking about: https://play.rust-lang.org/?gist=52e6f854ac55364809721f73452a6a30&version=nightly&backtrace=0

sebcrozet commented 8 years ago

That might be a useful option. Though I'm not sure how well it would work for very complex expressions (that include method calls inside of the mathematical formula).

Also it would be useful to verify that the compiler is able to remove those wrapper structs automatically during optimizations. We don't want them to hurt performances.

WaDelma commented 8 years ago

I made the numbers to go through #[inline(never)] function and looked ASM and didn't see any branching there. The macro should always generate if-else chain that has staticly only one branch true.
https://play.rust-lang.org/?gist=b69a280369d13ca296be24689d8ebbc0&version=nightly&backtrace=0
Ofcourse this should be checked with more complex test cases.

WaDelma commented 8 years ago

I was able to improve the macro: https://play.rust-lang.org/?gist=3ba719a8390b05cf6d0e331ed86134a4&version=stable&backtrace=0 It now supports multiple tokens long operators and equality checking.
I cannot unfortunately remove the unnessary paretheses because of macro_rules limitations (space is token, so removing parentheses makes it ambigious).
There is still problems with it:

standard_algebra! {
    ((a.clone()) * (b.clone())).approx_eq(&((b) * (a)))
}

doesn't parse (I am testing it by trying to convert usages in the library).