川合のプログラミング言語自作のためのテキスト第三版#1 ~ 通称「10日くらいでできる!プログラミング言語自作入門」

  • (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-9aまで読んでみてください。

  • もくじ(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-5214行7.5KB少し高速化260倍
    a21_txt01_6HL-6284行8.0KBもっと高速化(がんばった!)13.2倍
    a21_txt01_6aHL-6a297行8.5KBさらに高速化!(これをやるかどうかは好みが分かれるかも)5.5倍
    a21_txt01_7HL-7445行9.5KB式の導入(なんか急にかっこよくなった!)5.5倍
    a21_txt01_8HL-8557行11.0KBforやブロックifの追加5.5倍
    a21_txt01_8aHL-8a635行12.0KB配列や文字列リテラルの導入5.5倍
    a21_txt01_9HL-9754行19.5KBグラフィック命令の追加5.5倍
    a21_txt01_9aHL-9a772行20.0KBC言語っぽく改造(画像あり)5.5倍
    a21_txt01_10ここまでのまとめ・今後の課題
    [ a21_txt02 ]HL-11~続編(JITコンパイラ・普通のコンパイラ・理想の新言語へ)
    • (註)「.exeの大きさ」はWindows向けにgcc(MinGW)でコンパイルした時の大きさです。
      • しかしここで扱う言語処理系は、Windows専用というわけではなく、他のOSでも問題なく動作するようになっています。
      • 純粋に言語処理系の規模の目安を示すために書いてあります。
      • 基本的には小さければ小さいほどシンプルで、教材として理解しやすいと思っています(可読性を下げてまでのコンパクト化をやらないとして)。
      • 行数を書いているのも同じ意図です。行数だけだと、1行の文字数をうんと増やすことで、見かけ上の行数を減らすことができますが、そんなことをしても実行ファイルサイズは減らないので、
        この二つを併記すれば、規模感の目安としては十分だと思っています。
    • 「速度のめやす」は、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言語が得意じゃない人でも分かりやすくなるように一定の配慮をしています。
    • ポインタはやむをえないときは使っていますが、ポインタに対する加算や減算はできるだけやらないようにしています(ポインタは配列みたいなものだと理解している場合、ポインタに対する演算があるとそこで難しく感じてしまうので)。こういうマイルールを自分に課しています。

(5) 重要な注意事項

  • [Q]HLシリーズのソースコードは、グローバル変数を多用しているし、バッファオーバーランに対してもほとんど何の対策もせず、マジックナンバー(説明のない数値定数)も多く、さらにはstrcpy()などの危険な関数まで平気で使っており、とてもじゃないがきれいなソースコードとは言えない。こんなものをプログラミング初学者に見せていいのか??悪い例のデパートじゃないか!
    • [A]全面的にその通りです。私の意図は、とにかくエラーチェックを省略し、言語処理系として何をしなければいけないかだけを説明しきることです。セキュリティホールはとてもたくさんあるでしょう。もっと読みやすくすべきだと思うでしょう。それはぜひ、テキストの読者が自発的にやってくれればと思っています。・・・そしてその作業が、言語処理系への理解を深めると思っています。
    • これは私の説明のための教材であって、製品や実用的な言語処理系ではありません。私はこのレベルのものが製品になっていいなんてみじんも思っていません。しかし現在のスタイルのほうが、より教育的であると思って、あえてこのスタイルにしています。
    • またセキュリティを教えようと思ったときに、このプログラムはこういう風に書いているからダメ、みたいに教えることはままありますが、そういうときに、いかにもセキュリティホールがあるプログラムを用意して提示しても、「わざとらしい」感じがして、うまく授業にならないことがあります。一方で、このHLシリーズや「はりぼてOS」のように、意図せずにセキュリティ的に甘いところがあるプログラムがあると、この中から問題のある書き方を探しなさい、という課題が非常に盛り上がります(私がそういう経験をしています)。この脆弱性を使って実際に攻撃するためにはどうしたらいいかという議論もできましたし、それで攻撃が成功して大いに盛り上がったこともありました。そういう用途も想定した上で、このスタイルになっていることをご理解ください。

(6) 切実なお願い

  • このテキストは上記の通り、いろいろと問題を含んでいます。これを直すべきだ、直したバージョンも作るべきだ、それもあれば大いに勉強になるだろう、という指摘はもっともです。特にすべて直してしまうと教材としての価値が下がるかもしれないけど、何か一番ひどい関数だけでもいいから、解説付きで直した例があるべきだ、というのは非常に説得力があります。
  • また、HL-2以降のプログラムは差分で提供されており、入力ミスなどでうまく動かない場合に、ちゃんと動く比較可能なものがありません。そういうのを作っておいて提供すべきだという意見もあります。
  • またそもそも変数名や関数名などもきれいに読みやすくするべきだという意見もあります。
  • エラーチェックを略した説明に徹するのであれば、C言語ではなくPythonなどでコードを書くべきだったのではないかと言われました。そうするとPythonでC言語っぽい文法を実装することになりますが、それはそれで2言語の知識が必要になって面白くないので、言語もPythonっぽくするべきかなとは思いますが、しかしとにかく、「エラーチェックを略したいならC言語は適当じゃない」はまっとうな意見だと思います。
  • 全部もっともです。・・・しかし、それを全部私がやったら、それでまた数か月を要してしまうだろうなと思いました。
  • それに仮に私がやれば、それは私が「あれもこれもやった、すごい人」になるだけです。いやいや私はそんなものにはなりたくないのです。私は「はりぼて言語のオリジナル版の製作者」という肩書だけで十分です。だからもし他の人がこれらのうちのどれかを手掛けてくれたら、私は手間が省けて時間が節約できてもっと前進できるし、その方はその方で努力に見合った称賛を受けられるようになるしで、一石二鳥ではないでしょうか。
  • ということで、この「はりぼて言語」に関する何かをやってくださった方は、a21_bbs01でご連絡ください。ここに挙げられたことでも、それ以外のことでもいいです。こちからリンクさせていただきます!
  • もししばらく待っても何もやってもらえなかったら・・・しょうがないので、時間を見つけて私が自分でやります・・・。

次回に続く

こめんと欄

  • すみません、構文ハイライトが欲しいです! -- 名無しさん 2021-04-22 (木) 19:09:56
  • ごもっともです。・・・どなたか、ここのプログラムを勝手に使って、みやすいサイトを作ってくれたらうれしいのですが・・・。 -- K 2021-04-22 (木) 23:06:18

コメントお名前NameLink

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