続編へ

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

2012-11-30 (鈴)

1. はじめに

Ruby 2.0 メモ: Lazy と LINQ とループ融合 では Ruby 2.0.0 開発版の Enumerator::Lazy が C# 3.0 以降の LINQ to Objects (以下,単に LINQ) と実質的に同じであることを示した。 "Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド" ではそれらのメソッドが一部の例外を除き mruby と共通する Ruby 言語の骨格だけで実現できることを示した。 "Ruby のための LINQ ライク・メソッドの使用例" ではいくつかの例を与え, "LINQ ライク・メソッドの高速化と Ruby 1.9" ではその実装を簡素化した。

ここではそのメソッド実装を基礎として Google による Go 言語 [golang.org] に主要な LINQ メソッドを実現する試みを述べる。

メソッド名は Ruby ではなくオリジナルの Enumerable Methods (System.Linq) [microsoft.com] にならうことにします。 Go に規範となる言語標準のコレクション用メソッドがもともとほとんどないこと,Go と C# が (大域的な) メソッド名をともに大文字ではじめる点で似通っていることがその理由です。 Ruby と異なり,メソッド名をオリジナルの LINQ に合わせることへの差し障りはさしあたりありません。

2. 実装方針

Go 言語は抽象型からのメソッド実装の継承をサポートしない。 したがって LINQ に対する C# や Ruby の実装を Go に直訳することはできない。 C# では IEnumerable<T> インタフェースに対する拡張メソッドとして, Ruby では Enumerable モジュールへの追加メソッドとして LINQ のためのメソッドが定義される。 C# や Ruby の個々の具体型はメソッド実装の継承をとおしてそれらのメソッドを利用する。 しかし,どちらの方法も Go では直接表現できない。

力業で他の言語のメカニズム一式を模造することは避けるとしたら,Go ではどのように考えたらよいのだろうか?

"LINQ ライク・メソッドの高速化と Ruby 1.9" では LINQ が作る仮想的な列を次の Ruby クラスで表現した。

  class Iter
    include Enumerable
    def initialize(&block); @block = block; end
    def each(&y); @block[y]; end
  end

このとき,each メソッドをもつ任意のレシーバに対して_collect メソッド (LINQ の Enumerable.Select [microsoft.com] に相当) を次のように定義できる。

  def _collect
    Iter.new {|y| each {|e|
        y[yield e]
      }}
  end

このメソッドは (仮想的な) 列の各要素に関数引数を適用して得られる新しい仮想的な列を返す。

>>> [1, 2, 3, 4, 5]._collect{|e| e + 100 }.to_a
=> [101, 102, 103, 104, 105]

ここで _collect メソッドが Ruby のどんなオブジェクトをレシーバとし,どんなオブジェクトを結果とするのかを改めて考えてみよう。 レシーバに対しては each メソッドを備えていることだけが仮定される。 Iter クラスは each メソッドを定義する。 それが Ruby の標準モジュール Enumerable に適合するための唯一の条件である。 つまり,_collect メソッドは each メソッドを持つ何かをレシーバとし,each メソッドを持つ何かを結果とする。

each メソッドは任意の1引数手続きを引数にとる高階関数にほかならない。 _collect メソッドはつまるところ引数の高階関数から結果の高階関数を組み立てる高階関数にほかならない。 より一般に,Ruby の LINQ ライク・メソッドのレシーバと結果の型は,ともに任意の1引数手続きを引数にとる高階関数型にほかならない。 Ruby ではそれが Ruby の言語仕様と標準モジュール Enumerable が暗黙のうちに示す規範から,高階関数型そのものではなく each メソッドをもつクラスとして表現されることを強いられていると見ることができる。

もともと規範となるようなコレクション型のライブラリがなく,かつ関数型を含む任意の利用者定義型に対してメソッドを定義できる Go 言語では,そのような1引数手続きを引数にとる高階関数型をそのまま仮想的な列を表現するために使用できる。 これを Each 型と定義しよう。 当然ながら,この型を1引数手続きの引数として任意の型を与えることができるようにしたい。 しかるに任意の型を表現する Go 言語の interface{} は煩雑だから,Any を定義する。

type Any interface{}
type Each func(func(Any))
Each の名前の由来は,それが Ruby の each メソッドに相当する関数を表す型だからです ……あまり良い名前ではなかったかもしれません……。

このとき Each 型に対するメソッドとして Ruby の _collect に相当する GoSelect メソッドを次のように定義できる。

func (x Each) Select(f func(Any) Any) Each { // ~ "collect" in Ruby
    return func(y func(Any)) {
        x(func(e Any) {
            y(f(e))
        })
    }
}

この定義は十分に簡潔であり,いわば Go 言語本来のかたちで LINQ メソッドを表現していると言ってよい。

しかし,同時にここには Go の言語仕様に関する三つの論点があります。
  1. Any の導入意図は interface{} の簡略記法としてでしたが,たとえ望まなくても C の typedef A B や C# の using B=A のような型の素朴な別名定義以上の意味が伴います。 例えば,配列型 []Any と []interface{} は互いに別の型となってしまい互換性がありません。
  2. Any を引数型とするのでは静的型検査が事実上無効になります。 もしも C# のようなジェネリクスがあれば type Each<T> func(func(T)) のようにして型安全に定義できたはずです。
  3. Select の定義で仮引数 y や e に対する型宣言は明らかに冗長です。 もしも C# のような仮引数に対する型推論があれば省略できたはずです。
ここで 0. はそれが本当に問題なのか微妙ですが,1., 2. はモダンな言語が備えるべき機能として改善を望みたいところです。

3. 実装と使用例

列から述語 (predicate) を満たす要素だけを選んで新しい列を構成する Enumerable.Where [microsoft.com] 相当のメソッドは次のように定義できる。

func (x Each) Where(predicate func(Any) bool) Each { // ~ "select" in Ruby
    return func(y func(Any)) {
        x(func(e Any) {
            if predicate(e) {
                y(e)
            }
        })
    }
}

列からはじめの n 個の要素だけをとって新しい列を構成する Enumerable.Take [microsoft.com] 相当のメソッドは次のように定義できる。 Each 型の x による繰返しを中断するために panic で大域脱出する。 他の panic と混同しないように一意性が保証された値を合い言葉として recoverAsBreak 関数で脱出を受け止める。

func (x Each) Take(n int) Each { // ~ "take" in Ruby
    return func(y func(Any)) {
        var token token_t
        defer recoverAsBreak(&token)
        if n > 0 {
            i := 0
            x(func(e Any) {
                i++
                y(e)
                if i >= n {
                    panic(&token) // break from Each
                }
            })
        }
    }
}

type token_t int

func recoverAsBreak(t *token_t) {
    r := recover()
    if r != nil && r != t {
        panic(r)
    }
}

ここで一意性の保証について補足しよう。 ゼロ・サイズではない変数のアドレス (ここでは &token) の一意性は,あくまでアドレス型での比較演算に限れば Go の言語仕様で陽に保証されている。 しかし生のバイト列の値としてみたときは,偶発的に同じ値をもつ整数等が出現するかもしれない。 それでもこのコードに問題はない。 recover() の戻り値はインタフェース型 interface{} であり,インタフェース値との比較演算で等しいと判定されるにはインタフェース値の実行時型との一致が求められる。 アドレスは整数その他とは型で区別される。 したがって panic(&token) に対応する recover() を除き,その戻り値が偶発的に &token と等しいと判定されることはない。

列をリストに変換する Enumerable.ToList [microsoft.com] 相当のメソッドは次のように定義できる。 Each 型の x による繰返しごとに各要素をリスト y の末尾に追加する。

func (x Each) ToList() *list.List { // ~ "to_a" in Ruby
    y := list.New()
    x(func(e Any) {
        y.PushBack(e)
    })
    return y
}

この ToList メソッドを利用して,列を配列のスライス (事実上の可変長配列) に変換する Enumerable.ToArray [microsoft.com] 相当のメソッドを次のように定義できる。

func (x Each) ToArray() []Any { // ~ "to_a" in Ruby
    y := x.ToList()
    z := make([]Any, y.Len())
    i := 0
    for e := y.Front(); e != nil; e = e.Next() {
        z[i] = e.Value
        i++
    }
    return z
}
もしも Go 言語に C# のようなジェネリックがあったならば,このメソッドは T を型変数としたとき Each<T> 型のレシーバ に対して []T 型の戻り値を返すメソッドとして定義したかったところです。

一方,Each 型の値を新しく構築する関数 (事実上のコンストラクタ) は単に手続きを返す関数として定義できる。 下記は Enumerable.Range [microsoft.com] 相当の関数を定義する。

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

これらのメソッドと関数を使った例を示す。

package main

import (
    . "fmt"
    . "linq"
    "strings"
)

func main() {
    x := Range(1, 30).Select(func(i Any) Any {
        Print(i)
        return Sprintf("%d", i)
    }).Where(func(s Any) bool {
        Print("-")
        return strings.ContainsRune(s.(string), '3')
    }).Take(3).ToArray()
    Println()  //=> 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-
    Println(x) //=> [3 13 23]
}

これを "Ruby 2.0 メモ: Lazy と LINQ とループ融合 - 5. C# の LINQ との比較" の C# のプログラム例と比較しよう。

便宜のため "Ruby 2.0 メモ: Lazy と LINQ とループ融合 - 5. C# の LINQ との比較" の C# プログラムを下記に引用します。
using System;
using System.Linq;

class B
{
    static void Main(string[] args)
    {
        var x = Enumerable.Range(1, 30)
            .Select((i) => {
                    Console.Write(i);
                    return i.ToString();
                })
            .Where((s) => {
                    Console.Write('-');
                    return s.Contains("3");
                })
            .Take(3)
            .ToArray();

        Console.WriteLine("=> " + String.Join(", ", x));
    }
}
ここで Go と C# それぞれのコードの変数 x の宣言の右辺を比べると次のことに気付きます。
  1. Go では Any 型の s に対して s.(string) のように型アサーションを使って string 用の関数 strings.ContainsRune に適合させています。 型検査は静的ではなく動的に行われます。 C# ではジェネリクスにより s は string 型としてコンパイルされます。 string のためのメソッド Contains をキャストなしに型安全に呼び出せます。
  2. Go では i と s の仮引数宣言にいちいち型を付ける必要があります。 C# では仮引数に対する型推論を使って型の指定を省略しています。
この場合についていえば,C# と比べ Go は型の指定が煩雑な上に実行時に型アサーションの余分な処理がかかり,さらに型安全性も保証されていない残念な言語であると言わざるを得ません……。

4. 実行例

添付のソースの Linux 上での実行例を示す。Mac OS X でも同様である。 前節のプログラム例GOPATH=`pwd` go run linq_test1.go で実行されている。

01:~/tmp$ tar xvf ../Downloads/go-linq-24-11-28.tar.bz2
src/
src/linq/
src/linq/linq.go
linq_test1.go
linq_test2.go
linq_test3.go
01:~/tmp$ GOPATH=`pwd` go run linq_test1.go
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-
[3 13 23]
01:~/tmp$ GOPATH=`pwd` go run linq_test2.go
[]linq.Any{2, 7}
[]linq.Any{2, 7}
[]linq.Any{"2", "7"}
[]linq.Any{50, 55}
[]linq.Any{[]int8{2, 7, 1, 8, 2, 8}}
01:~/tmp$ GOPATH=`pwd` go run linq_test3.go 100
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fiz
z 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz
 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 Fi
zzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz
 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 
98 Fizz Buzz 
01:~/tmp$  
Windows の Cygwin からは次のようにすれば同様に実行できます。 cygpath コマンドの -a オプションでカレントディレクトリ "." を絶対パスで,-w オプションでそれを Windows 形式で取得します。
01:~/tmp$ GOPATH=`cygpath -w -a .` go run linq_test1.go

linq_test2.go のコードを示す。 これは配列や文字列から Each 値を得るテストである。

package main

import (
    . "fmt"
    . "linq"
)

func main() {
    z := Enumerable([]int{2, 7, 1, 8, 2, 8}).Take(2).ToArray()
    Printf("%#v\n", z) // => []linq.Any{2, 7}

    z = Enumerable([]Any{2, 7, 1, 8, 2, 8}).Take(2).ToArray()
    Printf("%#v\n", z) // => []linq.Any{2, 7}

    z = Enumerable([]string{"2", "7", "1", "8", "2", "8"}).Take(2).ToArray()
    Printf("%#v\n", z) // => []linq.Any{"2", "7"}

    z = Enumerable("2718281828").Take(2).ToArray()
    Printf("%#v\n", z) // => []linq.Any{50, 55}

    z = Enumerable([]int8{2, 7, 1, 8, 2, 8}).Take(2).ToArray()
    Printf("%#v\n", z) // => []linq.Any{[]int8{2, 7, 1, 8, 2, 8}}
}

ここで Enumerable 関数は src/linq/linq.go で次のように定義した。

func Enumerable(x Any) Each {
    switch x.(type) {
    case []int:
        return func(y func(Any)) {
            for _, value := range x.([]int) {
                y(value)
            }
        }
    case []string:
        return func(y func(Any)) {
            for _, value := range x.([]string) {
                y(value)
            }
        }
    case []Any:
        return func(y func(Any)) {
            for _, value := range x.([]Any) {
                y(value)
            }
        }
    case []interface{}:
        return func(y func(Any)) {
            for _, value := range x.([]interface{}) {
                y(value)
            }
        }
    case string:
        return func(y func(Any)) {
            for _, value := range x.(string) {
                y(value)
            }
        }
        // XXX More clauses should be added for other types...
    }
    return func(y func(Any)) {
        y(x)
    }
}
この関数はやや長いのですがそれでも不完全です。 場合分けの欠如のため,[]int8 の配列がそれ全体を要素とする長さ1の仮想的な列として扱われていることに注意してください。 また []Any と []interface{} が別個の場合分けとなっている点にも注意してください。 もしも Go にジェネリクスがあればこの状況は大いに改善されます。

linq_test3.go のコードを示す。 これは "Ruby のための LINQ ライク・メソッドの使用例 - 2. FizzBuzz を n 個だけ表示する" の例に相当する。 自然数 1, 2, 3, ... の無限の列を表す infSeq の定義の簡単さに注目しよう。

package main

import (
    . "fmt"
    . "linq"
    "os"
    "strconv"
)

var infSeq Each = func(y func(Any)) { // 1, 2, 3, ...
    for i := 1; ; i++ {
        y(i)
    }
}

func main() {
    n, err := strconv.Atoi(os.Args[1])
    if err != nil {
        panic(err)
    }

    fizzbuzz := infSeq.Select(func(e Any) Any {
        i := e.(int)
        if i%3 == 0 {
            if i%5 == 0 {
                return "FizzBuzz"
            } else {
                return "Fizz"
            }
        } else if i%5 == 0 {
            return "Buzz"
        }
        return i
    })

    fizzbuzz.Take(n)(func(e Any) {
        Print(e, " ") // => 1 2 Fizz 4 Buzz Fizz 7 8 Fizz ...
    })
    Println()
}
便宜のため "Ruby のための LINQ ライク・メソッドの使用例 - 2. FizzBuzz を n 個だけ表示する" の Ruby プログラムと実行例を下記に引用します。
#!/usr/bin/env ruby

require '_enum'

n = ARGV[0].to_i

fizzbuzz = (1 .. 1.0/0)._map {|i| 
  if i % 3 == 0 then
    if i % 5 == 0 then
      :FizzBuzz
    else
      :Fizz
    end
  elsif i % 5 == 0 then
    :Buzz
  else
    i
  end
}

fizzbuzz._take(n).each {|i|
  print i, " " 
}

puts
01:~/tmp$ ./fizzbuzz.rb 100
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fiz
z 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz
 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 Fi
zzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz
 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 
98 Fizz Buzz 
01:~/tmp$  

5. おわりに

Go 言語は,関数クロージャを備えた手続き型言語という Ruby や C# さらには C++ 11 まで含む有力なプログラミング言語の大グループに属しながら,そこに共通する暗黙の常識をいくつかの点で破っている新しい手続き型言語である。 問題に対して別の見方を与えながら,なおかつその表現力に遜色がない点で興味深い。 ここでは高階関数型に対して直接 LINQ メソッドを定義することで,その一端を示した。

しかし,同時に Go の弱点として,ジェネリクスの欠如による静的な型安全性の弱さと, 仮引数での型推論の欠如によるコードの煩雑化の問題も明らかにしました。 対照的に,C# 4.0 メモ: Lazy による遅延リストの作成 に見るように現行の C# はこれらの点で優れています。 だがそれでも希望はあります。 Go 言語公式サイトの FAQ - Why does Go not have generic types? [golang.org] には "Generics may well be added at some point." と書かれています。 ジェネリクスの欠如の問題は将来解決するかもしれません。 型推論の強化も,少なくとも現行の C# にある範囲のものならば十分容易に実現可能でしょう。
そのとき Go でも LINQ が実験レベルにとどまらず実用的になるはずです。 Go のユニークな特徴と組み合わせたとき,C# と異なるどのような世界が開けるかと期待されます。

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