(2) へ 続編 (Swift) へ

Go 言語による LINQ to Objects の試作 (3)

2014-07-17 (鈴)

1. はじめに

前回Go 言語 [golang.org] の (構造体ではなく) 関数に対するメソッドとして C# の LINQ to Objects の メソッド群 [microsoft.com] のいくつかを実装した。 しかし,ループの打ち切りを error 戻り値の伝播で実現したことは Go プログラムとしては正統的ではあったが C# の LINQ メソッドからは離れ,また使うには煩雑であるきらいがあった。

ここでは 前々回 と同じく,panic 文による大域脱出を利用した実装を与える。 ただし,その野放図な利用は避け,汎用的な高階関数 LoopWithExit の中に大域脱出の機能をカプセル化した。

前回,前々回と同じくここで与える実装の計算量は本来の LINQ to Objects と同じであり,LINQ のメソッド連鎖が事実上のループ融合 (loop fusion) を実現する。 無限の列を表現でき,リアクティブ・プログラミング (reactive programming) への応用も可能である。

Go 1.3 に対する添付のソースの Unix 類 (OS X 10.8.5, Linux 等でもほぼ同じ) での実行例を示す。

01:~/tmp$ tar xvf ../Downloads/go-linq-26-07-14.tar.bz2
x src/
x src/linq/
x src/linq/linq.go
x src/linq/linq_test.go
01:~/tmp$ GOPATH=`pwd` go test linq
ok      linq    0.013s
01:~/tmp$  
Cygwin では Go に Windows ネイティブのパス表記で環境変数を与える必要がありますから下記のようにします。
01:~/tmp$ GOPATH=`cygpath -w -a .` go test linq

このとき "go test linq" で実行される単体テスト・プログラム linq_test.go の一部を下記に示す。 "Output:" に続くコメントの内容がプログラムの出力と一致するかテストされる。 上記の実行例では ok が出力され,すべてのテストで出力が一致したことが分かる。

func ExampleEnumerator_Select() {
    seq := Range(7, 3).Select(func(e Any) Any {
        return e.(int) + 100
    })
    seq(func(e Any) {
        Println(e)
    })
    // Output:
    // 107
    // 108
    // 109
}

以下,§2 では実装の概要を, §3 では汎用的な高階関数 LoopWithExit とそれによる Take メソッド等の実装をそれぞ説明する。

2. 実装の概要

LINQ メソッドの実装は error 戻り値を省いたこと以外は前回と概ね同じである。

列の要素の型を Any とする。

type Any interface{}

何らかの列の各要素が順に与えられる (戻り値なしの) 関数を引数にとる (戻り値なしの) 関数の型を Enumerator とする。

type Enumerator func(func(Any))

この Enumerator 型に対して LINQ to Objects の各メソッドを定義する。

整数引数 startcount に対して start, start + 1, start + 2, ..., start + count - 1 の列を返す Range 関数は次のように定義できる。

func Range(start, count int) Enumerator {
    end := start + count
    return func(yield func(Any)) {
        for i := start; i < end; i++ {
            yield(i)
        }
    }
}

整数引数 n に対して n, n+1, n+2, n+3, ... と無限の列を返す IntsFrom 関数は次のように定義できる。

func IntsFrom(n int) Enumerator {
    return func(yield func(Any)) {
        for i := n; ; i++ {
            yield(i)
        }
    }
}
IntsFrom の名前は Haskell の文献によく現れる intsFrom にちなみます。 C# の元々の LINQ to Objects にはありませんが C# でも同様に定義できます。

列の各要素に関数 f を適用する Select メソッドは次のように定義できる。

func (forEach Enumerator) Select(f func(Any) Any) Enumerator {
    return func(yield func(Any)) {
        forEach(func(e Any) {
            value := f(e)
            yield(value)
        })
    }
}

列の各要素に述語関数 predicate を適用し,真を返した要素だけを残す Where メソッドは次のように定義できる。

func (forEach Enumerator) Where(predicate func(Any) bool) Enumerator {
    return func(yield func(Any)) {
        forEach(func(e Any) {
            if predicate(e) {
                yield(e)
            }
        })
    }
}

列の各要素からなるリストを返す ToList メソッドは次のように定義できる。

func (forEach Enumerator) ToList() *list.List {
    y := list.New()
    forEach(func(e Any) {
        y.PushBack(e)
    })
    return y
}

種 (seed) となる値に各要素を順に与えて関数 f を適用することにより,一つの値へと集約する Aggregate メソッドは次のように定義できる。

func (forEach Enumerator) Aggregate(seed Any, f func(Any, Any) Any) Any {
    forEach(func(e Any) {
        seed = f(seed, e)
    })
    return seed
}

3. 大域脱出をかなえる高階関数

大域脱出を panic 文を使って実現する高階関数を,次のような Enumerator に対する LoopWithExit メソッドとして与える。

type token_t int
func recoverAsBreak(token *token_t) {
    r := recover()
    if r != nil && r != token {
        panic(r)
    }
}
func (forEach Enumerator) LoopWithExit(
    f func(element Any, yield func(Any), exit func())) Enumerator {
    return func(y func(Any)) {
        var token token_t
        defer recoverAsBreak(&token)
        ext := func() {
            panic(&token)
        }
        forEach(func(e Any) {
            f(e, y, ext)
        })
    }
}

列の各要素ごとに関数引数 felement, yield, exit の3引数で呼び出される。 element は列の要素の値である。 yield(x) を呼び出すと,x が新しい要素値として LINQ メソッドの次の連鎖に与えられる。 1回の f の呼び出しで yield を 0 回または複数回呼び出してよい。 exit() を呼び出すと,その列の繰り返しがそこで打ち切られる。

f への yield と exit の与え方から Scheme 言語の call/cc (call-with-current-continuation) を連想するかもしれません。 呼び出し元を何らかの意味で制御する手段を与えるために,呼び出し先に yield や exit のような関数引数を供給するというやり方は call/cc に見ることができるように古典的な方法でした。 しかし,Java 等にもラムダ式が導入され,ファースト・クラスの値としての関数の概念が普及しはじめた今, この方法が新しい「デザイン・パターン」として喧伝されるようになるかもしれません。

列の各要素に述語関数 predicate を適用し,偽が返されたらそこで列挙を打ち切る TakeWhile メソッドは LoopWithExit を使って次のように自明に定義できる。

func (forEach Enumerator) TakeWhile(predicate func(Any) bool) Enumerator {
    return forEach.LoopWithExit(func(e Any, yield func(Any), exit func()) {
        if predicate(e) {
            yield(e)
        } else {
            exit()
        }
    })
}

列の最初の n 要素だけを列挙する Take メソッドは次のように定義できる。 メソッドの戻り値がとる関数引数 yLoopWithExityield として伝播していることに注意されたい。

func (forEach Enumerator) Take(n int) Enumerator {
    return func(y func(Any)) {
        if n > 0 {
            i := 0
            forEach.LoopWithExit(func(e Any, yield func(Any), exit func()) {
                i++
                yield(e)
                if i >= n {
                    exit()
                }
            })(y)
        }
    }
}

Aggregate メソッドが行うような列の要素値の集約処理を途中で打ち切ることができる AggregateWithExit メソッドを考えよう。 関数 f に従来どおりの引数 a, b に加えて exit 引数を与える。 f の中で exit(x) を呼び出すと,そこで集約処理が打ち切られて x がメソッドの戻り値になるとする。 このようなメソッドは次のように定義できる。

func (forEach Enumerator) AggregateWithExit(seed Any, f func(a, b Any,
    exit func(Any)) Any) Any {
    forEach.LoopWithExit(func(e Any, yield func(Any), ext func()) {
        seed = f(seed, e, func(x Any) {
            seed = x
            ext()
        })
    })(nil)
    return seed
}
AggregateWithExit メソッドの使用例を linq_test.go から引用します。 100 を seed として 100 * 1 * 2 * 3 * 4 * 5 を計算するはずのところ,2 の次に error 値が出現したため,100 * 1 * 2 で打ち切ります。 -1 をそれまでの集計値に掛けた値で exit していますから,結果の値は -200 になります。
func ExampleEnumerator_AggregateWithExit() {
    seq := From([]Any{1, 2, errors.New("poi"), 3, 4, 5})
    x := seq.AggregateWithExit(100, func(a, b Any, exit func(Any)) Any {
        if bi, ok := b.(int); ok {
            return a.(int) * bi
        } else {
            exit(-1 * a.(int))
            return nil // dummy
        }
    })
    Printf("%v\n", x)
    // Output:
    // -200
}

4. おわりに

今回の試みでは Go 言語による LINQ to Objects の実装を C# の該当するメソッドにより近い親しみやすい仕様で与えた。 しかし,そうしたとき,その処理の打ち切りに,呼び出し階層をとび越える大域脱出が必要となる。 その実装を1個の汎用的な高階関数 LoopWithExit にまとめることに成功した。

LINQ to Objects に関係する最近注目されるライブラリとして Dart 言語[dartlang.org] の Stream クラス [dartlang.org] が挙げられる。 これは単一スレッドによるイベント駆動システムでの非同期的な実行を実現する Future クラスの上に作られており,興味深いことにそのまま FRP (Functional Reactive Programming) の基礎として使うことができる。 反面,普通のデータ集計手段として使い勝手がよいとは言えない。 ここで与えた Go 言語の LINQ to Objects 実装をゴルーチンと組み合わせることで,より使いやすく表現力がある FRP システムを実現できるかもしれない。


Copyright (c) 2014 OKI Software Co., Ltd.