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.