never型があると便利か（言語処理系実装者の観点から）

TypeScriptをはじめとするいくつかのプログラミング言語には、never型という型がある。この型は典型的には「制御を返さない関数」の返り値として使われる：

function f(x: string): never {
    console.error(x);
    throw new Error();
}

never型は型システム的には「値を持たない型」「任意の型の部分型」として特徴づけられる。

他のプログラミング言語、例えば私が作っているLunarMLにもnever型があると便利だろうか？

前提：部分型はゼロコストで変換できて欲しい

これは私の意見だが、部分型から上位型へはゼロコストで変換できて欲しい。例えば Sub <: Super という関係があった時に、Sub 型の値をゼロコストで Super 型へ変換できて欲しいのはもちろん、関数型についても A -> Sub から A -> Super へもゼロコストで変換できて欲しいし、Super -> B から Sub -> B へもゼロコストで変換できて欲しい。

もちろん、「変換関数を挿入する」という形で部分型付けを実装することもあるが、そういう実装方法を許容するのだったら、Haskellで言うところの Functor/fmap のように、部分型の変換だけではなく任意の関数で変換できるようにするべきだ。なので、わざわざ「部分型」という関係を特別扱いするからにはゼロコストで変換できて欲しい（と私は考える）。

呼び出し規約の問題／noreturn属性とnever型の関係

C言語など、一部のプログラミング言語にはnever型はない代わりに、noreturn属性というものがある。C言語のnoreturnについては「C言語のざんねんなしよう事典」で触れた：

さて、noreturn属性と（関数の返り値の型として使った時の）never型は似ている。C言語の「noreturn属性が付いた関数」を「never型を返す関数」として扱うことはできないだろうか？

以下のプログラムを考えよう：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

[[noreturn]]
void goodbye(const char *message)
{
    fprintf(stderr, "Goodbye: %s\n", message);
    exit(1);
}

struct A {
    int x[100];
};

int main(int argc, char *argv[])
{
    if (argc > 1 && strcmp(argv[1], "void") == 0) {
        ((void (*)(const char *))goodbye)("void");
    } else if (argc > 1 && strcmp(argv[1], "int") == 0) {
        ((int (*)(const char *))goodbye)("int");
    } else if (argc > 1 && strcmp(argv[1], "double") == 0) {
        ((double (*)(const char *))goodbye)("double");
    } else if (argc > 1 && strcmp(argv[1], "A") == 0) {
        ((struct A (*)(const char *))goodbye)("A");
    }
}

もしC言語で「noreturn属性のついた関数」を「never型を返す関数」として使えるならば、goodbye 関数を好きな型を返す関数ポインターにキャストしても正常に動作するはずだ。やってみよう。

$ uname -ms
Darwin x86_64
$ clang -Wall -std=c2x test.c
$ ./a.out void
Goodbye: void
$ ./a.out int 
Goodbye: int
$ ./a.out double
Goodbye: double

Intel Macでは void, int, double についてはうまくいった。大きな構造体を返す関数の場合はどうだろうか。

$ ./a.out A
Goodbye: ?b???

なんじゃこりゃ？？？？？？？？！？！！？？

Goodbye: A と表示されて欲しかったが、ゴミが表示された。あたかも、初期化されていないメモリ領域を読んだかのようだ。表示内容は実行ごとに変わる。

実は、Intel Mac上のC言語が使っている呼び出し規約では、返り値の型によって（返り値の受け渡し方だけではなく）引数の渡し方も変化するのだ。つまり、大きな構造体を返すときは暗黙の第一引数として結果を格納するべきメモリ領域のアドレスが渡される。Macを持っていない人はLinuxとかで試してみよう。

（Apple Silicon Macでは同じプログラムを実行しても Goodbye: A が出力される。AArch64の呼び出し規約では「結果を格納するべきメモリ領域」のアドレスは引数とは別のレジスター（r8）で渡されるからだ。）

ということで、C言語では「noreturn属性が付いた関数」の返り値の型を別の型にキャストするとうまく動かなくなる場合があることがわかった。一方で、「never型を返す関数」はゼロコストで「Aを返す関数」に変換できて欲しい。よって、C言語の標準的な呼び出し規約では一般にはnever型は実現できないことが言える。（もちろん、ゼロコストで変換できて欲しい、という前提の下でではあるが。）

ちなみに、Haskellにはrepresentation polymorphismというのがあり、制御を返さない関数を「どんな型でも返せる関数」として実装できるが、あれはHaskellが独自の呼び出し規約を使っているからこそ実現できる、ということになる。

f :: forall rep (a :: TYPE rep). String -> a -- 返り値の型 a はどんな実行時表現でも大丈夫

f "Int" :: Int -- Int を返すと解釈できる（解釈のためのコストはゼロ）
f "Int#" :: Int# -- Int# を返すと解釈できる
f "Int4" :: (# Int#, Int#, Int#, Int# #) -- unbox化されたタプルを返すと解釈できる

直和型とnever型の組み合わせ／多相的なデータ型の実現方法との兼ね合い

直和型は便利だ。「現代的なプログラミング言語」の条件には直和型を備えていることを盛り込むべきだ。

型パラメーターを持つ直和型にnever型を突っ込むと、一部のデータ構築子が現れないことを表現できる。例えば、失敗しうる計算の結果を表す型

(* 疑似コード *)
datatype result['a, 'b] = OK of 'a | ERROR of 'b

を result[int, never] と適用すると「常に成功する」ことを表現できるし、 result[never, exn] と適用すると「常に失敗する」ことを表現できる。

あるいは、ML系言語での以下のコードを考えよう。

datatype option['a] = NONE | SOME of 'a
val xs = List.map (fn x => (x, NONE)) [2,3,5];

この xs にはどういう型がつくべきだろうか？純粋関数型言語なら xs : forall 'a. int * option['a] という風に多相的な型がつくかもしれない。しかし、Standard MLなんかではvalue restrictionというのがあって、 'a は多相的にはなれない。

ここでnever型があれば、xs に int * option[never] という型をつけられて便利ではないだろうか。

さて、例によって option[never] 型からは任意の option['a] 型にゼロコストで変換できて欲しい。result[int, never] からは任意の result[int, 'b] に変換できてほしい。never型を部分型によって規定したのだから当然だ。

素朴には、これは難しい要求ではないように思える。option[never] 型の値としてあり得るのは NONE だけだし、result[int, never] 型の値としてあり得るのは OK x だけだからだ。

しかし、多相型の実装の際に特殊化を行なっていたらどうなるだろうか。実現方法はRustやMLtonのようなコンパイル時にコードを複製する方法かもしれないし、実行時に型情報を受け渡すやり方かもしれない。

多相型の実装時に特殊化を行う場合、option[never] は「取りうる値が1つしかない」ということで、unit型と等価の表現（0ビット表現）を使うかもしれない。result[int, never] はタグ情報を省いて、int と同じ表現を使うかもしれない。すると、「never型を含む型からゼロコストで変換できて欲しい」という願望はどうなるだろうか？

そう、result[int, never] から result[int, string] への変換は「int を直和型 result[int, string] に詰め直す」という形になり、ゼロコストではなくなる。

なので、言語に安易に「ゼロコストで変換できるnever型」を導入してしまうと、多相型の実現方法に制約がかかってしまうのだ。もちろん、人によってはこれは大した制約ではないと思うかもしれない。option[never] や result[int, never] に対して常にタグ付きの表現を使うようにすればいいからだ。しかし、これは option 型の表現を設計するときに効いてくる話なので、「中身がnullになりえない option 型をnullableで実現する」表現方法を採用できるかにも関わってくるだろう（まあ、NONE を常にnullで表現すれば良いだけの話かもしれないが）。

今の所の考え

「LunarMLにnever型があったら便利なのでは」と思って考えたものの、やっぱり慎重になったほうが良いだろうというのが今の所の結論だ。もちろん、never型を入れるということは言語に部分型付けを入れるということで、「部分型付けがあるのに型推論は大丈夫なのか」という問題も発生する（とはいえ、こっちはそんなに大きな問題とは考えていない）。

Spread the love