[Julia] Holy trait 〜 共通の関数定義を気軽に記述しよう


[Julia Advent calendar 2019](https://qiita.com/advent-calendar/2019/julialang) の 9日目です。

「一度書いた関数を、別の型にも利用させる」手法である trait based dispatch あるいは Holy trait パターンを軽く解説します。

この記事は、blog記事 [The Emergent Features of JuliaLang: Part II - Traits](https://invenia.github.io/blog/2019/11/06/julialang-features-part-2/) の翻案です。Julia 公式ドキュメントの本項目 [trait-based dispatch]
(https://docs.julialang.org/en/v1.0/manual/methods/#Trait-based-dispatch-1) よりも説明が分かりやすく、ぜひ紹介したいと思いました。

以下の実行例は、Julia 1.1 による実行結果を示します。

```julia
julia> versioninfo()
Julia Version 1.1.1
Commit 55e36cc (2019-05-16 04:10 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin15.6.0)
  CPU: Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
```

# 「拡張可能」ではない関数

引数を一つとり、以下のように動作する関数を定義しましょう。
* 引数がタプルやベクトル（１次元配列）なら、それ自身を返します。
* 引数が数（スカラー）なら、1つの要素のベクトルを作って返します。

次のように、定義できます。
タプル型 `Tuple` とベクトル型 `AbstractVector` に対する挙動は同じなので、同じメソッド定義（`=` の右側）を繰り返し記述します。

```julia
julia> aslist1(x::Tuple) = x
       aslist1(x::AbstractVector) = x
       aslist1(x::Number) = [x]
```


関数 `methods(a)` を用いてメソッドを一覧しましょう。

```julia
julia> methods(aslist1)
# 3 methods for generic function "aslist1":
[1] aslist1(x::Tuple) in Main at REPL[2]:1
[2] aslist1(x::AbstractArray{T,1} where T) in Main at REPL[3]:1
[3] aslist1(x::Number) in Main at REPL[4]:1
```

では、関数の動作を確かめましょう。

```julia
julia> aslist1(1)          # スカラー
1-element Array{Int64,1}:
 1

julia> aslist1([1])        # ベクトル
1-element Array{Int64,1}:
 1

julia> aslist1([1,2])      # ベクトル
2-element Array{Int64,1}:
 1
 2

julia> aslist1((1.0,))     # タプル
(1.0,)

```

正しく動作していますね。

さて、文字列 `String` に対しても、タプルまたはベクトルと同じように振る舞うようにしましょう。`String` に対しても、`Tuple` と同じ定義（`=` の右側）を繰り返し記述することになります。

```julia
julia> aslist1(x::String) = x
aslist1 (generic function with 4 methods)

julia> methods(aslist1)
# 4 methods for generic function "aslist1":
[1] aslist1(x::String) in Main at REPL[10]:1
[2] aslist1(x::Tuple) in Main at REPL[2]:1
[3] aslist1(x::AbstractArray{T,1} where T) in Main at REPL[3]:1
[4] aslist1(x::Number) in Main at REPL[4]:1

julia> aslist1("abc")
"abc"
```

なお、この例で、タプル引数とベクトル引数のメソッド定義を一つにまとめるためには、それらの共用型（型ユニオン Type Union) を使ってもよいでしょう。

```julia
julia> aslist2(x::Number) = [x]
       aslist2(x::Union{AbstractVector,Tuple}) = x  # <=

julia> aslist2([1])
1-element Array{Int64,1}:
 1

```

しかし、別の型の引数に同じ機能を持たせるには、上の `String` 型の例のように、メソッド定義をやはり繰り返す必要があります。
すなわち、ここまで定義した関数 `aslist1`、`aslist2` はどちらも、「拡張可能（extensible）」ではありません。

この例では、簡単なメソッド定義を繰り返すのは容易ですが、定義が複雑になると、記述の誤りも起こりうるでしょう。


# 拡張可能な関数を書く 〜 Holy trait

では、trait パターンを用いて、「拡張可能な」関数を書いてみましょう。

まず、関数の挙動を整理し、それぞれの挙動に対応する型を定義します。トレイツ型 trait type と呼ばれます。

例題では、二通りの挙動があります。リストのような挙動と、そうでない挙動です。それぞれに `List`, `NoList` という型を与えます。


```julia
julia> struct List end
       struct Nonlist end
```

次に、引数の型から、トレイツ型のインスタンスを返す関数を定義します。トレイツ関数 trait function と呼ばれます。

例題のトレイツ関数は、こうなります。
実引数の型のみが必要なので、仮引数の並びは `(::T)` と書かれています。
式 `T()` は、型 `T` のインスタンスを作ります。

```julia
julia> islist(::AbstractVector) = List()
       islist(::Tuple) = List()
       islist(::Number) = Nonlist()
```

```julia
julia> methods(islist)
# 3 methods for generic function "islist":
[1] islist(::AbstractArray{T,1} where T) in Main at REPL[20]:1
[2] islist(::Tuple) in Main at REPL[21]:1
[3] islist(::Number) in Main at REPL[22]:1
```

最後に、各々のトレイツ型（のインスタンス）に対して、その挙動を定義します。
ユーザが呼び出す関数は、引数からトレイツ型を得て、そのトレイツ型に対応する挙動を、引数とともに呼び出すように定義します。 ２つ目に呼び出すメソッドを trait を用いて決めるので、trait-based dispatch というわけです。

 
例題は、以下のように整理されました。
ユーザが呼び出すのは、引数１つのメソッドです。その引数をトレイツ関数 `islist()` に渡してトレイツ型を得ます。トレイツ型と、元の引数で、引数２つのメソッドを呼出します。引数２つのメソッドが、各トレイツ型に対する挙動を定義します。

```julia
julia> aslist(x) = aslist(islist(x), x)
       aslist(::List, x) = x
       aslist(::Nonlist, x) = [x]
```

```julia
julia> methods(aslist)
# 3 methods for generic function "aslist":
[1] aslist(::List, x) in Main at REPL[26]:1
[2] aslist(::Nonlist, x) in Main at REPL[27]:1
[3] aslist(x) in Main at REPL[25]:1
```


動作を確認しましょう。

```julia
julia> # スカラー
       islist(1)
Nonlist()

julia> aslist(1)
1-element Array{Int64,1}:
 1

julia> # 数の配列
       islist([1,2])
List()

julia> aslist([1,2])
2-element Array{Int64,1}:
 1
 2
```

どちらも、題意の挙動が得られました。

さて、このようにしておけば、別の型に対応させることも簡単です。その型に対するトレイツ関数を用意するだけです。
上の例のように、`String` 型を、配列同様に振る舞わせるには、こうします。

```julia
julia> # 文字列
       islist(::String) = List()

julia> islist("abc")
List()

julia> aslist("abc")
"abc"
```

ところで、「トレイツ関数」を追加すると、間接コスト（オーバーヘッド）を増やす恐れがあります。
関数 `@code_typed` でコンパイル結果を表示させてみましょう。
ベクトルの引数を与えた場合のコンパイル結果は、実に、こうなります！！

```julia
julia> @code_typed aslist([1,2])
Body::Array{Int64,1}
1 ─     return x
```

トレイツ関数 `islist(x)` は消化されて、なくなってしまいました。引数を、そのまま返します。

引数に数を与えた場合のコンパイル結果は、こうなります。

```julia
julia> @code_typed aslist(1)
Body::Array{Int64,1}
1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Array{Int64,1}, svec(Any, Int64), :(:ccall), 2, Array{Int64,1}, 1, 1))::Array{Int64,1}
│        (Base.arraysize)(%1, 1)
└──      goto #3 if not true
2 ─      (Base.arrayset)(false, %1, x, 1)
3 ┄      goto #4
4 ─      goto #5
5 ─      return %1
```


少しわかりにくいですが、配列をメモリ確保して、引数の値を書き込んでいます。つまり、この場合も、トレイツ関数 `islist(x)` は消化されて、消えてしまいました。

というわけで、「トレイツ関数」の追加は、間接コストとはならないでしょう。Julia の最適化コンパイラの威力ですね。

# Julia の中のトレイツ

「拡張可能な関数」の発端は、[StridedArray should be an abstract class, not a union](https://github.com/JuliaLang/julia/issues/2345) 「StridedArray（筆者注：飛び飛びにアクセスされる配列、例えば画像）を拡張可能にするには、共用体にしてはいけない」という issue です。これを指摘した Tim Holy 先生は、上で紹介した実装を提案しています。そこで、この手法は Holy Trait と呼ばれています。


上の例では、引数１つの場合を示しましたが、Julia 公式ドキュメントの項目 [trait-based dispatch]
(https://docs.julialang.org/en/v1.0/manual/methods/#Trait-based-dispatch-1) には、２引数の関数に適用する例が紹介されています （それを、`map` に渡しているので、更に分かりにくいのですが）。 

Julia の基本ライブラリにも Holy trait が用いられています。
拙記事（[[逆引きJulia] 配列要素の参照、色々](https://qiita.com/tenfu2tea/items/e75559414ba7713b1f2d) ）で紹介しましたが、多次元配列の要素の添字指定には、２種類の書き方があります。列毎の添字を書くデカルト添字記法 `IndexCartesian` と、連番の添字を書く線形添字記法 `IndexLinear` です。そこで、（多次元）配列の型を定義した場合には、どちらを使うかを指定することになっています。`Base.IndexStyle` がトレイツ関数です。（既定は `IndexCartesian` なので、実際に指定すべきは `IndexLinear` とする場合のみですが。）


```julia
Base.IndexStyle(::Type{<:MyArray}) = IndexLinear()
```

# 動的なトレイツ関数

上の例では、引数の型からトレイツ型を決めました。

値がリストとして振る舞うか否かを、「その値の型が `iterate` メソッドを有するか否か」で判定してもよいでしょう。型 `T` がメソッド `iterate(::T)` を持つか否かは、 `hasmethod(iterate, Tuple{T})` で判定できます。
これを用いて、例題のトレイツ関数は、以下のように書けます。

```julia
julia> islistD(T) = hasmethod(iterate, Tuple{T}) ? List() : Nonlist()

julia> aslistD(x::T) where T = aslistD(islistD(T), x)
       aslistD(::List, x) = x
       aslistD(::Nonlist, x) = [x]
```

`AbstractArray` や `String` は `iterate` メソッドを持つので、上の例と同様に動作します。

```
julia> aslistD(1)
1

julia> aslistD([1])
1-element Array{Int64,1}:
 1

julia> aslistD("abc")
"abc"
```

しかし、現行の Juliaでは、上のような「動的な」トレイツ関数は、最適なコンパイル結果を与えません （`@code_warntype aslistD([1])` を試してください)。 しかし、`hasmethod`を用いたトレイツ関数も静的にコンパイルできるようになると予告されています → [WIP: Make `hasmethod` able to be used for static dispatch](https://github.com/JuliaLang/julia/pull/32732)


# 終わりに

他のオブジェクト言語をご存じの方は、trait が、（C++ などの）多重継承や、Ruby のミックスイン (mix-in)に相当することを見抜いたでしょう。

Julia では、柔軟な型と多重ディスパッチを用いて、特別な構文を用いずに記述できます。しかも、静的トレイツ関数ならオーバーヘッドもありません。もっと気軽に書いてみましょう。


この記事を投稿したのは、12月22日の夜です。
Julia ソースの中に隠れている Holy trait を数えながら、聖なる夜 Holy night を迎えましょう。