forthとコンパイラ

Forth言語特性

Forth言語では、古典的には"間接スレッディング方式"という特殊な実行形式が採用され、"コンパイル"というときにも特殊な意味で用いられていた。
しかし、ここでの話はマシン語を生成するネイティブコード・コンパイラを対象とするため、その解説は省く。参照

Forth系の言語ではコンパイラの作成が非常に容易ともいわれる。その第一の理由は構文解析や意味解析のためのコードを書く必要がないからだ。

Forth言語には特殊記号のようなものは、ほとんど — 全くというわけでもないが — ない。記号のように見えるものも、一つ一つが実行上の意味を持っている。その各々はワード(word)と呼ばれる。そのワードが書かれてある順番に実行されていくだけ、というのが原則となる（当然、例外も多くある）。ワードの特定には、まず区切り文字で区切られた文字列が取られる。続いて、その文字列を名前とするワードが既に辞書(dictionary)に登録されているかどうかが確認される。区切り文字としては、原則として、空白、タブ、改行のみが用いられる（コードファイルの初めと終わりも、文字ではないが、ワードの区切りとなる）。そのため、forthでは空白文字に挟まれた文字列を取り出す、ということだけで何を実行・コンパイルすべきかがわかってしまうのである。
他方、通常のプログラミング言語では、"+"のような明確に加法演算としての意味を持つ記号さえ、それ単独では実行あるいはコンパイル上の意味には何ら結びつけられていない、ただの文字記号である。構文解析を経て文（statement）の意味を判定した上で初めてそこで何を行うべきかがわかるのである。

上のようなforthの特性は、手練のプログラマには好都合だ。しかし、自分のような素人にはかえって困った事態であるともいえる。
というのも、世にあるコンパイラ作成のための標準的テキストブックでは、その分量の半分くらいは字句解析・構文解析・意味解析に割かれているのである。初級的になればなるほどその割合は増える。逆に言えば、forthコンパイラを構築するとき正に知りたいような事柄には、ごく僅かのページ数しか割かれていない。そのため、記述が簡潔に過ぎ、少し考えれば容易にわかるような大雑把なことしか書かれていない事も多い。しかし、これは仕方のない事でもある。まず、通常の数式のような外観を持つ表記を実際の計算手順に落とすには、必ず先読みと構文解析が必要になる。そして、さらにいえば、コンパイラ設計の教科書の目的は、コンパイラ設計が自分でできるようになるための方法を（その一冊で）教えることでは必ずしもないのである。そこでの目的はむしろ、様々なコンピュータ・アルゴリズム(定型的な処理手順)の応用を教えることなのだ。コードテキスト解析の領域は、いかにもコンピュータらしい考え方やアルゴリズムの応用が豊富に見いだせるようだ。教科書がこの領域の解説を無しで済ませるわけにはいかないのだ。

結局、教科書や体系書のようなものも入門書のようなものも、一冊も読まなかった。既存のコードとネットで拾った英語の論文の類だけが参考書だった。

マシンコード生成

重点はコード生成だった。しかし、直ちにマシン語を吐くものを初めから考えた。中間コードや仮想マシンは考えなかった。

Forthは実は古典的には仮想マシン方式といえる。仮想スタックマシンである。中間コード方式ではないが、上に述べた字句解析・構文解析・意味解析の部分が軽いため、インタープリタでも高速だった。コンパイルされた後はもちろんさらに速くなる。マシン語を直接生成するコンパイラに匹敵するものさえあった。しかし、コンパイラの最適化技術は進み、マシンも変化した。

最新のネイティブコード方式、つまり、最適化されたマシン語を生成・実行するタイプのforthでも、forth特有のデータスタックは維持されている。スタックマシンは仮想といってもコンピュータの実際の動作に極めて近い。そしてforthコードはその仮想スタックマシンのマシン語の様な基本ワード群から成るのである。スタックマシンという仮想マシンをつくってしまえば、その上でforthコードは、マシン語のように — つまりワードに動作を一対一に対応させるように — 実行・コンパイルできるわけだ。

けれども、パラメターをすべていちいちスタックに押し込んだりスタック操作ワードに合わせてアイテムを入れ替えたりするのでは、今ひとつ速度がでない。それでも32bitモードのx86ならある程度仕方がないが、64bitモードでは、32bitでは8本しかない汎用レジスタが16本に増えているのである。スタックメモリにはキャッシュは効くだろうが、レジスタを使う方が数倍速い。ど素人の初心者ではあるが、あまりに遅いコードを吐くコンパイラはつくりたくなかったのである。また、模範となった環境であるPowerMopsは、PowerPCが持つ多数のレジスタを用いて大規模に最適化されたものであったため、あまりに実行速度に落差のあるものではマズいとも思ったからである。

結果として、そこそこレジスタを多用するコード生成はできたと思う。したがって（素人作のオープンソースフリーウェアの）iMopsでさえ、その中身まではforthのようには実行されてはいない。データスタックはむしろ臨時のデータ避難場所として使われている。しかし、もちろん全体としてはスタックフレームではなく１セル１アイテムのスタックとして動作する。多くのネイティブforthコンパイラでもそうだろうと思う。Forthのスタックは実装そのものだと考えている人は今も多いが、forthのスタックとはむしろ抽象データ型である。

とはいえ、iMopsではその“避難”の頻度は割に高い。本当にきちんとやるには、ワード定義の終わりまで先読みして、全体として最適化するか、後になって判明した情報を使って既にコンパイルした部分を再コンパイルするかしないといけない。X86は単位マシンインストラクションのバイト長が区々なため、再コンパイルはかなりキツい。完全に最適化しようとすれば、コンパイル速度はかなり落ちるだろう。しかし、そういった大域的最適化で実際に書いたコードと全然違う処理に変換してしまうのは、あまりforth的ではない。forthでは、プログラマが自分で最適なコードを書く、というのが原則である。それができるし、またプログラマも普通にそうするというのが、forth言語環境の良さであり面白さでもある。iMopsの場合、データスタックに4つ以上のデータを積まないことと、条件分岐のところでは特にスタックを浅く保てるようにすることが、速いコードを生成する基本になっている。

雑論

知識量ではなく、目的の明確さが重要

「コンパイラやインタープリタをつくりたい」と考えると、定評のある教科書、よくあるのがドラゴンの本とか、そういう分厚くて重厚な本の内容を全部勉強しようとする人がいる。勉強するのはよいことではあろうし、学校のペーパーテストとかならそれでバッチリなのだろうが、実際に何かモノをつくるという目的のためには、迂遠な方法であると思う。多分、大抵はあまりの分量に挫折し、それどころか、最後まで勉強し切っても、まだ、どうやってつくるのか分からないという結果に終わるかも知れない。コンパイラやインタープリタの制作が高度な技だと思われている主要な理由は、そんなところにあるのではないかとさえ思われる。「あんなに高度な本を習得しても、まだできない」とかナントカ。

確かに、コンパイラをつくるとなれば、コンピュータという機械がどんな風に動いているか、とか、標準的にはどういう処理手順で回すことになっているのか、とか、そもそもコンパイラというプログラムは何ができないといけないのか、とか、そういう知識は必要である。そして、最近の便利な開発環境で普通にプログラムを書いているだけでは、そういうことは知らないかも知れない。けれども、実際は、そんなに詳しく知る必要はない。だいたい分かっていればいいのである。一番必要なのは、たくさんの知識と学識を身につけることではなくて、今まさにやろうとしていることを明確にすることである。作ろうとしている言語の基本文法と、インタープリタ方式にするかコンパイラにするかみたいなことは、初めに決めないといけない。基本構文を解析する部分は、フロントエンド問題、出力をどうするかはバックエンド問題などといわれるらしい。

インタープリタ方式かコンパイラ方式か

自分の場合、Mac OS Xで動くx86上でネイティブなコンパイラ方式のMops開発環境、ということで初めから絞られていたので、選択の余地はなかった。それをつくる上で解決しなければならない問題、を考えればよいだけだった。Mac OS X上で、Mac OS X用のソフトウェアを開発するとなれば、Xcodeで、言語はObjective-Cとか、ともかくC言語系、というのが普通だが、それだとあまりに当たり前であるし、forth系の異常なほど単純な機構を実現するのに、相当複雑な技を駆使しないといけないように思われた。そこで、forthの伝統的方法、つまり、自己生成という経路で構築することにした。最近のforth系は核部分はC言語で書かれることが多く、それにはいくつかもっともな理由があるのだが、Mopsに関しては、Mopsを構築するのに、Mops以外、他のコンパイラもリンカも要らない。

コンパイラ方式は、原則全て機械語に変換してから実行するので一般に実行速度は速く、インタープリタ方式では、機械の動作に変換しながら実行するので実行速度は遅めになる。ただ、最近は、計算速度が速い機械が多く、よほど濃い処理をしない限り、インタープリタでも、体感で差は感じられないことが多い。一般には、コンパイラ方式の方が難しく、初心者はインタープリタがよい、みたいな空気があるように思われる。けれども、本当はそうでもないような気がする。

とはいえ、まあ、確かにコンパイラ方式だと乗り越えなければならない、結構高いハードルがある。けれども、それは「ターゲット機械のマシン語を知る」というところではなくて、実行可能ファイルをつくるというところにある。厳密に言うと、多くの場合、実行可能ファイルを生成するのは、コンパイラの仕事ではなくて、（静的）リンカという別ソフトウェアの担当である。そういうのも全部まとめてコンパイラセットなどといったりするわけである。「コンパイラの設計」みたいなタイトルの本は、狭い意味でのコンパイラ、つまり、マシン語に変換するという部分のソフトウェアの解説であることが多い。しかも、その"マシン語"は架空のRISCマシンのアセンブリ言語だったりする。実用ではなくて原理を説明する、といわれれば、まあ、確かにそれでいいのだという気もするが、タイトルには「実用」とか書いてあったりする。一番高いハードルまでは、全然到達する気もないのである。そういう意味でも、書籍というのは割とあてにならない。とはいえ、この辺は同じ機械でもOSが違えば違う、みたいなところなので、教科書に書くというわけにもいかないのも確かであるのだが。

インタープリタ方式だと、インタープリタ自体がソフトウェアとして常駐している状態なので、独立に起動できるような実行可能ファイルをつくる必要はない。だから、今の環境で動くアプリケーションを書き出せる開発環境があれば、後はコンパイラ本に書かれてあるようなことだけで済む。そういう、いわば資料的な意味で、インタープリタをつくる方が易しいのである。というか、アプリケーション開発環境とコンパイラ本の世界で限定してみれば、インタープリタしかつくれないのである。だからといって、インタープリタをつくる方が、コンパイラ作成よりも、技術的に易しいとか初歩的だとはいえないように思う。プリミティブ（単位になる動作）を、どんな風に腑分けするかとかは、実行速度にも関連してくるので、結構、面倒な判断である。逆に、コンパイラだと、そういうプリミティブは機械の規格でばっちり決められているので、迷う必要がない。

インタープリタ方式は、今日ではプログラミングの主流となっている。ウェブ経由のプログラムは、コマンド処理のスクリプトというレベルのものであっても、詰まる所はインタープリタによる動作である。連動して動く一組のアプリケーションを、柔軟性や可変性を保ったまま連結する方法として、内部インタープリタ（スクリプト）の機構を持たせる場合も多い。インタープリタはテキストファイルであるソースコードの書き換えで動作を任意に変更することができるが、機械命令にコンパイルしてしまった場合には、コンパイラを用いて再構築し直さないことには、動作を変更できない、というのが一般的だからである。このような意味では、コンパイラをつくるよりも、インタープリタをつくる方が実践的意味があるようにも思える。

とはいえ、例えば、コンパイラ系のforthやMopsでは、ソフトウェア内部にコンパイラを組み込んで、内部スクリプトに利用することもできる。この場合、コンパイラ方式であるため処理は高速でありながら、内容は可変的である。同じことは、「オレ言語」でもできるはずであるから、そこでインタープリタにこだわる理由は、実はないのである。

要は工夫次第で何とかなる場合が多いのであって、どっちでもつくる側としては大差ないよ、という感じだろうか。

【補】用語の問題

何いってんのか、単語の意味が分からん、という人のために、説明。といっても、教科書にあるような正確な定義ではなくて、ここだけの語用の話。背景も説明するので、教科書とかの定義が、一体何がいいたくてそういう風になっているのかも分かるようになる。かも。

ネイティブコード：そのコンピュータの機械語のこと。OSとかには依存せず、機械（ハードウェア）にのみ依存する。
ソースコード：ブログラミング言語で書かれたプログラム。普通はテキストファイルとして保存される。インタープリタもコンパイラも、これをファイルから読み込んで機械の動作に変換する。コーディングをするというのは、これを書くこと。プログラミングをするといっても同義のこともあるが、それにはもっと抽象的な設計や仕様書を書く（その用語もプログラミング言語と呼ばれる）場合も含まれる。コーディングしないプログラマーもいる。テキストファイルといっても文字自体は1バイト（8ビット:ビットは1または0の一桁分）単位の数値で符号化（1文字1バイトとは限らない）されているので、コンパイラやインタープリタは、その符号を解析し、何を命令しているのかをプログラミング言語の文法にしたがって判別し、それと同等の処理動作を表す機械語に変換（そして実行）するのである。
インタープリタ：ソースコードを読み込んで、そのプログラムを実行するアプリケーションソフトウェア。最近は仮想機械（バーチャルマシン）ということが多いようだ。呼称の違いは考え方の問題で、コンピュータやOSとインタープリタを込みで考え、ソースコードを機械命令のように実行できる機械と見なすという発想で、仮想機械というようだが、ちょっと商売くさい意図が感じられる気がする。動作は、原始的というか原子的な部分は、もうアプリケーションで組んでしまって、ソースコードの内容を解析して、その原始的動作の系列に分解して実行するわけである。
コンパイラ：ソースコードを読み込んで、その内容を"機械が"実行できる命令の系列に変換して保存するアプリケーションソフトウェア。意図的にかなりぼかした説明。"機械が"に引用符を付けたのは、Javaとかのコンパイラは、本当の機械命令に変換するのではないのに、やはりコンパイラだからである。同じJavaでも機械命令に変換するのもあったりするのでややこしい。また、「保存する」先もファイルとは限らない。メモリーでもよい。ファイルに保存したとしても、それがそのまま実行可能なファイルとは限らない点は先述。「コンパイル」というと機械命令に変換することと短絡してしまう傾向はあるが、もともとはそういう意味ではないらしい。コンパイルは普通の英語なのであって、製本するという意味がある。それがコンピュータに適用された際には、多分、プログラムの内容を、機械で実行される命令の系列として一本に束ねる、というような意味合いであったのではないかと思われる。だから、forthはインタープリタ環境であったけれども、定義は「コンパイル」されるのである。コンパイラの出力が機械命令を含んだファイルとして保存されるとき、生成されるファイルは、オブジェクトファイルとかアーカイブファイルとかいわれたりする。この種のファイルはそのまま実行はできないことが多い。後でリンカが処理する。だから利用されるリンカアプリケーションに依存して形式は決まる。オブジェクトファイルにはリンク用に関数のリンク表も組み込まれる。関数（サブルーチン）の名前と対応する機械命令系列の位置（同じファイル内にある場合）などを、符号や文字列や数値を用いた既定の形式で書き込む。この表（テーブル）も必要ならコンパイラが生成すべきデータである。
実行可能ファイル：アプリケーションを起動する過程は、実はそれほど単純ではない。OSがその過程をサポートするわけだが、OSが理解できるようなファイル形式（内容のことではない）でないと何をどうサポートしていいかわからない。つまり、OSが「あ、これはアプリケーションで、起動するにはコレコレが必要だな」と理解できるような形式というのが、実行可能ファイル形式である。だから、それはOSと一緒に規格として決まっている。Mac OS XだとMach-Oフォーマットという名前で呼ばれている。Windowsは、良く知らないが、.exeの形式で、形式名はPE。確かおおもとはCOFF（UNIXのだったと思う）というのだったとどっかで見た気がする。略号のoは「オブジェクトファイル」のオである、確か。以前のPowerPC MacではPEFという名前で、Windowsのものと名前が似ているが、WindowsのPEのPはポータブルで、PPC Mac のPEFのPはPreferredなので別物である。ただ、基本は古いUNIXでの規格を元にしているようなので、大まかな形式は似ている。だいたい、ヘッダデータというのが冒頭に付いていて、実行ファイルであることとか、実質部分の大きさや配置構造、エントリーポイント（コードの最初の位置）、起動に必要な情報や命令とかが、既定の符号とか数値、文字列などで記録されている。そしてその後に、まさに機械命令の系列とかグローバル変数のための領域（実質部分）とかが続いているわけである。実行可能ファイルにも動的に関数にリンクするためのテーブル（表）が、普通ついている。ちなみに、LinuxではELFという名前だったと思う。
リンカ：最後の「カー」は伸ばした方がいい(linker:つなげるもの)と思うが、ここでは略す。リンカには二種類ある。静的リンカと動的リンカである。コンパイラの後に作動して実行可能ファイルをつくるのは静的リンカである。リンケージエディターとかリンクエディターとかいったりもする。動作としては、生成されたオブジェクトファイルから必要な部分をコピーして１つのファイルにまとめ、オブジェクトファイルのリンク表を使って呼び出しとかをうまく整合させて動作可能な状態にし、ヘッダをつくって実行可能ファイルフォーマットにするのである。また、実行ファイル用の関数リンク表もつくる。外部から関数にリンクしたり、逆に、外部の関数にリンクしたりするのに利用するのである。この「外部とのリンク」を実現するのが動的リンカである。動的リンカはOSサービスとして常駐しているソフトウェアで、アプリケーションが動作中に外部の関数を利用したいとき、この動的リンカの助けを借りてリンクするのである。動的リンクは、関数名文字列を渡して関数ポインタをもらい、そこにジャンプする、という感じになっている。

コンパイラ方式のハードル

実行可能ファイルを出力するコンパイラ方式の開発環境をつくろうとすると、ちょっと前にも書いたように、ターゲット環境の実行可能ファイルフォーマットの仕様を調べないといけない。これは英語であれば大抵資料はある。Macの場合、Appleの開発資料サイトにある。けれども、実は、ファイルフォーマットだけ分かっても、不十分である。というのは、外部関数を呼び出さないことには、アプリケーションは大したことができないからである。OSサービスとか標準Cライブラリの関数とか、外部関数の呼び出しは、ヒープメモリーを確保するという低レベルなことにさえも必要である。関数呼び出し一般には、そのための関数があるので、それを使えば良い。ところが、その関数も外部関数なのである。つまり、問題は、最初のOS関数呼び出しはどうするのか？である。

Mac OS Xで使われるMach-Oフォーマットに関しては、関連部分がオープンソースプロジェクトになっていたりして、自分の場合はナントカ動作方法は分かった。要するに、関数ポインタ専用フレームをデータ域内に準備して、その位置をヘッダで明示しておけば、アプリケーションを起動する際、OS側（ローダーと呼ばれるアプリケーション）が、外部への動的リンク用関数など、必要な関数のポインタをその場所に書き込んでくれるのである。Mach-Oの場合、そのポインタ格納用フィールドは、dyldセクションと呼ばれる。フルでいえば、ダイナミックリンクエディターセクションであるらしい（なぜか後半はleではなくldである。）。その枠の冒頭にはジェネリックな関数呼び出し用関数のポインタが格納される。Mopsでは、起動時のセットアップのために呼び出される外部関数が数個あるが、これらは、このジェネリック呼び出し関数を使って関数ポインタを取り、そこに分岐する。一旦取った関数ポインタは普通、終了まで変更されることはないので、保存しておいて、二回目以降は、そのポインタで直接リンクする。この数個の関数の中には、関数名から外部関数ポインタを取るための標準関数（dlopen()とdlsym()）も含まれている。これらの関数は、いってみれば、動的リンカのサービス関数なわけである。本当はこの二つだけ取っておけば後は全部リンクできるのだが、他にも数個、初期の外部呼出関数として同じ方法で呼び出している。それら以外は、全部、標準の動的リンク関数を用いている。オブジェクティブCのメソッドとかにもリンク可能になる。オブジェクティブCの、Cocoaなど、ハイレベルな外見のオブジェクト指向部分といえども、中身はC言語型の補助関数の組み合わせだからである。

Mac OS以外の環境での実行可能ファイルの規格や起動の手順も似たようなもののようではあるが、細かいところはどうなっているのかよくわからない。これは調べるしかない。普及した環境なら、多分結構資料は充実しているし、ネット経由でタダで手に入ると思う。ただし、英語だと思うけれども。コンピュータ関係なら、英語にひるまなければ、大抵のことは調べがつく。

とはいえ、どうしても分からないというときには、インタープリタ方式にして、実行可能ファイル形式の部分は、既に手元にある開発環境にまかせてしまうという手もある。それにもかかわらず、やっぱりコンパイラ方式にしたい、というのであれば、いくつか可能性はある。

このページは、もう長くなってしまったので、ベージを替えて続きを書いてみることにする。（そのうち）

「forthとコンパイラ」をウィキ内検索

最終更新：2017年11月16日 18:47

iMops-forth @Wiki