有理数を含む混合演算のための Go 言語パッケージの試作

2013-01-23 (鈴)

1. はじめに

Go 言語は無限多倍長有理数を標準パッケージ "math/big" でサポートしている (big - The Go Programming Language [golang.org])。 これを使って Scheme や Arc (Java による半分の Arc の改訂実装) に見られるような有理数を含む混合演算を簡単に実現できる。 ここではその試みを記述する。

2. 有理数を含んだ混合演算

Java の java.lang.Number クラスに相当するような数を表す共通の基底型が Go 言語にはない。 そこで次のようなインタフェースを定義し,これをそのような基底型であると見立てる。

type Number interface{}

Number は int32, float64 または *Rat を表す型とする。ここで *Rat は "math/big" が定義する無限多倍長有理数の構造体 Rat (rational number, 有理数) へのポインタ型である。 ただし,便宜のため関数の引数としては int, int64 も許す (実行時の値によって int32 または *Rat へと変換する)。

ただし,あくまでこれはそう見立てた取り決めであって,Go 言語の仕様上は任意の型の値がこの Number 型に適合します。 今の Go 言語にはコンパイラにその妥当性を検査させる手だてがありませんから,実行時に型をチェックします。 つまり,今のところ Number 型それ自身には,数を表すものだというコメント以上の意味はありません。

混合演算を実現する基本的なアイディアは次の三つである。

  1. int32 による整数の演算を int64 による倍長整数で行い,結果が 32 ビットに収まるならば int32 に変換する。 収まらなければ *Rat に変換する。
  2. 浮動小数点数を相手とする演算は,自分も浮動小数点数に変換してから行う。
  3. 有理数と有理数,有理数と整数の演算は両方を有理数として行うが,結果の有理数が int32 で表現できるならば int32 に変換する。

乗算の実装を下記に示す。

// 乗算: Multiply(7, 2) => 14
func Multiply(a, b Number) Number {
    switch x := a.(type) {
    case int32:
        switch y := b.(type) {
        case int32:
            return regulateInt64(int64(x) * int64(y))
        case float64:
            return float64(x) * y
        case *Rat:
            z := NewRat(int64(x), 1)
            return regulateRat(z.Mul(z, y))
        }
    case float64:
        switch y := b.(type) {
        case int32:
            return x * float64(y)
        case float64:
            return x * y
        case *Rat:
            return x * ratToFloat64(y)
        }
    case *Rat:
        switch y := b.(type) {
        case int32:
            z := NewRat(int64(y), 1)
            return regulateRat(z.Mul(x, z))
        case float64:
            return ratToFloat64(x) * y
        case *Rat:
            return regulateRat(new(Rat).Mul(x, y))
        }
    }
    return Multiply(regulateArg(a), regulateArg(b))
}

ここでは Number 引数 a, b の実行時の型にしたがって型 switch 文で処理を振り分けている。 適合しない型については関数末尾で regulateArg() を適用して再チャレンジする。 regulateArg() は int, int64 を実行時の値によって int32 または *Rat へと変換する。

int32 どうしの乗算はそれぞれを int64 に変換してから行う。その結果に適用する regulateInt64() の実装を示す。

// int64 の値を可能ならば int32 の値に,できなければ有理数にする。
func regulateInt64(a int64) Number {
    var i int32 = int32(a)
    if int64(i) == a {
        return i
    }
    return NewRat(a, 1)
}

一方が float64 の乗算は他方も float64 にそろえて行う。その結果をそのまま返す。

int32 と *Rat および *Rat どうしの乗算は (int32 を *Rat にそろえてから) Mul メソッドで行う。 その結果に適用する regulateRat() の実装を示す。

// 有理数を可能ならば int32 の値にする。
func regulateRat(a *Rat) Number {
    if a.IsInt() {
        n := a.Num()
        if n.BitLen() < 32 { // 符号ビットを除き 31 ビット長以内か?
            return int32(n.Int64())
        }
    }
    return a
}

完全なコードについては src/arith/num.go を参照されたい。

2.1 コード例

階乗計算の例とその出力を示す。

var n Number = 1
for i := 1; i < 30; i++ {
    n = Multiply(n, i)
    Println(String(n))
}
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
51090942171709440000
1124000727777607680000
25852016738884976640000
620448401733239439360000
15511210043330985984000000
403291461126605635584000000
10888869450418352160768000000
304888344611713860501504000000
8841761993739701954543616000000

完全なコードについては src/arith/num_test.go を参照されたい。

3. Scan 実装

Go 言語は,変数値を入力する C 言語の scanf() に似た一群の関数を,標準パッケージ "fmt" によってサポートしている (fmt - The Go Programming Language [golang.org])。 C 言語の scanf() と異なり,それらの関数はユーザ定義型の変数を入力するように拡張できる。 そのユーザ定義型に対して Scan メソッドを実装して fmt.Scanner インタフェースに適合させればよい。

インタフェースである Number 型に直接 Scan メソッドを設けることはできないから,次の補助的な構造体 NumberScanner を定義する。

type NumberScanner struct {
    Number
}

この構造体に対する Scan メソッドの実装を示す。 この実装では書式指定としてデフォルトで使われる "%v" に加えて "%r" をサポートする。 "%r""123.456" のような小数点付きの数の文字列を float64 ではなく 123456/1000 のような有理数として読み取ることを指定するものとする。

// fmt.Scanner インタフェースのためのメソッドを簡易に実装する
// (十進数のみ,指数表現なし,verb は 'v' または 'r')。
// verb が 'r' のときは int32 または *Rat として読み込む。
func (n *NumberScanner) Scan(ss ScanState, verb rune) error {
    if verb != 'v' && verb != 'r' {
        return Errorf("unsupported verb: %q", verb)
    }
    state := 0
    isFloat := false
    isRat := false
    erred := false
    tok, err := ss.Token(true, func(ch rune) bool {
        switch state {
        case 0:
            if ch == '+' || ch == '-' {
                state = 1
                return true
            }
            fallthrough
        case 1:
            if '0' <= ch && ch <= '9' {
                state = 2
                return true
            }
            return false
        case 2:
            if '0' <= ch && ch <= '9' {
                return true
            }
            if ch == '.' {
                if isFloat || isRat {
                    erred = true
                }
                isFloat = true
                return true
            } else if ch == '/' {
                if isFloat || isRat {
                    erred = true
                }
                isRat = true
                return true
            }
        }
        return false
    })
    if err != nil {
        return err
    }
    s := string(tok)
    if erred {
        return Errorf("invalid number: %q", s)
    }
    if isFloat && verb != 'r' {
        var f float64
        _, err = Sscan(s, &f)
        if err != nil {
            return err
        }
        n.Number = f
    } else {
        r := new(Rat)
        if _, ok := r.SetString(string(tok)); !ok {
            return Errorf("invalid rational number: %q", s)
        }
        n.Number = regulateRat(r)
    }
    return nil
}

入力文字列から実際に字句を取り出す操作は Go 標準パッケージ fmt の実装が供給する ScanState 引数の Token メソッドで行われます。 Scan はその Token メソッドに文字が字句の内か外かを判定する無名関数を与えることによってその動作を制御します。 この無名関数の判定はどこまでどんな文字を読んだかの状態に依存しますが,実装はその状態を無名関数の外側のローカル変数 (無名関数からみれば自由変数) である state, isFloat, isRat に保持します。

ここではこうしてあっさり済ませていますが,もしもローカル変数を自由変数として使える入れ子の関数がなかったならばもっと大げさなコードになっていたはずです。 これがもしも C 言語や昔の C++ や Java だったらどうなっていたか,どうせざるを得なかったか考えてみてください。 ……逆にもっと大昔の Algol 60 ならば,ライブラリさえ整備できたならば Go と同じぐらいエレガントに書けたかもしれません。言語の進化は決して一直線ではありません。

import 宣言等を含む完全なコードについては src/arith/scan.go を参照されたい。

3.1 コード例

NumberScanner の使用例とその出力を示す。

var x NumberScanner
Sscan("123", &x)
Printf("%T %v\n", x.Number, x.Number)
Sscan("-123.456", &x)
Printf("%T %v\n", x.Number, x.Number)
Sscan("355/113", &x)
Printf("%T %v\n", x.Number, x.Number)
Sscan("123456789012345678901234567890", &x)
Printf("%T %v\n", x.Number, x.Number)
_, err := Sscan("1..", &x)
if err != nil {
    Println(err.Error())
}

Sscanf("-123.456", "%v", &x)
Printf("%T %v\n", x.Number, x.Number)
Sscanf("-123.456", "%r", &x)
Printf("%T %v\n", x.Number, x.Number) // -123456/1000 = -15432/125
_, err = Sscanf("-123.456", "%t", &x)
if err != nil {
    Println(err.Error())
}
int32 123
float64 -123.456
*big.Rat 355/113
*big.Rat 123456789012345678901234567890/1
invalid number: "1.."
float64 -123.456
*big.Rat -15432/125
unsupported verb: 't'

完全なコードについては src/arith/scan_test.go を参照されたい。

4. フィボナッチ数列で 1000 桁になる最初の項を求める例

最後に応用例としてフィボナッチ数列で 1000 桁になる最初の項を求めよう。 ただし,第1項と第2項を 1 として数えるものとする。 いろいろなアプローチが考えられるが,ここでは "Go 言語による LINQ to Objects の試作" で与えた "linq" パッケージと組み合わせた例を示す。

// フィボナッチ数列で 1000 桁になる最初の項を求める.
package main

import (
    . "arith"
    . "fmt"
    . "linq"
)

// フィボナッチ数を 1, 1, 2, ... と順に与える内部イテレータ
var fib Each = func(yield func(Any)) {
    var a Number = 1
    var b Number = 1
    for {
        yield(a)
        a, b = b, Add(a, b)
    }
}

func main() {
    // 1 のあとに 0 が 999 続く数を target として用意する。
    var target Number = 1
    for i := 0; i < 999; i++ {
        target = Multiply(target, 10)
    }

    // 数列の項を 1 から数えるように count を用意する。
    count := 0

    // target 以上になる最初のフィボナッチ数を求める。
    value := fib.Where(func(e Any) bool {
        count++
        return Compare(e, target) >= 0
    }).Take(1).ToArray()[0]

    // count とその項のフィボナッチ数を表示する。
    Printf("F(%d) = %s\n", count, String(value))
}

Windows 7 SP1 (x64), go1.0.3.windows-amd64 に対してソース arith-25-01-21.tar.bz2 から展開して実行した例を示す。



ここで使用した Cygwin の bash と mintty の設定については Life with Cygwin 24 を参考にされたい。

Mac OS X や Linux など普通の Unix 類 OS でも同様の手順で実験できる。 ただし,その場合は環境変数 GOPATH を次のようにセットする。

01:~/tmp/arith-25-01-21$ export GOPATH=`pwd`
01:~/tmp/arith-25-01-21$  

5. おわりに

ここで示した有理数を含む混合演算のための "arith" パッケージは Go 言語による Lisp インタープリタ試作の足がかりとして始めたものだった。 しかし §4 の例に示すように通常のコードに違和感なく混ぜて使えるものになったことに我ながら驚いている。

倍長整数を仲立ちにした整数の変換は "Java による半分の Arc の改訂実装" の該当部分の改作である。 §4 のプログラム例は "C# 4.0 メモ: Lazy<T> による遅延リストの作成 - §4" の改作であり,数列を生成するイテレータの実装は "Groovy 応用: LINQ ライクなメソッドによるフィボナッチ数の計算 - §8" の改作である。

これらを振り返り比べると,クラス継承の乱用をつつしみ,制御構造としての高階関数と無名関数を活用する今の手続き型言語の潮流に Go 言語がよく従っていると感ずる。 むしろ,その傾向を先鋭化しているといってもよい。 従来の意味でのクラス継承そのものをなくした点は極端だが,それでも少なくとも混合演算の実現については semi_arc/BuiltinMath.java のような Java プログラムと比べて短所が一つしかなかったことは意外だった。

その短所とは Go 言語のために §2 で定義した Number 型に,値が数を表すというコメント以上の意味をもたせられないことである。 コンパイラは Number に任意の型が適合することを許す。 "Go 言語による LINQ to Objects の試作" と同じ論点ではないが,静的型安全性の貧弱さが現在の Go 言語の弱みである。

ソースを展開して環境変数 GOPATH を設定した後,次のようにして "arith" パッケージや "linq" パッケージを含む Go 言語ドキュメントをブラウザで読むことができます。 パッケージのドキュメントはソースから自動的に生成されます。

01:~/tmp/arith-25-01-21$ godoc -http=:6060 &
[1] 212
01:~/tmp/arith-25-01-21$  

上図の Example (Factorial) のコード例は src/arith/num_test.go にある ExampleNumber_factorial 関数のコードが関数名の取り決めにしたがって自動的にドキュメントの type Number の項に配置されたものです。 Output 例にはコードの Output: コメントの内容が写されています。 同じコメントが go test arith を実行したときテストの結果判定に使われます。 つまり,簡単な取り決めにしたがって1回サンプル・コードとその出力のコメントを書けば,自動的にドキュメントと単体テストの両方に役立ちます。 詳しくは testing - The Go Programming Language [golang.org] を参照してください。 Go のクールな一面です。


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