コンピュテーション式の Tips

F#

この記事は F# Advent Calendar 2014 - connpass の初日の記事です。

12月になってしまいましたね、進捗どうですか？私は駄目です。

タイトルは"コンピュテーション式の Tips"となっていますが、中身は Basis.Core や "Persimmon 内で使われているコンピュテーション式の実装方法を勝手に紹介するというだけです。

はじめに

この記事は 2014/12/01 JST 現在書きかけです。 よって、後々更新したときのために gist で diff を残しておきます。

FsAdvent.2014.md

モナド

  • 目的: Haskellのdo構文をエミュレート
  • 実装に使うもの: monad laws, Return, Bind, ReturnFrom (, Zero)

コンピュテーション式で一番よく知られている(そして誤解するかもしれない)パターン。

do 構文のエミュレーションに必要な最低限のメソッドのみ実装する。

// example
type OptionBuilder() =
  member __.Bind(x, f) = Option.bind f x
  member __.Return(x) = Some x
  member __.ReturnFrom(x: _ option) = x

let option = OptionBuilder()

let l = [10..99]

option {
  let! a = List.tryFind (fun x -> x % 2 = 0) l
  let! b = List.tryFind (fun x -> x % a = 9) l
  return (a, b)
}

フロー制御

  • 目的: 使うキーワードによって後続の計算を分岐させたい
  • 実装に使うもの: State, CPS, (try-with)

これは既に id:bleis-tift さんが詳しく解説しているので、紹介にとどめておきます。

more information: yield and return (poor English ver)

例外

  • 目的: 最小限のBuilderで例外をハンドリングする
  • 実装に使うもの: try-with, custom operator

参考: https://github.com/persimmon-projects/Persimmon/blob/87a83d55602268f43a6d31e04ac47dafa2bd8de4/Persimmon/ComputationExpressions.fs#L74

拡張メソッド

  • 目的: 既存のコンピュテーション式を拡張したい
  • 実装に使うもの: 拡張メソッド
//examle 1
open Basis.Core

type Option.OptionBuilder with
  member this.Source(x) = Result.toOption x
  member this.Source(x: _ option) = x
    
let res = option { return! Success 10 } // Some 10

//example 2
open System.Threading.Tasks

type AsyncBuilder with
  member __.Source(x: Task<_>) = Async.AwaitTask(x)
  member __.Source(xs) = Async.Parallel(xs)

let task =
  async {
    return 1
  }
  |> Async.StartAsTask

async {
  let! x = task
  return printfn "%d" (x + 1)
}
|> Async.Start

async {
  let! xs = [0..10] |> List.map (fun x -> async { return x })
  return printfn "%A" xs
}
|> Async.Start

型によるDSL制御

  • 目的: キーワードの呼び出し順序を固定したい
  • 実装に使うもの: 判別共用体(DU), custom operator, Sourceメソッド

unit

  • 目的: unitとそれ以外の型で挙動を変えたい
  • 実装に使うもの: 判別共用体, Sourceメソッド

例: https://github.com/persimmon-projects/Persimmon/blob/87a83d55602268f43a6d31e04ac47dafa2bd8de4/Persimmon/ComputationExpressions.fs#L19

Quotation Evaluation

query ビルダーが公式サンプルである。

カスタムオペレーター

TODO: write

why reverse?

カスタムオペレーターに関するおまけ。

type SampleBuilder() =
  member __.Yield(()) = Seq.empty
  member __.Yield(x) = x
  member __.For (state, _) = state
  [<CustomOperation("case", AllowIntoPattern=true)>]
  member inline __.Case(source, case) = seq { yield! source; yield case }
  [<CustomOperation("run")>]
  member __.SideEffect(source: _ seq, [<ProjectionParameter>]f: _ * _ -> unit) =
    source |> Seq.iter f

let sample = SampleBuilder()

(*
expected output:
1, 2
3, 4

but was:
2, 1
4, 3
*)
sample {
  case (1, 2)
  case (3, 4) into (x, y)
  run (printfn "%d, %d" x y)
}

なぜかタプルが逆順で出力されるのですよねー…仕様なのかバグなのか。

おわりに

TODO: write

余談

最初は FSharp.Karma や Higher や (未完成の) FreeF の解説を書こうかと思っていたけど、テンションがあがらなかったので断念。 それもこれも FreeF が未完成なのが悪い。 Please give me "higher kinded types"!

コンピュテーション式のカスタムオペレーターで遊ぶ

F#

柿プロジェクトを触っているときに思いついたネタです。

ホモビルダー

日本語を使ってみたかったので作ったもの。 ネタが思いつかなかったのでこのネタに…。

https://gist.github.com/pocketberserker/b0f67590f0bcc615b330

一番最初のカスタムオペレーターの変換に unit を引数に取る Yield が呼び出されます。

t-wada さんのサバンナスタンドを表示したかったが…

ネタがないと言っていたら「サバンナ表示させればよいのでは？」と提案されたので。 しかし、等幅フォントだと残念な結果に…。

https://gist.github.com/pocketberserker/4b748d75835737bf4d82

  • 指定の順序でない場合コンパイルエラーにしたいので、型を1ラインごとにわける
  • オペレーター名をリフレクションで取得する
  • バッククオートでくくらないと使えない識別子を使っていたりします

そんなに難しくないです。

ごちうさ

簡約 λカ娘 巻の七を見てやりたくなった。

https://gist.github.com/pocketberserker/ea1b9897ab9a602126fc

  • 関数を無理やり合成する感じ
  • 呼び出すオペレーターによって変換させたりさせなかったり結合順序を変えたりできる

おわりに

某ガンプラアニメ風に言えば「コンピュテーション式はどんな自由な発想で作ってもいいんだ」

あぁ＾～こころがぴょんぴょんするんじゃ＾～

FsAttoparsecとattoの内部構造が変わった話とか

F# Scala Haskell

私が 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な実装にした場合のパフォーマンス改善はなかなか難しい問題な気がしてます。

*1:初期実装はscala-attoparsecを参考にしていたので本家のコードを読んでなかった

"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を実装する際に使いそうな道具とか

F# Haskell Java Scala

現時点における GHC、Scala、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 くらいは書けるのではないだろうか
  • たぶん同じことをJavaやC#でやれなくはないだろう

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

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

まとめ

つらい楽しい!