関数に色をつけるべきか：LunarMLの場合

function coloring problem（関数色付け問題）という概念がある。知らない人のために説明すると、こういうことだ：

とあるプログラミング言語では、関数に色がついている。どの関数も、「青」か「赤」のいずれかの色を持つ。関数呼び出し構文にも色がついている。青い関数の呼び出し元の色はどちらでも良いが、赤い関数は赤い関数からしか呼び出せない。赤い関数の呼び出しには何らかの煩雑さが伴う。いくつかの重要な関数は赤い。

このような言語では、例えば map のような高階関数は色ごとに2通り書く必要があるだろう：

red_function red_map(f: a -(red)-> b, array: a[]): b[]
{
    let result = [];
    for (let i = 0; i < array.length; ++i) {
        result.push(f(array[i])red);
    }
    return result;
}
blue_function blue_map(f: a -(blue)-> b, array: a[]): b[]
{
    let result = [];
    for (let i = 0; i < array.length; ++i) {
        result.push(f(array[i])blue);
    }
    return result;
}

（この言い回しの初出はこの記事と思われる：「What Color is Your Function? – journal.stuffwithstuff.com」）

この概念を初めて聞いた人は、「そんな面倒くさい概念のある言語は実用的ではない」と思うかもしれない。しかし、勘の鋭い人はピンとくるだろう：「通常の関数とasync関数のことか」、と。

非同期処理を書きやすくするためにいくつかの言語に導入されているasync関数では、async関数を呼び出して結果を利用するには呼び出し元もasyncである必要がある。

この記事では、私が開発しているLunarMLという言語処理系で関数色付け問題をどう扱うかを検討する。

LunarMLの事情：これまで

LunarMLはStandard MLという言語をベースにしており、関数の型は一種類しかない。つまり、関数に色はついておらず、a -> b という通常の関数型だけがある。入出力はデフォルトでは同期的だ。

LunarMLはNode.jsやWeb向けのJavaScriptコードを生成することができる。JavaScriptは非同期処理を活用するエコシステムを持ち、入出力も非同期に行われる。async（Promiseを返す関数）と通常の関数では、結果を利用したいときの呼び出し方も違う（通常の関数呼び出しか、awaitを使う呼び出しか）。

この食い違いにどう対処するか？LunarMLが現在採用している戦略は、すべての関数をCPS変換するというものである。正確には、JavaScriptバックエンドに「すべての関数をCPS変換するモード」（JS-CPSバックエンドと呼んでいる）とそうではないモードを用意して、前者では入出力を使えるようにする。後者では入出力は制限される。この戦略では、関数に色はつかない。

この話はML Family Workshopでの発表でもした：

ML Family WorkshopでLunarMLについて発表した

しかし、最近「やっぱり関数に色をつける選択肢があってもいいのでは」と思うようになってきた。理由を2つ挙げる。

理由1：すべてCPS変換するのはオーバーキルではないか

理由その1は、すべての関数をCPS変換するのはやりすぎなのでは感が若干あることだ。ちゃんとパフォーマンスを測定したわけではないが、CPS変換によるオーバーヘッドがゼロということはないだろう。そうすると、デフォルトでは直接形式（CPS変換しない）で、必要な部分だけCPS変換するという選択肢を用意しても良いだろう。

関数の色は、型の違いとして表現する：

val f : a -> b (* 通常の関数 *)
val g : a ->[async] b (* 非同期関数（文法は架空） *)
val async : ('a ->[async] 'b) -> 'a -> 'b promise
val await : 'a promise ->[async] 'a

関数に色をつけるとして、「限定継続を使った任意の処理（汎用的なCPS変換）」を使えるようにするか、それとも非同期処理に特化するかはまだ考えがまとまっていない。

理由2：複数回制御を返す関数を許容するか

次の関数 f と g は等価だろうか：

function f(h: unit -> unit)
{
    let a = [];
    h();
    a.push(42);
    return a;
}
function g(h: unit -> unit)
{
    h();
    let a = [];
    a.push(42);
    return a;
}

普通の言語だったら「等価」だろう。a の構築が h の前でも後でも変わらない。

しかし、一部の言語には複数回制御を返す関数がある。例えば、C言語には setjmp という関数があり、これは複数回制御を返すことができる。また、第一級継続があってそれを複数回起動できる言語（例えば、Scheme）でも、関数が複数回制御を返す可能性がある。

LunarMLにも第一級継続があり、JS-CPSバックエンドでは継続を複数回起動できる。使用例は example/monad.sml にある。amb 関数がそれだ。

関数が複数回制御を返す可能性のある言語では、上記の f と g は等価ではない。

上記の例であればコンパイラーの最適化器がコードの意味を変えないように気をつければ良い話だが、関数が複数回制御を返す可能性がある言語ではライブラリーを書く場合にも気をつけないといけない。不変配列を初期化する関数 Vector.tabulate : int * (int -> 'a) -> 'a vector の実装を考えよう。SMLによる疑似コードならこうなるだろう：

fun tabulate (n, f) =
  let val array = Array.unsafeNew n (* 配列を確保する架空の関数 *)
      fun loop i = if i >= n then
                       ()
                   else
                       ( Array.update (array, i, f i)
                       ; loop (i + 1)
                       )
  in loop 0
   ; Array.unsafeFreeze array (* 配列をコピーせずにvectorに変換する架空の関数 *)
  end

JavaScript風に書けばこうなる：

function tabulate(n, f)
{
    let array = [];
    for (let i = 0; i < n; ++i) {
        array[i] = f(i);
    }
    return array;
}

さて、この実装は f が複数回制御を返す状況でも正しく動作するだろうか？否である。tabulate 関数は破壊的代入を行なっているからだ。

f が複数回制御を返す状況でも正しく動作する tabulate 関数を実装するためには、一旦内容を不変リスト 'a list として構築して、それを改めて不変配列 'a vector に変換するという手がある。あるいは、破壊的更新を使う場合でも内容のコピーを行えば大丈夫かもしれない。

いずれにせよ、関数が複数回制御を返す状況では破壊的更新を使った効率の良い実装は封じられる場合がある、ということだ。

実際問題として、LunarMLが提供する第一級継続の主な用途は非同期処理をいい感じに書くことだろう。その場合は、「関数が複数回制御を返す」という能力は必要ない。実際、OCamlのエフェクトはone shotに制限されているというような話をどこかで読んだ。

しかし、せっかくCPS変換で第一級継続を提供するのだから、継続の複数回の起動を使って面白いプログラムを書けるようにするのは悪いことではない気もする。

つまり、普段は「関数が一回しか制御を返さない」ようにしつつ、特別にマークした関数については複数回制御を返すことを許容する。関数について「一回しか制御を返さない」と「複数回制御を返す可能性がある」という区別（色）を与えるということだ。

val f : a -> b (* 通常の関数（せいぜい1回しか制御を返さない） *)
val g : a ->[multi] b (* 複数回制御を返す可能性のある関数 *)

関連する例として、GNU Cでは関数にreturns_twice属性を与えて、「複数回制御を返す可能性がある」ことをコンパイラーに教えることができる。

色に関する多相：コードの共用はできるか

関数に色をつけるということは、高階関数をそれぞれの分用意するということになる。map 関数なら次のようなバリエーションが生まれるだろう：

val map : ('a -> 'b) -> 'a list -> 'b list
val mapAsync : ('a ->[async] 'b) -> 'a list ->[async] 'b list
val mapMulti : ('a ->[multi] 'b) -> 'a list ->[multi] 'b list

これらを統一的に扱うことはできないだろうか？つまり、「色」（エフェクト、と呼んでも良いかもしれないが）に関する多相があれば、次のような関数一個で済ませられるだろう：

val map : ('a ->['color] 'b) -> 'a list ->['color] 'b list (* 'colorは「色」を表す変数 *)

多相の実現方法はいくつかある。この、「色」に関する多相はどのように実現されるべきだろうか？

まず、コードを複製するというやり方がある。ソースに書かれた一つの関数から、コンパイラーが「通常の関数」と「async関数」を生成する。あるいは使用箇所にコードをインライン化する。

関数が大きい場合はコードの複製は避けたいかもしれない。そういう場合に使えるコンパイル方法はあるだろうか？

私の答えを書く前に、Haskellの場合で考えよう。Haskellにも「純粋な関数」と「モナディックな関数」があり、実質的に関数に色がついている。例えば、map 関数には以下のバリエーションが考えられる：

map :: (a -> b) -> [a] -> [b]
mapIO :: (a -> IO b) -> [a] -> IO [b]

しかし、IO に依存しない処理であれば、実際には mapIO の IO の部分を一般のモナド m にすることが多いだろう：

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

この mapM 関数を利用して純粋な map 関数を実装することはできるだろうか？……実は、できる。Identitiy モナドについて適用すれば良い。

map = coerce (mapM :: (a -> Identity b) -> [a] -> Identity [b])

これと同じように、LunarMLの関数の色に関する多相でも、CPS変換した汎用の実装を用意しておいてそれを使って通常の関数版とasync版の両方を用意するという手が考えられる。

まあ、色に関する多相がどの程度欲しくなるかは実際に使ってみないとわからない。もしかしたら、色に関する多相を使いたくなるような関数は、インライン化しても問題ない小さな関数だけかもしれない。例えば、パイプ演算子 |> は色に関して多相になっていると便利な関数の一つだが、積極的にインライン化するべき関数だろう：

val |> : 'a * ('a ->['color] 'b) ->['color] 'b

LunarMLについて最近考えていることを書いてみた。実際に実装するには、文法や細かい戦略を詰める必要がある。あるいは、先にパフォーマンスの計測を行なってCPS変換のコストを見るべきなのかもしれない。

Spread the love