Julia Benefits from Tagless Final¶
It’s an article written extremely casually, and very short.
What Happened Today?¶
Today I found someone in Julia discourse asked me some questions about ADT encoding in Julia.
About the performance issues with Julia structures and subtyping for ADT emulations, I said it’s impossible to address.
Yes, it’s impossible for Julia to have fast ADTs, so far.
However, we have an alternative, to achieve everything that ADTs can achieve, in Julia.
It’s called tagless final.
There’re many resources about tagless final: http://okmij.org/ftp/tagless-final .
As Julia cannot encode ADTs/GADTs perfectly, with tagless final, the problem just gets eased.
An Example Turns Out to be Type Unstable¶
abstract type Expression end
struct Const <: Expression
value :: Int
end
struct Add <: Expression
lhs :: Expression
rhs :: Expression
end
evaluate(e::Const) = e.value
evaluate(e::Add) = evaluate(e.lhs) + evaluate(e.rhs)
@code_warntype evaluate(Add(Const(2), Const(3)))
Input above code in Julia shell, you got “a big piece of red”, which means type unstable(it’s just what @code_warntype
does).
Above code is an emulation of ADTs, and ADT approach is called initial approach in the research of tagless final.
We can have the final approach, which turns out to be superior in Julia.
Tagless Final Encoding about Above Code¶
struct SYM{F1, F2}
constant :: F1
add :: F2
end
function constant(v)
function (sym::SYM)
sym.constant(v)
end
end
function add(term1, term2)
function (sym::SYM)
sym.add(term1(sym), term2(sym))
end
end
# self algebra
self = SYM(constant, add)
evaluate =
let constant(v::Int) = v,
add(l::Int, r::Int) = l + r
SYM(constant, add)
end
@code_warntype add(constant(2), constant(3))(evaluate)
All in blue, all in blue, type stable all in blue!
How could you get the full mechanisms of turning ADTs to tagless final?
If you understand Haskell, you shall read First-class Pattern Matching in the Final Approach.
Otherwise, learn ocaml and go to Oleg-sensei’s website.