「レズと青い鳥」を読んだ

「レズと青い鳥」というのは、mikutterの薄い本制作委員会が今回の夏コミで頒布していた同人誌のこと。

brsywe.hatenadiary.com


今日は私がTwitterに登録してちょうど6年らしい。


通販されるのだしわざわざ買いに行かなくてもいいかな、と思っていたのだけれど、UserStreamが廃止されてから読むのはなんか違うなとも思ったし、せっかくだから買いに行くことにした。





私はいまだにスマートフォンを持っていないので、ほとんどのクライアントは使ったことがない。


でも、Shooting Starの章を見たときは何か「あの時代」が脳裏に浮かんだような気がする。


私の経験を少し書いてみる。





最初はtwitbeam[ﾂｲｯﾄﾋﾞｰﾑ]というクライアントを使っていた。

これは、ドワンゴが作っていたクライアントで、UIがとても好きだった。でも、2013/2/28でサービスを終了してしまった。

ちょうどAPI1.1に切り替わるのが三月だったので、twitbeamはXAuthを使っていたし、その影響なのだろう。


私がTweetのことを「ついっと」とよんでいるのもこのクライアント名が原因のような気がする。


ShootingStar for FeaturePhoneというクランアントも愛用していた。

Shooting Starの影響か、いわゆるUnicode文字を使った"キチ顔文字"が流行っていた時代、Unicode文字の含まれたツイートを画像で表示してくれるという機能はとても助かるものだった。

ガラケーはUnicode文字に対応していないため、そういった文字は、♡が「ガラケーの」ハートの絵文字に変換されるといったごく一部を除けば、?に変換されてしまっていた。

キチ顔文字のパターンはそんなに多くないので、文脈から推測できるものの、キチ顔文字を使ったコミュニケーションの「雰囲気」を再現できるクライアントはこれしかなかった。

それ以外にも、APIリミットが事実上無制限とか、キチ顔文字を入力できるエスケープがあるとか、そこには求めるものがすべてあった。


でも、2013/10/12には星になってしまった。





API1.1への移行の時から、Twitterはサードパーティーアプリを締め出そうとしているという風潮があった。たとえば、Display Requirementとか。

切り替わってすぐ、Shooting Starが10万アカウント制限に引っかかって、星になってしまったりしていた。


RestAPIが15分に15回というのはUserStreamが使えればあまり問題にはならなかった(UserStreamが使えないガラケーでは困ることになるけれど、ShootingStar for FeaturePhoneを使えばAPI制限は事実上回避できた)し、

絶対時間じゃなくて相対時間で示せ、っていうのがDisplay Requirementに含まれていて、わかりにくくなった(一時間前、の幅が広すぎていつだかわからない！)以外にはそれほど締め出されている感じはなかった。その時は、まだ。


複数人DM機能やアンケート機能のAPIが公開されないなど、そういった方面でサードパーティークライアントアプリと差別化していくのかなとも思っていたけれど、結局UserStreamAPIを廃止することに踏み切ってしまった。


公式によれば、1%しかUserStreamを使っていないらしい。ライト層というか、サイレントマジョリティ的な感じで、それ自体は正しいのだと思う。

でもやはり、そういった時代を作ってきたサードパーティークライアントアプリ製作者に、恩をあだで返すような仕打ちに思える。





読んでいて、ツイッタークライアント製作者って大学生が多かったのだなぁと思った。それと同時に、自分もそういうことをやってみたかった、でももうそんなことはできない、という気持ちにもなる。


提供されているものを取り上げられたからいじわるだ、という考え方ではなく、いままで与えられていたことに感謝して、時代が変わったと受け止めるべきなんだろう。





スマートフォンの普及の歴史、マイクロブログの隆盛の歴史、Twitterの歴史。


そういった時代を思い出すことができた。



すごくいいものを読ませてもらったと思う。


ありがとう、サードパーティークライアント製作者たち、さよなら、UserStream。



C++で安全に絶対値を求める

C++で安全に絶対値を求める方法について、調べても出てこないので書いておきます。 安全に、というのは「オーバーフローなどの未定義動作を起こさず」という意味です。

#include <type_traits>
#include <cstdint>

template<class T, class U = std::make_unsigned_t<T>>
U SafeAbs( T x ) {
    return x < 0 ? -static_cast<uintmax_t>(x) : x;
}

解説

std::make_unsigned_t<T>は見慣れないですが、単にTの符号なしバージョンを持ってこれるメタ関数です。たとえば、std::make_unsigned_t<int>はunsigned intになります。 Tが符号付整数の場合、その絶対値はTで表せるとは限らないので、符号なしバージョンを使わないと安全ではありません。 実際、負の数を二の補数で表現している処理系では、INT_MINの絶対値はintに収まらないことが問題となります。

まず、xが非負ならば自明にそのまま返せば問題ありません。以下、負の場合に何をやっているかを説明します。

uintmax_tも見る機会があまりありませんが、符号なし整数のうち最も大きいものです。 -xとしてしまった瞬間にオーバーフローの危険性があるので、まずは符号なし整数に変換します。 符号なし整数に変換されるときは、負の数であれば2Nを加えると決まっています。ここで、Nはその符号なし整数(ここではuintmax_t)のビット幅です。

次に、uintmax_tにキャストしたものに単項負符号演算子を適用しています。符号なし整数に単項負符号演算子を適用するのは一見するとおかしなことになりそうですが、問題ありません。 このような場合、数学的な結果を2Nで割った余りが得られることに決まっています。そのため、数学的には、-(x+2N) mod 2N を計算していることと等価になり、結局-xが得られます。

最後に、なぜuintmax_tを使っているかについて説明します。この部分は、Uでも問題なさそうに思われます。しかし、Uを使う場合、移植性をはばむ、C++における二大問題を避けることが困難になります。

  • 符号付整数のビット表現
  • 汎整数昇格

そんな処理系はまずありえないのですが、C++においては符号付整数の表せる範囲は物凄く偏っている可能性があります(C言語では、必ず「二の補数」「一の補数」「符号と絶対値」しかありえません)。 intは符号付整数ですので、やはりものすごく偏っている可能性があります。 たとえば、intの表せる範囲が-1073741824～3221225471という可能性もあります。

Uにキャストした場合、単項負符号演算子を適用する前に汎整数昇格が発生するかもしれません。 汎整数昇格が発生するのは、Uで表せる値がすべてintでも表せる場合ですので、この部分でオーバーフローが発生することはありません。 しかし、前述のようにintで表せる範囲が偏っている場合、intに昇格した値に単項負符号演算子を適用した結果がintで表せる保証はありません。

uintmax_tを用いた場合、intに昇格する可能性はないため、この問題は発生しません。

重箱の隅をつつくようですが、こういうパターンがあるためにuintmax_tの代わりにUを使うのは真の意味で「安全」とは言えません。とはいえ、むしろそのような処理系があれば教えていただきたいくらいのレベルで珍しい処理系ですが……。

速度について

ちなみに、安全性は気にしないから速度を重視したいという方もいらっしゃると思います。少なくともx86のネイティブコードを出力するまともなコンパイラであれば処理速度的にそれほど劣ったコードにはなりません。

gccでは、uintmax_tであってもUであってもビット演算を用いた条件分岐のないコードになりました。clangでは、uintmax_tであってもUであっても、char以外はcmov命令を用いたコードになり、cmov命令が使えないcharの場合はgccとほぼ同様のコードになりました。

ちなみに、charやshortの場合はキャストをしなくても安全です。clangでは変化しませんが、gccでは特定のパターンであることを見抜いたのか、cdq命令を使うようになります。

一方、intやlong longの場合、キャストをしないとソースコード上に潜在的に未定義動作を含むことになります。ただし、キャストをしない場合とコンパイラの出力するコードは変わりません。 この場合、結果は望むものになるとはいえ、ソースコード上は潜在的に未定義動作を含んでいます。

ちなみに、以下のように(移植性はないが、その処理系にとっての)未定義動作を排除したコードでは、コンパイラは条件分岐を出力するようです。 なお、gccかつlong long版のみ、後半部分を見抜いてcqo命令を使うようになりました。なぜintの時はcdqにならないのか、x == LLONG_MINの分岐がないとcqoにならないのかは不明です。

unsigned long long Abs( long long x ) {
    return x == LLONG_MIN ? 1ull<<63 : x < 0 ? -x : x;
}

ただし、これらの結果は関数単位でのコンパイル結果を見ている点については注意が必要です。呼び出し規約上、charやshortの引数は符号拡張されてから関数に渡されます。 実際にはこのような関数はほぼ確実にインライン展開されるため、符号拡張命令分のコストを考える必要もあります。

参考

絶対値以外の、一般の演算についてその安全性を議論した記事として、

C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足)

があります。落とし穴が詳しく解説されているためおすすめです。

constexprで書けない純粋な関数

今週はThe continuing evolution of C++の講演を聞いてきました。C++20では

  • concept
  • module
  • contract

を入れるというような話もしていました。どれもよい機能です。conceptは入ったらいいと皆が思うからこそ、微妙な点で意見が食い違ってなかなか入らないのですよね。さすがにそろそろ入ってほしいです。moduleはあまり話題になっていないので知らなかったです。コンパイルが速くなる誰もがうれしい機能のはずですが、つまみ食い的に使って楽になるような機能ではないことが話題に上らない理由なんでしょうか。inline変数などヘッダ前提の機能も着実に追加されていったりしていますし、ヘッダスタイルはまだまだ残りそうです。contractはプログラミングパラダイムを変えうるわけですが、だんだんと追加していくタイプの機能になるのでしょうか。

さて、先週は副作用を利用して関数の中身がどうなっているかを調べる話を書きました。

この方法に類似した面白い話題があります。それは、純粋関数型言語で定義できない純粋な関数 - sumiiの日記という問題です。純粋という単語の使われ方が紛らわしいですが、

  • 純粋関数型言語→副作用のあるような機能を実現する構文がない関数型言語
  • 純粋な関数→（内部で副作用を使ってもいいが）参照透明な関数

という意味です。

constexprは、C++11の段階では確かに純粋関数型言語でした。 しかし、C++14では関数内で完結する副作用が許されたため、あくまで純粋な関数しか書けないとはいえ、純粋関数型言語では書けないような関数が書けるようになったのです。C++17でラムダ式の呼び出しもconstexpr指定されるようになったため、さらに書きやすくなりました。

では実際にC++11では書けなかったような関数を書いてみましょう。

……

実際に書いてみるとわかりますが、普通にやってもこのようなことはできません。

局所的にせよ副作用のあるようなラムダ式はなんらかのキャプチャをしているはずなので、関数ポインタに変換できません*1。

つまり、「関数ポインタをとれる関数」かつ「constexpr文脈で評価できる関数（static変数とかを持っていない）」の範囲であれば、副作用を許したところで表現力は変わらないように思われます（本当にそうなのかよくわかっていません）。

ラムダ式を引数に取れるよう、関数ポインタ以外に関数オブジェクトもとれるようなテンプレート関数にするとどうでしょうか。

実際に書いてみたのがこちらです。

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

BOTTOM、つまり無限ループになることを確かめる方法は原理的にないのですが、このくらいの単純な関数なら、再帰深度制限で落ちれば無限ループと判断してよいでしょう。

……というのはちょっと罠で、clang++でstatic_assert( f() == nullptr )と書いてしまうと、f()の型はstd::nullptr_tだから恒真、と判断してしまい、関数呼び出しすらしないようです。

g++で確かめることにしましょう。

ところであまり素直ではない書き方になっているのが気になります。

先ほど書いたように、関数ポインタを受け取る関数を作るのでは、ラムダ式を受け取ることができなくて詰みます。

そうするとジェネリックラムダで受け取りたくなるわけですが、自己再帰関数関数が書けなくて詰みます*2。

自前でtemplate<...>と書けばいいのかというとそうでもなくて、関数テンプレートは、テンプレート引数を指定せず関数の引数に入れることができなくて詰みます*3。

というわけでテンプレートなoperator()を持った関数オブジェクトを作っているわけです。自己再帰は(*this)(unit)みたいになっていて微妙ですが、仕方ありません。

ただ、先のコードでは、C++14以降でしか書けないようなconstexpr関数があることを示したことにはならないような気がします。 オーバーロード関数を作ってしまえば、引数に与えられる関数ごとに挙動を変えることは非常に簡単です。 そういうような書き方をするとその多相関数は「一様」でなくなってしまうのですが、C++11でも書けるには書けるということです。

結局、C++14になって局所的な副作用が許されたからといってconstexprで書ける関数の範囲は変わらないということなんでしょうか。 関数ポインタをとれるという条件（あるいは、ヒープが使えないという条件下での型システム）によって、純粋関数型言語で書ける関数に限定されてしまうというのは不思議な気がします。

*1:C++的には、ただの関数と情報を持っているクロージャーでは当然サイズが違うので同じ型を付けられません（C++言語での型というのにはストレージをどれだけ使うかというのまで含まれてしまいます）。サイズが違っても同じ型に見せるには、動的確保が必要ですが、constexpr文脈では残念ながらできません。

*2:let recみたいなのがなく、ラムダ式の中で自己再帰する方法がありません。自前でfixみたいなものを作ればできないこともないですが、見た目がまるっきり変わってしまいます。

*3:関数テンプレートはあくまでテンプレートであり、C++の世界の値ではありません。つまり、多相関数をそのまま受け取る方法がありません。ランク1多相が偽物なのでランク2多相が書けなくなってしまっています。

ISAシミュレータを書くのを楽するためにTMPを使う方法

半年くらいブログをほったらかしにしていました。おひさしぶりです。 ついったーにC++のコードを張り付けていても検索性が低いなぁと思ったので今後はブログにまとめていこうかなぁという感じです。

ISAシミュレータを作るとき、一つ一つの命令の定義は非常に単純なのに、付加的な情報を定義しなければいけないために冗長になってしまうことがよくあります。 たとえば、レジスタの値をストアするSTORE命令を考えてみると、

mem[src[1]+imm[0]] = src[0];

くらいの情報量で充分に定義できているはずです。 しかし、ソースレジスタが2個だとか、デスティネーションレジスタはないだとか、そういった情報も使いたくなることがあります。 そういった情報は先ほどの定義から原理的には抽出できるはずですが、C++コードで行う方法は必ずしも自明ではありません。 また、ISAシミュレータは速いことが望まれますので、出来ることなら実行時に動的に判断するのではなく、コンパイル時に静的に決まってほしいです。 こういった情報を別の場所に手書きするのは、保守性が低下するのであまりやりたくないところです。

テンプレートメタプログラミングを使うとそういったこともできるということを示すためにちょっと書いてみました。

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

ltmpcほどテンプレートメタプログラミングという感じではなく、constexpr要素も含んでいます。

各命令の動作の定義には、ジェネリックラムダを使います。auto型の引数の部分は実質テンプレートなので、あえて変な型のオブジェクトを入れることもできます。 ここで、入れることのできる変な型のオブジェクトは、単に同じ名前の変数や関数が定義されていれば問題なく動きます（いわゆるダックタイピング的なことができます）。

これを利用（悪用ですね）して、ラムダ式の中でどのような変数にアクセスしているかを検出するオブジェクトを作ることができます。 これをラムダ式の引数に与えることで、ラムダ式の中での動作を調べ上げることができます。

今回は単にアクセスされるかだけの判定でしたが、演算子オーバーロード・式テンプレートと組み合わせればどういった依存関係になっているのかということも判定できそうです。 最初から式テンプレートを使えばconstexprなしの完全TMPで同じことができそうに思えますが、src[0]みたいな部分はうまく扱えないです。0_srcとかsrc<0>()とか書けば型に落とし込めますが、見た目とのトレードオフになりそうです。有限個なのでとあきらめてsrc0みたいな変数を作ってしまうのはちょっと負けた感じがあります。

ただ、こういうのを書くのは、簡単な命令の時は有効ですが、わけのわからない細かい仕様のある命令の時は結局愚直に書く必要があって、あまり楽をできなくなってしまいます。悲しい。

ltmpc: CodeEmitterの解説

CodeEmitterでは、これまでで得られた型付きの抽象構文木と配置情報をもとに、x86(32bit)のアセンブリを出力します。 ターゲットとしてx86(32bit)を選んだ理由は、私が最も慣れ親しんでおり、呼び出し規約も簡単だからです。

CodeEmitterのコードは、ほんとうにぎりぎりの、公開日当日に数時間で書かれました。 そのため、ところどころでParserやTypeAnalysisやLocationの関数を使っているなど、かなり汚い設計になってしまっている上、ごく一部のコードしかコンパイルできません。 それでも、N-Queen問題を解くコードが動いた時には感動しました。

x86(32bit)の呼び出し規約(cdecl)

  • eax, ecx, edx を保存せずに使用してよい。
  • ebx, esi, edi, esp, ebp は保存せねばならない。
  • 引数は全て後ろから順番にスタックに積む。
  • 返り値はeaxレジスタに乗せる。
  • コールスタックの片づけは呼び出し側で行う。

コード生成の作戦

ちゃんとした最適化コンパイラであれば、スタック割り付けなどの仕事をする必要がありますが、ltmpcではとりあえずコンパイルするだけでよいため、そのような面倒な仕事はしたくありません。 x86(32bit)の機械語にはスタック操作命令が豊富なため、スタックマシンとして扱うことができます。抽象構文木を一対一にアセンブリに変換する場合、スタックマシンとして考えると非常に簡単になります。 その上、スタックマシンとして扱うとeax, ecx, edx, esp, ebp以外のレジスタを使わずに済みます（少し手間をかければ、（可変長配列がなければ）ebpも不要になります）。 espとebpの操作は定型文になり、技巧的な方法を使う必要はありません。ebx, esi, ediは使わないので保存レジスタですが気にする必要がなくなります。eaxは返り値、edxは剰余演算の返り値、ecxはシフト演算のオペランドとして、それぞれ専用の役割があるため絶対使わないというのはほぼ不可能ですが、幸い日保存レジスタになっています（他にも役割は存在します）。 関数ポインタを使った関数呼び出しと静的に確定する関数呼び出しとでは普通は別の命令を使いますが、なるべく例外を少なくするために、静的に確定する関数呼び出しの場合でも関数ポインタで呼び出すことにします。

Code, concat

Codeは、単なるTMPにおけるcharの配列です。concatは、二つのchar配列をつなげる関数です。ここで、concatの定義時（つまり、定義前）にdecltypeの中にconcatが出現しており、これは定義前再帰ですが、同じ名前空間のCodeが引数に入るため、ADLで検索されるので問題ありません（このせいでdetailの中に入っていないのです）。

Intro

アセンブリコードの最初に必要な定型文です。

ToString, ToOffset

非型テンプレート整数を10進文字列に変換する関数です。ToStringは非負整数用であり、ToOffsetは符号付整数用で常に符号付で出力します。displacementの部分に書く用です。

StringRef, FuncRef

それぞれ、文字列（char配列の先頭アドレス）、関数へのポインタ、をスタックに積むときに書くべき定型文です。

Dword, Byte

それぞれ、ポインタの型を表すための定型文です。Dwordの場合はそのアドレスから4Byte分、Byteの場合はそのアドレス1Byte分のメモリ操作になります。

ラベル関連

一意なラベル情報を実際に文字列化しています。まず関数の名前、ifのネストは連番の整数を文字列化、ループ構文の先頭・条件部・末尾はそれぞれB, C, Eを、それぞれアンダースコアつなぎにすることで一意になることを保証しています。

PraceはPlaceの間違いでしょうか……。あまりにあわてて作ったので気づきませんでした……。

SetCCの利用

普通、x86での比較命令はcmp命令ですが、フラグを使うのが面倒なのと、(a<b)+(c==d)みたいなコードに対処しないといけないことを考えると、0・1がそのまま出力されるSetCC命令を使うと簡単になります。

Compile

ここで具体的に抽象構文木のノードをアセンブリコードに落としていきます。リテラルの場合、即値をスタックに積むだけのコードになります。addやsubでは、オペランドがポインタであるかなどにより三通りのパターンがありますが、左辺のプログラムと右辺のプログラムを再帰的にコンパイルしてコードにした後に必要な処理をする形になっています。代入の場合は、左辺のプログラムにアドレスを要求している点が異なります。後置増分・減分の場合はcharかintかポインタかで三通りのパターンがあります。

複雑なのは配列アクセスで、多次元配列の場合は値ではなくアドレスを返す点が特殊になっています。1[arr]のような変な書き方ができることと合わせて、四通りのパターンがあります。 関数コールは引数をスタックに積んだ後、関数ポインタをスタックに積み、それをポップしてレジスタ間接コールを行います。戻ってきたときはスタックを巻き戻します。

変数の場合は、右辺値なら値を、左辺値ならアドレスを、それぞれ返すコードを出力しなければいけません。値を返すコードはEmitCode、アドレスを返すコードはAddrに定義されるのですが、あわてて作った上に設計がめちゃめちゃなので、なぜこれで動くのかも私自身わかっていないところがあります。

StatementFold

構文ごとに対応するコードを出力する部分です。esp, ebp操作関連のコードはここで出力されます。

StringPoolFold

前回のLocationで回収した、文字列定数をグローバル領域に出力します。

GlobalStatementFold

グローバル変数と、関数定義と、文字列定数を出力する部分です。

おわりに

これで一通りすべてのモジュールの解説が終わりました。 まだまだ道のりは長いですが、ltmpcをより完成に近づけていけたらと考えています。

あまり関係ない話

これで書くことが尽きてしまったので、一か月くらいブログは休む気がします。またltmpcの進捗を公開できることを願って。

ltmpc: Locationの解説

Locationでは、グローバル変数・自動変数・文字列定数の割り付けを行っています。

このコードを書き始めたのは完成の前日で、あわてて書いていたのでコードが適当になってきています。

FrameEnvironment

フレームというか、中かっこ文ごとの、「今のSPがBPからどれだけ離れているか」と「中かっこを脱出した時に戻すべきSPのBP相対値」、「スコープに入っている自動変数のBP相対値の辞書」をまとめたものです。

ParseSize

sizeof演算子やalignof演算子の結果を計算するような部分です。FunctionのSizeが0であるのは、関数がスタックに取られたりすることはないためで、変数ではない証になっています。

add_global_environment

GlobalEnvironmentは、グローバル変数・関数定義の情報を収集して入れておくものですが、これに情報を追加します。この時、Sizeが0のものは変数ではなく関数の前方宣言なので、追加しません。

add_flame_environment

FrameEnvironmentに新たな自動変数を付け加えます（ブロック先頭以外での変数宣言も可能なので、途中でSPの値が変わり得ます）。また、アライン要求の一番大きな4Byteに強制的に揃えます。

StringPool, StringRef

文字列定数は、出現するたびにスタックに積むわけではなく、グローバル領域にその情報が置かれています。StringPoolはその情報を収集して入れておくもので、StringRefはそれを示す一種のポインタになる、StringPoolの先頭から何番目に存在するかを示す整数を保持します。

Locate

各式について、割り付けを行います。変数ならFlamePositionに変換し、文字列定数ならばStringRefに変換したうえでStringPoolに追加します。ほかの式の場合は、各部分式についてこれを再帰的に行います。 BinaryNodeは抽象化されていますが、他の部分は抽象化しておらず完全にコピペコードになっています。

あれ、これではグローバル変数が来た時にエラーになってしまうような……。

StatementFold

各文について、必要ならば再帰的にLocateを行います。TypeAnalysisでやったものと同じようなコードが並んでいます。

makeReturn

関数の終了には、暗黙的にreturn文が存在します。void型であれば何も問題なく、int型などであれば偶然残っていたゴミが返されることになります。そのreturn文を追加します。

GlobalStatementFold

グローバル領域に現れる文すべてについて、変数宣言ならGlobalEnvironmentに加える、関数定義なら中身をStatementFoldにかけたうえでGlobalEnvironmentに加える、ということを行います。

Fold

いつもの、線形再帰にならないようにタプルを分割しながら再帰するものです。

おわりに

Locationはほとんど自明な変換しか行っていないのであまり説明することがありませんでした。

あまり関係ない話

何とは言いませんが締切がせまってきていて、ltmpcをいじる暇が全くなくなってしまっています。はやくいろいろ改修したいです……。

ltmpc: TypeAnalysisの解説

TypeAnalysisでは、各部分式に型をつけていきます。また、制御構文により暗に生成されるラベルの生成も行っています（ここでやる必要はなかったですね……）。 もうこの辺では空間計算量を気にする余裕がなくなってきていたので、全部愚直な線形再帰で処理しています。 とはいっても、抽象構文木として暗に再帰的な構造になっているので、ふつうのケースでは問題になることは少ないと思われます。 変なケースとしては、int a1, a2, a3, ……, a1000;とか、a1+a2+a3+……+a1000;とか、void f() {{{{{……{{{{{}}}}}……}}}}}とか、こういうのがくると厳しいです。 ただ、こういうケースはそもそもParserの段階で厳しいので、Parserを通ってきた出力なら大丈夫でしょう、ということで手抜きをしています。

C言語における型は、ltmpcに実装されている範囲だと、「void・char・int」×「ポインタの数・配列・関数」×「左辺値・右辺値」くらいが必要な情報です。 C言語における型付けのルールを理解していないため、実装は全然正しくなっていません。特に、条件演算子の実装は完全に間違っています。

Typed<Ty, AST, Lval>

抽象構文木のノードをラップして、型の情報の左辺値であるかの情報を付け加えているノードです。

IsParameterListValid

関数の引数の型に、void型が混ざっていないかをチェックしています。sizeof...(Params) && falseというのは、無理やり依存式にしてstatic_assertを起こすのを遅延させるために行っています。

あれ、この書き方だと引数の最後にvoidがある場合に正しいと判定してしまうような気がしますね……。

ParseDeclare

C言語の型宣言の構文をパースしてできる抽象構文木は使いたいものと逆順になっているため、使いやすいようにひっくり返しています。末尾再帰のreverse関数のような方法で行っています。

TypeEnvironment

型の環境を保持するためのもので、変数や関数の識別子名から、その型を引くことができる辞書になっています。多重継承を利用した型の辞書イディオムを使っています。

NestEnviroment

制御構文（if, forなど）で暗に定義される一意なラベルを生成するための情報を保持するための物です。break、continueは最内のループの末尾に飛ぶため、ifのネストだけは別にカウントしないといけないので面倒です。

Convertible

C言語における暗黙の型変換が許されるかの定義ですが、これってあっているんでしょうか…………。

Error

Parserと違ってTypeAnalysisでは、エラーを発見した時にちゃんとstatic_assertで落とすようにしました（未既定の挙動を引き起こす諸悪の根源です……）。 Error_Assign_Type_Not_Convertible<T, U, N>だけTやUが存在するのは、デバッグ時の名残のようです（このようにすると、ltmpcの内部表現とはいえテンプレート実引数がエラーメッセージとして出力される（コンパイラを使っている）のでデバッグが楽になります）。

NonVoidCondition

bool的文脈に現れることができる型かのチェックをしています。void以外は全部大丈夫でしたよね……？

FunctionApply

関数適用について、型があっているかのチェックを再帰的に行い、すべての型があっていれば返り値の型を返しています。

addType

二項加算演算について、その結果の型を導出しています。オペランドがポインタであるかそうでないかで四通りの結果があります。本当は関数ポインタと整数の加算は正しくないのですが、はじけていません。また、longなどのintより大きな型が含まれる加算が返す型はintではなくlongなどにしないといけないのですが、今回はそういう型は存在しないので手抜き実装しています。

makeAddTyped

addTypeの結果を使い、実際に型付けされたノードTypedを作る関数です。

subType, makeSubTyped

addType, makeAddTypedとほぼ同じです。

integralBinaryOpTyped

その他のほとんどの二項演算子は両オペランド共に整数しか受け取らないので、それを扱うものです。

Assign系

代入演算では、代入の時に型変換が発生するので、その型変換が可能かをチェックしています。加算代入と減算代入の場合はポインタ演算の可能性があるので、追加の実装がしてあります。

makeConditionalTyped

条件演算子の型付け規則ですが、then部の型にそろえる、という完全に間違った実装になっています。共通の型を見つける方法がよくわからなかったので手抜き実装になっています……。

makeCommaTyped

順次演算子は、void型のオペランドを受け取ることもあり、右オペランドの型が全体の型になるという他の二項演算子と違う特徴を持っているため、別に実装してあります。

makeBinaryTyped, makeMultiBinaryTyped

ほとんどの二項演算子は、整数を二つ受け取って整数を返すのでそれを全てまとめた実装です。MultiBinaryというのは、Parserでも出てきた、複数の優先順位が同じ演算子をまとめて取り扱う抽象化に対応します。

makePtrCompareTyped, makePtrEqCompTyped

整数以外を受け取ることもある二項演算には、加減算だけでなく、比較演算も該当します。それを別に実装しています（実はNクイーン問題をコンパイルするときまで気づいていませんでした……）。

makeAddressOf

単項アドレス演算子の型付け規則の実装です。左辺値でないとエラーにしている点に注意が必要です。

これ、別に関数ポインタの時と区別する必要はなかったですね……。

以下、同様の単項演算子のmake系関数が続きますが、ほとんどやっていることは同じです。左辺値でないといけないだとか、ポインタでないといけないだとか、関数ポインタでないといけないとか、条件により振り分けて間違っている場合はエラーにしています。

promote

以下の四つの汎用的な自動変換を実装しています。

  • 左辺値から右辺値への自動変換
  • 配列のdecay
  • 整数昇格（現状はchar→intのみしか存在しない）
  • 関数の関数ポインタへのdecay

うち、配列のdecayが発生したかはアセンブリコード生成の際に重要な情報になるので、ArrayDecayというノードを新たに生成しています。

また、void型のものをpromoteしようとした、ということはvoid型の物をオペランドにとって演算しようとしたということなので、エラーにしています。条件演算子や順次演算子など、void型の物をオペランドにとれる演算子の場合でこのエラーを出したくない場合は、代わりにpromote_void関数を使います。

関数から関数ポインタへのdecayを実装しているため、(*****fp)()みたいなコードもコンパイルすることができます。

typed_expr

抽象構文木のノードを受け取り、再帰的に型付けを行う関数です。型環境Environmentを受け取っているため、ADLの対象となり、関数を使うタイプのTMPであっても相互再帰が可能になっています。

typed_expr_impl

ほとんどの二項演算ではpromoteを使い、一部の二項演算子でだけpromote_voidを使う、というのを先ほど説明しました。これを、関数の実質的な特殊化、つまりオーバーロード優先順位が高い、より詳しいテンプレート引数指定の関数で上書きする、という手法でやろうとするのですが、

「オーバーロード解決に不必要なテンプレートの実体化はしてもしなくてもよい（未規定）」

という未既定の挙動をまさに踏みました。

先の手法だと、たしかに思い通りのオーバーロード優先順位にはなるのですが、必要ない方（generalな、promoteを使う方）もインスタンス化され、そちらでstatic_assertを起こしてしまうのです。

これを防ぐために、この問題の発生する部分だけは、関数を使う形式のTMPをあきらめ、構造体を使う形式のTMPに切り替えました。それがtyped_expr_implです。TypeAnalysisでは暗黙の変換を使っているところは全くないので、この点は問題になることはありません。

また、clangはテンプレート引数が三つのConditional_Nodeについてもバグった挙動を示してBinaryNode<T, U>にマッチして同様の問題を引き起こすため、これも除外しています。

typed_expr

その下には、MultiBinaryに該当するEqComp_Node、Compare_Node、Shift_Node、Mult_Node、についての定義が並んでいます。enum classの型を推論してくれるとまとめることができるのですが、非型テンプレートパラメターの型を推論することは、C++11ではできないようです（コンパイラの動作を見る限りにおいては、C++17ではできるようになったようです）（ltmpcを作るにあたってはC++11で十分で、C++14やC++17の機能は役に立たないと思っていたのですが、この点だけはほんの少しだけ不便ですね）。

StatementFold

文ごとに、含まれる式に型付けを行い、型環境とネスト環境を更新していきます。また、break文とcontinue文について、どこにジャンプするべきかのラベル割り当ても行っています。

おわりに

基本的に、Parserまでが面倒な部分であって、それ以降はやるだけなのであまり面白い解説ではなかったと思います。まぁ、やるだけと言いつつC言語の型付けは暗黙のルールが多くてやたらに複雑なので正しく実装できていないませんが……。

全然関係ない話

ltmpcの未実装部分を実装したり、非効率な部分を書き換えたりしたいとずっと思っているのですが、最近忙しくてここ一か月くらいなにもできていません。

ltmpcの解説だけは、なんか毎週日曜日にブログを更新するみたいな感じになっているので書き続けていこうとしています。