３．超並列構文解析とプログラミング
３.１ 演算式の超並列構文解析
. . 代入文や２項演算式も、同じ機能と構造を持ち、同じ動作規則でデータ処理する沢山のプロセッサを決められた構造に結合したポリプロセッサシステムにより超並列処理が可能である。代入文x=aは等号を代入を意味する２項演算子と考えれば２項演算式である。２項演算式を構成する要素aやxはベクトル又はベクトルを値にとる変数とする。ベクトルの要素が一つのみであれば通常の数値及び変数である。しかし、必要が無い限り両者を区別せず定数a及び変数xのように記述する。演算式の超並列構文解析を行うシステムの基本構造は３個のプロセッサをFig. 3.1(a)の２分木に結合したものであり、そのために各プロセッサは３個の入出力ポートを持ち、ポート０を根、ポート１と２を枝として各枝に他のプロセッサのポート０を接続する。これを図示する際に、特に断らない限り左の枝をポート１とする。２項演算式x+aの各要素x, +, aはそれぞれプロセッサの内部状態に図のようにセットされるが、本システムのプロセッサにはアドレスが無いからプログラムによりセットすべき要素を割当てることはできない。各プロセッサは自分の内部状態と入力を比較して自らの内部状態を決定する。
. . 同図の２分木は演算指令を受けたとき、「内部状態が数値であればポート０に出力し、演算子ならポート１の数値にポート２の数値を演算してポート０に出力する」という簡単な実行動作規則により演算結果をポート０に出力する。一般に多項式で表される演算式の場合にも、全てのプロセッサがこの規則で動作することにより根のプロセッサが正しい結果を出力できるように内部状態がセットされなければならない。２項演算式x+aが直列データとして同図の先頭プロセッサのポート０に入力されたとき、最初の入力xを内部状態にセットし、次の入力“+”により内部状態をポート１に出力して入力を内部状態にセットし、次の入力aはポート２へ出力し、ポート１とポート２に接続されたプロセッサはそれぞれのポート０の入力を内部状態にセットすれば同図の２分木が構成される。そのためには、内部状態にセットする優先順位を「演算子>変数及び定数」と定め、「ポート０の入力が内部状態より順位が高ければ内部状態をポート１に出力して入力を内部状態にセットし、順位が逆なら入力をポート２へ転送する」という規則が必要である。
Fig3_1
. . 演算式がx+a+bのとき、計算の仕方はx+(a+b)と(x+a)+bの２通りあり、前者はFig. 3.1(b)後者は同図(c)とならなければならない。「ポート０の入力が内部状態と同順位のときは先入優先」とすれば同図(a)に入力された２番目の“+”はポート２に転送され、ポート２に接続されたプロセッサは内部状態aをポート１に出力して“+”を内部状態にセットする。最後のbは２度ポート２に転送されて同図(b)が得られる。後入優先にすれば同図(a)の“+”は２番目の“+”の入力によりポート1に出力されるが、このとき「ポート２に内部状態aの返還を要求し、ポート２の入力をポート1に転送した後にポート０の入力“+”を内部状態にセットする」ことにより後者が得られる。先入優先の方が処理は簡単であるが、常識的には後者の計算の仕方が普通であるので同順位は後入優先と規定する。
. . 演算式x+a×bはFig. 3.1(d)の２分木に変換されなければならない。そのためには「演算子が内部状態にセットされる優先順位は“+”が“×”より上位」でなければならない。これによりFig. 3.1(a)に入力された“×”はポート２に転送され、ポート２に接続されたプロセッサは内部状態aをポート１に出力して“×”を内部状態にセットし、bは２度ポート２に転送されてFig. 3.1(d)の２分木が得られる。“+”と“−”、“×”と“÷”は同順位でよいが、例えば、x−a+b, x÷a×bのような演算子の順序の場合は後入優先でないと正しい２分木が構成されない。演算子の優先順位を上位から“+”,“−”,“×”,“÷”の順とすれば先入優先でも後入優先でも正しい２分木を構成できる。
. . 演算式x+a×b−cはFig. 3.1(e)の２分木に変換されなければならない。そのためには、同図(d)の２分木が構成され、先頭プロセッサの内部状態“+”と優先順位の同じ“−”が入力されたとき、“+”をポート1に出力してポート２に内部状態の返還を求めるが、この要求はポート２に接続されたプロセッサ以降に転送され、a及びbを内部状態とするプロセッサはそれをポート０に出力し、“×”を内部状態とするプロセッサは「ポート１の入力、内部状態、ポート２の入力の順にポート０に出力」する。先頭のプロセッサはポート２に受けたa×bをポート１へ転送した後ポート０の入力“−”を内部状態にセットし、次の入力cをポート２へ転送して同図の(e)の２分木が構成される。
. . 数式に括弧が明記されている場合は括弧も内部状態に格納し、２分木を構成しなければならない。ポリプロセッサシステムでは内部状態を元の数式に復元して外部に出力することも重要な情報処理の一つであり、その際に括弧も含めて元と同じ式に復元するためである。c×(a+b)はx=a+bとc×xの２つの計算を１つの式に記述したものである。代入式x=a+bのa+bを１つの値としてポーランド記法に表せば=, x, a+bの順に表記されるが、又、=, a+b, xの順に表記してもよい。これを特別な記号で表したものが(a+b)であると考えることができる。従って、開括弧“(”は２項演算子、閉括弧“)”はa+bの計算結果を代入する名前の無い一時的変数である。数式の中の一部をその計算結果として表すときこのようなポーランド記法が用いられる。例えば、積分の表記Intfdtは被積分関数f(t)を積分演算子“Int”と積分変数dtで囲んで記述し、積分した結果を意味する。同様に、関数f(t)は“f(”が関数を指定し、tに対する関数値を計算する演算子、閉括弧がその関数値を代入される一時的変数である。プログラミングで使われる配列は引数に対して配列要素の値を対応させる関数を表し、開括弧迄が配列を指定し、引数に対する要素を検索する演算子、閉括弧が要素の値を代入される一時的変数である。
. . 代入式x=a+bはFig. 3.1(b)で先頭のプロセッサの内部状態を“=”に変えた２分木に構成されねばならない。従って、代入演算子“=”が内部状態となる優先順位は“+”“−”より上位である。開括弧は“=”に相当する演算子であるが、その順位は演算子“×”“÷”より下位であり、閉括弧は変数の優先順位を持つが、更に、これらは特別な順位を生ずる機能を持つ。演算式c×(d−e)はFig. 3.1(f)の２分木に構成されなければならない。計算を実行するときと同じ様に「ポート１の入力、内部状態、ポート２の入力の順にポート０に出力する］規則により入力された数式を復元出力できることを前提としているからである。従って、(d−e)は内部状態が“×”のプロセッサのポート２へ転送されなければならないが、“×”の優先順位は“−”より低いので順位の変更が必要である。この変更は「“(”をポート２へ転送したプロセッサ及び内部状態にセットしたプロセッサの内部状態は最上位の順位を得る」特権規則を設けることにより可能である。この特権は二重括弧では二重にセットされ閉括弧をポート０に受ける毎に１つずつ解除される。内部状態が開括弧“(”であるプロセッサは特権を持つ間はポート０の入力を全てポート１へ転送し、ポート０の入力“)”により特権が解除されれば本来の演算子の順位に戻り、従って、“)”はポート２へ転送する。この開括弧と閉括弧は対を成す。関数演算子“f(”、積分演算子“Int”は“(”と同順位であり同じ特権を生ずる。積分変数dtは“)”と同じく特権を解除する。
. . 演算式−a×bはFig. 3.1(g)に変換されなければならない。単項演算−aは0−aをポーランド記法−0aに変えて零を省略したものと考えられる。ポーランド記法が多項演算式の中に使われるとき、“×(d−”や“=−a×”のように演算子が二つ続くか又は数式の先頭に演算子が現れることで識別できる。“−”がそのような使われ方をしたとき単項演算子であり、内部状態にセットしたとき特別なフラグをつけて２項演算子の“−”とは区別する。単項演算−aが先頭のプロセッサに入力されるとFig. 3.1(a)で内部状態xが無く、“+”を“−”に変えた２分木に構成され、次に“×”がポート０に入力されるが、「“−”が単項演算子であるとき、内部状態となる優先順位は“×”及び“÷”より下位になる」のでポート１へ出力し、ポート２に要求して受けたaをポート１へ転送した後“×”を内部状態にセットする。次のbはポート２へ転送してFig. 3.1(g)の２分木が構成される。
. . BASICのプログラムにおいてx=1+x=1はx=1+(x=1)と演算され、右の“=”は比較演算子である。従って、Fig. 3.2(a)の２分木に構成されなければならない。そのためには、内部状態が“=”の先頭プロセッサに再度“=”がポート０に入力されたとき比較演算子のフラグを付けてポート２へ転送する。比較演算子の順位は四則演算子より下位となるが、内部状態にセットされると代入演算子と同順位となる。比較演算式がx=a+bのような場合に正しい２分木を構成するためである。しかし、比較演算式は括弧を用いる方が数式としても簡明であり、この場合には比較演算子は代入演算子と同順位でよく、内部状態が“(”のプロセッサがポート０に受けた“=”に比較演算子のフラグを付けてポート1に転送すればよい。従って、比較演算式は括弧で囲って表記すべきである。
. .
Fig3_2
. . x=1 OR 2の“=”は代入演算子で、この式はFig. 3.2(b)の２分木に構成されねばならない。従って、論理演算子の内部状態となる順位は代入演算子より下位である。論理演算子は２項演算式をオペランドに持つ場合もあるから演算子“+”よりも上位である。このとき、x=1 OR x=a+bはFig. 3.2(c)の２分木になるがこれは正しくない。論理演算の２つのオペランドはタイプが同じでなければならない決まりがあるからである。同図(c)の“OR”を内部状態とするプロセッサはx=a+bのxをポート２へ転送した後、ポート０に比較演算子“=”を受けたときこれをポート２へ転送するとポート１とポート２のタイプが異なることを知り、タイプ違反のフラグをポート０に返し、ポート１にデータの変換を求めて受けた“1”、内部状態“OR”の順にポート０に返し、ポート２にデータの返還を求めて受けた“x”をポート１に転送した後、比較演算子“=”を内部状態にセットする。内部状態が代入演算子“=”である先頭プロセッサはタイプ違反のフラグをポート２に受け、内部状態に比較演算子のフラグを付けてポート１に出力し、ポート２に返された“1”をポート１に転送し、続いてポート２に返された“OR”を内部状態にセットする。その後ポート０の入力“a+b”をポート２へ転送してFig. 3.2(d)の２分木が構成される。しかし、この数式は括弧を用いて(x=1)OR(x=a+b)と記述するのが簡明であり、このときは上記のような面倒な操作は必要なく、同図の内部状態が“OR”のプロセッサのポート１と２に“(”を内部状態とするプロセッサが存在する２分木となる。
. . このようにして簡単な演算式について種々の組合を調べていけば、ポート０の入力が内部状態となる優先権の順位及び演算式を２分木に変換する動作規則が得られる。

. .［ポート０の入力が内部状態となる優先権の順位］
1.基本順位は上位から、＝, XOR, OR, AND, NOT, 関係演算子, +と−, MOD, ¥, ×と÷, 冪乗, 単項演算子, “(”及び“f(”, 変数及び定数及び“)”で、同順位は後入優先である。
2.後入及び括弧内の“＝”は関係演算子であり、２分木ではフラグを付けて区別される。
3.“+”又は“−”が単項演算子であるとき、２分木ではフラグを付けて区別される。
4.タイプの一致を必要とする論理演算式のオペランドは括弧で括って明記する。

. .［演算式を２分木へ変換する動作規則］
1.内部状態が空ならポート０の入力を内部状態にセットする。
2.ポート０の入力が内部状態より優先権が上位なら内部状態をポート１へ出力してポート０の入力を内部状態とし、ポート１へ出力した内部状態が演算子のときはポート２へ内部状態の返還要求を出力してポート２の全入力をポート1へ転送する。
3.ポート０に内部状態の返還要求を受けたとき演算式復元の動作規則を実行して戻る。
4.ポート０の入力“(”及び“f(”をポート１又は２へ転送するか内部状態にセットしたとき、その内部状態はその後のポート０の全入力に対して上順位となる。このとき特権フラグをスタックに積む。ポート０の入力“)”をポート１又は２へ転送したとき特権フラグを１つ捨てる。
5.内部状態がポート０の入力より優先権が上位なら入力をポート２へ転送する。但し、内部状態が“(”又は“f(”で特権フラグがあるとき、“)”以外のポート０の入力はポート１へ転送し、“)”は特権が２重以上ならポート１へ、特権が１重ならポート２へ転送する。
6.内部状態が“+”又は“−”でポート０の入力をポート２へ転送したとき、ポート１へ出力していないなら内部状態は符号、即ち、単項演算子のフラグを付ける。

. .［演算式復元の動作規則］
1.内部状態が演算子でないなら内部状態をポート０へ出力して内部状態を空にする。
2.内部状態が“(”及び“f(”のときは返還要求をポート１と２へ転送し、内部状態、ポート１の全入力、ポート２の入力の順にポート０へ転送し、内部状態を空にする。
3.内部状態が単項演算子のときは返還要求をポート２へのみ転送し、内部状態、ポート２の全入力の順にポート０へ転送し、内部状態を空にする。
4.内部状態がその他の演算子のときは返還要求をポート１と２へ転送し、ポート１の全入力、内部状態、ポート２の全入力の順にポート０へ転送し、内部状態を空にする。

. . 代入式y=−a×b+c×(d−e)が２分木ポリプロセッサに入力されたとき、各プロセッサの内部状態の変化する様子をFig. 3.3に示す。プロセッサ間の枝に付記した記号はポート０に入力されたデータ又はポート１又はポート２へ出力されたデータを示す。２重円で示されたプロセッサはその内部状態がポート０の全ての入力より上位となる特権を持っていることを示す。この２分木を構成するのに要する処理時間は同図(a)でyが先頭のプロセッサに入力されたときから、数式を構成する最後のデータ“)”が同図(m)で入力されるまでの時間と、それが次々とポート２へ転送されて同図(r)で再右端のプロセッサの内部状態にセットされる迄の時間の和であり、他のプロセッサの処理はこれと平行に行われる。

Fig3_3 Fig3_3a

３.２ 演算式の超並列実行
. . ポリプロセッサの２分木に変換された演算式の実行は式の値を計算する他に、元の演算式に戻して出力する逆変換、ポーランド記法や逆ポーランド記法に変換出力する処理がある。元の演算式に戻す逆変換は前記の［演算式復元の動作規則］で簡単に変換できる。解析が複雑であるから合成は簡単になるのであり、ポリプロセッサシステムにおける解析処理と合成処理は第１節で述べた点対称的な関係にあるということが出来る。ポーランド記法への変換出力も次に示す動作規則により簡単にできる。この規則により全てのプロセッサが動作するとき、Fig. 3.1の各２分木、及び、Fig. 3.3(r)からは次のようなポーランド記法が出力される。但し、“−&”は単項演算子“−”を示す。
(a)+xa(b)+x+ab(c)++xab(d)+x×ab
(e)−+x×abc(f)×c(−de)(g)×−&ab(r)=y+×−&ab×c(−de)

［２分木をポーランド記法で出力する動作規則］
1.内部状態が空でなく演算子でないなら内部状態をポート０へ出力し内部状態を空にする｡
2.. .内部状態が単項演算子のときは、内部状態、ポート２の全入力の順にポート０へ出力し内部状態を空にする。このとき内部状態が符号のときは単項演算子を示すフラグ付きでポート０へ出力する｡
3.内部状態がその他の演算子なら、内部状態、ポート１の全入力、ポート２の全入力の順にポート０へ出力し内部状態を空にする｡

. . ポーランド記法が２分木ポリプロセッサに入力されたとき、各プロセッサの内部状態にセットする優劣順位は必要なく極めて簡単に正しくセットすることが出来る。その基本的な動作規則は、内部状態が演算子であるプロセッサはポート０の入力をポート１へ転送し、ポート１が終了すればポート２へ転送するという簡単なものである。終了の判定のために演算子を内部状態にセットしたプロセッサはカウンタというフラグに１をセットし、ポート１へ転送したものが演算子か否かでカウンタを増減し、零になったらポート１への転送を終了とする。前記のポーランド記法(a)～(g)及び(r)は各プロセッサが下記の動作を行えば２分木に変換される。

(a). .先頭のプロセッサがポート０の入力“+”を内部状態にセットし、カウンタに１をセットする。次の入力“x”をポート１へ転送してカウンタから１を減ずる。カウンタは零であるから次の入力“a”はポート２へ転送してFig. 3.1(a)が構成される。
(b)先頭のプロセッサは(a)と同様に“+x”を処理し、“+ab”はポート２へ転送する。ポート２に接続されたプロセッサはこれを(a)と同様に処理してFig. 3.1(b)が構成される。
(c)先頭のプロセッサがポート０の入力“+”を内部状態にセットし、カウンタに１をセットする。次の入力“+”をポート１へ転送してカウンタから１を減ずるが、同時にポート１のプロセッサがそのポート１と２へ転送するデータを２つ必要とするから差引きカウンタは１増加して２となる。従って、“x”と“a”はポート１へ転送し、“b”はポート２へ転送する。ポート１に接続するプロセッサは(a)と同じ処理をしてFig. 3.1(c)が構成される。
(d)２番目の演算子“+”が“×”に変わるが(b)と同じ動作によりFig. 3.1(d)が構成される。
(e)先頭のプロセッサがポート０の入力“−”を内部状態にセットし、カウンタに１をセットする。次の入力“+”をポート１へ転送して(c)と同様カウンタを１増加して２にする。次の“x”をポート１へ転送してカウンタを１減ずる。次の“×”をポート１へ転送してカウンタから１を減ずるが、同時にそれを内部状態にセットしたプロセッサがそのポート１と２へ転送するデータを２つ必要とするから差引きカウンタは１増加して２となる。従って、“a”と“b”はポート１へ転送し、“c”はポート２へ転送する。ポート１に接続するプロセッサは(d)と同じ処理をしてFig. 3.1(e)が構成される。
(f)先頭のプロセッサがポート０の入力“×”を内部状態にセットし、カウンタを１にセットする。次の入力“c”をポート１に転送してカウンタを１減じて零にする。従って、以後の入力はポート２へ転送する。ポート２に接続するプロセッサはポート０の入力を(c)と同様に処理してFig. 3.1(f)が構成される。
(g)先頭のプロセッサがポート０の入力“×”を内部状態にセットし、カウンタを１にセットする。次の入力“−&”をポート１へ転送してカウンタを１減ずるが、送ったのが単項演算子であるからそのポート２へ転送するデータを１つ必要とし、差引きカウンタの増減はない。従って、“a”はポート１へ転送してカウンタが零になり、“b”はポート２へ転送してFig. 3.1(g)が構成される。
(r)先頭のプロセッサがポート０の入力“=”を内部状態にセットし、カウンタを１にセットする。次の“y”をポート１に転送してカウンタを零にし、以後のポート０の入力をポート２へ転送する。ポート２に接続するプロセッサは“+”を内部状態にセットしてカウンタに１をセットし、“×”をポート１に転送してカウンタを２にし、単項演算子“−&”をポート１へ転送してカウンタは増減せず、“a”と“b”をポート１へ転送してカウンタを零にし、以後のポート０の入力はポート２へ転送する。ポート１に接続するプロセッサは(g)の処理をし、ポート２に接続するプロセッサは(f)の処理をしてFig. 3.3(r)が構成される。

これらの処理は次の動作規則にまとめることができる。

［ポーランド記法を２分木へ変換する動作規則］
1.内部状態が空ならポート０の入力を内部状態にセットし、それが２項演算子ならカウンタに１をセットする。
2.内部状態が単項演算子ならポート０の入力をポート２へ転送する。
3.. .内部状態が２項演算子のとき、カウンタが零ならポート０の入力をポート２へ転送する。カウンタが零でないならポート０の入力をポート１へ転送し、それが２項演算子ならカウンタを１増加し、単項演算子なら増減せず、演算子でないなら１減ずる。

. . ポーランド記法を２分木に構成するのは上記のように極めて簡単であるから、［演算式を２分木へ変換する動作規則］３の演算式復元の動作規則を実行して戻る処理を、［ポーランド記法に変換する動作規則］を実行して戻るに替えればポート２の部分木をポート１へ移動する処理は簡単になる。Fig. 3.1(e)を構成する際同図(d)が構成され、その先頭プロセッサに“−”が入力されたとき内部状態“+”をポート１へ出力し、続いてポート２に返還されるポーランド記法“+ab”をポート１に転送する。ポート１に接続するプロセッサは内部状態“x”をポート１へ出力して“+”を内部状態にセットするが、この状態を［ポーランド記法を２分木へ変換する動作規則］のポート１への出力終了として“+ab”をポート２へ転送すればよい。
. . 演算式は計算の手続きを記述する記号列であるから任意の位置で記号列を書き換えて手続きを簡単に変更できるが、ポーランド記法を変更するのは演算が複雑になると簡単ではない。積分演算の表記や括弧が示すように、ポーランド記法は計算した結果を示す記号列で演算式の値、即ち、意味を示しているからである。ポリプロセッサの２分木は１次元表記の演算式を２分木に２次元表記することにより、演算子の優先順位に関係なく２つの値が揃った演算子から演算することを可能にしている。この特性を保ったまま２次元表記の２分木を１次元に表記したものがポーランド記法であり両者は同じである。これがポーランド記法から２分木を構成するのが簡単である理由である。この故に、演算式をポリプロセッサシステムにおける外部表現、ポーランド記法を内部表現と呼び、プログラムを補助記憶装置に格納するときの記述形式としてポーランド記法を用いる。
. . 演算式を２分木に変換した後、計算を実行するためには変数を内部状態とするプロセッサに数値を与える必要があるが、このとき、演算実行動作に入る指令に続けて必要な全ての変数の値を=1x, =2a, =4b, … のようにポーランド記法で根のプロセッサに与える。これは括弧と同じポーランド記法で、演算子“(”を“=”に、一時的変数“)”を変数名に替えたものであり、代入文と区別するためである。各プロセッサは下記の［演算実行動作規則］に基づいてデータの揃ったプロセッサより演算を開始することにより並列処理が行われる。

［演算実行動作規則］
1.. .ポート０の入力が演算実行指令のとき、内部状態が“(”ならポート１へ、内部状態が代入演算子又は単項演算子ならポート２へ、内部状態がその他の演算子ならポート１と２へその指令及び続いて入力される変数の値を転送し、転送したポートに数値が返されるのを待つ。
2.内部状態が定数ならそのコピーをポート０へ出力し、ポート０に入力される変数の値は読み捨てる。
3.内部状態が変数なら、ポート０に入力された変数名が内部状態と一致しない値は読み捨て、一致する場合にはその数値を内部状態に代入すると共にコピーをポート０に出力する。
4.内部状態が“(”なら、ポート１の数値をポート０へ転送する。
5.内部状態が単項演算子ならポート２に入力された数値を内部状態で演算してポート０に出力する。
6.内部状態が代入演算子なら、ポート１に内部状態のコピーを要求し、代入演算子、ポート２の数値、ボート１の変数名のポーランド記法で全ポートへ出力する。
7.内部状態がその他の演算子なら、ポート１の数値にポート２の数値を内部状態で演算してポート０へ出力する。

. . 上記規則の６でポート０への出力は結果の外部への出力であり、ポート１への出力はポート１に接続するプロセッサの内部状態である変数に結果を代入するためである。ポート２への出力はポート２以降のプロセッサのどれかが同じ変数を内部状態としている場合にそれに計算結果を代入するためである。これにより、x=x+1の計算は初期値を与えた後は演算指令を与える毎にxの値を１づつ増加する。
. . ポーランド記法は内部状態、ポート１、ポート２の順に出力するが、内部状態の出力を最後にして、ポート１、ポート２、内部状態の順にすれば逆ポーランド記法を出力する。

［２分木を逆ポーランド記法で出力する動作規則］
1.. .２分木をポーランド記法で出力する動作規則］において、ポート０への出力順序を、ポート１の全入力、ポート２の全入力、内部状態に変更した規則。

. . Fig. 3.1の各２分木、及び、Fig. 3.3(r)から逆ポーランド記法で出力すると下記のようになる。
(a)xa+(b)xab++(c)xa+b+(d)xab×+
(e)xab×+c−(f)cde−)(×(g)a−&b×(r)ya−&b×cde−)(×+=

これらの逆ポーランド記法が２分木ポリプロセッサに入力されたとき、２分木に構成する処理はポーランド記法と同様に簡単である。その過程をFig. 3.4～Fig. 3.6に示す。

Fig3_4
(a). .“x”を内部状態にセットし、次の入力“a”で“x”をポート１へ出力して“a”を内部状態にセットし、次の入力“+”で“a”をポート２へ出力して“+”を内部状態にセットする。
(b)“xab”迄の入力で、(a)の場合と同様にして先頭のプロセッサの内部状態が“b”に変わった状態になる。次の入力“+”で“b”をポート２へ出力して“+”を内部状態にセットし、その次の入力“+”で内部状態の“+”をポート２へ出力して入力の“+”を内部状態にセットする。ポート２に接続するプロセッサは“b”の入力で内部状態“a”をポート１へ出力して“b”を内部状態にセットし、“+”の入力で内部状態“b”をポート２へ出力して入力を内部状態にセットする。これが基本的な動作である。
(c)“xa+”迄の入力でFig. 3.4(a)の２分木が完成する。この状態で先頭のプロセッサに“b”が入力されるとポート２に内部状態の返還を要求してポート２の入力“a”をポート１へ転送し、内部状態の“+”をポート１へ出力して“b”を内部状態にセットする。次の“+”の入力で内部状態“b”をポート２へ出力して“+”を内部状態にセットする。ポート１に接続するプロセッサは(a)と同じ動作で部分木の移動を完成する。
(d)最初の演算子が“×”である点が(b)と異なるが、処理は(b)と全く同じ。
(e)“xab×+”が２分木の構成を(d)により完成され、先頭のプロセッサに“c”が入力されるとポート２に内部状態の変換を要求し、逆ポーランド記法で返還された“ab×”と内部状態“+”をポート１へ転送して“c”を内部状態にセットする。ポート２に接続するプロセッサはポート０の入力を(d)と同様に処理して部分木の移動を完成し、先頭のプロセッサはポート０の入力“−”により内部状態“c”をポート２へ出力して入力を内部状態にセットする。
(f)(b)と同様にして“cde−”迄が２分木に構成されるがこの２分木は完全でない。従って、次の入力“)”は変数であるが先頭のプロセッサは基本動作を続け、内部状態“−”をポート２へ出力して入力を内部状態にセットする。次の入力“(”で内部状態“)”をポート２に出力して入力を内部状態にセットする。ポート２に接続するプロセッサはポート０に変数“)”を受けるが、このプロセッサ以降の２分木は完全であるからこれをポート１へ移動する動作を行って“)”を内部状態にセットする。先頭のプロセッサは次の入力“×”で内部状態“(”をポート２へ出力して入力を内部状態にセットする。ポート２に接続するプロセッサは“)”をポート２へ出力して“(”を内部状態にセットする。
(g)ポート０の入力“a”を内部状態にセットし、次の単項演算子“−&”の入力で内部状態をポート２に出力して入力を内部状態にセットする。この状態は単項演算の２分木として完全である。従って、次の入力“b”によりポート２に内部状態の返還を求めてポート１へ転送し、続いて内部状態“−&”を出力して“b”を内部状態にセットする。次の入力“×”で内部状態“b”をポート２へ出力して入力を内部状態にセットする。
Fig3_5
(r). .“ya−&”の入力によりFig. 3.6の最初の２分木が構成されるが、これは単項演算の２分木として完全でないので次の入力“b”によりこの２分木をポート１へ移動する操作は起こらず、基本動作により２番目の２分木が構成される。次に“×”の入力で先頭のプロセッサは内部状態“b”をポート２へ出力して入力を内部状態にセットする。ポート２に接続するプロセッサは“b”をポート０に受けるが、このプロセッサ以降の２分木は単項演算の２分木として完全であるのでこの２分木をポート１へ移動して“b”を内部状態にセットして３番目の２分木が構成される。この２分木は完全でないので次の入力“c”により基本動作が行われ４番目の２分木が構成される。次の入力“d”により先頭のプロセッサがポート２へ出力した“c”をポート０に受けたプロセッサは５番目に示すようにそれ以降の２分木をポート１へ移動する。次の入力“e”により６番目の２分木が構成された後は、先頭、及び、そのポート２に接続するプロセッサは基本動作により入力をポート２へ転送し、“c”が内部状態であるプロセッサ以降がFig. 3.5(f)の動作をすることにより２分木を完成する。
Fig3_6
. . これら２分木を構成するための動作規則において演算子に続いて変数又は定数がポート０に入力されたとき、そのプロセッサ以降の２分木をポート１へ移動するか否かを判断する必要がある。その判断はポーランド記法の場合のようにカウンタを使用して行うことが出来るが、ポーランド記法とは全く逆に、内部状態の変数又は定数をポート１又は２へ出力するか部分２分木をポート１へ移動したとき増加し、演算子を内部状態にセットしたとき減ずる。これらの動作規則は以下のようになる。

［逆ポーランド記法を２分木に構成する動作規則］
1.. .内部状態が空ならポート０の入力を内部状態にセットしてカウンタを零にする。
2.内部状態が変数又は定数のとき、ポート０の入力が単項演算子ならポート２へ、そうでないときはカウンタが零ならポート１へ、零でないならポート２へ内部状態を出力してカウンタを１増加し、ポート０の入力を内部状態にセットしてそれが単項演算子なら１、２項演算子なら２、カウンタを減ずる。
3.内部状態が演算子のとき、カウンタが零でないなら内部状態をポート２へ出力してカウンタを１増加し、ポート０の入力を内部状態にセットしてそれが単項演算子なら１、２項演算子なら２、カウンタを減ずる。
4.内部状態が演算子でカウンタが零のとき、ポート２へ内部状態の返還を要求し、返還された全データをポート１へ転送し、内部状態をポート１へ出力してカウンタを１増加し、ポート０の入力を内部状態にセットする。
5.ポート０の入力が内部状態の返還要求のとき、内部状態が２項演算子ならポート１と２へ、単項演算子ならポート２へ返還要求を転送し、内部状態が変数又は定数なら転送せずに、何れも［２分木を逆ポーランド記法で出力する動作規則］を実行する。
(注)“(”は演算子、“)”は変数である。規則４でポート０の入力が演算子ならその逆ポーランド記法は誤りである。

. . ポーランド記法を２分木に変換するには演算子を内部状態にセットしたプロセッサがそのポート０からポート１へ転送すべき入力数をカウントし、転送したものが演算子か否かでカウンタを増減し、カウンタが零になれば残りはポート２へ転送する。従って、一度セットされた内部状態は変わらない。一方、逆ポーランド記法を２分木に変換するにはポート０の入力を一度内部状態にセットして次の入力でカウンタが零ならポート１へ、そうでないならポート２へ送り出す。カウンタは内部状態をポート１又は２へ送り出したとき増加し、演算子を内部状態にセットしたとき減ずる。又、カウンタが零のときポート０に変数又は定数が入力されるとそのプロセッサを根とする部分木はポート１へ移動される。このように両記法の処理は全く反対であり、著者はこれを点対称的という。
. . 各プロセッサがどちらの記法であるかの指標を受けて動作規則を切り替えて処理することができるが、先頭のプロセッサがどちらの記法であるか判断し、ポーランド記法はポート１へ転送し、逆ポーランド記法はポート２へ転送すれば他のプロセッサはその判断や動作規則の切り替えは必要がなくなる。又、２項演算等の演算式はポート１へ転送すると、人間の脳が英語は左脳で処理し、日本語は右脳で処理する理由が明らかにされる。英文“x is a.”を記号化したものが代入演算x=aであり、命令文“add x a.”を記号化したものがポーランド記法+xaであり、“x is added a.”を記号化したものが２項演算式x+aである。日本語では逆ポーランド記法xa=を「xはaである。」xa+を「xにaを加える。」と表す。右脳は左半身を制御し、左脳は右半身を制御する。人間の基本的な運動である歩く、走るという動作において右腕を前に振れば左腕は後ろに振り、右足は後ろに蹴って左足は前に出す。即ち、右脳と左脳は基本的に反対に機能するように出来ているから英語は左脳、日本語は右脳で処理するのであり、脳はポリプロセッサによるポリプロセッシングで機能している。

３.３ プログラムの超並列処理
. . ポリプロセッサシステムではBASICのような自然言語に準じた言語により逐次処理的に記述されたプログラムを並列処理し、特別な並列化プログラムのようなものは使用しない。著者は自然言語によるプログラムを理想と考えるからである。プログラムを構成する代入文やその他の文に変数が使われている限り、その変数と無関係な代入文以外は同時に処理することはできない。両方の代入文の互いに関係しない部分を同時に処理する部分的並列処理は可能であるが、それについては後で述べ、先ず、プログラムを構成する文同士は逐次に処理し、文内部を並列処理する場合について述べる。
. . ポリプロセッサシステムではプログラムは各プロセッサの持つ局所RAMに格納される。各プロセッサのプログラムカウンタは同一の値を持ち、各局所RAMのプログラム領域の先頭番地からの相対番地を表す。プログラムを構成する代入文が入力されて２分木に変換されたとき、各プロセッサはその内部状態をプログラムカウンタの示す番地に格納してカウンタをインクリメントする。このとき、内部状態が空のプロセッサは空を格納する。プログラムカウンタの値は文番号に相当するが、プログラムに文番号や行番号、それらを示すラベルは使用しないし、それらを必要とするGOTO文も使用しない。本システムでは空を格納されたRAM領域が沢山生ずるが、これらは無駄ではなく、システムが正常に動作するために必要な空白である。脳には使用されていない脳細胞が沢山存在するといわれるが、それらは上記の空白と同じ理由もあり、全てが使用されていないと断定するのは正しくない。
. . 代入文x=aとy=a×bが２分木ポリプロセッサに入力された状態をFig. 3.7(a)に示す。各プロセッサのRAMが円で示され、各プロセッサのプログラムカウンタ=0のRAMの内容をプロセッサの結合状態で表したものがx=aであり、プログラムカウンタ=1のRAMの内容がy=a×bを表している。このようにして代入文を構成する演算子や変数は各プロセッサの局所RAMに分散して格納される。プログラムでは各文はコロン又は改行コードで結合されているが、同図の先頭プロセッサの前にそれらを内部状態とするプロセッサが単項演算子の形に接続されるだけであるので省略している。プログラムを実行するとき局所RAMのプログラムカウンタの示す番地の内容が内部状態に同時に読み出されて２分木を構成し、データの揃った部分より並列に演算される。プログラムカウンタの示す番地がそのときの各プロセッサの内部状態であるとしてもよい。

Fig3_7
. . 各プロセッサは局所RAMのプログラム領域に格納されている変数とその値との対応表を作成し、プログラムカウンタの示す変数が読み出されたとき対応表よりその値を得る。２分木の演算が終了し、＝を内部状態とするプロセッサが左辺の変数名と計算結果をポート１と２へ出力したとき、全てのプロセッサはそれをポート１と２へ転送すると共に自分の持つ対応表に同じ変数があれば値を更新する。
. . 制御文も同様に２分木に変換処理する。文をA, B, C, ……で表すと、if文は一般的に、
if A then{B:C:D:……} else{P:Q:R:……}
と記述できるが、この文はプログラムカウンタの値を処理する文と変数の値を処理する文に分けて下記に示すように記述されているものとして２分木に構成される。先頭のプロセッサは“if”を内部状態にセットし、次の演算式Aをポート１へ転送し、ポート２へ“then”を転送する。演算式Aはポート１に接続するプロセッサ以降に２分木に構成され、“then”を内部状態にセットしたプロセッサはポート１へ変数PC1を、ポート２へ“else”を出力する。ポート２のプロセッサは“else”を内部状態にセットし、変数PC2をポート１へ、変数PC3をポート２へ出力し、それらはそれぞれのプロセッサの内部状態にセットされる。従って、if文(1)はFig. 3.7(b)の２分木に構成され、これらの内部状態はif文の読込みが終了するまで保留状態に置かれる。
if A then PC1 else PC2,PC3(1)
{B:C:D: ……}(2)
{P:Q:R: ……}(3)
次に(2)が入力されるが、中括弧“{”と“}”及び文B, C, D, ……の関係は２分木に構成されないので、各文はFig. 3.7(a)に示すように先頭のプロセッサの内部状態から２分木に構成され、各内部状態はそれぞれのプロセッサのRAMのプログラムカウンタの指す位置に格納される。中括弧“{”と“}”も先頭のプロセッサのRAMに(2)に示す順に格納される。保留内部状態が“if”であるプロセッサは中括弧“}”をRAMに格納した後、ポート２に“then”の終了を通知し、保留内部状態が“then”であるプロセッサはポート１に“}”の次のプログラムカウンタの値をPC1にセットするよう指令する。保留内部状態が“if”のプロセッサは次に“else”が入力されると“else”の開始をポート２に通知、保留内部状態が“then”であるプロセッサはそれをポート２へ転送し、保留内部状態が“else”であるプロセッサはポート２に“else”の次のプログラムカウンタの値をPC3にセットするよう指令する。次に(3)が入力され、保留内部状態が“if”のプロセッサは“}”をRAMに格納した後ポート２に“else”の終了を通知する。保留内部状態が“then”のプロセッサはそれをポート２へ転送すると共にポート１にPC1を“}”の次のプログラムカウンタの値で更新するよう指令する。保留内部状態が“else”であるプロセッサはポート１に“}”の次のプログラムカウンタの値をPC2にセットするよう指令し、if文の読み込みを完了する。
. . If文を実行するとき、“if”を内部状態とするプロセッサはAの演算結果を要求し、そのフラグをポート２へ転送する。“then”を内部状態とするプロセッサはフラグが真ならポート１に内部状態のコピーを要求して受けたPC1をスタックに積むと共に全てのポートにその指令を送る。それを受けたプロセッサは受けたポート以外のポートにその指令を送ると共にPC1をスタックに積む。その後、プログラムカウンタは1加算されて全てのプロセッサは上記の(2)の実行に移る。“{”はノーオペレーションでB:C:D: ……を実行した後“}”で全てのプロセッサにスタックのPC1をプログラムカウンタにポップする指令が出され、“else”の終了“}”の次へ移る。演算Aの結果のフラグが偽なら“then”を内部状態とするプロセッサはポート２へそれを転送し、“else”を内部状態とするプロセッサはポート１と２に内部状態のコピーを要求し、受けたPC2をスタックに積みPC3をプログラムカウンタにロードする指令を全てのポートに出力すると共に自らもそれを実行する。その結果、全てのプロセッサは上記(3)を実行し、“}”でスタックのPC2をプログラムカウンタにポップして“else”の終了“}”の次へ移る。
. . If文に“else”がないときは通常は次の文との区切り記号“:”が読込まれるので、保留内部状態が“if”のプロセッサは“noelse”をポート２へ出力し、保留内部状態が“then”のプロセッサはそれをポート２へ転送し、保留内部状態が“else”のプロセッサはそれを“noelse”に変え、ポート２にPC3に“:”の次のプログラムカウンタの値をセットするよう指令し、if文の読み込みを完了する。従って、PC2には値がセットされないし、PC1の値の更新もされない。このif文が実行されるとき、演算Aの結果が真なら上記(2)が実行されて(2)の終了の“}”の次へ移るが、偽の場合は、内部状態が“noelse”のプロセッサはPC2は使用せず、PC3をプログラムカウンタにセットする指令を全てのプロセッサに送る。従って、(2)の次の“:”の次へ移り、通常は真でも偽でも同じ所へ合流する。しかし、繰返しループの中に使われた場合は偽ならループを脱出する。
. . 繰返し文はrepeat{A:B:C: ……}と記述し、“repeat{”, Aの２分木, Bの２分木, Cの２分木, ……, “}”の順にプログラムカウンタを１づつ増加してRAMに格納される。繰返し文を実行するとき、“repeat{”を内部状態とするプロセッサはそのときのプログラムカウンタの値をスタックに積み、プログラムカウンタに１を加える指令を全てのプロセッサに送る。従って、２分木A, B, C, ……が順に実行される。最後に“}”を内部状態としたプロセッサはスタックのカウンタ値をプログラムカウンタにポップする指令を全てのプロセッサに送り、プログラムの制御は“repeat{”に戻る。この繰返しは無限に続くので“}”の前にelseの無いif文を置くことで繰返しから脱出する。
. . プログラミングを初めて習った者が奇異に感ずるのはGOTO文と副プログラムである。人間の思考の過程にGOTO文は通常は存在しない。人間の思考を文章にした論文や小説で「何頁の何行目へ行け」というような文を書くことは無い。本文中に記述してある部分を「上記のように」とか「何処何処に記述したように」と参照するが、その参照される部分を本文とは別の場所にラベルをつけてまとめて記述することは通常はしない。そのような論文や小説は書くのもややこしいし、そのようなものがあったとしてもややこしくて読む気にならないであろう。従って、本プログラミングではGOTO文は使用しないし、副プログラムは本文中の最初に使用する場所で定義し、それを必要とする他の場所からも参照できるものとする。但し、組み込み関数のようなシステムが用意する副プログラムは本文の外で定義される。これは他の文献等を参照する場合に相当する。
. . 副プログラムの定義は、name{A:B:C: ……}と記述する。これを読込むとき、“name{”を内部状態にセットしたプロセッサは“name{”とそのときのプログラムカウンタの値を対応表に書き込んでポート２に変数REを出力し、ポート２のプロセッサはそれを内部状態にセットする。変数REには最後の“}”が読込まれたときその次のプログラムカウンタ値が代入される。この副プログラムが定義位置で実行されるとき、“name{”を内部状態とするプロセッサはポート２に内部状態のコピーを要求し、受けたREの値をスタックに積む指令を全てのプロセッサに送る。最後の“}”を内部状態にセットしたプロセッサはスタックのカウンタ値をプログラムカウンタにポップする指令を全てのプロセッサに送る。従って、プログラムカウンタは“}”の次へ移る。この副プログラムを他の場所から使用するには単に“name”と記述する。これを実行するとき、“name”を内部状態とするプロセッサはその次のカウンタ値をスタックに積み、対応表の“name{”に対応するカウンタ値に１を加えた値をプログラムカウンタにセットする指令を全てのプロセッサに送る。従って、副プログラムは２分木A, B, C, ……と実行し、“}”によりcallした場所の次へ戻る。
. . これらによりプログラムを作る際に注意することは流れ線が交差するフローチャートを書いてはならないことである。又、if文が“then”と“else”の両方を持つときは両者の流れ線は同一点に合流しなければならない。従来のプログラミングでは流れ線が交差することを禁じていないし、if文も上記の制限がないからGOTO文を必要とする。しかし、これらのフローチャートは上記の条件を満足するフローチャートに書き換えることが出来る。フローチャートFig. 3.8(a)はGOTO文が無いと、条件Aが真の場合と偽の場合の両方に繰返し文の終了を記述する必要があるので正しくない。これは偽のときの処理の一部しか真のときの処理と合流しないことに起因する。このフローチャートは(b)に書き換えれば上記の条件を満足し、下記のように記述できる。条件Cが真のとき実行すべき文は繰返しの終了処理“}”のみであるが、if文の解析法を上記に限定する限り実行文の無い括弧“{ }”が必要である。
…… :repeat{repeat{if A then{B}}:if C then{ }}: ……
Fig3_8
フローチャート(c)はループが交差するから正しくない。実行文Aを２箇所に使用して(d)に書き換えれば上記の条件を満たし次のように記述できる。
…… :A:repeat{if B then{if C then{D} else{A}}}: ……
. . 本節に於ける並列処理は代入文等の数式を並列計算したり、入出力文の変数並びの各変数の２進化、10進化等の変換を変数毎に別のプロセッサで処理したりする並列処理であり、文と文の関係は逐次に処理する。従って、上記に述べたGOTO文を使用しないプログラミング技法は従来の逐次処理プログラミングにも適用できる。BASICではWHILE文を無限ループとして使用して(b)を次のように記述できる。
WHILE 2>0:WHILE A:B:WEND:IF C THEN WEND ELSE ……
BASICではIF文のTHENの処理とELSEの処理の終わりが同一点に合流するためには改行しなければならないので、(d)は次のように２行に記述しなければならない。
A:WHILE B:IF C THEN D ELSE A
WEND: ……
これらの点に注意すればBASICではGOTO文は必要が無い。第２章に示した各プログラムはGOTOを使用しないBASICで書かれている。
. . アセンブリ言語でも上記のような条件処理命令と繰返し命令が備わっていればJUMP命令は必要が無い。JUMP命令を使用するとプログラムは幾らでも複雑にすることが出来、従来、プログラムの解読を困難にするために不必要なJUMP命令が使用されることもしばしばある。JUMP命令やGOTO文を禁止するとアルゴリズムが同じであれば誰が書いても殆ど同じプログラムとなり、プログラムが簡明となる利点がある。高級プログラム言語にGOTO文は設けるべきでない。

３.４ プログラム全体を２分木に構成する超並列処理
. . 演算式 a+b の２分木で内部状態が＋のプロセッサはポート１の入力aにポート２の入力bを加えるが、これはaをレジスタにロードしてbを加えるのであり、更に一般的に記述すればポート１の入力を処理してポート２の入力を処理することである。従って、２つの代入文aとbをこの順に逐次処理するとき、節のプロセッサのポート１に接続する２分木にaを変換し、ポート２に接続する２分木にbを変換すればよい。節のプロセッサの内部状態には代入文を接続する演算子“:”を入れる。この２つの代入文が他方の左辺の変数を参照していなければ両者は並列処理ができるが、２分木ポリプロセッサでは両者を演算子“:”により１本の２分木に構成すれば自動的に並列処理される。同様に、プログラム全体を１本の２分木に構成すればプログラム内に散在する並列処理可能な部分は自動的に並列処理される。当然に、このプログラムにはGOTO文は存在しない。しかし、条件により処理を変えたり、繰り返したりする操作が必要であり、それを２分木で表す必要がある。そのために、プログラムカウンタの制御を図で表したフローチャートをプログラムと考え、その２分木表現及び文表現の方法を示す。但し、フローチャートは前節で述べた条件を満たすように書かれなければならない。
. . 任意のプログラムはFig. 3.9の３つの型のフローチャートの組み合わせで表すことができる。記号a, b, c, ・・・ は代入文、関係式、入出力文等の２分木に表すことのできる文、及び、それらを３つの型の一つに組み合わせたものである。Ⅰ型は逐次処理であり、Ⅱ型は真偽により２つの処理を選択し、Ⅲ型は真偽によりループした処理とループよりの脱出を選択する。条件の真偽と処理の組み合わせはこれ以外にないことは明らかである。但し、Ⅱ型、Ⅲ型には処理b又はcが存在しない場合もあるが、その場合は無操作という処理があるものと考えてこれらの型に含める。各型は矢印の右に示す２分木で表し、その下に示した２項演算式の形式で文として表記できる。

Fig3_9
. . プロセッサの内部状態a, b, cは代入文等の実行文であり、数式の変数や定数に相当し、プログラムの読込み中は文のまま其々のプロセッサのRAMに格納される。プログラムの読込みが終了したとき、その指令によりRAMから読出し、ポート０の入力とみなして第１節で述べたように２分木に構成する。プログラムの２分木ではこれら実行文の２分木の表示は省略し、内部状態としてのみ表示する。記号“:”で表した内部状態は実行文の実行順序を制御する演算子で“;”を使用してもよい。改行記号も同じ演算子とする。
. . Ⅰ型はa:b:cと記述し、この順に逐次に実行する。各実行文は複数の実行文が“{ }”で括られたものである場合もあり、Ⅱ型、Ⅲ型である場合もある。Ⅰ型の記述を２分木に構成するために演算子“:”が内部状態にセットされる優先順位は実行文より上位で、内部状態が演算子“:”であるとき再び“:”がポート０に入力された場合は先入優先である。後入優先でも２分木は構成できるが実行時のデータ転送制御が非常に複雑になり好ましくない。各プロセッサの動作規則は、ポート０の入力が内部状態より優位なら内部状態をポート１へ出力して入力を内部状態にセットし、内部状態が優位なら入力をポート２へ転送する。
. . Ⅱ型は{aTbFc}と記述し、aの演算結果が真ならbを実行し、偽ならcを実行する処理を処理の流れを制御する演算子TとFにより２項演算式の形式で記述し、“{ }”で全体を１つの実行文として記述したものである。“{ }”は数式における“( )”と同様に“{”は処理の流れを制御する演算子で“}”は終了処理をする実行文であり、括弧内の２項演算式形式の実行文とはポーランド記法の関係にある。この関係を２項演算式の関係に直すと}{aTbFcとなるが、この“}{”をIFに置き換えたものがIF文である。BASICではこれをIF a THEN b ELSE cと記述する。本システムでもIF文で記述してもよい。実行文b, cが複数の実行文を“:”で結合したものであるときはそれを“{ }”で括る。
. . プログラム中で{aTbFc}は他の実行文と“:”で結合されるから、２分木に構成される際に内部状態にセットされる優先順位は“:”が“{”より優位である。演算子Fは演算子Tより優位で演算子Tが先に入力されて内部状態にセットされ、優位な演算子Fの入力によりポート１に出力されるが、数式の場合の動作規則と同様に、ポート２に内部状態の変換を要求して返されたものをすべてポート２へ転送してから演算子Fを内部状態にセットする。実行文b, cは複数の実行文が“{ }”で括られている場合もあるから両演算子は“{”より優位である。ポート０に入力された演算子“{”をポート１又は２へ転送するか内部状態にセットするとそれらのプロセッサの内部状態は演算子“(”と同様に特権を生じ、特権がある際のデータの転送も“(”と同様である。実行文“}”は“)”と同様に“{”の特権を解除し、“)”と同様に転送される。
. . Ⅲ型はR{c:{aTb}}と記述し、cを実行し、aの演算結果が真ならbを実行して再びcの実行へ戻るが、偽なら繰返しを終了する。繰返しを終了するためには偽の場合の処理を示す演算子Fを使用することは出来ない。この条件文もⅡ型と同様にIF文で記述することが出来る。この繰返し文を２分木に変換するとき、演算子“R{”が内部状態にセットされる優先順位は“{”と同順位で、内部状態に特権を生ずる。その処理は“{”と同様である。その特権は対応する“}”により解除される。副プログラムはⅢ型に含まれる。
. . 内部状態が演算子でポート０の入力がそれより優位のためポート１へ出力されるときポート２に接続されているプロセッサはそれ以降のプロセッサの内部状態を“:”で結合された元のプログラム記述に復元してポート０に返さなければならない。その動作規則は演算式の復元の場合と同様で、ポート１の入力、内部状態、ポート２の入力の順にポート０へ出力すればよい。但し、内部状態が“{”や“R{”のときは内部状態、ポート１の入力、ポート２の入力の順になる。Fig. 3.9の各型の２分木からこの規則により出力すれば２分木の下に示した記述になる。又、その出力を図に描けば各２分木の左に示したフローチャートになる。従って、プログラム全体を２分木に構成した各プロセッサがこの動作規則により内部状態を出力すればプログラムが出力され、出力を順に流れ線で結合した図を描けばフローチャートが得られる。このフローチャートは流れ線が交差することなく、前記のIF文の条件も満たし、GOTOを使用しない通常のコンピュータのプログラムとすることが出来る。
. . プログラム全体を２分木に構成する例としてn!を求めるフローチャートをFig. 3.10に示す。点線で囲われたブロックAはⅠ型、BはⅢ型、これらとブロックCはⅠ型に結合されているから、次のようにプログラムに表すことが出来る。
input n:k=0:m=1:R{{k<n T{k=k+1:m=m×k}}}:print m
これを上記に述べた動作規則により２分木プロセッサの内部状態にセットしていけば同図(d)の２分木が構成される。この２分木はフローチャートの各ブロックをFig. 3.9の各型の２分木に表し、“:”を内部状態とするプロセッサで結合して構成し、図示することができる。これを２分木チャートと呼ぶ。この２分木チャートの根のプロセッサより順に、“R{” 又は“{”が内部状態の場合は内部状態、ポート１、ポート２の順、それ以外はポート１、内部状態、ポート２の順に書き出せば上記のプログラムを得る。又、フローチャートを書かずに直接２分木チャートを書くことも簡単であり、通常のプログラミングにおいてもGOTOのないプログラムを書くためには直接２分木チャートを書くのがよい。
Fig3_10
. . フローチャートによるプログラミングの際に先ず概略のフローチャートを書き、順次詳細なフローチャートを書いていく手法が用いられる。直接２分木チャートを書く場合も同様の手法を用いるのがよい。上記の例は簡単であるので直接詳細な２分木チャート(d)を書くことが出来るが、フローチャートに示すブロックに纏めて概略のフローチャートとみなしてこの手法について述べる。先ず、n!を計算して結果を印刷するという二つの処理からなるから(a)の２分木チャートが書ける。そのポート１の処理は前処理Aと繰返し計算Bを“:”で結合した２分木に表せるので(b)の２分木チャートが書ける。このとき図のように“{”と“}”を挿入しなければならない。これはプログラムを２分木プロセッサシステムに入力するとき、“:”が内部状態にセットされる優先順位を先入優先としたことによるもので、２分木チャートの何処においてもそのポート１の処理を二つ以上に分けるときは必要である。２分木(b)のCはプリント文、Bは２分木(d)の繰返し処理と同じであり、Aは三つの実行文を“:”で結合した２分木となるから“{”と“}”を挿入する必要があり、結局(c)の２分木が得られる。一方、ポート２の処理を分けるときは"{"と"}"を挿入する必要がない。従って、前処理Aとその他の処理の２分木を書き、その他の処理を繰返し計算Bと出力処理Cの２分木に分ければ２分木(d)が得られる。
. . ２分木(c)と２分木(d)はプリント文やインプット文の位置を見れば明らかなように２分木としては全く異なっている。しかし、プログラムとしては全く同じである。２分木(c)の根から原則としてポート１、内部状態、ポート２の順、但し、内部状態が“{”と“R{”の場合は内部状態、ポート１、ポート２の順に書き出せば下記のプログラムを得る。
{{input n:k=0:m=1}:R{{k<n T{k=k+1:m=m×k}}}}:print m
これと２分木(d)のプログラムとの違いは先頭にある２つの“{”と其々に対応する“}”があることだけであり、これらを取り除いてもプログラムも実行結果も変わることはない。しかし、２分木プロセッサシステムに読込まれるとき(c)の２分木は構成されない。これは２つの代入文y=x+a+b+cとy=x+(a+(b+c))は代入文としても実行結果も同じであるが、２分木としては全く異なるのと同様である。
. . Fig. 3.10のフローチャートの各実行文を全く出鱈目な順序に並べ、それらの間にGOTO文を挿入して正しい順序に連結したプログラムを書くことが出来る。このプログラムは２分木プロセッサシステムでは使用できないが、従来のコンピュータでは正常に動作する。しかし、このプログラムは上記のプログラムとは異なるものであると主張するのは全く無意味である。プログラムが同じであるか否かを議論するときGOTO文を使用しないプログラムで議論しなければならない。又、A及びBとして示した部分を副プログラムに変えてもプログラムとしては同じである。
. . n!の計算はn(n−1)(n−2)……2•1と降順に掛算をして求めることが出来る。この場合のプログラムは次のように記述できる。
input n:k=n:m=1:R{{k>1 T{m=m×k:k=k−1}}}:print m
このプログラムはプロセッサを結合した形の上ではFig. 3.10(d)と全くおなじ２分木に構成される。しかし、kの初期値、kの比較式、mとkの計算式の順序、kが減算される等多くの違いがある。この違いはn!の計算の仕方(アルゴリズム)の違いによるものであり、両プログラムは異なるものである。このプログラムは次のように書くことも出来る。
input n:k=n+1:m=1:R{k=k−1:{k>1 T{m=m×k}}}:print m
このプログラムは繰返しの２分木が上のプログラムとは異なる。しかし、これはkにバイアス1を加えたためにkの減算を繰返しの先頭に持ってきただけで降順に掛算をするというアルゴリズムに変りがない。このようなプログラムを異なるプログラムとするならバイアスの値を任意に変えることにより幾らでも異なるプログラムを作ることが出来るが、これはGOTOの使用により変えるのと同様で意味がない。プログラムが異なるといえるためにはアルゴリズムに違いが無ければならない。

３.５　２分木プログラムの実行とデータ転送制御
. . ２分木ポリプロセッサにおいても２分木に構成されたプログラムの各実行文は原則的には逐次にしか実行できない。これはプログラムの基になるアルゴリズムが逐次的であるからで、さらに遡れば人間の思考過程が逐次的だからである。例えば、推論でよく使われる三段論法は大前提、小前提、結論という逐次処理で行わねばならない。一方、ある演算式を実行した結果はその後に実行されるいくつかの演算式で使用するために転送しなければならないが、その転送を並列に行うことが出来ればそれを使用する演算式は並列に実行できる。２分木ポリプロセッサの並列処理はこのようなデータ転送の並列化により自動的に行われる並列処理であって、プログラムやアルゴリズムは従来と何ら変わらない。但し、GOTOは使用できない等前節までに述べた違いはある。
. . 前節Fig. 3.10(d)の２分木に構成されたプログラムをFig. 3.11に再掲する。これを逐次に処理するには以下のようなデータ転送が必要である。
1.. .根より実行指令を送り、“:”を内部状態とするプロセッサはポート０に入力された実行指令をポート１へ転送する。
2.. .ポート１のプロセッサはnの入力処理を行う。入力処理は入力装置と無線接続する方法でも、ポート０にデータの入力要求を出し、その要求を根に転送して根に接続された入力装置より入力データを得る方法でもよい。入力処理を終えたとき、変数名nとその値及び実行完了フラグをポート０へ出力する。変数名とその値の組を変数の値と記述する。
3.. .“:”を内部状態とするプロセッサは実行完了フラグをスタックに積み、実行指令とnの値をポート２へ転送する。実行完了フラグはポート２に実行完了フラグを受けたときポート０へ出力して処理を終了する。
4.. .ポート２の内部状態が“:”のプロセッサはそのポート１へ実行指令とnの値を転送する。
5.. .ポート１のプロセッサはnの値はポート０へ返し、kに0を代入てkの値と実行完了フラグをポート０に返す。
6.. .“:”を内部状態とするプロセッサは実行完了フラグをスタックに積み、実行指令とn及びkの値をポート２へ転送する。
7.. .ポート２の内部状態が“:”のプロセッサはそのポート１へ実行指令及びnとkの値を転送する。
8.. .ポート１のプロセッサはn, kの値はポート０へ返し、mに1を代入してmの値と実行完了フラグをポート０に返す。
9.. .“:”を内部状態とするプロセッサは実行完了フラグをスタックに積み、実行指令とn, k, mの値をポート２へ転送する。
10.. .ポート２の内部状態が“:”のプロセッサ及び“R{” “{” “T”のプロセッサはそのポート１へ実行指令及びn, k, mの値を転送する。
11.. .内部状態が関係演算のプロセッサはmの値はポート０へ返し、n, kの値及び関係演算結果の真偽のフラグと実行完了フラグをポート０へ返す。
12.. .内部状態が“T”のプロセッサはポート１に返された関係演算フラグが真なら実行完了フラグと共にスタックに積み、実行指令及び返されたm, n, kの値をポート２へ転送する。
13.. .ポート２の内部状態が“{”のプロセッサ及び“:”のプロセッサはそのポート１へ実行指令及びm, n, kの値を転送する。
14.. .内部状態がkの演算であるプロセッサはm, nの値はポート０へ返し、kの演算を行った結果のkの値と実行完了フラグをポート０へ出力する。
15.. .内部状態が“:”のプロセッサは実行完了フラグをスタックに積み、m, n, kの値をポート２へ転送する。
16.. .内部状態がmの演算であるプロセッサはnの値はポート０へ返し、mの演算を行い、kの値及び演算結果のmの値と実行完了フラグをポート０へ返す。
17.. .内部状態が“:”のプロセッサはn, k, mの値とスタックにある実行完了フラグをポート０へ転送する。
18.. .内部状態が“{”のプロセッサはn, k, mの値と実行完了フラグをポート０へ転送する。
19.. .内部状態が“T”のプロセッサはスタックにある関係演算が真のフラグとn, k, mの値及びスタックにある実行完了フラグをポート０へ転送する。
20.. .内部状態が“{”のプロセッサはポート１の入力をポート０へ転送する。
21.. .内部状態が“R{”のプロセッサは関係演算フラグが真である間、実行指令とn, k, mの値をポート１へ転送する操作を繰り返す。
22.. .内部状態が“T”のプロセッサは関係演算が偽であるフラグをポート１に受けたとき、ポート２へのデータ転送は行わずに、偽のフラグとn, k, mの値及び実行完了フラグをポート０へ返す。
23.. .内部状態が“R{”のプロセッサはn, k, mの値と実行完了フラグをポート０へ返す。
24.. .内部状態が“:”のプロセッサは実行完了フラグをスタックに積んで実行指令とn, k, mの値をポート２へ転送する。
25.. .内部状態がプリント実行であるプロセッサはn, k, mの値及びmの値のプリント指令と実行完了フラグをポート０へ返す。これらは次々とポート０へ転送される。プリント指令は印刷装置へ無線接続で転送することも出来る。
26.. .先頭の内部状態が“:”のプロセッサはmの値のプリント指令を印刷装置へ転送して終了する。
Fig3_11 . . 上記の10, 12において、内部状態が“T”のプロセッサは実行指令とn, k, mの値をポート１と２へ同時に転送することが出来る。何故ならポート１ではこれらの値が更新されることはないし、新たな変数の値が設定されることもないからである。このときポート１の関係演算とポート２の演算は平行して行われる。内部状態が“T”のプロセッサはポート１に受けたフラグが真ならポート２から返されたn, k, mの値をポート０へ転送するが、フラグが偽ならポート２へキャンセル指令を送り、ポート２の完了を待つことなくポート１に返されたn, k, mの値をポート０へ転送する。
. . Fig. 3.9のⅡ型の“F”演算子を持つ条件文の場合もこの並列処理ができる。内部状態が“T”のプロセッサのポート２における演算結果と、内部状態が“F”のプロセッサのポート２における演算結果は互いに干渉することなく、どちらか一方が有効だからである。但し、実行することで結果が確定してしまう入力や印刷は関係演算の真偽が確定するまで保留されねばならない。これは“F”演算子を持たない条件文でも同じである。内部状態が“F”及び“T”であるプロセッサはそのポート１と２へ同時に同じ変数の値を転送する。内部状態が“T”のプロセッサはポート１に返された関係演算フラグが真なら、そのフラグとポート２に返された変数の値をポート０へ転送し、内部状態が“F”のプロセッサはポート２へキャンセル指令を送り、ポート２の完了を待つことなくポート１に受けた真のフラグと変数の値をポート０へ転送する。関係演算フラグが偽なら、内部状態が“T”のプロセッサはポート２へキャンセル指令を送り、ポート２の完了を待つことなくポート１に受けた偽のフラグと変数の値をポート０へ転送するが、内部状態が“F”のプロセッサはポート１に受けた偽のフラグとポート２に受けた変数の値をポート０へ転送する。
. . 上記においては、実行指令は先ずポート１へ転送し、その実行完了フラグを受けてからポート２へ転送する手順を守ったが、この手順を廃止することが出来る。全てのプロセッサはポート０に実行指令を受けたとき、ポート１と２へその指令を転送する。これによりnの入力、k=0, m=1の演算は平行して行われる。しかし、k<n, k=k+1, m=m×kの演算は実行指令を受けても変数の値が確定しないのでそれらが転送されるまで保留される。通常、入力処理は演算より時間がかかるが、それにより変数の値の転送順序がプログラムに記述された処理順序と変わっても結果に影響はない。しかし、ポート０に受けた変数の値はポート１へ転送し、ポート１に返された変数の値をポート２へ転送する手順は守らねばならない。但し、ポート０に変数の値を受けたとき、既にポート１に実行完了フラグを受けているときは、ポート１ではそれらの変数の値を必要としていないのであるから直接ポート２へ転送してよい。内部状態が“{”や“R{”のプロセッサはポート１より先にポート２から実行完了フラグを受けるが、この順序も任意であり、両ポートに実行完了フラグを受けたときその１つをポート０に転送すればよい。
. . 従来のコンピュータではプログラムを格納する領域と変数の値を格納する領域は区別され、プログラムの実行は変数の値を格納領域から取り出し演算して格納領域へ戻すことにより行われる。２分木ポリプロセッサでは通常、変数の値は特別な領域に格納されるのではなく、２分木プログラムの実行が完了するまでの間、その中を転送されている。即ち、２分木プログラムの実行はデータフロー型超並列演算である。個々の変数の値は、プログラムの実行の完了により構成される製品、即ち、変数の値の集合の構成部品素材であり、各プロセッサは２分木ベルトコンベアに乗せて運ばれてくる部品素材を演算加工してベルトコンベアに戻すマイクロロボットに相当する。
. . 大きな配列を処理するプログラムでは膨大な量の変数の値がそれを必要としない部分にも流れることが起こる。勿論、それはポート１又は２に実行完了フラグを受けた後はそのポートへの転送は阻止されるが、さらに効率良く不要な部分へ変数の値が転送されるのを防ぐことが出来る。
［内部状態が“T”及び“F”以外のプロセッサの基本転送規則］
1.. .内部状態が実行文であるプロセッサは実行指令を受けたとき、演算結果で更新する変数名、演算に必要な変数値の要求と要求完了フラグをポート０に出力する。
2.. .ポート０に接続するプロセッサはそのポート１と２からの更新変数名と変数値要求をポート毎に分けて保存し、ポート１と２の更新変数名(重複するものは１つのみ)のコピー、ポート１の変数値要求のコピー、及びポート２の要求からポート１の更新変数を除いたコピー(重複するものは１つのみ)と要求完了フラグをポート０へ出力する。
3.. .ポート０に変数の値を受けたとき、ポート１から要求があるか要求完了前ならポート１へ転送するが、要求完了で要求リストにないとき、更新変数リストにあれば捨て、更新変数リストにないなら第４項のポート２への転送を行う。
4.. .変数の値をポート２へ転送するとき、ポート２から要求があるか要求完了前ならポート２へ転送するが、要求完了で要求リストにないとき、更新変数リストにあれば捨て、更新変数リストにないならポート０へ返す。
5.. .ポート１に変数の値が返されたとき、第4項のポート２への転送を行う。
6.. .ポート２に変数の値が返されたときポート０へ返す。
7.. .内部状態が実行文であるプロセッサは演算を開始すると共に、演算結果で更新する変数以外の変数の値をポート０に返し、演算が終了したとき演算結果で更新した変数の値と実行完了フラグをポート０へ返す。
［内部状態が“T”及び“F”のプロセッサの基本転送規則］
1.. .ポート１及び２のどちらかの変数値要求が完了前ならポート０に受けた変数値を両ポートに転送する。
2.. .両ポートの要求完了後はどちらかのポートの要求リストにあれば両ポートに転送するが、なければポート０へ返す。
3.. .内部状態が“T”のプロセッサは関係演算のフラグが真なら、そのフラグとポート２に返された変数の値をポート０へ返すが、偽ならそのフラグとポート１に返された変数の値をポート０へ返す。
4.. .内部状態が“F”のプロセッサはポート１のフラグが真なら、ポート１に返された変数の値をポート０へ返すが、偽ならポート２に返された変数の値をポート０へ返す。フラグは捨てる。
［繰返しのため必要な基本規則に優先する転送規則］
1.. .内部状態が“R{”のプロセッサはポート１に受けた変数の値が更新変数リストにも変数値要求リストにもないならポート０へ転送し、あれば関係演算フラグを受けるまで転送を保留する。
2.. .関係演算フラグが偽なら、保留した変数の値とフラグ以降にポート１に受けた変数の値、実行完了フラグをポート０に転送する。フラグは転送しない。
3.. .フラグが真なら、ポート１に実行完了フラグを受けたら実行指令をポート１に出力し、保留した値とフラグに続く値の両者のうち要求リストにある値をポート１へ転送し、更新変数リストにあって要求リストにない値は捨て、その他はポート０へ転送する。フラグは転送しない。

. . このデータ転送制御により、Fig. 3.11の２分木の根から受けた実行指令は全てのプロセッサに転送され、全てのプロセッサは更新変数名と変数値の要求を根に向けて転送する。内部状態が入力文、k=0, m=1のプロセッサはそれぞれ更新変数名n, k, mをポート０に出力し、変数値の要求はない。内部状態がk<nのプロセッサはkとnの値を要求する。内部状態がk=k+1のプロセッサは更新変数名kとkの値の要求をポート０に出力する。内部状態がm=m×kのプロセッサは更新変数名mと、m及びkの値の要求をポート０に出力する。そのポート０に接続する内部状態が“:”のプロセッサは更新変数名k, mと、k及びmの値の要求をポート０へ転送する。ポート２に受けたkの値の要求はポート１に受けた更新変数kの値であるからポート０へは転送されない。内部状態が“T”のプロセッサは更新変数名kとm、ポート１と２から要求のある変数の重複を避けたk, n, mの値の要求をポート０へ転送する。これらは内部状態が“{” “R{” “:”のポート０へ転送される。プリントする変数mの値の要求は更新変数名mの存在により内部状態が“:”のプロセッサのポート０へ転送されない。その下の内部状態が“:”のプロセッサはポート１に更新変数名mを受けるのでポート２からの更新変数名m及びmの値の要求はポート０へ転送しない。従って、更新変数名m, kと、kとnの値の要求をポート０へ転送する。その下の内部状態が“:”であるプロセッサは同様に、更新変数名k, mと、nの値の要求をポート０へ転送する。その下の内部状態が“:”のプロセッサはポート１に更新変数名nを受けるので、更新変数名n, k, mと変数値の要求なしをポート０へ転送する。根に出力された更新変数名はこのプログラムでは無視されるが、このプログラムが他の主プログラムの中に組み込まれているときはその主プログラムのデータ転送制御に使用される。
. . 実行文を内部状態とするプロセッサは変数値の要求完了をポート０へ出力すると実行文の実行を開始し、上記の更新変数名及び変数値の要求の転送とプログラムの実行は並行して行われる。入力文、k=0, m=1は略同時に実行を開始する。入力文を内部状態とするプロセッサは入力装置よりnの値を得てポート０へ出力する。ポート０の内部状態が“:”のプロセッサはnの値をポート２へ転送する。ポート２の内部状態が“:”のプロセッサはポート１に変数値の要求なしで要求完了を受けているのでnの値をポート１へ転送せずにポート２へ転送し、ポート１にkの値を受けたときそれをポート２へ転送する。ポート２の内部状態が“:”のプロセッサは同様にn, kの値をポート１へ転送せずにポート２へ転送し、ポート１に受けたmの値をポート２へ転送する。ポート２の内部状態が“:”のプロセッサはポート２にmの値の要求を受けているが、ポート１に未だ変数値要求完了を受けていなければ転送の原則に従いポート０の変数値をポート１へ転送するし、要求完了を受けていればポート１の更新変数リストにmがあるのでポート２へは転送しない。内部状態が“T”のプロセッサはポート１と２のどちらかに要求のある変数の値は両方に転送しなければならないから、両ポートにk, n, mの値を転送する。内部状態が“:”のプロセッサはポート１にkの値を転送し、ポート２にmの値を転送する。ポート２の変数値要求リストにはkの値があるが、ポート１の更新変数リストにkがあるのでポート２へはポート０に受けたkの値は転送しない。ポート１に演算結果のkの値を受けたときそれをポート２へ転送する。内部状態が“T”のプロセッサはポート１に受けたフラグが真なら、そのフラグとポート２に受けたk, n, mの値をポート０へ転送する。内部状態が“R{”のプロセッサは実行指令に続けてポート１に受けたk, n, mの値をポート１へ返す。これを繰返し、フラグが偽になると内部状態が“T”のプロセッサはポート２に実行キャンセル指令を送り、フラグとポート１に受けたk, n, mの値をポート０へ転送する。内部状態が“R{”のプロセッサはフラグを除いてポート０へ転送し、内部状態が“:”のプロセッサはk, nの値はポート０へ、mの値はポート２へ転送する。ポート２のプロセッサはmの値をプリントすると共にポート０へ返す。これらの値は根のプロセッサのポート０へ出力されて消滅するが、このプログラムが主プログラムの一部であるときは主プログラムの２分木に転送される。
. . 副プログラムは読み込みの際そのコピーを一時的に作業領域に格納しておき、call文を読込む度に代わりに格納された副プログラムのコピーを読み込み、所謂組み込み関数的に処理することができる。このときの実行処理は繰返し文の実行と同様である。繰返し文はその定義位置のみで有効な副プログラムと考えることが出来る。又、副プログラムはその定義位置においてのみ２分木に構成し、call文は無線接続によりその副プログラムを実行して結果を受け取ることも出来る。２分木の根にあるプロセッサはcall文を読込むとcall文毎に異なる識別子(番号等)を付加してポート１又は２へ転送する。２分木が構成され実行指令が転送されると、call文を内部状態とする全てのプロセッサは同一の無線周波数を用いて副プログラム名と識別子を送信する。プログラム名と一致する副プログラムの先頭プロセッサは宛先に識別子を指定して副プログラムの２分木から受けた更新変数リストと要求変数値リストを返信する。識別子で指定されたプロセッサは更新変数リストと要求変数値リストをポート０へ転送し、ポート０より全ての要求変数の値を受けたとき再度無線接続によりそれらの値を副プログラムへ転送する。脳では軸索を伸ばして離れた位置にある脳細胞に結合を形成するが、ポリプロセッサでは無線接続でこれを実現する。
. . 配列変数も同様に無線接続で処理することができる。配列変数はRAMに確保し、変数名毎に少なくとも１つの管理プロセッサを置く。プログラムを読込んで２分木に構成するとき、配列変数を読込む毎に異なる識別子を付加する。配列要素D(i, j, k)を内部状態にセットしたプロセッサは実行指令を受けたとき、配列名Dと識別子及びi, j, kの値を無線で送信する。配列Dを管理するプロセッサは識別子を宛先に指定して配列変数D(i, j, k)の値を返送する。この方法ではどんなに大きな配列でも２分木の中を流れるのは配列の要素を示すi, j, kの値だけであり、i, j, kの値が変わることで全ての要素の参照、更新が出来る。

目次へ