Parametric type (new struct) whose parameter is a constant of a specific type?

General Usage
1

I wish to create an efficient type for integers modulo m. Yes, I do realize there are several existing ones out there, but I wish to have my own, and perhaps squeeze a bit more performance out of it.

I’ve already achieved this in this GitHub issue.
But I wish to further improve on this. Observe the code:

abstract type AbstractModInt <: Number end;
struct Mod8{m} <:AbstractModInt  where {m<:UInt8}  # m=modulus is a concrete value; during runtime it is not checked that m is of type UInt8
    val ::UInt8 
    function Mod8{m}(val ::tw) where {m, tw<:UInt8}
        return new{m}(mod(val,m)) end end;

It allows creating Mod8{UInt8(5)}, but also Mod8{Int(5)}, Mod8{Int}, ..., which is not what I wanted. How can I have a constant m::UInt8 as the type parameter, which is checked only at compile time, not at run time?

I’ve noticed there’s Val{m}, but am unsure how to use it.

2

Taking your question literally (how to constrain the value of a type parameter to some type?), the answer is you can’t, at least currently.

Your goal can be accomplished, though, by encoding m using a Zermelo ordinal-like construction (@Sukera). E.g., this is a recent piece of code of mine for representing natural numbers in the type domain, inspired by Zermelo ordinals:

module TypeDomainNaturalNumbers

module Internals
    export Internal
    struct Internal end
end

module TupleTail
    export tuple_tail
    function vararg_tail((@nospecialize ::Any), @nospecialize r...)
        r
    end
    function tuple_tail(@nospecialize t::Tuple{Any,Vararg})
        vararg_tail(t...)::Tuple
    end
end

export NonnegativeInteger, PositiveInteger, natural_successor, natural_predecessor, natural_tuple_length

abstract type AbstractNonnegativeInteger end

"""
    NonnegativeInteger

Nonnegative integers in the type domain.

The implementation is inspired by the Zermelo construction of the natural numbers.
"""
struct NonnegativeInteger{
    Predecessor<:Union{Nothing,AbstractNonnegativeInteger},
} <: AbstractNonnegativeInteger
    predecessor::Predecessor
    function NonnegativeInteger{P}(::Internal, p::P) where {P}
        new{P}(p)
    end
end

"""
    PositiveInteger

Positive integers in the type domain.
"""
const PositiveInteger = let t = NonnegativeInteger
    t{<:t}
end::Type{<:NonnegativeInteger}

"""
    natural_successor(::NonnegativeInteger)

Return the successor of a natural number.
"""
function natural_successor(o::NonnegativeInteger)
    NonnegativeInteger{typeof(o)}(Internal(), o)::PositiveInteger
end

"""
    natural_predecessor(::PositiveInteger)

Return the predecessor of a nonzero natural number.
"""
function natural_predecessor(o::PositiveInteger)
    o.predecessor::NonnegativeInteger
end

function (::Type{NonnegativeInteger})()
    NonnegativeInteger{Nothing}(Internal(), nothing)
end

function Base.zero(::Type{NonnegativeInteger})
    NonnegativeInteger()
end

function to_int(@nospecialize o::NonnegativeInteger)
    if o isa PositiveInteger
        let p = natural_predecessor(o), t = @inline to_int(p)
            t::Int + 1
        end
    else
        0
    end::Int
end

function Base.convert(::Type{Int}, o::NonnegativeInteger)
    to_int(o)
end

function from_val(::Val{N}) where {N}
    Vararg{Any,N}
    if N === 0
        NonnegativeInteger()
    else
        let v = Val{N - 1}(), p = @inline from_val(v)
            natural_successor(p::NonnegativeInteger)
        end::PositiveInteger
    end::NonnegativeInteger
end

function from_int(n::Int)
    Vararg{Any,n}
    if n === 0
        NonnegativeInteger()
    else
        from_val(Val{n}())
    end::NonnegativeInteger
end

function Base.convert(::Type{NonnegativeInteger}, n::Int)
    from_int(n)
end

"""
    natural_tuple_length(::Tuple)

Return a nonnegative integer which is the length of the given tuple.
"""
function natural_tuple_length(@nospecialize t::Tuple)
    if t === ()
        NonnegativeInteger()
    else
        let a = tuple_tail(t), b = @inline natural_tuple_length(a)
            natural_successor(b::NonnegativeInteger)
        end::PositiveInteger
    end::NonnegativeInteger
end

end

Then you could do something like this for your own type:

struct Mod8{M<:NonnegativeInteger}
    val::UInt8
end

Then you can convert M to Int or UInt8 or whatever as needed. Technically you could also constrain M to be less than 256 by constraining it with a big Union of NonnegativeInteger subtypes, however I guess this would make Julia’s subtyping really slow.

1 Like
3

Uhm, I’m a bit lost in your code, I don’t understand what all modules have to do with my modular integers? Isn’t module used to isolate namespaces and create packages, precompile them, …

Could you post a MWE on how my type could be implemented, pls? Or is all of the above code necessary?

1 Like
4

Your problem is the fact that in Julia it’s currently not possible to constrain non-Type type parameters. My proposal is to work around this by encoding the nonnegative integer value (m) as a type (M). I expect that you probably don’t want to bother with implementing this while you’re still a newbie, but perhaps you like this as food-for-thought.

1 Like
5

You can always do something like the following:

struct Mod8{m}
    val::UInt8 
    function Mod8(m::UInt8, val::UInt8)
        new{m}(val)
    end
end

Now you can only make a Mod8{m} with m::UInt8 because this is what is returned by the inner constructor.

Then of course you can add more constructors for convenience, such as:

function Mod8(m::Integer, val::Integer)
    Mod8(convert(UInt8, m), convert(UInt8, val))
end
2 Likes