JPS63208126A - リスト処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は２進木リスト処理装置に係り、特にリストで表
されるデータを効率良くアクセスできるリスト処理装置
に関する。

〔従来の技術〕

近年、計算機による知識処理が盛んになってきている。

知識などのデータは記号のまま扱うことが望ましく、記
号処理向き言語ＬＩＳＰが普及し始めている。ＬＩＳＰ
はデータやプログラムを２進木リストで表すことを特徴
としている。

第２図（ａ）に２進本リストの例を示す。計算機上では
このようなリストを左ポインタ　（ＣＡＲと呼ばれる）
及び右ポインタ（ＣＤＲと呼ばれる）から成るセルを使
って表している（第２図（ｂ）参照）。ここでＡ、Ｂ、
Ｃはアトムと呼ばれるデータである。また、ｎｉＱはリ
ストの終端を表す。

ＬＩＳＰにおいては、このようなセルのＣＡＲ部やＣＤ
Ｒ部をたどることによってデータにアクセスすることが
基本的な処理になる。

ところで、ＣＡＲ部、ＣＤＲ部はポインタ、すなわちア
ドレスであり、そのデータ長は計算機の基本語長とほぼ
等しい。従って、１つのセルは２語以上で表されるのが
一般的である。

リストを高速にアクセスするために、特開昭５ｇ−３０
５１号公報に記載のように、ＣＡＲ部またはＣＤＲ部に
アクセスした場合、他方も連続してアクセスを行うこと
が考えられた。これによりリストをたどる際に次に必要
となるデータを自動的に得られるようになった・ 〔発明が解決しようとする問題点〕 しかし、上記従来技術では１つのセルの読み込みのため
に主記憶装置には２回の読み出し命令が発せられていた
。また、セルの書き込みに関しては高速化は考慮されて
いなかった。

本発明の目的はリストアクセスを上記従来技術よりも効
率化し、またセルの書き込みに関しても効率化を図るこ
とにある。

〔問題点を解決するための手段〕

上記目的は、リスト処理装置内にＣＡＲ部ＣＤＲ部を同
時に保持する手段を設け、セルのＣＡＲ部またはＣＤＲ
部を読み込む際に、該セル全体を読み出し、該保持手段
に格納し、また、セルを新たに設けた時にはＣＡＲ部及
びＣＤＲ部にデータを書き込まなければならないが、そ
の際には、該保持手段に格納しであるデータを一度に書
き出すことで達成される。

〔作用〕

ＣＡＲ部ＣＤＲ部保持手段は制御部からの指令によって
主記憶装置から読み出されたセルの内容を保持している
ので、次にリストをたどる際に必要となるデータが得ら
れたことになる。また、セルにデータを書き込む際には
、保持手段の内容を制御部からの指令によって一度に主
記憶装置に書き出すことにより１回の書き込み動作でセ
ルへの書き込みが完了したことになる。

〔実施例〕

以下、本発明の一実施例を第１図〜第５図により説明す
る。

第１図は、本発明の一実施例を示すリスト処理装置の構
成を示すブロック図である。該処理装置１０はＣＡＲ部
ＣＤＲ部保持手段（ＣＣＲ）　１０１　。

ＣＣＲＩＯｌを含む複数のレジスタから成るレジスタフ
ァイル（ＲＦ）１０２．演算部（ＡＬＵ）１０３．メモ
リアドレスレジスタ（ＭＡＲ）１０４．　　リードデー
タレジスタ（ＲＤＲ）１０５．ライトデータレジスタ（
ＷＤＲ）　１０６　、制御部（ＣＴＲ）１０７．　ＣＴ
Ｒ１０７から主記憶装置（ＭＭ）１１への制御信号線１
０８．及びバス１０９，１１０を主な構成要素とする。

ＣＣＲＩＯＩはＭＭＩＩから読み出したセルの内容を格
納する。ＲＦ１０２に格納されたデータはバス１０９を
通してＡＬＵ１０３で処理されるか、またはバス１１０
を通しテＭＡＲ１０４やＷＤＲ１０６ニセツトされる。

ＭＡＲ１０４にセットされたデータはメモリアクセスの
ためのアドレスとしてＭＭＩＩに送出される。ＭＭＩＩ
から読み出されたデータはＲＤＲ１０５にセル１へされ
、その後バス１０９に送出される。

ｗｄｒ１０６にセットされたデータは書き込みデータと
してＭＭＩＩに送出される。ＣＴＲ１０７は処理装置１
０全体を制御する。ＭＭＩＩへのアクセスに関してはＭ
ＡＲ，１０４の内容をアドレスとして送出するとともに
制御信号線１０８を通して読み出し書き込みの選択、デ
ータ長の指定等の制御情報を送出する。ＭＭＩＩは該制
御情報に従い、ＭＡＲ１０４で指定されたアドレスのデ
ータを、読み出しの場合はＲＤＲ１０５にセットし、書
き込みの場合はＩｄＤＲ１０６の内容をＭＭＩＩ内に保
持する。

本実施例では、処理装置１０の基本語長を４バイトとす
る。第３図は本実施例におけるセルの例である。ＣＡＲ
部、ＣＤＲ部をそれぞれ４バイトで表し、１つのセルは
ＭＭＩＩ上の連続した９バイトの領域に格納される。第
４図は第２図のリストを本実施例におけるセルの形式で
表した例である。ＣＤＲ部は次のセルの先頭のアドレス
を保持している。ＣＡＲ部はアトム領域を指している。

次に、本発明の具体例を実施例により説明する。

ＲＦ１０２内のレジスタが第４図のリストの先頭すなわ
ち（１０００）ｚｅ番地を保持していたとする。次に該
レジスタの指すセルのＣＡＲ部すなわち（１００４）１
８番地の内容を読み込む処理を行う。ＣＴＲ１０７は該
レジスタの内容をバス１１０を通してＭＡＲ１０４にセ
ットするとともに制御信号線１０８によって読み出し処
理を行うことと読み出すデータの長さはセルの大きさ、
すなわち８バイトであることをＭ　Ｍ　ｌ　１に送出す
る。ＭＭＩＩはＭＡＲ１０４で示されたアドレスの内容
を読み出しＲＤＲ１０５にセットする。ＲＤＲ１０５に
セットされたデータはバス１０９を通してＣＣＲＩＯＩ
に格納される。これによりＣＣＲ１０１には（１０００
）１ｅのセルのＣＡＲ部及びＣＤＲ部が読み込まれたこ
とになる。読み込んだＣＡＲ部により処理が続行される
。

次に同じセルのＣＤＲ部を読み込もうとする際には、既
にＣＣＲＩＯＩのＣＲＤ部に該セルのＣＤＲ部は読み込
まれているので新たにＭＭＩＩから読み出しを行う必要
はない。

セルの書き込み処理について示す。新しいセルの生成は
、セルのための領域を確保し、確保した領域のＣＡＲ部
及びＣＤＲ部にデータを書き込むことによってなされる
。第４図のリストの先頭に新しいアトムを挿入する処理
を第５図に従って示す。新しいセルの領域が（２０００
）１ｅ番地から８バイト確保されたとする。次に０ＣＲ
ＩＯＩのＣＡＲ部に新しいアトムへのポインタ、ＣＤＲ
部に第４図のリストの先頭へのポインタすなわち（１０
００）１ｅ番地を格納する。次にＣＣＲ１０１は新しい
セルのアドレス（２０ｏＯ）１ｅヲＭＡＲ１０４ニセッ
トスルトトモニＣＣＲ１０１の内容をバス１１０を通し
てＩｄＤＲ１０６ににセットする。ＣＴＲ１０７は制御
信号線１０８によって書き込み処理を行うことと書き込
むデータの長さはセルの大きさ、すなわち８バイトであ
ることをＭＭＩＩに送出する。ＭＭＩＩはＭＡＲ１０４
で示されたアドレスに１ｄＤＲ１０５の内容を書き込む
。これによりＣＣＲＩＯＩの内容がＭＭＩＩに書き込ま
れることになる。

以上の具体例により、ＣＣＲＩＯＩを使ってセルの読み
出し、書き込みが１回の操作で実行できることがわかる
。

〔発明の効果〕

本発明によれば、従来２回読み出し、書き込みの操作を
しなければならなかったセルのアクセスを１回の操作で
行うことができるのでリスト処理が効率良く行える。

【図面の簡単な説明】

第１図は本発明の一実施例を示すリスト処理装置の内部
構成のブロック図、第２図は本発明で用いられるリスト
の説明図、第３図は本発明の一実施例で用いられるリス
トセルの例を示す説明図、第４図及び第５図は本発明の
一実施例で用いられるリストの例を示す説明図である。 １１・・主記憶装置、１０１・・・ＣＡＲ部ＣＤＲ部し
第　／Ｉ！！ ＄　２　図 （ｂ） Ａ　　　　　　　８　　　　　　０ ←クバイトーー十 茎　タ　図 メ　５　図

Claims (1)

【特許請求の範囲】
1. １、主記憶装置上で２進木リストを構成するＣＡＲ部、
   ＣＤＲ部の２つのポインタから成るセルを該主記憶装置
   から読み込みまたは書き込みながら処理を進めていくリ
   スト処理装置であつて、該セルの大きさが該処理装置の
   基本語長よりも大きい場合、ＣＡＲ部及びＣＤＲ部を一
   度に保持できる手段を備え、該セルのＣＡＲ部またはＣ
   ＤＲ部を該主記憶装置から読み込む際に該処理装置の制
   御部からの制御信号により他方のポインタも同時に読み
   込み、該保持手段に格納することを特徴とするリスト処
   理装置。