Help me refine my blog post introducing the value type

Wenjie · August 21, 2018, 11:19pm

I am amazed by the value type in Julia and hence wrote a blog post about it. During the writing, some idea came to my mind, and I’ll express it as follows.

I want to define the root function in a weird way

root( x::Float64, ::Val{n} ) where n

which calculates x^{1/n}.

This allows me not only to generate one piece of machine code for each integer n, but also to define some weird root methods, such as “cat root” and “dog root”:

root( x::Float64, ::Val{:cat} ) = "Meow"
root( x::Float64, ::Val{:dot} ) = "Bark"

Then I can call

root(2.0, Val(a))

which will be dispatched differently according to the value of a.

Although flexible, it still has some limitation. In the first method, if root has different behaviors for Integer n and AbstractFloat n, or for positive n and negative n, is it possible to dispatch accordingly, say, by

root( x::Float64, ::Val{n} ) where {n::Integer}
root( x::Float64, ::Val{n} ) where {n::AbstractFloat}

root( x::Float64, ::Val{n} ) where {n::Integer > 0}
root( x::Float64, ::Val{n} ) where {n::Integer < 0}

?

I am conscious that similar use cases may be rare. So, is it actually a good idea, or I overstretched?

My blog post can be found here.

stevengj · August 22, 2018, 2:09am

Most of the utility of Val occurs when you can use Val{x}() with x known at compile-time (either because it is a literal constant or because it comes from another compile-time value like a type parameter). Then the compiler choses the correct method to call based on x and there is no runtime cost.

If you call Val(x), you are relying on runtime dispatch, which is much slower, so it is only worthwhile if there is a big advantage to specializing the function on the argument value.

There is a cute (but not very practical) Val example here (from a lecture by @jeff.bezanson): Jupyter Notebook Viewer?

JeffreySarnoff · August 22, 2018, 2:39am

The better way to define Int_root_ofa_Float64 is:
root(x::Float64, n::Int) = x^inv(n)
because you do not really want to dispatch differently for each value of n.

julia> root(x::Float64, n::Int) = x^inv(n)

julia> root(x::Float64, n::String) = root(x, Val(Symbol(n)))

julia> root(x::Float64, n::Val{:cat}) = string(x,"^(1/meow)")

julia> root(2.0, 2)
1.4142135623730951

julia> root(2.0, "cat")
"2.0^(1/meow)"

It is bad practice to use many Val typed values for selective dispatch (just as you would avoid defining the_one_true_function(x::T) where {T}).

Julia’s multiple dispatch is a more powerful and flexible tool than single dispatch. Coupled with the value type, multiple dispatch can handle infinite use cases with one single function.

To have infinite dispatch paths is disrecommended .

Wenjie · August 22, 2018, 11:40am

Thanks for the reply, but I still have some doubt. Let’s forget the underlying meaning of root and just consider it as a function. I’ll explain it in two points.

The reason of this convoluted definition

You have already defined some methods like

root(x::Float64, n::Val{:cat}) 
root(x::Float64, n::Val{:dog}) 
root(x::Float64, n::Val{true}) 
root(x::Float64, n::Val{false})

and you have code depending on that — root(2.0, Val(a)) with finite possibilities of a.

Now you want to extend the function to Integer without refactoring the current code, it seems that the only way to go is to define

root(x::Float64, ::Val{n}) where n

This works, except that you can no longer extend it to float point values. That’s why I suggested the following language features:

root( x::Float64, ::Val{n} ) where {n::Integer}
root( x::Float64, ::Val{n} ) where {n::AbstractFloat}

I admit that your design may be more elegant, but it needs to refactor the code, whereas my approach provides a quick fix.

Infinite possibilities but with finite dispatch paths

root(x::Float64, ::Val{n}) where n can handle infinite possibilities, but it does not necessarily generate infinite actual dispatch paths. If each client has several (but different) values of n, it won’t be too different from functions with finite dispatch paths.

Let’s say, you write this function for many potential clients. Client A has use cases n \in \{1, 0, -1, \text{:cat} \}, Client B has use cases n \in \{2, 0, -3, \text{:dog} \}… And you cannot foresee all these use cases.

Your solution obviously still works, but I don’t see any problems of my approach in this scenario.

Edit: longer → no longer

fabiangans · August 22, 2018, 11:41am

Note also that in the past there were different attempts at implementing this, one I can remember is this package

which seems to be abandoned. I don’t know if there is a maintained package for pattern dispatch, but it might be intersting to look at if you like the idea of dispatching on values.

waldyrious · August 22, 2018, 1:28pm

There’s been some related discussion here: The relation between pattern matching and multiple dispatch

Tamas_Papp · August 22, 2018, 2:20pm

Some quick remarks:

Val types are nothing special, the same pattern applies to parametric (singleton) types.
One of the key features of Julia is achieving performance by optimizing code for parametric concrete types. Using Val{something} hooks into this mechanism. Note, however, that there is a trade-off between compile and runtime, and, unless the user-facing API expects Val types, the entry points will not be type stable. Val & friends are usually worth it when they pass through a chain of functions, ending up in a specialized implementation.
Also, v1.0 can propagate and fold constants in some cases, so you no longer need to rely on this pattern as extensively as before. I would recommend optimization and benchmarking, and only using Val and similar if absolutely needed.
If the purpose of blog posts is disseminating useful hints to a general audience, I would not talk about Val types. It is good to know that they exist, especially for developers, but for users they may just be confusing.
If you feel you still want to write a blog post, it would be good to have a real-world example instead of root(::Float64, ::Val{:cat}). Also, ::Float64 is almost surely overspecialization, I hope other <: Real types have Val{:cat} roots, too.

Wenjie · August 24, 2018, 11:50am

Upon reading the information provided by @fabiangans and @waldyrious , I understood the difference between type dispatch and pattern dispatch. However, I didn’t find any concept similar to pattern dispatch in other languages (e.g. C++). Is this thing exclusive to Julia? I tried to search for it on Google but didn’t get anything sensible.

JeffreySarnoff · August 28, 2018, 10:59pm

You could look at Icon, Prolog for examples of using syntactic patterns to guide the flow of control in a program.

fyi here is one appropriate use of Val types (from Base)


# Core.Compiler has complicated logic to inline x^2 and x^3 for
# numeric types.  In terms of Val we can do it much more simply.
# (The first argument prevents unexpected behavior if a function ^
# is defined that is not equal to Base.^)
@inline literal_pow(::typeof(^), x::HWNumber, ::Val{0}) = one(x)
@inline literal_pow(::typeof(^), x::HWNumber, ::Val{1}) = x
@inline literal_pow(::typeof(^), x::HWNumber, ::Val{2}) = x*x
@inline literal_pow(::typeof(^), x::HWNumber, ::Val{3}) = x*x*x

fabiangans · August 29, 2018, 6:36am

Rust has some very advanced mechanism for pattern matching The match Control Flow Operator - The Rust Programming Language but their match does not really resemble pattern method dispatch, but is rather a normal control flow operator, similar to GitHub - kmsquire/Match.jl: Advanced Pattern Matching for Julia

Wenjie · September 1, 2018, 1:57am

I see. Square and cube have more efficient implementation, and this is also why, in Python, x**2**2 is much faster than x**4.

BTW, several lines (Line 230) above the code you quoted read

# x^p for any literal integer p is lowered to Base.literal_pow(^, x, Val(p))
# to enable compile-time optimizations specialized to p.
# However, we still need a fallback that calls the function ^ which may either
# mean Base.^ or something else, depending on context.
# We mark these @inline since if the target is marked @inline,
# we want to make sure that gets propagated,
# even if it is over the inlining threshold.
@inline literal_pow(f, x, ::Val{p}) where {p} = f(x,p)

Does it generate infinite dispatch paths? If so, does the @inline help reduce the infinite dispatch paths?

JeffreySarnoff · September 1, 2018, 9:38am

To clarify, where you thought I was saying “Inartfully parameterized functions may allow for any number of distinct realizations, each with its own specialized dispatch path; and opening the door to infinite dispatch specialization is bad practice.”
I was not. My focus specific to the use of Val types because in most running software there is a relatively small number of distinct types and relatively large number of distinct values.

The comment you cite notes “optimizations… specialized to [the p in Val(p)].” Looking below that comment, those optimizations are given in the four lines that start @inline literal_pow … and the four ps specialized are x^0, x^1, x^2, x^3.
There are no other specializations over x^p for other nonnegative integers p.

The part about using @inline with those four literal_pow methods basically means “If you write @inline myfunction(x) ... y = x^2 .. end the call evaluating x^2 should be expanded inline within myfunction.”