第12章 構文木の構築

ノード

NODE

既に書いたようにRubyプログラムはいったん構文木に変換される。 そして構文木とは具体的に何かと言うと、「ノード(node)」と呼ばれる 構造体で作られるツリー構造である。rubyではノードは全てNODE型で 表わされる。

NODE

 128  typedef struct RNode {
 129      unsigned long flags;
 130      char *nd_file;
 131      union {
 132          struct RNode *node;
 133          ID id;
 134          VALUE value;
 135          VALUE (*cfunc)(ANYARGS);
 136          ID *tbl;
 137      } u1;
 138      union {
 139          struct RNode *node;
 140          ID id;
 141          int argc;
 142          VALUE value;
 143      } u2;
 144      union {
 145          struct RNode *node;
 146          ID id;
 147          long state;
 148          struct global_entry *entry;
 149          long cnt;
 150          VALUE value;
 151      } u3;
 152  } NODE;

(node.h)

構造体名RNodeから推測できるかもしれないが、ノードはRubyオブジェクト である。つまりノードの生成と解放はrubyのガーベージコレクタが面倒をみる。

だから当然flagsにはまずオブジェクト構造体のbasic.flagsと同じ役割がある。 つまり構造体の型T_NODEFL_FREEZEなどのフラグを記録している。 NODEの場合はこれに加えてノードのタイプもflagsに格納している。

どういうことだろうか。プログラムにはifwhiledefなどいろいろな 要素があるので、それに対応してノードにもたくさん種類がある。それが ノードのタイプである。NODEには複雑な共用体が三つ用意されているが、 この共用体の使いかたはそのノードのタイプによってただ一つに決定する。 例えばifのノードNODE_IFならこうだ。

メンバ共用体メンバ役割
u1u1.node条件式
u2u2.node真の本体
u3u3.node偽の本体

またnode.hではこの共用体メンバにアクセスするためのマクロも用意されて いる。

NODEアクセス用マクロ

 166  #define nd_head  u1.node
 167  #define nd_alen  u2.argc
 168  #define nd_next  u3.node
 169
 170  #define nd_cond  u1.node
 171  #define nd_body  u2.node
 172  #define nd_else  u3.node
 173
 174  #define nd_orig  u3.value
                 :
                 :

(node.h)

例えばこんなふうに使う。

NODE *head, *tail;
head->nd_next = tail;    /* head->u3.node = tail */

ソース中ではほぼ間違いなくこのマクロのほうが使われる。そのごくわずかな 例外はparse.yNODEを生成しているところとgc.cNODEをマークする ところの二カ所だけである。

ところでこのようなマクロを使うのはなぜだろうか。一つは、u1のようにそれ 自体何も意味のない数字を覚えるのは面倒だからだろう。しかしそれ以上に重 要なのは、対応する数字は変わっても問題ないし、実際に変わる可能性がある ことだ。例えばifの条件節がu1に入っている必然性はないので、なんらかの理 由でu2に変えたくなるかもしれない。しかしu1を直接使っていたらソースコー ドのあちこちを直してまわらないとならず、不便である。ノードは全部NODEで 宣言されるから、ifを表すノードを探すのは大変だ。アクセス用のマクロを用 意しておけばそんなことはなくなるし、逆にマクロからノードの種類を判定す ることもできるようになる。

ノードタイプ

NODE構造体のflagsにはノードの種類が記憶されていると言った。 この情報の記憶方法を見ておこう。ノードタイプはnd_set_type()で セット、nd_type()で取得できる。

nd_type nd_set_type

 156  #define nd_type(n) (((RNODE(n))->flags>>FL_USHIFT)&0xff)
 157  #define nd_set_type(n,t) \
 158      RNODE(n)->flags = ((RNODE(n)->flags & ~FL_UMASK) \
                             | (((t)<<FL_USHIFT) & FL_UMASK))

(node.h)

FL_USHIFT FL_UMASK

 418  #define FL_USHIFT    11
 429  #define FL_UMASK  (0xff<<FL_USHIFT)

(ruby.h)

nd_typeあたりに注目していけばたいして苦労しない。 ようするに図1のようになっているらしい。

(flagUsage)
図1: RNode.flagsの使われかた

それから、マクロだとデバッガで使えないので関数のnodetype()も 用意されている。

nodetype

4247  static enum node_type
4248  nodetype(node)                  /* for debug */
4249      NODE *node;
4250  {
4251      return (enum node_type)nd_type(node);
4252  }

(parse.y)

ファイル名と行番号

NODEnd_fileにはこのノードに対応するテキストが存在していたファイル名 (へのポインタ)が保持されている。ファイル名があれば行番号もありそうだが 対応するメンバは見あたらない。実は行番号は以下のマクロによってflagsに 埋めこまれているのである。

nd_line nd_set_line

 160  #define NODE_LSHIFT (FL_USHIFT+8)
 161  #define NODE_LMASK  (((long)1<<(sizeof(NODE*)*CHAR_BIT-NODE_LSHIFT))-1)
 162  #define nd_line(n) \
          ((unsigned int)((RNODE(n)->flags >> NODE_LSHIFT) & NODE_LMASK))
 163  #define nd_set_line(n,l) \
 164      RNODE(n)->flags = ((RNODE(n)->flags & ~(-1 << NODE_LSHIFT)) \
                             | (((l)&NODE_LMASK) << NODE_LSHIFT))

(node.h)

nd_set_line()などはなかなか壮観だ。だが、名前からしてnd_set_line()nd_lineが対称の働きをすることは間違いないので、簡単なnd_line()を調べて パラメータの関係をつかんでしまえばnd_set_line()はそもそも解析する必要 がない。

まずNODE_LSHIFTだが、これは前項のノードタイプの話を見てくれば想像 できる通り、flagsの使われているビット数だ。FL_USHIFTrubyのシステム 予約分(11ビット、ruby.h)、8がノードタイプ分である。

次にNODE_LMASK

sizeof(NODE*) * CHAR_BIT - NODE_LSHIFT

は残っているビット数。これをrestbitsとでも置いてみよう。すると かなり簡単になる。

#define NODE_LMASK  (((long)1 << restbits) - 1)

つまり図2のようなことらしい。 1を引くとくり下がりが起こるところがポイントだ。 最終的にNODE_LMASKはまだ使えるビット分の1の並びだとわかる。

(lmask)
図2: NODE_LMASK

では改めてnd_line()を見てみよう。

(RNODE(n)->flags >> NODE_LSHIFT) & NODE_LMASK

右シフトで未使用ビット領域をLSBまで落とす。bit andでその未使用ビット領 域だけを残す。つまりflagsの使われかたをまとめると図3のよう になる。FL_USHIFTは11だったから、32ビットマシンでは 32-(10+8)=13 ビッ ト分が行番号に使えるということだ。

(flags)
図3: NODEでのflagsの使いかた

……ということは、行番号が 2^13=8192 を超えると行番号表示が おかしくなるはずである。試そう。

File.open('overflow.rb', 'w') {|f|
    10000.times { f.puts }
    f.puts 'raise'
}

筆者の686マシンではruby overflow.rbでキッチリ1809行と表示された。成 功である。ただし64ビットマシンではもう少しファイルを大きくしないとうま く失敗できないだろう。

rb_node_newnode()

最後に、ノードを生成する関数rb_node_newnode()を見よう。

rb_node_newnode()

4228  NODE*
4229  rb_node_newnode(type, a0, a1, a2)
4230      enum node_type type;
4231      NODE *a0, *a1, *a2;
4232  {
4233      NODE *n = (NODE*)rb_newobj();
4234
4235      n->flags |= T_NODE;
4236      nd_set_type(n, type);
4237      nd_set_line(n, ruby_sourceline);
4238      n->nd_file = ruby_sourcefile;
4239
4240      n->u1.node = a0;
4241      n->u2.node = a1;
4242      n->u3.node = a2;
4243
4244      return n;
4245  }

(parse.y)

rb_newobj()は第5章『ガ−ベージコレクション』で見た。空いているRVALUEを一つ取得する 関数である。これに構造体型フラグT_NODEを付けたところでVALUEとして の初期化は完了。u1 u2 u3にはもちろんNODE*以外の値を受けることもあ るのだが、とりあえずNODE*でまとめて受けておく。rubyの構文木には doubleなどは入らないのでポインタで受けておけばサイズが小さすぎるといっ た心配はない。

ここまでわかったら、あとは細部は忘れて、NODEとは

の七つのメンバを持つ構造体だと思っていればよい。

構文木の構築

パーサの役割はバイト列であるソースコードを構文木に変換することだった。 文法が通るだけではその仕事の半分もこなせていないのであって、ノードを組 み立てて木を作らなければならない。この節ではその構文木の構築過程を見て いこう。

YYSTYPE

本章はようするにアクションの話だから、$$$1の型である YYSTYPEが重要になってくる。そこでまずruby%unionを見てみよう。

%union宣言

 170  %union {
 171      NODE *node;
 172      ID id;
 173      int num;
 174      struct RVarmap *vars;
 175  }

(parse.y)

struct RVarmapは評価器の構造体で、ブロックローカル変数を格納する。 あとはいいだろう。一番使うのはもちろんnodeである。

構文木のある風景

まず事実を見る、というのがコード読みのセオリーであった。今はどういう構 文木ができるのかを知りたいわけだから、まずその答え(構文木)を見ること から始めるべきだ。

いちいちデバッガで見てみるのでもよいが、添付CD-ROMに収録したツール nodedump\footnote{nodedump:添付CD-ROMのtools/nodedump.tar.gz}を 使うともっと手軽に構文木を視覚化することができる。このツールは Pragmatic Programmers\footnote{Pragmatic Programmers ^http://www.pragmaticprogrammers.com}作の NodeDumpを本書用に改造したものだ。 オリジナルはかなり説明的な出力をしてくれるのだが、こちらの改造版では 構文木の姿を徹底的にダイレクトに出力するようにしている。

例えばm(a)という単純な式をダンプするにはこうすればいい。

% ruby -rnodedump -e 'm(a)'
NODE_NEWLINE
nd_file = "-e"
nd_nth  = 1
nd_next:
    NODE_FCALL
    nd_mid = 9617 (m)
    nd_args:
        NODE_ARRAY
        nd_alen = 1
        nd_head:
            NODE_VCALL
            nd_mid = 9625 (a)
        nd_next = (null)

-rオプションでロードするライブラリを指定し、-eでプログラムを渡す。 するとそのプログラムの構文木表現がダンプされる。

中身の見かたを簡単に説明しよう。NODE_NEWLINENODE_FCALLというのが ノードタイプだ。それと同じインデントに書いてあるものがそのノードのメン バの内容である。例えばルートにはNODE_NEWLINEがあり、そのメンバは nd_file nd_nth nd_next の三つ。nd_fileはCの文字列"-e"を指し、 nd_nthはCの整数1を指し、nd_next には次のノードNODE_CALLが格納さ れている。と言葉で言ってもわかりにくいだろうから、図4と対照 してみてほしい。

(stree)
図4: 構文木

各ノードの意味を説明すると、NODE_FCALLはFunction CALL。 NODE_ARRAYはその名前の通り配列のノードで、ここでは引数のリストを 表している。NODE_VCALLはVariable or CALLで、未定義のローカル変数を 参照するとこれになる。

ではNODE_NEWLINEはなんだろう。これは、実行時に実行中のファイル名と行 番号を合わせるためのノードで、stmt一つにつき一つセットされる。だから 実行の意味を考えるうえではこのノードは無視してもよい。またnodedumpの かわりにnodedump-shortrequireするとそもそもNODE_NEWLINEのよ うな邪魔なものは省略して表示してくれる。単純なほうが見やすいから、今後 は特に書かない限りnodedump-shortを使う。

以下では構文木全体の様子をとらえるために三つのタイプの構成要素を 見ていく。まず最初に構文木の葉(leaf)。次にその組み合わせである式、 即ち構文木の枝。最後に、文を並べるためのリストつまり構文木の幹だ。

まずは末端、構文木の葉の部分から見よう。 リテラルや変数参照など、 規則で言うとprimaryの中の特に単純なものがこれに当たる。

% ruby -rnodedump-short -e '1'
NODE_LIT
nd_lit = 1:Fixnum

数値の1。なんのヒネリもない。ただしここでノードに入っているのは Cの1ではなくてRubyの1(Fixnumの1)であることには注意。なぜかと 言うと……

% ruby -rnodedump-short -e ':sym'
NODE_LIT
nd_lit = 9617:Symbol

このように、Symbolも構文木になると同じNODE_LITで表現されるからだ。 こうやって常にnd_litVALUEを入れるようにしておけば、Symbolだろ うとFixnumだろうと実行するときには全く同じように扱うことができる。つ まり、nd_litの値を取り出して返すだけでよくなる。構文木というのは 実行するために作るものなのだから、実行に都合がいいように作るのが正しい。

% ruby -rnodedump-short -e '"a"'
NODE_STR
nd_lit = "a":String

文字列。これもRubyの文字列である。 文字列リテラルは実際に使うときにはコピーする。

% ruby -rnodedump -e '[0,1]'
NODE_NEWLINE
nd_file = "-e"
nd_nth  = 1
nd_next:
    NODE_ARRAY
    nd_alen = 2
    nd_head:
        NODE_LIT
        nd_lit = 0:Fixnum
    nd_next:
        NODE_ARRAY
        nd_alen = 1
        nd_head:
            NODE_LIT
            nd_lit = 1:Fixnum
        nd_next = (null)

配列。これは葉とは言えないが、リテラルつながりなのでよしとしよう。 NODE_ARRAYのリストに各要素のノードがぶらさがっている感じだろうか。 これだけnodedump-shortを使わない理由は……この節を最後まで読めばわかる。

次は枝にあたる部分……「組み合わせ」に注目する。 例に取るのはifだ。

if

なにかと言うとifばかり例にしているような気がするが、それはなにしろ構造 が単純だし、ifを知らない読者はいないので書くほうからすると便利なのだ。

それはともあれifの例。例えばこんなコードを構文木化してみよう。

▼ソースプログラム

if true
  'true expr'
else
  'false expr'
end

▼その構文木表現

NODE_IF
nd_cond:
    NODE_TRUE
nd_body:
    NODE_STR
    nd_lit = "true expr":String
nd_else:
    NODE_STR
    nd_lit = "false expr":String

ここでは前述のnodedump-shortを使っているのでNODE_NEWLINEが消えてい る。nd_condが条件、nd_bodyが真の場合の本体、nd_elseが偽 の場合の本体である。

では今度はこれを作っているコードを見てみよう。

ifの規則

1373                  | kIF expr_value then
1374                    compstmt
1375                    if_tail
1376                    kEND
1377                      {
1378                          $$ = NEW_IF(cond($2), $4, $5);
1379                          fixpos($$, $2);
1380                      }

(parse.y)

NEW_IF()というのがNODE_IFを生成するマクロらしい。記号の値のうち $2 $4 $5を使っているので、規則の記号と$nの対応をとってみると

kIF    expr_value  then  compstmt  if_tail  kEND
 $1          $2      $3        $4       $5    $6
NEW_IF(expr_value,       compstmt, if_tail)

となった。つまりexpr_valueが条件式、compstmt$4)が真の場合、 if_tailが偽の場合だろう。

一方ノードを生成するマクロは全てNEW_xxxxという名前で、node.hで定義され ている。NEW_IF()を見てみよう。

NEW_IF()

 243  #define NEW_IF(c,t,e) rb_node_newnode(NODE_IF,c,t,e)

(node.h)

パラメータはそれぞれcがcondition、tがthen、eがelseを表しているようだ。 前節で書いたようにノードではメンバの順番にはあまり意味がないので こんなところでパラメータ名に凝ってみる必要はない。

またアクションで条件式のノードを処理しているcond()は意味解析関数である。 これについては後述する。

それとfixpos()は行番号の補正を行っている。NODEは自分が「生成さ れたときに」読み込んでいるファイル名と行番号で初期化される。だがifを 考えてみると、NODE_IFを作るときにはもうendまでパースしているはずだ。 だからそのままにしておくと行番号がズレる。そこでfixpos()で補正すると いうことになる。

fixpos(dest, src)

で、ノードdestの行番号をノードsrcのものにする。ifで言うなら、 if式全体の行番号は条件式の行番号になるということだ。

elsif

続いてif_tailの規則も見てみよう。

if_tail

1543  if_tail         : opt_else
1544                  | kELSIF expr_value then
1545                    compstmt
1546                    if_tail
1547                      {
1548                          $$ = NEW_IF(cond($2), $4, $5);
1549                          fixpos($$, $2);
1550                      }

1553  opt_else        : none
1554                  | kELSE compstmt
1555                      {
1556                          $$ = $2;
1557                      }

(parse.y)

まずこの規則は「ゼロ個以上のelsif節のあとopt_elseで終わるリスト」 を表している。なぜなら、elsifが続いている限りif_tailが再現なく現れ、 opt_elseが来ると消えるからだ。適当な回数だけ規則を展開してみればわか る。

if_tail: kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... kELSIF .... opt_else
if_tail: kELSIF .... kELSIF .... kELSIF .... kELSE compstmt

そして次にアクションに注目すると、なんと、elsifでは普通の ifと同じNEW_IF()を使っている。つまり、以下の二つのプログラムは 構文木になってしまうと違いがなくなってしまうということだ。

if cond1                  if cond1
  body1                     body1
elsif cond2               else
  body2                     if cond2
elsif cond3                   body2
  body3                     else
else                          if cond3
  body4                         body3
end                           else
                                body4
                              end
                            end
                          end

そう言われてみればC言語などは構文レベルでもこの二つの区別がないわけで、 当然と言えば当然かもしれない。他には条件演算子(a?b:c)も構文木になる とif文と区別がつかなくなる。

文法上では大きな意味があった優先順位は構文木の構造自体がその情報を含ん でいるのでもう必要ない。またifと条件演算子のような見ための違いに至っ ては何の意味もなくなり、その意味(振舞い)だけが重要になる。だからif と条件演算子の構文木表現が同じでも全く構わないのだ。

このような例をいくつか挙げてみよう。and&&は同じになる。 or||も同じだ。not!ifと修飾if、などなども同じである。

左再帰と右再帰

ところで第9章『速習yacc』ではリストを表現するときは常にリストの記号を 左に書いていたが、if_tailでは逆になっていたことに気付いただろうか。 肝心なところだけ以下に再掲する。

if_tail: opt_else
       | kELSIF ... if_tail

間違いなく今までと逆だ。リストの記号if_tailが右にある。

実はリストにはもう一つの定石があって、

list: END_ITEM
    | ITEM list

と書くと、ITEMゼロ個以上が続きEND_ITEMで終わるリストになるのだ。

リストの表現としてはどちらだろうとあまり重大な違いはないのだが、アクショ ンの実行のされかたが致命的に違う。listを右に書く形式だと後ろの ITEMから順番にアクションが実行されるのだ。左がlistの場合のスタッ クの動きはもうやったから、右にlistがある場合を試してみよう。入力は ITEM四つとEND_ITEMである。

最初は空
ITEMITEMをシフト
ITEM ITEMITEMをシフト
ITEM ITEM ITEMITEMをシフト
ITEM ITEM ITEM ITEMITEMをシフト
ITEM ITEM ITEM ITEM END_ITEMEND_ITEMをシフト
ITEM ITEM ITEM ITEM listEND_ITEMlistで還元
ITEM ITEM ITEM listITEM listlistで還元
ITEM ITEM listITEM listlistで還元
ITEM listITEM listlistで還元
listITEM listlistで還元
accept.

「左がlist」のときにはシフトと還元が交互に行われていたのに、 今回は見ての通りずっとシフト、ずっと還元で解析されている。

なぜif_tailは「右にlist」にしていたかというと、ボトムアップで構文木を 作るためだ。ボトムアップで作ると最後にifのノードが手元に残る。しかしも し「左がlist」でif_tailを定義すると、最後に手元にifのノードを残すため にはelsifを見付けるたびにelsifのリンクを全部辿っていって末尾に追加しな ければいけなくなってしまうのだ。これは面倒くさい。ついでに遅い。だから if_tailは「右がlist」で構築してあるのだ。

最後に見出しの意味だが、文法用語だと 「左がlist」を左再帰(left recursion)、 「右がlist」を右再帰(right recursion)と言うのである。 この用語は主に文法処理の論文を読むときやyaccの本を書くときに使う。

葉、枝と来たら最後は幹だ。 文のリストをどうつないでいるのか見よう。

▼ソースプログラム

7
8
9

これに対応する構文木をダンプすると次のようになる。 これはnodedump-shortではなく完全形である。

▼対応する構文木

NODE_BLOCK
nd_head:
    NODE_NEWLINE
    nd_file = "multistmt"
    nd_nth  = 1
    nd_next:
        NODE_LIT
        nd_lit = 7:Fixnum
nd_next:
    NODE_BLOCK
    nd_head:
        NODE_NEWLINE
        nd_file = "multistmt"
        nd_nth  = 2
        nd_next:
            NODE_LIT
            nd_lit = 8:Fixnum
    nd_next:
        NODE_BLOCK
        nd_head:
            NODE_NEWLINE
            nd_file = "multistmt"
            nd_nth  = 3
            nd_next:
                NODE_LIT
                nd_lit = 9:Fixnum
        nd_next = (null)

NODE_BLOCKのリストができており、それにNODE_NEWLINEがヘッダとして くっついているのがわかる(図5)。

(blocklist)
図5: NODE_BLOCKNODE_NEWLINE

つまり文(stmt)に一つの割合でNODE_NEWLINEが付き、それが複数並ぶと NODE_BLOCKでリスト化される。コードも見てみよう。

stmts

 354  stmts           : none
 355                  | stmt
 356                      {
 357                          $$ = newline_node($1);
 358                      }
 359                  | stmts terms stmt
 360                      {
 361                          $$ = block_append($1, newline_node($3));
 362                      }

(parse.y)

newline_node()NODE_NEWLINEをかぶせ、 block_append()でリストをつなぐ。わかりやすい。 block_append()だけ中身を見ておこう。

block_append()

この関数はド真ん中にエラーチェックがあって邪魔なので その部分は省略して示す。

block_append()(省略版)

4285  static NODE*
4286  block_append(head, tail)
4287      NODE *head, *tail;
4288  {
4289      NODE *end;
4290
4291      if (tail == 0) return head;
4292      if (head == 0) return tail;
4293
4294      if (nd_type(head) != NODE_BLOCK) {
4295          end = NEW_BLOCK(head);
4296          end->nd_end = end;    /*(A-1)*/
4297          fixpos(end, head);
4298          head = end;
4299      }
4300      else {
4301          end = head->nd_end;   /*(A-2)*/
4302      }

          /* ……省略…… */

4325      if (nd_type(tail) != NODE_BLOCK) {
4326          tail = NEW_BLOCK(tail);
4327          tail->nd_end = tail;
4328      }
4329      end->nd_next = tail;
4330      head->nd_end = tail->nd_end;   /*(A-3)*/
4331      return head;
4332  }

(parse.y)

先の構文木ダンプによるとNODE_BLOCKnd_nextを使ったリンクリストだった。 それに注意して読むと、「headtailのどちらかがNODE_BLOCKでなかったら NODE_BLOCKでくるみ、リスト同士を連結する」、と読める。

それと(A-1〜3)では、リスト先頭のNODE_BLOCKnd_endが常にリスト末 尾のNODE_BLOCKを指すようにしている。こうしておけばいちいちリスト を全部辿らなくても末尾に要素を連結できるからだろう(図6)。 逆に言えば、リストを追加する必要があるときはNODE_BLOCKが 適しているということだ。

(append)
図6: 追加が楽

二つのリスト

さて、ここまでで大枠は説明した。構文木の構造については第三部でも 大量に出てくるので、第二部ではこれくらいにしておこう。しかし終わる前に もう一つだけ話しておきたい。それは二つの汎用リストのことだ。

二つのリストとは、BLOCKLISTである。BLOCKは先程説明した NODE_BLOCKのリンクリストで、文をつなぐためにある。LISTは、 LISTと言いつつもその実体はNODE_ARRAYのリストだ。配列リテラルに 使われていた奴である。LISTはメソッドの引数や多重代入のリストを 格納するために使われている。

この二つのリストの違いはノードの使いかたを見るとわかりやすい。

NODE_BLOCKnd_head要素を格納する
nd_endリスト最後のNODE_BLOCKを指す
nd_next次のNODE_BLOCKを指す
NODE_ARRAYnd_head要素を格納する
nd_alenこのノード以降のリストの長さ
nd_next次のNODE_ARRAYを指す

使いかたが違うのは二番目の要素、nd_endnd_alenだけだ。 そしてこれがそれぞれの存在意義である。NODE_ARRAYはサイズを格納 できるので、頻繁にリストのサイズが必要になる場合はARRAYリストを使う。 そうでない場合は連結が高速なBLOCKリストを使う。このへんは 使うほうのコードを見ないと意義がわからないので深くは話さないが、 第三部で登場したら「ああ、長さを使ってる」と思い出してほしい。

意味解析

第二部の最初で簡単にふれたが、一口にプログラムの解析と言っても見ための 解析と意味の解析の二つがある。見ための解析はyaccがほぼやってくれるので、 あとはアクションの中で意味の解析をすればいい。

アクション内でのエラー

意味解析とは具体的にどんなことか。例えば型有り言語なら型の検査がある。 他には、同名の変数を何回も定義していないか、変数を定義前に使っていない か、使っている手続きが定義されているか、手続きの外でreturnを使っていな いか、などが意味解析に含まれる。

現在のrubyではどんな意味解析を行っているだろうか。先程の例を見てみると rubyではエラーチェックが意味解析のほとんどを占めているので、エラーを出 しているところを探してみればよさそうだ。yaccのパーサではエラーが起きた ときにはyyerror()を呼ぶことになっている……逆に言うとyyerror()がある ところではエラーが起きているということだ。そこでアクション中で yyerror()を呼んでいる場所をリストアップしてみた。

これらのチェックはだいたい以下のような目的に分類できるだろう。

例えば「メソッド外のreturn」は規則を複雑にしすぎないためのチェック である。このエラーは構造の問題なのだから文法で対処できないことはない。 例えばメソッド内と外での文の規則を分割し、許されるものと許されない ものをそれぞれ全部並べてやればいい。しかしどう考えても面倒だし、アク ションでハネたほうがよほど簡潔だ。

また「selfへの代入」は、よいエラーメッセージを出すためのチェック だと考えられる。これは「メソッド外return」よりも文法で除外するのは ずっと簡単だが、パーサで除外すると単に"parse error"という出力 で終わってしまう。それよりは今の

% ruby -e 'self = 1'
-e:1: Can't change the value of self
self = 1
      ^

というエラーのほうがずっと親切である。

もちろんキッチリと「この目的」と言えるとは限らない。例えば 「メソッド外return」にしても、これはよいエラーメッセージを出すための チェックだと考えることもできる。目的は重なりあっているものだ。

さて問題は「純粋な意味解析」だが、Rubyではこの分類に当てはまるものがあ まりない。型付き言語だと型の解析が一大イベントなのだが、Rubyは変数が型 無しなので無意味である。代わりに目立ってくるのが値を持つ式のチェックだ。

値を持つ、を正確に言うと「評価すると値が得られる」となる。returnbreakはそれ自体値を持たない。もちろんreturn先には値を渡すわけだが、 returnが書いてある場所それ自体には値が残らない。だから例えば次のような 式は変だ。

i = return(1)

こういう式は明らかに勘違い、あるいは単純ミスなのでコンパイル時点で 弾いてしまうほうがよい。以降はこの値を取ることを確認する関数の一つ、 value_expr()を見ていくことにする。

value_expr()

value_expr()は値(value)を持つexprであることをチェックする関数である。

value_expr()

4754  static int
4755  value_expr(node)
4756      NODE *node;
4757  {
4758      while (node) {
4759          switch (nd_type(node)) {
4760            case NODE_CLASS:
4761            case NODE_MODULE:
4762            case NODE_DEFN:
4763            case NODE_DEFS:
4764              rb_warning("void value expression");
4765              return Qfalse;
4766
4767            case NODE_RETURN:
4768            case NODE_BREAK:
4769            case NODE_NEXT:
4770            case NODE_REDO:
4771            case NODE_RETRY:
4772              yyerror("void value expression");
4773              /* or "control never reach"? */
4774              return Qfalse;
4775
4776            case NODE_BLOCK:
4777              while (node->nd_next) {
4778                  node = node->nd_next;
4779              }
4780              node = node->nd_head;
4781              break;
4782
4783            case NODE_BEGIN:
4784              node = node->nd_body;
4785              break;
4786
4787            case NODE_IF:
4788              if (!value_expr(node->nd_body)) return Qfalse;
4789              node = node->nd_else;
4790              break;
4791
4792            case NODE_AND:
4793            case NODE_OR:
4794              node = node->nd_2nd;
4795              break;
4796
4797            case NODE_NEWLINE:
4798              node = node->nd_next;
4799              break;
4800
4801            default:
4802              return Qtrue;
4803          }
4804      }
4805
4806      return Qtrue;
4807  }

(parse.y)

アルゴリズム

要約。ツリーを順番になめてみて「確実に値がない式」にぶちあたったらその 時点で値を持たないとわかる。rb_warning()で警告してQfalseを返す。値のな い式に当たらないままツリーをなめおわったら値を持つ。Qtrueを返す。

ここで、必ずしもツリー全体をチェックする必要はないことに注意してほしい。 例えばvalue_expr()がメソッドの引数に対して呼ばれたと仮定しよう。 ここだ。

argの値をvalue_expr()でチェック

1055  arg_value       : arg
1056                      {
1057                          value_expr($1);
1058                          $$ = $1;
1059                      }

(parse.y)

この引数$1の中にはまたメソッド呼び出しがネストしているかもしれない。し かしその内側のメソッドの引数は既にvalue_expr()でチェックされているはず なので、もう一度チェックする必要はない。

もっと一般的に考えよう。とある文法要素Aがあったとして、その全ての構 成要素に対してvalue_expr()を呼んだとしたら、その要素Aをまたチェックし なおす必要はなくなる。

では例えばifはどうだろうか。無条件に、全要素に対してvalue_expr()を 呼んだものとして扱えるだろうか。結論だけ言うと、そうはいかない。なぜ なら文である(値を使わない)ifならば本体は値を返さなくともよいはずだ からだ。例えば次のような場合。

def method
  if true
    return 1
  else
    return 2
  end
  5
end

このif文には値は必要ない。 しかし次のような場合は値が必要だ。

def method( arg )
  tmp = if arg
        then 3
        else 98
        end
  tmp * tmp / 3.5
end

だからこの場合は代入文全体をチェックするときに初めてif文もチェックする ようにしなければいけない。そういうものがvalue_expr()switch文に並んで いるわけである。

末尾再帰の除去

ところで、value_expr()全体を眺めると以下のようなパターンが頻出しているこ とがわかる。

while (node) {
    switch (nd_type(node)) {
      case NODE_XXXX:
        node = node->nd_xxxx;
        break;
         :
         :
    }
}

この表現は以下のように変えても同じ意味だ。

return value_expr(node->nd_xxxx)

このようにreturn直前に再帰呼び出しをするコードをtail recursion、 末尾再帰と言うのだが、それは一般にgotoに変換できることがわかっている。 最適化ではよく使われる手法だ。Schemeに至っては末尾再帰は必ず言語処理系が 除去し なければならないと規格で定めている。Lisp系言語ではよくループの代わりに 再帰を使うからだ。

ただし注意してほしいのは、末尾再帰は「return直前に呼ぶ」場合だけである。 例えばvalue_expr()NODE_IFを見ると

if (!value_expr(node->nd_body)) return Qfalse;
node = node->nd_else;
break;

というように最初の一回は再帰呼び出ししている。 returnを使う形式に書き換えてみると、

return value_expr(node->nd_body) && value_expr(node->nd_else);

となって、左のvalue_expr()が偽の場合は右のvalue_expr()も 実行される。つまりその場合、左のvalue_expr()return「直前」 ではない。従ってそれは末尾再帰ではない。 だからgotoには展開できない。

値チェックの全体像

値チェックについて関数を読むのはこれで終わりだ。早すぎると思うかも しれないが、他の関数はどれもvalue_expr()と同じように地道に地道に ノードを辿ってチェックするだけなので全く面白くない。ただ全体像は 押さえておきたいので、関係関数のコールグラフだけ示して終わることに する(図7)。

(callgraph)
図7: 値チェック関数のコールグラフ

ローカル変数

ローカル変数の定義

Rubyの変数定義は種類によって随分といろいろあった。 定数やクラス変数は最初の代入が定義になっていたし、 インスタンス変数・グローバル変数はあらゆる名前が定義済みと 考えることができ、 (警告は出るけれども)代入せずにいきなり参照できるのだった。

ローカル変数の定義はそれとはまたまるで違う。ローカル変数は、 プログラム上に変数への代入が現れた時点で定義される。例えば次のように。

lvar = nil
p lvar      # 定義されている

この場合、一行目にlvarへの代入を書いたのでその時点でlvarが定義 されている。未定義の場合は次のように実行時例外NameErrorになる。

% ruby lvar.rb
lvar.rb:1: undefined local variable or method `lvar'
for #<Object:0x40163a9c> (NameError)

"local variable or method"と出ているのはなぜだろう。メソッドは呼び出し のときに引数の括弧が省略できるので、引数がないときにはローカル変数と見 分けが付かなくなる。それを解決するためにrubyは未定義のローカル変数を発 見するととりあえずメソッドとして呼んでみるのだ。そういうメソッドがなけ れば、上記のようなエラーになる。

ところで、定義されるのは代入が「現れたとき」なので、実際には代入が行わ れなくても定義されるということになる。定義された変数の初期値はnilだ。

if false
  lvar = "この代入は決して実行されない"
end
p lvar   # nilと表示される

またさらに、定義されるのは代入が「現れた」「とき」なので、 記号列上で参照の前になくてはいけない。例えば次のような場合は 定義されていない。

p lvar       # 定義されていない!
lvar = nil   # ここで現れているのだが……

「記号列上で」というところに注意してほしい。評価順とはまるで 関係がない。例えば次のようなコードなら当然条件式を先に評価するが、 記号列順だとpの時点ではlvarへの代入は現れていない。 従ってNameErrorになる。

p(lvar) if lvar = true

ここまででわかるのは、ローカル変数は非常に見ために影響されるということ だ。代入である記号列が現れたときに、その見ための順番で定義される。その 情報をベースに考えれば、rubyはパースの時点でローカル変数を定義している らしいと予想できる。なぜなら記号列の順序などというものはパーサを出てし まったらもう存在しないからだ。そして実際にその通りで、rubyではパーサが ローカル変数を定義する。

ブロックローカル変数

イテレータブロックの中で初めて宣言されたローカル変数を ブロックローカル変数またはdynamic variableと言う。 ブロックローカル変数は言語仕様的には ローカル変数と同じものである。しかしこの二つは実装が違うのだ。 どう違うのかは、これから見ていく。

データ構造

まずローカル変数のテーブルstruct local_varsから話を始める。

struct local_vars

5174  static struct local_vars {
5175      ID *tbl;                    /* ローカル変数名のテーブル */
5176      int nofree;                 /* 外部から使われているか */
5177      int cnt;                    /* tblの配列のサイズ */
5178      int dlev;                   /* dyna_varsのネストレベル */
5179      struct RVarmap* dyna_vars;  /* ブロックローカル変数名 */
5180      struct local_vars *prev;
5181  } *lvtbl;

(parse.y)

prevというメンバ名からするとstruct local_varsは逆向きリンクリスト ……そこから想定されるのはスタックだ。同時に宣言されているグローバル変数 lvtblがそのスタックの先端のlocal_varsを指す。

またstruct RVarmapenv.hで定義されていて、評価器でも使われる 公開構造体である。ブロックローカル変数を格納するために使う。

struct RVarmap

  52  struct RVarmap {
  53      struct RBasic super;
  54      ID id;                  /* 変数名 */
  55      VALUE val;              /* その値 */
  56      struct RVarmap *next;
  57  };

(env.h)

先頭にstruct RBasicがあるのでこれはRubyオブジェクトである。 即ちガーベージコレクタによって管理される。またnextメンバで つながれているのでリンクリストだろう。

ここまでの観察結果と、後でわかる情報も加えてパーサ実行中の両者のイメー ジを図にすると図8のようになる。

(localvars)
図8: ローカル変数テーブルの実行時イメージ

ローカル変数スコープ

parse.yの関数名リストを眺めていると local_push() local_pop() local_cnt()といった関数が並んでいるのが見付か る。どう考えてもこれはローカル変数っぽい。しかも名前がpush popなので明 らかにスタックだ。そこでまずはこれらの関数を使っているところを探してみ よう。

local_push() local_pop()の用例

1475                  | kDEF fname
1476                      {
1477                          $<id>$ = cur_mid;
1478                          cur_mid = $2;
1479                          in_def++;
1480                          local_push(0);
1481                      }
1482                    f_arglist
1483                    bodystmt
1484                    kEND
1485                      {
1486                          /* NOEX_PRIVATE for toplevel */
1487                          $$ = NEW_DEFN($2, $4, $5,
                                  class_nest?NOEX_PUBLIC:NOEX_PRIVATE);
1488                          if (is_attrset_id($2))
                                  $$->nd_noex = NOEX_PUBLIC;
1489                          fixpos($$, $4);
1490                          local_pop();
1491                          in_def--;
1492                          cur_mid = $<id>3;
1493                      }

(parse.y)

defで使われているのを発見できた。他にはクラス定義や特異クラス定義、特 異クラス定義にもある。つまりローカル変数のスコープが切れるところである。 しかも使われかたを見てみると、メソッド定義が始まるところでpushして終わっ たところでpopしている。ということはやはりlocal_の付く関数がローカル変 数関係であることはほぼ間違いない。またpushからpopまでの間が一つの ローカル変数スコープだろうということも判明する。

さらにlocal_cnt()も探してみた。

NEW_LASGN()

 269  #define NEW_LASGN(v,val) rb_node_newnode(NODE_LASGN,v,val,local_cnt(v))

(node.h)

node.hで見付けてしまった。parse.yにも使っているところがあるのに わざわざ別ファイルから見付けてくるあたり、筆者も切羽詰まっているようだ。

このNEW_LASGNというのはnew local assignmentつまりローカル変数の代入 のノードに違いない、またこれを使っている場所も考えるとパラメータの vがローカル引数名のようだ。valは右辺の値(を表す構文木)だろう。

以上を勘案すると、ローカル変数スコープの開始地点でlocal_push()、途中 でローカル変数の代入があったらlocal_cnt()でローカル変数追加、スコー プ終了でlocal_pop()。という、完璧な筋書きが浮かんでくる (図9)。

(localtbl)
図9: ローカル変数管理の流れ

では関数の中身を見ていこう。

pushpop

local_push()

5183  static void
5184  local_push(top)
5185      int top;
5186  {
5187      struct local_vars *local;
5188
5189      local = ALLOC(struct local_vars);
5190      local->prev = lvtbl;
5191      local->nofree = 0;
5192      local->cnt = 0;
5193      local->tbl = 0;
5194      local->dlev = 0;
5195      local->dyna_vars = ruby_dyna_vars;
5196      lvtbl = local;
5197      if (!top) {
5198          /* 一つ上のスコープの変数テーブルをvalに保管しておく */
5199          rb_dvar_push(0, (VALUE)ruby_dyna_vars);
5200          ruby_dyna_vars->next = 0;
5201      }
5202  }

(parse.y)

やはりstruct local_varsはスタックとして使われるようだ。 そしてlvtblがそのスタックの先端を指していることがわかる。 rb_dvar_push()のくだりは後で読むのでとりあえず置いておく。

続いてlocal_pop()local_tbl()をまとめて見てみる。

local_tbl local_pop

5218  static ID*
5219  local_tbl()
5220  {
5221      lvtbl->nofree = 1;
5222      return lvtbl->tbl;
5223  }

5204  static void
5205  local_pop()
5206  {
5207      struct local_vars *local = lvtbl->prev;
5208
5209      if (lvtbl->tbl) {
5210          if (!lvtbl->nofree) free(lvtbl->tbl);
5211          else lvtbl->tbl[0] = lvtbl->cnt;
5212      }
5213      ruby_dyna_vars = lvtbl->dyna_vars;
5214      free(lvtbl);
5215      lvtbl = local;
5216  }

(parse.y)

local_tbl()を見てほしい。これは現在のローカル変数テーブル(lvtbl) を得る関数である。これを呼ぶと、現在のテーブルのnofreeが真になる。 nofreeの意味は当然「free()するな」ということだろう。つまりこれはリ ファレンスカウントみたいなもので、「このテーブルは使うからfree()しな いでね」ということだ。逆に言うと、local_tbl()を一回も呼ばれなかった テーブルはポップされるときに解放され、捨てられる。例えばローカル変数が 全くないメソッドならそういうことになるだろう。

ただしここで言う「必要なテーブル」とはlvtbl->tblのことだ。 見ての通りlvtbl自体はポップと同時に解放されてしまっている。 つまり評価器では作ったlvtbl->tblだけを使うらしい。そうすると このlvtbl->tblの構造がどうなっているのか、ということが重要に なってくる。変数を追加する(らしい)関数local_cnt()を見れば どうなっているのかわかるだろう。

それとその前に、lvtbl->tblのインデックス0にlvtbl->cntを入れて いるのは覚えておいてほしい。

変数の追加

ローカル変数を追加する(らしい)関数はlocal_cnt()である。

local_cnt()

5246  static int
5247  local_cnt(id)
5248      ID id;
5249  {
5250      int cnt, max;
5251
5252      if (id == 0) return lvtbl->cnt;
5253
5254      for (cnt=1, max=lvtbl->cnt+1; cnt<max;cnt++) {
5255          if (lvtbl->tbl[cnt] == id) return cnt-1;
5256      }
5257      return local_append(id);
5258  }

(parse.y)

lvtbl->tblをスキャンして、idと等しいものを探している。見付かったと きはそのままcnt-1を返し、見付からないときはlocal_append()するよう だ。local_append()appendと言うくらいだから追加する作業に決まって いる。つまりlocal_cnt()では既に変数が登録されているかどうか確認し、 登録されていなければlocal_append()で追加して返すのだとわかる。

この関数の返り値は何を意味しているのだろうか。lvtbl->tblは変数名の 配列のようなので、変数名と「そのインデックス-1(cnt-1)」は一対一に 対応する(図10)。

(lvtbltbl)
図10: 変数名と返り値の対応関係

しかもこの返り値は0起点になるように計算されているから、恐らくローカル 変数の領域は配列なのだろう。そしてそれにアクセスするためのインデックス を返しているのだと考えられる。そうでないのならインスタンス変数や定数の ように最初から変数名(のID)をキーにすればいいはずだ。

なぜかインデックス0を避けている(cnt=1からループを回している)のが気 になるが、そこにはきっとlocal_pop()で値を入れるからだろう。

以上のことからlocal_append()の役割は中身を見なくてもわかる。ローカル 変数を登録し、その変数の「lvtbl->tblでのインデックス-1」を返すことだ。 以下、確認しよう。

local_append()

5225  static int
5226  local_append(id)
5227      ID id;
5228  {
5229      if (lvtbl->tbl == 0) {
5230          lvtbl->tbl = ALLOC_N(ID, 4);
5231          lvtbl->tbl[0] = 0;
5232          lvtbl->tbl[1] = '_';
5233          lvtbl->tbl[2] = '~';
5234          lvtbl->cnt = 2;
5235          if (id == '_') return 0;
5236          if (id == '~') return 1;
5237      }
5238      else {
5239          REALLOC_N(lvtbl->tbl, ID, lvtbl->cnt+2);
5240      }
5241
5242      lvtbl->tbl[lvtbl->cnt+1] = id;
5243      return lvtbl->cnt++;
5244  }

(parse.y)

間違いないようだ。lvtbl->tblがローカル変数名の配列になっており、 「そのインデックス-1」を返り値(ローカル変数ID)にしている。

また注意すべきはlvtbl->cntを増やしていることである。lvtbl->cntを増 やすコードはここにしかなかったので、ここのコードだけからlvtbl->cntの 意味を決定できる。それではどういう意味かと言えば、「新しい変数が追加さ れるときにlvtbl->cntが1増える」のだから、「lvtbl->cntはこのスコー プに存在するローカル変数の数を表す」のである。

それと最後にtbl[1]tbl[2]について説明しておこう。この'_''~'というのは、Rubyに慣れていると予想が付くのだが、$_$~という 特殊変数である。この二つの変数はグローバル変数な見掛けとは裏腹にロー カル変数なのだ。そして明示的に使っていなくともKernel#getsなどのメソッ ドを呼ぶと暗黙のうちにこの変数への代入が起こるので、領域は常に割り当て ておく必要がある。

ローカル変数まとめ

ローカル変数の話はいろいろとややこしかったので一度まとめよう。

まず、ローカル変数は他の変数と違ってst_table管理ではないようだという ことが一点。では何に入っているかと言うとそれは配列らしい。しかもスコープ 単位で配列に入っている。

その配列とはlvtbl->tblのことで、インデックス0にはlocal_pop()でセッ トしたlvtbl->cnt即ちローカル変数の数が入っている。インデックス1以降 にはそのスコープで定義されているローカル変数名が保存されている。従って 最終的な姿は図11のようになるはずだ。

(tbl)
図11: 変数名と返り値の対応関係

ブロックローカル変数

残る問題はstruct local_varsのメンバdyna_varsである。つまりブロック ローカル変数だ。これを何かする関数があるはず、と思って関数名リストを眺 めてみると、やはりあった。dyna_push() dyna_pop() dyna_in_block()とい う怪しげな関数がある。しかもそれを使っているところがここだ。

dyna_push dyna_popの用例

1651  brace_block     : '{'
1652                      {
1653                          $<vars>$ = dyna_push();
1654                      }
1655                    opt_block_var
1656                    compstmt '}'
1657                      {
1658                          $$ = NEW_ITER($3, 0, $4);
1659                          fixpos($$, $4);
1660                          dyna_pop($<vars>2);
1661                      }

(parse.y)

イテレータブロックの開始でpush、終了でpop。これがブロックローカル変数 の処理に違いない。

では関数を見ていく。

dyna_push()

5331  static struct RVarmap*
5332  dyna_push()
5333  {
5334      struct RVarmap* vars = ruby_dyna_vars;
5335
5336      rb_dvar_push(0, 0);
5337      lvtbl->dlev++;
5338      return vars;
5339  }

(parse.y)

lvtbl->dlevを上げているのがブロックローカル変数が存在する印のようだ。 そしてrb_dvar_push()はと言うと……

rb_dvar_push()

 691  void
 692  rb_dvar_push(id, value)
 693      ID id;
 694      VALUE value;
 695  {
 696      ruby_dyna_vars = new_dvar(id, value, ruby_dyna_vars);
 697  }

(eval.c)

変数名id、値valをメンバに持つstruct RVarmapを生成し、それをグロー バル変数ruby_dyna_varsの先頭に追加する。これはまたまたconsの形だ。 dyna_push()ではruby_dyna_varsを退避していないので、上のスコープの ruby_dyna_varsにそのまま追加してしまうようである。

しかもここで追加しているRVarmapidメンバの値が0だ。本書では真面目 にやらなかったが、rubyIDは普通にrb_intern()で作っている限りは 絶対に0にはならない。つまりこのRVarmapNULNULLのような番兵 (sentinel)の役割を果たすのではないかと考えられる。そう考えれば、変数が 追加されてもいないのに変数のホルダ(RVarmap)を追加する理由にも説明が 付く。

次にdyna_pop()

dyna_pop()

5341  static void
5342  dyna_pop(vars)
5343      struct RVarmap* vars;
5344  {
5345      lvtbl->dlev--;
5346      ruby_dyna_vars = vars;
5347  }

(parse.y)

lvtbl->dlevを戻してブロック変数スコープが終わったことを記録する。 引数を使って何かしているようだが、これは後でまとめて見よう。

これだけではブロックローカル変数を追加するところがない。ローカル変数で 言うlocal_cnt()にあたるものがないとまずい。そこでdvardynagrepしまくってみたところ、こんなコードがあった。

assignable()(一部)

4599  static NODE*
4600  assignable(id, val)
4601      ID id;
4602      NODE *val;
4603  {
                            :
4634              rb_dvar_push(id, Qnil);
4635              return NEW_DASGN_CURR(id, val);

(parse.y)

assignable()は代入系のノードを作る関数で、引用したのはそのうちブロッ クローカル変数を扱う部分である。先程見たばかりのrb_dvar_push()で新し い変数を(ruby_dyna_varsに)追加しているようだ。

パーサでのruby_dyna_vars

さて以上を考慮に入れて、ローカル変数スコープ一つをパースしおわった 時点でのruby_dyna_varsの姿を想像してみよう。

まず先程言ったとおり、ブロックスコープの始まりで追加されるid=0RVarmapはブロックスコープの切れめを表す番兵である。これを 「ruby_dyna_varsのヘッダ」と呼ぶことにしよう。

次に、さっき見せたイテレータブロックの規則のアクションのうち この部分に注目してほしい。

$<vars>$ = dyna_push();    /* $<vars>$に入れたものは…… */
        :
        :
dyna_pop($<vars>2);        /* ……$<vars>2に出てくる */

dyna_push()はそのときのruby_dyna_varsを返す。dyna_pop()は 引数をruby_dyna_varsに入れる。つまりブロックの切れめごとに ruby_dyna_varsが保存・復帰されるわけだ。 ということは以下のプログラムをパースすると、

iter {
    a = nil
    iter {
        b = nil
        iter {
            c = nil
            # ネストレベル3
        }
        bb = nil
        # ネストレベル2
        iter {
            e = nil
        }
    }
    # ネストレベル1
}

ruby_dyna_varsは図12のようになるはずだ。

(dynavars)
図12: スコープをパースし終わったときのruby_dyna_vars

この構造はなかなかうまい。どのあたりがうまいかと言うと、ネストレベルが 深い時にもリストを全部辿っていけば自然と上のレベルの変数も見えてしまう ところである。レベルごとにテーブルを作るよりこちらのほうが検索過程が 単純で済む。

また絵ではbbが変なところにぶらさがっているように見えるが、これで正し い。ネストレベルが上がって下がった後に変数が見付かったら、元のレベルの リンクの続きに連結されるからである。しかもこうなっていると「記号列上で 先に存在する変数だけが定義されている」というローカル変数の仕様を自然な 形で表現できる。

それと最後に、(ブロックローカル変数でなく)ローカル変数スコープの 切れめではこのリンク全体がlvtbl->dyna_varsに保存・復帰されている。 少し戻ってlocal_push()local_pop()を確認してきてほしい。

ところでこんなに苦労して作ったruby_dyna_varsのリストだが、これ自体は 評価器では使わない。このリストは変数の存在チェックをするのに使うだけで、 パース終了と同時にGCされてしまう。そして評価器に入ってからもう一度別 の鎖を作るようになっている。それにはかなり深い理由があるのだが……その あたりは改めて第三部で見ることにしよう。


御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。

『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

Copyright (c) 2002-2004 Minero Aoki, All rights reserved.