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

  • (by K, 2021.02.28)

(1) はじめに

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

  • このテキストでは、最初はインタプリタ(スクリプト言語)の作り方を説明します。そしてある程度いろいろできるようになったら、JITコンパイラや普通のコンパイラの作り方も紹介します。
  • というとなんだか欲張りな構成ですが、結局プログラミング言語はインタプリタでもコンパイラでも共通の部分が多くて、だからついでに全部紹介してしまうのは効率的なのです。

  • 目的別ガイド:
    • とにかく言語の本質だけが知りたければ、HL-1だけ読めばいいです。49行で処理系を理解できます。
    • トークンを使って変数名を可変長にするやり方を知りたければ、HL-2まで読めば十分です。
    • 基本的な分岐処理を理解したければ、HL-3まで読めばいいです。
    • REPLの例が見たければ、HL-4まで読めばいいです。
    • 実行速度を高める工夫に興味があれば、HL-5やHL-6まで読めばいいです。HL-6では内部に簡単なVMを作ります。徐々にコンパイラっぽくなってきます。
    • 演算子の優先順位を反映した式の評価をやりたければ、HL-7まで読めばいいです。
    • for文やブロックif文などの実装方法に興味があれば、HL-8まで読めばいいです。
    • インタプリタ編を最後まで読みたければ、HL-9まで読んでみてください(→この段階でどの程度のことができるのかについて、a21_tl9aに詳しく書きました)。

  • もくじ(HL-1から順番に読んでいくとわかるように書いています)
    ページ名名前行数.exeの大きさ説明速度のめやす
    a21_txt01HL-149行6.0KB初めの一歩、たった49行のシンプルすぎる言語処理系計測不能
    a21_txt01_2HL-2128行6.5KB変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに計測不能
    a21_txt01_3HL-3148行7.0KB条件分岐などをサポートしてループ処理が可能に1520倍
    a21_txt01_4HL-4186行7.5KBREPLの導入(これは楽しい!)1520倍
    a21_txt01_5HL-5215行7.5KB少し高速化260倍
    a21_txt01_6HL-6285行8.0KBもっと高速化(がんばった!)13.2倍
a21_txt01_6aHL-6a303行8.5KBさらに高速化!(これをやるかどうかは好みが分かれるかも)6.5倍
a21_txt01_7HL-7456行9.5KB式の導入(なんか急にかっこよくなった!)6.5倍
a21_txt01_8HL-8622行12.0KBforやブロックifの追加6.5倍
a21_txt01_9HL-9グラフィック命令の追加
a21_txt01_10ここまでのまとめ・今後の課題
a21_txt01_11HJ-1最初のJITコンパイラ
  • (註)「.exeの大きさ」はWindows向けにgcc(MinGW)でコンパイルした時の大きさです。
    • しかしここで扱う言語処理系は、Windows専用というわけではなく、他のOSでも問題なく動作するようになっています。
    • 純粋に言語処理系の規模の目安を示すために書いてあります。
  • 「速度のめやす」は、C言語で10億回ループさせた場合と、この言語で10億回ループさせた場合の処理時間の比を書いています。数が大きいほうが遅いです。
    • なお、gccに対しては「-O3」という一番強い最適化を指示しています。
    • 遅すぎて10億回もまわせないときは、1億回とかにへらして、その結果を10倍して記入しています。
    • おおざっぱな目安です。

(2) HL-1

  • 事前の説明はこれくらいにして、とにかく言語を作ってみます。これは「HL-1」です。HLは「はりぼて言語」の略です。HL-1は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); // iは読み込んだバイト数.
    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] == '\r' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';')   // 空行など.
            continue;
        if (txt[pc + 1] == '=' && txt[pc + 3] == ';') { // 単純代入.
            var[txt[pc]] = var[txt[pc + 2]];
        } else if (txt[pc + 1] == '=' && txt[pc + 3] == '+' && txt[pc + 5] == ';') { // 加算.
            var[txt[pc]] = var[txt[pc + 2]] + var[txt[pc + 4]];
        } else if (txt[pc + 1] == '=' && txt[pc + 3] == '-' && txt[pc + 5] == ';') { // 減算.
            var[txt[pc]] = var[txt[pc + 2]] - var[txt[pc + 4]];
        } 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言語でたったの49行です。もちろん機能は少ないですし、たくさんの制限もあります。
    • 変数名は半角一文字のみ。
    • 数値定数は整数で一桁のみ。
    • しかも「a=3;」みたいにスペースを入れずに書かなければいけない。
    • ひとまず代入と足し算と引き算とprintしかできない。
    • printは「print 変数名;」の形式のみ解釈できる。このときのスペースは必ず1文字。
  • ええ本当にひどい仕様だと思います。・・・かつてのタイニーベーシックよりもさらに低機能です。でもとにかく出発点としては悪くないと思うんです。だってたったの49行ですよ?
  • しかも<stdio.h>と<stdlib.h>しか使っていません。それでも49行でここまでできるんです。
    • <stdio.h>はprintf()とファイル入出力のために使っています。
    • <stdlib.h>はexit()のために使っています。
  • このHL-1は以下のプログラムを問題なく実行する能力があります。以下の内容のテキストファイルを作って保存して(たとえば prog1.txt )、そのファイル名をHL-1のコマンドライン引数に渡せば実行できます。
    a=1;
    b=2;
    c=a+b;
    print c;
  • 今は足し算と引き算しかないですが、掛け算や割り算を追加するとしたらどうしたらいいかわかりますか?分かりますよね。
  • この先で、最初に課した制限を少しずつ減らしていきます。するとだんだんマシな言語になります。差分を追いかければ、どの制限をなくすことが言語を複雑にしているのか、理解できるようになるでしょう。

(4) HL-1の簡単な説明

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

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-03-04 (木) 01:15:07 (3d)