ハッカーも同じように、良いプログラムを見ることでプログラムを学ぶことができる。プログラムの動作を見るだけでなく、ソースコードを見ることでもだ。 - ポール・グラハム

はじめに

Kuin Advent Calendar 2018、残り３日となりました。このコンピュータ・サイエンス・セミナー(CSセミナー)の目的は、次の２つです。

くいなちゃんの思想に共感する人間を増やして、くいなちゃんがより多くの偉大なことをできるようにすること。
プログラミング初心者に、より登りやすい梯子を用意することで、プログラミング・パラダイムの進化と世界文明の発展に寄与すること。

さて、これからの３日間ではKuinのリポジトリを部分的に写経することによってKuin言語でKuinコンパイラを作成します。前回では、電卓を作成しました。パーサを作成するにあたって電卓を作れるようになること自体すごいことです。たいていの人はここでつまづきます。または電卓を作ることはできるのだけど、その先に進むと詰まってしまうという人が多かったりします。それはパーサジェネレータと格闘するのが難しいということなのですが、パーサをフルスクラッチで記述する汎用的な方法を知っておけばちょっとしたつまづきに対処することはできるでしょう。例えばC言語はパースする前にプリプロセッサが動作しますが、これは字句解析部や構文解析部を多段にしたりすることで対処できます。

とはいえ、前回示した方法でKuinを実装しようとすると少なくとも一か月はかかることでしょう。パーサを巨大化すると、今まで見えてこなかった課題が次々と見えてくるからです。だから、既存の処理系を模写するのです。どうして言語を自作する人間よりも既存の言語を利用する人間が多いのでしょうか。それはプログラミング言語をメンテナンスするのに大変な労力を必要とするからです。それっぽいプログラミング言語を作成することは簡単です。しかしコンパイラにはパーサの他にもコード生成部と呼ばれる部分があり、ここが複雑だったりします。電卓のプログラムにおいても数式の計算をする関数のボリュームが案外多いことに驚かれたことでしょう。

もちろん３日間でKuin言語の全てを模写することはできません。私たちはすでにパーサについての知識を持っているのですから、Kuinのパーサをできるだけ忠実に再現して、コード生成部は最低限にとどめることで落としどころといたしましょう。つまりこの試みは、Kuinコンパイラのソースコードを読むためのチュートリアルになります。この課題をこなせば複雑なソースコードを読むスキルが身に付くことでしょう。

Kuinのリポジトリをダウンロードする

Kuin言語は常に発展しているので、この記事を書いている時点で最新のソースコードをダウンロードすることにいたしましょう。

2018.12.17リリース時のスナップショット
 上記スナップショットのコピー

レポジトリの構成

レポジトリはVisual Studio 2015のソリューションとなっています。プロジェクトはsrcフォルダの中に入っています。コンパイラの実行ファイルを作成するプロジェクトはkuincl、コンパイラの本体はcompilerプロジェクトです。その他のプロジェクトはライブラリを実装するものがメインになっています。

kuinclプロジェクト

kuinclプロジェクトのmain.cを見ると、d0917.kndというファイルをロードしていることが分かります。.kndファイルの実体はWindowsのDLL(ダイナミックリンクライブラリ)です。func_build変数にd0917.kndのBuildFileの関数ポインタを取得して、これを実行しています。d0917.kndはcompilerプロジェクトによって出力されます。

コンパイラの概要

compilerプロジェクトのmain.c内にBuildFile関数があります。これはBuild関数を呼び出しています。

src/compiler/main.c(抜粋)

static Bool Build(FILE*(*func_wfopen)(const Char*, const Char*), int(*func_fclose)(FILE*), U16(*func_fgetwc)(FILE*), size_t(*func_size)(FILE*), const Char* path, const Char* sys_dir, const Char* output, const Char* icon, Bool rls, const Char* env, void(*func_log)(const Char* code, const Char* msg, const Char* src, int row, int col), S64 lang, S64 app_code, Bool not_deploy)
{
    SOption option;
    SDict* asts;
    U8 use_res_flags[USE_RES_FLAGS_LEN] = { 0 };
    SAstFunc* entry;
    SDict* dlls;
    U32 begin_time;

    // Set the system directory.
    if (sys_dir == NULL)
    {
        Char sys_dir2[1024 + 1];
        GetModuleFileName(NULL, sys_dir2, 1024 + 1);
        sys_dir = GetDir(sys_dir2, False, L"sys/");
    }
    else
        sys_dir = GetDir(sys_dir, True, NULL);

    SetLogFunc(func_log, (int)lang, sys_dir);
    ResetErrOccurred();

    timeBeginPeriod(1);

    begin_time = timeGetTime();
    MakeOption(&option, path, output, sys_dir, icon, rls, env, not_deploy);
    if (ErrOccurred())
        goto ERR;
    Err(L"IK0000", NULL, (double)(timeGetTime() - begin_time) / 1000.0);
    asts = Parse(func_wfopen, func_fclose, func_fgetwc, func_size, &option, use_res_flags);
    if (asts == NULL || option.Rls && ErrOccurred())
        goto ERR;
    Err(L"IK0001", NULL, (double)(timeGetTime() - begin_time) / 1000.0);
    entry = Analyze(asts, &option, &dlls);
    if (ErrOccurred())
        goto ERR;
    if (!option.Rls)
        MakeKeywordList(asts);
    Err(L"IK0002", NULL, (double)(timeGetTime() - begin_time) / 1000.0);
    Assemble(&PackAsm, entry, &option, dlls, app_code, use_res_flags);
    if (ErrOccurred())
        goto ERR;
    Err(L"IK0003", NULL, (double)(timeGetTime() - begin_time) / 1000.0);
    ToMachineCode(&PackAsm, &option);
    if (ErrOccurred())
        goto ERR;
    Err(L"IK0004", NULL, (double)(timeGetTime() - begin_time) / 1000.0);
    if (!option.NotDeploy)
        Deploy(PackAsm.AppCode, &option, dlls);
    if (ErrOccurred())
        goto ERR;
    Err(L"IK0005", NULL, (double)(timeGetTime() - begin_time) / 1000.0);

    timeEndPeriod(1);
    Err(L"IK0006", NULL);
    return True;

ERR:
    timeEndPeriod(1);
    Err(L"IK0007", NULL);
    return False;
}

Build関数では、MakeOption, Parse, Analyze, Assemble, ToMachineCode, Deploy関数が順次呼び出されます。ざっと見た感じですが、このような感じだと思います。

MakeOption: kuincl.exeのオプションをもとに初期化を行う(option.c)
Parse: 字句解析、構文解析を行う(parse.c)
Analyze: 抽象構文木を中間言語に変換する(analyze.c)
Assemble: 中間言語を機械語に変換する(assemble.c)
ToMachineCode: 実行可能ファイルの形式を記述する(machine.c)
Deploy: プログラムを配置する(deploy.c)

次回予告

次回はKuinのパース部分をKuinで模写しながら、その構造について見ていきましょう。

CSセミナー009 KuinでKuin①