継続の話

継続とは、計算途中における「次の計算」を示す手続きのことです。
Schemeでは継続は第一級オブジェクトであり、
call-with-current-continuation手続きで
継続復帰手続きをいつでも取得することができます。

継続はチューリング機械の時代から常に計算と共に存在していました。*1

継続はトリッキーですが、非常にシンプルな概念です。
CPS変換されたプログラムにおいて、
継続復帰手続きは呼び出す継続が変更されるだけのことであり、
SECDマシンでは継続復帰手続きはDumpレジスタの保存と表すことができます。

以下に示す例は継続の利用例です。

  • 非決定計算
  • コルーチン
  • 大域脱出
  • 例外処理
  • ジェネレーター

本題

完全な継続をサポートするべきかどうかという話が出てきます。
問題となる事は一点、現在の主要な計算環境が
継続復帰手続きの生成が不得手であるということです。

スタックベースの関数呼び出しに最適化されているため、
完全な継続復帰手続きとは、「コールスタック領域の保存」になります。
コルーチン、ジェネレータレベルの利用であれば、
スレッドごとスタックを分離して処理すればよいので
「スレッドの凍結」で代用が効きます。

cal/ccは便利な反面、複数の計算スレッドを用意できる現在のハードウェアでは、
完全な継続のサポートは保留したほうが無難ではないかという気持ちです。

*1:チューリング機械でいうところの継続は、ある計算状況における次の状態遷移関数で、継続復帰手続きは任意の状態から捕捉した継続を呼び出せるよう機械の状態とテープの内容を復元するマクロオペレータと解釈できます