JPS584452A - 関数型情報処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、数値ではなく記号を処理するリスｌ（Ｌｌｓ
ｐすなわちＬｉ５ｔ　Ｐｒｏｃｅｓｓｏｒ　）のような
関数型言語用の関数型情報処理装置に係〕、とくに関数
が実行される環境（変数の値として何をつかうかという
こと）をコンビ、−タ内部の記憶回路にスタック構造的
に格納するにあたって、そのスタ。

りに格納された変数の検索時間を短縮する良めに上記ス
タックメ毫りの外部に連想ｄラッテを設けることを特徴
とする関数型情報処理装置に関する。

リスプは第１図に示すような２進水リストすなわち記号
のつながりを閉路を含まない節点と枝の集合である木構
造（第１図（ａ））であられしえものを扱うものである
。すなわち、纂ＩＷＡ（ａ）のような木構造であられさ
れる記号のつなかｐｔ第１図（ｂ）のように各ノードか
らでる枝が２本づつである２進水表現に直し良形で第１
図（＠）に示されるような主記憶装置に格納する。すな
わち、各リストセルは主記憶装置の１＃＃また［２１１
からなり七の各セルは左、右２つの部分からなる。各セ
ルの左の部分は畳通鉱ある記号、たとえば木という文字
の記号のピットＩり一ンが格納され、右の部分はその記
号とつながるべき、次の記号を格納しているセルの番地
を格納することによって２つセルが連結して−、ること
を表現する。従って、第１図（・）のりストセルのっな
が）は、Ｊ１１’図（ｂ）の２進木リストを記憶回路上
で実現しているものであるｅリスプは、このようなリス
ト構造をリス！言語を実行することによりて、ｆｃ１セ
、？を使りて動的に変換し、目的のリスト構造を得る装
置である。

リスプにおいてｆａダッムするということは、２進水リ
ストを変換する丸めに必要な以下の５つの基本関数を組
み合せて形成される関数を定義し、その値を求めること
である・ ５つの基本関数とは１ イ）　　ｅａｒ（ｚ）カール ２過木リス）Ｘの左の枝の先にある２進水リストを値と
ｊる・ 口）　　ｃｄｒ（Ｘ）クダー ２進木リス）Ｘの右の枝の先にある２進木リストを値と
する。

／９　　＠０！ｋｌ（Ｘ：Ｙ）　コンス新しいリスト・
セルを設け、その左の枝を２進木リス）Ｘとし右の枝を
２進木リストＹとするような新たな２進水リストを作っ
てそれを値とする。

→　ａｔｏｍ（Ｘ）　　アトム Ｘがアトムの時、真という値（”？”中１＊Ｔ＊”で示
１）す）ｅｌｌ夛、そうでないとき、偽（″ＮＩＬ”と
いうアトムで示す）とする。

ホ）・ｑ　（Ｘ：Ｙ）イク ＸとＹが同じ２進木リストの時、真の値（′″Ｔ＃や一
＊Ｔ＊’）を城）、そうでない時、偽の値（”ＮＩＬ’
　）を取る。

例えば、／　（ｘ　ｅ　ｙ　）　ｗ＝　ｚ７４　、Ｘの
定義Ｌ−ｆ−λ（（Ｘ　Ｉ　Ｙ　）　；　Ｘ’　＋ｙ”
）と表わすことにより、／（２、３）の値は、 λ（（ｘｔｙ）；ｘ’＋ｙつ（２，３）口２’　＋　３
２とな）、変数の対応関係を明確に規定することができ
る。

こζで％（Ｘ−Ｙ）は仮引数と呼ばれる変数でありて（
２，３）は（ｘ、ｙ）のそのときの値である実引数と呼
ばれるものである。そして、この実引数（２，３）を仮
引数（ｘ、ｙ）に代入することｔ−束縛（ｂｌａｍｌｍ
ｇ　）すると呼び、実引数を仮引数に束縛することによ
って関数の値、この場合２　＋３　という目的のリスト
をつくることがリスｆｆ実行することである。したがっ
て、リス！すなわち関数型情報処理装置にあっては、仮
引数と実引数をどのように束縛するかが問題となる。

本発明において社、変数の束縛値（ＢｌｎｄＶａｌ−・
）が線形リスト（ＩＩ境ツリストすなわちＦＩＬＯ（Ｆ
ｌｒｓｔ　　Ｉ！Ｌ　　Ｌａ５ｔ　　Ｏｕｔ　　゛ま　
ｌヒは　ハａｈ　ｄｏｖｎｓ　　Ｐｏｐ　　ｕｐ　　　
）　　１１スタツクへ変数名と値の対で格納される。こ
こでＦＩＬＯＩＪｌスタ、りとは前記記憶回路上で２進
水リスト構造でデータを間接アドレス方式（すなわち、
あるセルに次につながるセルのアドレスを格納しておく
方式）で格納していくむとである。この変数名と値との
対を格納していく順序は、引数変数の関数が呼ばれたと
きに実引数を値とする順番になる、いわゆるダイナさ、
クスコーピンダ（Ｄｙｎａｍｌ＠ｉｉ＊ｅｐ１ｍｇ　）
型Ｏｍｌ境をもつ関数型言語でありて、その変数の値が
なにであるかを参照する手順蝋、基本的には上記環境リ
スト（又はスタ。

り）を先頭からシーケンシャルに検索して最初に見つか
つ九値を使う、いわゆるディーｆバインド（Ｄ・すＩｌ
ｌｍｄ）ｆｉ変数束縛を・行なう場合に、大域変数（関
数の引数のように関数を起動する時に束縛値が決定され
ている局所変数とは異なり、それ以前からその値が決め
られている変数）ｔａし出すアクセスタイムを短縮する
九めに主記憶装置の他に連想ノ量ツ７アを設けることが
本発明の特徴であ一般に、第２図に示すように関数型と
は、そのグーグクム構造や実行形態が呼ぶべき関数すな
わち実行するべき関数ｆ−λ（（Ｘ　＃　Ｙ　）　：　
Ｘ”　＋　Ｙ”　）の仮引数（ｘ、ｙ）へ実引数（２，
３）を結合すなわち束縛（バインド）シ、呼けれたく起
動された）関数社、捜されたすなわち代入されるべき実
引数や大域変数を参照して所定の手続きを実行し、その
関数の値２’　＋　３２を呼び側へ返し、それ以外の副
作用（ＩＩ境を変更すること）はないものを言う、副作
用については、本発明の要旨からみて、説明を省略する
。

関数を呼び出す（Ｃａｌｌ　）場合、その仮引数への実
引数の束縛の方法には、ディー！バインド法とシャロー
ノ量インド（Ｓｈａｌｌ譚Ｂ量１１ｄ）法がある。

ディー７’　ｔ４インｒ法は前述しえように、束縛され
た変数名（ｘ、ｙ）と値（２ｅ　ｓ＞の対（ペア、すな
わち、Ｘは２．Ｙは３の対）を線型リストやスタック構
造に格納し、変数値を参照する場合に杜、最後に束縛さ
れた方向からシーケンシャルにたど９、最初に発見した
その変数の値を使うという環境の構成である。

すなわち、グイー！バインド法は、第３図（ａ）　Ｋ示
すように、主記憶装置の記憶単位である語の構成が左、
右２つの部分に分かれ、１つのセルＫｌっていて、左部
に変数名を格納し、右部はそのセルが接続する次のセル
のアドレスを格納することによって次のセルのその変数
の値を知ることができ、沢山の変数がある場合は、第３
図（＆＞のように連結し、等測的に第３図（ｂ）のよう
なＦＩＬＯ型のスタ、りを構成するものである。

関数コール（Ｃａｌｌ）の時に、引数変数に値を／曹イ
ンドするときには、環境リスト（を九は積項スタック）
Ｏ検索出発点の方向から、その名前と値の対をつなげ、
検索出発点−インタを新えに付加し九項目の先頭へ更新
する。すなわち、第３図（荀の主記憶装置上では、先頭
に１つのセ＃１＋１を設妙ることに対応し、そのセルが
つながる次のセルが亀であることに対応する。これ祉、
第３図（呻においては、スタックのフッタ、　（Ｐｕｓ
ｈ　）動作へに対応し、その変数名がｍ＋１であって、
その値が（ｍ＋ｔ）であるセルをスタ、ｆの最下段に！
。

シ、して入れることに対応する。関数のリターン（Ｒ＠
ｔｔｒｒｍ　）時には、その関数がコールされたと愈の
状態に検索出発点−インータを戻す、すなわち、第３図
（ａ）の主記憶回路上では、先頭のセルｍ＋１を１つと
って、セル１を先頭にすることに対応し、第３図（ｂ）
では、１＋１とその値（ｎ＋１）をポツプ動作８で外に
出すことを意味する。ディーグーインド法の長所は、ス
タックのグッシ、ブッダ動作が簡単であるので関数コー
ル時の引数変数のバインド処理関数リターン時の引数変
数のアンバインド（Ｕｎｂｌｓｕｌ　）処理のオーバー
ヘッドが比較的少ないことであ多、短所は、大域変数（
自由変数とも呼ぶ）のように、かなり以前にバインドさ
れた変数すなわちスタ、りの奥の方にある変数の参照に
時間がかかることである。

シャルーパインＰ法は、各変数毎に、その値を保持する
ランメムアクセス域（Ｖａｌｕ＠Ｃ＠ｌｌと呼ぶ）を設
け、関数コール時には引数変数のパリ、−セルへその実
引数を格納し、パリ、−セルに以前から存在し九値を、
線形リスト（またはスタック）へ名前と旧懐の対として
格納し、変数参照は対応するパリ、−セルを読むだけで
よく、関散りター７時には、その引数変数のΔす、−セ
ルへ線形リス）（ｔたはスタック）へ格納してあった出
値を戻す、シャローバインド法の長所は、変数参照時間
が短かいことであや、短所は関数コール時の引数変数の
バインド処理、関数のリターン時のアンバインド処理の
オーバーヘッドが大きいことである。

以上のようにディーｆＡインド法はシャローバインド法
に比べて、引数のバインド／アンバインド処理について
社高速であるが、変数の参照とくに大域変数６参照が遅
い、この点を改良するのが本発明の方式である。

本発明の目的は、上述したような関数型情報処理装置に
おいて、データ間のっながシを表わすリス）ヲティーグ
パインド方式に従ってスタックメモリ内に格納される変
数を参照するアクセスタイムを短縮する丸めに主記憶装
置の外部に連想Δ、ファを設けた関数型情報処理装置を
提供することにある。

本発明の特徴とするところ社、グログラムの構造及び実
行形態が仮引数としての変数名と実引数としての変数値
の対として環境リストであるＦｉｒｓｔ　−Ｉｎ　−Ｌ
ａ５ｔ　−０ｕｓｔ型のスタックメモリへ格納すること
によって呼ぶべき関数の仮引数変数へ実引数を束縛し、
呼ばれた関数は変数の値を参照する場合、上記環境リス
トの最近の束縛値を使って処理を行い、その関数の値が
得られれば、関数の仮引数変数を上記環境リストから削
除して上記゛関数値をリターンするという一連の処理を
繰返す関数型情報処理装置において変数名、変数値およ
びその変数が束縛されている前記環境リスト上の位置情
報を対として各ワードが構成され、ｆｏダラム実行中に
変数を参照する場合には変数名をキーとして連想検索し
内部変数と一致がとれれば対応する変数値を読出して使
い、不一致であれば前記環境リストから変数名を検索し
最近にみつかる変数値をつかう処理装置の動作にともな
ってその変数名と変数値を前記環境リスト上の位置情報
も加えて新しく書込み、引数変数名と名前が一致するワ
ードを削除する機能を有し、変数値を変更する場合には
、上記環境リスト上の最近値を変更する情報処理装置の
動作と共にその変数が内部に存在すればその変数値のみ
を変更する機能を有し、関数がその呼び側に復帰する場
合には、その引数名と束縛値の対を上記環境リストから
外す処理装置の動作に伴なってその環境リスト上の位置
情報をキーとして対応するワードを削除する機能を有す
る連想ｚｆ　２７７を設けた関数型情報処理装置である
。

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

まず、スタック上のディーグバインド方式では次のよう
な処理が行なわれる。関数呼び出しが起こる手前で実引
数がそろうとスタ、りは第４図（ａ）のようになる、こ
こで８ＴＰはスタ、クト、ｆｌインクである関数が呼び
出されると呼び出された関数側で第４図（ｂ）のような
形になる０以上のような処理によって第４図（、）のよ
うにスタ、り中の関数毎の情報間は、旧ＦＰによってリ
ンクされる。ここでＦＰはフレームポインタすなわち現
在実行している関数の制御情報の先頭を指すものである
。

このリンクによって変数の参照があったときそれをたど
うて変数名をサーチすることによってその値を得ること
ができる。

たとえば Ｆｌ（Ｚ）　露ｚ２４４２（１０） Ｆ２（ｘ）＝ｘ２＋！＋Ｆ３（７） Ｆ３（ｘ）＝ｘ’＋１＋Ｚ という関係にある３つの関数において、Ｆｌ（３）の値
を求める場合を説明する。関数Ｆｌ（Ｚ）をコールする
時点で仮引数２は３に束縛されて、環境リスト上にその
束縛関係が格納される。しか２し、Ｆｌ（Ｚ）の計算に
紘関数Ｆ２（ｘ）の値Ｆ２（１０）が必要であるので、
関数Ｆ２（ｘ）をコールする。

このコール時において仮引数ＸはｌＯに束縛されて環境
リスト上にその束縛関係が格納される。しかし、また、
Ｆ２（１０）の計算には関数Ｆ３（Ｘ）の値Ｆ３（７）
が必要であるので、関数Ｆ３（ｘ）をコールする。この
プール時において、仮引数Ｘは７に束縛されて環境リス
ト上にその束縛関係が格納される。しかし、Ｆ３（ｘ）
の値Ｆ３（７）を求めるのにＦ３（Ｘ）−Ｘ’＋１＋Ｚ
の２は入城変数、すなわち、その時点で束縛されない変
数であるが、２はＰＩ（Ｚ）をコールする時点で２■３
に束縛されているので、環境リスト上をさかのばりて２
が３であることをサーチするわけである。そしてはじめ
てＦ３（７）−７’＋１＋３が求ま）、Ｆ２（りにリタ
ーンしてＦ２（１Ｇ）冨１０２＋１０＋Ｆ３（７）が求
ｔ９、Ｆｌ（Ｚ）にリターンして、Ｆｌ（３）−３”＋
Ｆ２（１０）とな夛、Ｆｌ（３）という値が求まるので
ある。

一般に関数型情報処理装置において、入城変数は束縛さ
れた局所変数（また娘仮引数）に比べその数は少いが少
数の入城変数が多数回参照される場合が多い、そこで本
発明の関数型情報処理装置において社新しく連想バッフ
ァを設置ある関数が入城変数を参照した場合、前記２１
７丁にその変数がない場合は、環境リス）（ｔたはスタ
、り）をシーケンシャルに検索し、得九値をその変数名
と対にして前記高速な連想バッファメモリに格納してお
き、以後その変数が参照された場合には、変数名でバッ
ファを連想アクセスしてアクセス時間の大幅な短縮をす
ることができるのである。

第５図（荀の環境リストにおいて、関数Ｆ１はＦ２ｔ、
Ｆ２はＦ３を、Ｆ３はＦ４を、Ｆ４はＦ５を、そして？
　！Ｓａｔ　６をコールするようになっているとする。

このとき関数Ｆ６を ７６（Ｎ）−Ｎ”＋ｘ＋Ｚ＋Ｚ２ であると仮定する。すなわち、Ｎは局所変数で、Ｘと２
は入城変数である。入城変数であるＸは関数ｒ　２　（
ｘ　＊　ｙ　）　　をコールする時点でｚ　Ｗ　５であ
るように束縛されてお夕、ｚは関数Ｆ３（Ｚ）をコール
する時点で２■８であるように束縛されている。

Ｆ６（Ｎ）の値を計算するために、ＮとＸそして２の各
変数を参照する喪め、まず環境リスト上をサーチするが
、局所変数Ｎに対しては即座にその値（例えばＮ−１０
）をみつけることができるが、ｘ　’ｐ　Ｚ　社最初Ｆ
ｉ環境すスト上をさかの埋ってサーチする必要があり、
Ｘ　ｗｍ　５．７．　ｗｍ　ｇであることがわかる、し
かし、もし、この最初のサーチにおいて、見つけたＸ冨
５、Ｚ−８を第Ｓ図（ｂ）のように連想・（、ファに対
として格納しておけば、２＊目の同じ変数名の参照状連
想／譬、７アをまずアクセスする仁とによってなされ高
速化されることになる。すなわち、Ｆ６（Ｎ）＝Ｎ２＋
ｘ＋Ｚ＋Ｚ”　Ｏ最後の項ｚ２は連想バッファにＺ−Ｓ
という対が格納されていて変数２をキーとして連想検索
すればＺ−８であることがただちに決ｔ　Ｉ　Ｆ２に代
入すればよいことになる。・本実明線このような連想／
４ツ７アを設置することＫよって入城変数の参照アクセ
スタイムを速くすることができる。

このバッファメモリの持つべき機能は以下のものである
。なお、バッファメモリの具体的構成は第９図を参照し
て後述する。

（１）　　ある入城変数を初めてアクセスした場合、そ
の変数をバッファへ登録しておき、以後のアクセスの高
速化をはかる。この場合、変数名、変数値の他に、その
バインド値の環境リスト（又はスタック）上での位置情
報ＥＩＤ　（ＥｎｖｌｒｏｎｍｅｎｔＩｄ＠ｎｔｌｆｌ
＠ｒ　）も同時に格納する。

（２）　　与えられた変数名が内部格納変数名と一致す
るかどうかをＩ・−ド的に行ない、一致がとれればその
変数名に対応する値を読んだり書いたシすることができ
ること、すなわち、変数名をキーとしてバッファを連想
検索して、値をリードまたはライトする機能をもつこと
である。これは、変数を参照した）、変更したシする場
合に必要である。

（３）　　変数名をキーとしてパ、７アメモリ上でその
変数と同一名の変数の有効表示ビットｖをリセ、トする
機能を持つことである。これは参照されてＩ４ツ７アに
存在する入城変数と同一名の仮゛引数名をもつ関数を＝
−ルする場合、バッファ上のその入城変数を削除するた
めに必要である。

この処理をおこたると同一変数名の参照の場合に、入城
変数より局所変数を優先するスコーピングの原則が８ず
れる。

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

上述したように、各変数を環境上での位置情報ＥＩＤ付
でバッファに格納していないと、リターンする関数の各
仮引数基をキーとして、それぞれ／ｆッ７アを検索して
除去するか、バッファのオールクリアを行なう必要があ
る。前者では、時間がかかり、後者では大域変数のバッ
ファ内での寿命拡初めて参照した関数がリターンするま
でとなり、バッフ７０効果はほとんどなくなる。

第６図は、前述のべ、７アメモリの必要機能（１）を説
明する図であり、Ｅｌは参１関数の引数のバインドブロ
ック、Ｆｌは参１関数のフレーム、ＩＰはエンパイμン
メントポインタ（環境リストイインタ）である、今、関
数＃４がある変数ＶＡＲを参照したとし、！８ＰからＥ
４．Ｉｉ：３．Ｅｌと環境を検索し、Ｅｌでその変数Ｖ
ＡＲが見つかったとすると、／々ツファに格納する環境
リスト上の位置情報とはＥ２バインドツク、りのスタ、
り内アドレスＥＡ２のことである。このアドレスを７１
．シング（圧縮コード化）して、長さを短縮してＥＩＤ
とすることもできる。

第７図（１）　、　（ｂ）はバッファメモリの前述の必
要機能（３）を説明するものである。いま、関数＃４が
仮引数基ＷＡＲをもつ関数Ｉ＃５をコールしようとして
いるとする。このときバインドブロックに変数ｖＡＲと
その実引数値が対として格納され、更に、変数バッファ
に変数名ｖＡＲをもつ項目がもし存在すれば、それのバ
リッドピットをリセットする。

第８図は、前述のバッファメモリの必要機能（４）を説
明するものである。関数＃４が大域変数ＷＡＲを参照し
、それがＥ２内で見つかり、／４ツ７リターンしてゆき
、関数Φ２＃ザリターンする場合を考える。関数−＃２
がリターンすれば、その引数ＷＡＲのｇ２／４インド！
ロックでの束縛も解除されるので、ｚ青ｙ　７　ｙメモ
リ中の変数ＷＡＲ４削除される必要がある。そこで、そ
のときの鳶Ｐの値ＩＡ２をキーとして／４ツファからＥ
ＩＤが一致する項目を削除する。

第９図は、本発明の連想バッファメモリの具体的構成図
である。すなわち、グロダラムの構造および実行形態が
変数名と変数値の対として、環境リストへ格納すること
によって、呼ぶべき関数の仮引数変数に実引数を束縛し
、呼ばれた関数は、変数の値を参照する場合、上記環境
リストの最近の束縛値を使Ｊ、って処理を行ない、関数
の値が得られれば、関数の仮引数変数を上記環境リスト
から削除して、上記関数値をリターンするという一連の
処理を繰り返す関数型情報処理装置の内部に連想バッフ
ァメモリを新たに加えてなる構成図である。前記連想バ
ッファメモリの持つべき機能は、前記（１）　、　（２
）　、　（３）　、　（４）である。

上記実施例には、まずメモリ１０，２０．３０が設けら
れ、それぞれが１〜ｎのレジスタで構成される。メモリ
ｌＯは変数名ネームを格納するものであり、２０は環境
アイデンテイ７アイヤＥＩＤを格納するものであり、３
０は変数値ヴアリ、−を格納するものである。前記メモ
リ１０，２０゜３０の１番”目（ｉ　ｖｘ　ｌ　、　２
．−”　１ｋ　）のレジスタはそれぞれが対応し、１つ
のワードを形成している。

これが第１の機能である。関数情報処理装置の環境リス
ト内のある大域変数をはじめてアクセスした場合、その
大域変数とＫＩＤと変数値鵞前記連想バッファの前記メ
モリ１０，２０．３０−にそれぞれ登録していき、以後
のアクセスの高速化を図る。連想バッファへの登録線変
数名ネームに対しては入力線１０１，１０３をネーム１
のセルに書込み／４ルス信号ＷＥｉを活性化して書き込
む。仁のとき同時に、環境位置情報である環境アイデン
テ４ファイヤ）ＪＤ　ｔ−人力線２０１，２０３を通し
て、ＥＩＤの１番目のセルに前記書込み信号ＷＥ１　　
を活性化して書き込む、同様に変数値は入力線３０１か
らグアリ、−の１番目のセルに前記書込み信号ｗｚ１　
を活性化して書込む、前記第２の機能を行なうために、
連想パ、７ア社、与えられた変数名ネームが、あらかじ
め内部メモリｌＯに格納しておいた変数名と一致回路４
０で一致するかどうかを検出し、一致がとれれば出力１
ｉ４０１ｏ１１本のうちのどれか一本が活性化されて、
選択回路６゜を制御して、対応するセル３０の内容、す
なわち対応する変数値を出力線６０１に出力する。すな
わち、変数名を中−として、連想検索して変数値を読出
すことができる機能をもつ、しかも、変数値を格納する
メモリ３０は書き込みも行えるので、変数名に対応する
値を読出し九９、書込んだ夛することができる。これは
、変数値を参照し九カ変更した〕するときに必要である
。

第３及び第４の機能である、変数名まえは環境アイデン
ティファイブをキーとして、連想メモリバッファから同
一名の項目の有効表示ビットｖをリセットする機能を実
現するため、本実施例には、選択回路７０、有効表示ビ
ット格納セル群８ｏおよび選択回路９０が含まれる。

有効表示ピットｖを格納するセル群のうち、Ｖｉミセル
前記変数名１、ＥＩＤｉ、変数値１を書き込むときの前
記書込み信号ｗｇ１によりてセットする。

変数名をキーとする場合は、選択回路７０で一致回路４
０１の出力を選択し、リセット信号１００１が論理ｌの
とき、にの回路１０Ｇによりて出力１００２のうち一致
回路４０で内部変数名１番目と入力された変数名１番目
の一致がとれたとき、対応する有効表示ピットｖ１がリ
セットされる。

有効表示ビットセル群の出力社選択回路９０に入力され
、一致回路４０の出力４０１の制御をうけて選択される
ので、出力９０１には変数名と格納変数名が一致がとれ
ている対応する有効表示ビット選択回路９０の出力９０
１に出力される。

また、機能（４）を実現する九めに、選択回路７０で、
一致回路５０の出力５０１を選択すれば入力のＫＩＤと
格納されているＫＩＤの一致がとれたとき、対応する有
効表示ビットがリセットされ、外部変数名と内部変数名
が一致がとれたとき、選択回路９０で選択されて、出力
９０１に出力される。

以上説明し喪ように、本発明によれば、デーグ・臂イン
ド方式に従って実行していく関数型情報処理装置におい
て、特に大域変数の値を検索するアクセスが前記連想パ
、ファを使うことによって高速に行なうことができる。

【図面の簡単な説明】

第１図（ａ）　ｌ　（ｂ）　、　（ｅ）は２進水リスト
を説明するための図、第２図は関数型情報処理を説明す
るための図、第３図（ａ）　、　（ｂ）　ａディーｆｓ
インド法を説明する図、第４図（ａ）　ｅ　（ｂ）　ｅ
　（＠）はスタ、り上のディー　７’　ｚ４インＰ法を
説明する図、第５図（ａ）　ｅ　（ｂ）は環境リストを
説明する図、第６１社本発明のバッファメモリの機能を
説明する図、第７図（＆）　ｅ　（ｂ）は本発明のバッ
ファメモリの他の機能を説明する図、第８図は本発明の
バッファメモリのさらに他の機能を説明する図、第９図
は本発明の一実施例のブロック図である。 １０・・・変数名メモリ、２０−・位置情報（ＩＣＩＤ
）メモリ、３０・−変数値メ篭り、４０．５０・・・一
致回路、６０．７０．９０・・・選択回路。 青４図 （ａ）　　　　　　　　　　（ｂ） （ｃ） 實５図（ａ） 實５図（ｂ、） 實６図 青７１！ＩＩ（ａ） 青 青７図（Ｊ）） ホ ８図

Claims (1)

1. 【特許請求の範囲】 １、　グロダラムの構造及び実行形態が仮引数としての
   変数名と実引数としての変数値の対として環境リストで
   あるＦｌｒｓｔ　−Ｉｎ　−Ｌａ５ｔ　−Ｏｕｔ型のス
   タックメモリへ格納することによって呼ぶべき関数の仮
   引数変数へ実引数を束縛し、呼ばれた関数は変数の値を
   参照する場合、前記環境リストの最近の束縛値を使って
   処理を行い、その関数の値が得られれば関数の仮引数変
   数を前記環境リストから削除して前記関数値をリターン
   するという一連の処理を繰返す関数型情報処理装置にお
   いて、変数名、変数値およびその変数が束縛されている
   前記環境リスト上の位置情報を対として各ワードが構成
   され、グロダラム実行中に変数を参照する場合には、変
   数名をキーとして連想検索し、格納されている変数と一
   致がとれれば対応する変数値を読出して使い、不一致で
   あれば前記環境リストから変数名を検索し最近に見つか
   る変数値を使う処理装置の動作にともなってその変数名
   と変数値を前記環境リスト上の位置情報も加えて新しく
   書込み、それとともに引数変数名と名前が一致するワー
   ドを削除でき、変数値を変更する場合には前記環境リス
   ト上の最近値を変更する情報処理装置の動作と共に、そ
   の変数が内部に存在すればその変数値のみを変更し、関
   数がその呼び側に復帰する場合には、その引数基と束縛
   値の対を前記環境リストからはずす処理装置の動作にと
   もなって、その環境リスト上の位置情報をキーとして対
   応した　−ワードを削除する連想バッファメモリを設置
   した関数型情報処理装置。 λ　変数値を変更する場合において、連想バッファメモ
   リ上にその変数が存在する場合には、連想／苛ツ７アメ
   モリ中の変数値のみを変更し環境リストの該変数値はそ
   のｔまにしておき、連想／９ツフアメモリがオーバーロ
   ーした時に、そのリグレースされる変数の値ｔ−環境リ
   ストに戻すようにした特許請求の範囲集１項記載の関数
   型情報処理装置・