Scala Advent Calendarの18日目の記事です。
公開が遅れてしまいnnao45さんから下記の記事で代行もして頂いていました。
【Scala】catsのValidatedの使い所、及びValidatedNecとValidatedNelについて
ありがとうございました!!
はじめに
ScalaのCompilerは型推論、型消去、エラー構文の検知など、いろんなところで活躍していますが、僕はソースコードをバイトコードに変換してくれるものくらいの理解で開発していました。(雰囲気で使っていた。)
しかし最近はScalaのコンパイル速度を気にするようになり、さらにScala次世代のコンパイラであるDottyがどんどん開発されてきたので、コンパイラの動きを理解したいなと思い、今回はScalaのCompilerを調べました。
ですが、Compilerの実装はあまり見ておらずこちらの英語の記事を読みました。
- Typelevel The Phases
- Scala Compiler Phases with Pictures
- 記事のScalaのバージョンが2.12系
各phaseで、上記の記事を日本語に意訳しながら理解をしていきたいと思います。
ScalaのCompilerとは
Scalaのソースコードを解析してバイトコードを生成してくれます。
またScalaのCompilerはScalaで実装されている大規模なコードです。
コンパイルのフェーズ
コンパイルにはフェーズ(phase)と呼ばれる順次実行されるステップの処理に分割されています。
scalac
コマンドで-Xshow-phases
オプションを使うとソースコードを解析して、JVMのバイトコードが生成させるコンパイラのフェーズを出してくれます。
※ scalacコマンドはscalaをインストールすると利用できます。
% scalac -Xshow-phases
phase name id description
---------- -- -----------
parser 1 parse source into ASTs, perform simple desugaring
namer 2 resolve names, attach symbols to named trees
packageobjects 3 load package objects
typer 4 the meat and potatoes: type the trees
superaccessors 5 add super accessors in traits and nested classes
extmethods 6 add extension methods for inline classes
pickler 7 serialize symbol tables
refchecks 8 reference/override checking, translate nested objects
patmat 9 translate match expressions
uncurry 10 uncurry, translate function values to anonymous classes
fields 11 synthesize accessors and fields, add bitmaps for lazy vals
tailcalls 12 replace tail calls by jumps
specialize 13 @specialized-driven class and method specialization
explicitouter 14 this refs to outer pointers
erasure 15 erase types, add interfaces for traits
posterasure 16 clean up erased inline classes
lambdalift 17 move nested functions to top level
constructors 18 move field definitions into constructors
flatten 19 eliminate inner classes
mixin 20 mixin composition
cleanup 21 platform-specific cleanups, generate reflective calls
delambdafy 22 remove lambdas
jvm 23 generate JVM bytecode
terminal 24 the last phase during a compilation run
parserからterminalまでの24のフェーズがあります。
全てのフェーズを紹介できないですが、いくつかフェーズを見ていきます。
Parser (phase 1)
parse source into ASTs, perform simple desugaring
- 最初のフェーズでパーサーとスキャナーを使用して型なし抽象構文木(AST)を作成します。
- 抽象構文木(AST、Abstract Syntax Tree)とは、コードがコンパイラによってどのように解釈されるか表現したものです。
※構文木
- 抽象構文木(AST、Abstract Syntax Tree)とは、コードがコンパイラによってどのように解釈されるか表現したものです。
- このタイミングでASTにエラーがあれば、構文エラーが投げれます。また、
for
式は、flatMap
、map
、およびfilter
に変換されます。
object Sample {
def append(a:Option[Int], b:Option[Int]) = {
for {
i <- a
j <- b
} yield i + j
}
val double: Int => Int = _ *2
}
-Xprint:parser
のオプションを使うことで、parser
のphaseを表示できます。
$ scalac Sample.scala -Xprint:parser
[[syntax trees at end of parser]] // Sample.scala
package <empty> {
object Sample extends scala.AnyRef {
def <init>() = {
super.<init>();
()
};
def append(a: Option[Int], b: Option[Int]) = a.flatMap(((i) => b.map(((j) => i.$plus(j)))));
val double: _root_.scala.Function1[Int, Int] = ((x$1) => x$1.$times(2))
}
}
ASTが作成され、for式もがflatMapとmapに、関数リテラル=>
も Function1に変換されます。
Namer, Typer, Package Objects (phases 2,3,4)
show-phases
の説明だけ見ると、一見単純そうな処理に見えます
- namer
- 名前を解決して、名前付きのASTにシンボル(symbol)を追加する。
- packageobjects
- パッケージオブジェクトを読み込む
- typer
- 「the meat and potatoes」: ASTに型をつける
-
meat and potatoes
とは、そのまま「肉とじゃいがいも」という意味ではなく主要部分という意味の方で、Scalaのリッチな型システムを処理するための主要部分という意味だと思います。
-
- 「the meat and potatoes」: ASTに型をつける
しかしThe Phasesによると
Namer
,Typer
,Package Objects
は実装上の理由から3つの要素に分割されていますが、3つに多くの相互依存関係があるため、事実上一つのフェーズとみなせるとのことです。
namer, packageobjects, and typer (phases 2,3, and 4) are effectively a single phase. Although split into 3 elements for implementation reasons, the dependencies between them means you can consider it one.
下記のスライドがわかりやすいのです。、最初にNamer
がシンボルテーブルを作り、その後Typerが型付きASTを作っています。
A deep dive into scalac - ScalaMatsuri 2016
さらにScala Compiler Phases with Picturesによると、typerフェーズで下記のScalaの型システムを処理しているそうです。
- 型を推論
- 型が一致するか確認
- 暗黙的な引数(implicit parameter)を検索し、ASTに追加
- 暗黙的な変換(implicit conversions)を行う
- 全ての型操作が許可されているかどうかを確認(たとえば、型はそれ自体のサブタイプにはできません)
- オーバーロードを解決
- 親の参照の型をチェック
- 型違反をチェック
- implicitsの検索
- マクロを展開
- ケースクラスの追加メソッド(copy、applyなど)を作成
typerが完了すると全ての型チェックが完了し、もし型クラスの暗黙的な実装がない場合などは、このタイミングでエラーになります。
typerがコンパイルで一番時間がかかっているといわれますが、この一連のフェーズでは確かに色々な処理をしていますね。
Patmat(phase 9)Pattern matching
このフェーズで、パターンマッチをif、elseに変換しています。
object Color {
case object Red extends Color
case object Blue extends Color
case object Green extends Color
def toJapanese(color: Color) = color match {
case Red => "赤"
case Blue => "青"
case Green => "緑"
}
}
scalac Color.scala -Xprint:patmat
//省略
def toJapanese(color: Color): String = {
case <synthetic> val x1: Color = color;
case7(){
if (Color.this.Red.==(x1))
matchEnd6("赤")
else
case8()
};
case8(){
if (Color.this.Blue.==(x1))
matchEnd6("青")
else
case9()
};
case9(){
if (Color.this.Green.==(x1))
matchEnd6("緑")
else
case10()
};
case10(){
matchEnd6(throw new MatchError(x1))
};
matchEnd6(x: String){
x
}
}
Uncurry(phase 10)
- アンカリーして、関数を無名クラスに変換します。
def f(a: Int)(b: Int): Int = a + b
def f2(seq: Int*): Int = seq.sum
def f3(a: => Int): Int = a + 5
def f4: Int = 5
$ scalac Sample.scala -Xprint:uncurry
[[syntax trees at end of uncurry]] // Sample.scala
//省略
def f(a: Int, b: Int): Int = a.+(b);
def f2(seq: Seq[Int]): Int = seq.sum[Int](math.this.Numeric.IntIsIntegral);
def f3(a: () => Int): Int = a.apply().+(5);
def f4(): Int = 5
curry化と関数の糖衣構文が削除されます。
Tail calls (phase 12)
- 末尾再帰を最適化します。
末尾再帰で実装されている箇所は、バイトコードでジャンプ制御に変換してくれます。
Specialize (phase 13)
specializedアノテーションがあるクラスやメソッドを特定の型に特殊化したクラス、メソッドにします。
- specializedの説明ついては、Scala specializedアノテーションをご確認ください。
- コンパイラにプリミティブ型の使用を強制し、型消去を回避します。
Erasure and posterasure (phase 15,16)
erase types, add interfaces for traits
clean up erased inline classes
- ジェネリッククラスまたは値クラスを使用すると、このフェーズで消去されます
- 型消去は、後方互換性を有効にするためにJava 5のジェネリックで作成されたJVM機能
- 不要なコードをクリーンアップし、いくつかの最適化を行い、値クラスのボックス化を解除します。
package model
class Stack[A] {
private var elements: List[A] = Nil
def push(x: A) { elements = x :: elements }
def peek: A = elements.head
def pop(): A = {
val currentTop = peek
elements = elements.tail
currentTop
}
}
% scalac Stack.scala -Xprint:erasure
[[syntax trees at end of erasure]] // Stack.scala
package model {
class Stack extends Object {
def <init>(): model.Stack = {
Stack.super.<init>();
()
};
private[this] var elements: List = scala.collection.immutable.Nil;
<accessor> private def elements(): List = Stack.this.elements;
<accessor> private def elements_=(x$1: List): Unit = Stack.this.elements = x$1;
def push(x: Object): Unit = Stack.this.elements_=({
final <synthetic> <artifact> val rassoc$1: Object = x;
Stack.this.elements().::(rassoc$1)
});
def peek(): Object = Stack.this.elements().head();
def pop(): Object = {
val currentTop: Object = Stack.this.peek();
Stack.this.elements_=(Stack.this.elements().tail().$asInstanceOf[List]());
currentTop
}
}
}
Lambda lift, constructors, flatten (phase 17, 18, 19)
- ネストされたメソッドをトップレベルへ移動
- フィールド定義をコンストラクタへ移動
- 内部クラスを排除
JVM (phase 23)
- JVMバイトコードを生成
と一通りフェーズの流れを見ていきました。
Compilerの処理の流れ(まとめ)
- parser
- ソースコードを解析し、ASTを作る
- namer
- 名前を解決し、名前付きASTにシンボルをつける
- packageobjects
- パッケージオブジェクトを読み込む
- typer
- 型推論、implicit検索、マクロ展開や型違反チェックなど
- Scalaのリッチな型システムを処理するための主要部分を行っている
- superaccessors
- トレイトやネストされたクラスにスーパーアクセッサーを追加
- extmethods
- インラインクラスに拡張メソッドを追加
- pickler
- シンボルテーブルをシリアライズする
- refchecks
- 参照とオーバーライドをチェックし、ネストしたオブジェクトを変換する
- patmat
- パターンマッチをif、elseに変換
- uncurry
- アンカリーして、関数を無名クラスに変換します。
- fields
- アクセッサーとフィールドの合成、ビットマップを遅延評価につける
- tailcalls
- 末尾再帰を最適化し、ジャンプコールに変換する
- specialize
- specializedアノテーションのクラス、メソッドを、特定の型に特殊化したクラス、メソッドに変換
- explicitouter
- 外部ポインタへの参照
- erasure
- 型消去
- posterasure
- 不要なインラインのクラスを消去
- lambdalift
- ネストされたメソッドをトップレベルで移動
- constructors
- フィールドの定義をコンストラクタへ移動
- flatten
- インナークラスを排除する
- mixin
- ミックスインを組み立てる
- cleanup
- プラットフォーム固有のクリーンアップと、リフレクションコールの生成
- delambdafy
- ラムダ関数を削除する
- jvm
- JVMバイトコードを生成する
- terminal
- コンパイル実行時の最後のフェーズ
コンパイラが遅くなる原因
色んな資料でtyperに時間がかかっており、さらにimplicit検索とマクロの処理に時間がかかるということが書かれています。
the longest phase (not surprisingly) is typer. As I mentioned before, Scala has a rich, complicated type system that needs a lot of time to process. Furthermore, such libraries as Shapeless are based on implicits and macros that are also time consuming.
コンパイルを速くするには?
今回調べて感じたことですが、まずは下記かなと思います。
- まずはScalaをアップデートする
- Scalaのリリースを見ていると、コンパイルが改善されている
- Scala2.12.9ではScala2.12.8より5-10%速くなり、Scala 2.13.0でも5-10%速くなったとある。
- Scalaのリリースを見ていると、コンパイルが改善されている
-
scalac-profiling使ってボトルネックを調査して、遅い原因を見つける。
- 参考SPEEDING UP COMPILATION TIME WITH SCALAC-PROFILING
- ワイルドカードのimportを変更する
- もし不要なimplicit、マクロがあれば使わない方法で対応する
- 参考SPEEDING UP COMPILATION TIME WITH SCALAC-PROFILING
- コンパイルを速くするツールを試す(まだ使ったことがない)
Scala3のコンパイラはどうなっているのか?
Scala3からは、TASTy(Typed Abstract Syntax Trees (y))という表現形式が入るようです。
(コンパイルで.tastyファイルが作られる)
名前が解決され、型推論と型チェックされ、オーバーロードが解決され、implicitsが挿入されているそうです。
バイトコード生成のフェーズは同じ方法であると記載がありました。
Scala 2.13 and 3.0 will use the same standard library, and their compiler back-ends will emit bytecode in the same way
The code generation phase of the Scala 3 compiler is the same as in Scala 2.13
SCALA 2 ROADMAP UPDATE: THE ROAD TO SCALA 3
終わりに
今回Scala Compiler Phases with Picturesの記事を読んで、どのタイミングでどんな処理が行われているのかを把握しました。
typerに時間がかかるということですが、implicitもマクロも使うケールは出てくると思うので、Compilerのスピードを劇的に速くすることは難しいと感じています。
ただscala自体のCompilerの性能が良くなっていますし、Scala3で速くなるかもしれません。
またCompilerを速くするツール(Hydra、Bloopなど)が出ているので、試してみたいなと思います。