沖縄に行ってきました！

社員旅行で沖縄に行ってきたので、その報告です。

お分かりいただけただろうか？

＿人人人人人人人人人人人人人＿
＞　Javaプログラミング講座　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣

報告は以上です。

Ruby嫌いがアンダースタンディングコンピュテーションを読んで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

一番最初にはっきりさせておきますが、Rubyは嫌いな言語です。 が、この本はRubyが嫌いな自分でもいい本だと言える*1本でした。 自分が対象読者に入っているかどうかは実際に読んでみるまで微妙かな、と思っていましたが、とても楽しめました。 以下、書評です。

Rubyという選択

説明用のコードとして本書はRubyを使っていますが、 これに関してはその理由が1章にあります。

私はその明瞭さと柔軟さに魅かれてRubyを選びました

また、続けて

本書にはRuby独自の機能に依存しているところはありません。 そのため、もしあなたにとってわかりやすくなるなら、本書のサンプルコードをお好みの言語、特にPythonやJavaScriptといった動的言語に変換してもよいでしょう。

とあります。

ここで注目すべきは「特にPythonやJavaScriptといった動的言語」という風に、静的型付き言語を省いている(少なくとも積極的に推奨はしていない)点です。 で、これにはまっとうな理由がある(少なくとも自分は納得できる)のですが、この説明だけだとそれが全然わからないんですよね。 その理由をここに書いてしまうのは、ある意味この本を読む楽しさの一部を削いでしまうことになりかねない気もするのですが、そうなったとしてもこの本は依然として面白いであろうということで、書きます。 もちろん、「こういう理由があるからだ」という風に書きますが、すべて想像です。

対話環境があり、モンキーパッチングが可能であり、定数が削除できる

この本の素晴らしい点の一つに、実際に対話環境で一つ一つコードを入力していき、動作が確認できるというのがあります。 対話環境がない言語の場合はいちいち実行し直す必要があり、しかもこれまでに見てきた最早不要の出力(ようはゴミ)も表示されてしまいます。 面倒に思うかもしれませんが、きちんと理解したい方はRubyの環境を整えて*2、実際に対話環境でコードを入力して結果を確認しつつ読み進めるのがいいでしょう。

また対話環境前提で構成されているため、「以前定義したクラスのコードに戻ってこのメソッドを追加しましょう」ということができません。 そのため、モンキーパッチングができるような言語でないと実際に試しながら読むのはつらいです。

更には、「以前定義したクラスのコードに戻ってこの部分を書き換えましょう」もできません。 なので、定数を削除(というより、クラスを削除)できる必要があるのです。

もちろん、モンキーパッチングの代わりに別のモジュール内に既存のモジュールと同じものを定義してそれをopenするだとか、定数の削除の代わりにシャドウイングを使う等、このあたりはこの機能そのものがないと厳しいというわけではありません。

evalを持つ

eval的な、渡されたコードを実行する仕組みが欲しくなる場所があります。 本書で変換対象として挙げられていた言語(や、動的言語の多く？)は、eval的なものが用意されています。 これが気軽に使える言語でないと、evalを自分で実装・・・ということになりかねません。 すると当然のことながらすべてを本文に載せることは出来なくなり、本文のコードで試せないものができてしまいます。

もちろんこれにも回避方法はありますが、説明をシンプルに保つ、という点において本書がRubyのような言語を採用したのは正解だったと思います。

ちなみに、ここで挙げた理由を持つPythonやJavaScriptが本書の言語として選ばれなかった理由としては、著者の好みもあるでしょうが、一番の理由はP.188からP.191な気がしています。

クラス分割の教材という観点

Rubyのメタプログラミング的な技法などを使えば本書のコードはよりDRYに書けるでしょう。 ですが、それをすることなく一般的なOOPLで扱える程度の記述にとどめているため、他のOOPLでもクラス分割のひとつのお手本としてみることができます。

そういう観点でのオススメは3章です。 3章をすべてやると(正確には3.3まで)、基本的な機能をもった正規表現の処理系が手に入ります。 正規表現の処理系を「じゃぁ作って」と言われても、難しいと感じるプログラマは多いと思います。 3章では、それをボトムアップで作っていきます。 この際のクラスの分割方法や命名のセンスは素晴らしいです*3。

3章の動機づけの弱さ

3章はコードは素晴らしいのですが、構成にもったいなさを感じました。 最終的には基本的な機能を持った正規表現の処理系が手に入るにもかかわらず、導入部分には

計算する機械というアイディアにある本質を明らかにし、それがどんな用途に使えるのか紹介しながら、単純なコンピュータにできることの制限について調べます。

としかないのです。 3章の最初の方はこの本の対象読者にとって「これが一体何に使えるんだ・・・」という感じの話が続きます。 人によっては退屈に感じて途中でやめてしまうかもしれません。 なので、個人的には最初の方に「この章では単純な例から始め、基本的な正規表現の処理系を作り、単純なコンピュータでも役に立つことを示します」くらいの人参をぶら下げた方がよかったのではないかな、と思います。

6章のバランス

この本は非常に内容の詰まった本であり、技術書の中ではページ数も少な目か普通程度のものです。 これだけの内容をこれだけ分かりやすくこれだけのページ数に収めているのは驚異的だと思うのですが、6章は少しアンバランスな気がしました。 もう数ページ増やして、リストの説明をより詳細に行ってもよかったのではないかな、と思うのです。 これまで丁寧に解説をしていたのに、リストでは解説なしに5つの関数が与えられてあとはその動作の確認にとどまっています。 本書のもったいないと思ったところで一番大きな部分が(言語の話ではなく)ここでした。

日本語としての読みやすさ

とても読みやすかったです。 「的」をあまり使わない方針なのか、一部ひっかかりを覚えた部分もありますが、好みの問題でしょう。 何か所か原文を確認したくなったところはありましたが、とても少ないです。 意味がよく分からないな、と思った個所は一つだけです。 P.169に、

ブール値を将来のコードが読める決まったデータとして考えるのではなく、2つの選択肢を引数として呼び出し、1番目と2番目の選択肢のどちらかを選ぶコードとして、直接的に実装しましょう。

とありますが、この前半部分の意味が分かりませんでした。 ただ、ここが分からなくても後半部分だけで実際にやりたいことはわかるため、それほど問題とも思いませんでした。

本書を読むために必要なレベル

人は自分がわかっていることに対してそのレベルを低く設定しがちな気がします。 「わかっている人にはわかる説明」というのはいくつもあり、分かってしまえばその説明で確かに十分だ、と思ってしまうことはそれなりにあります。

自分はある程度知識がある状態でこの本を読んでいるため、本書を読むために必要なレベルを本来よりも低く見積もってしまう可能性があります。 という言い訳を置いたうえで、この本を読むために必要なレベルはそこまで高くないと感じています。 ただし、最初の方にも書きましたが「実際にコードを試しながら読む」のを前提として、です。 逆に、実際に試さずに「難しかった」というのは、この本の読み方としては難易度の高い方法を選んだからかもしれませんよ？

汚れ？

P.210ページの右下付近、「partial」の「a」の上にななめ線が入っていました。 自分の周りの3冊を確認したところ、3冊すべてで入っていたので、多くの本で同じようなものが入っているでしょう。 内容には関係ない話なのでこれがあるからと言って本書の価値が下がるわけではありませんが。 むしろ、将来直った場合には自慢ポイントになるかも？

全体

全体を通して、「そういう説明をするのか、なるほど」と感じた個所が多い本でした。 これまで理解できていなかった部分が理解できるようになったり、新たな知識(薀蓄的なもの)が知れたりして勉強にもなりました。 Ruby嫌いは直りそうにありませんが、この本は好きになりました。

追記

サポートページはGithubなんですね。 そして、Issue 1に登録されていました。

次に読む本がWikiとしてまとめられているのも素晴らしいです。

*1:Rubyを使っているというだけですでにマイナスポイントからのスタートであるにも関わらず、いい評価

*2:好きな言語にコンバートしつつ、でもいいでしょうが、その場合でも本文を読み飛ばさずに進めた方が楽しいと思います。

*3:ただし、正規表現の処理系としてのクラス分割や名前付けが素晴らしい、という話ではないです

TypeProviderについて、勝手に補足

昨日行われたF# Meetup in TokyoのPart 1で@kos59125さんがTypeProviderに関する素晴らしい発表をしてくれました。

今日の発表資料アップロードしました。 commpass からもアクセス可能です。 http://t.co/XrdiVppTpM #fsugjp

— kos59125 (@kos59125) 2014, 8月 3

TypeProviderを作りたい場合に、最初の入り口として素晴らしい発表資料だと思います。 何より、日本語で読めるのがすばらしいですね！

この資料について勝手に補足します。

ProvidedTypes.fsについて

ProvidedTypes.fsというのは、TypeProviderを作るうえであると便利なものを提供してくれる素敵なファイルです。 正直、これがない状態でTypeProviderを作るのは至難の業であり、事実上必須のファイルです。

しかし、このファイルは資料にもある通り、F# 3.0 Sample Packの中にあるものをTypeProviderを提供する各ライブラリがコピーして使っているという状況です。 さらに、各々がこのファイルをいじくり、独自の進化を遂げているような状態になっています。 これは、F# 3.0 Sample Packのリポジトリが全然更新されないので仕方ないと言えば仕方ないです。

この状況を打破する可能性となるプロジェクトとして、FSharp.TypeProviders.StarterPackというものがあります。 このプロジェクトではNuGetパッケージを提供しており、NuGet参照としてこれを追加するだけでProvidedTypes.fsが自分のプロジェクトに追加されます。 まだ試してはいませんが、NuGetパッケージの更新をすれば、最新版に置き換えてくれたりするのでしょう。

消去型の使い道

20枚目に載っている「消去型」ですが、発表では「ほとんど使わないのでunitでもいい」という風に説明されていました。 こいつの使い道ですが、例えばExcelHouganshiTypeProviderでは

ProvidedTypeDefinition(asm, ns, typeName, Some typeof<ExcelFile>, HideObjectMethods = true)

引用: Houganshi.fs

のように、ExcelFileという型を指定しています。 こうすると何が嬉しいかと言うと、

type MyHouganshi = Houganshi<"Def.fs">

let h = MyHouganshi("sample.xls", NPOI.NpoiBook.Load)
(* hを使った操作 *)
h.Save()

と書けます。 最後の行のSaveメソッド呼出しは、ExcelFileが持っているメソッドです。 全てをProvidedMethodで定義するのではなく、生成する必要のないものは消去型に指定した型に定義すると便利です。

他にも、既存の型を元にしたTypeProviderを作る場合、既存の型を受け取る関数にTypeProviderによって提供された型のインスタンスも渡せると便利ですよね。 そういう場合には、既存の型を消去型として指定することになります。

生成型について

TypeProviderには消去型と生成型という2つの種類があります。 発表されていたのは、消去型についてでした。 自分も最近までは消去型のTypeProviderしか作っていなかったのですが、 最近生成型の有用さに気付いたので書いておきます*1。

消去型の欠点

多くのケースでは、消去型で問題ありません。 しかし、消去型は「型が提供される」といってもILレベルではその型は消えているので、 「提供された型」自体やその型情報が欲しい場合は消去型では対応できません。

そこで使えるのが生成型のTypeProviderです。

生成型のTypeProviderの作り方

参考になるのは、F#の標準ライブラリとして提供されているEdmxFileや、SqlDataConnectionの元となる、 DataProvidersです。 このTypeProviderは、一つのTypeProviderで複数の似たTypeProviderを提供するような構成になっており、このテクニックは消去型でも参考になると思います*2。

生成型のTypeProviderで提供される型は、実際にどこかのアセンブリに存在する必要があります。 DataProvidersでは、最終的にcscを呼出すことで実際にdllを作り、 生成したdllを読み込んでいます。

他にも、ProvidedTypeDefinitionのIsErasedプロパティをfalseに設定する必要もあります。

生成型のTypeProviderの活用例は、アイディアがあるので近いうちに見せれたらな、と思います。

*1:ちなみにVisual Studio 2012がVisual Studio 11 Developer Previewだったころには、情報がなさ過ぎて生成型の方を使っていました。そのときとはGenerateという属性が型を提供される側で必要だったのですが、現在はこの属性は消えているようです

*2:ただし、その場合ProvidedTypes.fsのTypeProviderForNamespacesを継承せずに、ITypeProviderやIProvidedNamespaceを自分で実装する必要がある

値制限

なんかTLで偶然そんな話題があったので。 コードはF#です。

まずrefについて

値制限の話題に行く前に、refについて説明します。 refは、「変更可能な値」を実現するために使える型で、大体こんな感じに実装されています。

type 'a ref = { mutable contents: 'a }
(* refの生成 *)
let ref x = { contents = x }
(* refが格納している値を参照 *)
let (!) x = x.contents
(* refが格納している値に再代入 *)
let (:=) x y = x.contents <- y

これによって、以下のようなコードが書けます。

let a = ref "hoge"
printfn "%A" !a

a := "piyo"
printfn "%A" !a

これを実行すると、hogeとpiyoが出力されます。 aの指す値が途中で変わっているということですね。

では、こんなコードは許されるでしょうか？

let xs = ref []

これが許されるとするならば、xsの型は'a list refとなるでしょう。 ではさらにコードを追加してみましょう。

(* xsの型が'a list refとするならば・・・ *)
let xs = ref []

let f (ints: int list) =
  (* xsは'a list refなんだから、これは合法 *)
  xs := ints

let g (strs: string list) =
  (* xsは'a list refなんだから、これは合法 *)
  xs := strs

あるぇー？fを実行したらxsの中にはint listが、次にgを実行したらxsの中にはstring listが入っていることになってしまう！ 静的な型とはいったい何だったのか・・・

値制限とは

と言うことで、この問題を回避するために値制限と言うものがあります。 要は、

let xs = ref []

を自動ジェネリック化しない、ということですね。

(書きかけ。あとで何か書くかも？)

JavaでTupleってみる

可変長な型変数の表現より、タプルの話です。

.NETのタプル

.NETでは、型引数の数が違うクラスを定義できるので、Tupleという名前で7要素まで対応しています。

public class Tuple<T1> { ... }
public class Tuple<T1, T2> { ... }
public class Tuple<T1, T2, T3> { ... }
public class Tuple<T1, T2, T3, T4> { ... }
public class Tuple<T1, T2, T3, T4, T5> { ... }
public class Tuple<T1, T2, T3, T4, T5, T6> { ... }
public class Tuple<T1, T2, T3, T4, T5, T6, T7> { ... }

そして、各要素にアクセスするために、Item1, Item2のようなプロパティを使います。

さて、では.NETのタプルは8要素以上は対応していないかと言うと、そうではありません。 タプルのインスタンスを作るためには、Tuple.Createというメソッドを使って作るのが楽です。 そしてこのTuple.Createは、なんと8引数版まで用意されているのです。

var t = Tuple.Create(true, 2, 3.0, "4", new[] { 5 }, 6M, 7L, 8);

このtの型は、こうなります。

Tuple<bool, int, double, string, int[], decimal, long, Tuple<int>>

実は、Tupleは8番目の型引数として、「残りの要素を保持するタプルの型」が受け取れるようになっています。 ちなみにTuple<T1>という謎のクラスはこの時のみ使われるクラスです。

public class Tuple<T1, T2, T3, T4, T5, T6, T7, TRest> { ... }

「残りの要素を保持するタプル」にアクセスするためには、Item8ではなく、Restという名前のプロパティを使います。 そのため、8要素タプルの8番目の要素にアクセスしたい場合は、

var value = t.Rest.Item1;

となります。 さてさて、ここからが.NETの残念なところなのですが、実は9要素以上のタプルを作る簡単な方法は用意されていません*1。 ので、コンストラクタを使うことになります。

var t = new Tuple<int, int, int, int, int, int, int, Tuple<int, int>>(
    1, 2, 3, 4, 5, 6, 7, Tuple.Create(8, 9));

コンストラクタの型パラメータは省略できないので、悲惨なことになっていますね・・・ これは、Tuple.Createの8要素版が8要素タプルを作るためではなく、ネストしたタプルを作るためのヘルパーになっていればもっと楽が出来たのです。

var t = Tuple.Create(1, 2, 3, 4, 5, 6, 7, Tuple.Create(8, 9)); // こうはなっていない

残念すぎる・・・

Restという考え方

さて、.NETのタプルは残念ですが、「足りない部分はRestで」というのはどこかで聞いたことのあるような話です。 そう、コンスセルですね！

ということで、コンスセルの考え方を使ってタプルのないJavaにタプルを作ってみましょう。 まずは、コンスセルの終端を表すためのクラスを導入します。 以降では、特にパッケージとか書きませんけど、全部同一パッケージに入っていると思ってください。

public final class TupleNil {
    static final TupleNil nil = new TupleNil();
    private TupleNil() {}
}

簡単ですね。 こいつは状態を持っておらず、インスタンスも外部からは生成できず、 さらには唯一の静的フィールドであるnilもパッケージプライベートなので、 パッケージ外からはこのフィールドにすらアクセスできません。 これだけでは本当に全く何の役にも立たないクラスです。

次に、2つの型パラメータを取って実際に要素を保持するクラスを作ります。

public final class TupleCons<T, Rest> {
    public final T value;
    public final Rest rest;

    TupleCons(T value, Rest rest) {
        this.value = value;
        this.rest = rest;
    }
}

これも簡単ですね。 単に、値を2つ持っているだけのクラスです。 このクラスのvalueに値が、restに残りの要素を表すものが格納されます。

コンストラクタがパッケージプライベートなので、パッケージ外からこのクラスのインスタンスを生成することはできません。

最後にタプルを作るためのメソッドを持ったクラスです。

public final class Tuple {
    private Tuple() {}

    public static <T> TupleCons<T, TupleNil> singleton(T value) {
        // こことか
        return new TupleCons<T, TupleNil>(value, TupleNil.nil);
    }

    public static <T1, T2, Rest> TupleCons<T1, TupleCons<T2, Rest>> cons(T1 value, TupleCons<T2, TupleNil> rest) {
        // ここってダイアモンド演算子使えるんですか？使えそうだけどJavaとかわかりません＞＜
        return new TupleCons<T1, TupleCons<T2, Rest>>(value, rest);
    }
}

あとは、これを使ったコードです。

TupleCons<Integer, TupleCons<String, TupleNil>> t2 = Tuple.cons(42, Tuple.singleton("hoge"));
System.out.println(t2.value); // 42
System.out.println(t2.rest.value); // hoge

やったー！(何が

まとめ(ない)

• .NETのタプルは割と現実見て、7要素までは自然に扱える
  • 大量要素のタプル使うな
  • でももし扱う場合があるといけないから、一応対応しとくぜ！
• .NETのTuple.Createはクソ
  • 8要素版をなぜそういう形で用意したし
  • 9要素以上のタプルを作りたい場合はコンストラクタで頑張るしかない
  • それLangExtならCreate.Tuple(1, 2, 3, 4, 5, 6, 7, 8, 9)でできるよ！
  • それF#なら(1, 2, 3, 4, 5, 6, 7, 8, 9)でできるよ！
• タプルってコンパイル時のリスト(コンスセル)だよね！
  • Javaでそういう実装してみた
  • 元記事が後ろに後ろに拡張していくのに対して、こっちは(consで)前に前に拡張していくという違いがちょっと面白い
  • 元記事がインスタンスメソッドで拡張していくのに対して、こっちはクラスメソッドで拡張していくのもちょっと面白い
    • インスタンスメソッドにもできるけど、キモイことになる(字面上は後ろに書いたものが前に追加される)のでやめた
  • 実用性？しりませんなぁ

*1:まぁ、そんなタプル作るなと言われればその通り、としか言えないですが

コンピュテーション式におけるreturnとyield

今日、id:htid46 とF#の話をしつつ帰った時のまとめです。

前提条件

次の2つのエントリを読んでいることが前提です。

1. 詳説コンピュテーション式 - ぐるぐる～
2. コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走

returnとyieldの変換規則

先日のエントリでも書いたように、ReturnとYield、ReturnFromとYieldFromは全く同じ変換のされ方をします。

T(return e, C) = C(b.Return(e))
T(yield e,  C) = C(b.Yield(e))
T(return! e, C) = C(b.ReturnFrom(src(e)))
T(yield! e,  C) = C(b.YieldFrom(src(e)))

つまり、ReturnもYieldも同じ実装にしたとしても、コンパイルは通ります。 ということは、そのコンピュテーション式により合うと思う方を実装すればいい・・・？

returnの意味とyieldの意味の違い

ところで、returnとyieldではそれを使ったコードの持つ意味が違うように思えます。 例として、listコンピュテーション式を作ったとしましょう。

let f x = list {
  if x = 0 then
    return -1
  return 1
}
let g x = list {
  if x = 0 then
    yield -1
  yield 1
}

let f0, f1 = (f 0, f 1)
let g0, g1 = (g 0, g 1)

さて、f0, f1, g0, g1のそれぞれの値は、どうなっていてほしいでしょうか？

こうなっていることを期待しませんか？

val f0 : int list = [-1]
val f1 : int list = [1]
val g0 : int list = [-1; 1]
val g1 : int list = [1]

つまり、returnはそこで処理を打ち切るけど、yieldは打ち切らない、という違いがあるように思うのです。 これ、C#で考えてみた場合、yield breakとyield returnの関係に似ていませんか？

F#にはyield breakがない

そういえばありませんでした。 が、OptionBuilderでの実装を使うと、returnがyield breakの代わりになるのでは！？

ということで、こういう実装を考えてみました。

open System
open Basis.Core.ComputationExpr

(* 最初にpredを満たさなかった要素は結果に含めるtakeWhileの別バージョン *)
module Seq =
  let takeWhileButFirst pred xs = seq {
    let cont = ref true
    use itor = (xs :> _ seq).GetEnumerator()
    while itor.MoveNext() && !cont do
      let x = itor.Current
      if not (pred x) then
        cont := false
      yield x
  }

type ListBuilder internal () =
  member this.Zero() = [], Continue
  (* returnはBreak、yieldはContinue *)
  member this.Return(x) = [x], Break
  member this.ReturnFrom(xs: _ list) = xs, Break
  member this.Yield(x) = [x], Continue
  member this.YieldFrom(xs: _ list) = xs, Continue
  (* fしていって、Breakが出たら後ろは捨てる(isBreakをtrueにしたうえでfalseを返す) *)
  member this.Bind(xs, f: _ -> _ list * FlowControl) =
    let isBreak = ref false
    let res =
      xs
      |> Seq.map f
      |> Seq.takeWhileButFirst (function _, Continue -> true | _ -> isBreak := true; false)
      |> Seq.collect fst
      |> Seq.toList
    (res, if !isBreak then Break else Continue)
  (* Continueだったらrestを実行してappend、Breakだったらrestは捨てる *)
  member this.Combine((x: _ list, cont), rest: unit -> _ list * FlowControl) =
    match cont with
    | Break -> x, Break
    | Continue -> let rest, cont = rest () in List.append x rest, cont
  (* 以降、OptionBuilderと型以外は同じ定義 *)
  member this.While(guard, f) =
    if not (guard ()) then this.Zero()
    else let x = f () in this.Combine(x, fun () -> this.While(guard, f))
  member this.For(xs: #seq<_>, f) =
    this.Using(
      xs.GetEnumerator(),
      fun itor -> this.While(itor.MoveNext, fun () -> f itor.Current))
  member this.Delay(f: unit -> _ list * FlowControl) = f
  member this.Run(f) = f () |> fst

let list = List.ListBuilder()

Bindは複雑ですが、まぁ、こんなもんでしょう。 最初に出てきたBreakは結果に含めたいので、takeWhileではなく別バージョンを定義して呼び出しています。

Combineも難しくはないでしょう。

ミソは、Return系とYield系で、タプルの第二要素が違う点です。 こうしてみると、シグネチャや変換規則が同じなだけで、ReturnとYieldは別のものだという感じがしませんか？

C#のyield breakは式をとれないため、yield returnしてからyield breakする必要がありました。 ですが、今回実装したlistコンピュテーション式は、return exprとすることで値を返しつつ処理を抜けることができます。 ちなみに、C#でのyield breakがしたい場合は、return! []とでもするといいでしょう。

カスタムオペレータが使えたら素敵！

queryコンピュテーション式のheadなどのように、yieldBreakのようなカスタムオペレータが作れれば、よりそれっぽいと思いませんか？

・・・が、これは出来ません。 先日は簡単のために省略したqというパラメータを覚えているでしょうか？ これは、「その中でカスタムオペレータが使えるかどうか」を示すフラグです。 通常、yieldBreakしたいのはifの中ですが・・・お気づきですね。 最後のパラメータがqです。

T(if e then ce1 else ce2, V, C, q) = Assert(not q); C(if e then {| ce1 |}0 else {| ce2 |}0)

ifを使うためには、qがfalseである必要があります。 つまり、カスタムオペレータが使えない場所にしかifは書けないんですね。残念・・・

ちなみに、elseを伴わないifは、elseを伴うifに変換されたうえでさらに変換が走るので、結局上のAssert(not q)から逃れることは出来ません。 無念・・・

最後に

returnの挙動をどうするのがいいのか、実は2通り考えたんですが、どういう方針で行けばいいのか指針がないのでつらかったです。 yield breakをまねる、という方針があったのでよかったのですが、それがなかった場合はもう一方の(実装が楽な方)を実装してしまっていたでしょうね。 たぶん、それがなかったら今回のエントリの挙動ではなく、簡単な方を実装して済ませていたと思われます。

さて、もう一つの挙動はどんなものでしょうか。 これは読者への課題にしますね！

詳説コンピュテーション式

コンピュテーション式とは

コンピュテーション式とは、機能を制限したマクロです。 ・・・では投げやりすぎるので、もうちょっとだけ説明を試みると、 「式変形によって言語の用意する構文の意味をカスタマイズできるようにする仕組み」です。 モナド用の構文として紹介されることもありますが、それはコンピュテーション式という仕組みの上でモナドを扱っているだけに過ぎません。

もっとも、コンピュテーション式はモナド用の構文として使うことが一番多いでしょうから、 モナド用の構文と理解しても問題はないでしょう。 また、このような状況を考えると、モナド以外のことにコンピュテーション式を使う場合は、 現状では「これはモナドではありません」という表明をドキュメントなりなんなりでしておくのが無難でしょう。 特に、let!とreturnを提供する場合でコンピュテーション式をモナドではない構文とする場合は、 うるさいくらいその旨を伝えるようにしましょう。 作ったものがモナドっぽいけど確信が持てない・・・という場合にも、「モナドっぽいけど本当にそうかどうかはちゃんと確認してないよ」とか書いておくといいでしょう。 これは、見ず知らずの誰かのためですし、自衛のためでもあります。

このエントリはコンピュテーション式の仕様を、 日本語で出来る限り分かりやすく解説することを試みたナニカです。 コンピュテーション式自体を使ったことがある人を対象に、その変換の仕組みを説明します。 カスタムオペレータがかかわる部分を省いてあるため、仕様書よりも単純化されており、より理解しやすくなっていると思います。 これを読んでから仕様書を読めば、カスタムオペレータ部分を理解するのもそう難しくはないでしょう。

詳説コンピュテーション式

コンピュテーション式は、以下の構文で表されます。

builder-expr { cexpr }

builder-exprは、後述するReturnやBindなどのメソッドを持つ型(以降、ビルダー)をもった式です。 cexprは、通常のF#の文法に加えて、この中でのみ使える記法(let!など)を加えた文法によって書かれた式です。 cexprの中で使える記法は、ビルダーがどんなメソッドを提供しているかによります。 例えば、ビルダーがBindメソッドを提供している場合はcexprの中でlet!が使えますが、 提供されていない場合はlet!は使えません。

builder-exprには通常、後述するビルダーのインスタンス(例えば、asyncなど)を指定しますが、 関数呼び出しの結果やメソッド呼出しの結果としてビルダーが戻ってくるようなコンピュテーション式も当然考えられます。

let x = someCompExprBuilder (a, b) { ... }

これは、コンピュテーション式の動作を使う側で変更したい場合や、 ビルダーが内部に状態を持つなどして使いまわせない場合に有効です。

これを使っている例としては、Basis.Coreの ResultWithZeroBuilderがあります。 これは、コンピュテーション式を使う側でゼロ値を指定することで、 通常のResultBuilderでは提供不可能な構文をサポートしています。

(* xに負の数を指定した場合、Zeroメソッドが呼び出され、
   resultWithZeroに指定した"oops!"がFailureに包まれて返る *)
let f x = resultWithZero "oops!" {
  if x >= 0 then
    return x * 2
}

let x = f 10  (* => Success 20 *)
let x = f -10 (* => Failure "oops!" *)

コンピュテーション式の変換

コンピュテーション式はまず、以下のように変換されます((bは「フレッシュな変数(名前が他とかぶらない変数)」です))。

let b = builder-expr in {| cexpr |}c

ここで、{| ... |}cという表記が出てきますが、これは「その中の式をコア言語の式(つまり通常のF#の式)に変換する」ことを意味します。 似たような表記に、{| ... |}0もありますが、これは「カスタムオペレータが許されるかどうか」が違います。 {| ... |}cの方はカスタムオペレータが許されますが、{| ... |}0の方はカスタムオペレータが許されません。

以降では、話を単純化するためにカスタムオペレータについては省略します。 そのため、cや0といった使い分けはせず、単純に{| ... |}という表記を使いますが、言語仕様を読む際は注意してください。

また、builder-exprは1回しか実行されない点に注意してください。 cexprの変換中にビルダーにアクセスする際は、bを通してアクセスされます。 このルールによって変換の際に使われるオブジェクトは同じものであることが保証されているため、 毎回ビルダーを作るようにすれば、ビルダーの中に状態を持っても大丈夫なのです。

Run, Delay, Quote

ビルダーにRun, Delay, Quoteの各メソッドが実装されている場合、 コンピュテーション式は先ほどの変換の際に、これらのメソッドの呼び出しを差し込みます。

3つとも実装されている場合、以下のように変換されます。

let b = builder-expr
b.Run(<@ b.Delay(fun () -> {| cexpr |}) @>)

変換の順番としては、Delay, Quote, Runの順で変換されます。 もし対象のメソッドがなかった場合は、対応する変換は行われません。

Delay変換

ビルダーにDelayメソッドが存在する場合、cexprの変換した式をラムダ式で囲い、Delayに渡します。

builder-expr { cexpr }

これが、以下のように変換されます。

let b = builder-expr
b.Delay(fun () -> {| cexpr |})

ビルダーにDelayが存在しない場合、b.Delay(fun () -> {| cexpr |})の部分は単に{| cexpr |}となります。

{| cexpr |}に対する変換の結果の式を、delayed-exprとします。 Delayが存在する場合はb.Delay(fun () -> {| cexpr |})、存在しない場合は{| cexpr |}がdelayed-exprです。

Delayは、ここでの変換よりも、他の変換の中で現れる際に重要になってきます。 whileの変換までDelayは出てきませんが、Delayの存在はその時まで頭の片隅にでも置いておいてください。

Quote変換

ビルダーにQuoteメソッドが存在する場合、delayed-exprをコード引用符<@ ... @>で囲みます。

let b = builder-expr
delayed-expr

これが、以下のように変換されます。

let b = builder-expr
<@ delayed-expr @>

ビルダーにQuoteメソッドが存在しない場合、コード引用符で囲わずに、特に変換は行いません。

delayed-exprに対する変換の結果の式を、quoted-exprとします。 Quoteが存在する場合は<@ delayed-expr @>、存在しない場合はdelayed-exprがquoted-exprです。

このように、Quoteメソッドは呼び出されることはありません。 単に、存在すればいいだけのメソッドです。 ビルダーに対する属性にしなかったのは、拡張メソッドでQuoteの機能を後付けできるようにするためでしょうか？

Run変換

ビルダーにRunメソッドが存在する場合、quoted-exprをRunに渡します。

let b = builder-expr
quoted-expr

これが、以下のように変換されます。

let b = builder-expr
b.Run(quoted-expr)

ビルダーにRunメソッドが存在しない場合、特に変換は行いません。

Runは最後に一回だけ呼び出されるメソッドになるので、このメソッドの結果がコンピュテーション式の結果になります。 活用方法としては、Readerモナド用のビルダーに対して、最終的に値を取り出すビルダーを作るようなものが考えられます。

type Reader<'TEnv, 'T> = 'TEnv -> 'T

type ReaderBuilder () =
  ...

(* 普通のreaderコンピュテーション式 *)
let reader = ReaderBuilder ()

type ReaderBuilderWithRun<'TEnv> (env: 'TEnv) =
  ...
  member this.Run(x: Reader<'TEnv, _>) = x env

(* 一番外側で使うと便利なコンピュテーション式 *)
let readerWithRun env = ReaderBuilderWithRun<_> env

変換のルール

仕様書では、

{| cexpr |}c ≡ T (cexpr, [], fun v -> v, true)
{| cexpr |}0 ≡ T (cexpr, [], fun v -> v, false)

が変換のルールとして記載されています((このTは、translateもしくはtranslationの略でしょう))。 T(e, V, C, q)とあった時、

• eは変換されるコンピュテーション式
• Vはこれまでにバインドされた変数群
• Cは変換済みのコンテキスト情報
• qはカスタムオペレータを許すかどうかの真偽値

を表します。 Cの部分に変換されたものが入ると考えましょう。上の変換規則では、まだ何も変換されてないので、fun v -> vと、id関数になっています。

この中で、Vはカスタムオペレータに関係する変換中で使われるもののため、 またqもカスタムオペレータが絡む変換の際に必要になってくるもののため、今回は無視します。 そのため、このエントリでは

{| cexpr |} ≡ T (cexpr, fun v -> v)

という単純化したルールを使います。

returnの変換とyieldの変換

returnの変換は、以下のルールで表されます。

T(return e, C) = C(b.Return(e))

これは、return eがb.Return(e)に変換されることを意味します。

簡単な例を考えてみましょう。

type SimpleBuilder () =
  member this.Return (x) = x

let simple = SimpleBuilder ()

let res = simple { return 10 }

この最後の行を変換してみます*1。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| return 10 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(return 10, fun v -> v)

(* 3. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> v) (b.Return(10)))

(* 4. ラムダ式部分を計算 *)
let res =
  let b = simple
  b.Return(10)

変換できました。

yieldの変換は、

T(yield e, C) = C(b.Yield(e))

と、returnがyieldに、ReturnがYieldになっただけなので、同じステップで変換できます。

return!の変換とyield!の変換

return!の変換は、以下のルールで表されます。

T(return! e, C) = C(b.ReturnFrom(src(e)))

これは、return! eがb.ReturnFrom(src(e))に変換されることを意味します。

src(e)は、ビルダーがSourceメソッドを持っており、 かつ最も内側のForEachがユーザによるもの(変換により生成されたコードではなく、ユーザが書いたコードであるということ)である場合のみ、 b.Source(e)に変換されます。

2番目の条件は仕様書からのものですが、どうも実際の実装はちょっと違っているようです。 コードを軽く眺めただけですが、ForEachとForEachThenJoinOrGroupJoinOrZipClauseのForEach部分とLetOrUseBangの場合に、 ユーザコードかどうかの判定をしているようで、そのほかの部分ではビルダーにSourceメソッドがあればそれを呼び出しているようです。 そのため、return! eはビルダーにSourceメソッドが存在すればb.ReturnFrom(b.Source(e))に、存在しなければb.ReturnFrom(e)に変換されます。

yield!は、ReturnFromではなくYieldFromが使われる以外は同じです。

letの変換

letの変換は以下のルールで表されます。

T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))

これは、returnやreturn!とは異なり、変換後にもT(e, C)形式が出てくるとおり、変換後もさらに変換が行われます。 実際にどう変換されるかを一歩一歩確認していきましょう。

letの変換を追う

returnの時に定義したSimpleBuilderを使い、以下のコンピュテーション式を変換してみます。

let res = simple {
  let a = 10
  return a * 2
}

letの変換規則はこうでした。

T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))

これを使って変換します。 returnの時も言いましたが、変換の途中は有効なF#コードではないことに注意してください。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| let a = 10 in return a * 2 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(let a = 10 in return a * 2, fun v -> v)

(* 3. T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))のルールを適用 *)
let res =
  let b = simple
  T(return a * 2, fun v -> (fun v -> v) (let a = 10 in v))

(* 4. Tの最後の部分を計算 *)
let res =
  let b = simple
  T(return a * 2, fun v -> let a = 10 in v)

(* 5. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> let a = 10 in v) (b.Return(a * 2)))

(* 6. ラムダ式部分を計算 *)
let res =
  let b = simple
  let a = 10
  b.Return(a * 2)

これで変換できました。 ステップ5のコードは、有効なF#のコードにも見えますが、Returnの引数に出てくるaがどこにもないことからもわかる通り、 最終段階まで変換するまでは有効なF#のコードではないことに注意してください。

変換の結果を見ると、let p = e in ceの変換は、ceの部分のみ変換することになります。 これをT(e, C)形式ではなく{| ... |}形式で書くと、

{| let p = e in ce |} = (let p = e in {| ce |})

となります。 特に何も定義しなくても、letはコンピュテーション式の中でも使えるということですね。

let!の変換

let!の変換は以下のルールで表されます。

T(let! p = e in ce, C) = T(ce, fun v -> C(b.Bind(src(e), fun p -> v)))

letの変換を見たので、この変換は分かりやすいですね。 {| ... |}形式で書くと、

{| let! p = e in ce |} = b.Bind(src(e), fun p -> {| ce |})

となります。 このように、let!を使うためにはビルダーにBindメソッドが定義されている必要があります。 Bindメソッドは引数を2つ取り、2番目の引数は関数である必要があることが分かります。 また、eの型とpの型は一致していなくてもいいことも分かります。

eをpに代入するように見える構文のため、Bindメソッドの中では第一引数の値(e)を変換するなどして、 第二引数の関数に渡すようにBindメソッドを実装することがほとんどでしょう。 また、通常はBindメソッドはモナドにおける>>=の定義と同じようなものになるでしょう。

useの変換とuse!の変換

useの変換は以下のルールで表されます。

T(use p = e in ce, C) = C(b.Using(e, fun p -> {| ce |}))

ここまで理解できた人にとっては簡単ですね。

use!も見てみましょう。

T(use! p = e in ce, C) = C(b.Bind(src(e), fun p -> b.Using(p, fun p -> {| ce |})))

ちょっと複雑ですね。 が、順番に見て行けば難しくはありません。

SimpleBuilderにUsing(とBind)を追加してみましょう。

type SimpleBuilder with
  member this.Bind(x, f) = f x
  member this.Using(x, f) =
    printfn "start"
    try f x
    finally printfn "end"

これを変換します。

let res = simple {
  use! a = 10
  return a * 2
}

順番に変換していきます。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| use! a = 10 in return a * 2 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(use! a = 10 in return a * 2, fun v -> v)

(* 3. T(use! p = e in ce, C) =
      T(ce, fun v -> C(b.Bind(src(e), fun p -> b.Using(p, fun p -> v))))
      のルールを適用 *)
let res =
  let b = simple
  T(return a * 2, fun v -> (fun v -> v) (b.Bind(10, fun a -> b.Using(a, fun a -> v))))

(* 4. Tの最後の部分を計算 *)
let res =
  let b = simple
  T(return a * 2, fun v -> b.Bind(10, fun a -> b.Using(a, fun a -> v)))

(* 5. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> b.Bind(10, fun a -> b.Using(a, fun a -> v))) (b.Return(a * 2)))

(* 6. ラムダ式部分を計算 *)
let res =
  let b = simple
  b.Bind(10, fun a -> b.Using(a, fun a -> b.Return(a * 2)))

変換作業には慣れましたか？

use/use!の注意点

use/use!は、let/let!と意味が似ている(変数を導入する)うえ、Usingのシグネチャがlet!を使えるようにするために必要なBindのシグネチャと同じようなものであるため、 何も定義せずともuseが使え、Usingによってuse!が使えると思ってしまうかもしれません。 しかし、変換規則を見たとおり、useであってもUsingがビルダーに定義されていなければ使えません。 また、Usingの第一引数はuseの場合はuse p = eのeがそのまま、use!の場合はBindの第二引数で渡された関数の引数が入ってくることから、 UsingはそのままBindに相当するような機能*2は持たせられず、単にletやlet!をラップする存在でしかないことが分かります。

useはletに対してUsing機能を付けたもの、use!はlet!に対してUsing機能*3を付けたもの、と考えてください。 通常、Usingの実装は以下のようになるでしょう。

member this.Using(x: #IDisposable, f) =
  try
    f x
  finally
    match x with
    | null -> ()
    | _ -> x.Dispose()

doの変換

doの変換は以下のルールで表されます。

T(do e in ce, C) = T(ce, fun v -> C(e; v))

特に問題はないでしょう。eが実行された後、変換されたceが実行されるだけです。

do!の変換

do!の変換はルールが2つあり、後ろに式が続く場合と、do!より後ろにこれ以上変換する式がなかった場合で変換のされ方が若干異なります。

T(do! e in ce, C) = T(let! () = e      in ce,         C)
T(do! e;,      C) = T(let! () = src(e) in b.Return(), C)

do!より後ろにこれ以上変換する式がなかった場合、return ()が書かれているような動作になります。 do!の変換規則は、let!に変換してからlet!の変換規則を適用するような形になっています。 DRYでいいですね。 それ以外は、特に難しいところはないでしょう。

do!の変換にはlet!が必要となるため、do!を使うためにはBindメソッドがビルダーに必要になります。 また、場合によってはBindメソッドのほかに、Returnメソッドも必要となります。

if-then-elseの変換

2分岐の条件分岐の変換は以下のルールで表されます。

T(if e then ce1 else ce2, C) = C(if e then {| ce1 |} else {| ce2 |})

特に難しくありませんね。 ビルダーに何も定義しなくても、elseを伴うifを使えることが分かります。

if-thenの変換

elseを省略したifの変換は以下のルールで表されます。

T(if e then ce, C) = T(ce, fun v -> if e then v else b.Zero())

elseを持つifとは違い、ビルダーにZeroメソッドが必要なことが分かります。

elseを省略しないifと表記を合わせると、変換規則は以下のようになります。

T(if e then ce, C) = C(if e then {| ce |} else b.Zero())

matchの変換

matchの変換は以下のルールで表されます。

T(match e with pi -> cei, C) = C(match e with pi -> {| cei |})

piはi番目のパターンを表し、ceiはi番目の式を表します。 パターンが複数あった場合は、それぞれが変換されます。

また、何も定義しなくてもmatchは使えることが分かります。

whileの変換

whileの変換は以下のルールで表されます*4。

T(while e do ce, C) = T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))

Whileのほかに、Delayメソッドも必要であることが分かります。 手で変換してみましょう。 ビルダーには、SimpleBuilderの拡張を使います。

type SimpleBuilder with
  member this.While(cond, body) = while cond () do body
  member this.Delay(f) = f ()

変換する対象はこれです。

let f x = simple {
  while x do
    printfn "while"
    return ()
}

変換してみましょう。

(* 1. 全体の変換 *)
let f x =
  let b = simple
  b.Delay(fun () -> {| while x do let () = printfn "while" in return () |})

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(while x do let () = printfn "while" in return (), fun v -> v))

(* 3. T(while e do ce, C) =
      T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))
      のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(let () = printfn "while" in return (), fun v -> (fun v -> v) (b.While((fun () -> x), b.Delay(fun () -> v)))))

(* 4. Tの最後の部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(let () = printfn "while" in return (), fun v -> b.While((fun () -> x), b.Delay(fun () -> v))))

(* 5. T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(return (), fun v -> (fun v -> b.While((fun () -> x), b.Delay(fun () -> v))) (let () = printfn "while" in v)))

(* 6. Tの最後の部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(return (), fun v -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in v))))

(* 7. T(return e, C) = C(b.Return(e))のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> (fun v -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in v))) (b.Return()))

(* 8. ラムダ式部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in b.Return())))

変換できました。 コンパイル時に行われる変換はここまでですが、これだと結局どうなるのか分かりにくいので、Delayメソッドを展開してみましょう。 Delayメソッドは単に受け取った関数を実行するだけのものとして実装しているので、b.Delay(fun () -> expr)をexprにするだけですね。

(* 内側のDelayを展開 *)
let f x =
  let b = simple
  b.Delay(fun () -> b.While((fun () -> x), let () = printfn "while" in b.Return()))

(* 外側のDelayを展開 *)
let f x =
  let b = simple
  b.While((fun () -> x), let () = printfn "while" in b.Return())

whileを使うためには、このようにWhileメソッドとDelayメソッドが必要です。 が、これで本当に大丈夫でしょうか・・・？ 実際に、fを呼び出したときにどう動くのか見てみます。 falseを渡してみましょう。

(* whileの実装:
  member this.While(cond, body) = while cond () do body *)

(* step 1: 呼び出し *)
f false

(* step 2: fを展開 *)
let b = simple
b.While((fun () -> false), let () = printfn "while" in b.Return())

(* step 3: b.Whileの引数を評価 *)
let b = simple
let arg1 = (fun () -> false)
let arg2 =
  printfn "while"
  b.Return()
b.While(arg1, arg2)

(* step 4: b.Whileを展開 *)
let b = simple
let arg1 = (fun () -> false)
let arg2 =
  printfn "while"
  b.Return()
while arg1 () do
  arg2

なにかおかしいのが分かりますか？ 変換する前のコードを再掲します。

let f x = simple {
  while x do
    printfn "while"
    return ()
}

変換する前のコードは、printfnによる出力はwhileの中にありました。 そのため、直感的にはxがfalseであれば、何も出力されることなくループが終了すると考えてしまいます。 しかし、変換後のコードではwhileの外側に出力が移動してしまいました。 これでは、xにtrueを渡そうがfalseを渡そうが元のwhileの処理が呼び出されてしまいます((さらには、trueを渡したにもかかわらず、whileの中の処理は一回しか実行されません))。 これは使い物になりませんね。

これではまずい場合は、WhileメソッドとDelayメソッドの定義を変更し、Runメソッドを実装することで解決します。

SimpleBuilderを再実装

SimpleBuilderを拡張してきましたが、もう最初らへんのメソッド忘れ気味ですよね。 なので、ここで今までのSimpleBuilderを捨て、新たなSimpleBuilderを定義します。

(* Usingは提供しない *)
type SimpleBuilder () =
  member this.Zero() = Unchecked.defaultof<_>
  member this.Return(x) = x
  member this.Bind(x, f) = f x
  member this.While(cond, body) = while cond () do body () (* body -> body () *)
  member this.Delay(f) = f  (* f () -> f *)
  member this.Run(f) = f () (* new! *)

let simple = SimpleBuilder ()

let f x = simple {
  while x do
    printfn "while"
    return ()
}

fの本体を変換した結果がこちらになります(実際の変換は各自の課題とします)。

let f x =
  let b = simple
  b.Run(b.Delay(fun () -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in b.Return()))))

今回のビルダーでは、Delayは何もせずに返しますので、b.Delay(fun () -> ...)は単に(fun () -> ...)に展開できます。 展開してみましょう。

(* 内側のDelayを展開 *)
let f x =
  let b = simple
  b.Run(b.Delay(fun () -> b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))))

(* 外側のDelayを展開 *)
let f x =
  let b = simple
  b.Run(fun () -> b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return())))

(* Runも展開してしまう *)
let f x =
  let b = simple
  b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))

展開できました。 Runが必要なのは、Delayを実装すると一番外側も関数にくるまれてしまうため、それを実行しないと全体として関数が戻ってしまうからですね。

元の展開結果と比べてみます。

(* 元の展開結果 *)
let f x =
  let b = simple
  b.While((fun () -> x), let () = printfn "while" in b.Return())

(* 今回の展開結果 *)
let f x =
  let b = simple
  b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))

第二引数部分が関数で包まれたままになりました。 この関数fにfalseを渡すと、最終的には以下のようなコードが実行されることになります。

(* whileの実装:
  member this.While(cond, body) = while cond () do body () *)

let b = simple
let arg1 = (fun () -> false)
let arg2 =
  (fun () ->
    printfn "while"
    b.Return())
while arg1 () do
  arg2 ()

これで、思い通りの結果になりますね。

このように、whileの展開にはWhileメソッドとDelayメソッドのみが必要ですが、現実的にはRunメソッドも実装する必要がある場合が多いです。

ce1; ce2の変換

ce1; ce2の変換は以下のルールで表されます。

T(ce1; ce2, C) = C(b.Combine({| ce1 |}, b.Delay(fun () -> {| ce2 |})))

CombineメソッドとDelayメソッドが必要ですね。 簡単です。

ですが、ce1; ce2の変換は、whileなどを実用的なものにするために必要になるため、非常に重要です。

whileを実用するためのCombine

whileの変換で、「whileの展開にはWhileメソッドとDelayメソッドのみが必要ですが、現実的にはRunメソッドも実装する必要がある場合が多いです」と書きましたが、 実はこれだけではまだ足りません。 今のWhileの実装では、while以降に別のceを置けず、かつwhileの本体はunitを返す必要があります。

member this.While(cond, body) =
  while cond () do
    body () (* while式の本体はunitである必要があるため、bodyの型はunit -> unitのみ許される *)

どうすればいいか。そうですね、Combineです。

type SimpleBuilder () =
  let mutable isExit = false
  member this.Zero() = Unchecked.defaultof<_>
  member this.Return(x) = isExit <- true; x
  member this.Bind(x, f) = f x
  member this.Combine(x, f) = if isExit then x else f ()
  member this.While(cond, body) =
    if not (cond ()) then this.Zero()
    else let x = body () in this.Combine(x, fun () -> this.While(cond, body))
  member this.Delay(f) = f
  member this.Run(f) = isExit <- false; f ()

let simple () = SimpleBuilder ()

isExitとCombineの追加、ReturnとWhileの変更を行いました。 さらに、simpleを関数にしています。 詳しい説明は省きますが、これによって以下のようなコードが書けるようになりました。

let f x = simple () {
  while x do
    return 10
  return 0
}

これで、trueを渡すと10が返り、falseを渡すと0が返ります。 展開や、なぜsimpleを関数にしたのかを考えるのは読者の課題とします。

ちなみに、simpleを関数にしなくても済む方法があります。 それを実装した例がBasis.CoreのOptionBuilderなどで見れます。*5 このエントリは、その時の苦労の反動が書くきっかけとなっています。

よくあるコンピュテーション式の実装では、上のようなwhileの中でreturnするコードを上手く扱えないと思います。 「このコードを扱えるコンピュテーション式を実装しているコードが他にもあるよ！」というものがあったらコメント欄で教えてくれると嬉しいです。

tryの変換

tryの変換は以下のルールで表されます。

T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce |}), fun pi -> {| cei |}))
T(try ce finally e, C) = C(b.TryFinally(b.Delay(fun () -> {| ce |}, fun () -> e)))

ここまで来たら、もはや何も難しいことはありませんね。 ただ、withの変換はちょっと怪しいです。 正しくは多分、こうですね。

T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce |}), function pi -> {| cei |}))

forの変換

forの変換は以下のルールで表されます。

T(for x in e do ce, C) = T(ce, fun v -> C(b.For(src(e), fun x -> v)))
T(for x = e1 to e2 do ce, C) = T(for x in e1 .. e2 do ce, C)

forも難しいところはありません。 下の形式は、上の形式のforに書き換えたうえで変換するようになっていますね。

eの変換

eの変換は以下のルールで表されます。

T(e, C) = C(e; b.Zero())

簡単ですね。 simple { () }や、simple { printfn "hoge" }などは、Zeroの呼び出しを付けて変換されます。

まとめ

他にもカスタムオペレータが絡む変換規則がいくつかありますが、 取りあえずコンピュテーション式の実装でよく使うであろう変換規則の説明は以上です。 ここまで理解できれば、カスタムオペレータが絡む変換規則も理解できるでしょう。

みなさんもコンピュテーション式の変換規則を理解して、色々なコンピュテーション式を作ってみましょう！

付録 変換規則一覧

このエントリで紹介した変換規則の一覧を載せておきます。

(* {| cexpr |}とT(...)の関係 *)
{| cexpr |} ≡ T (cexpr, fun v -> v)
(* return *)
T(return e,  C) = C(b.Return(e))
T(return! e, C) = C(b.ReturnFrom(src(e)))
(* let/let! *)
T(let p  = e in ce, C) = T(ce, fun v -> C(let p = e in v))
T(let! p = e in ce, C) = T(ce, fun v -> C(b.Bind(src(e), fun p -> v)))
(* use/use! *)
T(use p  = e in ce, C) = C(b.Using(e, fun p -> {| ce |}))
T(use! p = e in ce, C) = C(b.Bind(src(e), fun p -> b.Using(p, fun p -> {| ce |})))
(* do/do! *)
T(do e  in ce, C) = T(ce, fun v -> C(e; v))
T(do! e in ce, C) = T(let! () = e in ce, C)
T(do! e;,      C) = T(let! () = src(e) in b.Return(), C)
(* if *)
T(if e then ce1 else ce2, C) = C(if e then {| ce1 |} else {| ce2 |})
T(if e then ce,           C) = C(if e then {| ce  |} else b.Zero())
(* match *)
T(match e with pi -> cei, C) = C(match e with pi -> {| cei |})
(* while *)
T(while e do ce, C) = T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))
(* ; *)
T(ce1; ce2, C) = C(b.Combine({| ce1 |}, b.Delay(fun () -> {| ce2 |})))
(* try *)
T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce|}), function pi -> {| cei |}))
T(try ce finally e,      C) = C(b.TryFinally(b.Delay(fun () -> {| ce |}, fun () -> e)))
(* for *)
T(for x in e do ce, C) = T(ce, fun v -> C(b.For(src(e), fun x -> v)))
T(for x = e1 to e2 do ce, C) = T(for x in e1 .. e2 do ce, C)
(* e *)
T(e, C) = C(e; b.Zero())

Delay変換、Quote変換、Run変換は上記規則で表現できないので省略します。

*1:もちろん、変換の途中段階は有効なF#コードではありません

*2:モナドの話をすると、モナドで包まれた値を「はがす」機能

*3:通常は第一引数に対するDispose呼び出し

*4:仕様書上はWhileの第一引数を囲むカッコはありませんが、 このカッコがないとWhileが「ユニットを受け取りタプルを返す関数」を受け取る一引数メソッドと解釈されてしまうため、必要です

*5:id:pocketberserker がコンピュテーション式の実装にStateを用いる - pocketberserkerの爆走で解説記事を書いてくれました！