はじめに 通常のプログラムは実行時(ランタイム)に1 + 1など様々な計算を行う。一方でコンパイラーを持つ言語では、コンパイラーの型検査やジェネリクスなどの機構を利用して、コンパイル時にも計算を行うことができる。このようなプログラミングを、コンパイル時に検査・推論される“型”[1]に注目して型レベルプログラミングと呼ばれる。 ランタイムの計算の中にはたとえばwhile(1);のような簡単な計算で無限ループといった停止しない状況に陥いることがある。コンパイル時にできる計算でこのように無限ループに陥いってコンパイルが停止しなくなってしまったら、プログラムを実行することなく自明なエラー(型があってないとか、Rustであればfreeするタイミングが自明でないなど)を検出しようというモチベーションが崩壊してしまう。したがってコンパイル時にできる計算とはランタイムに比べて非常に限定された計算しか許可さ