多値について本気で考えてみた

Go 妄想

先日のエントリの反応として、多値の批判をしているように受け取られた方がいました。 実際には、多値の批判をしているのではなく、Go言語の「多値とそう見えるけど違うものがある」という仕様を批判したものでした。

また、タプルにこだわっているという受け取り方をした方もいました。 このエントリでは、「タプルにこだわっているのではない、多値にこだわっているのだ」ということを説明しようと思います。 このエントリで出てくるコードは言及がない限り妄想上のもので、実際の言語のコードではありません。

長いから3行で。

  • スタックマシンと多値は仲良し。継続と多値も仲良し。
  • 多値は多値、タプルはタプル、みんなちがってみんないい。
  • 多値とは、カンマで区切られた単なる複数の値だよ。妄想だけどね。

これで満足して仕事に戻っていただいて構いません。以下オマケ。

多値とタプルの違い

まず、多値とタプルの意味的な違いについてをはっきりさせておきましょう。 ただし、多値はタプルと違って扱える言語が少ない*1うえ、各言語での違いもそれなりに大きいため、ここで紹介する違いは参考程度に考えてください。

他の値の一部になれるかどうか

タプルは何の制約もない、単なる値です。 そのため、他の値の一部になれます*2。 当然、タプルの要素にタプルを入れるという風に、入れ子構造も取れます。

それに対して、多値は他の値の一部にはなれません。 例えば、クラスのフィールドに多値を含むこともできませんし、多値の要素として多値を含むこともできません。 これを、制約の付いた型と見なすこともできますが、単に多値はファーストクラスのオブジェクトではないと考えてもよいでしょう。

多値は制限されたタプルなのか

ここまででは、多値は制限されたタプルであり、多値には何のメリットもないとしか思えないかもしれません。 しかし、多値には効率という大きなメリットがあるのです。 その話に入る前に、多値と相性のよいものについて見ていきましょう。 スタックマシンと、継続です。

スタックマシンと多値

まずはスタックマシンです。 スタックマシンというのは、スタックを用いて計算を行う計算機のことを言いますが、ここでは詳細には踏み込みません。 Java仮想マシンや、.NETのCLRや、RubyVM(旧称YARV)などもスタックマシンをベースにしています。少なくとも30億のデバイスでスタックマシンは動いていることになりますね。すごい。

スタックマシンでの関数呼び出し

スタックマシンでは、引数をスタックに積んでから関数に処理を移すだけで関数呼び出しができます。 例えば、Javaで次のようなメソッドを書いたとしましょう。

public static int add(int a, int b) {
    return a + b;
}

このメソッドを add(10, 20) のように呼び出した場合、以下のようなバイトコードが出力されます。

bipush 10           // byte範囲に収まる数値10をpush
bipush 20           // byte範囲に収まる数値20をpush
invokestatic add    // addメソッドを呼び出す

これをスタックの状態を含めて図にすると、このような感じになります。

|    | bipush 10 |    | bipush 20 | 20 | invokestatic add |    |
|    |---------->| 10 |---------->| 10 |----------------->| 30 |
+----+           +----+           +----+                  +----+

まさに、スタックに引数を積んでから関数が呼び出されています。 そして、結果はスタックに積まれます。

関数から戻る場合はどうでしょうか。 上で作った add のバイトコードを見てみましょう。

iload_0 // 0番目の引数を整数としてpush
iload_1 // 1番目の引数を整数としてpush
iadd    // スタックに積まれた2つの整数を加算、結果をpush
ireturn // スタックに積まれた数値を戻り値としてメソッドからreturn

add(10, 20) で呼び出された場合のスタックの移り変わりはこのようになります。

|    | iload_0 |    | iload_1 | 20 | iadd |    | ireturn
|    |-------->| 10 |-------->| 10 |----->| 30 |-------->
+----+         +----+         +----+      +----+

スタックマシン上での多値の表現

スタックマシンでは、多値はスタック上に積まれた(複数の)値でしかありません。 n個の値を積んで関数を呼び出すということは、n値を入力にする関数を呼び出すということですし、 m個の値を積んだ状態で関数からreturnするということは、m値を出力として関数を終えた、ということです*3。

これはとてもきれいですよね。 例えばGo言語がスタックマシン上で実装されているとしたら、

func add(a int, b int) int {
    return a + b
}

func f(a int) (int, int) {
    return a, a * 2
}

add(f(3))

は、

push 3
call f      // 3が積まれた状態でfを呼び出す。実行が終わるとスタックに値が2つ積まれている。
call add    // 3と6がスタックに積まれた状態でaddを呼び出す。

と表現されていることでしょう。

継続と多値

継続について説明しだすと延々と横道にそれていってしまうので、 解説ページ へのリンクだけ置いておきます。 未完成部分が埋められることはもはやないと思われます。残念。

さて、継続と多値の関係ですが、継続とはつまるところ「関数からのreturnを、returnした後の処理を表す関数呼び出し」と考えてしまおう、ということです*4。 このとき、「継続に渡される引数が複数個ある」ということの意味を考えてみましょう。 「継続に渡される引数」は、「returnされた値」に対応しますので、これが複数個あるということは「複数の結果が関数から返ってきた」ことを意味します。 つまりは多値です。

すべてを継続で考えれば、returnはすべて関数の引数になります。 その世界においては、多値とは単に継続(もしくは関数)に渡す引数が複数あるというだけとなります。 これもとてもきれいですね。

ちょっと無理やりですが、Go言語であればこのようなイメージの世界です。

// スタックマシン上での多値の表現で使ったプログラムをreturnやGo言語の多値なしに表現してみた例
func add(a int, b int, k func(int)) {
    k(a + b) // returnの代わりに継続を呼び出す
}

func f(a int, k func(int, int)) {
    k(a, a * 2) // returnの代わりに継続を呼び出す(多値！)
}

func main() {
    f(3, func(a int, b int) { // fは多値を関数の引数として渡してくる
        add(a, b, func(x int) {
            fmt.Println(x)
        })
    })
}

returnもGo言語の多値も使っていませんが、やっていることはGo言語の多値を使ったコードと同じです。

ちなみに、継続を扱える言語であるSchemeでは、多値を作る関数をこう定義できます。

(define (values . xs)
  (call/cc (lambda (k) (apply k xs))))

call/cc で values 呼び出し以降の処理を切り取って k とし、その継続に values の引数を入れるという、まさに「継続の引数が多値である」をそのまま表したコードになっています。 きれいだ・・・！

関数

さて、ここまでは多値と相性のよいものを見てきました。 ここからは、関数について少し考えてみます。

関数型プログラミング言語と関数

メジャーな関数型プログラミング言語では、関数は1入力1出力というモデルです。

多入力したい場合は「関数を返す関数」のように関数を値として扱えるようにしたことで解決しています(カリー化というやつ)。

// F#
// let add x y = x + yと同じ
let add = fun x -> fun y -> x + y

多出力したい場合はどうでしょうか。 これも、「関数を受け取る関数」により実現できます。 これはつまり、継続で見た方法です*5。

// F#
let f = fun x -> fun k ->
  k x (x * 2) // (k x)で返ってきた関数に(x * 2)を適用

// シンタックスシュガーを使うと、
// f 3 (fun x y -> add x y)
// とか
// f 3 add
// とか書ける
f 3 (fun x -> fun y ->
  add x y // (add x)で返ってきた関数にyを適用
)

このように、関数型プログラミング言語では1入力1出力の関数だけですべてを表せる世界を作っているわけです*6。 これはこれできれいですね。

手続き型プログラミング言語と関数

Go言語を除いた多くの手続き型プログラミング言語では、関数は多入力1出力です。 なぜ入力は複数許すのに、出力は1つか許してないのでしょうか。 自分はC言語が1つの戻り値しか許さないようになっていたのをずっと引きずってきたのではないか、と考えています。

アセンブリレベルまで降りていけば、そもそもレジスタを使って複数の値を返すようなサブルーチンなんかは普通に書けるわけです。 x86であれば、divはeaxに商を、edxに余りを格納しますが、これも多値を返していると見なせます。

アセンブリレベルまで降りれば多値が使えるのに、今までのプログラミング言語ではそれを有効活用してこなかったことになります。 これは、手続き型プログラミング言語が計算機を効率よく使えるように進化してきたことを考えると、少し不幸な感じがします。 Go言語は、そういった世界をぶち壊すインパクトを持った言語だと思います*7。

タプルと多値(と手続き型プログラミング言語)

多値はネストができません。他の値の要素となることもできません。 この制約によって多値は何を手に入れたのでしょうか。

それは、効率です。 多値と同じようなものとみられることもあるタプルですが、タプルはあくまで1つの値に複数の値をパックしたものです。 パックする処理(タプルの構築)も、アンパックする処理(タプルの分解)も、どれもタダというわけではありません。 言語処理系において、タプルの効率を上げようとする試みはいくつもありますが、タプルが値である以上、すべてのタプルを最適化できるわけではありません。

それに対し、多値は単なる複数の値であり、それ自体は値ではありません(スタックに積んであるだけ、レジスタに並んでいるだけ)。 そのため、パックやアンパックなどとは無縁の世界で生きていられます。

手続き型プログラミング言語でも関数がファーストクラスの値として使えるような言語が増えてきましたが、 手続き型プログラミング言語は本来、計算機を効率を程よく保ったまま抽象的に扱えるようにした言語であるべきではないでしょうか(ただし異論は認める)。 その場合、関数だのタプルだのをファーストクラスで扱えることにこだわらず、効率よく扱えるものを扱うにとどめるという割り切った言語があってもいいと思います。

ただ、ユーザー定義できる型とジェネリクスがあるとそれだけでタプルが作れてしまうので、多値がないがしろにされがち、というのはあるかもしれません。

多値とは

さて、多値とは何者でしょうか。

  • 「単なるスタックに積まれた値だよ」
  • 「単なる継続の引数だよ」
  • 「Go言語の多値が多値だよ」

色々と意見はあるでしょうが、ここからは「カンマで区切られた単なる複数の値だよ」という妄想の世界の話です。 ちなみに、上の3つだと一番下が一番近いです(が、別物です)。

多値かくあるべし！

架空の言語(WillGoとでもしておきましょう)を考えます。 この言語では、多値はカンマで区切られた単なる複数の値です。 どういうことか見てみましょう。 まずは、多値を返す関数です。

// 型と値の間にはコロンを置く(趣味)
// 多値を出力する関数は、出力する型をそれぞれカンマで区切って表現する
func f(a: int): int, int {
    return a, a * 2 // 多値を返している。
}

x, y := f(3) // x, yというのは多値を表している。

多値はカンマで区切られたものとして表現されていますね。

多値を受け取る関数も見てみましょう。

// a: int, b: int というのは、多値を受け取る関数であることを表している。
// 関数の出力で多値を表す場合と同じ表現であることが分かる。
func add(a: int, b: int): int {
    return a + b
}

result := add(1, 2) // 1, 2というのは多値を表している。

当然、多値を返す関数の結果をそのまま多値を渡す関数に渡せます。

result := add(f(3)) // 多値を渡す関数に多値を返す関数の結果をそのまま渡している。

ここまではいい感じですね。

多値かくあるべし・・・？

さて、多値は「カンマで区切られた単なる複数の値」でした。 ここから、妄想らしくなっていきます。

// 4引数版addを定義。
func add4(a: int, b: int, c: int, d: int): int {
    return a + b + c + d
}

result := add4(1, 2, 3, 4) // 1, 2, 3, 4は多値。

この add4 に対して、こんな呼び出しはどうでしょうか。

res1 := add4(1, 2, f(3))
res2 := add4(1, f(2), 3)
res3 := add4(f(1), f(2))

くどいようですが、多値は「カンマで区切られた単なる複数の値」でした。 であるならば、「そこに展開した結果がvalidであればvalidとする」としてもいいと思いませんか。 きれいだ・・・！

きれいな多値の分かりにくさ

さて、この架空の言語ですが、関数呼び出しを見ても引数の個数が分からないという問題があります。

res3 := add4(f(1), f(2)) // 2引数関数に見える

今どきのIDEなら、コード上に書かれていない文字列を表示するくらいやってのけるので、IDE前提であれば使えるかもしれません。

// 上のコードは、IDEで開くとこう見える(実際に書いてない部分はグレーアウト)。
res3 := add4(a, b=f(x=1), c,d=f(x=2))

もしくは、関数名さえ気を付ければそれほど問題にはならないかもしれません。

ちなみに、実在するGoという言語はこの問題に足を片方入れています。

// Go言語
res := f(g()) // さて、fは何引数関数でしょう？

そこまでやったのであれば、きれいな多値が欲しくなりませんか？

可変長引数と多値、もしくは可変長戻り値と多値

ここまでくると、行くところまで行ってみたい気がしますね。 引数を何個でも指定できる関数というものがあります。

func sum(xs: ...int): int {
    res := 0
    for _, x range xs {
        res += x
    }
    return res
}

result := sum(1, 2, 3)

では、戻り値を何個でも指定できる関数というのはどうでしょうか。

func f(b: bool): ...int {
    if b {
        return 1, 2
    } else {
        return 4, 5, 6
    }
}

これは、通常の手段では受け取れない関数となります。 この結果を使うためには、可変長引数の関数が必要です。

result := sum(f(true))

または、コンパイル時定数が渡された場合のみ受け取れるようにするのも面白そうです*8。

a, b, c := sum(f(false)) // OK
d, e, f := sum(f(true)) // コンパイルエラー

スライスに変換する組み込み関数があれば(効率以外は)問題ありません。

xs := valuesToSlice(f(true))
ys := valuesToSlice(f(false))

これで、多値を「カンマで区切られた単なる複数の値」としてみなしても成り立ちそうだということがなんとなくわかっていただけたかと思います(便利だとは言っていない)。

このように、多値は多値で面白い世界が広がっているのです。 Go言語の多値は始まりでしかありません。 みなさんも自分だけの多値の世界を考えて、どんどん多値のすばらしさを世界に発信していきましょう！

参考ページ

*1:メジャーな言語だとScheme/Common LispとGoくらいではないでしょうか。何をメジャーに入れるかという問題はありますが。※Luaも多値を持っているようです。Twitterで教えてもらいました。※GHC拡張にもUnboxed Tuplesという構文拡張があるようです。これもTwitterで教えてもらいました。

*2:クラスのフィールドとして持たせられる。

*3:ただし、上で例に挙げたJava仮想マシン(や、他の仮想マシン)では、m個の値を積んだ状態で関数からreturnすることを許していません。

*4:http://www.kmonos.net/wlog/95.html#_1109090307 という記事を思い出したので置いておきます。この記事では、returnを関数と見なすとどうなるだろう、という思考実験をしています。

*5:多入力と多出力で戻り値の位置に関数がくるか、引数の位置に関数がくるかが入れ替わるのも面白いですね。双対性というやつでしょうか。

*6:念のため: 実際にこんなコードは書きません。

*7:しかし、前のエントリでも書いたように、Go言語は多値っぽいけど多値じゃないものを入れてしまったのでそこはすごく残念。

*8:ただし、コンパイル時間は無視するものとする。