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に依存しているライブラリとの相性は良いのではないでしょうか。

F# でFree MonadとOperational Monad(未完成)

F#

JavaでFreeモナドを表現するためのテクニックやexistential type(存在型)の話 - scalaとか・・・

JavaでFree Monadを実装する際のテクニックをxuweiさんが解説されているので、F#側も少し説明してみようと考えた次第です。

筆者はCLIジェネリックに詳しくないので、そのあたりゆるく書きます。 変なこと書いてたらごめんなさい…。

なお、関連するつぶやきのまとめは以下にあります(xuweiさん、ありがとうございます)。

F# でFree MonadとOperational Monad - Togetterまとめ

現物

https://github.com/pocketberserker/free-monad-fsharp/tree/4466903b5fa09f4e4c67598248a56fa186b63bf7

この時点での話をします。

記事タイトルに未完成とついている理由は、Operational Monadが正しく動いているという自信を持てないためです(動かしてはみたが、自動テストまでもっていけていない)。

Free.resume

Java版の解説記事で、以下のように書かれています。

Scalazでの現行versionがAny型を使っているのと同じように、Gosubの型パラメータにはjava.lang.Object型を当てはめておけば、(C#やF#はどうなのか知らないが)Javaではtype erasureのお陰で、べつに普通に動きます。

しかし、java.lang.Objectを明示的に使うのは気持ち悪い*3わけです。

F#ではobjをあてはめるとInvalidCastExceptionが発生するため動きません。 クラスでは変位指定できずtype eraseもされないため、型があいません。 ちなみに型推論に任せるとobjと推論されます。

というわけで、基本はJava版と同様の方式をとっています。 Monadic Trampoline | F# Snippetsを参考にすればもっと良い実装になるかもしれませんが、最適化されるのかわかつていない*1ので試してません。

Coyoneda

Coyonedaは、GHCではRank2Types(他の環境はよく知らない)、Scalazでは抽象タイプを用いて実装されています。 しかし、F#にはこれらと同等の機能がありません。 そこで抽象メソッドと型パラメータでの解決を試みましたが、以下のコードはコンパイルできません。

[<Sealed>]
type CoYoneda<'F, 'A>(fi: 'F) =
  abstact member Func : 'I -> 'A

module CoYoneda =
  let apply fi k =
    { new CoYoneda<_, _> with(fi) with
      member this.Func(x) = k x }

型が解決できないためです。 仕方がないので、2つの案を考えました。

  • obj -> 'A で代用する
  • ダウンキャスト + applyするスコープでのみFuncを呼び出すよう心掛ける

現状は後者ですが、これはこれで面倒くさい(型を片っ端から明示しないといけない)ので良かったのか悪かったのか。 よさそうな案があれば教えていただきたく…。

https://github.com/pocketberserker/free-monad-fsharp/blob/4466903b5fa09f4e4c67598248a56fa186b63bf7/FSharp.Monad.Free/CoYoneda.fs#L14

確証がないので何とも言えませんが、今の実装で型推論にたよるとすぐにInvalidCastExceptionになる予感がします。

Operational

Freeモナドを超えた!?operationalモナドを使ってみよう - モナドとわたしとコモナド ScalaでOperational Monadできた - scalaとか・・・

上記記事を参考に実装してみましたが、型略称を定義するのが思ったよりもつらかったのでFreeのままです…。

https://github.com/pocketberserker/free-monad-fsharp/blob/4466903b5fa09f4e4c67598248a56fa186b63bf7/FSharp.Monad.Free/Operational.fs

今のinterpretは、resumeに指定する最初の型パラメータ2つを同じ型にすることでごまかしています。 このためunitを指定する機会が激減し(値をとりたいことのほうが多い)、Free型用のコンピュテーション式で使用可能だった do! がほぼ使い物にならなくなっています。 無意味な値を捨てたい場合はlet! _ = ...で代用して回避しています。 Scalazに存在するIO型(型パラメータがつかないやつ?)を真面目に実装すればなんとかなるかもしれませんが、IO Monadまで実装するのはつらそうだったので諦めました…。

感想

機能が限られた中でこういった型レベルプログラミングを行う場合、Type Erasure方式のほうが融通が利く気がしています。 もちろん型情報が残る場合の利点も多いので、一概にどうこう言えるものではありませんが…。

*1:64bitReleaseビルドは最適化されることは把握しているが…

"JavaでFree Monad"をF# に移植してみた

F#

JavaでFree Monad - scalaとか・・・

上記記事で紹介されているFree Monad in Java*1をF#に移植してみた。

https://github.com/pocketberserker/free-monad-fsharp

実用的かどうかとかF#っぽいかなどは置いておくとして、表現できなくもないようである。 実際にTrampolineが表現できている。

以下、元コードとの差異(たぶん)。

  • resume関数は末尾再帰最適化されてるはず
  • 既存のFSharpFuncに_1を追加実装する方法がないので、F0を定義してofFuncとかでしのいでる
  • 一応コンピュテーション式を用意してみた
  • サボっている部分多数

解説とか

後で書くかも(読みたい人はpocketberserkerを急かすと良いと思う)

課題

gosub2 のキャストが怪しい。

https://github.com/pocketberserker/free-monad-fsharp/blob/8a2c068cfbfea727248e5b75f9a5cf54ba864c0a/FSharp.Monad.Free/Free.fs#L48

Free<'F, obj, 'A> で大丈夫だろーとか思ってたけど、フィボナッチ数列を試していたら実行時にキャスト失敗で落ちた。 共変反変の影響かなぁ。

もみあげは如何にしてF# を学んだか

F#

現実逃避の一環として、私(私をもみあげと呼ぶ人もいる)がどうやってF#を学んだか書き下してみる。

ダイジェスト

  1. その言語に詳しい方からおすすめ書籍を教えてもらって学ぶ
  2. 挫折する
  3. 気が向いたときに1時間弱でできるコードを書いては晒す(ブログ、gistにかいてtwitter放流)
  4. 興味のあるコンテンツを見つけたらとりあえず触ってみる
  5. 気が向いたときにF#ライブラリのコードを読む(当時の私に読めそうなものはFSharpxしか知らなかった。今は選択肢が増えている)
  6. 気が向いたら他言語のライブラリを移植する(他言語について学べる、車輪の再発明にならない、当該ライブラリの知識が増える、などなど)
  7. 気になる勉強会の情報は拾っておく(他言語からヒントを得られることもあるので)
  8. F#言語仕様を読む
  9. コンパイラのコードを眺める

当時のスペック

  • オブジェクト指向プログラミングよくわからん
  • JUnitで簡単なテストは書ける(講義で習った)
  • Mockは存在自体知らなかった
  • 学科内の同期の中ではプログラミング書籍を読むほうではあったが、やさしめの本を数打てば当たる方式で"読んでいた"
  • つまり手を動かすことをおろそかにしていた
  • 講義でJavaを書いた程度 + 休みの時にちょっとしたトイプログラミング
  • C++は大学の講義でSTLまでは学んだ。しかし講義でC++を使わなくなったタイミングで逃亡。
  • OSS???

いろいろひどい…

前置き

私がプログラミング言語のF# *1 を初めて見たのは2010年4月。 つまり、研究室に配属されてPCの環境構築をしていた時だ。

インストール一覧にそっと存在する"F#"。 調べてみるとMSなんとかが開発した関数型言語であるとかなんとか。

「うーん、関数型言語…こわいから近寄らないでおこう」

この頃の私は、講義で触ったLISPにすっかり恐怖してしまい、ちょっと関数型的な何かは避けたい心境だったのだ。 今にして思えば、なんと勿体ないことだろうか!

しかし事実は変えられないので、ここはこれで終わり。

2010年8月~2011年3月

7月にTDDBC名古屋に参加した時、"関数型怖い"から"関数型使ってる人たちの笑顔素敵!なぜにWhy?"とか、"あのレベルでないとプログラマになれないの…?"という別の恐怖に襲われた。

プログラミングF#

プログラミングF#

最初に用いた道具はこの本。 F#を選んだのは偶然だ。 Twitterで(当時フォロワーが30人未満だった)「関数型言語で何か良い本はないだろうか」とつぶやいたとき、一番最初にお勧めされたのがこの本だったから、ただそれだけ。

この本を読むのには2か月以上かかった気がする。 一番理解に苦しんだのはfoldだ。 「なんだよ畳み込みって…フーリエ変換のアレか!?」と、よくわからないことを叫びながらfoldだけで一週間ほど悩んだ記憶がある。 ちなみにコンピュテーション式は挫折した。

その後、F# Advent Calendarに勢いで参加したことも含め、少しコードを書いたりしていた。

ああ、実践F#が発売されたのもこの時期だ。

実践 F# 関数型プログラミング入門

実践 F# 関数型プログラミング入門

この本にも色々とお世話になったが、やはりコンピュテーション式は読んでもよくわからなさそうだったので飛ばした記憶がある。

2011年4月~2011年7月

この空白期間は、大学院の課題でJavaを触ることになったとき、どうせならとGroovyを触っていたことが主な要因である。

2011年8月~2012年3月

講義が終わったあたりから、F#をもうちょっと書かなければと思いトイ・プログラミングを実装していた。 残念ながら私は作りたいものが思いつかないタイプだったので、たまにTwitterで流れてきたお題を試すのが限界だった。 また、講義が再開してからは、いくつかの講義の課題をF#で書いて提出したりもした。

そうそう、年末年始にかけてはKinect SDKで遊んでいた。 わりとミーハーなので、こういうデバイスにはほいほいされてしまうのである。 この時は、C#勉強するのが面倒だし、F#でも動かせるだろうとか言ってた気がする。

年明けのJaSST東京では、bleisさんとセッション中にペアプロ(?)したりもした。 その前の週の大阪の勉強会翌日に、irofさんを二人で取り囲んでF#のコードを強制的に読んでもらったのは懐かしい思い出*2

就職活動の際にコード提出を求められたのでF#のコードを送ったのも良い思い出である。 今見るとひどいコードだけど!


この時期に一度FParsecを学んでみたものの、まだよくわからないしライブラリのコードはカオスで読めない、と叫んでいた。

2012年4月~2012年7月

また空白期間だ。 一体何が起こった?

"すごいHaskell楽しく学ぼう"と積読だったコップ本を読んでいた気がしている。 あと遊んでいた 旅にでていた。

2012年8月~2013年3月

F#に本格的に戻ったのは、FSharpxリポジトリ内にIterateeを見つけた時だ。 HaskellのIterateeを見てもいまいちわからなかっため、F#に同じ概念のものを見つけた私は「読める!読めるぞ!」と言いながら嬉々として遊び始めた。 おそらく、Scalazを知ったのもこの頃だ。

その後は内定した会社からだされていた研修課題にF#+Erlangで挑んでみたり、BKTreeやIntMapを実装したり。
あと、3月の3連休にFsMachinesの大半を実装している*3。 おそらく、Ekmett勉強会のつぶやきを拾っていた時に知って実装したという流れだろう。

2013年4月~2013年10月

就職してからは転職するまでの期間は、実はそんなにF#F#していない。 仕事で使わないというのもあったし忙しくもあったが、それ以上にC++に再チャレンジしたかったのだ。 触り始めた6年前と異なり、C++11もリリースされていたのも大きい。

2013年11月以降

仕事でF#を使う機会が増えたこと、周りのメンバーがF#に詳しいこともあって、F#に触れることが多くなった。

懺悔しておくと、言語仕様をきちんと最初から読んだのはこの時が初である(まだ読みかけだ…)。 少し眺めることはあったが、かいつまんでしか読んでいなかった。

で、結局何をしたのか

抽象化すると

  • 本読んだ
  • コード晒した
  • コード読んだ
  • コード書いた

のローテーションが結論が気がする。

追記: よく読むブログ

たくさん紹介したいのですが、量が多くなるので一部のみ紹介。

余談: なぜFSharpを続けるのか

F#は好きかもしれないが、愛憎入り交じっている。 ちなみにプログラミングが好きなわけでもない(本当は理論専攻したかったが、残念ながら生来の怠け癖と発想力のなさがその道を私に否定させた)。

ではなぜF#か?

  • CLIと呼ばれる基盤は、一部世間曰く『実用的 or 現実的である』
  • 実用的な話をしている場所で理論理論してもいいじゃない。現実舞台で理想を追い求めて何が悪いのか。
  • 車輪の再発明に該当しない可能性が高い
    • 多言語では既に実装されていても、F#にはない可能性が高い
    • "選択の自由"。ライブラリは競い合うほうが良い。

「F#には○○がない」というと、「なら他の言語に変えればいいじゃない」と言われるかもしれない。 しかしだ、そこには"既存"という現実がある。 この現実とバトルすることは、私にはできない。

*1:音楽でのそれは、幼い頃クラシックギターを習っていた際に知った

*2:新世界でシュークリーム串カツを食べたのもこの時か

*3:実際にリリースしたのは今年に入ってからだが…

F# のパーサコンビネータライブラリ事情

F#

F# のパーサコンビネータに関するメモ書きです。 情報が揃ったら、Qiitaに投下するかもしれません。

種類

ここでは3つのライブラリを対象にします。

  • FParsec
  • ParsecClone
  • FsAttoparsec

他にも「これかけよ!」などあればご連絡ください。

FParsec

FParsec は Haskell でポピュラーな Parsec の F# 適応です。

古の時代から存在しているライブラリです(ぉぃ

入力は文字列のみ

https://bitbucket.org/fparsec/main/src/c234349e7b738e09a1b9eb53f5f1ef77d584f09b/FParsec/Primitives.fsi?at=default#cl-20

を見ていただけると分かる通り、FParsec では CharStream を受け取って計算結果を返す関数を Parser として扱います。 CharStream は文字列操作を扱う FParsec 独自の型です。

File や Stream を入力として受け取り、解析を行う関数も用意されています。 しかし、これらの関数には System.Text.Encoding を渡す必要があります。

速い

文字列に特化させただけあってか、かなり高速です。おそらく、

  • CharStream 内ではポインタなどを駆使している
  • コンビネータの内部実装は for や mutable を駆使した泥臭い実装(外部からは immutable に見える)

などが高速化につながっているのではないか、と考えられます。

ドキュメントが整備されている

ドキュメントが充実しています。

日本語チュートリアルが存在する

@ さんの手によって、チュートリアルが日本語に翻訳されています。

http://blog.livedoor.jp/gab_km/archives/1437534.html

また、F# 黎明期から存在するので、FParsec を利用した日本語記事も多数確認できます。

ライブラリ自体のコードを読むには C# の知識も必要

CharStream を始めとして、多くの型が C# で実装されています。これらの実装は FParsecCS.dll に含まれています。

また、 CharStream の実装にはポインタが使われています。つまり、C# のポインタの知識がなければコードが読めません。

ParsecClone

ParsecClone は FParsec の subset clone です。

入力は IStreamP を実装した型

標準で提供されている入力は stringbyte [] (バイナリ)ですが bit (ParsecClone 独自の型)ですが、 IStreamP インターフェースを実装すれば、入力として指定できます。

バイナリ解析は速い

バイナリ解析の入力として使用される BinStream は、内部でキャッシュを持っていたりします。

では StringStream はというと…キャッシュを持っていないので、遅いです。つまり、入力データ型の実装によって速度はまちまちです。

エラー情報が少ない

Parser の適用結果が Option と IStreamP のタプルなので、失敗した場合の情報が少ないです。

また、いくつかの関数では特定の条件で例外を投げる実装になっているため、問題特定が難しい場合があります。

シグネチャが読みづらい

ParsecClone の関数の多くは型が明示されていません。 かといって fsi が定義されているわけでもないので、Visual Studio でカーソルを合わせてみても Parser 型と表示されません。

Parser を合成すると型エラーが読めず苦労する、なんてこともあります。

サンプルコードが面白い

サンプルコードとして、CSVパーサとMP4ヘッダーバイナリパーサが用意されています。

FsAttoparsec

Haskell の Attoparsec を、 F# へと移植したライブラリです。

筆者が(主に現実逃避中に)実装したものです。

入力はいくつかの関数と Monoid を実装した型

length, head, tail, splitAt, span, skipWhile, take, cons 操作を持つ型に対して Monoid を定義すれば、入力として扱うことができます。

遅い

atto の名に反して、遅いです。

  • 1万件の要素を持つJsonデータの解析で、 FParsec と比較して 約10倍差
  • バイナリ解析で、ParsecClone と比較して約10倍差(要再計測)

おそらく、入力データの操作で遅くなっています。改善策を検討中です。

エラー情報が少ない

エラー情報が全くないわけではありませんが、原因特定はちょっと大変かもしれません。 ここは Attoparsec 所以なので、仕方ないかなと諦めています。

Trampoline

継続渡しスタイルを用いて実装しているのですが、x64 環境での Release ビルドでしかメソッド呼び出しの最適化が(おそらく)行われない関係で、他の環境ではスタックオーバーフローを引き起こします。 これを回避するため、Trampoline を使っています。

サンプルコード

現時点でLTSVパーサ、Jsonパーサが存在します。

Pure FSharp

F# のみで実装しています。 また、ほぼ Attoparsec (もしくは scala-attoparsec およびその fork である atto )と同様の実装になっているため、HaskellScala 使いの方にもやさしいです。

まとめ

選択肢が増えることは、良いことだなって。