Persimmon用のランダムテストライブラリ案(もしくは scalacheck の F# 移植)
あけましておめでとうございます。
さっそくですが進捗どうですか? 私は駄目でした(Persimmon用VS Test Explorer拡張的な意味で)。
今回はランダムテスト実装の話です。
Persimmon と FsCheck の相性について
FsCheck には IRunner という、拡張ポイントがあります。
この型を実装して Config
に設定することで、実装した各メソッドがコールバックされます。
が、これは このコメント にもある通り、xUnit.NET や NUnit ぽいものとは相性が良いものの、型を欲する Persimmon とは若干相性が良くないです。
では、 Runner だけ自力実装…というのも考えたのですが、断念しました。
実行に必要そうないくつかのモジュールや型が internal
になっており、互換を崩してまであのエグい実装をコピーしてメンテしたいかというと、うーん…。
FsCheck の公開関数が unit
を返す関数ばかりなのは何かの呪いですかね…。
そんなこんなで、FsCheck との連携は使いやすいかなんともいえないので、代替案のライブラリを作ってみようと思ったのが昨年末の話です。
干し柿(という名の scalacheck 移植)
というわけで、大晦日あたりから本命の息抜きに作ってみました。
persimmon-projects/Persimmon.Dried · GitHub
この干し柿は scalacheck をベースにしています。 手を入れるうちにいろいろ変わっていくと思うので、現時点では、という注釈つきですが。
FsCheck と scalacheck がどの程度異なるかは下記記事を参考にしてみてください。
FsCheck と ScalaCheck とを見比べる — a wandering wolf
以下、ちょっとした違いについて書いてみます。
Arbitrary
scalacheck の forAll
などは型クラスを用いて Arbitrary
インスタンスや Shrink
インスタンスをコンパイル時に補完します。
なので、別に Arbitrary
が Gen
しかもっていなくても不都合が起きません。
*1
しかし、この方法は正攻法で書いた場合の F# とは相性が悪いです。
そのため、 Persimmon.Dried では Arbitrary
にシュリンカとプリティプリンタも持たせ、 forAll
などには明示的に Arbitrary
を適用する方式にしています。
プリティプリンタ
このあたりは scalacheck に似せています。 そういう理由もあって型に対応する出力を自分でカスタマイズ可能です。
型クラス
とはいえ、型クラスを全く使わないわけにもいきません。 なぜかというと、 Prop 型への変換は基本的に単純作業になりやすいからです。
そのため、 Prop を返す関数や演算子では基本的に PropApply
という値を第1引数にとるに引数メソッド Instance
を持つ第2引数の型に限って、inline 展開と型推論によって型を変換します。
現時点では
- bool
- PropResult
- Prop
- Persimmon.TestResult
- Persimmon.AssertionResult
が変換対象です。
乱数生成
FsCheck は自前の、 scalacheck は標準のランダムモジュールを使っています。
Persimmon.Dried ではどうしようかなと迷ったのですが、この際なので FsRandom を使ってみることにしました。 既存かつ精度も申し分ないので問題ないと思っています。
実は単独でも動く
scalacheck ベースなので、当たり前といえば当たり前の話です。 ただ、 ConsoleReporter とコマンドラインパーサを(意図的に)実装していないので、スクリプトで実行しても何も出力されません。
この辺りも実装するかどうかは気分次第ですね。
おわりに
また一つ、オレオレライブラリが増えてしまった。
*1:Arbitrary 型がなくてもよいのでは、といわれることがあるのはこのためだと思っています
FsAttoparsecとattoの内部構造が変わった話とか
私が FsAttoparsec を実装し始めた5月頃、実は本家 attoparsec は内部構造を新しいものに変更していたということに先月末気が付きました*1。 どういう変更かというのは
A major upgrade to attoparsec: more speed, more power | teideal glic deisbhéalach
これ読めばいいと思います。
というわけで、attoparsec の F# 移植である FsAttoparsec や Scala 移植で最近もメンテナンスされている atto も追随させたいと思って修正することにしました。
内部の状態に position を持たせる
とはいえ、F# や Scala は Haskell ではないし、パフォーマンス調査するのも面倒だなーということで内部構造のみ変更することにしました。 そのあたりの変更部分は
https://github.com/pocketberserker/FsAttoparsec/commit/5082a9aa6102b39ee31264aa734117b925be5c52
と
new internal design · 5082a9a · pocketberserker/FsAttoparsec · GitHub
で確認できます。 大雑把にいうと内部状態に position を持つようにしたのでいろいろ取れるようになったね、という。
ちなみにこの内部設計、attoparsec 的には第3世代らしい(前述の記事参照)。
atto のアレなところ?
attoparsec のセールスポイントの一つに"不完全な入力でも動作する"というものがあります。 が、atto の parse メソッドと parseOnly メソッドはその中で feed メソッドを呼び出してしまっているため、このポイントをつぶしているようにも見えるのでした。
(というかこれに気が付かずテストがこけて何事かと思った)
雑感
正直、 attoparsec みたいな実装は rankNtype があって濃度解析のような最適化が組み込まれていて Trampoline を差し込まなくてもスタックオーバーフローにならない言語でないと速度改善は厳しいのかなと。
いやまぁ、インターフェースのメソッドを inline 指定できるとか高速に動作する Trampoline があれば問題ないのですけど、それはちょっと難しそうだしなぁ…。
クラスベースでCPSな実装にした場合のパフォーマンス改善はなかなか難しい問題な気がしてます。
各言語でtype classesを実装する際に使いそうな道具とか
現時点における GHC、Scala、F#、Java の type classes 実装に使う道具比較をメモしておきます。
言語比較したいわけではなく、論争を繰り広げたいわけでもないのであしからず。
あとてきとーに書いてる感は否めないので、間違っている言葉、表現、概念などあれば適宜突込みをお願いします。
高階型
F# や Java に関しては以下の記事を参照してください。
JavaでFree Monad - scalaとか・・・ F# で高階型のエミュレーション - pocketberserkerの爆走
ランクN多相的な何か
末尾再帰最適化
- GHC: よく知らない(そもそも lazy evaluation だし…)
- Scala: あり。 tailrec annotation をつけておくと末部再帰になっていない場合コンパイルエラー。
- F#: あり。次のバージョンあたりで Scala の tailrec annotation みたいな機能追加したいねとか言っていたような…
- Java: なし
型クラスのインスタンス作成
表現が思いつかなかった…とりあえず Maybe での例
-- GHC instance Monad Maybe where ...
// scalaz の Maybe での例 new Monad[Maybe] {
// F# type Option = Z { new Monad<Option.Z>
F# の場合、型パラメータの制約に hoge メソッドを持つ、とかできるので、高階型をエミュレーションしない場合はこの書き方にならない。 が、あれを説明するのは面倒なので FsControl というライブラリを検索してください。
Java は inner class に型クラスを継承させるのがやりやすい、だったかな?
型引数が2つある場合
- GHC: Monad (Free f) とかやれば書ける
- Scala: Monad[({type f[x] = Free[S, x]})#f]
- F#: 型を握りつぶすか、Option.Zにしておいてメソッドを呼び出したときに型パラメータを指定する
- Java: ワイルドカードを使う
Scalaは今後 type lambdas というシンタックスシュガーが入るかもしれない?
このあたりは F# が不利。 型をいい感じにできるのはもしかしたら type erasure 方式の利点かもしれない。
これと
これとかの比較だと、F# は型が残る上に変位指定ができない(できるならだれか教えてください)から、下手に obj も使えなくて悲しいことになっていたりします。 Java版はそのあたりすっぱり割り切っている。
型推論
これに関してはあまり書きたくない…。
どの言語にもあるけど、どこまで推論されるかは言語次第だよ、くらいでいいですかね? (指摘受けそうだなぁ…)
型クラスライブラリとか
- GHC: Hackage 調べましょう
- Scala: Scalaz が有名ですね
- FsControl, FSharp.Karma
- Java: Functional Java, highj, free-monad-java
おわりに
variance とか GADTs とか代数的データ型とかパターンマッチとか色々書いていない気がするけれど、気が向いたらで…。
あ、OCaml がないのは書いたことないからです…突っつかれたら勉強します。
F# で高階型のエミュレーション
この記事では、F# で 高階型 (higher kinded types) をエミュレーションすることについて記述します。
本当は 函数型なんたらの集い 2014 in Tokyo - connpass で話そうと思っていたのですが、運営を考えると発表できる気がしなくなった*1ので、記事にしてお茶を濁します。
注意事項
- F# で推奨される実装、ガイドラインから逸脱した実装になっています
- 型安全かどうかは考察しません(時間が足りない)
- この記事をみただけで"F# は残念な言語"という判断を下すのは誤りです
- 専門家ではないので、厳密なことは書けません。生暖かい目で見守ってください。
- Haskell, Scala(z), Java のコードも登場します
参考文献?
- highj - Haskell-style type classes in Java - Google Project Hosting
- ocamllabs/higher · GitHub
- xuwei-k/free-monad-java · GitHub
本記事に登場する FSharp 実装まとめ
本記事で実装した型に幾つか修正、追加を行ったライブラリが下記になります。
pocketberserker/FSharp.Karma · GitHub
問題点: この世界に奴はいない
世の中には高階型というものが存在します。高階型については、
(もりそば)Scalaによる高階型変数 - Higher-kind Generics - ( ꒪⌓꒪) ゆるよろ日記
とかを読んでみてください。
高階型が存在しないとどういう問題点があるのかという話については、
関数を扱えるだけでは、モナドを表現するには不十分過ぎる - scalaとか・・・
を読みましょう。
さて、 F# も高階型をサポートしていない言語の一つです。
抽象化や共通化のみを考える場合、F# には overload や"静的に解決された型パラメータ"を使えば、解決できる部分もあります。 これらの機能を使って実装されたライブラリとしては
があります。
しかし、型コンストラクタで高階型が要求されるような型クラスは、高階型がなければ実装が困難です。*2
解決案: ないなら…作るしかねぇ!
参考文献にあげた highj や higher、 free-monad-java では 高階型をエミュレーションするための型を用意しています。 この方法は、F# でも利用可能です。 本記事では free-monad-java のスタイルを採用して記述していきます。
// Scala の F[A] を表す型 type _1<'F, 'A> = interface end
_1
は 型パラメータを一つ持つ高階型です。
'F
は対象の型を、 'A
はその型がもつ型パラメータを表します。
今回は highj における μ
の代替として判別共用体を用います。
例: Identity
最も簡単な(そして標準に存在しない型の)例として、Identity型を定義してみましょう。
// 同名の判別共用体を用意 // highj の Id.μ 、 free-monad-java の Id.z 相当 type Id = Id // 実際の Id 型 type Id<'A> = { Value: 'A } with interface _1<Id, 'A>
まず、Id 型を表す高階型用の判別共用体 Id を用意します。
次に、実際に利用する Id 型に _1
を実装します。
こうすることで、その型が高階型であることを表現出来ます。
あとは、例えば Functor などを用意してあげれば、
type Functor<'F> = abstract member Map: ('A -> 'B) * _1<'F, 'A> -> _1<'F, 'B> module Functor = // 任意の Functor を対象にできる let map (fa: Functor<_>) f a = fa.Map(f, a)
ダウンキャストによって、それなりに抽象化できます。
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] module Id = // functor は F# の予約語なので使用できない let functor_ = { new Functor<Id> with // fa は _1<Id, 'A> なので、Id<'A> ダウンキャスト可能 member this.Map(f, fa) = (fa :?> Id<_>) |> map f :> _1<Id, _> }
例: Free
ここまでは、F# だと overload と 静的に解決された型パラメータを用いればよい話でした。
しかし、 Free Monad の実装には高階型が必要になるので、型パラメータでなんとかなるとは限りません。 Free Monad については検索したら色々と記事があるので探してください。
Haskell 実装
まずは、Free Monad の Haskell 実装から見てみましょう。 今回は ekmett 氏の free を参考にします。
f
が高階型になっており、 Free 型コンストラクタ内で Free 型を持っています。
Scala 実装
Scala では Scalaz のものが有名です。
S
が高階型となっています。
Haskell での Free 型コンストラクタに対応する Suspend 型コンストラクタをみると
Free を持つことがわかります。
_1 を用いてエミュレーション
Suspend を _1 を使って表現すると、次のようになります。
type private Suspend<'F, 'A> (a: _1<'F, Free<'F, 'A>>) = ...
あとはうまい具合に型を合わせてあげれば、Free Monadの完成です。 これに関しては本記事の内容ではないので、もっと詳しく知りたい方は
JavaでFreeモナドを表現するためのテクニックやexistential type(存在型)の話 - scalaとか・・・
を読んでください。 Java と F# での違いは
- F# は末尾再帰最適化される
- F# は type erasure ではないため、型パラメータの型が異なっていると InvalidCastException
- F# にてきとーに型推論させると、Gosubの型パラメータが obj に推論されて死ぬ(ので、結局明示しないとだめ)
あたりです。
問題点
- mixin がないので、既存の型に 1 を実装できない(Wrapper 型に対して 1 を実装するはめに)
- 明示的にキャストする必要があるので、ダウンキャストやアップキャストの嵐に
次回予告
もみあげ「やった、Free Monadができた...ん?」
GitHub「xuwei-k pushed to develop at xuwei-k/free-monad-java operational monad」
もみあげ「ナンデ!?ワイルドカードナンデ!?」
scodecでmsgpackライブラリを作ってみた
pocketberserker/scodec-msgpack · GitHub
名前は特に思いつかなかったのでそのまんまです。
実装理由
- scalazフレンドリーなmsgpackライブラリがほしかった(建前)
- scodecの勉強のため
- そろそろ一度はscalaのライブラリレベルのコード書かないとなーと思っていた(本音)
必要なもの
scodecに依存しているので、scodecに関連する知識が必要です。具体的には、
- scodec-bits
- scalazの一部(少なくともEither)
- shaplessの一部(HListの使い方は必須。Genericも知っていると便利?)
とかです。
まぁ、Eitherは難しくないですしshapelessもHListを使うことに限れば理解するのに何日もかからないと思うので、そんなにこわくないはずです。
使い方
極力scodecと同じように書けるようにしたつもりです。
import scodec._ case class Point(x: Int, y: Int, z: Int) val pointCodec = (msgpack.int :: msgpack.int :: msgpack.int).as[Point] val encoded: String \/ BitVector = pointCodec.encode(Point(-5, 1024, 1)) // \/-(BitVector(40 bits, 0xfbcd040001)) val decoded: String \/ Point = pointCodec.decode(BitVector(0xfb, 0xcd, 0x04, 0x00, 0x01)) // \/-(Point(-5,1024,1))
pointCodec
の中身がint8
ではなくmsgpack.int
なのが重要な点です。
考えないといけないこと
- extを楽に生成することができない
- 無駄にimplicitを使ってしまっている気がするので外す
- Map周りがこれでいいのかわからない
- IndexedSeqをVectorに差し替えるかも
- case classからjson styleにマッピングする関数を作るかどうか
- パフォーマンス調査
実装時に困ったこと
scodecを調べながらだったので結構時間がかかってしまいました。 README、テストコード、ブログ、最終的にソースコードと読んでいったのでこの作業で2,3日使ったような…?
なお、CodecがMonadでないことはねこはるさんとxuwei-kさんに教えていただきました。ありがとうございました。
あとはScalaの作法がわからず困ったとか、そんな感じです。
おわりに
scodecのコードはわりと読みやすいと思います(Argonautに比べて、ですが)。 その影響で解説記事を書く気力がおきない…ので、情報がほしい方は私に「記事の進捗どうですか」と連呼してください。
http4s 0.2.0の依存ライブラリについてメモ
http4s 0.2.0 時点での話です。 あと、特にぶつかりそうなライブラリのみ対象にしています。
scalazに依存するライブラリ群
http4s 0.2.0時点では、scalaz 7.0.x系に依存したものが使われています。 というわけで、たぶん他のscalazに依存するライブラリも 7.0.x系を使ったほうがいいんじゃないでしょうか。
scalaz-stream、argonaut、specs2、scalaz-scalacheck-binding、scodecとscalazに依存するライブラリが多いのものの、scalaz-streamのscalaz 7.1.x対応版が出る頃には他のライブラリも対応が完了していると思うので、あとはhttp4s 0.3.0のリリースがいつになるか次第ですかねーという感じ。
(json4s関連はjson4s-scalazを使っているわけではないので大丈夫なはず)
scala-logging
scala-logging-slf4j 2.1.2に依存している影響で、scala-logging 3.0.0は使えません。 私はそれに気がつかずどはまりしました…。
- scala-logging 3.0.0はScala2.11のみサポート
- scala-logging 2.1.2がScala2.10とScala2.11の両方をサポート(教えてくださった id:xuwei さんに感謝)
- http4sはScala2.10とScala2.11をサポート
というわけで、当面はscala-logging-slf4j 2.1.2を使いましょう。
メンテされるのかとかはよくわかっていないのでアレですが、2.1.2と3.0.0で機能にそんなに差があるわけではないような気もします。 (3.0.0でLoggingやAbstractLoggingがなくなってるとかその辺りくらい?)
config
typesafe社のconfig 1.0.0が内部で使われてるみたいです。 別に 1.2.1にあげても影響がそんなにあるわけでもなさそうな…?
ScalaのArgonautを触ってみた
最近、 Argonaut: Purely Functional JSON in Scala というライブラリを興味本位で触っているのでメモ。
利用したライブラリのバージョン
"io.argonaut" %% "argonaut" % "6.0.4" "com.github.nscala-time" %% "nscala-time" % "1.2.0"
サンプル
本家サイトのドキュメントを眺めればイメージは掴めると思います。
というわけで、まずはドキュメントを読みましょう。
エンコード・デコード
org.joda.time.DateTime
などの型もデコードしたくなったので試しに定義してみました。
(import は省いてます)
implicit def DateTimeDecodeJson: DecodeJson[DateTime] = DecodeJson.optionDecoder(_.string.flatMap(_.toDateTimeOption), "org.joda.time.DateTime") implicit def DateTimeEncodeJson: EncodeJson[DateTime] = EncodeJson(a => jString(a.toString))
optionDecoder
の第一引数が Json => Option[A]
なので、ここに変換関数を渡す方法でも定義できそう。
Case Classへのデコードなどはドキュメントに書かれているので略。
代数的データ型をエンコード・デコード
|||
を使えば、最初に成功した結果が返るので、表現できそうな気がします。
trait Hoge case class Fuga(foo: String, bar: Int) extends Hoge case class Piyo(buz: Double, qux: Option[String]) extends Hoge implicit def HogeDecodeJson: DecodeJson[Hoge] = jdecode2L(Fuga.apply)("foo", "bar") ||| jdecode2L(Piyo.apply)("buz", "qux")
これ、もっと他に方法がありそう…要調査。
直接関係はしないですが、Optionなどよく使われる型に関しては既にデコーダ・エンコーダが定義されているので、楽ですね。
利点?
Scalazに依存しているので、Scalazに依存しているライブラリとの相性は良いのではないでしょうか。