Is Julia lazy?

Hi everybody
Right now I use Julia for maths educational purpose. There’s a lot of subjects but I concentrate on linear algebra. Representation of real vector spaces by Floats of any kind isn’t convenient because some determinants which should be null are actually epsilon, and so on.
Exact computation occurs with the field of rationals or any finite field like Fp=Z/pZ where p is a prime number. These cases are better suited for teaching.
My question is contained in the following code . Instructions which lead to errors have been commented . if this matter is of any interest for you please uncomment and check by yourself.
Till now I find solutions for every case and I’m not stuck nowhere…
I simply would like to understand why, sometimes Julia forces me to do some extra-job:
Thanks for reading !

#generates model for field Z/pZ with prime integer p
macro Z(p)
    quote
        struct F_p
            x::Int
            function F_p(n::Int)#internal constructor
                r=n % $p
                if r>= 0
                    return new(r) # possible to use keyword 'new' only here
                else
                    return new($p+r) # because of the special definition of remainder in Julia 
                end
            end
        end
    end
end

@Z 5 # calling this macro with parameter 5 realizes construction of F_p=Z/5Z
#overloading standard operators, just a minimum for illustration of my request
Base.:+(k::F_p,h::F_p) = F_p(k.x+h.x)
Base.:*(k::F_p,h::F_p) = F_p(k.x*h.x)
Base.:-(k::F_p)=F_p(-k.x)
Base.:-(k::F_p,h::F_p)=F_p(k.x-h.x)
#basic use
K=[F_p(i) for i in 0:4] #the elements of the field
println(typeof(K)) # appears as a vector which can be used as an iterator
#the following is just cosmetic sugar
prettyprint(k::F_p)=print(k.x)
prettyprint(V::Vector{F_p})= map(k->print(k.x," "),V)
#let's give it a try
prettyprint(K);print("\n")
#so K is a vector with coordinates in Z/5Z
# since Julia knows how to add in F5 it can compute K+K
#let's try
prettyprint(K+K);print("\n")# result is correct
#the following is quite logically refused because Julia doesn't know how to multiply an integer by an element of Z/5Z
#prettyprint(2K)
#so try something else
two=F_p(2)
println(two) #just to make sure...
#Again the following
#println(2*two)
#fails !!!
#Julia pretends not to know how to multiply an int by a F_p which is true, 
#but C++ has more imagination finding a constructor taking an int as an argument 
#it will automatically promote an int to a F_p and apply internal F_p multiplication
# too difficult for Julia ?
#Nevertheless normally the following has meaning
#two*K
#but Julia answers that he doesn't know how to multiply a scalar by a vector although he does it very well, coordinates by coordinate for usual types Int, Float and so on.
#let's see an example with rationals
println(1//2*[0//1,1//1,2//1,3//1,4//1])
#so we must explain by a new overload
Base.:*(k::F_p,V::Vector{F_p}) = [k*h for h in V]
#and now
prettyprint(two*K); println("\n")
#gives exactly what was expected K+K
#isn't it possible to implement scalar multiplication of a vector with coordinates in any field ?
#and what about automatic promotion ?

This is another example of the same situation.
Julia, together with LinearAlgebra knows, by genes, how to add and multiply matrices with coefficients in a custom finite field. Good point !
But cannot multiply any matrix by a scalar and consequently cannot evaluate a linear combination of matrices.
OK, if we teach it’s possible.
Why some complex operations (product of matrices) are basically taken into account, and elementary ones (multiplication by scalar) ignored ?

using LinearAlgebra


#classe paramétrée pour représenter tous les corps Z/pZ

macro Z(p)
    quote
        struct F_p
            x::Int
            function F_p(n::Int)#constructeur interne
                r=n % $p
                if r>= 0
                    return new(r) # appel à new possible unqiuement dans le constructeur 'interne'
                else
                    return new($p+r) # à cause de la définition du reste en julia ...
                end
            end
        end
    end
end

@Z 5 # appel de la macro avec paramètre 5, construction de F_p=Z/5Z

K=[F_p(i) for i in 0:4] #le corps entier
#surcharge des opérateurs
Base.:+(k::F_p,h::F_p) = F_p(k.x+h.x)
Base.:*(k::F_p,h::F_p) = F_p(k.x*h.x)
Base.:-(k::F_p)=F_p(-k.x)
Base.:-(k::F_p,h::F_p)=F_p(k.x-h.x)
Base.string(k::F_p)=string(k.x)
nul(k::F_p)=k.x==0
# fin de la définition


function Base.:*(λ::F_p,M::Matrix{F_p})#produit d'une matrice par un scalaire
    m,n=size(M,1),size(M,2)
    R=copy(M)
    for i in 1:m,j in 1:n
        R[i,j]=λ*M[i,j]
    end
    return R
end

function printsimplif(M::Matrix{F_p})
    m,n=size(M,1),size(M,2)
    for i in 1:m
        for j in 1:n
            print(M[i,j].x);print(" ")
        end
        println("")
    end
    println("--------------")    
end

function main()
    A=[F_p(3) F_p(4) F_p(4); F_p(0) F_p(1) F_p(0);F_p(2) F_p(2) F_p(3)]
    B=[F_p(3) F_p(2) F_p(1); F_p(1) F_p(2) F_p(0);F_p(3) F_p(1) F_p(4)]
    println(typeof(A))
    println("matrice A")
    printsimplif(A)
    println("matrice B")
    printsimplif(B)
    println("matrice A+B")
    printsimplif(A+B)
    println("matrice A*B")
    printsimplif(A*B)
    println("2A+3B")
    printsimplif(F_p(2)A+F_p(3)B)
end

main()

Why would you expect this to work? You’ve only told julia how to multiply two numbers of type F_p, but 2 is not an F_p (and since you don’t subtype any of the available abstract number types, there’s no other method to fallback to). There’s nothing special about * or + or any of the other functions you’re overloading here.

In any case, why do you expect julia to automatically reach into your struct and “just know what you want the behaviour to be”, as it seems to be the case for C++?

This should be adding a method to Base.iszero instead.

5 Likes

From reading your post, it seems like you’re saying you would like F_p to behave like a number (unless I misunderstand something). If that’s the case, you have to tell julia that

struct MyType <: Number
    x::Int
end

m = MyType(2)

# minimal example
Base.:*(m::MyType, y::MyType) = MyType(m.x * y.x)

m * m == MyType(4) # true

Base.promote_rule(::Type{MyType}, ::Type{<:Integer})= MyType
Base.convert(::Type{MyType}, x::Integer) = MyType(Int(x))

2m == MyType(4) # true
m * [1,2,3]  == [m, 2m, 3m] # true

You just have to ask julia for what you want :slight_smile:


By the way, I think that rather than using a macro to vary p, you probably just want to create a general F_p parametric type with p as the parameter.

12 Likes

The relevant section of the docs can be found here:

https://docs.julialang.org/en/v1/manual/conversion-and-promotion/

3 Likes

I’m a bit surprised. Does C++ really create its own promotion rules, automatically, without the programmer specifying any, and without the types being placed in a hierarchy?

It’s not obvious to me that Int should be promoted to Zp, instead of the other way around. How would C++ decide that?

I also support making this a parametric type, Z{P}. This doesn’t look like a job for a macro.

1 Like

Thank you for your interesting answers. I’ll be very busy today outside, but as soon as I have some time I will read carefully each of them and answer.
I noticed already some interesting suggestions to write a better code.
Thanks again to you all and have a good day.
Gilles

2 Likes

Shouldn’t this be just

return new(mod(n, p))

?

You can use broadcast for this type of operations (denoted by a point)

julia> M = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4
julia> 2 .* M # of course, for a Matrix{Int}, the brodcast is not needed
2×2 Matrix{Int64}:
 2  4
 6  8

julia> M .* 2
2×2 Matrix{Int64}:
 2  4
 6  8

julia> 2 .+ M
2×2 Matrix{Int64}:
 3  4
 5  6

You can also do element wise multiplication

julia> M .* M
2×2 Matrix{Int64}:
 1   4
 9  16

The broadcast generate very efficient code, it will works in your case (as long as you defined the product between the scalar and your matrix elements)

2 Likes

Sorry, no !
please check this link

Yes, I know. I’m not at my computer, how is it different from what your code does?

Can you give me a simple example please ?
My parameter here, is not a type, it is a constant of type Int64. So I was looking for a solution ‘à la Python’ or ‘à la C++’ (classes with parameters) but what I found in Julia’doc about parametrized types, although interesting and useful doesn’t correspond to my case.
As far as I know Julia function can return instances of of a given struct but not struct themselves (Python can, Julia macros can).
Solutions based on ‘static variables’ (data belonging to the whole class, and not to instances) are difficult to find too. As I understood constants exist, accessible only by inner constructor but every instance has a copy. In any case this is not satisfactory because such constructor has to be rewritten every time. Examples I could find are not clear.
Of course if you want to avoid macros you can use global variables
this works ::

global p=5

struct F_p
    x::Int
    function F_p(n::Int)#internal constructor
        r=n % p
        if r>= 0
            return new(r) # possible to use keyword 'new' only here
        else
            return new(p+r) # because of the special definition of remainder in Julia 
        end
    end
end

println(F_p(11))

I refuse negative values, like in all good maths textbooks.

But that’s what mod does too.

You’re completely right , excuse me, the page which is linked tells stories.

for i in -10:10
    print(mod(i,5));print(" ")
end
result 
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 
So make it the simple  way, without macro without test using mod

global prime_caracteristic=5

struct F_p
global prime_caracteristic
x::Int
function F_p(n::Int)#internal constructor
return new(mod(n,prime_caracteristic))
end
end

println(F_p(11))

`

Sorry, no, but I have a complicated, messy example. Below, I implemented a lot of stuff, probably a lot of it is unwise, and in particular I am unsure if promoting general integers to Zp is a good idea. Implementing the Integer interface is not something I really know how to do, so it’s a bit of a mess.

I actually used two type parameters, because it seemed wasteful to use an Int64 to represent Z7, so you can use UInt8 for example.

But maybe you can take some of this and use it. Scroll to the bottom to see some usage examples:

struct Z{P, T<:Integer} <: Integer
    x::T
    function Z{P, T}(n) where {P, T}
        (isa(P, Integer) && P > 0) || error("Type parameter P must be a positive integer.")
        return new{P, T}(mod(n, P))
    end
end

Z{P, T}(z::Z) where {P, T} = Z{P, T}(z.x)
Z{P, T}(z::Z{P, T}) where {P, T} = z
(::Type{T})(z::Z) where {T<:Integer} = T(z.x)

@generated function Z{P}(x) where {P}
    inttypes = (UInt8, UInt16, UInt32, UInt64, UInt128)
    i = findfirst(typemax.(inttypes) .>= P)
    return :(Z{P, $(inttypes[i])}(x))
end


@generated function Base.show(io::IO, z::Z{P, T}) where {P, T}
    if P < 10
        sub = '₀' + P
    else
        sub = join('₀' .+ reverse(digits(P)))
    end
    return :(print(io, Int(z.x), $sub)) 
end

Base.typemax(z::Z) = typemax(typeof(z))
@generated function Base.typemax(::Type{Z{P, T}}) where {P, T}
    return :($(Z{P, T}(P - 1)))
end

Base.:+(a::Z{P, T}, b::Z{P, T}) where {P, T} = Z{P, T}(a.x + b.x)
Base.:-(a::Z{P, T}, b::Z{P, T}) where {P, T} = Z{P, T}(a.x - b.x)
Base.:-(a::Z{P, T}) where {P, T} = Z{P, T}(-a.x)
Base.:*(a::Z{P, T}, b::Z{P, T}) where {P, T} = Z{P, T}(a.x * b.x)
Base.div(a::Z{P, T}, b::Z{P, T}) where {P, T} = Z{P, T}(a.x ÷ b.x)
Base.rem(a::Z{P1, T1}, b::Z{P2, T2}) where {P1,T1,P2,T2} = Z{P1, T1}(a.x ÷ b.x)
Base.rem(a::Z{P, T}, b::Real) where {P, T} = Z{P,T}(rem(a.x, b))
Base.rem(b::Real, a::Z{P, T}) where {P, T} = rem(b, a.x)
Base.rem(a::X, ::Type{X}) where {X<:Z} = a

Base.:<(a::Z{P, T}, b::Z{P, T}) where {P, T} = (a.x < b.x)
Base.:<=(a::Z{P, T}, b::Z{P, T}) where {P, T} = (a.x <= b.x)

Base.promote_rule(::Type{<:Number}, ::Type{Z{P, T}}) where {P, T} = Z{P, T}
@generated function Base.promote_rule(::Type{Z{P1, T1}}, ::Type{Z{P2, T2}}) where {P1, T1, P2, T2}
    if P1 >= P2
        return :(Z{P1, T1})
    else
        return :(Z{P2, T2})
    end
end

Base.zero(::Type{Z{P, T}}) where {P, T} = Z{P, T}(0)
Base.one(::Type{Z{P, T}}) where {P, T} = Z{P, T}(1) 
Base.float(z::Z) = float(z.x)
Base.Integer(z::Z) = z
Base.length(r::UnitRange{<:Z}) = Int(last(r)) - Int(first(r)) + 1
Base.length(r::StepRange{X, X}) where {X<:Z} = div(Int(last(r)) - Int(first(r)), Int(step(r))) + 1


using Random
function Random.rand(rng::AbstractRNG, ::Random.SamplerType{Z{P, T}}) where {P, T}
    return Z{P, T}(rand(rng, T(0):T(P-1)))
    # return reinterpret(Z{P, T}, rand(rng, T(0):T(P-1)))  # does not work
end

The convenience constructor Z{P}() will find the most efficient representation, so Z{7}(21) will use UInt8, while Z{712}(8) will use UInt16.

One of the first things to do, for convenience, would be to define some aliases:

const Z5 = Z{5, UInt8}
const Z13 = Z{13, UInt8}

Now you can do

jl> Z13(7)
7₁₃

jl> Z13(17)
4₁₃

jl> Z13(7) + Z13(17)
11₁₃

or

jl> M = rand(Z13, 4, 5)
4×5 Matrix{Z13}:
 8₁₃   1₁₃   6₁₃   0₁₃  11₁₃
 6₁₃   6₁₃   4₁₃  12₁₃   6₁₃
 5₁₃  10₁₃  10₁₃   9₁₃   1₁₃
 5₁₃   7₁₃   2₁₃  12₁₃   2₁₃

jl> 2 .* M.^2
4×5 Matrix{Z13}:
 11₁₃  2₁₃  7₁₃  0₁₃  8₁₃
  7₁₃  7₁₃  6₁₃  2₁₃  7₁₃
 11₁₃  5₁₃  5₁₃  6₁₃  2₁₃
 11₁₃  7₁₃  8₁₃  2₁₃  8₁₃

jl> (2 + 3im) .* z
3×4 Matrix{Complex{Z13}}:
  9₁₃+7₁₃im    3₁₃+11₁₃im  11₁₃+10₁₃im  2₁₃+3₁₃im
 11₁₃+10₁₃im  10₁₃+2₁₃im   12₁₃+5₁₃im   5₁₃+1₁₃im
  2₁₃+3₁₃im   12₁₃+5₁₃im   11₁₃+10₁₃im  7₁₃+4₁₃im

You can do a lot of stuff, make ranges, etc. I dunno. Maybe you can use some of it.

I kind of liked the printing, by overloading the show function. Much easier than doing this prettyprint business.

PS: some of the @generated functions can just be normal functions, I did this just for performance, and it seemed right.

5 Likes

Yes as far as I remember I made intensive use of C++ from 1988 till 2008, and abandoned completely during these last 13 years. I’m pretty sure that if asked to multiply an Int by an F_p C++ will look for a F_p-constructor taking an Int as an argument and make automatic promotion by calling this constructor to perform multiplication inside F_p.
This is why I tried this which doesn’t seem natural to another reader. On one hand it’s not natural, on the other hand like we say in France “People want butter and money for butter as well…”
Fortunately nobody answered " If you like your C++ so much, what are you doing here ?".

But don’t you have to tell C++ which way the promotion goes?

Ah yes, this is a central point. You can use isbits data types as type parameters. That’s how Array{Int, 2} works, for example, 2 is a type parameter here.

Very interesting, thank you.
I will study this in detail for myself. I don’t think I will use it on my site, because for education I don’t take care about power, performance, elegance, I privilege ‘readability’ that’s why my first choice was Python.
Julia allows the same simple style with better performance.
As a rule, the better the code the more difficult to read.
For me programs are just a support for my lectures, practical jobs for students to study maths rules by translating them into a code.