kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

scala-nativeでは相互末尾再帰呼び出しも最適化される

Scala Nativeなのかscala-nativeなのか迷ったのですが、今後はリポジトリ名のscala-nativeに統一しようかと思います。さて、タイトルについてですが、そのまんまです。

サンプルコードは以下:

gist.github.com

通常のJVM上でのScalaでは、末尾呼び出しが自分自身で(自己末尾再帰)、かつ、その関数(メソッド)がオーバーライドされない場合に限り、末尾呼び出しを除去することができましたが、scala-nativeはそれに限らず、一般の末尾呼び出しも除去(ジャンプに置き換えることができる)という話です。

上記サンプルコードでは、単純にやるとおよそ100000000個分スタックを積む必要がありますが、そのまま関数呼び出しとして実装するとスタックオーバーフローします。事実、最適化オプションを付けないclang(3.7)では同等のコードを実行しようとするとsegmentation faultを起こしました(-O1以上の最適化オプションを付けるとちゃんと実行できました)。

JVM上でのScalaでは末尾呼び出しの除去をやろうと思うと、非常に高いコストを払って自前でトランポリン形式にするくらいしか選択肢がなかったですが、scala-nativeではJVMという制約がないので、その辺の最適化もできるようになった、ということです。

追記: LLVMでは言語非依存の最適化として末尾呼び出しの除去が行えるらしいのでscala-nativeはその機能をそのまま使っているのかもしれませんね。