WEKO3
アイテム
PROLOGコンパイラにおける非決定性処理の最適化方式
https://ipsj.ixsq.nii.ac.jp/records/31101
https://ipsj.ixsq.nii.ac.jp/records/31101d761d3c4-ecdc-4e81-b7d4-46ed368548c5
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-PRO87045002.pdf (1.5 MB)
|
Copyright (c) 1988 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1988-03-23 | |||||||
| タイトル | ||||||||
| タイトル | PROLOGコンパイラにおける非決定性処理の最適化方式 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Optimization Method for Non - determinate Predicate of PROLOG | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 大阪大学産業科学研究所 | ||||||||
| 著者所属 | ||||||||
| 大阪大学産業科学研究所 | ||||||||
| 著者所属 | ||||||||
| 大阪大学産業科学研究所 | ||||||||
| 著者所属 | ||||||||
| 大阪大学産業科学研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The Institute of Scientific and Industrial Research Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The Institute of Scientific and Industrial Research Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The Institute of Scientific and Industrial Research Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| The Institute of Scientific and Industrial Research Osaka University | ||||||||
| 著者名 |
松本, 一夫
× 松本, 一夫
|
|||||||
| 著者名(英) |
Kazuo, Matsumoto
× Kazuo, Matsumoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本報告では、PROLOGの非決定性処理を最適化する2つの方式を提案する。PROLOGの非決定性処理は、後戻り処理によって複数の節を試行することにより実現されている。したがって、非決定性処理を最適化するためには節間の関係を利用する必要がある。提案する2方式は、節を単位とする従来の最適化方式と異なり、述語を単位として最適化を行うものである。まず初めに、述語単位での変数分類による述語内ローカル変数の導入と、分類情報を利用して最適化を実現するための処理系アーキテクチャを提案する。この方式は、後戻り処理時の単一化処理を効率化することによって非決定性処理を最適化するものである。次に、カットや組込み述語の特性を利用したプログラム変換によって非決定性処理を最適化する方式を提案する。この方式は、本質的に決定性の述語でありながら、PROLOGの言語仕様上の制約から非決定的に実行されている述語を、インデキシング手法により決定的に実行される形式に変換するものである。変換された述語は、後戻り処理が削除されるため高速な実行が可能になっている。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The main computational mechanisms of PROLOG are "unification" and "backtracking". These mechanisms are usually implemented by use of WAM (Warren's Abstract Machine) architecture. However, optimization methods used in WAM works well only for determinate and backtracking-free predicates. To execute any PROLOG programs efficiently, optimization method for non-determinate predicates should be added on. In this paper, we will, first, present an optimization method for non-determinate predicates consist of a new variable classification method and an new architecture for performing efficient backtracking. This classification method classifies the variables which take the same value in some clauses into "predicate local variables". Unification of these variables in non-deternimate predicates can be removed except for the first time in this architecture. Second, we will discuss an optimization method by using program transformation technique. In this method, a non-determinate predicate is transformed into determinate predicates. With this optimization, a non-determinate predicate can be executed so fast by indexing technique without backtracking. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10485570 | |||||||
| 書誌情報 |
情報処理学会研究報告プログラミング（PRO） 巻 1988, 号 23(1987-PRO-045), p. 1-8, 発行日 1988-03-23 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
