JPS6367691B2

JPS6367691B2 -

Info

Publication number: JPS6367691B2
Application number: JP56104020A
Authority: JP
Inventors: Akira Hatsutori; Hiroshi Hayashi; Akio Shinagawa; Takeshi Shinoki
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1981-07-03
Filing date: 1981-07-03
Publication date: 1988-12-27
Also published as: JPS585853A

Description

【発明の詳細な説明】本発明は、数値ではなく記号を処理するリスプ
（LispすなわちList Processor）のような関数型
言語用の関数型情報処理装置に係り、とくに、関
数が実行される環境（変数の値として何をつかう
かということ）をコンピユータ内部の記憶回路に
スタツク構造的に格納するにあたつて、そのスタ
ツクに格納された変数の検索時間を短縮するため
に上記スタツクメモリの外部に連想バツフアとカ
ウンタを設けることを特徴とする関数型情報処理
装置に関する。

リスプは第１図に示すような２進木リストすな
わち記号のつながりを閉路を含まない節点と枝の
集合である木構造（第１図ａ）であらわしたもの
を扱うものである。すなわち、第１図ａのような
木構造であらわされる記号のつながりを第１図ｂ
のように各ノードからでる枝が２本づつである２
進木表現に直した形で第１図ｃに示されるような
主記憶装置に格納する。すなわち、各リストセル
は主記憶装置の１語または２語からなりその各セ
ルは左、右２つの部分からなる。各セルの左の部
分は普通はある記号、たとえばＡという文字の記
号のビツトパターンが格納され、右の部分はその
記号とつながるべき、次の記号を格納しているセ
ルの番地を格納することによつて２つセルが連結
していることを表現する。従つて、第１図ｃのリ
ストセルのつながりは、第１図ｂの２進木リスト
を記憶回路上で実現しているものである。リスプ
は、このようなリスト構造をリプス言語を実行す
ることによつて、プロセツサを使つて動的に変換
し、目的のリスト構造を得る装置である。

リスプにおいてプログラムするということは、
２進木リストを変換するために必要な以下の５つ
の基本関数を組み合せて形成される関数を定義
し、その値を求めることである。

５つの基本関数とは、 (イ) car〔Ｘ〕カール２進木リストＸの左の枝の先にある２進木リ
ストを値とする。

(ロ) cdr〔Ｘ〕クダー２進木リストＸの右の枝の先にある２進木リ
ストを値とする。

(ハ) cons〔Ｘ：Ｙ〕コンス新しいリスト・セルを設け、その左の枝を２
進木リストＸとし右の枝を２進木リストＹとす
るような新たな２進木リストを作つてそれを値
とする。

(ニ) atom〔Ｘ〕アトムＸがアトムの時、真という値（“Ｔ”や“＊
Ｔ＊”で示す）を取り、そうでないとき、偽
（“NIL”というアトムで示す）とする。

(ホ) eq〔Ｘ：Ｙ〕イクＸとＹが同じ２進木リストの時、真の値
（“Ｔ”や“＊Ｔ＊”）を取り、そうでない時、
偽の値（“NIL”）を取る。

例えば、ｆ（ｘ、ｙ）＝x^y＋y^xの定義はｆ＝λ
〔〔Ｘ、Ｙ〕；X^Y＋Y^X〕と表わすことにより、ｆ
（２、３）の値は、λ〔〔Ｘ、Ｙ〕；X^Y＋Y^X〕〔２、
３〕＝2³＋3²となり、変数の対応関係を明確に規
定することができる。

ここで、（Ｘ、Ｙ）は仮引数と呼ばれる変数で
あつて（２、３）は（Ｘ、Ｙ）のそのときの値で
ある実引数と呼ばれるものである。そして、この
実引数（２、３）を仮引数（Ｘ、Ｙ）に代入する
ことを束縛（binding）すると呼び、実引数を仮
引数に束縛することによつて関数の値、この場合
2³＋3²という目的のリストをつくることがリスプ
を実行することである。したがつて、リスプすな
わち関数型情報処理装置にあつては、仮引数と実
引数をどのように束縛するかが問題となる。

本発明においては、変数の束縛値（Bind
Value）が線形リスト（環境リスト）すなわち
FILO（First In Last OutまたはPush down Pop
up）型スタツクへ変数名と値の対で格納される。
ここでFILO型スタツクとは前記記憶回路上で２
進木リスト構造でデータを間接アドレス方式（す
なわち、あるセルに次につながるセルのアドレス
を格納しておく方式）で格納していくことであ
る。この変数名と値との対を格納していく順序
は、引数変数の関数が呼ばれたときに実引数を値
とする順番になる、いわゆるダイナミツクスコー
ピング（Dynamic Scoping）型の環境をもつ関
数型言語であつて、その変数の値がなにであるか
を参照する手順は、基本的には上記環境リスト
（又はスタツク）を先頭からシーケンシヤルに検
索して最初に見つかつた値を使う、いわゆるデイ
ープバインド（Deep Bind）型変数束縛を行な
う場合に、大域変数（関数の引数等のように、関
数を起動するときに束縛値が決定されている局所
変数とは異なり、それ以前からその値が決められ
ている変数）を捜し出すアクセスタイムを短縮す
るために主記憶装置の他に連想バツフアおよび関
数のコール時およびリターン時にそれぞれ＋１、
−１されるカウンタを設けることが本発明の特徴
である。

一般に、第２図に示すように関数型とは、その
プログラム構造や実行形態が呼ぶべき関数すなわ
ち実行するべき関数ｆ＝λ〔〔Ｘ、Ｙ〕；X^Y＋Y^X〕
の仮引数（Ｘ、Ｙ）へ実引数（２、３）を結合す
なわち束縛（バインド）し、呼ばれた（起動され
た）関数は、渡されたすなわち代入された実引数
や大域変数を参照して所定の手続きを実行し、そ
の関数の値2³＋3²を呼び側へ返し、それ以外の副
作用（環境を変更すること）はないものを言う。
副作用については、本発明の要旨からみて、説明
を省略する。

関数を呼び出す（call）場合、その仮引数への
実引数の束縛の方法には、デイープバインド法と
シヤローバインド（Shallow Bind）法がある。

デイープバインド法は前述したように、束縛さ
れた変数名（Ｘ、Ｙ）と値（２、３）の対（ペ
ア、すなわち、Ｘは２、Ｙは３の対）を線型リス
トとしてのスタツク構造に格納し、変数値を参照
する場合には、最後に束縛された方向からシーケ
ンシヤルにたどり、最初に発見したその変数の値
を使うという環境の構成である。

すなわち、デイープバインド法は、第３図ａに
示すように、主記憶装置の記憶単位である語の構
成が左、右２つの部分に分かれ、１つのセルにな
つていて、左部に変数名を格納し、右部はそのセ
ルが接続する次のセルのアドレスを格納すること
によつて次のセルのその変数の値を知ることがで
き、沢山の変数がある場合は、第３図ａのように
連結し、等価的に第３図ｂのようなFILO型のス
タツクを構成するものである。

関数コール（call）の時に、引数変数に値をバ
インドするときには、環境リスト（または環境ス
タツク）の検索出発点の方向から、その名前と値
の対をつなげ、検索出発点ポインタを新たに付加
した項目の先頭へ更新する。すなわち、第３図ａ
の主記憶装置上では、先頭に１つのセルｎ＋１を
設けることに対応し、そのセルがつながる次のセ
ルがｎであることに対応する。これは、第３図ｂ
においては、スタツクのプツシユ（push）動作
Ａに対応し、その変数名がｎ＋１であつて、その
値が（ｎ＋１）であるセルをスタツクの最下段に
プツシユして入れることに対応する。関数のリタ
ーン（Return）時には、その関数がコールされ
たときの状態に検索出発点ポインタを戻す。すな
わち、第３図ａの主記憶回路上では、先頭のセル
ｎ＋１を１つとつて、セルｎを先頭にすることに
対応し、第３図ｂでは、ｎ＋１とその値（ｎ＋
１）をポツプ動作Ｂで外に出すことを意味する。
デイープバインド法の長所は、スタツクのプツシ
ユポツプ動作が簡単であるので関数コール時の引
数変数のバインド処理、関数リターン時の引数変
数のアンバインド（Unbind）処理のオーバーヘ
ツドが比較的少ないことであり、短所は、大域変
数（自由変数とも呼ぶ）のように、かなり以前に
バインドされた変数すなわちスタツクの奥の方に
ある変数の参照に時間がかかることである。

シヤローバインド法は、各変数毎に、その値を
保持するランダムアクセス域（Value Cellと呼
ぶ）を設け、関数コール時には引数変数のバリユ
ーセルへその実引数を格納し、バリユーセルに以
前から存在した値を、線形リスト（またはスタツ
ク）へ名前と旧値の対として格納し、変数参照は
対応するバリユーセルを読むだけでよく、関数リ
ターン時には、その引数変数のバリユーセルへ線
形リスト（またはスタツク）へ格納してあつた旧
値を戻す。シヤローバインド法の長所は、引数参
照時間が短かいことであり、短所は関数コール時
の引数変数のバインド処理、関数のリターン時の
アンバインド処理のオーバーヘツドが大きいこと
である。

以上のようにデイープバインド法はシヤローバ
インド法に比べて、引数のバインド／アンバイン
ド処理については高速であるが、変数の参照とく
に大域変数の参照が遅い。すなわち、従来は変数
の参照をポインタを１つづつ減らす逐次方式で行
なつていたので、非常に処理が遅かつた。この点
を改良するのが本発明の方式である。

本発明の目的は、上述したような関数型情報処
理装置において、データ間のつながりを表わすリ
ストをデイープバインド方式に従つてスタツクメ
モリ内に格納される変数を参照するアクセスタイ
ムを短縮するために主記憶装置の外部に連想バツ
フアおよび関数のコール時とリターン時にそれぞ
れ＋１、−１するカウンタを設けた関数型情報処
理装置を提供することにある。

本発明の特徴とするところは、プログラムの構
造及び実行形態が仮引数としての変数名と実引数
としての変数値の対として環境リストである
First−In−Last−Out型のスタツクメモリへ格納
することによつて、呼ぶべき関数の仮引数変数へ
実引数を束縛し、呼ばれた関数は変数の値を参照
する場合、上記環境リストの最近の束縛値を使つ
て処理を行ない、その関数の値が得られれば、関
数の仮引数変数を上記環境リストから削除して上
記関数値をリターンするという一連の処理を繰返
す関数型情報処理装置において、関数をコール及
び関数がリターンする毎にそそれぞれ＋１、−１
されるカウンタと、変数名、変数の環境リストの
位置情報、変数が参照されて登録されるときの前
記カウンタ値から各ワードが構成される連想バツ
フアメモリを有し、変数の参照は、変数名をキー
としてまず前記連想バツフアメモリをアクセスし
て存在すれば対応する変数の環境リスト上の位置
より変数値を求め、存在しなければ、前記環境リ
ストを関数フレーム毎にカウンタFCTRをデクレ
メントしながらさかのぼつて検索して、最初に見
つかる変数の値を使い、その変数名、FCTR値、
環境リスト（又はスタツク）上のアドレスを対と
してバツフアに格納し、関数がリターンする時に
は、その関数の前記カウンタ値と一致する前記連
想バツフアのワードを削除する関数型情報処理装
置を提供することである。

以下図面を参照して本発明の一実施例を説明す
る。

まず、スタツク上のデイープバインド方式では
次のような処理が行なわれる。関数呼び出しが起
こる手前で実引数がそろうとスタツクは第４図ａ
のようになる。ここでSTPはスタツクトツプポ
インタである。関数が呼び出されると呼び出され
た関数側で第４図ｂのような形になる。

以上のような処理によつて第４図ｃのようにス
タツク中の関数毎の情報間は、旧FPによつてリ
ンクされる。ここでFPはフレームポインタすな
わち現在実行している関数の制御情報の先頭を指
すものである。このリンクによつて変数の参照が
あつたときそれをたどつて変数名をサーチするこ
とによつてその値を得ることができる。

たとえば F₁（ｚ）＝z²＋F₂(10) F₂（ｘ）＝x²＋ｘ＋F₃(7) F₃（ｘ）＝x⁵＋１＋ｚという関係にある３つの関数において、F₁(3)の
値を求める場合を説明する。関数F₁（ｚ）をコー
ルする時点で仮引数ｚは３に束縛されて、環境リ
スト上にその束縛関係が格納される。しかし、
F₁（ｚ）の計数には関数F₂（ｘ）の値F₂(10)が必要
であるので、関数F₂（ｘ）をコールする。このコ
ール時において、仮引数ｘは10に束縛されて環境
リスト上にその束縛関係が格納される。しかし、
また、F₂(10)の計算には関数F₃（ｘ）の値F₃(7)が必
要であるので、関数F₃（ｘ）をコールする。この
コール時において、仮引数ｘは７に束縛されて環
境リスト上にその束縛関係が格納される。しか
し、F₃（ｘ）の値F₃(7)を求めるのにF₃（ｘ）＝x⁵＋
１＋ｚのｚは大域変数、すなわち、その時点で束
縛されない変数であるが、ｚはF₁（ｚ）をコール
する時点でｚ＝３に束縛されているので、環境リ
スト上をさかのぼつてｚが３であることをサーチ
するわけである。そしてはじめてF₃(7)＝7⁵＋１＋
３が求まり、F₂（ｘ）にリターンしてF₂(10)＝10²＋
10＋F₃(7)が求まり、F₁（ｚ）にリターンして、F₁
(3)＝3²＋F₂(10)となり、F₁(3)という値が求まるので
ある。

一般に関数型情報処理装置において、大域変数
は束縛された局所変数（または仮引数）に比べそ
の数は少いが少数の大域変数が多数回参照される
場合が多い。そこで本発明の関数型情報処理装置
においては新しく連想バツフアおよび関数のコー
ル時とリターン時と、変数を環境リスト（又はス
タツク）上で検索する時にそれぞれ＋１、−１す
るカウンタを設け、ある関数が大域変数を参照し
た場合、前記バツフアにその変数がない場合は、
環境リスト（またはスタツク）をシーケンシヤル
に検索し、変数名が格納してある前記スタツクの
位置情報たとえばアドレスをその変数名と対にし
てさらに変数が見つかつた環境ブロツクに対応す
るカウンタの内容をも対にして１ワードとして前
記高速な連想バツフアメモリに各ワードごとに格
納しておき、以後その変数が参照された場合に
は、変数名でバツフアを連想アクセスしてアクセ
ス時間の大幅な短縮をすることができると同時
に、関数リターン時において前記カウンタの内容
をキーとして前記連想バツフア内の対応するワー
ドを高速に削除することができる。

第５図の環境リストにおいて、関数F₁はF₂を、
F₂はF₃を、F₃はF₄を、F₄はF₅を、そしてF₅はF₆
をコールするようになつているとする。このとき
関数F₆を F₆（Ｎ）＝N²＋ｘ＋ｚ＋z² であると仮定する。すなわち、Ｎは局所変数で、
ｘとｚは大域変数である。大域変数であるｘは関
数F₂（ｘ、ｙ）をコールする時点でｘ＝５である
ように束縛されており、ｚは関数F₃（ｚ）をコー
ルする時点でｚ＝８であるように束縛されてい
る。F₆（Ｎ）の値を計算するために、Ｎとｘそし
てｚの各変数を参照するため、まず環境リスト上
をサーチするが、局所変数Ｎに対しては即座にそ
の値（例えばＮ＝10）をみつけることができる
が、ｘやｚは最初は環境リスト上をさかのぼつて
サーチする必要がありｘ＝５、ｚ＝８であること
がわかる。しかし、もし、この最初のサーチにお
いて、見つけたｘ＝５、ｚ＝８を第５図ｂのよう
に連想バツフアに対として格納しておけば、２度
目の同じ変数名の参照は連想バツフアをまずアク
セスすることによつてなされ高速化されることに
なる。すなわち、F₆（Ｎ）＝N²＋ｘ＋ｚ＋z²の最
後の項z²は連想バツフアにｚ＝８という対が格納
されていて変数ｚをキーとして連想検索すればｚ
＝８であることがただちに決まりz²に代入すれば
よいことになる。さらに後述するようなコール時
およびリターン時にそれぞれ＋１、−１するカウ
ンタを設けて前記バツフア内のいらなくなつたワ
ードを高速に削除するようにしている。

次に、バツフアメモリの持つべき機能は以下の
ものがある。なお、バツフアメモリの具体的構成
は第７図を参照して後述する。

(1) ある大域変数を初めてアクセスした場合、そ
の変数をバツフアへ登録しておき、以後のアク
セスの高速化をはかる。この場合、変数名とそ
のバインド値の環境リスト（又はスタツク）上
での位置情報（スタツク内アドレス）も同時に
格納して、変数値はスタツク内アドレスを参照
してランダムアクセス的にスタツクから引き出
す。

同時に、第６図にバツフアエントリ（ワー
ド）のフオーマツトを示すように外部に設けた
カウンタFCTR（Function Counter）は関数の
コール、リターンに応じてカウントアツプ、カ
ウントダウン、及び変数を環境リスト（又はス
タツク）上をさかのぼつて検索する時、環境ブ
ロツク毎にカウントダウンを行ない、変数をバ
ツフアへ登録するとき、その環境ブロツクに対
応するFCTRの値をバツフアのFNO域へ書き
込みまた関数がリターンするとき、そのFCTR
値と一致するFNO域を有するバツフアエント
リを削除するのに用いるためFNO域を対とし
て設ける。なお、変数名すなわちネーム域は変
数を参照する際のキーおよび関数コールの時に
変数バインドする際に、その変数を削除するの
に用いる。また、FNO域はその対応する変数
がどの関数の引数であるかを区別するのに用い
る。さらに、ポインタ域は変数の他が格納され
ている環境リストすなわちスタツク上のアドレ
スを指すもので、変数をアクセスする時、変数
名が一致するエントリのポインタ域で環境リス
ト（又はスタツク）をアクセスする。なお、第
６図において、Ｖは有効表示ビツトを示すもの
である。

(2) 与えられた変数名が内部格納変数名と一致す
るかどうかをハード的に行ない、一致がとれれ
ばその変数名に対応するスタツクアドレスを読
むこと、すなわち、変数名をキーとしてバツフ
アを連想検索して、アタツクアドレスをリード
機能をもつことである。これは、変数名を参照
する場合に必要である。

(3) 変数名をキーとしてバツフアメモリ上でその
変数と同一名の変数の有効表示ビツトＶをリセ
ツトする機能を持つことである。これは参照さ
れてバツフアに存在する大域変数と同一名の仮
引数名をもつ関数をコールする場合、バツフア
上のその大域変数を削除するため、必要であ
る。この情報をおこたると同一変数名の参照の
場合に、大域変数より局所変数を優先するスコ
ーピングの原則がくずれる。

(4) リスト上の位置情報（FCTR）をキーとし
て、それが一致するすべての項目の有効表示ビ
ツトＶをリセツトする機能を有する。これは関
数が呼び側の関数へリターンする時に、そのリ
ターンする関数の引数変数を全てバツフアから
除去するものに必要である。この処理をおこた
ると、もしこの関数の仮引数変数と同一名の変
数がこの関数以前にバインドされており、その
変数を参照すると、既に環境から除去されたは
ずの値が誤まつて使われることになる。

上述したように、各変数を環境上での関数フレ
ーム位置に対応するFCTR値付でバツフアに格納
していないと、リターンする関数の各仮引数名を
キーとして、それぞれバツフアを検索して除去す
るか、バツフアのオールクリアを行なう必要があ
る。前者では、時間がかかり、後者では大域変数
のバツフア内での寿命は、初めて参照した関数が
リターンするまでとなり、バツフアの効果はほと
んどなくなる。

以下にバツフアの動作を説明する。まず、変数
参照は次のように行なう。バツフアをその変数名
をキーとして検索し、存在すればそのポインタ域
でスタツク上の値をアクセスする。存在しなけれ
ば、環境リスト（スタツク）を変数名をキーとし
て検索する。この時、関数フレームを１つさかの
ぼることにFCTRをカウントダウンし、最初にみ
つかつたその変数値を使うことになる。そして、
バツフアへ変数名、FNO域（みつけた関数フレ
ームに対応するFCTR）、ポインタ域を登録して、
以後の参照に備えるものである。

関数コールは次のように行なう。コールする関
数に引数が存在すればバツフア中の同一名の変数
を誤まつてアクセスしないように、仮引数変数と
ネーム域が一致するバツフアエントリーを削除す
る。

そして、関数リターンは次のように行なわれ
る。リターンする関数に引数が存在すれば、その
関数フレームに対応する現在のFCTRとFNO域
が一致するバツフアエントリを削除する。これに
より、バツフア中にこの引数変数の旧バインド値
が残るのを防ぐ。そして、FCTRをカウントダウ
ンして、戻り先の関数フレームに対応するFCTR
値にする。

以上のように、FCTRの役目は、関数リターン
の際の引数変数のアンバインド処理の時に、複数
個の引数が存在しても、FCTR値をキーとして
FNO域がそれと一致するバツフアエントリを一
度にクリアすることである。

第７図は、本発明の連想バツフアメモリおよび
関数コール時およびリターン時にそれぞれ＋１、
−１するカウンタの具体的構成図である。すなわ
ち、プログラムの構造及び実行形態が変数名と変
数値の対として、環境リストへ格納することによ
つて、呼ぶべき関数の仮引数変数に実引数を束縛
し、呼ばれた関数は変数の値を参照する場合、上
記環境リストの最近の束縛値を使かつて処理を行
ない、関数の値が得られれば、関数の仮引数変数
を上記環境リストから削除して、上記関数値をリ
ターンするという一連の処理を繰り返す関数型情
報処理装置の内部に連想バツフアメモリ及び関数
コール時およびリターン時にそれぞれ＋１、−１
するカウンタを新たに加えてなる構成図である。
前記連想バツフアメモリの持つべき機能は、前記
(1)、(2)、(3)である。

上記実施例には、まずメモリ１０，３０が設け
られ、それぞれが１〜ｍのレジスタで構成され
る。メモリ１０は変数名ネームを格納する変数名
域メモリであり、前記変数名がメモリ１０に格納
されるとき、メモリ２０は関数フレームを１つさ
かのぼるごとにカウントアツプするカウンタ２１
のそのときの値を格納するFNO域メモリであり、
メモリ３０はスタツク内アドレスを格納するポイ
ンタ域メモリである。前記メモリ１０，３０のｉ
番目（ｉ＝１、２、…ｎ）のレジスタはそれぞれ
が対応し、１つのワードを形成している。関数型
情報処理装置の環境リスト内のある変数をはじめ
てアクセスした場合、その変数のFCTRカウンタ
２１０の内容とスタツク内アドレスを前記連想バ
ツフアの前記メモリ１０，３０にそれぞれ登録し
ていき、以後のアクセスの高速化を図る。連想バ
ツフアへの登録は変数名に対しては入力線１０
１，１０３を介して変数名ｉのセルに書き込みパ
ルス信号WE_i（図示せず）を活性化して書き込む。
このとき同時に、FCTRカウンタ２１０の内容を
入力線２０１，２０３を通して、RNO域のｉ番
目のセルに前記同じ書き込み信号WE_iを活性化し
て書き込む、同様にスタツク内アドレスは入力線
３０１からポインタ域のｉ番号のセルに前記書き
込み信号WE_iを活性化して書き込む。連想バツフ
アは与えられた変数名が、あらかじめ内部メモリ
１０と一致回路４０で一致するかどうかを検出
し、一致がとれれば出力線４０１のｎ本のうちの
どれか一本が活性化されて選択回路６０を制御し
て、対応するセル３０の内容、すなわちスタツク
内アドレスを出力線６０１に出力する。すなわ
ち、変数名をキーとして、連想検索を行いスタツ
ク内アドレスを読み出すことができる。しかも、
スタツク内アドレスを格納するメモリ３０は、書
き込みも行えるもので、変数名に対応するアドレ
スを読み出したり、書き込んだりすることができ
る。これは、アドレスを参照したり変更したりす
るときに必要である。

また、カウンタFCTR２１０の内容をキーとし
て連想バツフアから同一パターンのFNO域の有
効表示ビツトＶをリセツトする機能を実現するた
めに、本実施例には、有効表示ビツト格納セル群
８０およびヴアリツド（Valid）更新回路９０が
含まれる。有効表示ビツトＶを格納するセル群８
０のうちV_iセルは、ヴアリツド更新回路９０によ
つて、変数名ｉ、アドレスｉを書き込むときの前
記書き込み信号WE_i（図示せず）によつてセツト
される。

一致回路５０の出力５０１を選択すれば、入力
のカウンタ内容出力２０１とメモリ２０に格納さ
れているFNO域パターンの一致がとれたとき、
対応する有効表示ビツトがリセツトされ、FCTR
値をキーとしてFNO域がそれと一致するバツフ
アエントリを一度にクリアすることができる。

なお変数名はｎ−wayリプレースロジツク１０
０にも加えられ、その出力がメモリ１０，２０，
３０の入力に接続されていることも付言する。

以上説明したように、本発明によれば、デープ
バインド方式に従つて実行していく関数型情報処
理装置において、変数の値を検索するアクセス
を、前記連想バツフアおよび関数コール時および
リターン時にそれぞれ＋１、−１するカウンタを
用いることによつて高速に行なうことができる。

【図面の簡単な説明】

第１図はａ，ｂ，ｃは２進木リストを説明する
図、第２図は関数型情報処理を説明する図、第３
図ａ，ｂはデイープバインド法を説明する図、第
４図ａ，ｂ，ｃはスタツク上のデイープバイド法
を説明する図、第５図はスタツク上で具体的にデ
イープバインド法を説明する図、第６図はバツフ
アエントリのフオーマツトを示す図、第７図は本
発明に用いられるバツフアの一実施例のブロツク
図である。１０……変数名域メモリ、２０……FNO域メ
モリ、２１……カウンタ、３０……ポインタ域メ
モリ、２１０……FCTRカウンタ、４０，５０…
…一致回路、６０……選択回路、８０……有効表
示ビツト格納セル群、９０……ヴアリツド更新回
路。

Claims

【特許請求の範囲】

１プログラムの構造及び実行形態が仮引数とし
ての変数名と実引数としての変数値の対として環
境リストであるFirst−In−Last−Out型のスタツ
クメモリへ格納することによつて呼ぶベき関数の
仮引数変数へ実引数を束縛し、呼ばれた関数は変
数の値を参照する場合、前記環境リストの最近の
束縛値を使つて処理を行ない、その関数の値が得
られれば関数の仮引数変数を前記環境リストから
削除して前記関数値をリターンするという一連の
処理を繰返す関数型情報処理装置において、関数
をコール及び関数がリターンする毎にそれぞれ＋
１、−１されるカウンタと、変数名、変数の環境
リストの位置情報、変数が参照されて登録される
ときの前記カウンタ値から各ワードが構成される
連想バツフアメモリを有し、変数の参照は、変数
名をキーとしてまず前記連想バツフアメモリをア
クセスして、存在すれば、対応する変数の環境リ
スト上の位置より変数値を求め、存在しなけれ
ば、前記環境リストから変数名を検索して最初に
見つかる変数の値を使い、関数がリターンする時
には、その関数の前記カウンタ値と一致する前記
連想バツフアのワードを削除することを特徴とす
る関数型情報処理装置。