Glasgow Haskell Compilerにおける再帰的データ構造のための遅延オブジェクトの再利用

情報処理学会 Web Site

書誌事項

タイトル別名
  • Glasgow Haskell Compiler ニ オケル サイキテキ データ コウゾウ ノ タメ ノ チエン オブジェクト ノ サイリヨウ
  • Reusing Thunks for Recursive Data Structures in Glasgow Haskell Compiler

この論文をさがす

抄録

遅延評価は，プログラムの簡潔な記述を可能にするため，純関数型言語などで採用されている．特にリストなどの再帰的データ構造を扱う際には，必要に応じて評価を進めることが可能となり，遅延評価により得られる記述性の向上は大きい．一方，計算を遅延するために必要なオブジェクト（遅延オブジェクト）の生成は，プログラム実行時のオーバヘッドとなってしまうため，効率の良い遅延評価機構を実装するには，遅延オブジェクトの削減が必要である．本論文は，リストのような線形に再帰的に定義される代数データ構造に注目し，必要となる遅延オブジェクトを再利用する手法を提案する．提案手法は，すでに割り当てられている遅延オブジェクトの保持している値を更新して再利用する．このような再利用を可能とするために，提案手法は，コンパイル時にプログラム変換を行い，再利用対象とする遅延オブジェクトへの参照を単一にする．提案手法を，純関数型言語Haskellの処理系であるGlasgow Haskell Compiler上に実装し，実験を行った．その結果，オーバヘッドはあるものの，総メモリ割当て量を削減できることが分かった．

Lazy evaluation helps programmers write clear programs. However, it has significant run-time overheads for building many as-yet unevaluated expressions, or thunks. Because thunk allocation is a space-consuming task, it is important to reduce the number of thunks in order to improve the performance of a lazy functional program. We propose static analysis algorithms that achieve the thunk reuse technique. Thunk generation is suppressed by reusing an already allocated thunk at the tail of a list, on the condition that the thunk is singly referred, i.e., pointed to only from the tail field of a cons cell. This method guarantees that reused thunks definitely satisfy this singly referred condition on the basis of a static analysis with program transformations. We have implemented our method in the Glasgow Haskell Compiler and measured total memory allocations and execution times for some programs.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ