JPS63118941A - デ−タ処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明）よ主に人工知能分野へ使用することを目的とし
たデータ処理装置に関するものである。

従来の技術 近年、コンピュータ応用の一つとして人工知能分野が盛
んに研究されている。この分野においては構造を持った
データを処理する必要があり、そのため構造データを取
り扱うことのできる言語であるＬＩＳＰが広く使用され
ている。ＬＩｓＰ言語は汎用のコンピュータで実行する
のは非効率であるため、様々な工夫を施した専用マシン
が開発されてきた（例えば、ｒＩｌｓＰマシン」情報処
理　ｖｏｌ、２３　Ｎｏ、８　　ｐｐ７５２　７７２）
−これら専用マシンは主に言語的側面からアプローチを
行って改善を図ったものであるが、構造体データである
リストの計算機内部における表現を、通常のポインタに
よる表現ではなく、表形式を用いるようにした研究も行
われている（例えば、「構造をもったデータの高速マツ
チング方式」情報処理学会第３３口金国大会　７Ｏ−２
）。

以下図面を参照しながら、上述したリストの表形式表現
を用いた従来のデータ処理装置について説明する０表形
式表現では、リストの葉のノード位置を表現する方法と
してＣＤＲ方向に順次番号を付け、ＣＡＲ方向に順次項
目を割り当てた一次元ベクトル表現を採用することによ
り、葉の位置情報と葉自身の情報を順次並べた表で、リ
ストデータを表現する。すなわち、リストデータは葉の
位置情報を示すベクトルと葉自身の情報を組としたデー
タの集合で表現される。

第３図にリストデータの表現例を示す、これは８式で表
記した場合（Ａ　（Ｂ　（Ｃ）　＞　Ｄ）となるリスト
データの図式表現＋ａ＋、及び、表形式表現（１））を
示したものである０図式表現Ｔａｌにおいて丸印は葉で
ないリストノードを表し、四角で囲ったものは葉のノー
ドを示している。また各ノードの上に付記した数字列は
、上記した方法にしたがって表したノード位置を示すも
のである。この葉の部分を抜きだして表の形で表現した
ものが表形式データ）であって、アドレス部にノード位
置ベクトルが、バリュ一部に葉の要素が入った表で構成
されている。

リストをこのような表形式で表現すると、当然のことに
その演算方式は通常のポインタ表現の場合と異なるもの
になり、このような表形式データを処理する従来のデー
タ処理装置は以下に示すような表操作を必要とする。

第４図にＬＩＳＰの基本リスト操作関数における表操作
の一例を示す。

第４図で明かなように、ＣＡＲ関数はアドレス部の先頭
が１の要素を抜き出し、２番目以下のアドレスを先頭方
向にシフトすることにより　（これを以下ＣＡＲシフト
と呼ぶ）実行することができる。ＣＤＲ関数はＣＡＲ関
数とは逆に先頭アドレスが１の要素を取り除き、残った
要素の先頭アドレスから１を減じることにより　（以下
これをＣＤＲシフトと呼ぶ）実行される。

Ｃ０Ｎ５関数についてはもう少し複雑である。

まｆｃＯＮｓ関数の第一引数について、アドレス部を先
頭方向とは逆の方向にシフトし、先頭アドレスを１とす
る。これは前記したＣＡＲシフトとは逆の演算であり、
以下ＲＣＡＲシフトと呼ぶ。

第二引数については先頭アドレスに１を加算する（以下
これをＲＣＡＲと同じ理由でＲＣＤＲシフトと呼ぶ）。

次にこの二つの引数を一つの表としてまとめればＣ０Ｎ
５関数は実行される。

発明が解決しようとする問題点 しかしながら、ポインタ表現では極めて容易に行えるＣ
ＡＲ，ＣＤＲ，Ｃ０Ｎ５といったＬＩＳＰの基本関数が
、表形式表現では全ての要素に対してシフト演算を必要
とするため、表形式表現に基づいた従来のデータ処理装
置は非効率的であるという問題点を有していた。

本発明は上記問題点に鑑みてなされたもので、筒車な構
成で効率良く表形式のリストデータを処理することので
きるデータ処理装置を提供するものである。

問題点を解決するための手段 上記問題点を解決するために本発明のデータ処理装置は
、リストデータのアドレス部のシフト操作を行うシフト
装置を備え、上記シフト装置はリストデータを格納する
レジスタ装置内のデータばかりでなく、上記レジスタ装
置へ転送されるリストデータについてもシフト操作を行
うことができるようにしたものである。

作用 本発明は上記した構成により、表形式のリストデータを
レジスタ装置に転送すると同時にそのアドレス部をシフ
トすることができるので、不要な転送を実行する必要が
なくなり、効率的にリストデータを処理することが可能
となる。

実施例 以下本発明の一実施例について、図面を参照しながら説
明する。第１図は本発明の一実施例におけるデータ処理
装置の構成を示すブロック図である。第１図において、
１０はリストデータを表形式で記憶するメモリ装置、１
１はメモリ装置１０またはレジスタ装置１２の出力を、
入力選択信号とシフト制御信号に基づいてシフトするシ
フト装置、１２は表形式のリストデータの要素を格納す
るレジスタ装置である。

以上のように構成された本実施例のデータ処理装置につ
いて、以下その動作を説明する。シフト装置１１は、第
２図にしたがって入力の選択、シフトの種類の決定、シ
フトの実行を行う。すなわち、まずステップ２０で入力
選択信号を参照し、メモリ装置１０またはレジスタ装置
１２のいずれかの出力を入力する（ステップ２１、ステ
ップ２２）０次に、入力したリストデータのアドレス部
をステップ２３で切り出し、シフト制御信号に基づいて
シフトの種類を決定する（ステップ２４）。シフトの種
類としては、前記したＣＡＲシフト、ＣＤＲシフト、Ｒ
ＣＡＲシフト、ＲＣＤＲシフト、及びシフトなしの５種
類があり、ステップ２４で決定したシフト動作の実行を
ステップ２５で行う、そして、最後にシフト後のアドレ
ス部と元のバリュ一部を一つにまとめて出力する（ステ
ップ２６）。

なお、本実施例ではシフトの種類として上述した５種類
を用いたが、この５種類に限定されるものではない６例
えば、ＣＡＲシフト、ＣＤＲシフト、ＲＣＡＲシフト、
ＲＣＤＲシフトをそれぞれ複数回実行するＮＣＡＲシフ
ト、ＮＣＤＲシフト、ＲＮＣＡＲシフト、ＲＮＣＤＲシ
フトを行えるようにしてもよい。さらに、以上のシフト
の組合せを実行できるようにしてもよい。

発明の効果 以上の説明から明らかなように、本発明はりストデータ
を、ノードの位置を示すアドレス部とデータ値へのリフ
ァレンスを示すバリュ一部とで構成した表形式のデータ
として記憶するメモリ装置と、上記表形式データの要素
を記憶するレジスタ装置と、上記レジスタ装置の入力に
接続され、上記メモリ装置や上記レジスタ装置から出力
されたりストデータのアドレス部のシフト操作を行うシ
フト装置を具備し、上記シフト装置は上記レジスタ装置
内のリストデータのシフト操作を行うと共に、上記メモ
リ装置から上記レジスタ装置ヘリストデータを転送する
際にもシフト操作を行うことができるようにしたので、
リストデータのアドレス部に対するシフトを効率的に実
行することが可能となり、リストデータを高速に処理で
きるという優れた効果が得られる。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータ処理装置の構
成を示すブロック図、第２図は本発明の一実施例におけ
るシフト装置の処理の流れを示すフローチャート、第３
図はリストデータの表形式表現の一例を示す図、第４図
はＬ■ＳＰの基本リスト操作関数に対応する裏操作を説
明するための説明図である。 １０・・・・・・メモリ装置、１１・・・・・・シフト
装置、１２・・・・・・レジスタ装置。 代理人の氏名　弁理士　中尾敏男　はか１名第１図 第２図 第３図 （Ａ　（Ｆ３（こ））Ｄ）

Claims (1)

【特許請求の範囲】
1. リストデータを、ノードの位置を示すアドレス部とデー
   タ値へのリファレンスを示すバリュー部とで構成した表
   形式のデータとして記憶するメモリ装置と、上記表形式
   データの要素を記憶するレジスタ装置と、上記レジスタ
   装置の入力に接続され、上記メモリ装置や上記レジスタ
   装置から出力されたリストデータのアドレス部のシフト
   操作を行うシフト装置を具備し、上記シフト装置は上記
   レジスタ装置内のリストデータのシフト操作を行うと共
   に、上記メモリ装置から上記レジスタ装置へリストデー
   タを転送する際にもシフト操作を行うことができるよう
   にしたことを特徴とするデータ処理装置。