"F# でのテスト用 DSL について考える"で書いたコンピュテーション式

発端や流れに関しては

F# でのテスト用 DSL について考える — a wandering wolf

を読んでください。

本記事では私が実装してみたコンピュテーション式についてゆるく説明します。

先に読むべきもの

詳説コンピュテーション式 - ぐるぐる~

コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走

第1版

https://gist.github.com/pocketberserker/40006f8da7e195924713/092438c92ed1de1cb65809876fdddcd15c2ad401

  • do! で失敗したら移行を実行しない
  • それ以外はとりあえず実行する

みたいな話があったので、ぱっと思いついた Source メソッドを悪用する方針で攻めることにしました。 Source メソッドオーバーロードすることで、unit型かそれ以外の型かをBindメソッドなどに伝えます。

このタイミングはここで時間切れだったので、中途半端な状態で公開しました。

第2版

こういう話と、bleis さんの実装した

TestBuilder.fs

を眺めながらいじったコードが以下になります。

https://gist.github.com/Gab-km/86dd730a8d8e407a699f に触発された何か

Bindメソッドの基本はbleisさんのものを借りつつ、Value に入力型を持たせることで失敗したアサーション以降のアサーションも実行できるようにしました。 Unchecked.defaultof を使っているので危険では?という意見もあるかもしれませんが、 `let! _`` で捨てる前提なので、これでいいかな、と。

第3版

とはいえ、 let! _ はあまりきれいじゃない気がしますし、どうせなら yield! のほうがよさそうだよね、ということでさらにいじりました。

https://gist.github.com/Gab-km/86dd730a8d8e407a699f に触発された何か

過去に紹介した、引数で状態を引き回す方法を使ってCombineを実装することにより、 yield! を連続で呼び出すことが可能です。

Sourceメソッドで注意すべき点

Sourceメソッドはそこそこ変換に現れるので、型合わせるのが簡単ではないです(そこまで難しいわけでもないですが)。

最終版の場合だと、Source メソッドで結果、型情報、状態を生成して型をあわせつつ、YieldFromやReturnFromで状態のみ書き換えるとかしてしのいでいます。

おわりに

実用化?知らない子ですね。

#関数型なんたら という勉強会をやります(ニコ生もあるよ!)

2014年10月25日土曜日に関数プログラミング的な交流会(?)のような勉強会を開催します。

函数型なんたらの集い 2014 in Tokyo - connpass

なぜ1週間前のこのタイミングで告知記事を書いているかというと、二木ニコ生放送があることを伝えたいからです(ドワンゴスタッフの方々、ありがとうございます!)

函数型なんたらの集い 2014 in Tokyo - 2014/10/25 11:30開始 - ニコニコ生放送

当日見れそうにない方も、アカウントがあるならタイムシフト予約しておくと便利かもしれません。

ちなみに

この勉強会の発端は、だいたい毎年行われている"函数プログラミングの集い"が今年はないという話をきいてちょっと残念に思っていたところ、

「野良でやってもいいんじゃない」

という話をTLで観測したので、会場があればやりたいなーと思っていました。 そんなときに

Scalaz勉強会を開催しました - scalaとか・・・

この記事の最後のほうにドワンゴさんの会場の話が書かれていたことを思い出したので、ScalaMatsuriのときに相談した、という流れです。

各言語でtype classesを実装する際に使いそうな道具とか

現時点における GHCScala、F#、Java の type classes 実装に使う道具比較をメモしておきます。

言語比較したいわけではなく、論争を繰り広げたいわけでもないのであしからず。

あとてきとーに書いてる感は否めないので、間違っている言葉、表現、概念などあれば適宜突込みをお願いします。

高階型

  • GHC: m a
  • Scala: M[A]
  • F#: インターフェース _1<'M, 'A> を用意して擬似的に表現
  • Java: インターフェース _1<M, A> を用意して擬似的に表現

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つある場合

Scalaは今後 type lambdas というシンタックスシュガーが入るかもしれない?

このあたりは F# が不利。 型をいい感じにできるのはもしかしたら type erasure 方式の利点かもしれない。

https://github.com/pocketberserker/FSharp.Karma/blob/9d6aab537793875727f8625acf146e9cbf9931cf/FSharp.Karma/CoYoneda.fs#L13

これと

https://github.com/xuwei-k/free-monad-java/blob/aa7ec1c2897d0982c406524082cd9f8c6fefed37/free/src/main/java/free/Coyoneda.java#L3

これとかの比較だと、F# は型が残る上に変位指定ができない(できるならだれか教えてください)から、下手に obj も使えなくて悲しいことになっていたりします。 Java版はそのあたりすっぱり割り切っている。

型推論

これに関してはあまり書きたくない…。

どの言語にもあるけど、どこまで推論されるかは言語次第だよ、くらいでいいですかね? (指摘受けそうだなぁ…)

型クラスライブラリとか

  • GHC: Hackage 調べましょう
  • Scala: Scalaz が有名ですね
  • FsControl, FSharp.Karma
  • Java: Functional Java, highj, free-monad-java

おわりに

variance とか GADTs とか代数的データ型とかパターンマッチとか色々書いていない気がするけれど、気が向いたらで…。

あ、OCaml がないのは書いたことないからです…突っつかれたら勉強します。

ermine-parser(scala-trifecta?)の F# 移植を試みたが…

F#

ermine-parser という、Haskell の trifecta を参考に実装されたパーサコンビネータライブラリが Scala には存在します。

ermine-language/ermine-parser · GitHub

今回はこれの F# 移植を試みました。

注意事項

  • F# で推奨される実装、ガイドラインから逸脱した実装になっています
  • この記事をみただけで"F# は残念な言語"という判断を下すのは誤りです

現時点

pocketberserker/fsharp-trifecta · GitHub

現状をまとめると、

  • 型はあった
  • がんばれば動くかもしれない
  • 壊滅的な実行速度だろう
  • 移植元にあるけど移植できていないコンビネータが5個くらい、モジュールが1個
  • とはいえ Json Parser くらいは書けるのではないだろうか
  • たぶん同じことをJavaC#でやれなくはないだろう

といったところです。 テスト書いてないとかお前それ @t_wada の前でも同じこと言えんの? と言われかねないですが…。

Scalaz の機能の多さを改めて知る良い機会でした。

まとめ

つらい楽しい!

F# で高階型のエミュレーション

この記事では、F# で 高階型 (higher kinded types) をエミュレーションすることについて記述します。

本当は 函数型なんたらの集い 2014 in Tokyo - connpass で話そうと思っていたのですが、運営を考えると発表できる気がしなくなった*1ので、記事にしてお茶を濁します。

注意事項

  • F# で推奨される実装、ガイドラインから逸脱した実装になっています
  • 型安全かどうかは考察しません(時間が足りない)
  • この記事をみただけで"F# は残念な言語"という判断を下すのは誤りです
  • 専門家ではないので、厳密なことは書けません。生暖かい目で見守ってください。
  • Haskell, Scala(z), Java のコードも登場します

参考文献?

本記事に登場する FSharp 実装まとめ

本記事で実装した型に幾つか修正、追加を行ったライブラリが下記になります。

pocketberserker/FSharp.Karma · GitHub

問題点: この世界に奴はいない

世の中には高階型というものが存在します。高階型については、

(もりそば)Scalaによる高階型変数 - Higher-kind Generics - ( ꒪⌓꒪) ゆるよろ日記

とかを読んでみてください。

高階型が存在しないとどういう問題点があるのかという話については、

関数を扱えるだけでは、モナドを表現するには不十分過ぎる - scalaとか・・・

を読みましょう。

さて、 F# も高階型をサポートしていない言語の一つです。

抽象化や共通化のみを考える場合、F# には overload や"静的に解決された型パラメータ"を使えば、解決できる部分もあります。 これらの機能を使って実装されたライブラリとしては

gmpl/FsControl · GitHub

があります。

しかし、型コンストラクタで高階型が要求されるような型クラスは、高階型がなければ実装が困難です。*2

解決案: ないなら…作るしかねぇ!

参考文献にあげた highj や higher、 free-monad-java では 高階型をエミュレーションするための型を用意しています。 この方法は、F# でも利用可能です。 本記事では free-monad-java のスタイルを採用して記述していきます。

// ScalaF[A] を表す型
type _1<'F, 'A> = interface end

_1 は 型パラメータを一つ持つ高階型です。 'F は対象の型を、 'A はその型がもつ型パラメータを表します。

今回は highj における μ の代替として判別共用体を用います。

例: Identity

最も簡単な(そして標準に存在しない型の)例として、Identity型を定義してみましょう。

// 同名の判別共用体を用意
// highj の Id.μ 、 free-monad-java の Id.z 相当
type Id = Id

// 実際の Idtype 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 MonadHaskell 実装から見てみましょう。 今回は ekmett 氏の free を参考にします。

https://github.com/ekmett/free/blob/a2008da7fe75b4cc80904d9bd3275e5772a28c91/src/Control/Monad/Free.hs#L103

f が高階型になっており、 Free 型コンストラクタ内で Free 型を持っています。

Scala 実装

Scala では Scalaz のものが有名です。

https://github.com/scalaz/scalaz/blob/2f80af1f512d80a2a531c1859f58b09f4002da1d/core/src/main/scala/scalaz/Free.scala#L50

S が高階型となっています。 Haskell での Free 型コンストラクタに対応する Suspend 型コンストラクタをみると

https://github.com/scalaz/scalaz/blob/2f80af1f512d80a2a531c1859f58b09f4002da1d/core/src/main/scala/scalaz/Free.scala#L17

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

もみあげ「ナンデ!?ワイルドカードナンデ!?」

*1:想定以上に大規模になった...

*2:試していないので絶対にできないとは言えない。もしかしたら Map を持つ型などの制約をつければ実装できるかも…?

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にあげても影響がそんなにあるわけでもなさそうな…?