先月のコラムで説明したように、以下の点が理解できれば、元のコードを入手できるかどうかは問題になりません。

• 構成用スクリプトをどう見分けるか
• 許可する構成をどのように選択するか
• どんな場合にブラック・ボックス拡張性が必要かを判断する
• 拡張性を構築した場合により複雑になるのはどんな点か
• 構成用スクリプトを用意するとは、実際には 言語を作成しているのだということ

さらに前回の記事で説明したように、S式を使用すると、アプリケーションのブラック・ボックス拡張性を可能にしながら、短時間で効率的に構成言語をセットアップできます。今回の記事ではS式についてさらに詳しく解説するとともに、S式を使って、特定アプリケーション用の構成言語を迅速かつ簡単にセットアップする方法を例示します。

S式とは何か

S式とは、要素のリストを括弧で区切って表した構文表現です。次の3種類があります。

• 空の要素リスト
• 空ではない要素リスト
• 単一原子の要素 (たとえば1つの単語)

S式は構文解析しやすいので、構成言語に非常に適しています。一般的なS式パーサー (構文解析プログラム) を使ってデータをプログラムに読み込み、その後、式がより具体的な構文制約に適合するかどうかを検査することもできます。それで、従来型のパーサーのような作成および保守に伴う余分の労力やオーバーヘッドを避けつつ、入力データの構文解析の大きな利点 (入力の誤りを早期に発見したり、セキュリティーを追加することなど) を享受できます。また、構文解析ルーチン生成システムによって作成されたパーサーとは異なり、構文エラーの元を突き止めるのに役立つ正確なエラー・メッセージを出力することが可能です。

"S" がXMLよりも優れている点

先回の記事で説明したように、XMLベースの構成言語を使用した場合にも、多くの面でS式と同じ利点が得られます。S式ベースの構成言語がXMLよりも優れている点は、何よりもS式がきわめて軽量で、すばやくセットアップできることです。

さらに、S式ベースの構成スクリプトの方が、XMLベースの同等のスクリプトよりも見やすく、編集しやすい場合が多いのです。以下にS式ベースの構成スクリプトをいくつか例示しますが、仮にそれらをXMLにしたらどうなるか考えてみてください。

上に戻る

例: マクロ・サポートをエディターに追加する

ユーザーが一連のプリミティブ操作の組み合わせを定義できるよう、簡単なマクロ・サポートをテキスト・エディターに追加するとしましょう。さらに、ループ構造や再帰構造のサポートを追加することもできるでしょう。

そのようなマクロの一例を以下に示します。

                
(define (cutAndPasteAtEnd)
 (sequence
  (cut HIGHLIGHTED_TEXT)
  (move-to END_OF_DOCUMENT)
  (paste CLIPBOARD))

この構成言語の構文とセマンティクスをまだ説明していませんが、読者はこのスクリプトの意図をおそらく想像できるでしょう。アプリケーション・ユーザーがしばしば実行する、テキストに対する一連のcut、move、paste 操作です。

構成言語に実際に組み入れたいようなスクリプトをサンプルとして書くと、言語作成の効果的な第一歩となります。実際、このようなサンプルは、そのインタープリターの優れた一組の単体テストを作成するのに役立ちます。

以下は、より複雑なマクロの例です。

                
(define (find-and-replace target replacement)
 (move-to BEGINNING_OF_DOCUMENT)
 (while (not AT_END)
  (cut NEXT_WORD)
  (if (equals CLIPBOARD target)
      (paste replacement)
      (paste target))
  (move-to NEXT_WORD)))

ここでもまた、このスクリプトがfind-and-replace (検索して置換) の実装をアプリケーションのスクリプト言語で表したものだと予想できるでしょう。スキーム型構文について精通していない読者のために、少しの点を解説します。

• すべての操作は接頭表記法 を使用します。このスタイルによって構文解析はさらに簡単になりますが、(たとえば、通常は2項演算子として書かれるequals のような) いくつかの操作の外観は、やや奇妙で洗練されていないように見えます。
• 他のほとんどの言語と同様に、if 文は条件文節、結果、代替 の3つの部分から成り、この順序で書かれます。しかしここでも、構文解析を簡単にするために、代替を表すelse キーワードを省略しました。

この例は、機能が十分に豊富なスクリプト言語をアプリケーションに追加することにより、拡張性を実現できることを示しています。元のソース・コードを変更せずに、いや表示さえせずに、あらゆる種類の新機能を追加できます。

上に戻る

例: スクリプト言語を決定する

このようなスクリプト言語を実装するには、まず、その言語がどんなものかを正確に指定する必要があります。つまり、構文とセマンティクスを確定しなければなりません。

BNF表記を使って、以下のように構文を指定することができます。

                
<script> ::= (<definitions> <expression>)
<definitions> ::= <empty>
                | <definition> <definitions>
<definition> ::= (define (<var> <args>) <statement>)
<args> ::= <empty> | <var> args
<statement>   | (cut <name>)
              | (paste <name>)
              | (move-to <name>)
              | (sequence <statements>)
              | (if <expression> <statement> <statement>)
              | (while <expression> <statement> <statement>)
              | (return <expression>)
              | (<var> <args>)
<statements> ::= <empty>
               | <statement> <statements>
<name> ::= <var>
         | <constant>
<expression> ::= <name>
               | (not <expression>)
               | (or <expression> <expression>)
               | (and <expression> <expression>)
               | (equals <name> <name>)
               | (<var> <args>)
<var> ::= any word consisting of only letters and numbers
          (but starting with a letter).
<constant> ::= BEGINNING_OF_DOCUMENT
             | END_OF_DOCUMENT
             | AT_END
             | CLIPBOARD

詳細

この言語にはプロシージャー定義が含まれることに注目してください。これによって、ユーザーは頻繁に使う一連の操作を抽象化して、さまざまな引数や値を渡すことによってこの抽象化を多くの場所で適用できます (これは、Java言語のメソッド定義に似ています)。今回の例では、こうした定義のシーケンスと、それに続くひとつの式からなるスクリプトを定義します。

この簡単な言語には、以下のような少しの点が欠けています。

• プロシージャー内の複数の変数をバインドするlet 式:余分のプロシージャー定義を使えばlet式をシミュレートできますが、言語の一部として組み込む方が便利です。
• 代入ステートメント
• 静的タイプ・システム

とくに静的タイプ・システムを追加すれば、スクリプトを実行する前にインタープリターがたくさんのエラーを検出できるでしょう。

一方、静的タイプによって言語はより長くなり、その結果、本当のエラーを含むプログラムだけでなく、正常に実行される一部のプログラムをも拒絶するようになることは避けられません。この理由で、(短いプログラムとして書かれることの多い) スクリプト言語では、静的タイプはしばしば除外されます。今回の例でも除外しますが、読者が希望に応じてこれを追加できない理由はありません。

上に戻る

3段階からなるパーサーの作成

言語の文法ができました。次はパーサーの作成に取りかかります。この点において、S式の利点が大いに発揮されます。従来のような2段階 (トークン化および構文解析) からなるパーサーを書く代わりに、もう1段階を加えることによって、処理全体を大幅に単純化できます。

追加の段階は、トークン化と、構文木への解析との間に入ります。入力を、S式による内部表記のセクションに分けます。このセクション分け処理は基本的に括弧マッチングに相当しますが、この処理によって構文解析はずっと単純になります。

ストリームの中から表記を取り出す

トークン分割プログラム (たとえばjava.util.StreamTokenizer、または入力が小さい場合にはStringTokenizer) を使って、データをトークンのストリームに変換したとしましょう。各トークンは、左括弧、右括弧、または1つの単語のいずれかとします。

このストリームを扱う最も手軽な方法は、スタックです。リスト5では、どんなトークン分割プログラム (tokenizer) をも扱えるアダプター付きインターフェースStackI が定義されています。こうすれば、特定のトークン分割プログラムの詳細を心配せずに、プログラムの構造に集中できます。その後、このストリームからS式表記を構築するメソッドを作成することができます。

基本的な処理は、まずストリーム内の最初のS式を構文解析し、S式の後に何もないことを判別します (プログラム全体が1つの巨大なS式ですから)。複雑なS式の各要素はそれ自体がより単純なS式であるため、S式の構文解析は再帰的に定義できます。

                
import java.util.LinkedList;
import java.util.*;

class SExpParseException extends Exception {
  public SExpParseException(String msg) {
    super(msg);
  }
}


interface StackI {
  public Object peek();
  public Object pop();
  public Object push(Object o);
  public boolean empty();
}

abstract class SExp {
  
  public static final String LEFT_PAREN = "(";
  public static final String RIGHT_PAREN = ")";
  
  public static SExp parseSExp(StackI tokens) throws SExpParseException {
    SExp nextSExp = parseNextSExp(tokens);
    if (tokens.empty()) {
      // The stack of tokens consisted of a single S-expression
      // (with possible subexpressions), as expected.
      return nextSExp;
    }
    else {
      throw new SExpParseException("Extraneous material " +
                                   "at end of stream.");
    }
  }
  
  public static SExp parseNextSExp(StackI tokens) throws SExpParseException {
    if (tokens.empty()) {
      throw new SExpParseException("Unexpected end of token stream.");
    }
    else { // tokens.pop() succeeds
      Object next = tokens.pop();
      
      if (next.equals(LEFT_PAREN)) {
        // The S-expression is a list. Accumulate the subexpressions 
        // this list contains, and return the result.
        SList result = new SEmpty();
        
        while (! tokens.empty()) { // tokens.pop() succeeds
          next = tokens.peek();
          
          if (next.equals(RIGHT_PAREN)) {
            // We've reached the end of the list. We need only
            // pop off the ending right parenthesis before returning.
            // Since subexpressions were accumulated in the front
            // of the list, we must return the reverse of the list
            // to reflect the proper structure of the S-expression.
            tokens.pop();
            return result.reverse();
          }
          else {
            // Recursively parse the next subexpression and
            // add it to result.
            result = new SCons(parseNextSExp(tokens), result);
          }
        }
        // If we haven't yet returned, then we've reached the end
        // of the token stream without finding the matching right
        // paren.
        throw new SExpParseException("Unmatched left parenthesis.");
      }
      else if (next.equals(RIGHT_PAREN)) {
        // A right parenthesis was encountered at the beginning of
        // the S-expression!
        throw new SExpParseException("Unmatched right parenthesis.");
      }
      else { 
        // The next S-expression is an atom.
        return new Atom(next);
      }
    }
  }
}

abstract class SList extends SExp {
  abstract SList reverse();
}

class SEmpty extends SList {
  public String toString() {
    return "( )";
  }

  SList reverse() {
    return this;
  }
}

class SCons extends SList {
  public SExp first;
  public SList rest;
  
  public SCons(SExp _first, SList _rest) {
    this.first = _first;
    this.rest = _rest;
  }

  SList reverse() {
    SList result = new SEmpty();
    SList elements = this;
    while (! (elements instanceof SEmpty)) {
      result = new SCons(((SCons)elements).first, result);
      elements = ((SCons)elements).rest;
    }
    return result;
  }
}

class Atom extends SExp {
  public Object value;
  
  public Atom(Object _value) {
    this.value = _value;
  }
}

構文木を解析するクラスを定義する

さて、生のトークン・ストリームを構文解析することに比べると、S式を解析して構文木にすることなど朝飯前です。しかし、これを行うには、文法内のそれぞれの構文構造ごとに個別のクラスを定義すべきでしょう。

                
import java.util.LinkedList;
abstract class SyntaxTree {
  public abstract Object accept(SyntaxTreeVisitor that);
}
class Script extends SyntaxTree {
  LinkedList definitions;
  Expression body;
   public Script(LinkedList _definitions, Expression _body) {
   this.definitions = _definitions;
   this.body = _body;
  }
  public Object accept(SyntaxTreeVisitor that) {
    return that.forScript(this);
  }
}
abstract class Statement extends SyntaxTree {}
class CutStatement extends Statement {
  Name name;
  public CutStatement(Name _name) {
    this.name = _name;
  }
  public Name getName() {return this.name;}
  public Object accept(SyntaxTreeVisitor that) {
    return that.forCutStatement(this);
  }
}
...
abstract class Expression extends SyntaxTree {}
...
abstract class Name extends SyntaxTree {}
...
abstract class SyntaxTreeVisitor {
  public abstract Object forScript(Script that);
  public abstract Object forCutStatement(CutStatement that);
  ...
}

このように続いてゆきます。文法内のそれぞれの非終端記号ごとに抽象クラスが必要であり、その非終端のそれぞれの形態ごとに具象クラスが必要です。さらに、このクラス階層の上にvisitorも定義すべきでしょう。

概念を示すために、実際に必要なコードのごく一部しかご紹介しませんでした。これを拡張するのは単純です。このようなコードは、コードの自動生成用として有力な候補です。

構文解析メソッドを再帰的に定義する

こうしてクラスをすべて定義した後、それぞれの構文構造ごとに構文解析メソッドを再帰的に定義できます (たとえば、parseStatement、parseExpression)。

それぞれのメソッドは、1つのS式を入力とします。本体には大きなif-then-else 文があり、SExp の最初の要素を検査して、それがどの構文構造に対応するかを判別します。その時点では、単にSExp の形式がその構造の有効な形式に一致するかどうかを検査し (たとえば、if 文に1つの式と2つの文、合計3つのコンポーネントが含まれるかどうかを検査し)、適切なコンストラクターを呼び出して、サブコンポーネントを再帰的に構文解析するだけです。

例として、if 文を構文解析する様子がリスト6に示されています。

                
 parseStatement(SExp sExp) {
   ...
   }
   else if (sExp.nth(0).equals("if") && sExp.length() == 4) {
     return new IfStatement(parseExp(sExp.nth(1)),
                            parseStatement(sExp.nth(2)),
                            parseStatement(sExp.nth(3)));
   }
   ...
 }

このif-then-else の末尾には、S式が構文構造のどの有効な形式にも一致しないケースに対応するelse 節があります。その場合は、SyntaxError と適切なエラー・メッセージがthrowされます。

上に戻る

次のステップ: 評価

スクリプトがこの形式に解析された後は、変換処理の他の段階を簡単に実装できます。静的タイプ・システムを言語に取り入れる場合、ここにタイプ・チェッカーを組み込みます。

さらに、他のすべての言語制約のチェッカーをここに組み込みます。たとえば、クラス階層を含むスクリプト言語の場合、階層に循環が含まれないことを検査すべきでしょう。

こうしたさまざまな段階を実装する便利な方法は、各段階ごとに、構文木のvisitorを使用することです。そのようにすれば、ある特定の段階に対応するコード全体が1つの場所に収納されます。しかも、段階を簡単に追加できます。ただvisitorをもう1つ作成して、それをシーケンスに含めるだけです。その他のクラスにはまったく手を付ける必要がありません。

しかし今回のサンプル言語では、このような制約をまったく追加しません。それで、変換処理の最終段階である評価に移ることができます。構文解析後の他の段階と同じように、この段階もまた構文木のvisitorとして実装できます。ぜひそうすることを私はお勧めします。

visitor内のそれぞれのfor 文節は、特定形式のプログラム構造をどのように評価するかを記述します。今回の言語におけるプリミティブ操作の評価は、サポートするアプリケーションにおけるメソッド呼び出しに対応します。

                
class Evaluator extends SyntaxTreeVisitor {
  Application app;
  public Object forCutStatement(CutStatement that) {
    app.cut(that.getName());
    // A VoidObject is returned as the result of evaluating
    statements, to meet the signature of the for methods.
    return new VoidObject();
  }
  ...
}

より複雑な操作の場合、基礎となっているJava言語のプログラム構造を活用して、こうした操作を実装することができます。たとえば、if 構造およびwhile 構造を実装する例を以下に示します。

                
  public Object forWhileStatement(WhileStatement that) {
    while (that.getTest().accept(this).equals(new Boolean(true))) {
      that.getBody().accept(this);
    }
    return new VoidObject();
  }
  public Object forIfStatement(IfStatement that) {
    if (that.getTest().accept(this).equals(new Boolean(true))) {
      that.getConsequent.accept(this);
    }
    else {
      that.getAlternative.accept(this);
    }
    return new VoidObject();
  }
}

上に戻る

使用上のご注意

今回の言語を使ったスクリプト変換処理も、いよいよスクリプトを含むファイル (またはストリーム) を読み込んで、この記事で紹介したさまざまな段階の処理を行うだけとなりました。

アプリケーションのユーザーと開発者のどちらも、ソース・コードにまったく手を触れずに、アプリケーションをさまざまな方法で拡張できるでしょう。S式ベースの言語を使ったブラック・ボックス拡張性がこうして完成しました。

この記事は、アプリケーションの拡張性を実現することに関する4部からなるミニ・シリーズの最後です。これらの技法は、研ぎ澄まされたナイフ -- 諸刃の剣 -- であることに注意してください。コードを再利用する強力な手段になり得る反面、見境なく使用して安易に拡張性を追加した場合、非常に危険でもあります。アプリケーションの複雑さが制御不能なレベルに膨れあがる可能性があるのです。ですから、注意が必要です。

参考文献

• World Wide Web Consortium (W3C) には、XML のすべてを網羅する情報源があります。
  
  
• developerWorksのXMLゾーンは、受賞暦のあるXML開発者向けのテクニカル情報のソースです。
  
  
• W3CはBNF表記の使用法に関する8つの表記規則を提供しています。
  
  
• BNF表記の簡単な歴史および紹介をご覧ください。
  
  
• マサチューセッツ工科大学 (MIT) の電子工学/コンピューター・サイエンス学科の教授Ronald Rivestは、特に公開鍵インフラストラクチャーの新しい設計であるSDSI (シンプル分散セキュリティー・インフラストラクチャー、Simple Distributed Security Infrastructure) において、S式、およびさまざまなセキュリティー・アプリケーションにおけるその使用について論じています。
  
  
• JUnit Webサイトは、プログラム・テスト・メソッドを扱った、さまざまな情報源からの興味深い記事へのリンクを多数紹介しています。
  
  
• 2回シリーズの第1回、高信頼性の銀行用システム: J/XFSの紹介 (Christoph Czernohous著、developerWorks、2001年8月) では、既存のシステムにJavaプラットフォーム用の会計サービス拡張機能 (Extensions for Financial Services、J/XFS) を組み込むことについて説明されています。
  
  
• Ericの「Javaコードの診断」の全記事をご覧ください。
  • バグ・パターン： Javaプログラムで頻発しがちなバグの分析と修正
  • 「宙ぶらりん複合型」バグ・パターン： ヌル・ポインター例外の最もよくある原因を鎮圧する
  • 「ヌル・フラグ」バグ・パターン： 例外状況を表すフラグとしてヌル・ポインターを使うことを避ける
  • 「二段たどり」バグ・パターン： 再帰的なクラス・キャストという概念上のエラーを最初から克服する
  • うそつきビューのバグ・パターン： GUIの最良の友になってうそつきビューを暴き出しましょう
  • 破壊工作データのバグ・パターン： 隠れたデータ爆弾が奇妙なクラッシュの原因かもしれません
  • 破綻したディスパッチのバグ・パターン： 引き数のアップ・キャストによって、不正確なメソッドの呼び出しを修正する
  • Javaコードのパフォーマンスを向上させる： 末尾再帰変換はアプリケーションの速度を向上させる可能性はあるが、すべてのJVMで可能な操作ではない
  • 正しいメソッド呼び出しのためのRecorderによるテスト： メソッドの呼び出しを順序正しく行うために、ユニット・テストのためのRecorderを記述する
  • 型詐欺師のバグ・パターン： タグを使用したオブジェクトの型の区別は、ラベルの貼り違えにつながる可能性がある
  • クリーンアップ・コード散在バグ・パターン： リソースの獲得および解放を同時に実行する
  • 虚偽の実装というバグ・パターン: 第1回： 前提とした不変条件がインターフェースの破壊を招くこともある
  • 虚偽の実装というバグ・パターン: 第2回： 表明とユニット・テスト - バグを除去するための実行可能なドキュメンテーション -
  • 「みなし子スレッド」バグ・パターン： マスター・スレッドが自滅し、その他のスレッドが生き残っていると、どうなるか?
  • 「テスト可能な」アプリケーションの設計： 以下に示す7つの原則は、テストを念頭においてコード設計を行う際のもとになるものです
  • 拡張可能アプリケーションの設計 第1回： ブラック・ボックス、オープン・ボックス、またはガラス・ボックス: どんな場合にどれがふさわしいか?
  • 拡張可能アプリケーションの設計 第2回： ガラス・ボックスはどんな時、どこで、どのように最もよく機能するかを調べる
  • 拡張可能アプリケーションの設計 第3回： ブラック・ボックスはどんなとき、どこで、どのように最もよく機能するかを調べる
  
  
  
• developerWorks Javaテクノロジー・ゾーン には、Javaに関するその他の参考文献があります。
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• S式とは何か
• 例: マクロ・サポートをエディターに追加する
• 例: スクリプト言語を決定する
• 3段階からなるパーサーの作成
• 次のステップ: 評価
• 使用上のご注意
• 参考文献
• 著者について
• コメント