シーケンス式はどう動いているのか
実を言うと、僕がF#に入れ込んでいる理由の半分ぐらいはこの「シーケンス式」に惚れたことではないかと思うほど、個人的にSequence式を気に入っている僕なのですが、周りの人（ほとんどJava使い）に熱く語れば語るほど「ぽか～ん」とされるのもまたこのシーケンス式なのです。関数型言語を知らない人にとって、見よう見まねで使うことはできても、これほど不思議な動きをするプログラムはあまりないのではないかと思うのです。
とはいえ、周りの人を「ポカン」化してしまう理由の多くは僕の説明にあり、説明が伝わらない理由は僕自身がその中で何が起こっているのかをちゃんと分かっていないせいである、ということもはっきりしているので、シーケンスの裏の動きを追いかけてみることにしました。
しかし、F#のシーケンス式について深く書かれた日本語の文献も少なく、「Programming F#」はほとんど説明するつもりもなさそうですし、「実践F#」はかなり食いついているものの、核心の部分には触れてくれていません。仕方ないのでF#コンパイラのソースなど覗きながら、プログラムの動きを見て、シーケンスがどのような式に展開されているか推測することにしました。
単純なシーケンスの動き
最も単純なシーケンスは、以下のようなものです。
let s =
seq {
yield 1
yield 2
yield 3
}
これをSeq.iterなんかにかけて
Seq.iter (fun i -> printfn "%d" i) s
なんてやるのがベタなシーケンス式です。まぁ普通こんな書き方はせず、[1..3]などと書くのが普通でしょうが、ここは研究中ということで。
これを展開するのに必要な変換ルールは「実践F#」の記述によると、以下のようになります。
yield expr ⇒ Seq.singleton expr
expr1; expr2 ⇒ Seq.append expr1 expr2
これを使って変換した式は、以下のようなものです。
let s =
Seq.append
(Seq.singleton 1)
(Seq.append
(Seq.singleton 2)
(Seq.singleton 3)
)
こういう変換がよく分からないという人は、
StatefulFuncはなぜ動くかを先に読んでみて下さい。損はさせません。
これを先ほどのようにiterにかけると、最初のシーケンスと同じように動くことがわかります。展開されたコードは、yieldに渡された値を、項が一つしかないシーケンス（singleton）に変換して、それをappendでつなぎ合わせているだけのものです。
ここまではいいのです。ここまでは。
間に副作用のある式を挟んだシーケンスの動き
次のステップとして、yieldの間にprintfを挟んでみましょう。
let s =
seq {
printfn "1"
yield 1
printfn "2"
yield 2
printfn "3"
yield 3
}
この式を評価した結果は、以下のようになります。
val s : seq<int>
>
この時点ではまだシーケンス式の中は評価されていませんね。しかし、
Seq.iter (fun i -> printfn "Got %d." i) s
とした時点で
> Seq.iter (fun i -> printfn "Got %d." i) s;;
1
Got 1.
2
Got 2.
3
Got 3.
val it : unit = ()
>
のように、中のprintfnも含めて順次評価されることが分かります。ちなみに、先頭の要素だけを返すSeq.headで先頭要素だけを見ると
> Seq.head s;;
1
val it : int = 1
>
と言う風に、最初のprintfnしか実行されません。このあたりがシーケンスの動きのマカ不思議なところです。
このようなシーケンス式はどのように展開されるのでしょうか。
「実践F#」を見ると、このような式もSeq.appendに展開されるように書かれています。
let n = 10 in
Seq.append(printfn "First = %A" n,
Seq.singleton n)
が、どう考えてもこの記述は間違っているとしか思えません。Seq.appendの型はseq<'a> ->seq<'a> ->seq<'a>なので、最初の引数はシーケンスでなければならないのです。で、自分で書いてみたのが以下のようなソースです。
let s =
Seq.append
(Seq.singleton (printfn "1"
1)
(Seq.append
(Seq.singleton (printfn "2"
2)
(Seq.singleton (printfn "3"
3)
)
これでうまくいきそうな気がしたのですが、これを評価すると以下のような結果になります。
1
2
3
val s : seq<int>
>
singletonが作成されるときにその中身が評価されてしまい、先にprintfnが動いてしまいます。これは先ほどのシーケンス式と明らかに動きが違います。
ここで1時間悩みました。で、しょうがなくF#のソースを読んでみたりして、なんとかひねり出したのが以下のソースです。
open System.Collections
open System.Collections.Generic
open Microsoft.FSharp.Collections
let mkSeq f =
{ new IEnumerable<'U> with
member x.GetEnumerator() = f()
interface IEnumerable with
member x.GetEnumerator() = (f() :> IEnumerator) }
type Singleton<'T>(v:'T) =
let mutable started = false
interface IEnumerator<'T> with
member x.Current = v
interface IEnumerator with
member x.Current = box v
member x.MoveNext() = if started then false else (started <- true; true)
member x.Reset() = ()
interface System.IDisposable with
member x.Dispose() = ()
let Singleton x = (new Singleton<'T>(x) :> IEnumerator<'T>)
let s =
Seq.append
(mkSeq (fun () -> printfn "1"
Singleton 1))
(Seq.append
(mkSeq (fun () -> printfn "2"
Singleton 2))
(mkSeq (fun () -> printfn "3"
Singleton 3))
)
なんだかえらいことになっていますが、先頭３分の２はF#のソースコードからのコピペです。最後のletだけをみてもらうと、printfnがfun()->という遅延実行の式の中に隠れているのがわかります。こうしないとどうしても最初のシーケンスと同じように動いてくれません。実行結果は以下のようになります。
val s : seq<int>
>
この時点では何も評価されず、iterなどで中身を取り出して
> Seq.iter (fun i -> printfn "Got %d." i) s;;
1
Got 1.
2
Got 2.
3
Got 3.
val it : unit = ()
>
これで最初のシーケンスと同じ動きになりました。シーケンス式は恐らくこんな風にyieldを境にコードのブロックをfun()->で包み、singletonに変換した後シーケンスに並べてから、それを最初から取り出して一つずつ評価しているのです。
ここまではいいのです。ここまでは。（またか）
forを含むシーケンスの展開
さて、実際のところシーケンスをこんな風に書く人はいないと思います。簡単なものは簡単に書くにしても、シーケンスとするからには中に何らかの形で繰り返しを持つのが普通でしょう。
let s =
seq {
for i in [1..3] do
printfn "%d" i
yield i
}
Seq.iter (fun i -> printfn "Got %d." i) s
実践F#によると、これはSeq.collectを使って以下のように展開されます。
for pat in expr do expr2 ⇒ Seq.collect(fun pat ->> expr2) expr1
このルールと前項の展開方法を使って上のシーケンス式を展開すると、以下のようになります。
let s =
Seq.collect(
fun i ->
mkSeq (
fun () ->
printfn "%d" i
Singleton i
)
)[1..3]
Seq.iter (fun i -> printfn "Got %d." i) s
実行結果も、
1
Got 1.
2
Got 2.
3
Got 3.
val s : seq<int>
>
となり、うまく動いているようです。
ここまではいいのです。ここまでは。（しつこい）
forの前にyieldを伴わない式がある場合の展開のナゾ
ところで、forの前にも式を書くことができます。
let s =
seq {
printfn "start"
for i in [1..3] do
printfn "%d" i
yield i
}
この最初のprintfnは、最初の要素を取り出したときに初めて評価されます。
> Seq.head s;;
start
1
val it : int = 1
>
さて、この最初のprintfnはどこにくっついているのでしょうか。
let s =
printfn "start"
Seq.collect(
fun i ->
mkSeq (
fun () ->
printfn "%d" i
Singleton i
)
)[1..3]
のように先頭にくっつけると、当たり前ですがシーケンスが作成されたときに評価されてしまいます。これでは動きが違います。
let s =
Seq.collect(
fun i ->
mkSeq (
fun () ->
printfn "start"
printfn "%d" i
Singleton i
)
)[1..3]
のようにcollectの中に入れてしまうと項を取り出すごとに評価されてしまいます。かといって、
let s =
Seq.collect(
fun i ->
mkSeq (
fun () ->
if i = 1 then printfn "start"
printfn "%d" i
Singleton i
)
)[1..3]
のようにすると確かに動きは同じになりますが、さすがにこれはないでしょう。
実を言うと、これについては今のところ僕には正解が分かっていません。せいぜい、forの中と外のコードの関係を崩さないように、
let s =
let first = ref true
let topfunc () = printfn "start"
Seq.collect(
fun i ->
mkSeq (
fun () ->
if !first then
first := false
topfunc ()
printfn "%d" i
Singleton i
)
)[1..3]
Seq.iter (fun i -> printfn "Got %d." i) s
とするぐらいの知恵しか思い浮かびません。これなら機械的に展開するのも不可能ではなさそうですが、この線もなさそうだなぁ・・・
どなたか正解をご存知の方、教えていただけませんか？
（文責：片山 功士 2012/01/05）
サポート
「ながとペイント」のながとさんが、この件についていろいろ調べてくださいました。結果は以下の通り。
コンピュテーション式の展開ルールで気になる部分 2
わずか半日でここまで調べてしまいました。恐るべし。
これによると、シーケンス限定で、最初の式が遅延評価されるように作りこまれているようです。これは通常のコンピュテーション式の範囲では難しく、シーケンス式のためにコンパイラの機能として組み込まれている実装のようです。まだまだシーケンス周辺には特別なことがたくさんありそうです。
それとは別に、上であげたサンプルですが、forの展開を以下のようにしています。
let s =
Seq.collect(
fun i ->
mkSeq (
fun () ->
printfn "%d" i
Singleton i
)
)[1..3]
ここでcollectの引数の関数の中身をわざわざmkSeq(fun ()->)でラップしていますが、これはどうも必要がない処理のようです。Seq.collectはそれ自身遅延評価で動くので、こんなことをしなくてもいいのでした。
let s =
Seq.collect(
fun i ->
printfn "%d" i
Singleton i
)[1..3]
このへんの「アチャー」な感じは、
lazyさ加減に萌にまとめてありますのでこちらもあわせてご覧下さい。
（文責：片山 功士 2012/01/06）
今日： - 人
昨日： - 人
トータル： - 人
最終更新：2012年02月03日 01:59
