PLY (Python Lex-Yacc) で作る Algol 60 処理系 第２部

2008.10.17 - 2008.12.4 (鈴)

7. 名前の解決

言語処理系を実現するためには，遅かれ早かれプログラム中に現れる名前 (変数名，手続き名，ラベル名など) の意味を明らかにする必要があります。 ある場所に出現している名前と，同じつづりで別の場所に出現している名前を同一視してよいのか悪いのか， それは変数名なのか手続き名なのか，整数型なのか実数型なのか等々の問題を，プログラムの意味論にしたがって 正しく解決しなければなりません。

例えば，下記のプログラムで foo(x) と bar(x) に出現する x は int x で宣言される整数型の単純変数と見なす必要があります。 一方，baz(sin(x)/x, x) に出現する x は real x で宣言される実数型の単純変数と見なす必要があります。 

begin
   int x;
   ……
   if foo(x) then begin
      real x;
      ……
      baz(sin(x)/x, x);
   end;
   bar(x)
end

Algol のように陽な宣言と入れ子のブロック構造と静的スコープ則をもった言語で，これを実現する一つの方法は， 構文木の中で宣言部に出現する名前について，それぞれその型情報等をもったオブジェクト (本処理系では Quantity インスタンス，Types.py 参照) をひとつひとつ構築することです。 そして，名前からそのオブジェクトへの辞書 (典型的にはハッシュ表) を作り，その辞書をもって ブロックの中をトラバース (traverse) します。 該当する名前がみつかったら，それが解決済みかどうかを調べます。 もしも未解決な名前ならば，辞書を引いてオブジェクトに関連づける (本処理系では，名前を表す Identity インスタンスの quantity 属性に Quantity インスタンスへの参照を代入する) ことで，その名前を解決 (resolve) します。

これ以降の説明を省いて実際のコードをすぐに確かめたければ，Types.py の ProcedureQuantity クラスと Block クラスのあたりを見てください。 人によっては，それだけで本節の要点を完全に把握できると思います。

これを最内のブロックから順に行えば，Algol の意味論に沿ってすべての名前を解決できます。 最後まで未解決のまま残された名前は，未定義の名前ということになります。 名前の解決が終わった構文木は， そのままインタープリタにかけて実行することもできますし， あるいは他の言語へとコンパイルすることもできます。

Scheme 以降の近代 Lisp の処理系も同じようにして実現できます。 §2 で述べたように Scheme は Algol の (ある意味，ひそかな) 子供ですから，これは驚くべきことではありません。 極論すれば，動的スコープをもつ Lisp の純血種は Emacs Lisp 等のわずかな生き残りを例外として途絶え， 今の Lisp の家系は半分 Algol の血にすりかわっている，とさえいえます。
具体的なコードとしては，L2 Lisp の Python による実装 の Interp.__compile メソッドにそのような名前解決の実例を見ることができます。 ブロックに相当するものはラムダ式であり，宣言に相当するものは仮引数の並びです。 ただし，あくまで Lisp ですから，マクロ展開はあっても，これといった構文木への変換の過程はありませんし， 型情報が不要ですから，オブジェクトへの参照ではなく，じかにフレームのオフセット値へと解決しています。

名前の解決は概念的には単純な処理ですが，構文木に対して実施するには多少の手間があります。 本節では以下，その実際を説明します。

7.1 クラスによる構文木の構成

§5 で述べた構文解析器は，解析対象のプログラムの意味を考えずに単に文法から構文木を作っていました。 例えば，下記のようなプログラム (の断片) 

 7:    integer procedure Fac(k);
 8:      value k; integer k;
 9:      begin
10:        if k = 0 then Fac := 1
11:                 else Fac := k * Fac(k - 1)
12:      end Fac;

に対して，この構文解析器は次のような構文木 (の枝) を作っていました。 Python に組込みのデータ型である文字列，数，タプル，リストだけから構成されています。 含まれる 7 や 8 などの数は，もとのプログラムの行番号です。 

  ['procedure_declaration',
   7,
   ('integer', 7),
   ('IDENTIFIER', 'Fac', 7),
   [('IDENTIFIER', 'k', 7)],
   [('IDENTIFIER', 'k', 8)],
   [[('integer', 8), [('IDENTIFIER', 'k', 8)]]],
   ['compound_statement',
    [],
    [['conditional_statement',
      [],
      (10, 10, 11),
      ['operator',
       ('=', 10),
       ('IDENTIFIER', 'k', 10),
       ('UNSIGNEDINTEGER', '0', 10)],
      ['basic_statement',
       [],
       ['assignment_statement',
        [[('IDENTIFIER', 'Fac', 10), 10]],
        ('UNSIGNEDINTEGER', '1', 10)]],
      ['basic_statement',
       [],
       ['assignment_statement',
        [[('IDENTIFIER', 'Fac', 11), 11]],
        ['operator',
         ('*', 11),
         ('IDENTIFIER', 'k', 11),
         ['function_designator',
          ('IDENTIFIER', 'Fac', 11),
          [['operator',
            ('-', 11),
            ('IDENTIFIER', 'k', 11),
            ('UNSIGNEDINTEGER', '1', 11)]]]]]]]]]]

原理的には，この構文木をもとに名前の解決とそれ以降の処理を進めることができますし， そうしたほうが，これまで作った字句解析プログラム Lexer.py, 構文解析プログラム Parser.py とは独立したサブプログラムの作成という教科書的な分業制になります。

しかし，いざ，この構文木を扱おうとすると，Algol の (再帰的な) 文法構造にしたがって リストを (再帰的に) トラバースする必要があります。したがって，典型的には， 文法構造を反映した (再帰的な) 呼出し関係をもつ一群のメソッドを各文法構造 ごとに定義する必要があります。 つまり，Parser.py とよく似た (ただし，今度はフレームワークである PLY 経由で陰に LALR 法のボトムアップをするのではなく， 自ら陽にトップダウンで再帰下降を行う) 記述を繰り返すことになります。

これはかなり退屈な作業です。 むしろ，どのようにトラバースしたらよいか自ら知っているクラスを主要な文法構造ごとに定義し， はじめからそのようなクラスのインスタンスで構文木を構成するように Parser.py を書き直すのが簡単です。

§5 で作成した Parser.py は，Algol の生成規則が PLY で処理できることを 早期に確認するのが主眼であって，構文木を構成するためのメソッド記述は，正しく解析できている ことを確認するために，ほぼ機械的に書き下ろしたものですから， ここで今までの Parser.py を捨てることは惜しくありません。 プロトタイプの宿命です。
さらに言えば，実際には意外に流用が利きます。 結局，主要な文法構造に対応するクラスのコンストラクタに必要な引数がそろうまで， 下位の非終端記号に対して，これまでと同じような構文木をボトムアップに構築する必要があるからです。

必要なクラスを，新しく設けた Types.py で定義することにします。 例えば，構文木で conditional statement (条件付き文) つまり if 文にあたる節点を表現するクラスとして下記を定義します。 

class IfStatement (Traversable):
    def __init__(self, if_exp, if_lineno, then_s, then_lineno, 
                 else_s=None, else_lineno=None):
        self.if_exp = if_exp
        self.if_lineno = if_lineno
        self.then_s = then_s
        self.then_lineno = then_lineno
        self.else_s = else_s
        self.else_lineno = else_lineno

    def __repr__(self):
        if self.else_s:
            return 'if ' + pprint.pformat((self.if_exp,
                                           self.then_s, self.else_s))
        else:
            return 'if ' + pprint.pformat((self.if_exp, self.then_s))

    def traverse(self, f):
        traverse(self.if_exp, f)
        traverse(self.then_s, f)
        if self.else_s is not None:
            traverse(self.else_s, f)

コンストラクタの引数として，条件を表すブーリアン式 if_exp， 条件成立時に実行する文 then_s，条件不成立時に実行する文 else_s と，それぞれの先頭の行番号 (例外時のメッセージ作成に使う) をとります。 トラバース用のメソッド traverse では，式と文について再帰的にトラバースします。

クラス Traversable はそのインスタンスがトラバース可能であることを示します。 これは C# や Java の interface に相当しますが，Python ではさしあたり空のクラスで十分です。 

class Traversable:
    pass

実際にトラバースするときは，メソッドではなく下記の関数を利用します。 前述の traverse メソッドでも入れ子の要素について，それぞれこの関数を適用していました。 こうすることにより，非 Traversable な任意のオブジェクトを対象とすることができます。 

def traverse(x, f):
    if f(x):
        if isinstance(x, list):
            for s in x:
                traverse(s, f)
        elif isinstance(x, Traversable):
            x.traverse(f)

書き直した Parser.py の，Algol 修正報告書 4.5 節 "Conditional statements" に該当する主要部分を以下に示します。 クラス IfStatement のインスタンス構築の様子が分かると思います。 下位の非終端記号である狭義の if_statement に対する処理は，書き直し前からの流用です。 

    # 4.5 Conditional statements
    def p_if_statement(self, p):
        'if_statement : if_clause unconditional_statement'
        p[0] = (p[1], p[2])     # ((if_exp, if_lineno, then_lineno), then_s)


    def p_conditional_statment_1(self, p):
        'conditional_statement : if_statement'
        (if_exp, if_lineno, then_lineno) = p[1][0]
        then_s = p[1][1]
        p[0] = IfStatement(if_exp, if_lineno, then_s, then_lineno)

    def p_conditional_statment_2(self, p):
        'conditional_statement : if_statement ELSE statement'
        (if_exp, if_lineno, then_lineno) = p[1][0]
        then_s = p[1][1]
        else_s = p[3]
        else_lineno = p.lineno(2)
        p[0] = IfStatement(if_exp, if_lineno, then_s, then_lineno,
                        else_s, else_lineno)

    def p_conditional_statment_3(self, p):
        'conditional_statement : if_clause for_statement'
        (if_exp, if_lineno, then_lineno) = p[1]
        then_s = p[2]
        p[0] = IfStatement(if_exp, if_lineno, then_s, then_lineno)

7.2 Identifier と Quantity

名前解決の対象となる名前，つまり識別子 (identifier) を表すクラス Identifier の定義を示します。 quantity 属性が非 None ならば，その名前は解決済みと見なすことにします。 

class Identifier:
    def __init__(self, name, lineno):
        self.name = intern(name)
        self.lineno = lineno
        self.quantity = None

    def __repr__(self):
        if self.quantity:
            return '%s@%x' % (self.name, id(self.quantity))
        else:
            return '%s' % self.name

名前が表す実体である quantity は，Algol 修正報告書 2.7 節 によれば，simple variable (単純変数)，array (配列)，label (ラベル)，switch (スイッチ…いわゆるラベルの配列， Fortran でいう計算型 goto に使う)，そして procedure (手続き) の５種類に分けられます。 共通の基底クラス Quantity の派生クラスとして，それぞれの quantity に対応する クラスを定義します。 仮引数についても専用のクラスを Quantity から派生させます。 

class Quantity:
    def __init__(self, identifer_at_definition):
        self.identifier = identifer_at_definition

    def __repr__(self):
        return 'def %s@%x' % (self.identifier.name, id(self))

quantity の identifer 属性は，宣言の中で名前を定義する出現を参照するものとします。

各派生クラスは，それぞれ必要な型情報等を持ちます。例えば単純変数では，型 (整数か，実数か，ブーリアンか) と own かどうか (C 言語でいう static かどうか) のフラグを持ちます。 

class SimpleVariableQuantity (Quantity):
    def __init__(self, identifier, type, is_own):
        Quantity.__init__(self, identifier)
        self.type = type
        self.is_own = is_own

    def __repr__(self):
        s = Quantity.__repr__(self) + ':%s' % self.type
        if self.is_own:
            s += '_own'
        return s

Algol プログラム内の「宣言」(declarations) に対する構文木は，quantity のリストとして構成します。 これを実現するため，Parser.py では構文解析器ながら意味論に基づく簡単な操作をします。 例えば Algol 修正報告書 5.1 節 "Type declarations" に該当する個所では，単純変数の型 (type) に対応するキーワードを取り出し， それを名前の並びの各要素に対する SimpleVariableQuantity コンストラクタの引数として渡します。 

    # 5.1 Type declarations
    def p_type_list_1(self, p):
        'type_list : simple_variable'
        p[0] = [p[1]]

    def p_type_list_2(self, p):
        'type_list : simple_variable COMMA type_list'
        p[0] = [p[1]] + p[3]


    def p_type(self, p):
        '''type : REAL
                | INTEGER
                | BOOLEAN'''
        p[0] = KeyWord(p[1], p.lineno(1))


    def p_type_declation_1(self, p):
        'type_declaration : type type_list'
        identities = p[2]
        p[0] = [SimpleVariableQuantity(id, p[1], False) for id in identities]

    def p_type_declation_2(self, p):
        'type_declaration : OWN type type_list'
        identities = p[3]
        p[0] = [SimpleVariableQuantity(id, p[2], True) for id in identities]

例えば，real x, y, z; という宣言に対し，単なるキーワードと識別子の並びと見るのではなく， x， y， z がどれも実数型の単純変数と宣言されている，とここで解釈するわけです。

ここではまるで計算機が意志をもっているかのような表現をしました。 もちろん，実際には，この操作が「解釈」にあたると見るのは，それをさせている人間の心の反映にすぎません。 計算機はただ，指示された動作を文字通り機械的に進行させているだけです。

7.3 ラベル付きの文

Algol 60 では名前に原則として宣言が必要です。しかし，ラベルは例外です。 ラベルは宣言なしに文に付けることができます。 例えば，§7.1 で例示した「条件付き文」 "conditional statements" の構文解析ルールには 実はまだ一つ続きがありますが，それが下記の，条件付き文にコロンをはさんでラベルを付けられる，というルールです。 

    def p_conditional_statment_4(self, p):
        'conditional_statement : label COLON conditional_statement'
        p[0] = LabelledStatement(p[1], p[3])

ここでは (そして他の実行文のルールでも同様に) 動作として「ラベル付きの文」を意味する LabelledStatement のインスタンスを構築して，その構文要素の値としています。 

class LabelledStatement (Traversable):
    def __init__(self, label, statement):
        self.statement = statement
        self.label = LabelQuantity(label, self)

    def __repr__(self):
        return 'label %s: ' % self.label + pprint.pformat(self.statement)

    def traverse(self, f):
        traverse(self.statement, f)

その正体は，ラベル付けの対象となる文と，ラベルの宣言に対応する quantity です。 ラベルの quantity は次のように定義します。 

class LabelQuantity (Quantity):
    def __init__(self, identifer, target):
        Quantity.__init__(self, identifer)
        self.target = target

もちろん，このままでは，このラベルのことは，ここでしか知られず，よそで goto 文の行き先として使われていても，その名前を解決することはできません。 定義したラベルを構文木の一部としてボトムアップに持ち上げていく方法も不可能ではありませんが， 繁雑になるきらいがあります。 ラベル付き文の構文解析ルールの動作は上記のように単純なままにしておき，ラベルを含む名前の 有効範囲を決める「ブロック」からトップダウンにトラバースして，この問題を解決することにします。

7.4 Block

Algol の「ブロック」は１個以上の宣言と１個以上の文 (空文，dummy statement，が許されますから実質的には ０個以上の文) を begin と end ではさんだもので，それ自体が一つの文と見なされます。 ですから，構文木で「ブロック」を表すクラス Block は，コンストラクタの引数として，宣言のリストと，文のリストをとるようにします。 

class Block (Traversable):
    def __init__(self, declarations, statements):
        self.declarations = declarations
        self.statements = statements
        # ブロックの文のラベルを集めて宣言に追加する
        labels = []
        traverse(statements, lambda x: collect_labels(labels, x))
        declarations.extend(labels)
        # 宣言から辞書を作る
        dd = {}
        for q in declarations:
            name = q.identifier.name
            if dd.has_key(name):
                raise SemanticsError("double definition in" 
                                     " declaration: %s at %d" %
                                     (name, q.identifier.lineno))
            dd[name] = q
        # 辞書でブロック内 (宣言と文) の名前を解決する
        traverse(self, lambda x: resolve_identifier(dd, x))

    def __repr__(self):
        return 'block ' + pprint.pformat((self.declarations,
                                          self.statements)) + ' end-block'

    def traverse(self, f):
        traverse(self.declarations, f)
        traverse(self.statements, f)

このコンストラクタでは，まず，空のリスト labels を部分適用した関数 collect_labels を引数として，文のリスト statements に対してトラバースしていることに注意してください。 ブロック内に定義されているラベルの quantity をこうして labels にかき集め， そしてそれを宣言のリスト declarations に連結します。

これでラベルにまとまった宣言がないという問題は解決しました。

次に，二重定義がないかどうか，名前の重複検査をしながら，宣言のリストで辞書を作ります。 そして最後に，その辞書を部分適用した関数 resolve_identifier を引数として，宣言と文のリストの 中をトラバースしてブロック内の名前を解決します。 実行時にどれだけローカル変数用の領域をとればよいかなどは，宣言のリスト declarations から決定できますから，不要になった辞書はここでそのまま捨てます。

最後のトラバースでは，文だけでなく宣言も対象としていることに注意してください。 例えば，ブロック内で宣言されている手続きどうしで相互呼出しをするとき，互いの手続き本体に相手の手続き名が 出現しているわけですが，その名前を，両手続きを取り囲むブロックの「宣言」に対するトラバースで解決するわけです。 もちろん，このとき，それぞれの手続きが内部で宣言している名前はすでにその手続き自身の構文木構築のときに解決されて いるはずですから，トラバースでは安全に無視されます。 Quantity インスタンスは，他のオブジェクトと同じくそれぞれ固有のアイデンティティを持ちますから (ひらたくいえば，別々のアドレスに割り付けられたデータ構造どうしですから)，別々の quantity への参照として解決された名前があやまって同一視されることはありません。 

def collect_labels(labels, x): # labels を部分適用して traverse の引数とする
    if isinstance(x, (Block, Operation, Quantity)):
        return False
    else:
        if isinstance(x, LabelledStatement):
            labels.append(x.label)
        return True

ラベルをかき集めるとき，入れ子の式はもちろん，文であっても，入れ子のブロックの中に入ることはしません。 他のブロックの中のラベルは，他のブロックの宣言に含まれるものです。 collect_labels の本体の最初の if 文ではこの判断をしています。 

def resolve_identifier(dd, v):  # dd を部分適用して traverse の引数とする
    if isinstance(v, Identifier):
        if v.quantity is None and dd.has_key(v.name):
            v.quantity = dd[v.name]
        return False
    else:
        return True

一方，resolve_identifier で名前を解決するときは，ブロック内の すみずみまでもれなく走査する必要がありますから，なんら立ち入り制限はしません。 Identifier インスタンスに対して False を返して中に立ち寄らないのは， それがトラバースすべき内部構造を持たないことを知っているうえでの些細な最適化です。 ここで True を返しても，Identifier は Traversable ではありませんから，判断の手間が増えるだけで結果は変わりません。

手続きを定義する 手続き宣言 (procedure declaration) でも 仮引数 (formal parameter) に対して似たような名前解決をします。 Parser.py の p_procedure_declaration_proc(self, p)， p_procedure_declaration_func(self, p) と Types.py の ProcedureQuantity を順に追ってください。

7.5 名前解決後の構文木の例

§5 で述べた Parser.py 内蔵の単体テストの現時点での実行例を示します。 構文木のなかで，同じはずの名前どうしが同じ quantity への参照となっている (@ 以降の 16 進数が等しい) こと， 各 quantity (文字列表現が def ではじまる) が妥当な型情報を持っていることを確かめてください。 

$ python Parser.py
block ([def Fac@76cad0(k@779b48 by value as integer SimpleVariableQuantity,) ret
urns integer block ([],
 [if ((k@779b48 = 0_int),
 set [Fac@76cad0] := 1_int,
 set [Fac@76cad0] := (k@779b48 * call:Fac@76cad0((k@779b48 - 1_int),)))]) end-bl
ock,
  def n@784c88:integer,
  def LOOP@126db98,
  def EXIT@70caf8],
 [label def LOOP@126db98: call read(n@784c88,),
  if ((n@784c88 < 0_int), goto EXIT@70caf8),
  call print(n@784c88, call:Fac@76cad0(n@784c88,)),
  goto LOOP@126db98,
  label def EXIT@70caf8: pass]) end-block
$

8. インタープリタ - 文の単方向リンクと goto 文

Algol のインタープリタを作るとき，基本的には，構文はともかく意味論が似通った Scheme のような言語が参考になります (正確には，Scheme が Algol に似せて作られたわけですが)。 注意しなければならないことの一つは，Algol に goto 文があることです。

ラベルの有効範囲をブロック内に限定していること (for 文は，入れ子の文を暗黙のうちにブロックで囲んでいると想定します。 修正報告書 4.6.6 節)， およびラベルから構成される式 (designational expression) が出現できる場所を制限していること (例えば，ブロック外でも有効な変数に designational expression の値を代入することはできません) により，未設定のローカル変数やループ制御変数が使われているところにいきなり飛び込むような意味論的に不明瞭なことは そもそもできないようになっています。 たとえそのようなプログラムを書いても，そうしたラベルの出現は前節で行った名前解決で未解決のまま 残されますから，エラーとして検出できます。

ただし，変数とおなじく有効範囲が入れ子になっていることから当然予想されるように，現在の Pascal と同じく，入れ子の手続きから goto 文で大域脱出することは可能です。 つまり goto 文には，例外の発生処理と同じく，スタックを畳む処理が伴うことがあります。

問題を困難にしているのは，goto のジャンプ先が普通， 複合文 (compound statement，宣言を伴わない begin … end) の途中の文や，if 文の一つの分岐のように (変数のスコープと無関係な) 入れ子の文であることです。 ジャンプ先の文が，複合文の中にあるという文脈情報や if 文の分岐の中にあるという文脈情報， いいかえれば，ジャンプ先のラベルが付いた文そのもの (Parser ではこれを LabelledStatement のインスタンスとして構成しました) だけでなくその文を無事実行した後，次に継続してどの文を実行すればよいかという情報が必要です。

こうした情報を与えるひとつの方法は，構文木の中の一つのノードだけが (ジャンプ先として) 与えられたとき， それが木の中でどのように位置づけられるのか分かるようにノード間のリンクを双方向にすることです。

もうひとつの方法は，構文木のまま処理するのではなく，いったん実在のあるいは仮想的な機械語にコンパイルし，次に 実行すべき文は，プログラムカウンタの次のアドレスにある命令であると決め打ちできるようにすることです。

しかし，ここでは，前節までの構文木が与えられたとして，より簡易にできる方法を採りました。 それは，構文木の中の「文」にあたる各ノード s にそれぞれ 次の文への単方向のリンク s.next_statement を付けていくという方法です。 入れ子の文の末尾を判定できるように s.is_terminal という属性も付けます。 これが真のとき，s.next_statement は入れ子の親への戻りリンクを意味することにします。

構文木の中で if 文など，入れ子の文を持つものは，元々，入れ子の文へのリンクを持っていました。 ですから，それらのリンクと next_statement によるリンクをあわせて結局は 双方向のリンクを持つことになります。 ただし，次に述べる複合文では，純粋に単方向のリンクになります。 これは理屈で考えるより，後述の図を見ればすぐ分かると思います。

構文木の中で複合文は Python のリストで表現していましたが，ここで専用のクラスを定義します。 

class CompoundStatement (Traversable):
    def __init__(self):
        self.next_statement = None

    def __repr__(self):
        r = []
        s = self
        while True:
            s = s.next_statement
            if s is None:
                break
            r.append(repr(s))
            if s.is_terminal:
                break
        return "begin " + "; ".join(r) + " end"
    
    def traverse(self, f):
        s = self
        while True:
            s = s.next_statement
            if s is None:
                break
            traverse(s, f)
            if s.is_terminal:
                break

入れ子の文 x （ただし，親は home ）に対して，next_statement で単方向のリンクを張る関数 make_statements_threaded は次のように書けます。 

def make_statements_threaded(x, home):
    """x の文どうしを next_statement 属性で正方向に連結する。
    末尾の文は home につなげる。
    """
    if x is None:
        return None
    elif isinstance(x, list):
        if len(x) == 1:
            return make_statements_threaded(x[0], home)
        c = CompoundStatement()        
        tail = __make_threaded(c, x)
        x = c
    else:
        __make_inner_threaded(x)
        tail = x
    tail.next_statement = home
    tail.is_terminal = True
    return x

def __make_threaded(prev, x):   # returns tail
    if isinstance(x, list):
        for s in x:
            prev = __make_threaded(prev, s)
        return prev
    else:
        __make_inner_threaded(x)
        prev.next_statement = x
        prev.is_terminal = False
        return x

def __make_inner_threaded(x):
    if isinstance(x, Block):
        x.statements = make_statements_threaded(x.statements, x)
    elif isinstance(x, IfStatement):
        x.then_s = make_statements_threaded(x.then_s, x)
        x.else_s = make_statements_threaded(x.else_s, x)
    elif isinstance(x, (ForStatement, LabelledStatement)):
        x.statement = make_statements_threaded(x.statement, x)

こうすると，インタープリタの中心部を， 一つ文を処理してから，next_statement をたどって次の文へ進む 無限ループ として記述できます。 goto による手続き間の大域脱出を実現するため， Python 自身のスタックは使わず，Frame インスタンスのリストとして構成した self.stack を利用します。 各ラベル j にそれを取り囲む手続きを j.procedure 属性として持たせておき， これを使って，どれだけ self.stack_pop() でスタックを畳めばよいか判定します。 

class Interpreter:
    ……
    def do_statement(self, x):
        "構文木のノード x を文として実行する。"
        while True:
            print "DO", x, x.is_terminal, x.next_statement.__class__
            if isinstance(x, LabelledStatement):
                x = x.statement
            elif isinstance(x, ProcedureStatement):
                frame = Frame(x.fun.quantity, x.args, caller=x, interp=self)
                self.stack_push(frame)
                x = x.fun.quantity.body
            elif isinstance(x, Block):
                self.do_declarations(x.declarations)
                x = x.statements
            elif isinstance(x, GoToStatement):
                j = self.eval_expression(x.desig)
                assert isinstance(j, LabelQuantity)
                while True:
                    current_frame = self.stack[-1]
                    if current_frame.procedure is j.procedure:
                        break
                    else:
                        self.stack_pop()
                x = j.target
            elif isinstance(x, IfStatement):
                e = self.eval_expression(x.if_exp)
                assert e is True or e is False
                if e:
                    x = x.then_s
                else:
                    if x.else_s is None:
                        x = x.next_statement
                    else:
                        x = x.else_s
            else:
                if isinstance(x, AssignmentStatement):
                    self.do_assignment(x.lhs, x.rhs)
                else:
                    ……
                while x.is_terminal:
                    x = x.next_statement
                    if isinstance(x, ProcedureQuantity):
                        print " RETURN", self.stack
                        frame = self.stack_pop()
                        x = frame.caller
                        if x is None: # 文が尽きるとき caller=None
                            return
                        assert isinstance(x, ProcedureStatement)
                x = x.next_statement

無限ループを作る while True: の次の行の print "DO", x, …… は動作確認用の print 文です。次の節ではこれを使って実験の経過を観察します。

8.1 実験

0.2 版 Interpreter.py に下記の Alogl プログラムを与えてみます。 

$ cat ex8_1.txt
begin
  integer x;
L1:
  if true then goto L2
          else goto L1;
  x := 3;
L2: 
end
$

下記のような出力が得られます。 

$ ./Interpreter.py ex8_1.txt
 FRAME (main):0@dc0f8 [None]
DO block ([def x@dc378:integer, def L1@dc9b8, def L2@de210],
 begin label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8); set [x@dc378
] := 3_int; label def L2@de210: pass end) end-block True Types.ProcedureQuantity
DO begin label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8); set [x@dc3
78] := 3_int; label def L2@de210: pass end False Types.LabelledStatement
DO label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8) False Types.Assig
nmentStatement
DO if (True, goto L2@de210, goto L1@dc9b8) True Types.LabelledStatement
DO goto L2@de210 True Types.IfStatement
DO label def L2@de210: pass True Types.Block
DO pass True Types.LabelledStatement
 RETURN [(main):0@dc0f8]
$
このとき，構文木は次のようにリンクづけられています。

以下，この図を念頭において各出力行を解説します。

最初の出力行は，トップレベルのためのフレームが構築されたことを表しています。 

 FRAME (main):0@dc0f8 [None]

変数の扱いを一様にするため，トップレベルのブロックを仮想的に (main) という名前の手続き (構文木の中では ProcedureQuantity インスタンス) の本体 (body) とします。 この手続きのためのフレーム構築です (詳しくは次節で述べます)。

次に続くのは，この本体 (body) に対する do_statement メソッドの動作確認用出力です。 

DO block ([def x@dc378:integer, def L1@dc9b8, def L2@de210],
 begin label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8); set [x@dc378
] := 3_int; label def L2@de210: pass end) end-block True Types.ProcedureQuantity

本体として１個のブロック，つまり Block インスタンス (出力中では block … end-block) が与えられています。 出力末尾の True Types.ProcedureQuantity は，これが終わったら 入れ子の親である (main) 手続きに戻ることを意味します。

ブロック自身の入れ子の文 (Block インスタンスの statements 属性) へ進みます。 

DO begin label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8); set [x@dc3
78] := 3_int; label def L2@de210: pass end False Types.LabelledStatement

出力行の begin … end は複合文 CompoundStatement のインスタンスを表します。 セミコロンで区切られて三つの文が並んでいます。 出力末尾の False Types.LabelledStatement は，複合文はまだ終わりではなく，複合文の中の次の文としてラベル付き文が来ることを意味します。 

DO label def L1@dc9b8: if (True, goto L2@de210, goto L1@dc9b8) False Types.Assig
nmentStatement

ラベル付き文です。ラベル L1 を定義し，if 文を含んでいます。 出力末尾の False Types.AssignmentStatement は，複合文はまだ終わりではなく， 複合文の中の次の文として代入文が続くことを意味します。 入れ子の if 文に進みます。 

DO if (True, goto L2@de210, goto L1@dc9b8) True Types.LabelledStatement

if 文です。 出力末尾の True Types.LabelledStatement は，これが終わったら親のラベル付き文に戻ることを意味します。 if 文に与えられた条件 True を評価します。 これは真ですから，then 節に進みます。 

DO goto L2@de210 True Types.IfStatement

then 節の goto 文です。 出力末尾の True Types.IfStatement は，これが終わったら親の if 文に戻ることを意味します。 goto 文を実行します。 その結果，実際には親元に戻らずに，ラベル L2 が定義されているラベル付き文に進みます。 

DO label def L2@de210: pass True Types.Block

ラベル付き文です。 出力末尾の True Types.Block は，これが終わったらブロックに戻ることを意味します。 入れ子の空文 (構文木では DummyStatement インスタンス，出力では pass) に進みます。 

DO pass True Types.LabelledStatement

空文は何もしません。ラベル付き文に戻ります。 ラベル付き文には次がなくブロックに戻ります。 ブロックには次がなく手続き (main) に戻ります。 これはトップレベルで呼出し元 (caller) がありませんから，これで終わりです。

手続きを終えてフレームをスタックから除く前に，スタックの状況を表示します。 

 RETURN [(main):0@dc0f8]

確かに (main) 用の１個のフレームだけがあります。 これでプログラムを終了します。

図 から分かるように，この方法で実行するとき，本来ならば，構文木に CompoundStatement インスタンスは不要です。 複合文の中の最初の文をそのまま単方向リストの先頭要素にすればよいわけです。 そうなっていないのは，今までの __repr__ メソッドやtraverse メソッドをそのまま使えるようにするためです。 CompoundStatement インスタンスを使わないようにする改造は，読者への課題とします。

9. インタープリタ - 手続きとディスプレイとスタック

単純変数と call by value の引数渡しに限られていますが，前節で暗示したように， 現時点でのインタープリタ実装である 0.2 版 Interpreter.py では変数束縛と手続き呼出しも実現しています。

Scheme と異なり，Algol 60 のローカル変数の寿命は無期限ではなく，手続き本体の駆動期間に 限られていますから，その割付けは常に単純なスタック (stack) で実現できます。 実際には，ローカル変数を個々別々にスタックに積むかわりに， それらを手続き呼出し単位でひとつの組にまとめたフレーム (frame) を作って，スタックに積み上げます。

手続きの静的な入れ子構造から決定される静的スコープを実現するために， 必ずしも静的な入れ子構造とは一致しない動的呼出し関係を反映したスタックから， とびとびにフレームを参照しなければならないことがあります。 ここでは，その実現方法として，手続きの静的な入れ子レベルごとに，その時点で有効なフレームへの参照を保持する ディスプレイ (display) という小さな配列を設ける方法を採りました。 この配列の大きさの上限は静的な入れ子の最大深さと一致しますから，プログラムの実行前に決定できます。

下図は，手続きとディスプレイとスタックを，静的な入れ子レベルごとに色分けした模式図です。 トップレベル (main) から Foo を呼び出し，それが Bar を呼び出し， それが Baz を呼び出し，それが Foo を呼び出し，それが Bar を呼び出したときのディスプレイとスタックの様子を示しています。

ローカル変数へのアクセスには，そのローカル変数が属する手続きの静的な入れ子レベル (level) と， その変数自身のフレーム中での位置つまりオフセット (offset) を使います。 下記は Interpreter クラスの eval_expression(self, e) メソッドのなかでローカル単純変数の値を取得している部分です。 

            elif isinstance(q, SimpleVariableQuantity):
                frame = self.display[q.level]
                return frame.vars[q.offset]

一方，代入文の実装メソッド do_assignment(self, lhs, rhs) で，右辺 (right-hand side) の評価値をローカル単純変数に代入している部分は，下記のようになっています。 

                frame = self.display[var.level]
                frame.vars[var.offset] = rhs_value

ディスプレイのほかに静的リンク (static link) を使う実装方法もあります。 ディスプレイと静的リンクの比較は，下記文献 (いわゆるタイガーブック) の演習 6.7 (pp.146-147) で取り上げられています。

下記文献の第９章にも両者に関する記述があります。

いわゆるドラゴンブックでは第7.4節で取り上げられています。 同書では「静的リンク」"static link" ではなく "access link" という用語が使われています。

ちなみに Scheme と同じく静的スコープを採用する L2 Lisp のインタープリタでは，(Scheme と同様の変数の無期限の寿命を素直に実装して) フレームはスタック構造をとりません。しかし，静的リンクにあたる構造は備えています。 下記はその Python 版の実装でのローカル変数値の取得メソッドです。 ここでのレベル (level) は現在の手続き (ラムダ式) を 0 として数える相対的な値です。 入れ子の外側の変数にアクセスするときは，この相対レベルだけの回数，静的リンクをたどります。 
    def get_value(self, env):
        "与えられた環境で仮引数の値を得る"
        for i in range(self.level):
            env = env.cdr
        return env.car[self.offset]

9.1 手続きの入れ子レベルとローカル変数の解決

ローカル変数は，手続きの仮引数として宣言されるほか， 手続きに含まれるそれぞれのブロックで宣言されます。 ブロックごとにフレームを作る方法もありますが，今回の実装では， 手続き単位でブロックのローカル変数をまとめて一つのフレームとして構成することにします。 まとめるために構文木をトラバースします。 

class Interpreter:
    def __init__(self, parser):
        self.parser = parser
        self.owns = []

    def run(self, source_text):
        "ソーステキストをプログラムとして実行する。"
        tree = self.parser.parse(source_text)
        self.max_level = 0
        locals = []
        traverse(tree, lambda y: self.__transform(1, locals, y))
        ……

このとき，ついでですから手続きの入れ子深さのレベルを決定し， 各 ProcedureQuantity インスタンスの level 属性として記録します。 ディスプレイの大きさを決定するために，入れ子の最大深さ self.max_level も記録します。

どのみち Python で実装するのですから，事前に大きさを決定しなくても実行時に必要なだけリストを伸長すればよいわけですが， プログラムが満たすはずの条件を (リーズナブルなコストで) 事前に得ておくことは，誤り検出/解析のために悪いことではありません。

さらに，ついでですから，§8 で述べた goto 文のための単方向リンクを，各 ProcedureQuantity インスタンスの body に対し， make_statements_threaded 関数を使って張ります。 本節の話題としては，ついでの傍題ですが，メソッド名 __transform は，このリンク張りで実質的に構文木を変形することに由来しています。 

    def __transform(self, level, vars, x):
        """
        字句的な入れ子の深さに応じて手続きに level 属性 (1 から) を与え，
        手続きの本体の文を正方向に連結する。
        また，その手続き内で宣言された変数の quantity を locals 属性に
        まとめる。ただし，own 変数は self.owns にまとめる。
        各ラベルに procedure 属性 (取り囲む手続きを指す) を与える。
        """
        if isinstance(x, ProcedureQuantity):
            if self.max_level < level:
                self.max_level = level
            x.level = level
            locals = []
            traverse(x.body,
                     lambda y: self.__transform(level + 1, locals, y))
            x.locals = self.filter_out_non_locals(locals, x)
            x.body = make_statements_threaded(x.body, x)
            resolve_locals(x)
            return False
        elif isinstance(x, Block):
            vars.extend(x.declarations)
            return True
        else:
            return isinstance(x, (list,
                                  LabelledStatement,
                                  IfStatement,
                                  ForStatement))

メソッド __transform では，仮引数 vars として渡されたリストに対し 

        elif isinstance(x, Block):
            vars.extend(x.declarations)
            return True

で各ブロックの宣言 (実体は，quantity インスタンスのリスト) を集積します。 ただし，宣言には own 変数やラベルなど，フレームに入れるべきではないものも含まれています。 ローカル変数だけをこしとったリストを ProcedureQuantity インスタンスの local 属性とします。 フレームを構築するときは，この属性と仮引数の属性 params がひながたになります。 

            x.locals = self.filter_out_non_locals(locals, x)

こしとるとき，ついでですから，ラベルに対して，それを取り囲む手続きを procedure 属性として記録します。 §8 で述べたように，この属性は，goto 文で大域脱出するとき， 脱出先のラベルの手続きに該当するフレームにたどりつくまでスタックを pop するために do_statement メソッドで使われます。 

    def filter_out_non_locals(self, locals, procedure):
        """
        宣言された変数の quantity からなるリスト locals から
        非 own な単純変数と配列および switch をこしとって戻り値とする。
        own 変数はリスト self.owns に追加する。
        またラベルには procedure 属性を付加する。
        """
        local_vars = []
        for q in locals:
            if isinstance(q, LabelQuantity):
                q.procedure = procedure
            elif isinstance(q, (SimpleVariableQuantity, ArrayQuantity)):
                if q.is_own:
                    self.owns.append(q)
                else:
                    local_vars.append(q)
            elif isinstance(q, SwitchQuantity):
                local_vars.append(q)
        return local_vars

トラバースでは，各 ProcedureQuantity インスタンスに対し，最後に resolve_locals 関数を適用します。 

            resolve_locals(x)

この関数は，引数である ProcedureQuantity インスタンスの params 属性と locals 属性の各要素，つまりローカル変数の quantity に対して，level 値と offset 値を設定します。 §7 で述べたように，この時点ですでに手続き本体のローカル変数の出現はすべて，その quantity への参照として解決されています。 フレームに含まれる実行時の変数値の格納場所は level 値と offset 値から決定できますから，これでローカル変数の実行前解決が完了したことになります。

インタープリタではひとまずここまでですが，コンパイラならば，各ローカル変数の出現に対して， 具体的な値の取得と代入のためのコードを生成できる情報がそろったことになります。 
def resolve_locals(procedure):
    assert isinstance(procedure, ProcedureQuantity)
    level = procedure.level
    for (i, var) in enumerate(procedure.params):
        var.offset = i
        var.level = level
    args_len = len(procedure.params)
    for (i, var) in enumerate(procedure.locals):
        var.offset = i + args_len
        var.level = level

9.2 フレームの構築と解放

現時点でのフレーム・クラスの定義を下記に示します。 手続きの入れ子レベル procedure.level を，そのままフレームの level とします。 コンストラクタの引数 args は Algol の手続き呼出しの実引数です。 Frame インスタンスの vars 属性の仮引数に対応する offset 位置に実引数の評価結果を代入することで，call by value の引数結合を実現します。 

class Frame:
    def __init__(self, procedure, args, caller, interp):
        assert isinstance(procedure, ProcedureQuantity)
        self.procedure = procedure
        self.caller = caller
        self.level = procedure.level
        self.vars = [None] * (len(procedure.params) + len(procedure.locals))
        # XXX call by value の単純変数のみ 型検査なし
        for (i, exp) in enumerate(args):
            val = interp.eval_expression(exp)
            self.vars[i] = val
        print " FRAME %s %s" % (self, self.vars)

    def __repr__(self):
        return "%s:%d@%x" % (self.procedure.identifier, self.level, id(self))

インタープリタのスタックにフレームを積むときは， その level に対応するディスプレイがフレームを参照するように設定します。 

class Interpreter:
    ……
    def stack_push(self, frame):
        """
        frame とその level で self.display を設定してから
        frame を self.stack に追加する。
        """
        level = frame.level
        frame.old_display = self.display[level]
        self.display[level] = frame
        self.stack.append(frame)

スタックからフレームを下ろすときは，対応するディスプレイの値を元に戻します。 

    def stack_pop(self):
        """
        self.stack の末尾から frame を取り出し，self.display を復旧してから
        frame を返す。
        """
        frame = self.stack.pop()
        self.display[frame.level] = frame.old_display
        del frame.old_display
        return frame

Algol の手続き文による手続きの呼出しと，手続きおよび関数の本体からの戻りは， do_statement メソッドの下記の箇所で行います。 

    def do_statement(self, x):
        "構文木のノード x を文として実行する。"
        while True:
            ……
            elif isinstance(x, ProcedureStatement):
                frame = Frame(x.fun.quantity, x.args, caller=x, interp=self)
                self.stack_push(frame)
                x = x.fun.quantity.body
            ……
            else:
                ……
                while x.is_terminal:
                    x = x.next_statement
                    if isinstance(x, ProcedureQuantity):
                        print " RETURN", self.stack
                        frame = self.stack_pop()
                        x = frame.caller
                        if x is None: # 文が尽きるとき caller=None
                            return
                        assert isinstance(x, ProcedureStatement)
                x = x.next_statement

トップレベルの文は，次のように caller=None で (main) 手続きを模造して実行します。 文が尽きたとき caller=None により return が行われます。 

    def run(self, source_text):
        ……
        traverse(tree, lambda y: self.__transform(1, locals, y))
        main = ProcedureQuantity(Identifier("(main)", 1), type=None,
                                 params=[], values=[], specs=[], body=tree)
        main.level = 0 # base level
        main.locals = self.filter_out_non_locals(locals, main)
        main.body = make_statements_threaded(main.body, main)
        resolve_locals(main)
        self.display = [None] * (self.max_level + 1)
        self.stack = []
        self.stack_push(Frame(main, [], caller=None, interp=self))
        self.do_statement(main.body)

Algol の式の中から関数呼出しを行うときは，eval_expression メソッドから call_function メソッドを呼び出します。 Algol 60 では無引数関数を呼び出すときに括弧をつけませんから，構文上は単純変数と区別できません。 名前解決 (§7) の後，ProcedureQuantity インスタンスを参照していることで区別されます。 

    def eval_expression(self, e):
        "構文木のノード e を式として評価する。"
        ……
        elif isinstance(e, Identifier):
            q = e.quantity
            if isinstance(q, ProcedureQuantity):
                return self.call_function(q, [])
            ……
        else:
            assert isinstance(e, Operation)
            (op, arg) = (e.op, e.arg)
            ……
            elif isinstance(e, FunctionDesignator):
                return self.call_function(op.quantity, arg)
            ……

関数呼出しのときは caller=None を指定して，関数本体の文が尽きた後， すぐにここに戻ってくるようにします。 

    # XXX この中で大域 goto が実行されたら？
    def call_function(self, procedure, args):
        "関数を呼び出す。関数の戻り値を結果の値として返す。"
        frame = Frame(procedure, args, caller=None, interp=self)
        self.stack_push(frame)
        self.do_statement(procedure.body)
        return frame.result

ちなみに，加減乗除や大小比較などの演算も，「式」の構文木に沿って eval_expression メソッドを再帰的に呼び出して (つまり，Python ネイティブのスタックを積み上げて) 行います。 ただし，各演算子の実装は Python のコードですから，それにオペランドを渡すとき，いちいち Frame インスタンスは作りません。

9.3 実験

再帰による階乗計算の例を実行した結果を示します。 出力の繁雑さを避けるため，do_statement メソッドの print "DO", x, …… をコメントアウトしています。 

$ cat E_fac5.txt
  begin
    comment
      階乗を計算する;

    integer procedure Fac(k);
      value k; integer k;
        if k = 0 then Fac := 1
                 else Fac := k * Fac(k - 1);

    integer ans;
    ans := Fac(5)
  end
$ ./Interpreter.py E_fac5.txt
 FRAME (main):0@ddd00 [None]
 FRAME Fac:1@dcd78 [5]
 FRAME Fac:1@78f7d8 [4]
 FRAME Fac:1@78f0a8 [3]
 FRAME Fac:1@78ffd0 [2]
 FRAME Fac:1@78ff58 [1]
 FRAME Fac:1@78ff08 [0]
 RESULT OF Fac:1@78ff08 := 1: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78, Fac:1@78f7d8, Fac:1@78f0a8, Fac:1@78ffd0, 
Fac:1@78ff58, Fac:1@78ff08]
 RESULT OF Fac:1@78ff58 := 1: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78, Fac:1@78f7d8, Fac:1@78f0a8, Fac:1@78ffd0, 
Fac:1@78ff58]
 RESULT OF Fac:1@78ffd0 := 2: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78, Fac:1@78f7d8, Fac:1@78f0a8, Fac:1@78ffd0]
 RESULT OF Fac:1@78f0a8 := 6: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78, Fac:1@78f7d8, Fac:1@78f0a8]
 RESULT OF Fac:1@78f7d8 := 24: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78, Fac:1@78f7d8]
 RESULT OF Fac:1@dcd78 := 120: <type 'int'>
 RETURN [(main):0@ddd00, Fac:1@dcd78]
 SET (main):0@ddd00[0] := 120: <type 'int'>
 RETURN [(main):0@ddd00]
$

正しく再帰が行われ，5! = 120 がトップレベルのフレームの最初の位置の変数，つまり ans に代入されています。

10. インタープリタ - 式の中からの大域脱出

call_function メソッドのコメントでも言及しましたが， ここまでの実装方法では，「文」として呼び出した手続きの本体からの大域 goto はできますが，Python のネイティブなスタックを積み上げて評価する「式」の 中から関数を呼び出したとき，その関数の本体からの大域的 goto による脱出はできません。 do_statement メソッドの中でいくら self.stack_pop() をしても， ネイティブなスタックが積み上がったままだからです。 関数と手続きの入れ子により「式」と「文」が多層的に重なることが，この問題を一層困難そうなものにしています。

しかし，トップレベルからにせよ，「式」からにせよ，外から do_statement メソッドの中に入ったとき，スタック・トップにある現在のフレームの呼出し元 (caller) が None であることを利用すれば，この問題は案外簡単に解決できます。

0.3 版 Interpreter.py では，そのために，まず goto 文のための例外を定義します。 

class GoToException (Exception):
    def __init__(self, label):
        self.label = label

次に，do_statement メソッドをこの例外を使って書き直します。 ジャンプ先のラベルを取り囲む手続きのフレームに出会うまで self.stack_pop() することは，今までと同じですが， もしもスタックトップのフレームの呼出し元が None になっているところまで来たら，今の do_statement が呼び出された最初のところまで該当フレーム無しだったということになりますから， raise ex で例外を再送出してメソッドから脱出します。 ほかではこの例外は捕捉しませんから，「式」の評価をするために積み上がった Python のネイティブ・スタックがどんどん畳まれ，その「式」を評価している「文」に対応する下方の do_statement メソッドのところまでたどりつきます。 

    def do_statement(self, x):
        "構文木のノード x を文として実行する。"
        while True:
            try:
                ……
                elif isinstance(x, GoToStatement):
                    j = self.eval_expression(x.desig)
                    raise GoToException(j)
                ……
                else:
                    ……
                    while x.is_terminal:
                        x = x.next_statement
                        if isinstance(x, ProcedureQuantity):
                            print " RETURN", self.stack
                            frame = self.stack_pop()
                            x = frame.caller
                            if x is None: # 文が尽きるとき caller=None
                                return # 正常終了
                            assert isinstance(x, ProcedureStatement)
                    x = x.next_statement
            except GoToException, ex:
                j = ex.label
                assert isinstance(j, LabelQuantity)
                while True:
                    frame = self.stack[-1]
                    if frame.procedure is j.procedure:
                        break
                    self.stack_pop()
                    if frame.caller is None:
                        print " EXIT TO", j, self.stack
                        raise ex # 大域脱出
                print " JUMP TO", j, self.stack
                x = j.target

10.1 実験

サンプル・プログラム E_goto_in_nesting.txt で実験してみます。 

$ cat E_goto_in_nesting.txt
begin
  procedure P;
  begin
    integer procedure F;
    begin
      procedure Q;
      begin
        procedure R;
        begin
        end R;

        R;
        goto L1
      end Q;

      Q;
      P;
    L1: goto L2
   end F;

   integer a;
   a := F
  end P;

  procedure S;
  begin
  end S;

  P;
  S;
L2:
end
$ ./Interpreter.py E_goto_in_nesting.txt
 FRAME (main):0@790f80 []
 FRAME P:1@790d00 [None]
 FRAME F:2@790f30 []
 FRAME Q:3@790eb8 []
 FRAME R:4@790cb0 []
 RETURN [(main):0@790f80, P:1@790d00, F:2@790f30, Q:3@790eb8, R:4@790cb0]
 JUMP TO def L1@dde18 [(main):0@790f80, P:1@790d00, F:2@790f30]
 EXIT TO def L2@790d78 [(main):0@790f80, P:1@790d00]
 JUMP TO def L2@790d78 [(main):0@790f80]
 RETURN [(main):0@790f80]
$

Algol の関数 F からトップレベルのラベル L2 に goto L2 でジャンプするとき，確かに GoToException 例外の再送出 (出力上は "EXIT TO …") が行われています。 下図は，このプログラムの構造と実行時のスタックを模式図にしたものです。 図中，スタックの各フレームに書いた「←p」 は p が呼出し元 (caller) であることを意味します。赤い矢印は goto によるジャンプを表しています。

11. インタープリタ - call-by-name の実現

§9 では，さしあたり単純変数だけですが，多くのプログラミング言語でおなじみの call-by-value の引数渡しを実現しました。 この機構では，実引数をその出現場所で評価し，その結果の値で仮引数を初期化します。 仮引数は単に初期化されたローカル変数として扱います。 ですから，とにかくローカル変数さえ実現できれば，call-by-value の実現は簡単です。

一方，Algol は，特徴的な (というより，むしろ，ほとんど固有の) 機能として，call-by-name で引数を渡すこともできます。 文法的には，むしろこちらが Algol 60 本来の機構であり，call-by-name で渡すにはわざわざその仮引数を value 節で指名する必要があります。 本節では call-by-name の引数渡しの実現を考えます。

11.1 クロージャによる実現方法

§2 で述べたように，call-by-name による引数渡しは， 今の目で見れば，Scheme などに見られるクロージャを，ある制限された形式で渡しているものとみなせます。 ですから，もしも処理系のターゲット言語にクロージャがあれば，その実装は少なくとも原理的には簡単です。 例えば， 

procedure P(a);
  … foo(a) …

P (x + y);

のような Algol コードは，次のような Scheme のコードに直訳できます。 

(define (P a)
  … (foo (a)) …

(P (lambda () (+ x y)))

翻訳方法は簡単です。 call-by-name で実引数として式 x + y が与えられたとき，これを 無引数のラムダ式 (lambda () (+ x y)) に変換します。 そして手続きの中で仮引数 a の値を取得する箇所では， a の出現をその無引数呼出し (a) に変換します。

一方，仮引数が代入の左辺に出現するときは，実引数を，代入を行う１引数のラムダ式に変換します。 

procedure P(a);
  … a := z; …

P (x);

のような Algol コードは，次のような Scheme のコードに直訳できます。 

(define (P a)
  … (a z) …

(P (lambda (value) (set! x value)))

ラムダ式の本体が評価されるとき，そこに出現する呼出し側の変数のための正しい環境が静的スコープの 機構によって正しく再現されますから，この方法で正しく call-by-name を実現できます。 むしろ，call-by-name の機構の汎用化として Scheme のクロージャが考案されたとみるのが妥当かもしれません。

一般の場合，仮引数は代入の右辺にも左辺にも出現する可能性がありますから， 実引数として，無引数のラムダ式と，１引数のラムダ式のペアを渡すようにします。 つまり，いわゆる getter 関数と setter 関数のペアを渡すわけです。 

(P (cons (lambda () x)
         (lambda (value) (set! x value))))

ラムダ式については形式的意味論がよく研究されていますから，call-by-name のこのような取り扱いは，言語の実装に利用できるほか，言語の厳密な意味論の議論にも有用でしょう。

11.2 本処理系の実現方法

しかし，Algol の call-by-name の機構は，クロージャに相当するものをファーストクラスの値として扱わない (つまり，他の変数に格納して，呼出しの終わった後まで持ち越せない) ことから，実装に役立つ性質を持ちます。

したがって，本処理系では，次の実現方法をとることにします。



0.4 版 Interpreter.py の Frame クラスの定義を示します。call-by-name のとき (つまり by_value 属性が偽のとき)，実引数の構文木を eval_expression メソッドで評価せずにそのままフレーム内に格納します。 

class Frame:
    def __init__(self, procedure, args, caller, interp):
        assert isinstance(procedure, ProcedureQuantity)
        self.procedure = procedure
        self.caller = caller
        self.level = procedure.level
        params = procedure.params
        self.vars = [None] * (len(params) + len(procedure.locals))
        for (i, exp) in enumerate(args):
            q = params[i]
            # XXX 単純変数のみ 型検査なし
            assert q.quantity_class is SimpleVariableQuantity
            if q.by_value:
                exp = interp.eval_expression(exp)
            self.vars[i] = exp
        print " FRAME %s %s" % (self, self.vars)

    ……

eval_expression メソッドでは，仮引数の値を評価するとき， それが call-by-name によるものだったら，得られた変数値 v を実引数式の構文木とみなし，self.stack_pop() してからさらに (再帰的に) 評価します。 

    def eval_expression(self, e):
        "構文木のノード e を式として評価する。"
        ……
        elif isinstance(e, Identifier):
            q = e.quantity
            if isinstance(q, ProcedureQuantity):
                return self.call_function(q, [])
            # 変数ならば quantity の束縛値をとる
            # XXX 単純変数のみ
            elif isinstance(q, SimpleVariableQuantity):
                frame = self.display[q.level]
                return frame.vars[q.offset]
            elif isinstance(q, FormalParameter):
                assert q.quantity_class is SimpleVariableQuantity
                frame = self.display[q.level]
                v = frame.vars[q.offset]
                if q.by_value:
                    return v
                else:
                    current_frame = self.stack_pop()
                    try:
                        return self.eval_expression(v)    
                    finally:
                        self.stack_push(current_frame)
            ……
        else:
            ……

評価後は，try … finally でスタックを復旧します。 もしも実引数式を評価しているとき，そこから呼び出した関数の本体から goto 文で大域脱出したとしても， §10 で議論したように，今この時点のスタックを畳むまえに (caller=None によって) 必ず GoToException 例外でこの場所を通過します。 その場合でも finally 節は必ずその道すがらスタックを復旧します。

代入についても同様です。 仮引数に格納された構文木を得た後，self.stack_pop() してから，左辺式として (再帰的に) 解釈します。 

                frame = self.display[q.level]
                exp = frame.vars[q.offset]
                current_frame = self.stack_pop()
                try:
                    self.do_assignment(exp, rhs)
                finally:
                    self.stack_push(current_frame)

11.3 多重の call-by-name

前節で述べた実現方法についてちょっと考えると，なにもスタックトップのフレームを実際に pop しなくても，display のポインタだけ一時的にすげかえればよさそうに思えます。 どのみち goto 文によるスタックの畳みも，caller=None が障壁となって，finally 節の通過前に現在のトップに及ぶことはありませんから， 変数参照に使われる display はともかく，スタックはこの際どうとでも出来そうに思えます。

しかし，call-by-name の引数が，さらに別の手続きの call-by-name の引数として再び引き渡される場合を考えると，現在の方法がよいことが分かります。 スタックトップを実際に pop しない場合，なんらかの方法で，次にすげかえるべき display はどれかという情報を引き渡す必要があります。

サンプル・プログラム E_call_by_name.txt を用意したので，これで考えてみましょう。 

begin
  procedure P(x); value x; integer x; begin
    integer procedure F; begin F:= x; x := x * 10 end;
    Q(F)
  end;

  procedure Q(x); integer x;
    R(x + x);

  procedure R(y); integer y;
    S(y + y + y);

  procedure S(z); integer z;
  begin integer a; a := z end;

  P(1)
end

手続き P の内部で定義されている関数 F を呼び出す式が， 手続き Q，R，S へと，評価されることなく call-by-name で渡されます。 実際に関数 F が呼び出されるのは，手続き S の中で代入文の右辺として仮引数 z が評価されるときです。 このとき，手続き S の仮引数 z が，手続き R の仮引数 y を使った式 

y + y + y

へと展開されます。y は手続き Q の仮引数 x の式 

x + x

へと展開され，そしてそれは手続き P の F の関数呼出しへと展開されますから， 

(F + F) + (F + F) + (F + F)

という式が評価されます。ここで F は１回呼び出されるごとに 手続き P の call-by-value の仮引数 x (実引数により 1 に初期化されている) を自身の結果の値とし，さらに副作用として x を 10 倍しますから，結局， 

1 + 10 + 100 + 1000 + 10000 + 100000 = 111111

が評価結果として得られます。 ちなみに，手続き P の call-by-value の仮引数 x は， 手続き Q の call-by-name の仮引数 x と同名ですが， スコープが別なので別々の変数になります (実装上は，名前解決 の時点で， スコープにしたがって別々の Quantity インスタンスに結びつけられますから， 同名だからといってインタープリタが混同することはありません)。

前節で述べた実現方法では，このように call-by-name による引渡しが多重になっても， self.stack_pop() で順に呼出し元をさかのぼりますから， プログラムを正しく実行することができます。 

$ ./Interpreter.py E_call_by_name.txt
 FRAME (main):0@7909e0 []
 FRAME P:1@790f58 [1]
 FRAME Q:1@7907b0 [F@de878]
 FRAME R:1@790558 [(x@dedc8 + x@dedc8)]
 FRAME S:1@790508 [((y@790800 + y@790800) + y@790800), None]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 1: <type 'int'>
 SET P:1@790f58[0] := 10: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 10: <type 'int'>
 SET P:1@790f58[0] := 100: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 100: <type 'int'>
 SET P:1@790f58[0] := 1000: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 1000: <type 'int'>
 SET P:1@790f58[0] := 10000: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 10000: <type 'int'>
 SET P:1@790f58[0] := 100000: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 FRAME F:2@7904b8 []
 RESULT OF F:2@7904b8 := 100000: <type 'int'>
 SET P:1@790f58[0] := 1000000: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, F:2@7904b8]
 SET S:1@790508[1] := 111111: <type 'int'>
 RETURN [(main):0@7909e0, P:1@790f58, Q:1@7907b0, R:1@790558, S:1@790508]
 RETURN [(main):0@7909e0, P:1@790f58, Q:1@7907b0, R:1@790558]
 RETURN [(main):0@7909e0, P:1@790f58, Q:1@7907b0]
 RETURN [(main):0@7909e0, P:1@790f58]
 RETURN [(main):0@7909e0]
$

12. インタープリタ - のこりの言語要素

この第２部では，第１部での PLY による構文解析をうけて，名前解決および Algol に特徴的な局所・非局所的 goto と call-by-name の引数渡しのインタープリタによる実現について議論し，実装してきました。 のこりの言語要素のほとんどは他のプログラミング言語にもよく見られるものです。 いささか退屈な残りの部分を実装します。

実装の方針は次のとおりです。

今回の変更分として，Types.py を 0.5 版 に， Interpretr.py も 0.5 版 に差し替えてください。 Algol 60 修正報告書に記述された (組込みの関数を除く) 言語本体の言語要素は，すべて実装していますが， 型の不一致の検出は完全ではありません。 正しい Algol 60 プログラムは，インタープリタにバグが残っていなければ，正しく動くはずですが， 型に矛盾があるプログラムもまた，誤りが検出されることなく動くことがあります。

言語仕様からの意図的な逸脱として，own 変数以外の変数の初期値を Python の None にしています。 Algol 60 修正報告書 5.1.3節では，そのような 変数の初期値として変数の型の範囲の何らかの値をとるとだけ規定しています。 したがって，典型的な実装では，実際には初期化せずにゴミの値を入れたままにできます。 正しい Algol 60 プログラムはこの値に依存すべきではありません。 初期値を None にしておけば，そのような初期化されていない変数のうかつな参照を検出することができます。


目次へ 第３部へ

Copyright (c) 2008 Oki Software Co., Ltd.