Sign in

    luna-generic

    Algebraic traits and default numeric instances that define the generic foundation for LunaFlow math packages.

    math
    algebra
    interface
    Download zip
    Author
    Version
    0.4.0
    License
    Apache-2.0
    Last updated
    7 hours ago
    Downloads
    6K

    #Luna-Generic

    General algebraic traits and default numeric instances for Luna projects.

    #v0.4.0 - Canonical Maps and Representative Lifts

    This documentation tracks the intended v0.4.0 release content.

    #Package Positioning

    • luna-generic provides lightweight algebraic traits for additive, multiplicative, ring-like, field-like, and numeric behavior.
    • The package ships default instances for signed integers, unsigned integers, BigInt, Float, and Double.
    • Conversions between number types separate the canonical homomorphism out of ℤ from the choice of a representative for a machine integer.

    #What Defines v0.4.0

    • FromNat and FromInteger are target-side traits for the unique homomorphisms ℕ -> Self and ℤ -> Self, taking a BigInt argument.
    • Integral now extends Semiring + FromInteger: an integral type is ℤ or a quotient ℤ/2^k, and normalize must be a section of the canonical map, from_integer(normalize(x)) == x. This is a breaking change for external Integral instances.
    • lift_to lifts an integral value to its representative and maps it into any FromInteger target. It is a function, not a homomorphism.
    • Section[S, Q, A] certifies representative lifts of quotient algebras; Section::of_integral is the canonical one for every integral type.
    • Hom::from_integer certifies the canonical map out of ℤ.
    • NatHomomorphism, IntegralHomomorphism, Hom::from_nat and Hom::from_integral are deprecated: they compose a lift with a canonical map, which is not a homomorphism for fixed-width sources.

    #Public Surface

    • Traits: AddMonoid, MulMonoid, AddGroup, MulGroup, Semiring, Ring, Field (commutative), FromNat, FromInteger, Integral, Nat, Num, and the deprecated NatHomomorphism, IntegralHomomorphism
    • Operations: One, Zero, Inverse, Conjugate
    • Functions: lift_to
    • Generalized homomorphisms: Hom, Section, Algebra, Op, Prod, Reduct, and the signature tags AddMonoidSig, MulMonoidSig, AddGroupSig, SemiringSig, RingSig
    • Default numeric types: Int, Int16, Int64, UInt, UInt16, UInt64, BigInt, Float, Double

    #Integer Families

    • Integral covers signed and unsigned integers plus BigInt: Int, Int16, Int64, UInt, UInt16, UInt64, BigInt
    • Nat covers the integral types with non-negative representatives: UInt, UInt16, UInt64
    • Fixed-width integers are ℤ/2^k: their canonical map from ℤ reduces modulo 2^k, and normalize picks the representative in the type's range
    • Byte is intentionally excluded from both traits
    • Unsigned integer instances stop at Semiring and do not implement AddGroup, Ring, or Num

    #Conversion Guidance

    • FromInteger::from_integer is exact for BigInt, reduces modulo 2^k for fixed-width integers, and rounds for Float and Double
    • lift_to(x) turns a machine integer into another number type without promising to preserve operations; it is a homomorphism only when the target modulus divides the source modulus, as for Int64 -> Int
    • Use Section::of_integral and Hom::from_integer when the laws need to be certified and checked

    #Documentation

    Comprehensive API documentation is available at mooncakes.io.

    The manual is published at lunaflow.cn/en/luna-generic, with Simplified Chinese and Japanese translations. Its English source lives in doc/manual; translations are maintained as gettext catalogs in doc/locale.

    #Changelog

    The current version is 0.4.0. Release notes for every version are in CHANGELOG.md.

    #Development

    Requires the MoonBit toolchain 0.10 or later. Useful local commands:

    moon check moon test

    #Release Checklist

    Before triggering the publish workflow:

    1. Confirm moon.mod contains the intended version.
    2. Confirm the README and doc/manual match the exported package surface.
    3. Run moon check and moon test.
    4. Trigger publish-package after the release commit is pushed.

    AddGroup

    pub(open) trait AddGroup : AddMonoid + Neg + Sub {
    }

    impl AddGroup for Int
    impl AddGroup for Int16
    impl AddGroup for Int64
    impl AddGroup for Float
    impl AddGroup for Double
    impl AddGroup for BigInt

    AddMonoid

    pub(open) trait AddMonoid : Add + Zero {
    }

    impl AddMonoid for Int
    impl AddMonoid for Int16
    impl AddMonoid for Int64
    impl AddMonoid for UInt
    impl AddMonoid for UInt16
    impl AddMonoid for UInt64
    impl AddMonoid for Float
    impl AddMonoid for Double
    impl AddMonoid for BigInt

    Conjugate

    pub(open) trait Conjugate {
    fn conjugate(Self) -> Self
    }

    Field

    pub(open) trait Field : Ring + Inverse + Div {
    }

    A field: a commutative ring in which every non-zero element has an inverse.

    Laws, which the compiler does not check: a * b == b * a, a * inv(a) == 1 for a != 0, and a / b == a * inv(b) for b != 0. Commutativity is part of the contract: a division ring whose multiplication does not commute must not implement Field, because generic code may rely on inv(a * b) == inv(a) * inv(b).
    impl Field for Float
    impl Field for Double

    FromInteger

    pub(open) trait FromInteger : FromNat {
    fn from_integer(
    BigInt
    ) -> Self
    }

    The canonical map out of the integers: the unique ring homomorphism ℤ -> Self. It must agree with from_natural on non-negative arguments.
    impl FromInteger for Int
    impl FromInteger for UInt

    FromNat

    pub(open) trait FromNat {
    fn from_natural(
    BigInt
    ) -> Self
    }

    The canonical map out of the naturals: the unique semiring homomorphism ℕ -> Self. The argument must be non-negative.
    impl FromNat for Int
    impl FromNat for Int16
    impl FromNat for Int64
    impl FromNat for UInt
    impl FromNat for UInt16
    impl FromNat for UInt64
    impl FromNat for Float
    impl FromNat for Double

    Integral

    pub(open) trait Integral : Semiring + FromInteger {
    fn normalize(Self) ->
    BigInt

    }

    An integer type: ℤ itself, or a quotient ℤ/2^k such as the fixed-width integers. normalize picks the representative of each class as a BigInt; it is a homomorphism only when Self really is ℤ.

    Law: normalize is a section of the canonical map, Self::from_integer(normalize(x)) == x. Section::of_integral packages the pair as a certificate.
    impl Integral for UInt16
    impl Integral for UInt64

    IntegralHomomorphism

    #deprecated("Implement `FromInteger` and use `lift_to` instead.")
    pub(open) trait IntegralHomomorphism : NatHomomorphism {
    fn[S : Integral + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + FromInteger + FromNat] from_integral(value : S) -> Self
    }

    Deprecated: lifts an Integral source to ℤ and maps it into Self, which is not a homomorphism for fixed-width sources. Implement FromInteger and use lift_to instead.

    Inverse

    pub(open) trait Inverse {
    fn inv(Self) -> Self
    }

    impl Inverse for Float
    impl Inverse for Double

    MulGroup

    pub(open) trait MulGroup : MulMonoid + Inverse + Div {
    }

    impl MulGroup for Float
    impl MulGroup for Double

    MulMonoid

    pub(open) trait MulMonoid : Mul + One {
    }

    impl MulMonoid for Int
    impl MulMonoid for Int16
    impl MulMonoid for Int64
    impl MulMonoid for UInt
    impl MulMonoid for UInt16
    impl MulMonoid for UInt64
    impl MulMonoid for Float
    impl MulMonoid for Double
    impl MulMonoid for BigInt

    Nat

    pub(open) trait Nat : Integral {
    }

    An integer type whose representatives are non-negative, such as the unsigned fixed-width integers.
    impl Nat for UInt
    impl Nat for UInt16
    impl Nat for UInt64

    NatHomomorphism

    #deprecated("Implement `FromNat` and use `lift_to` instead.")
    pub(open) trait NatHomomorphism {
    fn[S : Nat + Integral + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + FromInteger + FromNat] from_nat(value : S) -> Self
    }

    Deprecated: lifts a Nat source to ℕ and maps it into Self, which is not a homomorphism for fixed-width sources. Implement FromNat and use lift_to instead.

    Num

    pub(open) trait Num : Ring {
    fn abs(Self) -> Self
    fn signum(Self) -> Self
    }

    impl Num for Int
    impl Num for Int16
    impl Num for Int64
    impl Num for Float
    impl Num for Double

    One

    pub(open) trait One {
    fn one() -> Self
    }

    impl One for Int
    impl One for Int16
    impl One for Int64
    impl One for UInt
    impl One for UInt16
    impl One for UInt64
    impl One for Float
    impl One for Double

    Ring

    pub(open) trait Ring : Semiring + Neg + Sub {
    }

    impl Ring for Int
    impl Ring for Int16
    impl Ring for Int64
    impl Ring for Float
    impl Ring for Double
    impl Ring for BigInt

    Semiring

    pub(open) trait Semiring : AddMonoid + MulMonoid {
    }

    impl Semiring for Int
    impl Semiring for Int16
    impl Semiring for Int64
    impl Semiring for UInt
    impl Semiring for UInt16
    impl Semiring for UInt64
    impl Semiring for Float
    impl Semiring for Double
    impl Semiring for BigInt

    Zero

    pub(open) trait Zero {
    fn zero() -> Self
    }

    impl Zero for Int
    impl Zero for Int16
    impl Zero for Int64
    impl Zero for UInt
    impl Zero for UInt16
    impl Zero for UInt64
    impl Zero for Float
    impl Zero for Double

    AddGroupSig

    pub enum AddGroupSig {
    }

    Signature tag: 0, + and unary -.

    AddMonoidSig

    pub enum AddMonoidSig {
    }

    Signature tag: 0 and +.

    Algebra

    pub struct Algebra[S, A] {
    // private fields
    }

    An interpretation of the signature S on the carrier A.

    Two algebras of the same S must list the same operations in the same order; Hom::check_by aborts when they do not.

    Algebra::add_group

    fn[A : AddGroup + AddMonoid + Add + Zero + Neg + Sub] Algebra::add_group() -> Algebra[AddGroupSig, A]

    Algebra::add_monoid

    fn[A : AddMonoid + Add + Zero] Algebra::add_monoid() -> Algebra[AddMonoidSig, A]

    Algebra::make

    fn[S, A] Algebra::make(ops : Array[Op[A]]) -> Algebra[S, A]

    Builds an algebra for a custom signature tag.

    Certificates assume one S-algebra per carrier: every Algebra[S, A] passed to check for the same S and A must interpret the operations the same way. Hom::then chains certificates through the middle carrier, so two different algebras on it (say max and min both tagged S) would compose into a map that preserves neither.

    Algebra::mul_monoid

    fn[A : MulMonoid + Mul + One] Algebra::mul_monoid() -> Algebra[MulMonoidSig, A]

    Algebra::prod

    fn[S, A, B] Algebra::prod(a : Algebra[S, A], b : Algebra[S, B]) -> Algebra[S, Prod[A, B]]

    The componentwise product algebra.

    Algebra::ring

    fn[A : Ring + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + Neg + Sub] Algebra::ring() -> Algebra[RingSig, A]

    Algebra::semiring

    fn[A : Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One] Algebra::semiring() -> Algebra[SemiringSig, A]

    Hom

    pub struct Hom[S, A, B] {
    // private fields
    }

    A map A -> B certified to preserve every operation of S.

    Hom::apply

    fn[S, A, B] Hom::apply(self : Hom[S, A, B], x : A) -> B

    Hom::check

    fn[S, A, B : Eq] Hom::check(self : Hom[S, A, B], src : Algebra[S, A], dst : Algebra[S, B], samples : Array[A]) -> Bool

    Tests the homomorphism law with exact equality on every operation of S over all tuples drawn from samples.

    Hom::check_by

    fn[S, A, B] Hom::check_by(self : Hom[S, A, B], src : Algebra[S, A], dst : Algebra[S, B], samples : Array[A], rel : (B, B) -> Bool) -> Bool

    Tests rel(f(op_A(xs)), op_B(xs.map(f))) for every operation of S over all tuples drawn from samples. Choose rel to set the strength of preservation: equality for strict homomorphisms, <= for lax ones such as subadditive maps, and a tolerance for floating-point targets.

    An operation of arity n is tested on samples.length()^n tuples.

    Hom::forget

    fn[S, T, A, B] Hom::forget(self : Hom[S, A, B], _reduct : Reduct[S, T]) -> Hom[T, A, B]

    Forgets part of the preserved structure along a reduct.

    Hom::from_integer

    The canonical map ℤ -> R given by FromInteger, as a certificate. It is the unique semiring map out of ℤ, so it holds on every input; use Hom::to_ring when R is a ring. Float and Double targets only satisfy it up to rounding.

    For a fixed-width source, first lift with Section::of_integral: the composite is not a homomorphism unless the target modulus divides the source modulus.

    Hom::from_integral

    #deprecated("Use `Hom::from_integer` with `Section::of_integral`, or `lift_to`.")
    fn[Z : Integral + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + FromInteger + FromNat, R : IntegralHomomorphism + NatHomomorphism] Hom::from_integral() -> Hom[SemiringSig, Z, R]

    Deprecated: certifies IntegralHomomorphism::from_integral, which is not a homomorphism for fixed-width sources. Use Hom::from_integer together with Section::of_integral, or lift_to when no certificate is needed.

    Hom::from_nat

    #deprecated("Use `Hom::from_integer` with `Section::of_integral`, or `lift_to`.")
    fn[N : Nat + Integral + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + FromInteger + FromNat, R : NatHomomorphism] Hom::from_nat() -> Hom[SemiringSig, N, R]

    Deprecated: certifies NatHomomorphism::from_nat, which is not a homomorphism for fixed-width sources. Use Hom::from_integer together with Section::of_integral, or lift_to when no certificate is needed.

    Hom::fst

    fn[S, A, B] Hom::fst() -> Hom[S, Prod[A, B], A]

    Hom::id

    fn[S, A] Hom::id() -> Hom[S, A, A]

    Hom::pair

    fn[S, A, B, C] Hom::pair(f : Hom[S, A, B], g : Hom[S, A, C]) -> Hom[S, A, Prod[B, C]]

    Pairing into the product: x => { fst: f(x), snd: g(x) }.

    Hom::postulate

    fn[S, A, B] Hom::postulate(f : (A) -> B) -> Hom[S, A, B]

    Trusts f as an S-homomorphism without proof.

    Proof obligation for the caller: for every operation op of S and all arguments xs, f(op_A(xs)) == op_B(xs.map(f)). Back every call with a Hom::check or Hom::check_by test.

    The obligation is always strict equality. A map that only passes a lax (<=) or tolerance check is still composed as a strict homomorphism by then, pair and the other rules, so do not compose such certificates without checking the result again.

    Hom::snd

    fn[S, A, B] Hom::snd() -> Hom[S, Prod[A, B], B]

    Hom::then

    fn[S, A, B, C] Hom::then(self : Hom[S, A, B], next : Hom[S, B, C]) -> Hom[S, A, C]

    Composition: first self, then next.

    Hom::to_add_group

    fn[A : AddGroup + AddMonoid + Add + Zero + Neg + Sub, B : AddGroup + AddMonoid + Add + Zero + Neg + Sub] Hom::to_add_group(self : Hom[AddMonoidSig, A, B]) -> Hom[AddGroupSig, A, B]

    A monoid homomorphism between groups preserves negation.

    Hom::to_ring

    fn[A : Ring + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + Neg + Sub, B : Ring + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + Neg + Sub] Hom::to_ring(self : Hom[SemiringSig, A, B]) -> Hom[RingSig, A, B]

    A semiring homomorphism between rings preserves negation.

    MulMonoidSig

    pub enum MulMonoidSig {
    }

    Signature tag: 1 and *.
    pub(all) struct Op[A] {
    name : String
    arity : Int
    eval : (Array[A]) -> A
    }

    One operation of a single-sorted signature. arity == 0 is a constant. eval receives exactly arity arguments.

    Prod

    pub(all) struct Prod[A, B] {
    fst : A
    snd : B
    } derive(Eq,
    Debug
    )

    Binary product carrier. Operations act componentwise.
    impl AddGroup for Prod[A, B]
    impl AddMonoid for Prod[A, B]
    impl MulMonoid for Prod[A, B]
    impl One for Prod[A, B]
    impl Ring for Prod[A, B]
    impl Semiring for Prod[A, B]
    impl Zero for Prod[A, B]
    impl Add for Prod[A, B]
    impl Mul for Prod[A, B]
    impl Neg for Prod[A, B]
    impl Sub for Prod[A, B]

    Prod::add

    fn[A : Add, B : Add] Prod::add(x : Prod[A, B], y : Prod[A, B]) -> Prod[A, B]

    Prod::equal

    fn[A : Eq, B : Eq] Prod::equal(Prod[A, B], Prod[A, B]) -> Bool

    Prod::mul

    fn[A : Mul, B : Mul] Prod::mul(x : Prod[A, B], y : Prod[A, B]) -> Prod[A, B]

    Prod::neg

    fn[A : Neg, B : Neg] Prod::neg(x : Prod[A, B]) -> Prod[A, B]

    Prod::not_equal

    fn[A : Eq, B : Eq] Prod::not_equal(x : Prod[A, B], y : Prod[A, B]) -> Bool

    Prod::one

    fn[A : One, B : One] Prod::one() -> Prod[A, B]

    Prod::sub

    fn[A : Sub, B : Sub] Prod::sub(x : Prod[A, B], y : Prod[A, B]) -> Prod[A, B]

    Prod::zero

    fn[A : Zero, B : Zero] Prod::zero() -> Prod[A, B]

    Reduct

    pub struct Reduct[S, T] {
    // private fields
    }

    Witness that every S-structure is also a T-structure, so an S-homomorphism is also a T-homomorphism. Only this package creates witnesses.

    Reduct::refl

    fn[S] Reduct::refl() -> Reduct[S, S]

    Reduct::then

    fn[S, T, U] Reduct::then(self : Reduct[S, T], _next : Reduct[T, U]) -> Reduct[S, U]

    RingSig

    pub enum RingSig {
    }

    Signature tag: 0, 1, +, * and unary -.

    Section

    pub struct Section[S, Q, A] {
    // private fields
    }

    A lift of the quotient Q back into A along the projection proj.

    Section::check

    fn[S, Q : Eq, A] Section::check(self : Section[S, Q, A], samples : Array[Q]) -> Bool

    Tests the section law proj(lift(q)) == q on every sample.

    Section::check_ops

    fn[S, Q : Eq, A] Section::check_ops(self : Section[S, Q, A], quotient : Algebra[S, Q], cover : Algebra[S, A], samples : Array[Q]) -> Bool

    Tests proj(op_A(xs.map(lift))) == op_Q(xs) for every operation of S over all tuples drawn from samples, which exercises proj as a homomorphism on representatives.

    Together with the section law this means lift preserves every operation up to the kernel of proj, and exactly whenever op_A(xs.map(lift)) is a representative: then it equals lift(proj(...)) == lift(op_Q(xs)). Outside the representatives the difference is a kernel element, such as the carry of a wrapped addition.

    Section::forget

    fn[S, T, Q, A] Section::forget(self : Section[S, Q, A], reduct : Reduct[S, T]) -> Section[T, Q, A]

    Forgets part of the structure along a reduct. The section law does not mention the operations, so only the projection changes.

    Section::is_representative

    fn[S, Q, A : Eq] Section::is_representative(self : Section[S, Q, A], a : A) -> Bool

    Whether a is the chosen representative of its class. On such results the lift agrees exactly with the operations of A.

    Section::lift

    fn[S, Q, A] Section::lift(self : Section[S, Q, A], q : Q) -> A

    The chosen representative of q.

    Section::normalize

    fn[S, Q, A] Section::normalize(self : Section[S, Q, A], a : A) -> A

    The normal form of a: the chosen representative of its class.

    Section::of_integral

    The canonical section of an integer type: proj is the canonical map BigInt -> Z given by FromInteger, and lift is Integral::normalize. The obligation sits on those instances: Z::from_integer(normalize(x)) ==x for every x. Use to_ring when Z is a ring.

    Section::postulate

    fn[S, Q, A] Section::postulate(proj : Hom[S, A, Q], lift : (Q) -> A) -> Section[S, Q, A]

    Trusts lift as a section of proj without proof.

    Proof obligation for the caller: proj.apply(lift(q)) == q for every q. The law makes proj surjective; proj carries its own Hom obligation. Back every call with a Section::check or Section::check_ops test.

    Section::proj

    fn[S, Q, A] Section::proj(self : Section[S, Q, A]) -> Hom[S, A, Q]

    The projection onto the quotient.

    Section::then

    fn[S, Q, A, B] Section::then(self : Section[S, Q, A], next : Section[S, A, B]) -> Section[S, Q, B]

    Composition: lift Q into A with self, then A into B with next. The projection is next.proj followed by self.proj.

    Section::to_add_group

    fn[Q : AddGroup + AddMonoid + Add + Zero + Neg + Sub, A : AddGroup + AddMonoid + Add + Zero + Neg + Sub] Section::to_add_group(self : Section[AddMonoidSig, Q, A]) -> Section[AddGroupSig, Q, A]

    Upgrades the projection along Hom::to_add_group.

    Section::to_ring

    fn[Q : Ring + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + Neg + Sub, A : Ring + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + Neg + Sub] Section::to_ring(self : Section[SemiringSig, Q, A]) -> Section[RingSig, Q, A]

    Upgrades the projection along Hom::to_ring.

    SemiringSig

    pub enum SemiringSig {
    }

    Signature tag: 0, 1, + and *.

    add_group_to_add_monoid

    let add_group_to_add_monoid : Reduct[AddGroupSig, AddMonoidSig]

    lift_to

    fn[S : Integral + Semiring + AddMonoid + Add + Zero + MulMonoid + Mul + One + FromInteger + FromNat, R : FromInteger + FromNat] lift_to(x : S) -> R

    Lifts x to its representative in ℤ, then maps it into R along the canonical map. This is a function, not a homomorphism: for a fixed-width source it is one only when the modulus of R divides that of S, as for Int64 -> Int. Use it to turn machine integers into exact or approximate numbers that are not mapped back.

    ring_to_add_group

    let ring_to_add_group : Reduct[RingSig, AddGroupSig]

    ring_to_semiring

    let ring_to_semiring : Reduct[RingSig, SemiringSig]

    semiring_to_add_monoid

    let semiring_to_add_monoid : Reduct[SemiringSig, AddMonoidSig]

    semiring_to_mul_monoid

    let semiring_to_mul_monoid : Reduct[SemiringSig, MulMonoidSig]