読者です 読者をやめる 読者になる 読者になる

kmizuの日記

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

scala-nativeのサンプルプログラムをLinuxで動作させる場合の注意点

kmizu.hatenablog.com

についての補足的なエントリです。scala-nativeのサンプルプログラムsmallpt.scala__stderrpを使っていますが、Linux系には存在しないので、リンク時にこけてしまいます。

これを修正するには、smallpt.scalastdlib.scala__stderrp__stdoutpをそれぞれ、stderrstdoutに書き換えてやる必要があります。現状、条件コンパイルのような仕組みはサポートされていないのでこれをクロスプラットフォームで動作させる方法がたぶんないのがちと困ったものです(作者本人が作ったIssueには入っているので、そのうち解決されるだろうとは思いますが)。実は手元でunameを使ってOSによって分岐するコードを書いてみようとしたのですが、構造体のメモリレイアウトが微妙に違うのか、unameは呼び出せるものの、返り値に謎の値が入っているという事態になりました(なにか勘違いしているかも)。

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

Scala

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はその機能をそのまま使っているのかもしれませんね。

Scala Nativeを動かしてみた(1)

Scala Compiler

Scala Nativeはscalaのコードを(LLVMのIRを経由して)ネイティブコードにコンパイルするAOTコンパイラ(Ahead Of Time Compiler)です。その存在については、少し前にサイトができていたことで一部で話題になっていましたが、Scala Days 2016 NYCにて正式に公開されました。現在はPre-Release段階ですが、既にサンプルコードを試せるようになっていたので、環境を構築してみました(on Mac OS)。

$ git clone git@github.com:scala-native/scala-native.git --recursive

git submoduleとしてscala/scalaを持っているので、--recursiveを付けるのを忘れないようにしましょう。

  • llvm(clang)とbdw-gcをインストールする
$ brew install --with-clang llvm
...
$ brew install bdw-gc
$ sbt
> project rtlib
> publishLocal
> project nscplugin
> publishLocal
  • デモプロジェクトに移動(sbtを起動したまま)
> project demoNative
  • 実行(gc.hがないといったエラーが出るはず)
> run
  • bdw-gcにパスを通す
nativeClangOptions := Seq("-I/usr/local/Cellar/bdw-gc/7.4.2/include", "-L/usr/local/Cellar/bdw-gc/7.4.2/lib")

この、nativeClangOptionsというsettingKeyは、ここで定義されていて、要はclangに渡すオプションを格納するためのものです。インクルードパスとライブラリパスの両方を渡してやります。なお、ここでは、明示的にbdw-gcをインストールしたディレクトリにパスを通しましたが、うまくやればそもそもここでつまづく事はない…かもしれません。うまくいかない場合はこの辺をいじればなんとかなるということでもあります。

  • 再度実行
> run

なにやら色々warningが出ますが、それはともかく、赤枠で囲った部分が表示されればひとまず成功です。 f:id:kmizushima:20160512221647p:plain

Scala Nativeを試してみたいけど、うまく行っていない人が居るようだったので、とりあえず走り書き程度ですが、参考になればと思います。気が向いたら、サンプルプログラムをちょっといじってなんかやってみたいと思います。

Kotlin用不変コレクションライブラリ kollection 0.2リリース

  • リストベースの集合であるKListSet
  • リストベースのマップであるKListMap
  • 遅延評価を提供するKLazy

のサポートを追加しました。また、必要になった時点で、KListにもメソッドを随時継ぎ足していってます。詳細についてはREADMEを参照ください。

github.com

Kotlinでメソッド定義にrunを使う意義

Kotlin プログラミング言語

Kotlinにはrun というメソッドがstdlibにあります。これ、定義をみると、

@kotlin.internal.InlineOnly
public inline fun <R> run(block: () -> R): R = block()

引数で渡された0引数ラムダ式(とKotlinの用語法に従っておく)をそのまま呼び出すだけというものになっています(もう一バージョンあるのですが、そっちについては割愛)。本来の意味での用途かはわからないですが、これが役に立つケースとして、メソッド定義でreturnを書かなくても済むというものがあります。

たとえば、引数を取り、それぞれを出力した後、二つの値を足したものを返すメソッドprintAndAddは、通常は以下のように書く必要があります。

fun printAndAdd(x: Int, y: Int): Int {
  println(x)
  println(y)
  return x + y
}

さて、このreturn必須というのが、(式ベースの言語から来ると)地味に嫌なわけですが、この制限をrunを使って回避することができます。以下のように書き換えるだけです。

fun printAndAdd(x: Int, y: Int): Int = run {
  println(x)
  println(y)
  x + y
}

runにその場で生成したラムダ式を渡して実行するという形になりますが、ラムダ式の返り値の型をKotlin処理系が推論してくれるため、書く必要がなくなっています。

ところで、メソッド呼び出しのたびにラムダ式が生成されるというと実行コストが気になる人がいるかもしれませんが、心配ご無用。runにインラインで渡された無名関数はそのままインライン展開されるため、オーバーヘッドはほぼゼロです。

試しに、次のコードをコンパイルしてみます:

fun add(x: Int, y: Int): Int = run {
  x + y
}

javapした結果:

Compiled from "P.kt"
public final class PKt {
  public static final int add(int, int);
    Code:
       0: nop
       1: iload_0
       2: iload_1
       3: iadd
       4: ireturn
}

nopが入ってしまっているのが多少残念ですが、さすがにこのレベルで無駄なコードはJITコンパイラが消去してくれることを期待できますし、万が一消去してくれなかったとしても、メソッド一つにつきnop命令一つ分のオーバーヘッドはほぼ無視できます。

ただ、性能面での問題点はないものの、Kotlinの標準的な慣習に沿っていないという点はやや微妙かもしれません。まあ、その辺は統一してrunを使っていれば問題は少ないのではないかとも思いますが。

stripMarginの歴史

ScalaのString(正確にはStringOps)にはstripMarginというメソッドがあります。これは、主に複数行文字列に使われる機能で、たとえば、

"""|class Hello {
   |  
   |}""".stripMargin

のようにすると、

res0: String =
class Hello {

}

という文字列が得られ、行頭のスペースを除きたい場合に非常に便利な機能です。この機能、どうやらGroovyにもあるらしく、名前もまんまstripMarginです。さて、これ、GroovyがScalaのそれにインスパイアされたのか、それとも逆なのか調べていたところ、Groovyの過去のIssueにstripMargin()を追加するというものがあり、

[GROOVY-3349] Add stripMargin() to multi-line strings - ASF JIRA

どうやらScalaのstripMargin()が先のようです。他には、npmのstripmarginがありますが、これは、

A helper for strip string's margin like scala

なので、元がScalaということのようです。Kotlinにはメソッド名を微妙に変えた trimMargin

kotlinlang.org

というメソッドがありますが、登場年代からしても、おそらくScalaの影響を受けたものでしょう。他にも類似メソッドがあるかもしれませんが、とりあえずこんなところで。

Kotlin用不変コレクションライブラリ kollection 0.1リリース

ちょっと前から少しずつ作っていたのですが、最低限の機能はそろったので公開してみることにしました。Kotlinの標準ライブラリのコレクションは読み取り専用ビューは提供してくれるものの、不変コレクションがないのが不満だったので作ってみようというのが動機です。

github.com

ドキュメントは未整備ですが、現時点で

を使うことができます。

たとえばこんな感じです:

KList(1, 2, 3, 4, 5).foldLeft(0){a, e -> a + e} //15
KList(1, 2, 3) zip KList(4, 5, 6) // KList(Pair(1, 4), Pair(2, 5), Pair(3, 6))

詳細についてはテストコード を読んでみてください。

今後も継続的に扱える不変コレクションの種類を充実させていきます。