OpeLa メインページ

OpeLa のジェネリクスに登場する演算子の考察

OpeLa 言語はジェネリクスを実現するためにいくつかの演算子を用います。 それぞれがどのような意図で選ばれたのか、逆に言えば、なぜそれ以外の記号にならなかったのかを説明します。

型リスト < >

C++ や Rust、Java などは、ジェネリクスの型変数を表す記法として < 型, 型, …… > を使います。 例えば C++ で任意の型のペアを表す構造体は次のように定義できます。

template <class T>
struct Pair {
    T a, b;
};
using MyInt = int;
int main() {
    Pair<MyInt> x = {2, 3};
    return x.a + x.b;
}

この記法の問題点は < や > が比較演算子としても使われることにあります。 端的に言えば Pair<MyInt> が Pair < MyInt という比較なのか、Pair< 型 > という構造なのかを区別しにくいということです。

C++ は、型を前方宣言しなければならないという制約により、Pair<MyInt> に出会うときには Pair と MyInt が指すものが分かります。 そのため、上記のような簡単な例であればそれほど文法解釈は難しくはありません。 構文解析の段階で Pair や MyInt が指すものを知る必要がある（意味解析の結果を使う）という点では、気持ち悪さはありますが。

OpeLa では型や関数の定義を、使用箇所より後ろに書くことができます。 そのため Pair<MyInt> の構文を解析する段階で Pair と MyInt が何を表すのかが不明だという前提に立たなければなりません。 もし、Pair と MyInt が普通の変数であれば変数同士の大小比較式があり、その後ろに余分な > がある、ということでエラーにしなければなりません。

ぱっと考えると、一旦ソースコードを後ろまでざっくり見て識別子を認識してから、戻ってきて詳しく構文を解析すればいいのでは、と思いますよね。 でも、それはプログラムが複雑になります。なぜなら、ざっくり見る、というのは前半の構文を多少あいまいに解釈する、ということだからです。 < が比較演算子でもジェネリクスの記号でも問題が起きないように、どちらの可能性も考えつつ読み進めるというのは、複数の可能性を保持しなければならず、処理が複雑になります。 また、このような判断が分かれるところは 1 箇所だけとは限りません。 判断が分かれる箇所の数を n とすると、2 の n 乗もの可能性を考慮しなければならないので、メモリも大量に必要になります。

その他の記号を検討する

< > という記号の問題は大きく 2 つあると思います。

1. 対にならない使われ方をしうる演算子である
2. 通常、値を期待するところで使われる演算子である

1 について。他の括弧類（( )、[ ]、{ }）と違い、< や > 単体で用いることがあるのが大きな特徴です。

2 について。通常、< あるいは > は、両辺に値を取り、結果として 0/1 という値を返す演算子です。

1 だけに着目すれば、他の括弧類を採用すれば回避可能です。例えば Pair[MyInt] などという表記が思いつきます。 構造的に A [ B ] となり、決して A [ B という中途半端な形にはなりませんので、構文木の大まかな形は [ ] の意味に依存せず決まります。

ただ、1 を回避したとしても問題が残ります。Pair[MyInt] が配列と添え字なのか、ジェネリック関数の具体化なのか区別が付かないのです。 これに関しては、一旦添え字演算子だと思って構文解析をしておいて、後でジェネリック関数の具体化であることが判明したら解釈を修正する、というやり方ができなくはないと思います。 ただ、プログラミングはそれなりに煩雑になりそうです。

仮に Pair[MyInt](1) という式があるとします。 この解釈としては、関数ポインタの配列 Pair があって、その MyInt 番目の要素を取ってきて呼び出す、という意味の可能性があります。 あるいは、ジェネリック関数 Pair を MyInt 型で具体化し、呼び出す、という意味かもしれません。 この両者の可能性を抱えたまま処理を進め、後で意味を確定するのは、面倒なプログラミングになること必至です。

( ) も多くの意味で使われる演算子なので、どの意味で解釈するかに揺れが発生します。 [ ] と ( ) は後置演算子（postfix operator）として使われるという共通点があり、同様の扱いにくさがあります。

実は { } は後置演算子としては今のところ使われないので、ジェネリック関数の具体化に使うのに適しているかもしれません。 ただ、将来的に 型 { 初期値 } という書き方でその型の即値を作る機能を入れたいので、そのための記号として取っておきたいなと思います。

型変換演算子 @

OpeLa 言語では型変換（キャスト）の記法は 値 @ 型 となっています。その当時、何も使われていなかった @ という演算子を、型変換のために使ったのです。 @ は at mark なので、型、すなわち kATa のもじりともなっており、ちょうど良いと思って採用しました。

今回、この型変換記法を拡張して 値 @ < 型リスト > と書けるようにすることで、ジェネリック関数の具体化を実現することにしました。 @ の後には型が来る、という原則を変えずに新しい機能を追加する、とてもスマートな拡張だと uchan は思います。

> = と >=

まだ些細な問題が残っています。型 Pair<int> の変数定義を次のように書いたとします。

var x Pair<int>={2,3};

字句解析器は > を、型リストの閉じ括弧ではなく >= という比較演算子として認識してしまうのです。

これは Pair<int> ={2,3}; とスペースを入れることで回避可能です。でも、プログラマにこのような変なルールを覚えてもらうよりは、コンパイラを賢くして解決したいです。

そこで、OpeLa コンパイラでは、一旦 >= という演算子として字句解析しつつも、構文解析の段階で解釈を変更することによって、この問題に対処しました。 型リストの閉じ括弧を期待する場面で >= に出会ったら、> と = の 2 つの演算子に分割して認識するのです。

https://github.com/uchan-nos/opela/blob/master/compiler/v2/ast.cpp#L854 の ConsumeOrSub(">") がその処理を行います。 このメソッドは、先頭がトークン > ならそれを消費し、もし > で始まるトークンなら > とそれ以降で 2 つのトークンに分割したうえで 1 つ目のトークンを消費する、というものです。

TypeList の処理の中で >= を消費してしまうと、= の意味を上位の処理まで伝播させねばならず、構文解析のプログラムが全体的な影響を受けます。= を未消費のトークン列として残すことで、全体的なプログラム変更をせず、構文解析器の構造が綺麗なまま保たれます。

»= の場合

まだ OpeLa コンパイラには実装していませんが、シフト代入演算子（指定したビット数だけシフトしてから代入する演算子）を将来的に実装したくなるかもしれません。上記と同様の問題で、次のようなプログラムにおいて、>>= の字句解析が間違った結果となります。

var x Pair<Pair<int>>={ {1,2},{2,3} };

この場合でも、先ほどの解決策は有効に機能するでしょうか？処理を時系列で考えてみます。

1. 字句解析器が < Pair < int >>= というトークン列を出力する
2. TypeList の処理がトークン >>= に出会う
3. TypeList の処理は > と >= にトークンを分割し、> だけを消費する（この時点で内側の型リストの末端処理が完了する）
4. TypeList の処理がトークン >= に出会う
5. TypeList の処理は > と = にトークンを分割し、> だけを消費する（この時点で外側の型リストの末端処理が完了する）
6. 構文解析器は = を見て、初期値が続くと認識する

このような処理となるので、どうやら上手くいきそうです。

トークンを、構文解析時に改めて異なる意味として再認識する今回の方法は、今後の構文を考えるうえで柔軟性を与えてくれる汎用的な手法となるかもしれませんね。

他の選択肢

他の解決策としては < > の代わりに [ ] などの記号を使うことも考えられます。]= という演算子は今のところありませんし、将来的にも増えないでしょうから、>= と違って字句解析が間違うことがありません。理論的にはこちらの方が綺麗ですね。ただし、ジェネリクスでは < > を使うという、多くのプログラミング言語で共通する慣習を破ることになります。

どちらの選択肢にもメリデメがありますが、今回は OpeLa 言語の学習容易性を優先し、< > を継続的に使える選択肢を取りました。