PLに起因する(未解決の)複雑さの問題のリスト

プログラミング言語、特にプログラムの解析とコンパイルから生じる主要な、オープンな計算上の複雑さの問題は何ですか?私は、「ヒンドレーミルナー型推論の時間的複雑さ」や「0CFAの時間的複雑性」の問題点を探しています(どちらも解決されていますが)。

ベストアンサー

1996年のPippenger(1)は、(いくつかの仮定の下で)厳密な(CBV)関数型プログラミング言語は命令型言語よりも漸進的に遅いことを示しています。
(2)で指摘したように、Pippengerの結果が怠け者の関数型言語に一般化できるかどうかは問いません。

ピッペンジャーは、2つの単純化する仮定(オンライン計算と入力のある原子性)を課す。それは開いているかどうか
削除することができます。 Pippengerはそれができると推測しますが、
“結果は[…]計算の複雑さの理論で現在利用可能な方法の範囲をはるかに超えているようです”

(3)のCampbellの答えとBen-Amramの注釈(4)も参照してください。


 1. N. Pippenger、 Pure vs. Impure Lisp

 2. R. Bird、G. Jones、O. De Moor、 もっと早く、スピードが遅い:遅延
    熱心な評価

 3.スタックオーバーフロー、
純粋に関数型プログラミングの効率

 4. A. M. Ben-Amram、 PippengerのPure and Impure
LISPの比較に関する注記

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です