ScalaのCompilerについて #Scala

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にエラーがあれば、構文エラーが投げれます。また、for式は、flatMap、map、およびfilterに変換されます。

Sample.scala

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 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に変換しています。

Color.scala

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)

アンカリーして、関数を無名クラスに変換します。

Sample.scala

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機能
不要なコードをクリーンアップし、いくつかの最適化を行い、値クラスのボックス化を解除します。

Stack.scala

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 Compiler Phases with Pictures

コンパイルを速くするには？

今回調べて感じたことですが、まずは下記かなと思います。

まずはScalaをアップデートする
- Scalaのリリースを見ていると、コンパイルが改善されている
  - Scala2.12.9ではScala2.12.8より5-10%速くなり、Scala 2.13.0でも5-10%速くなったとある。
scalac-profiling使ってボトルネックを調査して、遅い原因を見つける。
- 参考SPEEDING UP COMPILATION TIME WITH SCALAC-PROFILING
  - ワイルドカードのimportを変更する
  - もし不要なimplicit、マクロがあれば使わない方法で対応する
コンパイルを速くするツールを試す(まだ使ったことがない)
- Hydra ※有料
- Bloop

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など)が出ているので、試してみたいなと思います。

ScalaのCompilerについて