Before getting started in Julia, I did most of my work in Haskell. It’s a great language, but a few things kept causing me trouble:
- The strong PL focus of the community was great, but it seemed to come at a cost of concern about numerical algorithms. I really need both.
- The type system is amazing, but PPL tends to push this to its limits. Doing anything new seemed to turn into a type theory research effort, which isn’t really my thing.
- There’s a “Template Haskell” for metaprogramming, but it’s not very integrated into the language itself, it’s not type-safe, and its use is often discouraged.
I feel like moving to Julia has mostly solved these problems. (1) has just been amazing. For (2), Julia’s type system isn’t quite as expressive as Haskell’s, but for the most part it seems helpful without being so constraining. And generated functions seemed to entirely solve (3).
From my experience using Haskell, I came to see the best way to get performance as “get as much information to the compiler as possible”. Types are the way to do this. The compiler is required to figure out the types before execution, so we can be sure the result is known statically. It’s just beautiful.
In Julia, my need for staged compilation led me to learning about generated functions. These are just amazing. The type system isn’t quite as powerful, but with generated functions you can pass information to the compiler much more directly. “When you see these types, generate this code”. Until relatively recently, I viewed this as a way to help the compiler. It still has the same job to do, but you get the chance to give it a push in the right direction. This is a huge amount of control, and I found it really elegant.
Recently – maybe in the last year or so – I’ve been hearing a lot of pushback against this idea. I hear a lot of talk about the optimizer and constant propagation, and recommendations to avoid using the type system too much.
This is kind of disheartening, in part because it breaks my mental model, but also because it doesn’t offer a replacement. The optimizer seems very magical and difficult to reason about. I’ve always understood staged compilation to require generated functions, which in turn requires types. But now, I’m really not sure what to think. We have some information in the types and some in the optimizer. It’s not at all clear what goes where. And we can program on types, but I’ve never seen a way to query the optimizer. And the only way I see of enforcing constraints on the optimizer is @assume_effects
. That seems interesting, but it’s very new, it’s not clear how robust it is, and it comes with this:
│ Warning
│
│ Improper use of this macro causes undefined behavior (including crashes, incorrect answers, or
│ other hard to track bugs). Use with care and only if absolutely required.
Here’s an example of the kind of thing I’m doing, adapted from KeywordCalls.jl:
julia> @generated function keysort(nt::NamedTuple{K}) where {K}
sorted_K = tuple(sort(collect(K))...)
:(NamedTuple{$sorted_K}(nt))
end
keysort (generic function with 1 method)
julia> keysort((b=1, a=2))
(a = 2, b = 1)
Because of the way this is set up, we can guarantee that the sort
happens at compile time. Here’s how the compiler handles it:
julia> @code_typed keysort((b=1, a=2))
CodeInfo(
1 ─ %1 = Base.getfield(nt, 2)::Int64
│ %2 = Base.getfield(nt, 1)::Int64
│ %3 = %new(NamedTuple{(:a, :b), Tuple{Int64, Int64}}, %1, %2)::NamedTuple{(:a, :b), Tuple{Int64, Int64}}
└── return %3
) => NamedTuple{(:a, :b), Tuple{Int64, Int64}}
Just beautiful. For Soss and Tilde, I do this sort of thing all over the place. Models are lifted to the type level, and “primitives” generate code specialized for a particular model.
This can sometimes get tricky, but luckily there are libraries to support this style. MLStyle.jl is great for manipulating ASTs, and GeneralizedGenerated.jl lets you extend generated functions to allow closures, along with some utilities for more easily lifting things to the type level.
There’s lots more of this. In measure theory, we often define a measure in terms of a log-density over another measure. That second measure is the base measure. So for example,
julia> basemeasure(Normal())
0.3989 * Lebesgue(ℝ)
julia> typeof(ans)
WeightedMeasure{Static.StaticFloat64{-0.9189385332046728}, Lebesgue{MeasureBase.RealNumbers}}
Here we have a Float64
represented as the type-level, using Static.jl. This has to be static so we can do things like
julia> m = For(1:10) do j
Normal(j, 1)
end
For{Normal{(:μ, :σ), Tuple{Int64, Int64}}}(j->Main.Normal(j, 1), (1:10,))
julia> basemeasure(m)
0.0001021 * For{Affine{(:σ,), Lebesgue{MeasureBase.RealNumbers}, Tuple{Int64}}}(#13, (1:10,))
MeasureTheory.jl recognized that the components of m
have base measures of the same type. That happens to be a singleton type, so we know the base measures are exactly the same. Because of this, we can factor out the constant, making things much more efficient.
The point is, I’ve built up lots of infrastructure around this approach. It may be that somehow using the optimizer for this could work better, but it’s not at all clear to me what that would look like. In contrast, the current approach is very clear and concrete.
Hearing suggestions like “avoid types” or “avoid generating functions” leave me a little worried about the future of this approach and Julia’s support for it. I’d appreciate any guidance on where things are going, the role of generated functions compared to that of the optimizer, and what it even means to get the optimizer to help in situations like the ones I’ve described.