あらすじ
Juliaのコンパイラの内部実装を読んでいくシリーズです。
シリーズ自体については
Type Inference
今回からは Julia の型推論について概観します。
今回は具体的な型推論アルゴリズムについて詳しく調べる前に、それ以外の部分について整理します。
Julia の型推論について学ぶためにこの記事を読むのはオススメしません。
もっと多くのことが、もっとわかりやすく、正確に書いてある文章があるからです。
勉強記録を読む感覚でお願いします。おそらく間違いがたくさんあるので見つけたら↓のコメント欄にお願いします。
もっと多くのことが、もっとわかりやすく、正確に書いてある文章があるからです。
勉強記録を読む感覚でお願いします。おそらく間違いがたくさんあるので見つけたら↓のコメント欄にお願いします。
もっと良い文章の例:
What is Type Inference?
まずは ( Juliaにおける ) 型推論とは何かを説明します。
Julia は動的型付けのプログラミング言語です。実行時に \( (変数, 場所) \) の型は定まります。
一方で、 Juliaコンパイラは、各コントロールフローにおける変数の型を実際に実行する前に可能な限り推論します。
それによって最適化─ 例えば多重ディスパッチで実際に呼び出すメソッドを静的に解決したりします。
さらに、Juliaの型推論は inter-procedural に行われていて、その関数の中で呼び出される関数にも飛んでいって解析を行います。
この辺どこまで潜るかのトレードオフは大変そうに見えますが、実際大変なようです。 [1]
Example
例えば
f(x) = 2x
という関数を考えます。これは、
x::Int
なら Int
が帰ってきます。julia> f(x) = 2x
f (generic function with 1 method)
julia> @code_typed f(2)
CodeInfo(
1 ─ %1 = Base.mul_int(2, x)::Int64
└── return %1
) =>
Int64
@code_typed
マクロで実際推論できているのがわかります。さらに
x::Float64
なら Float64
が帰ってきます。julia> @code_typed f(2.0)
CodeInfo(
1 ─ %1 = Base.mul_float(2.0, x)::Float64
└── return %1
) => Float64
推論できてますね。さらに、内部的には
mul_int
と mul_float
が使われています。ではもう少し意地悪な例を検討してみます。
julia> a = 2
2
julia> f(x) = a * x
f (generic function with 1 method)
julia> f(3)
6
グローバル変数
a
を定義して f(x) = a * x
とします。 f(3)
は 6 と正しく計算できていますが、julia> @code_typed f(2)
CodeInfo(
1 ─ %1 = Main.a::Any
│ %2 = (%1 * x)::Any
└── return %2
) => Any
と、
Any
となりました。 これは Main.a
の型を考慮した型推論は Julia は行わないためです。 (これがなぜかは分かりません。)さらに、出力をよく見るとこれまで特化した関数 (
mul_int
, mul_float
) が使われていたところが *
になっています。(
@code_typed
によって行われるものという意味で、) Julia の型推論プロセス全体は
引数の実際の型
⬇︎ から、
各処理における型を推論 (推測ではない)
⬇︎ して、
最適化を行う
ものと言えます。
How Julia's Type Inference Works (アルゴリズム以外)
まず、具体的な型推論アルゴリズムに入る前に、一旦読むべきところだけ整理します。
第 0 回で掲載した Julia の処理系の概観図を再掲します。

Julia の型推論は、 Lowering されて得た IR に対して行われます。
前回まででみたように IR は以下のようなものでした.
- マクロは全て展開済み
- ループなども分解されて、全て直列の命令に書き換えられている
型推論の「入力」はこれになります。
CodeInfo
という型のオブジェクトです。julia> ci = @code_lowered f(2)
CodeInfo(
1 ─ %1 = Main.a * x
└── return %1
)
julia> dump(ci)
Core.CodeInfo
code: Array{Any}((2,))
1: Expr
head: Symbol call
args: Array{Any}((3,))
1: GlobalRef
mod: Module Main
name: Symbol *
binding: Core.Binding
value: #undef
globalref: GlobalRef#= circular reference @-2 =#
owner: Core.Binding
value: * (function of type typeof(*))
globalref: GlobalRef
mod: Module Base
name: Symbol *
binding: Core.Binding
owner: Core.Binding#= circular reference @-1 =#
ty: #undef
flags: UInt8 0x07
ty: #undef
flags: UInt8 0x00
2: GlobalRef
mod: Module Main
name: Symbol a
binding: Core.Binding
value: Int64 2
globalref: GlobalRef#= circular reference @-2 =#
owner: Core.Binding#= circular reference @-1 =#
ty: Any
flags: UInt8 0x00
3: Core.SlotNumber
id: Int64 2
2: Core.ReturnNode
val: Core.SSAValue
id: Int64 1
codelocs: Array{Int32}((2,)) Int32[0, 0]
ssavaluetypes: Int64 2
ssaflags: Array{UInt32}((2,)) UInt32[0x00000000, 0x00000000]
method_for_inference_limit_heuristics: Nothing nothing
linetable: Array{Any}((1,))
1: Core.LineInfoNode
module: Module Main
method: Symbol f
file: Symbol REPL[19]
line: Int32 1
inlined_at: Int32 0
slotnames: Array{Symbol}((2,))
1: Symbol #self#
2: Symbol x
slotflags: Array{UInt8}((2,)) UInt8[0x00, 0x08]
slottypes: Nothing nothing
rettype: Any
parent: Nothing nothing
edges: Nothing nothing
min_world: UInt64 0x0000000000000001
max_world: UInt64 0xffffffffffffffff
inferred: Bool false
propagate_inbounds: Bool false
has_fcall: Bool false
nospecializeinfer: Bool false
inlining: UInt8 0x00
constprop: UInt8 0x00
purity: UInt16 0x0000
inlining_cost: UInt16 0xffff
と、こんな感じです。
型推論の本質パートは
typeinfer.jl
, abstractinterpretation.jl
などにあり、 typeinf
とその中身である _typeinf
などを見ると良いです。このあたりのフローはバージョン違いでかなり構造が変わっていました。初回記事に見ているコミットが載っているので確認してください。
なんやかんやあるのですが、 (え?) 最終的にはおそらく
abstract_call_*
関数たちが実際に型推論を行っているのだと思います。なんやかんやはメモ用の scrapbox にあります:
あまりにも中身がないですが、一応今回 具体的な型推論アルゴリズムについて詳しく調べる前に、それ以外の部分について整理する記事、なのでここまでです。
(毎記事頑張って中身を詰めることにすると全然 Publish されなくなってしまうので...)
次回は、 @aviatesk さんの解説記事を参考に実際の Julia の型推論のアルゴリズムについて見ていきます。
今日の一曲
[1] https://techblog.recruit.co.jp/article-912/