JuliaSyntaxを手探る
皆さんはjuliaという言語をご存知でしょうか？juliaは数値計算でよく用いられる言語で、Pythonのような書きやすさを持ちつつ、C言語のように高速に処理を実行することができるという夢のような言語です。
今回はそんなjuliaの公式が出しているJuliaSyntax(https://github.com/JuliaLang/JuliaSyntax.jl )という、juliaの構文解析を行うライブラリを改造してみました。
レポジトリは→(https://github.com/doss-eeic/2024-04-julia)
JuliaSyntaxとは
JuliaSyntaxの使い方を簡単に説明します。次のような何の変哲もないコードをJuliaSyntaxのparseall関数にかけてみます。
julia> using JuliaSyntax
julia> code = """
a = 1 + 2
if a == 3
a = 2
end
"""
"a = 1 + 2\nif a == 3\n a = 2\nend\n"
julia> ast = parseall(SyntaxNode, code)
line:col│ tree │ file_name
1:1 │[toplevel]
1:1 │ [=]
1:1 │ a
1:5 │ [call-i]
1:5 │ 1
1:7 │ +
1:9 │ 2
2:1 │ [if]
2:3 │ [call-i]
2:4 │ a
2:6 │ ==
2:9 │ 3
2:10 │ [block]
3:5 │ [=]
3:5 │ a
3:9 │ 2
するとこのようにcodeの抽象構文木を作成してくれます。
ここで少し注意したいのは、"1 + 2"のパース結果の部分です。ここでは親が[call-i]であり、子は1、+、2の３つといった構成になっています。よくある抽象構文木の説明においては親が+で子が1、2といったことが多いかと思いますが、JuliaSyntaxにおいては+や&などの二項演算は全て[call-i]という親で抽象化されています。
そして、今回行った改造はこのようにパースしてくれるJuliaSyntaxに対して型チェックを行ってくれるJuliaTypeCheckというものを実装しました。先ほどのcodeをJuliaTypeCheckにかけてみると次のようになります。
julia> JuliaTypeCheck.codetest(code)
[toplevel]
[=]
a ::Int
[call]
1
[+]
2
[if]
[call]
a ::Int
[==]
3
[block]
[=]
a ::Int
2
このように変数や後程見ますが関数、構造体などに対して型を自動でアノテーションしてくれ、また文法的におかしなところがあれば簡易的ではありますがエラーを出力してくれるようになっています。
JuliaTypeCheck全体の構造
JuliaTypeCheckでは型アノテーションを行うにあたって大きく分けて3つの重要な構造体、EXPRとBindingとScopeになります。これらの役割について一つずつ説明していこうと思います。
1. EXPR構造体
これはexpression(式)を表す構造体で、JuliaSyntaxが生成した構文木の一つのノードにつき一つのEXPRが対応しています。構造体の具体的な構造は次のようになっています。
mutable struct EXPR
parent::Union{Nothing,EXPR}
children::Vector{EXPR}
data::Union{Nothing,SyntaxData}
tree::SyntaxNode
function EXPR(parent::Union{Nothing,EXPR}, children::Vector{EXPR}, data::Union{Nothing,SyntaxData}, tree::SyntaxNode)
new(parent, children, data, tree)
end
end
parentとchildrenに関しては木構造を構成するために必要な親子関係を格納するためのものです。一方で、dataやtreeに関しては何かというとJuliaSyntaxのTreeNode型が持っているフィールドで表示を行う際にこれらに含まれているメタ情報を使っています。しかし、あまり本質的ではないので割愛します。
2. Binding構造体
Binding構造体はあるExpr（変数）に対して型をアノテーションすることになった場合に、それを記録しておくための構造体です。中身は次のようになっています。
mutable struct Binding
name::EXPR
type::Union{CustomType,Nothing}
function Binding(name::EXPR, type::Union{CustomType,Nothing})
new(name, type)
end
end
ここでCustomTypeというのは自前で定義した構造体で、型を表す構造体の抽象型になっています。どういうことかというと、CustomType構造体は下のように定義されており、
abstract type CustomType end
juliaに存在する型たちは下のようにCustomTypeを継承するような形で定義されています。つまり、Binding構造体のtypeフィールドにはCustomTypeを継承するような構造体であればなんでも代入することができます。
struct AnyType <: CustomType end
struct StringType <: CustomType end
struct CharType <: CustomType end
struct BoolType <: CustomType end
struct IntType <: IntegerType end
3. Scope構造体
今回のアーキテクチャで最も重要といっても過言ではないのがこのScope構造体です。このScope構造体は現在自分のScope内にいる変数たちがどのような型で定義されているかを把握するための構造体です。
mutable struct Scope
parent::Union{Nothing,Scope}
expr::EXPR
names::Dict{Symbol,Binding}
children::Dict{String,Scope}
function Scope(parent::Union{Nothing,Scope}, expr::EXPR, names::Dict{Symbol,Binding},
children::Dict{String,Scope}=Dict{String,Scope}())
new(parent, expr, names, children)
end
end
parentとchildrenはScopeの木構造を表すためのフィールドです。そして重要なフィールドがnamesでこれは変数名（シンボル）とそのBindingの組を辞書形式で保持しているものになります。そして、exprは後に登場しますが、型付けを行っている際に現在どのexpr(式)に注目しているのかを知るためのフィールドになります。
これがコード全体で使われている構造体の説明になります。ここからは実際に型付けを行っているtcheck関数の実装について説明していこうと思います。
tcheck関数
1.全体
これから今回の型チェックのメインフローであるtcheck関数の処理について説明しようと思います。tcheck関数は下のような定義をされている関数です。Scope型の変数を渡すと、そのScope内の変数に対して型付けを行い、戻り値として最後のEXPRに対する型を返してくれるような関数になります。
function tcheck(scope::Scope) -> CustomType
では実際にtcheck内の実装の話に移りたいと思います。
function tcheck(scope::Scope)
expr = scope.expr
if (istoplevel(expr))
for child in expr.children
new_scope = Scope(scope.parent, child, scope.names, scope.children)
tcheck(new_scope)
end
return
elseif (isinteger(expr) || isstring(expr) || isfloat(expr) || ischar(expr) || isbool(expr))
return get_kind(expr)
elseif (isvector(expr))
return vector_check(scope, expr)
elseif
...
上のコードのようにScope型の中のexprに対して型を付けていきます。まず最初のif文はistoplevel(expr)となっていますが、これは何を判断しているかというと抽象構文木のrootノードであるかを判断しています。
下は先ほども提示したコードですが、抽象構文木にするとrootノードは[toplevel]というラベルがつけられます。これに当たるかどうかを判断しています。
そして、toplevelにあたる時はそのexprの子に対して型付けを実行するためfor文で再帰的に処理を書いています。
julia> ast = parseall(SyntaxNode, code)
line:col│ tree │ file_name
1:1 │[toplevel]
1:1 │ [=]
1:1 │ a
1:5 │ [call-i]
1:5 │ 1
1:7 │ +
1:9 │ 2
2:1 │ [if]
2:3 │ [call-i]
2:4 │ a
2:6 │ ==
2:9 │ 3
2:10 │ [block]
3:5 │ [=]
3:5 │ a
3:9 │ 2
その次のelseifは名前から明らかかと思いますが、プリミティブな値に関する分岐です。get_kind(expr)によってCutomType型が返されるようになっています。
2.関数型と構造体
関数型と構造体に関する説明をしようと思います。なぜ関数型と構造体が同じカテゴリーで話されるのかわからないと方もいらっしゃると思うので、まずは次のコードを見てください。
log("hello world")
"hello world"と表示してくれる関数に見えます。しかし、もしかするとこれは下のようなlog構造体へのコールかもしれません。
mutable struct log
content: String
end
何が言いたいのかというと関数と構造体のコールはとてもよく似ており、抽象構文木のパースの段階では区別することができないということです。なので、コールに関しては関数なのか構造体なのかをスコープから判断してやる必要があります。
1. struct
まずは構造体の処理から説明します
function typecheck(scope::Scope)
...
elseif (isstruct(expr))
struct_name_original = string(get_tree_val(expr.children[1]))
struct_name = "struct" * struct_name_original
new_scope = Scope(expr.children[2], scope)
block_expr = expr.children[2]
fields::Vector{Binding} = []
for child in block_expr.children
annotation_type = annotation_check(child)
if annotation_type !== nothing
push!(fields, add_binding!(new_scope, child.children[1], annotation_type))
elseif isfunction(child)
construct_scope = Scope(child, scope)
tcheck(construct_scope)
end
end
struct_type = CustomStruct(struct_name_original, fields)
add_struct_binding(new_scope, expr, struct_name_original, struct_type)
scope.children[struct_name] = new_scope
return struct_type
実装は上のようになっています。まずは1行目で構造体の名前を取得し、先頭に"struct"という文字をつけて保持しておきます。これは本当は良くないのですが、関数型と差別化するために文字列"struct"を先頭につけるという暴挙を行いました。
そして、3行目で構造体の中のスコープを定義しています。for文で構造体の内部で定義されている変数とその型、およびコンストラクタが存在しているかをチェックし、コンストラクタが存在した場合はグローバルなスコープに関数として登録するためにtcheck関数を呼び出しています。
その後CustomStructによって構造体の型を作り、該当するスコープに先ほど説明した"struct"から始まる構造体名で登録を行なっています。
2. function
次に関数型について説明します。juliaでは多重ディスパッチという考え方に基づいて関数が設計されており、同名の関数であっても引数が異なれば定義することができるようになっています。なので、ここら辺にうまく対処できるようにスコープに関数を登録していかなければいけません。
具体的なコードは次のようになっています
function tcheck(scope::Scope)
...
elseif (isfunction(expr))
call = expr.children[1]
new_scope = Scope(expr.children[1], scope)
new_bindings = fargs_binding(new_scope, expr.children[1])
new_scope_block = Scope(scope, expr.children[2], new_scope.names, new_scope.children)
ret_type = tcheck(new_scope_block)
f_name = get_tree_val(call.children[1])
function_type = CustomFunction(string(f_name), new_bindings, ret_type)
fargs_type = CustomCalledType(function_type)
scope.children[string(fargs_type)] = new_scope
add_function_binding!(scope, expr, function_type) #global function definition
add_function_binding_local!(new_scope, expr, f_name, function_type) #local function definition
return function_type
end
まずはfargs_bindingから引数の型情報を取得し、new_bindingsに保存します。そしてtcheck(new_scope_block)を実行して戻り値の型をret_typeに代入します。関数名を取得したのち、これらの情報を合わせてCustomFunction型を作ります。
scopeにはCustomFunction型で登録することによって多重ディスパッチを実装しています。また、関数内部はグローバルとは異なるスコープとなるので、scope.children[string(fargs_type)] = new_scopeによってscopeのツリー構造を作っています。
実際に多重ディスパッチが実装できていることは次のように確認できます。
julia> code = """
function test(a ::Int)
return a + 1
end
function test(a ::Float64)
return a
end
test(1)
test(1.0)
"""
julia> codetest(code)
[toplevel]
[function]
[call]
test ::Function test(a :: Int) -> Int
[::]
a ::Int
Int
[block]
[return]
[call]
a ::Int
[+]
1
[function]
[call]
test ::Function test(a :: Float64) -> Float64
[::]
a ::Float64
Float64
[block]
[return]
a ::Float64
[call]
test :: Function test(a :: Int) ->Int
1
[call]
test :: Function test(a :: Float64) ->Float64
1.0
表示
juliaの表示は大きく分けて２つ存在していて、REPLと標準出力です。REPLとはjuliaのインターラクティブモード（ターミナルでpythonって打つと始まる対話型のアレです）で、標準の出力と異なる装飾が施されて表示されることがよくあります。今回は実験という限られた時間内で行なったため、標準出力とREPLに差異はありません...。
が、先ほども見た下の例のように結構見やすいようにスタイリングされた表示を行なっているので、折角なら説明したいと思います。
julia> JuliaTypeCheck.codetest(code)
[toplevel]
[=]
a ::Int
[call]
1
[+]
2
[if]
[call]
a ::Int
[==]
3
[block]
[=]
a ::Int
2
上の表示は単にprint(Scope型の変数)としてやると表示してくれるのですが、何も手を加えずにこれを実行するとお分かりの通りネストしたScope構造体の情報がダーーーっと表示されるだけで何のことなのかさっぱりわかりません。
juliaにおいて表示をカスタマイズするにはBase.show()という関数を定義する（元々juliaの内部のBaseモジュールにて定義されているので多重定義になる）必要があります。具体的には次のように行います。
Base.show(io::IO, t::IntType) = print(io, "Int")
例えば上のようにIntType型に関するBase.show関数を定義すると、print(IntTypeのインスタンス)をすると標準出力にはIntと表示されます。
では実際のScope型に対するBase.showはどのようになっているかというと次のようになっています
function Base.show(io::IO, s::Scope)
Base.show(io, s, s.expr, s.names)
end
function Base.show(io::IO, scope::Scope, e::EXPR, dict::Dict{Symbol,Binding}, indent::String="")
name = get_tree_val(e)
if isfunction(e)
...
elseif isstruct(e)
...
elseif iscall(e)
...
end
if name !== nothing
if haskey(dict, name)
print(io, indent, name)
print(io, " ::")
println(io, dict[name].type)
elseif !isleafnode(e)
print(io, indent, "[")
print(io, name)
print(io, "]")
println(io)
else
print(io, indent, name)
println(io)
end
end
if e.children !== nothing
for child in e.children
Base.show(io, scope, child, dict, indent * " ")
end
end
まずget_tree_val(e)はJuliaSyntaxは抽象構文木のノードの値を取ってきてくれます。例えばblockやif,vect,1などです。そして、その後の部分はちょっと長くなりそうなので一旦飛ばします...
後ろの方が本質的で、nameに値がnothingでなければ、indentを追加して表示しています。その際に型アノテーションをしたり、[block]、[if]、[vect]などのラベルへの変換も行っています。その後に、eに子がいるのであればインデントを追加して再帰的に呼び出す。このような仕組みで動いています。
formatter
ここからはちょっと話が変わります．JuliaTypeCheckパッケージの中には，tcheck関数をもとに型アノテーションを行って表示するcodetestメソッドと主に，formatterメソッドというのも実装しました．formatterメソッドには文字通りフォーマッターが実装されており，コードのインデント，空白，改行などのフォーマットを統一する機能があります．その実装について説明していきます．
1. EXPR構造体の修正
まずEXPR構造体にcodeというフィールドを追加します．このcodeフィールドには，構文木における自分の全子孫ノードのコードを，フォーマットを揃えた状態でまとめ，格納します．最終的にはtoplevelのノードのcodeフィールドに，整形された全体のコードが文字列として入ります．
mutable struct EXPR
parent::Union{Nothing,EXPR}
children::Vector{EXPR}
data::Union{Nothing,SyntaxData}
tree::SyntaxNode
code::Union{Nothing, String}
function EXPR(parent::Union{Nothing,EXPR}, children::Vector{EXPR}, data::Union{Nothing,SyntaxData}, tree::SyntaxNode, code::Union{Nothing, String})
new(parent, children, data, tree, code)
end
end
2. 深さ優先探索（DFS）による更新
各ノードのcodeをどのように決定するかですが，これは構文木をDFSしながら更新していきます．以下のような関数が実装されており，「もし今みているノードが葉ノードならば，そのノードのcodeに自身の値を格納」「それ以外ならば自身の子ノードをDFSし，帰り際に，自分の子ノードのcodeを見て自身のcodeを決定するget_code関数を実行」という操作がされます．
function dfs_tree(node::EXPR)
if length(node.children) === 0
node.code = string(get_tree_val(node))
else
for child in node.children
dfs_tree(child)
end
get_code(node)
end
end
3. formatterメソッドの実行結果
formatterメソッドには，DFSによって全てのノードのcodeを更新したのち，toplevelのノードのcodeを表示する実装がされています．
例えば以下のようなインデント，空白，改行などのフォーマットがバラバラのコードをformatterメソッドの引数にとって実行すると，
julia> code = """
function messy_code(a :: Int,b::Float64)
if a>b
println("a is greater than b" )
elseif a <b
println( "b is greater than a" )
else println("a and b are equal" )
end
end
"""
このようになります．インデント，空行，改行などがそろい，適度な空行も挿入されて見やすいコードに整形されていることがわかります．
julia> JuliaTypeCheck.formatter(code)
function messy_code(a ::Int, b ::Float64)
if a > b
println("a is greater than b")
elseif a < b
println("b is greater than a")
else
println("a and b are equal")
end
end
4. 既存のフォーマッターと違い
既存のフォーマッターでは空行が整形されず，詰め詰めになったりスカスカになったりするため，長いコードを書くときに見にくいという問題点があります．今回の実装ではif・elseif・else・for・whileなどのブロックの前後に，一行づつ空行が挟まるようになっており，Juliaで大規模な実装をする際にもコードが見やすくなっています．また，空行が挟まりすぎて不自然すぎないよう，代入などの操作が続く時は詰める，というようにしました．
5. 問題点
セクションの最後に今回のフォーマッター実装の問題点についても軽く述べておこうと思います．
まず，JuliaSyntaxのparseallがコメントアウトを無視するため，formatterを実行するとコメントアウトが消えてしまうという点が挙げられます．コードを見やすく整形しようとしてコメントアウトが消えてしまうというのはなかなか不便なので，コメントアウトがない部分ごとにformatterにかけるのがいいでしょう
また，kind関数というのがノードの値の型を判別する際に使用されているのですが，一部の表現方法が同じkind関数の返り値を持つため，mutable struct が structに，baremodule が moduleになってしまったりします．構造体やモジュール定義などの部分はformatterを使用しないほうがいいです．
エスケープ文字に関する不具合もあります．エスケープ文字を文字列にするときにエスケープ文字だと認識されて変な改行などが生じることがあるため，なるべくコード内の文字列にはエスケープ文字を使わないほうがいいでしょう．
パッケージのインストール
これはReadmeにも書かれていることですが、パッケージのローカルでの使い方を説明します。
パッケージのtomlファイルにも書かれていますが、juliaはバージョン1.11.0、JuliaSyntaxはバージョン0.4.10、Testはバージョン1.11.0を使用しています。
$ git clone git@github.com:doss-eeic/2024-04-julia.git
$ cd JuliaTypeCheck
$ julia
julia> using Pkg
julia> Pkg.develop(path="/absolute/path/to/JuliaTypeCheck")
julia> using JuliaTypeCheck
julia> codetest("""
a = 3.5
if a >= 1
return true
end
"""
)
[toplevel]
[=]
a ::Float64
3.5
[if]
[call]
a ::Float64
[>=]
1
[block]
[return]
true
julia> code = """
function messy_code(a :: Int,b::Float64)
if a>b
println("a is greater than b" )
elseif a <b
println( "b is greater than a" )
else println("a and b are equal" )
end
end
"""
julia> formatter(code)
function messy_code(a ::Int, b ::Float64)
if a > b
println("a is greater than b")
elseif a < b
println("b is greater than a")
else
println("a and b are equal")
end
end
julia>
上の方法でJuliaTypeCheck内のcodetestメソッドが使えるようになります。同様にformatterメソッドも使えます
また、JuliaTypeCheckにはテストコードが用意されていて、その実行方法は次のとおりです。
julia>
press ] to enter Pkg mode
(@v1.11) pkg> test JuliaTypeCheck