日本ソフトウェア科学会第 33 回大会 (2016 年度) 講演論文集

OMeta のための衛生的マクロ定義機構導入方式
星野 友宏

高桑 健太郎渡部 卓雄

本研究では，OMeta を用いて定義された言語に衛生的マクロの定義機構を導入する手法を提案し，例題の記述を通してその有用性を明らかにする．OMeta は PEG による強力なパターンマッチング機構を備えた言語であり，構文解析器や言語処理系の記述に適している．OMeta によって定義された言語にマクロの定義機構を追加する際，マクロ定義およびマクロ展開の記述のために対象言語の構文をそれぞれ拡張する必要がある．また，マクロを衛生的にするためにはマクロ展開機構で識別子のスコープを管理する必要がある．提案手法は，これらに共通する機構をOMeta のモジュールとして提供し，既存の対象言語にマクロ定義機構を容易に導入できるようにするものである．

Programming languages with macro definition mechanisms often need special treatment for parsing macros.
If a macro introduces a new syntax to a language, an extended parser is needed to recognize a code written
using the macro. Also, the language might use some specific mechanisms such as pattern matching to define
macros. In this paper, we propose a method of introducing hygienic macro definition mechanisms into languages defined in OMeta, an object-oriented language with PEG-based general-purpose pattern matching.
Using the proposed method, extended parsers for macro definition are automatically generated from thespecifications of macro definition mechanisms.

題点を回避する仕組みを備えた衛生的マクロ機構と1 はじめにいうものが考えられているが、現状では衛生的マクロプログラムにおいて、よく用いられるコード片に名機構を言語機能として持つ言語は Scheme などの一前を付けて再利用を可能にするマクロは、プログラ部の言語に留まる。

ミングの可読性や効率の向上、およびある種のメタ

本論文では、OMeta [2] を用いて実装された言語処プログラミングを可能にする便利な言語機構である。

理系に対し、元の言語処理系にはほぼ手を入れずに現状では、マクロを備えている言語は限られている。

衛生的マクロ機構を導入する手法を提案する。本手

C の#defineのような単純な文字列置き換えによるマ法を用いることで、DSL などを開発する言語開発者

クロであれば、m4 などのプリプロセサを使うことでは開発中の言語に比較的容易に衛生的マクロ機構を言語を問わず簡便に利用できるが、この方法にはいく導入することが可能になる。これにより、DSL の構つかの問題点があることが知られている [1]。その問文の変更等に比べて素早いプロトタイピングが可能∗

A Method for Implementing Hygienic Macro Definers for OMeta
This is an unrefered paper. Copyrights belong tothe Authors.
Tomohiro Hoshino, Takuo Watanabe, 東京工業大学・情報理工学院, School of Computing, Tokyo Instituteof Technology.
Kentarou Takakuwa, 東京工業大学・工学部情報工学科,
Department of Computer Science, Tokyo Instituteof Technology.になり、言語のユーザの利便性向上につながるといった効果が期待できる。
提案手法では、言語処理系の字句解析器に拡張を施し、さらに構文解析に関するデータフローの途中に、構文解析器拡張モジュール、マクロ定義管理モジュー
ル、マクロ展開器モジュールを挿入することにより、最終的に元の文法に従う（マクロを含まない）抽象構文木を生成できるようにしている。我々はこの手法を例題として作成した簡単な手続き型言語に対して適用し、提案手法の有効性を確認した。

# define SWAP (x , y ) \{ int tmp = x ; x = y ; y = tmp ; }本論文の構成を記す。まず次節で本研究の背景について述べ、次に第 3 節では提案手法の概要について述べる。第 4 節では例題として作成した言語の仕様と実装について簡単な説明を述べ、続く第 5 節でその実装を通して提案手法の有用性について述べる。第 6節では現状の制約と今後の課題について述べる。第 7節で関連研究について述べ、第 8 節でまとめを行う。

コード 1

SWAP マクロint main ( void ) {int a = 0;
int tmp = 5;
SWAP (a , tmp ) ;printf ( " %d , ␣ % d \ n " , a , tmp ) ;return 0;}

2 背景

コード 2

SWAP マクロの利用例

2. 1 OMeta
OMeta [2] は、パターンマッチング機構を備えたオブジェクト指向言語であり、Parsing Expression

Grammar (PEG) を基礎とする文法定義のための構文と、オブジェクト指向の特徴である継承やオーバーライド、親文法のルール呼び出しといった各種操作

int main ( void ) {int a = 0;
int tmp = 5;
{ int tmp = a ; a = tmp ; tmp = tmp ; }printf ( " %d , ␣ % d \ n " , a , tmp ) ;return 0;}をサポートしている。また、OMeta は JavaScript
コード 3(ECMAScript5) を含む様々な言語上で実装されていコード 2 の展開例

る。OMeta による定義はそれぞれのホスト言語で動作するプログラムへと変換することが出来る。

ロ SWAPをコード 1 のように定義する。このマクロはOMeta は言語設計とそのプロトタイピングにおいコード 2 のように使って 2 つの変数（ここでは aとて強力な基盤を提供するが、OMeta そのものには、tmp）の内容を交換することを意図して定義したもの

OMeta 上で作成された処理系に対してマクロ機構をである。

付与するためのサポートはない。そこで、本研究では

コード 2 を展開して得られたコード 3 は「0, 5」

OMeta の JavaScript 実装を用いて、動的に OMetaという結果を出力するが、これは意図した結果であるの定義を生成し言語処理系を拡張することにより、 「5, 0」と等しくない。この原因は、マクロが展開さOMeta 上で定義された言語処理系に対してマクロ機れる直前で定義されている変数 tmpを、マクロ内で一構を付与することを試みた。

時変数として定義される tmpが隠蔽してしまうことにある。これ以外にも、単純な文字列置き換えによるマ

2. 2 衛生的マクロ機構

クロ展開にはいくつかの問題があることが知られてコード片に名前を付けて、あたかも新たな言語機いる [1]。

構であるかのように再利用可能にする言語機構はマ

そのような問題を回避する仕組みを備えたマクロ

クロと呼ばれ、いくつかのプログラミング言語で利機構として、衛生的マクロ (hygienic macro) があ用可能になっている。例えば C では#defineにより、る。衛生的マクロの実現方式の一つである Syntactic

Scheme では define-syntaxによってマクロを定義でClosure [1] は、「マクロ定義時の環境を保存する」ときる。

いうアイデアを元にしている。本研究ではこのアイデ

C におけるマクロは単純な文字列置き換えに基づアを利用し、提案方式で作られるマクロ定義機構にくものであるため、以下の例に示すように、展開後よって定義されるマクロが衛生的マクロとなるようにの名前の衝突が生じることがある。まず、C のマクしている。

MACRO_FROM

3 提案手法⟪ マクロ構文定義 ⟫本手法でマクロ機構を既存言語の処理系へ実装するためには、主に以下の手順を行う。

1. 字句解析器の拡張

MACRO_TO⟪ コードテンプレート ⟫
MACRO_END

2. 構文解析器拡張モジュールの実装
3. マクロ展開器モジュールの実装

図2

マクロ定義のための構文

この手順によって拡張された言語処理系（構文解析器）の構造は図 1 のようになる。構文解析器拡張モとが出来る。一方 ⟪ コードテンプレート ⟫ は展開後のジュールにより元の構文解析器がマクロによる新規コードの記述である。この記述はこのマクロ定義が出構文を取り扱えるように拡張され、マクロ展開器モ現するより前の（マクロによる拡張が導入される前の）ジュールによりマクロの衛生的展開が行われる。

構文によって行われる。加えて、⟪ マクロ構文定義 ⟫本手法で拡張された言語においてマクロを定義内でキャプチャされた部分構文木は、束縛するメタ変す る に は 、図 2 の よ う な 構 文 を 用 い る 。こ こ で数を@...@ で囲むことにより取得することができるよ⟪ マクロ構文定義 ⟫ は OMeta で記述されたマクロ構うにしている。

文の定義である。この定義では OMeta のキャプチャ機能を利用し、部分構文木をメタ変数へと束縛するこ

3. 1 字句解析器の拡張
まず、先述のマクロ定義構文を正しく受け取り処理できるように、字句解析器の拡張を行う。具体的には、オリジナルの字句解析器をもとに、メタ変数（@...@で囲まれた識別子）および図 2 で示したキー
ワード MACRO_FROM，MACRO_TO および MACRO_END をマクロ定義トークンとして認識できるように拡張した字句解析器を定義する。
拡張された字句解析器は、マクロ定義トークンの組を見つけた場合、MacroDefinition というトークンを生成する。このトークンには次のデータが含まれるようにする。

• マクロルール文字列：⟪ マクロ構文定義 ⟫ による文法定義 (OMeta の処理系に渡すため、文字列のまま格納)• マクロ展開木用トークン列：⟪ コードテンプレート ⟫ を、メタ変数を扱える拡張字句解析器を利用してトークン化したもの

3. 2 構文解析器拡張モジュール
図 1 中の Syntax Extenderが構文解析器拡張モジ
ュールに当たる。このモジュールでは、あらかじめ入図1

マクロ機構の構造力されたソースコード中に出現する全てのマクロを適切な条件を付け加えた上で処理してしまい、適切な全トークンの処理が終わった後、その時点での構ブロックスコープでマクロを処理できる構文解析器を

文解析器を MacroDefinitionトークンを適切に処理生成する。

できるように拡張し、それを Parser with Macro

Syntax Extender は、以下の項目に関する追跡・処理を行う。

• 全トークンへのインデックス付与Supportとして扱う。以上の処理により、入力されたソースコード中に出現する全てのマクロを適切な有効範囲で処理可能な拡張済み構文解析器が生成される。

• ブロックへのラベル付けとブロックスコープの追跡• MacroDefinitionトークンの処理• 全トークンの処理後にマクロ定義トークンを処理できるように構文解析器を拡張

3. 3 マクロ展開器モジュール
図 1 中の Macro Expanderがマクロ展開器モジュールに当たる。このモジュールでは、拡張済み構文解析器が生成した抽象構文木中のマクロ定義ノード・マク

全トークンへのインデックス付与 とブロックへのロノードを、マクロ内の環境がマクロ以外のプログラ

ラベル付けとブロックスコープの追跡は、構文解析器ム上の環境と衝突しないように対策を行いながら処がマクロの有効範囲を判定するために必要となる。

理を行い、最終的にマクロを含まない元の文法によっ

MacroDefinitionトークンの処理により、マクロを処理できるように構文解析器が拡張される。ここでは以下のような手続きが行われる。

• マクロルール文字列を OMeta 文法定義の文字列へ必要に応じて変換• マクロルール文字列から取得するべきメタ変数の列を取得• 取得したメタ変数の列を利用し、メタ変数を適切に受け取れるように拡張した構文解析器を生成ても生成が可能な抽象構文木を生成する。

Macro Expander は、基本的にはマクロを含む抽
象構文木を訪問しながら、以下の項目に関する追跡・処理を行う。

• プログラム上で定義される全てのシンボルの収集• プログラム上のブロックスコープを含む環境の追跡• マクロ定義ノードを発見した時に必要なシンボルのエイリアスを生成• 生成した構文解析器を利用して、マクロ展開木• マクロノードを発見した時にマクロ内一時変数用トークン列を解析し、マクロ展開用の抽象構文のシンボル名の変更を行いマクロ展開を実行木を得る

プログラム上で定義される全てのシンボルの収集• マクロを処理できるように現在の構文解析器をは、マクロ定義ノードを発見した時に必要なシンボル拡張し、拡張した構文解析器で現在の構文解析器のエイリアスを生成する時、プログラム上全体で衝を置き換える突しないシンボル名の生成を行うために必要になる。

• MacroManagerに、現在のブロックのラベル名、マクロ展開用の抽象構文木、メタ変数名の列を通知・登録
この処理は、MacroDefinitionトークンが検出される度に行われる。これにより、別のマクロ定義内でそれまでに定義したマクロを利用可能にしている。ここで拡張された構文解析器は、マクロのルールにマッチするトークン列を見つけると、マクロ展開に必要な情報 (マクロ名、メタ変数の内容) を含むノードを生成する。(以下、マクロノード とする)

この時は、ブロックを考慮せずにプログラムのコード上に現れる全ての変数・関数宣言を追跡し、収集を行う。
プログラム上のブロックスコープを含む環境の追跡は、マクロの展開を行う時に衝突しないシンボル名の生成を行うために必要になる。ブロックスコープは階層構造も含めて追跡を行う。
マクロ定義ノードを発見した時、まず該当するマクロの展開用構文木を訪問し、「マクロ内で定義されてなく、且つマクロ内で使用されているシンボル」を全て列挙する。これらのシンボルをマクロが定義時の環• 関数呼び出し境に依存しているシンボルとし、それらのシンボルを• 変数定義定義時の状態で展開されたマクロ内で使用可能にす• 変数参照るために、それらのシンボルにプログラム上で定義さ• 変数代入れる全てのシンボルと衝突しない別名シンボルを与• if 文える。その後、マクロ内の定義時依存シンボルをその• while 文

別名を利用するように適切に変更し、マクロ定義ノードの位置にエイリアスを生成するノード (つまり、エイリアスを定義する変数定義ノード) を追加する。これにより、まずマクロ内で定義されずに使用されている変数・関数などに関する環境を、マクロ定義時の状態に固定する。
マクロノードを発見した時、まず該当するマクロの展開用構文木を訪問し、マクロ内で定義されるシンボルを、ブロックスコープに関する情報と共に全て列挙する。これらのシンボルをマクロ内一時変数とし、それらのシンボルを定義及び使用するノードを、マクロノードが出現した時点で定義されている全てのシンボルと衝突しない別名シンボルを生成した上で、そのシンボルを定義・使用するように、ブロックスコープを考慮しながら適切に書き換える。これにより、マクロ内一時変数が誤ってプログラム上のシンボルを隠蔽してしまうことを防ぐ。その後、マクロの展開用構文木に含まれるメタ変数に関するノードを適切に該当する文法要素や識別子に置き換え、マクロ展開後の構文木をマクロノードの位置へ挿入する。
以上の処理により、衛生的なマクロ展開が行われ、元の文法に従う抽象構文木が生成される。

4 実装
本研究のケーススタディーのため、提案手法を用いてマクロ機構を実装する言語を設計した。本言語は手続き型言語の構造を持ち、以下のような特徴を持つ。

• 変数に型はない• ブロック• 四則演算・括弧による計算優先順位の明示
ここで、衛生的マクロを実現するために、注意して追跡を行うべき 2 種類の抽象構文木ノードがある。

1 つ目が「環境に対して変更を加える抽象構文木ノード」である。これは、実行された時点での環境に対して、シンボルを新たに加える操作を行うようなノードを指す。変数定義、関数定義などがこれに該当する。これを本論では環境変更要素 と呼ぶこととする。

2 つ目は「環境に対して問い合わせを行う抽象構文木ノード」である。これは、実行された時点での環境に対して、シンボルの内容を問い合わせたり、シンボルへの参照を得る操作を行うようなノードを指す。変数参照、変数代入、関数呼び出しなどがこれに該当する。これを本論では環境利用要素 と呼ぶこととする。
本研究で実装したマクロ機構では、マクロ展開器モジュールにおいてこれらの要素内のシンボル名を適切に操作することにより、衛生的マクロを実現している。
本研究では、概ね図 1 に従うプログラムを、OMetaの JavaScript 実装である OMeta/JS、JavaScript 実
行環境である Node.js、JavaScript をコンパイル結果として出力するオブジェクト指向言語の TypeScriptを用いて実装した。

5 例題
本節では、マクロの衛生性が問題となる 2 つの例• 関数は第一級オブジェクト

題を示し、本研究で設計したマクロ機構が衛生的と• ブロックによるレキシカルスコープを持つなっていることを示す。

サポートされる構文は以下のとおりである。

• 関数定義var flag = 1;
MACRO_FROM
alternateness ( Block : ctxa , Block : ctxb ) ;MACRO_TO
if ( flag ) {@ctxa@flag = 0;}
if ( not ( flag ) ) {@ctxb@
flag = 1;}
MACRO_END{
var flag = 0;
while ( operationLT ( flag , 10) ) {alternateness ( {print (5) ;}, {print (10) ;} );flag = flag + 1;}

var flag = 1;
var flag__at_2 = flag ;var not__at_2 = not ;{var flag = 0;
while ( operationLT ( flag , 10) ) {if ( flag__at_2 ) {{print (5) ;}flag__at_2 = 0;}
if ( not__at_2 ( flag__at_2 ) ) {{print (10) ;}flag__at_2 = 1;}
flag = _operationAdd ( flag , 1) ;}}コード 5

コード 4 の展開

すような対策付きのマクロ展開を行うことにより、こ}の問題を回避する。
コード 4

ブロックの交互実行マクロ

このように、マクロが依存する flagと notに対して、マクロ定義の出現箇所にエイリアスを作成し、そ5. 1 マクロが定義時の環境に依存する場合

れをマクロ内で利用することにより、プログラム上でマクロが定義時の環境に依存する例として、コー定義されうるシンボルとの衝突を回避するため、マド 4 のようなプログラムを考える。alternatenessマ

クロが定義時の環境に依存していても、依存するシ

クロは、実行される度に指定された 2 つのブロックがンボルについては環境が保存されることを保障する。

交互に実行されることを意図している。そのような機また、別名の作成時には作成した別名が本当に衝突し能を実現するため、このマクロでは flagという変数ていないかを再度チェックしているので、マクロ外のをマクロ定義前に宣言し、利用している。flagは保プログラムで flag__at_2のような変数を定義しても存されないといけないため、マクロ内一時変数として問題は起こらない。

ではなく、マクロの外に定義する必要がある。また、検証用言語には否定の演算子が無いため、not()という関数も中で使用されている。これもマクロ定義時の環境に依存する要素である。

5. 2 マクロ内で一時変数を使う場合
次に、マクロ内で一時変数を使う例としてコード 6のようなプログラムを考える。これは、第 2 節で示

しかし、このプログラム上では、マクロ外のプログした SWAPマクロを提案方式で実装した言語とマクロラムにも flagという変数が定義されているため、単機構に適応するように書きなおしたものである。第 2

純なマクロ展開ではマクロ内からの flagへの参照が節で触れたように、このプログラムはマクロ内で定義本来意図した変数への参照と異なってしまう。これにされた一時変数が意図せずマクロ外のプログラム上より、マクロの意図が損なわれる可能性が出てくる。の変数を隠蔽してしまい、マクロの意図が損なわれる提案方式で実装したマクロ機構では、コード 5 に示可能性を持っている。提案方式で実装したマクロ機構

MACRO_FROM
swap ( Identifier : lhs , Identifier : rhs ) ;MACRO_TO{
var temp = @lhs@ ;@lhs@ = @rhs@ ;@rhs@ = temp ;}MACRO_END• ポインタ・参照の仕組みを持つ言語の場合、ポインタ・参照が示すオブジェクトの保存を行っていないため、そのオブジェクトに関してマクロ定義時の状態が保存されることを保証しない• 式として取り扱えるマクロを定義できない• 再帰的定義は出来ない• マクロ内でマクロを定義することは出来ない
また、現在の設計では字句解析直後のトークンレベ

var temp = 2;
var other = 3;

ルでブロックスコープの追跡を行っているが、言語の構造によってはトークンレベルでは厳密なブロックス

swap ( temp , other ) ;コープの追跡が難しい可能性があることが分かってprint ( temp ) ;print ( other ) ;いる。
どのような言語に対して本手法が適用可能かにつ

コード 6

マクロ内で一時変数を使う例

いてもまだ実装例が足りておらず、手続き型言語以外の言語や実用言語に対して本手法が適用可能か十分

var temp = 2;
var other = 3;{
var temp__at_5 = temp ;temp = other ;other = temp__at_5 ;}print ( temp ) ;print ( other ) ;には分かっていない。本論文の執筆時点で Lisp 風の構造を持つ言語に対して本手法が適用できるかを試行しているが、本手法で提案したマクロ機構の構造をそのまま使用できない可能性があることが判明している。そのため、本手法が提案するマクロ機構の構造が十分一般的でないことも考えられ、今後マクロ機構の構造についてより議論を重ねていく必要があると考えている。

コード 7

コード 6 の展開

本手法はマクロ機構の実装の方針と仕様について述べるに留まっており、字句解析器の拡張はほぼそのでは、コード 7 のように対策付きのマクロ展開を行まま本研究での実装例と同じようにできるが、構文解うことによりこの問題を回避する。

析器拡張モジュールとマクロ展開器モジュールについこのように、マクロ内で定義された一時変数 tempては実装先の言語の構造・仕様に依存しているため、を、その時点で可視である環境に存在するシンボル、再利用できる箇所が少なく、実装コストはまだ高いと及びメタ変数で指定された変数・関数宣言・識別子と考えている。そのため、今後実装例を増やしていく中被らないようにリネームすることにより、プログラムで再利用可能な箇所を増やし、自動化可能な箇所を見上で定義された変数との衝突を回避し、マクロの意図つけていくことが必要であると考えている。

を保護している。

7 関連研究6 制約・今後の課題
本研究で設計・実装したマクロ機構には、以下のような制約が存在する。

甫水らによる研究 [3] では、動的に拡張できるパー
ザと Scheme 処理系に含まれる衛生的マクロ機構を用いて、JavaScript に対して表現力に優れた衛生的• 実装対象の言語がレキシカルスコープを持つこマクロ機構を付与する手法を提案している。この研究とを仮定しているため、ダイナミックスコープをでは、Scheme 処理系が持つ衛生的マクロのシステム持つような言語には適用できないを利用するため、ホスト言語と S 式間の変換を行う。

構文の言語に対する適用例を増やして提案手法の有

一方本研究のマクロ機構では、拡張後のパーザによっ用性を示すとともに、より洗練されたマクロ定義機構て得られた抽象構文木に対して直に訪問処理を行い、の導入方式を確立することを目指す。

マクロ定義時のマクロ展開時のそれぞれで決められた対策を行う。これによって条件付きで衛生的なマクロ謝辞展開を実現している。まだ表現力は豊かでなく、対象

本 研 究 の 一 部 は JSPS 科 研 費 26330079 お よ び

言語に対応する OMeta 定義 (字句解析器、構文解析15K00089 の助成を受けている．

器) や構文木訪問処理が書けることが必要になるが、マクロ機構を実現するのに必要な実行環境は 1 つで良参 考 文 献い (本研究では JavaScript のみ) という利点がある。

[1] Bawden, A. and Rees, J.: Syntactic Closures,
Proceedings of the 1988 ACM Conference on LISP
and Functional Programming, LFP ’88, New York,NY, USA, ACM, 1988, pp. 86–95.
[2] Warth, A. and Piumata, I.: OMeta: An ObjectOriented Language for Pattern-Matching, Symposium on Dynamic Languages (DLS 2007), ACM,
2007, pp. 11–19.
[3] 甫水佳奈子, 脇田建, 佐々木晃: 解析表現文法と Scheme
マクロ展開器を用いた JavaScript 向け Hygienic 構文
マクロシステムの実装, 情報処理学会論文誌プログラミング（PRO）, Vol. 6, No. 2(2013), pp. 85–101.

8 まとめ
本論文では、OMeta で実装された字句解析器・構文解析器からなる言語処理系に対して衛生的なマクロ機構を追加するための手法を提案し、例題として作成した言語に対して提案手法を適用することで、衛生的マクロ機構を実現できることを示した。今後様々な