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という言語処理系で関数色付け問題をどう扱うかを検討する。

続きを読む →