このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

多値関数の話をもう少し -- 課題を3つ

多値関数の話をもう少し続けます。

最初に、ここで言っている「多値」の意味を限定して、それから3つほど問題を提示します。

ここで扱う多値とは

まず、「多値」(multiple-value)という1つの言葉に抱くイメージが色々あるみたいですから、絞り込んでおきますね。

  1. 多値は、非決定性ではない。
  2. 多値は、複合データ(タプルなど)を値とすることではない。
  3. 多値は、主たる値とオマケの値達のことではない。

少し説明:1番目は、非決定性は異なる話題として区別しましょう、ってこと。2番目; もし複合データを多値とするならば、配列を返しても/オブジェクト参照を返しても多値だってことになって収拾がつかないから。3番目はどういうことかっていうと; 例えば、割り算関数は基本的に商を返すのだが、もったいないから余りも一時的に保存していて、必要とあらば(何か特別な構文で)余りも取り出せる、と、そういうのは範囲外にしようってことです。

それで、もともとの問題意識が「なんで、引数はn個なのに戻り値は1個なんでしょう?」だったので、この線に沿って考えます。つまり、「複数引数と複数戻り値を対等に扱おうよ」の方針。

lethevertさんは、上の方針を「対称性」という言葉で表現し、Concurrent Cleanが「対称」とは呼べないことを示す例を出しています。


f a b = (a*2, b*2) // 引数aとbのそれぞれ2倍を2つの値として返す
(x, y) = f(f(1, 2)) // 結果は(4, 8)のはずだが、実際はできない

Kuwataさんによる、Pythonの同様な例。


def f(x, y, z):
return x+y, y+z, x+z

def f2(x, y, z):
return x+y+z

f2(f(3, 2, 1)) # エラー!
f2(*f(3, 2, 1)) # アンパックすれば OK

僕としては、引数/値の「対称性」または「対等性」が欲しいので、次も条件に入れます。

  • n値関数とn引数関数は(何の細工もしなくても)結合(compose)可能である。

アリティのチェックと結合方式

通常の意味でのデータ型は考えないことにして、関数の引数の個数(これをアリティと呼ぶ)、戻り値の個数(コアリティと呼ぶ)だけを考えます。fがアリティn、コアリティmである(つまり、n-in m-outの)ことをf:n→m と表記しましょう。

f:n→m、g:j→kだとして、fとgが結合可能(composable)に関して、3つの定義が可能でしょう。

  1. m = jのときだけ結合可能とする。
  2. m ≧ j のとき結合可能として、余った値は捨てる。
  3. m ≧ j のとき結合可能として、余った値はそのまま出力に流す。

3番目では、fとgの結合は(k + m - j)個の戻り値を持ちます。「m < j のとき補完する」話は今はしません(out-of-scope)。

実は、1番目だけを基本にとって、2番目と3番目を実現できます。値を捨てる関数をdischarger、値をそのまま流す関数をidentityというのですが、gに対してdischargerを挿入すれば「捨てる方式」、gに対してidenittyを挿入すれば「そのまま流す方式」を実現できます。(http://www.chimaira.org/docs/EtbDiagrams.htmでは、dischargerとidentityをそれぞれ放電器、ストレートジャンクションと呼んでます。)

それはともかく、使い勝手としては、どの結合方式がいいのでしょうかね。「fのコアリティ=gのアリティ」以外はエラーとするのが安全な気がするのですが、チェックがきつすぎて(人間が)イヤになるかもしれませんし。

可変アリティ/コアリティ

単値関数でも、可変引数はあります。これがないと不便ですよね。例えば、足し算関数は sum(2, 3), sum(2, 3, 1), sum(2, 3, 1, -5)とか使いたいですから。可変アリティを許すとは、sum:2→1, sum:3→1, ...をすべて考えること、あるいは、sum:{2, 3, ...}→1 の形のアリティ指定を認めることです。

では、コアリティのほうも可変てのはどうでしょう。自明な例として、n引数をそのままn値で返す関数をidとすると、これはコアリティも可変です。コアリティも可変だとすると、静的な(コ)アリティチェックは困難、なんかイヤーな予感がするんですが… それと、同じ関数名(記号)に対し、アリティに応じて別な定義本体と別なコアリティを割り当てることは、オーバーロードでもあります。

可変アリティ、可変コアリティ、オーバーロード; 多値関数の文脈では、これらはどう取り扱うべきでしょうか。

ラムダ計算

カリー化を使えば、f(x1, x2, ..., xn)は (...((f x1)x2)...)xn の略記として解釈されます。ようするに、高階関数を導入して、すべての関数を1引数にしてしまうわけです。これで、計算を1-in 1-outの世界に持ち込めます。では、多値をラムダ計算でどう扱うのでしょうか? 引数に関するカリー化のように、戻り値の多値を1値に還元する方法があるのでしょうか。

タプルを作る機構を最初から入れてしまう、とか、タプルを通常のラムダ式でエミュレートする方法はあるでしょうが、それはつまらない。「複数引数と複数戻り値を対等に扱おうよ」スタイルのラムダ計算は構成できるのでしょうか。すでに計算体系がありそうですが、僕は知りません。

なお、ここでいうラムダ計算とは、ラムダ風の構文(あまりうるさいことは言わない)を持った形式計算系で、ラムダ抽象を備え、納得のいくdenotationを持つものです。

※ アリティの計算が、線形論理のシーケント計算と似てる気がする、これはなに?