とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

プログラム言語を考える (7)

コンパイラとは

もうね,日常生活そっちのけで一日中このことばっかり考えてる。頭が割れるような頭痛がするけど気にせずに。
いやー,今日,一つ分かりました。「コンパイラチューリングマシントランスレータだ」ってことです。うーん,かっこいい響きだぜ!

チューリング完全の最小の要素って何だろう?ってずっと考えていたらこんな(あたりまえの)結論が出たわけですが,ここで言う「チューリングマシン」とはチューリング完全*1任意のプログラム言語と機械語(すなわちプログラムの実行)の事です。トランスレータってのは変換器のことです*2

単純な変換 (上位互換)

チューリング完全 - Wikipedia
ここを見ると,「純Lisp」と「Brainfuck」はチューリング完全なようです。手続き型の言語になれた方でしたら,Brainfuck形式のチューリングマシンが分かりやすいでしょう。まず,Brainfuckの方から考えてみます。

Brainfuck

Brainfuck - Wikipedia
この言語はたった8つの命令からなる,非常にシンプルな処理系です。さぁ,インタプリタを書きましょう!きっとプログラム言語Cインタプリタを書けば簡単です。なぜだと思いますか?
C言語Brainfuckの機能を包含しているからです。実際,Wikipedia には Brainfuck と C の対応が書いてあります。最小のチューリングマシンを考える上で Brainfuck は非常に参考になります。

純Lisp

純LISP - Wikipedia
この言語はたった5つの命令からなる,非常にシンプルな処理系です。さぁ,純Lisp処理系を書きましょう!きっとプログラム言語C++で書けば簡単*3です。なぜだと思いますか?
C++言語のテンプレートが純Lispの機能を包含しているからです。
以下,実装例:
おびなたのはてな日記 - C++テンプレートは計算完備
おびなたのはてな日記 - C++テンプレートでLisp
予定は未定Blog版 - C++テンプレートとマクロでLisp
ひげぽんさんは Scheme を実装する上で「C++のテンプレートをうまく使いたいなとか思っています。」とコメントしているが,この純LispC++のテンプレートの対応を当然の事として知っていたのだと思います。
ひげぽん OSとか作っちゃうかMona- - 未踏

単純ではない変換

今,これについて考えています。純Lisp←→Brainfuckの変換です。他のシンプルでチューリング完全な言語についても調べています。
さらに,コンパイラインタプリタ(とアセンブラと逆アセンブラ)の区別についても考えてみます。
C++について考えてみます。C++のコンパイル時の言語と実行時の言語の入力言語と出力言語について考えてます。Schemeのマクロと比較して考えてみたいと思います。C++→Cのコンパイラ(トランスレータ)cfrontについても考えてみたいと思います。言語内言語についてももう少し考えてみたいと思います。
脳みそを沸騰させる参考資料:
更新履歴兼雑記
更新履歴兼雑記
更新履歴兼雑記
お、大阪っすよ!
いやいや,読んだ当時はよく分かってなかったけど,プログラム言語についてひたすら考えていたらこれらの資料を思い出し,かつ理解しかけてる。頭のいい人たちの思考パスを自分もたどっていると思うとなんかうれしい。

*1:つまりチューリングマシン互換の

*2:あぁ,説明になっていませんね。

*3:ただ,語呂をあわせて「簡単」言っただけです。真に受けないで。