2014-09-29

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

F# Scala Haskell Java

この記事では、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 のスタイルを採用して記述していきます。

// 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 を参考にします。

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 を持つ型などの制約をつければ実装できるかも…?

2014-08-16

scodecでmsgpackライブラリを作ってみた

Scala

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に比べて、ですが)。その影響で解説記事を書く気力がおきない…ので、情報がほしい方は私に「記事の進捗どうですか」と連呼してください。

2014-08-06

http4s 0.2.0の依存ライブラリについてメモ

Scala

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

2014-07-31

ScalaのArgonautを触ってみた

Scala

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

2014-06-14

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

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ビルドは最適化されることは把握しているが…

2014-06-11

"JavaでFree Monad"を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> で大丈夫だろーとか思ってたけど、フィボナッチ数列を試していたら実行時にキャスト失敗で落ちた。共変反変の影響かなぁ。

*1:https://github.com/xuwei-k/free-monad-java

2014-05-23

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

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

ダイジェスト

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

当時のスペック

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

いろいろひどい…

前置き

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

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

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

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

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

2010年8月～2011年3月

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

プログラミングF#

作者: Chris Smith,頃末和義,鈴木幸敏
出版社/メーカー: オライリージャパン
発売日: 2010/08/26
メディア: 大型本
購入: 4人クリック: 47回
この商品を含むブログ (19件) を見る

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

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

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

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

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

作者: 荒井省三:いげ太
出版社/メーカー: 技術評論社
発売日: 2011/01/07
メディア: 大型本
購入: 6人クリック: 264回
この商品を含むブログ (26件) を見る

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

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:実際にリリースしたのは今年に入ってからだが…