首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:型代入を遅延する最適化型推論アルゴリズム
  • 本地全文:下载
  • 作者:上野 雄大 ; 大堀 淳
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2008
  • 卷号:25
  • 期号:2
  • 页码:2_101-2_113
  • DOI:10.11309/jssst.25.2_101
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

    多相型型推論は型付き関数型言語のコンパイルステップの中でも最も複雑かつ時間を要する処理の1つであるにもかかわらず,その最適化方式や最適化による効果などはあまり研究されていない.多相型型推論問題の最悪のケースを考慮したアルゴリズム論的な複雑さはDEXPTIME完全であることが示されており,アルゴリズム論的な改善の余地はないが,宣言的でかつ現実の多くのプログラムに対してより効率よく動く型推論アルゴリズムの開発は,多相型プログラミング言語の設計と実装にとって重要な課題である.本稿では,型の代入を型変数が参照されるまで遅延するという考え方に基づく新しい型推論アルゴリズムDWを提案し,その健全性を証明する.DWは,多くの場合型の代入の計算を軽減でき,従来の型推論アルゴリズムWと比較して実用上より効率的であると期待できる.本稿ではさらに,そのアルゴリズムをStandard MLの型言語に対して実装し,ベンチマークテストを通じその実用性を検証するとともに,実用的なコンパイラへ採用する上での課題に関して議論する.

国家哲学社会科学文献中心版权所有