川合のプログラミング言語自作のためのテキスト第二版#0001

  • (by K, 2019.06.29)

(1) はじめに

  • 「プログラミング言語を作ってみたい」と思ったことがある人は、プログラマの中にはけっこうたくさんいるのではないかと思います。・・・でも、実際に作ってみた人はそれほどには多くないかもしれません。それはなぜでしょうか。
  • おそらくは、多く人にとってプログラミング言語を作るのは難しいということになっているからだと思います。そう思うからこそ、チャレンジするまでもなくあきらめてしまうわけです。とてももったいないです。
  • 私はプログラミング言語は(世間の人が思っているよりは)ずっと簡単に作れるものだと思っています。・・・今からここにそのためのテキストを置きます。これを読んで是非作れるようになってください。そうすれば「作りたいけど、作り方が分からない」を卒業することができます。そして今後は「じゃあどんな言語を作ろうか」をメインで考えられるようになるのです。それはとても素敵なことだと思います。
  • この時点では「本当にプログラミング言語を作るのは簡単なのか?」という疑問を持つ人は少なくないと思いますが、かつてはタイニーベーシックのような言語があり、それはたった数キロバイトの機械語でした。それらの言語はもちろん言語を作りやすくするために文法規約にいろいろと制限がありましたが、つまり逆に言えば、適切な制限を導入すれば言語は簡単に作れるということなのです。私はこの観点で言語の作り方をどう教えるかを研究してきたのです。

  • このシリーズが主張していること:
    • [1] プログラミング言語を作るのは難しくない!
    • [2] JITコンパイラはとても高速。しかも難しくない!
    • [3] うまくライブラリを作ると、有用な言語を自作するのと同じくらいの効果がある

  • 1億回ループでのベンチマーク
    言語処理系行数タイプ説明実行時間(gccの-O3を1.00としての相対値)リンク
    TL-3c119行単純インタプリタ代入・加算・減算・print・whileのみサポート627.85倍text0012
    TL-3d123行単純インタプリタTL-3cを高速化したもの55.35倍text0013
    TJ-03a185行JITコンパイラTL-3dをJITコンパイラ化したもの6.78倍text0014
    TJ-03b224行JITコンパイラTJ-03aにレジスタ変数を追加して高速化1.70倍text0015
    TJ-03c247行JITコンパイラTJ-03bにdo~whileを追加して高速化1.00倍text0016
    • JITコンパイラ(註:JITコンパイラはインタプリタ実行のための技術)によって、コンパイラのほうが高速であるという時代は終わりました。

  • ライブラリの威力
    言語処理系行数削減率実行時間(gccの-O3を1.00としての相対値)
    TL-1k(TL-1c相当)52行→31行40.4%削減text0017
    TL-2k(TL-2c相当)104行→31行70.2%削減text0018
    TL-3k(TL-3d相当)123行→45行63.4%削減46.00倍text0019
    TJ-03x(TJ-03a相当)185行→61行67.0%削減6.78倍text0020
    TJ-03y(TJ-03b相当)224行→78行65.2%削減1.70倍
    TJ-03z(TJ-03c相当)247行→88行64.3%削減1.00倍
    • 仮に言語を自作としたとして「私の自作言語を使うことで、コードが6割以上削減できます!」みたいな主張ができたらかっこいいですよね。でもこのように、新言語を作らずともライブラリを作るだけで、同じような効果を得ることができるのです。
    • 一般にライブラリを作るのは言語を作るよりもずっと楽です。既存言語の上に付け足すだけだからです。
    • ちなみにJITコンパイラが100行未満で作れちゃうのは、「かなり優秀」だと自分では思っています!

(2) インタプリタかコンパイラか

  • プログラミング言語は、大きく分けるとインタプリタ型とコンパイラ型に二分できると思います。コンパイラ型は、ソースコードをコンパイラにかけると実行ファイルが出力されてきます(アセンブラソースが出力されるタイプもあります)。実行に際しては、この実行ファイルだけがあればよく、ソースコードもコンパイラ本体も不要です。一般にコンパイラ型はアプリケーションの実行速度が高速で、上級のプログラマに人気があります。またコンパイルはソースコードが大きくなってくるとそれなりに時間を要するようにもなります。
  • 一方でインタプリタ型は、ソースコードを実行前にコンパイルしておく必要はなく、そのまますぐに実行できます。ただ実行に際しては、ソースコードと言語本体の両方が必要です。また実行速度はコンパイラには劣るというのが普通です。コンパイルを必要としないので、気軽に実行することができ、コンパイラと比較すれば初心者に人気がある言語だと言えるかと思います。
  • こう書くとなんだかコンパイラ型がとてもよさそうに思えますが、実は私はまったくそう思っていません。コンパイラ型には「未来」や「発展性」がないのです。なぜならeval命令との相性がよくないからです。
  • eval命令というのは、プログラムの中で "i = 3;"みたいな文字列を生成すれば、eval命令によってそれをただちに実行することができる、という機能を指します。・・・この機能をインタプリタ型の言語に持たせるのはかなり容易です。なぜならインタプリタはまさにその機能を使ってプログラムを実行しているからです。・・・しかしコンパイラはそうはいきません。コンパイラによって生成された実行ファイルは、もうその言語を解釈するための仕組みは持っておらず、変換された結果の機械語しかないからです。
  • eval命令はそんなに重要でしょうか?・・・その話をする前に、JITコンパイラの話をしようと思います。・・・JITコンパイラというのは、(その名称にもかかわらず)インタプリタ型の言語を作るためのテクニックです。これにより、インタプリタ型でありながら、コンパイラ型に負けない実行速度でプログラムを実行することができるようになります。
  • どうしてそんな魔法みたいなことができるのかと言えば、つまり言語は実行に際してソースコードを機械語に変換してしまうからです。その変換をしてから実行するのです。たいていこの変換時間はかなり軽微で、ほとんど体感できないので、ユーザはインタプリタとしてこの言語を扱えます。
  • ここで既存のプログラミング言語で新しいJITコンパイラを作ることを考えてみましょう。もしeval命令があればJITコンパイラを作るのは簡単です。実行したいプログラムを適当に変換して、それをevalすればすぐに実行できるからです。でもコンパイラ型の言語にはeval命令がないので、言語プログラムはevalしたい文字列から自力で(=言語の助けなしに)機械語を生成しなければいけません。ライブラリとかを使えばできる場合もあるかもしれませんが、それはどちらかというとレアケースで、何のサポートもない場合だって十分にあり得ます(たとえばあなたはC言語のソースコードをevalできるライブラリに心当たりがありますか?かなりメジャーな言語であるC言語でさえそんな状況なのですよ)。
  • evalがない言語でJITコンパイラを書こうと思ったら、機械語の勉強をしなければいけないですって?ちょっと待ってください、今は21世紀ですよね。新しい言語をJITコンパイラで作ろうと思ったら機械語に戻らなければいけないんて、いったい今までのソフトウェア技術の積み上げは何だったのでしょうか。みんな機械語やアセンブラをやらずに済ませるためにプログラミング言語を開発してきたのではなかったのですか?・・・つまりコンパイラは根本的なところで、ソフトウェア技術を進歩させていなかったのです。進歩していたのは表面だけなんです。コンパイラはコンパイラを機械語の知識なしで作ることができますが、JITコンパイラを作ることはできないのです。・・・一方でインタプリタは機械語の知識なしにJITコンパイラを作ることができるのです。インタプリタで普通のコンパイラももちろん作れます。つまりインタプリタは万能なのです。
  • そして今まではインタプリタは遅いとバカにされてきましたが、JITコンパイラの技術を使えば、それはもはや問題にならないのです。
  • いろいろ書きましたが、つまり川合はJITコンパイラで作ったインタプリタが大好きで、コンパイラはあまり好きじゃないということです。だからこのテキストでは、普通のインタプリタと、JITコンパイラの作り方しか紹介しません。
    • コンパイラは好きじゃないとか言いつつ、組み込み向けとかではコンパイラの方がいいのはよくわかっていますし、自分自身も今はC言語(=コンパイラ)をよく利用しているので、絶対にコンパイラがダメだと思っているわけではありません。
    • 要するにここで作り方を説明していないことに対するいいわけみたいなものです(苦笑)。

(3) TL-1c

  • うざい説明はこれくらいにして、とにかく言語を作ってみようじゃないですか。これは「TL-1c」です。C言語で書いています。
    #include <stdio.h>
    #include <stdlib.h>
    
    void loadText(int argc, const char **argv, unsigned char *t, int siz)
    {
        FILE *fp;
        int i;
        if (argc < 2) {  // 引数が少ないのでエラー表示して終了.
            printf("usage>%s program-file\n", argv[0]);
            exit(1);
        }
        fp = fopen(argv[1], "rt"); // テキストモードでファイルを開く.
        if (fp == 0) {  // ファイルを開けなかった.
            printf("fopen error : %s\n", argv[1]);
            exit(1);
        }
        i = fread(t, 1, siz - 1, fp);
        fclose(fp);
        t[i] = 0; // 終端マークを書いておく.
    }
    
    int main(int argc, const char **argv)
    {
        unsigned char txt[10000]; // ソースコード.
        int i, pc, var[256];	// varは変数.
        loadText(argc, argv, txt, 10000);
        for (i = 0; i < 10; i++)
            var['0' + i] = i; // テクニック#1.
        for (pc = 0; txt[pc] != 0; pc++) {
            if (txt[pc] == '\n' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';')   // 空行など.
                continue;
            if (txt[pc + 1] == '=') { // 2文字目が"=".
                if (txt[pc + 3] == ';') { // 単純代入.
                    var[txt[pc]] = var[txt[pc + 2]];
                } else if (txt[pc + 3] == '+' && txt[pc + 5] == ';') { // 加算.
                    var[txt[pc]] = var[txt[pc + 2]] + var[txt[pc + 4]];
                } else if (txt[pc + 3] == '-' && txt[pc + 5] == ';') { // 減算.
                    var[txt[pc]] = var[txt[pc + 2]] - var[txt[pc + 4]];
                } else
                    goto err;
            } else if (txt[pc] == 'p' && txt[pc + 1] == 'r' && txt[pc + 5] == ' ' && txt[pc + 7] == ';') { // 最初の2文字しか調べてない(手抜き).
                printf("%d\n", var[txt[pc + 6]]);
            } else
                goto err;
            while (txt[pc] != ';')
                pc++;
        }
        exit(0);
    err:
        printf("syntax error : %.10s\n", &txt[pc]);
        exit(1);
    }
  • はいこれだけです。C言語でたったの52行です。もちろん機能は限定的です。
    • 変数名は半角一文字のみ。
    • 数値定数は整数で一桁のみ。
    • 「a=3;」みたいにスペースを入れずに書かなければいけない。
    • ひとまず足し算と引き算とprintができればいい。
  • ええ本当にひどい仕様だと思います。・・・かつてのタイニーベーシックよりもさらに低機能です。でもとにかく出発点としては悪くないと思うんです。だってたったの52行ですよ?
  • しかも<stdio.h>と<stdlib.h>しか使っていません。それでも52行でここまでできるんです。
  • このTL-1cは以下のプログラムを問題なく実行する能力があります。以下の内容のテキストファイルを作って保存して(たとえば prog1.txt )、そのファイル名をTL-1cのコマンドライン引数に渡せば実行できます。
    a=1;
    b=2;
    c=a+b;
    print c;
  • 今は足し算と引き算しかないですが、掛け算や割り算を追加するとしたらどうしたらいいかわかりますか?分かりますよね。
  • この先で、最初に課した制約を少しずつ減らしていきます。いつの間にかけっこうまともな言語になります。差分を追いかければ、どの制約をなくすことが言語を複雑にしているのか、理解できるようになるでしょう。

(4) TL-1cの簡単な説明

  • 関数:
    • loadText() : コマンドライン引数で指定されたソースファイルを配列変数に読み込む。
    • main() : 言語処理の本体。
  • 変数:
    • var[] : 変数の値を記憶しておくための変数。
    • txt[] : ソースコードを記憶しておくための変数。
    • pc : 現在プログラムのどこを実行しているのかを記憶するための変数。
  • プログラム中で「テクニック#1」と書かれた部分があります。ここがやっていることは、「3」という定数さえも「3」という名前の変数であると解釈することにして、その代わり変数「3」には初期値として3を代入しておくのです(そうでないと変数「3」を参照したときに3にならなくなってしまうため。
    • こうすることで、プログラムでは以降変数と定数を区別する処理が不要になって、TL-1cは短く書けるようになります。
  • C言語での文字列の扱いに不慣れな人のために、簡単な説明ページを作りました。必要な人はご利用ください。→text0001a
  • [隠れたこだわり]
    • このTL-1cやそれ以降のプログラムは、C言語が得意じゃない人でも分かりやすくなるように一定の配慮をしています。
    • ポインタはやむをえないときは使ってもいいが、ポインタに対する加算や減算はしない(ポインタは配列みたいなものだと理解している場合、ポインタに対する演算があるとそこで難しく感じてしまうので)。
    • 文字列を扱うときは極力標準関数で扱える形式にする。

次回に続く

こめんと欄

  • (2)の内容について、コンパイラが上級者向けで、インタプリタがそれと比較すれば初心者向きであるという説明は、少なくとも近年の傾向とは違うのではないかという指摘を受けました。そうかもしれません。これらの記述は以降の説明の本質とは無関係なので、私としては結論がどちらでも構いません。 -- K 2019-02-25 (月) 23:10:33

コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-06-30 (日) 07:58:17 (139d)