不定元を含むストリーム計算の実現

概要

論文の詳細を見る
計算機で実数計算を行うとき,グレイコードによる実数表現を用いれば,実数を一意に表すことができ,実数上の標準的な計算可能概念を導出できる.グレイコードとは,一般の2進表現とは異なる{0,1}の無限列としての実数表現であり,その列の中に無限列をたかだが1つ含むものである.このグレイコードによる実数表現を扱う計算を不定元を含むストリーム演算として関数型言語で実装することを考える.グレイコードに含まれる不定元はふつうの文字と同じように評価するとその評価を終了できないため,その部分の評価を行わずに計算を進めていく必要がある.これは,決定不能な部分の評価を非決定的に避けるMcCarthyのambという演算子を用いれば実現できる.しかし,この演算子を実現するには並列処理の機構が必要である.ところが,グレイコードを用いた実数計算を行う関数に含まれるamb演算子には,その2つの引数を表すグラフが必ず部分グラフを共有しているという特徴がある.そして,この特徴を用いれば並列処理を行うことなく,実数計算に必要な部分に関してambと同じ動作をする演算子gambを関数型言語に追加することができる.さらに,この演算子の評価は,グラフの書き換え規則の適用と共有されている部分の評価を繰り返し行うだけでよい.本発表では,不定元を含むストリーム演算を実現する際に,gamb演算子をどのように関数型言語に追加するかについて述べ,この演算子が正しく動作することについての説明を行う.
一般社団法人情報処理学会の論文
2004-11-15

不定元を含むストリーム計算の実現

スポンサーリンク

概要

著者

関連論文

スポンサーリンク