Explore cs in depth!

情報系の専門学校生.compiler/assembler/linker/loader/os/any lowlevel implementations

原点に立ち返ってLinuxのopen(2)について勉強する

原点に立ち返ってLinuxのopen(2)について勉強する

お久しぶりです.
最近は自作コンパイラや自作TCP/IPプロトコルスタック
YouTubeでのアウトプット活動 をやってたりしました.

現在インフラ部門での就職活動に取り組んでおり,
将来その分野で専門的に精進したいという思いから,
Linuxに関する知識をもう一度整理しようと考えました.

今回はLinuxの機能でも特に中核を担う"ファイル"と,
ファイルを扱う上でまず必要になる open(2) システムコールについてまとめます.
基本的にはユーザ視点のドキュメントになりますが,
Linuxカーネルにあるシステムコールの実装をちょっと覗き見するまでの記事です.

詳解UNIXプログラミング等,書籍の内容も含みます.

ユーザから見るopen(2)

基本

まずはmanの内容を引っ張り出してきます.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

       int open(const char *pathname, int flags);
       int open(const char *pathname, int flags, mode_t mode);

       int creat(const char *pathname, mode_t mode);

       int openat(int dirfd, const char *pathname, int flags);
       int openat(int dirfd, const char *pathname, int flags, mode_t mode);

引数にはファイルパスである pathname と,
open(2) 時の挙動を制御する flags が存在します.
また,mode は,open(2) によって新しくファイルが作成される場合,そのファイルに設定するパーミッションを設定します.

返り値の int 型はファイルディスクリプタを表しますが,
何らかの原因で失敗した場合は-1を返します.

ファイルディスクリプタは非負の整数であるため unsigned int 型を返したくなりますが,
C言語でエラーを表現する場合,負の数をエラーとする事は非常に多いのでしょうがないですね.
int open(const char *pathname, int flags, unsigned int *fd); として, fd に書き込むという方式もよく取られます.
こうすればエラーとファイルディスクリプタをうまく分けられるので,私がC言語でエラーを返す関数を定義する時はこのようにしがち.

実際にopen(2)に渡されるフラグを見てみましょう.
すべてのフラグについて解説するわけではなく,
私の方で特筆すべきと判断した内容にのみ触れます.

O_APPEND

ファイルを追加モードでオープンします.
イメージしづらいと思うので実際に使ってみます.

以下のようなファイルを用意します.

Drumato
123

次のようなCプログラムをコンパイル&リンクして実行します.

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

int main()
{
    const char *msg = "New Drumato\n";
    int fd = open("sample.txt", O_WRONLY | O_APPEND);
    if (fd == -1)
    {
        fprintf(stderr, "open(2) failed\n");
        return 1;
    }

    ssize_t nbytes = write(fd, msg, strlen(msg));

    if (nbytes == -1)
    {
        fprintf(stderr, "write(2) failed\n");
        return 1;
    }

    return 0;
}

実行結果は以下のようになります.

$ gcc c.c
$ ./a.out
$ cat sample.txt
Drumato
123
New Drumato

上記Cプログラムは以下のCプログラムと同じように振る舞います.

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

int main()
{
    const char *msg = "New Drumato\n";
    int fd = open("sample.txt", O_WRONLY);
    if (fd == -1)
    {
        fprintf(stderr, "open(2) failed\n");
        return 1;
    }

    if (lseek(fd, 0, SEEK_END) == -1)
    {
        fprintf(stderr, "lseek(2) failed\n");
        return 1;
    }

    ssize_t nbytes = write(fd, msg, strlen(msg));

    if (nbytes == -1)
    {
        fprintf(stderr, "write(2) failed\n");
        return 1;
    }

    return 0;
}

つまり,O_APPENDによって開かれたfdは,
ファイルのオフセットをファイル末尾に設定した状態でユーザに渡されます.

O_CLOEXEC

プロセスの親子関係において,
親プロセスが開いているファイルディスクリプタは,子プロセスにもそのまま引き継がれます.

この挙動を許したくない場合,つまり子プロセスにファイルディスクリプタ群をコピーしたくない場合,
open(2) して開いたファイルディスクリプタに対して fcntl(2) を呼び出し,
FD_CLOEXEC フラグを設定するというプログラムを書く必要があります.
これを close-on-exec フラグの設定 といいます.

しかし, open(2) の呼び出し終了から fcntl(2) の呼び出しが行われるまでに,
子プロセス等からfdを触られてしまうかもしれません.
これを回避するためにLinux 2.6.23 以降から, O_CLOEXEC フラグを設定できるようになりました.
fcntl(2) を明示的に呼び出さなくても,fdに対してclose-on-exec フラグを設定してくれます.

実際に試してみましょう.
まずは子プロセスを生成する親プロセスのプログラムを作ります.

#include <dirent.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

static void print_file_descriptors_by_current();

void open_sample_txt_many_times()
{
    for (int i = 0; i < 20; i++)
    {
        int fd;
        if ((fd = open("sample.txt", O_RDONLY)) == -1)
        {
            fprintf(stderr, "open(2) failed\n");
            exit(1);
        }
    }
}
int main(void)
{
    open_sample_txt_many_times();

    print_file_descriptors_by_current();

    pid_t pid;
    if ((pid = fork()) == -1)
    {
        fprintf(stderr, "fork(2) failed\n");
        return 1;
    }
    else if (pid == 0)
    {
        fprintf(stderr, "\nchild process start\n");
        char *child_argv[] = {"./child", NULL};
        execve("./child", child_argv, NULL);
        return 0;
    }
    else
    {
        int status;
        if (waitpid(pid, &status, 0) == -1)
        {
            fprintf(stderr, "waitpid(2) failed\n");
            return 1;
        }
        fprintf(stderr, "child process end\n");

        return 0;
    }
}

static void print_file_descriptors_by_current()
{
    pid_t pid = getpid();
    DIR *dir;
    struct dirent *dp;

    if ((dir = opendir("/proc/self/fd")) == NULL)
    {
        fprintf(stderr, "opendir(3) failed");
        exit(1);
    }

    int i = 0;
    for (dp = readdir(dir); dp != NULL; dp = readdir(dir))
    {
        printf("files[%d] => %s (in pid=%d)\n", i, dp->d_name, pid);
        i++;
    }
}

procfsには /proc/[pid]/fd というディレクトリが存在し,
pid に対応するプロセスが開いているファイルディスクリプタのエントリが存在します.
親プロセスではたくさんのファイルを開いておきましょう.

次に,子プロセスのプログラムを作ります.
このプログラムでも print_file_descriptors_by_current() を呼び出すことで,
子プロセスに親プロセスのファイルディスクリプタが引き継がれているかどうか確認します.

#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

static void print_file_descriptors_by_current();

int main()
{
    print_file_descriptors_by_current();
    return 0;
}

static void print_file_descriptors_by_current()
{
    pid_t pid = getpid();
    DIR *dir;
    struct dirent *dp;

    if ((dir = opendir("/proc/self/fd")) == NULL)
    {
        fprintf(stderr, "opendir(3) failed");
        exit(1);
    }

    int i = 0;
    for (dp = readdir(dir); dp != NULL; dp = readdir(dir))
    {
        printf("files[%d] => %s (in pid=%d)\n", i, dp->d_name, pid);
        i++;
    }
}

実行結果は以下のようになります.

$ gcc -o parent parent.c
$ gcc -o child child.c
$ ./parent
files[0] => . (in pid=10636)
files[1] => .. (in pid=10636)
files[2] => 0 (in pid=10636)
files[3] => 1 (in pid=10636)
# stripped
files[25] => 23 (in pid=10636)

child process start
files[0] => . (in pid=10637)
files[1] => .. (in pid=10637)
files[2] => 0 (in pid=10637)
files[3] => 1 (in pid=10637)
# stripped
files[25] => 23 (in pid=10637)
child process end

それでは,sample.txt のopen時に O_CLOEXEC を渡してみます.
parent.copen(2) 呼び出し部分を変更するだけです.
実行結果は以下のようになります.

$ gcc -o parent parent.c
$ gcc -o child child.c
$ ./parent
files[0] => . (in pid=10796)
files[1] => .. (in pid=10796)
files[2] => 0 (in pid=10796)
files[3] => 1 (in pid=10796)
# stripped
files[25] => 23 (in pid=10796)

child process start
files[0] => . (in pid=10797)
files[1] => .. (in pid=10797)
files[2] => 0 (in pid=10797)
files[3] => 1 (in pid=10797)
files[4] => 2 (in pid=10797)
files[5] => 3 (in pid=10797)
child process end

確かに,各 open(2) によって開かれたfdがコピーされていない事がわかります.

O_CREAT

ファイルを新規作成する場合にこのフラグを設定します.
このフラグを設定せず,存在しないファイルをオープンしようとすると -1 が返ります.
逆に O_CREAT を設定して既に存在するファイルをオープンした場合には問題なくopenできます.
この挙動を変更したい場合, O_EXCL フラグを使用します(後述).

O_CREAT を利用する場合,第三引数である mode を渡す必要が出てきます.
S_IRWXU などのマクロ定数を利用できますが,8進数で 0644 などとした方が使いやすい印象.

O_CREAT 単体で利用するよりは, O_WRONLY 等と組み合わせて使う事が多いですね.

O_DIRECTORY

pathnameディレクトリでなければ失敗する,という条件を追加できるフラグです.
opendir(3) の為に作られたものらしい.

O_EXCL

open(2) の呼び出しによってファイルが新規作成されることを保証するフラグです.
これも実際に使ってみましょう.

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

int main()
{
    const char *msg = "Drumato\n";
    int fd = open("new.txt", O_CREAT | O_EXCL, 0644);
    if (fd == -1)
    {
        fprintf(stderr, "open(2) failed\n");
        exit(1);
    }

    exit(0);
}

まだ存在しないファイル new.txt を上記フラグでopenします.
このプログラムは一回目の実行は成功しますが,二回目の実行で失敗します.

O_PATH

fd に対する操作を制限したい場合に,
具体的には,

の2つの用途に制限するフラグです.

ファイルディスクリプタレベルとは,
open/close/fstat/dup/fcntl など,
ファイルの中身自体にアクセスしたりしなくても使用できるAPIのことです.

O_TMPFILE

一時ファイルを作成する為のフラグです.
このフラグを設定する場合, pathname には "作成する一時ファイルを含むディレクトリ"を指定します.

O_TRUNC

通常ファイル(後述)が既に存在し,書き込み許可状態でopenされているとき,
ファイルの長さを0に切り詰めます.

実際に使ってみましょう.

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

int main()
{
    struct stat st;
    const char *msg = "Drumato\n";
    int fd = open("sample.txt", O_RDWR | O_TRUNC);

    if (fd == -1)
    {
        fprintf(stderr, "open(2) failed\n");
        exit(1);
    }

    if (fstat(fd, &st) == -1)
    {
        fprintf(stderr, "fstat(2) failed\n");
        exit(1);
    }

    char buf[2048];
    if (read(fd, buf, st.st_size) == -1)
    {
        fprintf(stderr, "read(2) failed\n");
        exit(1);
    }

    fprintf(stderr, "read from sample.txt: %s\n", buf);

    exit(0);
}

実行結果は以下のようになります.

$ cat sample.txt 
Hi! I'm Drumato.
$ gcc main.c
$ ./a.out 
read from sample.txt: 
$ cat sample.txt

readが行われる前に,中身が切り詰められているのがわかります.
O_CREAT によるファイルの新規作成をしたいが,既にファイルが存在する場合初期化したい際に用いられます.
int creat(const char *pathname, mode_t mode);open(pathname, O_CREAT|O_WRONLY|O_TRUNC, mode) と等しいため,
creat() を用いる際, O_TRUNC が暗黙的に渡されているということですね.


カーネルから見るopen(2)

ここからはLinuxカーネルの中身に入っていって,
open(2) によってOSのどんな機能が動いているのかを理解していきましょう.
対象となるLinuxカーネルv5.10.9 です.

前提知識

Linuxにおいて各ユーザプロセスはファイルディスクリプタを使ってメモリ上のマッピングにアクセスします.
プロセスディスクリプタを表す task_struct 構造体には struct files_struct *files; というメンバがあり,
これは オープンファイルオブジェクト を管理する構造体です.
オープンファイルオブジェクトはオープンファイルディスクリプタとも,
ファイルハンドルとも呼ばれます.
オープンファイルディスクリプタという呼称はPOSIXで用いられるようです.

dup(2) 等によってファイルディスクリプタが複製されることがありますが,
この場合2つのファイルディスクリプタが同じオープンファイルオブジェクトを指すことになります.

/*
 * Open file table structure
 */
struct files_struct {
  /*
   * read mostly part
   */
    atomic_t count;
    bool resize_in_progress;
    wait_queue_head_t resize_wait;

    struct fdtable __rcu *fdt;
    struct fdtable fdtab;
  /*
   * written part on a separate cache line in SMP
   */
    spinlock_t file_lock ____cacheline_aligned_in_smp;
    unsigned int next_fd;
    unsigned long close_on_exec_init[1];
    unsigned long open_fds_init[1];
    unsigned long full_fds_bits_init[1];
    struct file __rcu * fd_array[NR_OPEN_DEFAULT];
};

このうち,struct fdtable *fdt を用いてオープンファイルオブジェクトにアクセスします.
int fd は単にこのテーブルのインデックスでしかありません.
例えばread(2) では struct fd f = fdget_pos(fd); のようにして intstruct fd に変換していますが,
最終的に rcu_dereference_raw(fdt->fd[fd]); という関数呼び出しの中で struct fdtable.fd にアクセスしています.

struct fdtable {
    unsigned int max_fds;
    struct file __rcu **fd;      /* current fd array */
    unsigned long *close_on_exec;
    unsigned long *open_fds;
    unsigned long *full_fds_bits;
    struct rcu_head rcu;
};

struct file __rcu **fd; がオープンファイルオブジェクトのテーブルです.
つまり struct file がオープンファイルオブジェクトの実体となります.
大きな構造体なので,ここでは定義の紹介はしません.
先程のサンプルで sample.txt を20回openしたように,
同じファイルを複数回オープンする事はあり得るので,
一つのファイル(inode)に対して複数のオープンファイルオブジェクトが存在する可能性があります.

"大まか"なコードリーディング

それでは実際に open(2) の中身に入っていきます.
全ての関数を深堀りするわけではなく,あくまで大まかな理解にとどめます.

簡単なコールツリー

簡単にコールツリーを書き起こしておきました.
私が後々本格的にコードリーディングする場合に使用するつもりで作りましたが,
よかったら参考にしてください.

- `sys_open` ... `open(2)` のカーネル側エントリポイント
  - `force_o_largefile` ... プロセスの実行ドメインを検証し,必要に応じて `O_LARGEFILE` を設定
  - `do_sys_open` ... `struct open_how` の構築
    - `do_sys_openat2` ... `open(2)` の実体
      - `build_open_flags` ... より詳細なフラグの設定,検証
      - `getname` ... ユーザプロセス空間の`filename` を取得する
      - `get_unused_fd_flags` ... カレントプロセスが使用していないfdを探索して返す
      - `do_filp_open` ... `struct file` に必要な情報を突っ込んで返す
        - `path_openat` ... `do_filp_open` の本筋
          - `alloc_empty_file` ... `kmem_cache_zalloc()` で `struct file` を初期化
          - `do_open` ... ここまでの情報をもとにファイルを開く
            - `vfs_open` ... 仮想ファイルシステムに問い合わせ,実際にファイルを開く
      - `fd_install` ... 新しい `struct file` をfdtableに登録する
      - `putname` ... `kmem_cache_free` を呼んで `struct filename` を開放

SYSCALL_DEFINE3

システムコールの実装を追う場合,
まずは SYSCALL_DEFINEN マクロ関数の呼び出しを見ると良いです.
例えばopen(2) であれば,/fs/open.c#1192 にあります.

SYSCALL_DEFINE3(open, const char __user *, filename, int, flags, umode_t, mode)
{
    if (force_o_largefile())
        flags |= O_LARGEFILE;
    return do_sys_open(AT_FDCWD, filename, flags, mode);
}

force_o_largefile() マクロは,プロセスのパーソナリティを調べます.
PER_LINUX32 フラグが立っていなければtrueが返るという処理で,
恐らく32bit Linuxかどうかのチェックだと思います.

O_LARGEFILE フラグについては説明していませんでしたが,
ファイルサイズが32bit幅で表せず,64bit幅を必要とする場合に設定します.
プロセスのパーソナリティによっては,このフラグが自動で設定されるということですね.

do_sys_open()

long do_sys_open(int dfd, const char __user *filename, int flags, umode_t mode)
{
    struct open_how how = build_open_how(flags, mode);
    return do_sys_openat2(dfd, filename, &how);
}

build_open_how() 関数はその名の通り,
open(2) の挙動を制御する構造体 struct open_how を組み立てる関数です.
組み立てたあとは open(2) の実体である do_sys_openat2() に渡して呼び出します.
dfd には AT_FDCWD が渡されています.
これは, open(2)dfdAT_FDCWD を指定した openat(2) と実質的に同じ動作をするからです.

build_open_how()

inline struct open_how build_open_how(int flags, umode_t mode)
{
    struct open_how how = {
        .flags = flags & VALID_OPEN_FLAGS,
        .mode = mode & S_IALLUGO,
    };

    /* O_PATH beats everything else. */
    if (how.flags & O_PATH)
        how.flags &= O_PATH_FLAGS;
    /* Modes should only be set for create-like flags. */
    if (!WILL_CREATE(how.flags))
        how.mode = 0;
    return how;
}

WILL_CREATE() マクロによってファイルが作成されるかどうかのチェックが行われます.
そうでない場合 struct open_how.mode は使用されません.
O_PATH_FLAGS マクロは (O_DIRECTORY | O_NOFOLLOW | O_PATH | O_CLOEXEC) に展開されます.
つまり, O_PATH フラグを渡した時点で,上記以外のフラグは全て無視されます.

do_sys_openat2()

static long do_sys_openat2(int dfd, const char __user *filename,
               struct open_how *how)
{
    struct open_flags op;
    int fd = build_open_flags(how, &op);
    struct filename *tmp;

    if (fd)
        return fd;

    tmp = getname(filename);
    if (IS_ERR(tmp))
        return PTR_ERR(tmp);

    fd = get_unused_fd_flags(how->flags);
    if (fd >= 0) {
        struct file *f = do_filp_open(dfd, tmp, &op);
        if (IS_ERR(f)) {
            put_unused_fd(fd);
            fd = PTR_ERR(f);
        } else {
            fsnotify_open(f);
            fd_install(fd, f);
        }
    }
    putname(tmp);
    return fd;
}

build_open_flags によって,詳細なフラグの検証と設定が行われます.
その後 get_unused_fd_flags で未使用のファイルディスクリプタを探索,取得します.
実際にファイルを開くのは do_filp_open という手続きです.


まとめ

この記事では, open(2) システムコールについての知識を整理しました.
カーネルのコードはすべてを紹介していませんが,
大まかに把握することで詳細なコードリーディングをする時の助けになると思います.

この調子でLinuxの勉強もがんばります.

参考

TaPLの5,6章を読み,7章をHaskellで

TaPLの5,6章を読み,7章をHaskell

今回もTaPLの内容を実装ベースで理解します.
前回の記事はこちら.

drumato.hatenablog.com

今回は5, 6章で解説されている"単純型なしラムダ計算"を理解し,
7章のOCaml実装をHaskellに移植してみようと思います.
この記事はあくまでも 言語処理系の"理論"に疎い人間が実装ベースで理解する という趣旨なので,
その点注意してご覧いただければと思います.

コード全体はこちらに.

github.com

  • TaPLの5,6章を読み,7章をHaskell
    • 前提知識
      • ラムダ計算の基礎
      • 意味論
      • 項の名無し表現
    • Haskellによる実装
    • まとめ
続きを読む

TaPLの3章を読み,4章をHaskellで

TaPLの3章を読み,4章をHaskell

あけましておめでとうございます.
2021年も,細々とした技術活動を頑張ってやっていきます.

さて,今年のお正月にTaPLを購入しました.

twitter.com

難しい内容の本ですが,少しずつ読み進めています.
今回は3章で解説されている"型なし算術式"を理解し,
4章のOCaml実装をHaskellに移植してみようと思います.
この記事はあくまでも 言語処理系の"理論"に疎い人間が実装ベースで理解する という趣旨なので,
その点注意してご覧いただければと思います.

コード全体はこちらに.

github.com

前提知識

まずは3章で解説されている内容を軽く紹介.
詳細は本書を参照してください.

対象言語の構文

まず,以下のようなシンプルな構文を持つ言語を仮定します.
この言語で記述されたプログラムはただ一つの項であり,
入れ子関係を持つこともあります.

t ::= 
    true
    false
    if t1 then t2 else t3
    0
    succ t1
    pred t1
    iszero t1

ここでメタ変数 t1, t2, t3 は実際には項そのものであり,
項である任意の表現が埋め込まれます.

項の評価結果は必ずブール値か数値となります.
この評価結果を として区別します.
例えば succ (succ (succ 0)) -> 3 です.
(ただし,3 という構文要素は存在せず,"0にsucc関数を3回適用した形"のまま残しておきます)
他にも, if true then 0 else 0 のような項も正当です.

あくまで構文の定義に過ぎないため,
この段階では if (succ 0) then (iszero 0) else 0 のような項も許容されるという点に注意です.

本書では,帰納法を用いた項の定義も紹介されています.
帰納的に定義することで,項の深さに関する性質や定数の集合等について論理的に述べることができますが,
ここでは厳密な解説や定義は追わないことにします.

意味論

本書では,言語の意味論 を正確に定義するアプローチ法が紹介されています.

  • 操作的意味論( Operational Semantics )
    • プログラムの意味を,抽象機械の動作として記述する
      • 実際の機械と異なり, 項を認識する という点で抽象的
  • 表示的意味論( Denotational Semantics )
  • 公理的意味論( Axiomatic Semantics )

実際に,本書で取り上げられている ブール式だけの操作的意味論 について考えてみましょう.

t ::=
    true
    false
    if t1 then t2 else t3

v ::=
    true
    false

ここで t は項, v は値を表します.
次に,項の評価関係について見ていきます.

E-IFTRUE: if true then t2 else t3 -> t2
E-IFFALSE: if false then t2 else t3 -> t3
E-IF: t1 -> t'1 | if t1 then t2 else t3 -> if t'1 then t2 else t3

一つ目/二つ目の評価関係は,
"条件部が定数ブール値であるような(if-then-elseの)項"を見つけたとき,
単一ステップでt2/t3に評価してしまって良いということを示しています.

三つ目は,パイプ記号の左(前提)から読むとわかりやすいです.
t1t'1に"単一ステップで"評価可能な時if t'1 then t2 else t3 に評価してしまって良いという意味になります.

例えば,次のような項を単一ステップ評価器に入力します.
ここで括弧は項の階層構造を明確にするために用いているだけで,構文要素としてではありません.

if (if true then true else false) then true else false

t1: if true then true else falseE-IFTRUE により単一ステップで true に評価可能なので,
if true then true else false という項に評価可能です.

本書では, t2 に if-then-else項が来たときを例にとって,
評価戦略(評価規則の適用順) について説明してします.
ここで, 推論規則のインスタンス という考え方が生きてきます.
推論規則のインスタンスとは, 規則中に現れるメタ変数を具体的な項で置き換えたものです.
例えば,

if true then true else (if false then false else false) -> true

E-IFTRUEインスタンスです.
t1 => true; t2 => true, t3 => (if false then false else false) という対応付けがされています.

このような単一ステップの評価は,
評価の最終結 を定めることで停止させることができます.
実際には単一ステップの評価規則を繰り返し適用させることで最終結果を得るために,
"抽象機械がこれ以上評価規則を適用できない状態"を定める必要があるのです.
このような項を 正規形( normal form ) といいます.

ブール式のみを取り扱う場合,正規形は truefalse になります.
これは truefalse が左側に来るような評価規則が存在しない,
つまりこれらの項を別の表現に置き換える事ができないからです.

項が正規形ではあるが値ではないとき,その項は 行き詰まり状態( stuck state ) であるといいます.
例えば succ false という項に対する評価規則が存在しないので正規形ではありますが,
値ではないことがわかります.


Haskellによる実装

さて,ここからが本題です.
本書ではOCamlによる実装のサンプルが記載されていますが,
ここではHaskellに移植してみます.

ただそのまま移植しても勉強にならないので,
いくつか追加で関数を実装してみました.
少しずつ見ていきましょう.
先程も載せましたが,実装全体はこちらに.

github.com

-- | 項
data Term
  = TermTrue -- "true"
  | TermFalse -- "false"
  | TermZero -- "zero"
  | TermSucc Term -- "succ" t
  | TermPred Term -- "pred" t
  | TermIsZero Term -- "iszero" t
  | TermIf Term Term Term -- "if" t1 "then" t2 "else" t3
  deriving (Show, Eq)

項の定義です.
本書では info という,ソースコード上の位置を表す型を持たせていましたが省略しました.

-- | 項が数値であるかどうかの判定
isNumericValue :: Term -> Bool
isNumericValue t = case t of
  TermZero -> True
  TermSucc t1 -> isNumericValue t1
  _ -> False

-- | 項が値であるかどうかの判定
isValue :: Term -> Bool
isValue t = case t of
  TermTrue -> True
  TermFalse -> True
  x -> isNumericValue x

これも本書の実装とほぼ同じです.
TermSucc (TermSucc (TermSucc TermZero)) のような項,
(つまり succ (succ (succ 0'))) が値であると判断できているかどうかが大事.

評価規則を適用する部分を見てみましょう.

eval1 :: Term -> Either EvalError Term
eval1 t = case t of
    -- stripped 評価規則が並ぶ

評価器の中身を説明するまえに,この関数の型シグネチャを解説.
本書では例外を投げていましたが, Either モナドにくるんで返すことでより明確にしました.
なお本書にも term option 型を返すことでうまくいくという紹介はされています.

気を取り直して eval1 関数の中身を.
適宜コメント入れてます.

eval1 :: Term -> Either EvalError Term
eval1 t = case t of
  -- E-IFTRUE
  TermIf TermTrue t2 t3 -> Right t2
  -- E-IFFALSE
  TermIf TermFalse t2 t3 -> Right t3
  -- E-IF
  TermIf t1 t2 t3 -> case eval1 t1 of
    Right t1' -> Right $ TermIf t1' t2 t3
    e -> e
  -- E-SUCCZERO
  TermSucc t1 -> case eval1 t1 of
    Right t1' -> Right $ TermSucc t1'
    e -> e
  -- E-PREDZERO
  TermPred TermZero -> Right TermZero
  -- E-PREDSUCC
  TermPred (TermSucc t1) | isNumericValue t1 -> Right t1
  -- E-PRED
  TermPred t1 -> case eval1 t1 of
    Right t1' -> Right $ TermPred t1'
    e -> e
  -- E-ISZEROZERO
  TermIsZero TermZero -> Right TermTrue
  -- E-ISZEROSUCC
  TermIsZero (TermSucc t1) | isNumericValue t1 -> Right TermFalse
  -- E-ISZERO
  TermIsZero t1 -> case eval1 t1 of
    Right t1' -> Right $ TermIsZero t1
    e -> e
  -- すでに正規形
  _ -> Left NoRuleApplies

パターンマッチを用いて,評価規則を順々に見ていくだけなので特に読むのに苦労しないと思います.
これも本書の実装とほぼ同じですね.

単一ステップ評価器が出来上がったので,eval1 のラッパーを作ってしまえば実装は終わりです.
しかし,本書のまま実装しては 項の行き詰まり状態 を検知することができません.
よって,少し独自の実装を取り入れました.

-- 本書の実装の場合
eval :: Term -> Term
eval t = case eval1 t of
    Right t' -> eval t'
    Left _ -> t

-- 私の実装
eval :: Term -> Either EvalError Term
eval t = case eval1 t of
  Right t' -> eval t'
  Left e -> if isValue t then Right t else Left NormalizedButIsNotValue

eval1 関数が返すエラーは NoRuleApplies のみなので,
eval1 に適用して Left e を返すような項 t はすべて正規形であることがわかります.
後は最初に定義した isValue でチェックを挟めばOKです.
ユニットテスト を見れば,
succ false のような項に対して NormalizedButIsNotValue を返す事ができていることがわかると思います.

ここまでで実装は終わりなのですが,
せっかくなので succ nv を数値に変換してしまいましょう.

data Value = ValueTrue | ValueFalse | ValueInteger Int deriving (Eq, Show)

runEvaluator :: Term -> Either EvalError Value
runEvaluator t = case eval t of
  Right t' -> Right $ toValue t
  Left e -> Left e

toValue :: Term -> Value
toValue TermTrue = ValueTrue
toValue TermFalse = ValueFalse
toValue TermZero = ValueInteger 0
toValue (TermSucc t1) = case toValue t1 of
  ValueInteger n -> ValueInteger (n + 1)
  _ -> error "unreachable"

eval tRight t' にマッチする時点で
正規形であり値である ことがチェックできているので, error を使ってしまっています.
ここらへんも真面目にハンドリングしたい方はもうちょい書き込む必要がありそうです.


まとめ

今回はTaPL3章を軽く読み流し,4章のOCaml実装をHaskellに移植するミニ記事でした.
本当はパーサとか作ってinterpretしたかったんですけど,本筋からは外れてしまうので省略しました.
挑戦したい方はぜひやってみてください.

数学にも疎く,言語処理系の"理論"の勉強も疎かにしていた私にとってTaPLの内容はとても難しいですが,
実装ベースで理解することは比較的簡単(だと思う)ので,
苦手意識のある方は私と同じような勉強法を推奨します.

TaPLは読破して感想記事を上げる予定ですが,
それまでに細々と記事を上げるつもりなので,お楽しみに.

Drumatoの2020年をまとめて2021年を生み出すポエム

2020年をまとめて2021年を生み出す

タイトルのとおりです.
2020年を振り返って,2021年に価値のある活動をするためのモチベーションを考えます.


振り返り

振り返りですが,実はもうしてあります.

スレッドにまとめてあるので,お時間ある方は読んでいただけると.
この記事では来年について色々語りたいと思っています.


2021年

ラボユース活動

現在参加しているラボユース活動は,これからも努力したいと思います.

を念頭に置いて頑張って作っています.

また,今はコンパイラプロジェクト全体を再設計しつつ,以下の問題を解決するために頑張っています.

  • 最適化手法もちゃんと勉強して実装したい
    • とはいえ複数アーキテクチャに対するコンパイルと両立するのは"めちゃくちゃ"難しい
    • まずはやりたいことを切り分けて,半分ずつやっていきたい
    • 具体的には,x64のパスのみ最適化を頑張る感じ?

コンパイラ実装をずっと頑張ってきた私ですが,
振り返ってみると初歩的で入門的なことばかりやってきたのではないか,と常々思っています.
少しでも先進的なものを実装したいですが,これまでなかなかうまくできませんでした.
このジレンマを取っ払いたいという思いでラボユース活動に参加しています.

特にモダンなコンパイラに採用されている最適化手法は,必ず実装してみたいと思っているのですが,
コンパイラ分野でやりたいことがありすぎる為に,一つに絞れていないという大きな問題を抱えています.
まずは 複数アーキテクチャに対するコンパイル をちゃんと作り上げてから,別のやりたいことに手を付けようと思います.

peachcc

下のツイートのとおりです.

seccamp2019で出来なかったセルフホストを今こそ,という感じですね.
これは2021年というか,1月中にやりたいぐらいの気持ちです.

2022年新卒就活

現在4年制学科の3年生である私ですが,
真剣に"エンジニアリングで就職する"ということについて考え始めています.

コンパイラ(やその時の私がやりたくなった技術)の勉強を頑張ってきた私ですが,
この時期になって"私はどんなエンジニアになれるんだろう"という疑問が浮かびあがってきました.

  • コンパイラ開発を仕事にできる(ほどの知識と力がある)のだろうか
  • それ以外の分野で業務に貢献できるほどエンジニアリングできるのだろうか
    • 私は技術分野のほぼ全てに興味があるので楽しめるし真剣に勉強できる自身はあるが,専門性が低いのではないか

みたいなふうに,現在色々考えながら就活に取り組んでいます.

既に,いくつかの企業さんに応募させて頂いておりますが,
Twitter就活 も真剣に考えています.
(これまでの経歴や成果物をまとめたGistを公開し,Twitterで声掛け)

インターン等にも参加したいなあ.
低レイヤインターン,参加できないだろうか.


まとめ

珍しくネガティブな記事になってしまいましたが,
技術を楽しむ姿勢だけはこれからも変わらないので,
2021年もがんばります.

一緒に学ぼう,Rustで作る単相型システム

一緒に学ぼう,Rustで作る単相型システム

この記事は IPFactory Advent Calendar 202020日目です.
このネタを 言語実装 Advent Calendar 2020 の記事に採用すればよかったかもしれない.
私は1日目にも記事を上げていますので,興味があればそちらも見てください.

drumato.hatenablog.com

言語処理系の勉強をしていればほぼ100%,そうでなくても一度は目にしたことがあるであろう,"型システム" という言葉.
何やらかっこいい名前ですが,どういったものかは理解していても実装方法まで知っている人は多くありません.
かくいう私も,今まで作ってきた言語達はすべて "型の明示を強制する" 言語だったので経験はありませんでした.
また,そもそも型システムについて勉強しようという気になったことがありませんでした.

そんな私が SecHack365 に参加していたとき,
同期の方サクッと実装 していて大変びっくりした記憶があります.
"よくわかんなければ作りましょう,作ったことなきゃ作りましょう" が私の技術に対するモチベーションなので,
記事読んで満足するだけじゃなく,ちゃんと自分でも作ってみないとね,と思っていました(そして数千年の時が経ちました).

本記事はあくまで "型システムを実装するための記事,実際にRustで実装した記事" になるので,
型システムについての詳細な解説等は行いません.
記事末尾に参考資料を記載しておくので,
そちらをご覧いただければと思います.
当方型システムについての勉強はこれが初めてなので,間違っている点もあるかもしれません.
その際は是非コメント等で教えていただけると助かります.

ソースコード全体がGitHubで見れるようになっているので,そちらも是非.

github.com

対象読者

  • 一番シンプルな型推論アルゴリズムを知りたい!という人
  • Rustで型システムをどうやって作るのか知りたい人

対象でない読者

読んでほしくない,というわけではなく,
このレベルに該当する人にとっては退屈かもよ,という意味です.

目次

型システムについての前提知識

ここでは最低限,型システム関連の情報を整理しておきます.
後に,それら概念や知識を使って実装の解説をしていきます.
また,本記事の後,型システムに関する論文や他記事を読む為の助けにもなるでしょう(なるといいな).
興味のない人は飛ばしてください.
基本的には,以下のページ等に書いてある知識の要約であり,n番煎じです.
間違っていたらコメントお願いします.

www.fos.kuis.kyoto-u.ac.jp

型システムの用語

まず, "型環境( type environment ) Γ 下においてプログラム中の式 e が型 T を持つ" という表現を 型判断 (type judgement ) といいます.
これは,以下のように書きます.

\Gamma \vdash e \colon T

type judgement は, 型付け規則( typing rule ) というものを使って導出されます.
イメージとしては, "こんなコンテキストで前提xxが全て導出できれば,結論xx" みたいな感じです.
下に示した型付け規則は,
"型環境 Γ 下において xσ 型を持つと言えるとき,そのようにして扱える" みたいな意味になります.

\frac{x \colon \sigma \in \Gamma}{\Gamma \vdash x \colon \sigma}

導出中において"未知の変数"を表すために 型変数 (type variable) という概念が用いられます.
これにより,関数適用 ((fn x -> x) 3) のような式についても推論が可能になります.
a0 -> a0 な関数に対し int を適用すると,最終的に int -> int が導出されます.
このとき, "型変数とその正体の対応関係" を 型代入( type substitution ) と呼びます.

単一化

ここで,fn x -> x + 3 という関数という推論について考えます .
二項演算のオペランドである x, 3 の推論結果はそれぞれ a0, int となります.
a0int は単純比較すると異なるように見えますが,
a0 = int であればこの関数はvalidであることがわかります.
これを解決するために, 単一化( unification ) という操作を行います.
S(a0) = int となるような型代入を得ることができれば,上式は推論可能であることがわかります.

単相と多相

ここまでの仕組みを実装して得られる型推論器を "単相的である" と表現します.
let f = fn x -> x + 3 in f 4 のようなプログラムでは,
f :: 'a -> 'a というシグネチャ'a = int という型代入を持ってして,
"let式 let f = fn x -> x + 3 in f 4 は型 int を持つ" という型判断が得られました.

しかし,こちら で取り上げられているように,
let f = fn x -> x in if f true then f 2 else 3 のような式が推論できません.
しかし,Haskellなどの関数型言語ではこのような使い方も可能です.
Haskellを含むいくつかの言語は多相を実現するための言語機能を持っています. (コードの意味は特にありません)

main = do
    let r = let f = (\x -> x) in if f True then f 3 else f 5
    print r

これを実現するために導入されるのが let多相( let-polymorphism ) という概念です.
Haskellでは多相的なプログラムを構築することが可能です.
同様に 型変数( variable ) という概念が存在しますが,
それらは 全称量化 されていると考えることができます.
推論途中の"未知変数"を表す型変数とは区別して, 型スキーム( type scheme ) と呼ばれます.


型推論システムの実装

型推論を実現するいくつかのアルゴリズムを紹介します.
他にもあったら教えて下さい.

今回はこのうち,MinCamlコンパイラ型推論システム(っぽいもの)を実装してみます.
(いずれ全部やりたいなあ)

MinCamlコンパイラ型推論を一部実装

MinCamlは多くの言語機能を有していますが,
ここでは言語機能をある程度制限します.
また,コードすべてを載せるととんでもないことになってしまうので一部のみ取り上げます.
全体はこちらに.
cargo test を動かしていただければ雰囲気はつかめると思います.

github.com

//! src/expr.rs

pub enum Expr {
    /// `x`
    Variable(String),
    /// `42`
    Integer(i64),
    /// `true` | `false`
    Boolean(bool),
    /// `x + 3`
    Plus(Box<Expr>, Box<Expr>),
    /// `\x -> x + 3`
    Lambda(String, Box<Expr>),
    /// `f 3`
    Application(Box<Expr>, Box<Expr>),
    /// `let x = 3 in x + 3`
    Let(String, Box<Expr>, Box<Expr>),
}

今回の型推論器で扱う式を表します.
Rustではこのような再帰的データ構造を表現する場合,
Box<T> を使用するのが最もシンプルなので,今回はそうしています.
他には, typed-arena のようなアロケータクレートを用いるという方法もあります.
私はこのtyped-arenaを好んでよく使っています.

//! src/types.rs
pub enum Type {
    Boolean,
    Integer,
    Fn(Box<Type>, Box<Type>),
    Variable(String),
}

推論結果として使用する型です.
Type::Variable は型変数であり,その名前を持ちます.

実際の推論アルゴリズムを見てみましょう.

fn infer(
    mut env: Env,
    mut iter: RangeInclusive<char>,
    e: Expr,
) -> Result<(Env, RangeInclusive<char>, Type), InferenceError> {
    match e {
        Expr::Boolean(_b) => { /* stripped */ },
        Expr::Integer(_v) => { /* stripped */ },
        Expr::Variable(name) => { /* stripped */ },
        Expr::Let(x, e1, e2) => { /* stripped */ },
        Expr::Lambda(var, expr) => { /* stripped */ }
        Expr::Application(f, param) => { /* stripped */ }
        Expr::Plus(lhs, rhs) => { /* stripped */ }
    }
}

第一引数の env: Env は,型変数から実際の型や,
Expr::Lambdaに登場する束縛変数から型を導出するために使用します.
MinCamlでは Type.t.VarType.t option を持っており,
導出結果を型自体に保存する手法を取っていますが,
今回はハッシュマップを持って取り回す方がシンプルに実装できそうだったので,そうしています.
しかし,env"関数の引数に関する型環境"型変数の代入 という2つの意味を持って使用されてしまうので,少し読みづらいかもしれません.
区別して読みやすくするために,単純なハッシュマップではなく,それをラップする構造体を定義しています(src/types.rsstruct Env を参照).

第2引数の RangeInclusive<char>'a'..='z' というrange objectを生成して渡しています.
これは型変数名のジェネレータです.
他の実装では,呼び出すたびに+1される作用を持った関数を実装して,
a0, a1, a2, ..., an という名前を生成する物を見つけました.
Rustではイテレータを使う方が良さそうだったので,そうしています.
count: RefCell<usize> 等の参照を infer() に渡せば同様の事が出来そうです.

第3引数は推論の対象となるノードです.
パターンマッチを行って,式の種類ごとに分岐しています.
トップダウン的に推論を行うアルゴリズムですが,
解説はボトムアップに行おうと思います.
実際のコードについては, src/inference.rs に定義されたテストも合わせてご覧いただければと思います.

リテラルに対する推論

これは説明するまでもないですね.

match e {
    Expr::Boolean(_b) => Ok((env, iter, Type::Boolean)),
    Expr::Integer(_v) => Ok((env, iter, Type::Integer)),
}

対応する型をそのまま返しています.

変数に対する推論

match e {
    Expr::Variable(name) => match env.vars_in_fn.get(&name) {
        Some(var_ty) => Ok((env.clone(), iter, var_ty.clone())),
        None => Err(InferenceError::NotFoundSuchAVariable { v: name.to_string() }),
    },
}

後に示す Expr::Lambda(var, expr) に対する推論時に,
env.vars_in_fn.insert(var, new_type_var) が行われ,更新された env が渡されます.
λx.x のようなラムダ式の場合, x => a のような"変数と型変数の対応"がマップに存在するので,
その対応が存在すれば取り出し,そうでなければエラーを返しています.

MinCamlでは外部変数もうまく扱えるようになっていますが(自由変数のキャプチャも推論出来る),
今回は実装をシンプルにするためにその機能は無視しています.

let式に対する推論

match e {
    Expr::Let(x, e1, e2) => {
        let (mut env, iter, e1_t) = infer(env, iter, *e1)?;
        env.vars_in_fn.insert(x, e1_t);
        infer(env, iter, *e2)
    }
}

変数に代入する式 e1 を推論して,変数の型が得られます.
それを env に登録した状態で,変数の使用部分である e2 を推論するだけです.

実はこれだけでネストした let の推論等も動いてしまいます.
ここまで説明した内容を元に,let x = 3 in let y = x in y という式を理解してみましょう.
階層構造的には, Let("x", 3, Let("y", "x", "y")) となっている点に注目すると良いです.

  1. 3 が推論され, envx => int が登録される
  2. let y = x in y の推論開始
    1. x が推論される. env をlookupして, int が返される
    2. envy => int が登録される
    3. y が推論され,int が返される.これがinner-let-exprの型となる
  3. inner-let-exprの型がouter-let-exprの型となる

言語処理系の実装をする人にとって再帰関数は馴染み深いものですが,
何度作っても魔法のように見えますね.

λ抽象に対する推論

match e {
    Expr::Lambda(var, expr) => {
        let new_type_var = iter.next().unwrap().to_string();
        let new_type_var = Type::Variable(new_type_var);
        env.vars_in_fn.insert(var.to_string(), new_type_var.clone());

        let (env, iter, expr_ty) = infer(env, iter, *expr)?;
        Ok((
            env,
            iter,
            Type::Fn(Box::new(new_type_var), Box::new(expr_ty)),
        ))
    }
}

id 関数を例に考えましょう.
λx.x に対する推論は,次のようになります.

  1. 新しく型変数 a を作る
  2. envx => a を登録する(これにより,expr に登場する束縛変数の型を推論できる)
  3. x に対する推論を行う.2番の操作により,a 型が得られる
  4. a => a な型を返す

この関数型に登場する型変数aは,実際に適用されるまでわかりません.
また,この関数 a はあくまでも "未知である単一の型" である点に注意です.

関数適用に対する推論

match e {
    Expr::Application(f, param) => {
        let new_type_var_name = iter.next().unwrap().to_string();
        let new_type_var = Type::Variable(new_type_var_name.clone());

        let (env, iter, fn_ty) = infer(env, iter, *f)?;
        let (env, iter, param_ty) = infer(env, iter, *param)?;
        let env = unify(
            env,
            fn_ty,
            Type::Fn(Box::new(param_ty.clone()), Box::new(new_type_var)),
        )?;
        
        if let Some(resolved_ty) = env.type_vars..get(&new_type_var_name) {
            return Ok((env.clone(), iter, resolved_ty.clone()));
        }

        Ok((env, iter, param_ty))
    }
}

少し長いので複雑に見えますが,一つ一つじっくり追っていきましょう.
やはり実例がわかりやすいと思うので,((λx.x) 3) について考えます.
ASTを書き下すと, Apply(Lambda("x", "x"), 3) という感じです.

まず,新たな型変数 a を作ります.
そして,λx.x に対して infer() を呼び出します.
先程の解説から,この推論が b => b のような関数型を返すことがわかっています.
そして,引数の3に対する推論で int が得られます.

最後に,2つの型 ((b => b), (int => a)) に対して unify() を呼び出します.
このような呼び出しになっている理由は,
f の推論結果である b => bbint で置換したとき,
((int => int), (int => a)) となるかどうかをチェックしたい為です.
すぐ後に説明しますが,unify() 内部では未知の型変数に対する代入(substitution)が行われる為,
a => int もすぐに判明します.

int => a な関数に対する適用とわかったところで,
a の型が既に判明しているかどうかenvに問い合わせます.

unify 関数について定義を示します.
少しキレイな書き方ではなくなってしまったので,概要だけ説明します.
詳細に知りたい方はGitHubを御覧ください.

fn unify(
    mut env: Env,
    t1: Type,
    t2: Type,
) -> Result<Env, InferenceError> {
    match (t1.clone(), t2.clone()) {
        // シンプルな比較
        (Type::Integer, Type::Integer) | (Type::Boolean, Type::Boolean) => Ok(env),
        (Type::Fn(var_ty1, ret_ty1), Type::Fn(var_ty2, ret_ty2)) => {
            // 引数同士,返り値同士で型の比較
            let env = unify(env, *var_ty1, *var_ty2)?;
            unify(env, *ret_ty1, *ret_ty2)
        }
        (Type::Variable(name1), Type::Variable(name2)) if name1 == name2 => Ok(env),

        // 一方が型変数の場合を調べる
        (Type::Variable(var), _) => {
            // 定義済み(割り当て済み)の場合,単純比較
            if let Some(var_t) = env.type_vars.get(&var) {
                return unify(env.clone(), var_t.clone(), t2);
            }

            // 未定義(未知)の場合,occur check後代入
            if occur(&var, &t2) {
                return Err(InferenceError::FoundOccurrence);
            }

            env.type_vars.insert(var.to_string(), t2);
            Ok(env)
        }
        (_, Type::Variable(var)) => { /* 上記と同様にチェック */ }
        _ => Err(InferenceError::CannotUnify),
    }
}
  • 渡された2つの型が等しいかチェック
  • どちらか一方が型変数の場合,occur checkを行った後代入
    • occur checkとは, t1: int => a, t2: a な場合等で a => (int => a)としてしまうと無限ループに陥ってしまうので,そういったケースの検出をする手続き

をする関数だということだけ理解していただければ問題ありません.
ちょっとぐちゃっとなってしまったので,まとめましょう

  • ((λx.x) 3) に対する推論はじめ
    • この関数適用の結果 a が得られるとして型変数を持っておく
    • λx.x の型が b => b だとわかる
    • 3 の型が int だとわかる
    • ここまでで, int => a という関数に対する適用だとわかる
  • unify((b => b), (int => a)) を呼び出す
    • unify(b, int) が呼ばれ, b => intenvに登録される
    • unify(b, a) が呼ばれ,b => int がわかっているので, unify(int, a) としてもっかい呼ぶ
      • a => int が登録される
  • int => int として導出できたので,返り値型である int を返す

という感じです.
かなり複雑でしたが,実装することで理解が深まりました.

二項演算に対する推論おまけ

match e {
    Expr::Plus(lhs, rhs) => {
        let (env, iter, lhs_ty) = infer(env, iter, *lhs)?;
        let (env, iter, rhs_ty) = infer(env, iter, *rhs)?;
        let env = unify(env, Type::Integer, lhs_ty.clone())?;
        let env = unify(env, Type::Integer, rhs_ty.clone())?;

        if let (Type::Variable(var), _) = (&lhs_ty, &rhs_ty) {
            let resolved_ty = env.type_vars.get(var).unwrap().clone();
            return Ok((env, iter, resolved_ty));
        }
            
        if let (_, Type::Variable(var)) = (&lhs_ty, &rhs_ty) {
            let resolved_ty = env.type_vars.get(var).unwrap().clone();
            return Ok((env, iter, resolved_ty));
        }

        Ok((env, iter, lhs_ty))
    }
}

+ 演算子を,2つの引数を取る中置関数だと考えると,ほぼ同じことをしているとわかります.
しかし + は今回想定する言語では int しか引数を持たないので,
unify の呼び出し回数は少なくて済みます.

MinCamlコンパイラ型推論を一部実装所感

150行程度の実装でしたが比較的複雑で,実装にもある程度時間がかかってしまいました.
OCamlで実装されたコードをRustに変換するとき,
Rustの知識が足りないせいであまりキレイじゃない書き方になってしまい,若干悔しい思いをしています.
Rustでもっと関数型っぽい書き方に慣れていきたいところですね.

型推論アルゴリズムというとあれですが,
自作言語では let x : i64 = x + 3; みたいな代入に対して,
"右辺がちゃんと宣言通りの型を持っているか"みたいな型検査の実装をしたことがあったので,少し親近感はありました.
しかし unify() はやはり複雑でしたし,ちゃんとテストが通ったときは凄いびっくりしました.


WIP: 多相型推論システムの実装

時間が足りずできませんでした(無念…)
後日別記事にまとめてあげようかな,なんて思っていたりします.

まとめ

今回はRustで単相型推論アルゴリズムを実装しつつ,お勉強してみました.
本当は多相型推論も実装しようとしたんですが何分記事のアイデアを思いついたのが期日ギリギリだったので厳しかったです.
なんだかなあなあになってしまった感じがあるので,後日記事書きたいなあ,なんて思っています(できたら).

先程も述べましたが,Rustで関数型っぽく書く力をもっと身につけたいなあ,と感じることができましたね.
ここらへんRustのベストプラクティスも調べながら知っていきたい.
OCamlMap.add のように,エントリ挿入後のマップが返るようなAPIstd::collections::HashMapにもほしいなと思います(おもいませんか?)

とはいえ,効率を考えたら &mut HashMap<K, V> でごにょごにょするほうがいい気もします.
うーん,難しい.

参考資料

Rust製のパーサコンビネータcombineを"覗き見"する(v4.4.0)

Rust製のパーサコンビネータcombineを覗き見する(v4.4.0)

この記事は 言語実装 Advent Calendar 2020 の10日目です.
昨日は @kimiyuki さんの記事でした.
明日は @fukkun さんの記事です.

2019年 に私が上げた記事については こちらのページ を.

Twitter等で rustcのコードリーディングを助ける為の記事 を書くみたいなこと言っていましたが,
後述する理由により実現できませんでした.
楽しみにしてくださっていた方がいたら,申し訳ありません.

お気持ち

実は rustcのコードリーディングを助ける為の記事 みたいなものを想定して,数十日前から少しずつ書き始めていました.
しかし担当日前日になって,こんな素敵な記事を見つけてしまったのです.

qiita.com

見つけた瞬間のわたしがこちら.

やむなく今まで書いていた記事を全削除,前日になって焦って作り始めました.
ということで完全に思いつきネタです,完成度はご容赦ください…
(30k文字以上の記事になる予定だったので,かなり辛い)

  • Rust製のパーサコンビネータcombineを覗き見する(v4.4.0)
    • お気持ち
    • Motivation
    • サンプルから読み始める
      • parser::char::letter
        • letter() で使われている各種トレイトや型
        • letter() 内部
    • まとめ
    • 余談: any について

Motivation

つい先日,このような記事を上げました.

drumato.hatenablog.com

nomという比較的よく使われるパーサコンビネータについて解析し,
パーサコンビネータとRustに詳しくなろう,みたいな目的の記事です.
思ったより多くの方にご覧頂けたようで,大変嬉しく思っております.

この記事の冒頭で言っていた,まさにそれです.
combineも同様に理解することで,更にRustに詳しくなろうと考えています.

パーサコンビネータについての解説等は特にしないですし,
「nomと比較してxxな実装なんですね」という切り口で解説したいと思っているので,
是非nom解説の記事もご覧頂ければと思います.
実際にnom解説を理解したあとこちらの記事に戻ってくると,
あまり理解するのに時間はかからないんじゃないかなと思います.
nom解説の記事は2,3週間練って作ったものなので出来がいいのもあります

2つのプロジェクトの規模感を把握するために,
clocを使って比較してみました.

$ cloc nom/src/
      32 text files.
      32 unique files.
       0 files ignored.

github.com/AlDanial/cloc v 1.82  T=0.04 s (853.9 files/s, 581289.6 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Rust                            32           1480           7348          12957
-------------------------------------------------------------------------------
SUM:                            32           1480           7348          12957
-------------------------------------------------------------------------------

$ cloc combine/src/
      23 text files.
      23 unique files.
       0 files ignored.

github.com/AlDanial/cloc v 1.82  T=0.03 s (778.9 files/s, 551101.4 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Rust                            23           1401           3594          11278
-------------------------------------------------------------------------------
SUM:                            23           1401           3594          11278
-------------------------------------------------------------------------------

こうしてみると,そこまで大きな差はなさそうですね.

今回は v4.4.0 を対象に読み進めていきます.

続きを読む

Rust製のパーサコンビネータnomを解剖する(v6.0.0)

Rust製のパーサコンビネータnomを解剖する(v6.0.0)

この記事は IPFactory Advent Calendar 2020 の1日目です.
IPFactoryという技術サークルについては 余談 を御覧ください.

普段コンパイラ自作をしていて,LLパーサを手書きすることが多い私ですが,
「そういえばパーサライブラリ使ったことないな」と思い,現在 自作コンパイラプロジェクト のパーサを書き換えています.
そこで使っているのが, Geal/nom というパーサコンビネータのライブラリです.

Rustの強力な型システムの上でジェネリックなパーサ関数を実装しているということで,
きっと様々なRustのエッセンスが含まれていると思い,コードリーディングしようと感じました.
また,いずれパーサライブラリも自作したいなと思っているので,
その前段階として既存実装を調べる必要があると思いました.

Rustのパーサライブラリとしてもう一つ有名なものに Marwes/combine がありますが,
これも記事上げようかなーなんて考えています.
IPFカレンダーにあげようかなー,他メンバーの記事で埋まらなかったら上がるのでお楽しみに.

今回はv6.0.0を対象とします.
投稿前日に見返したら6.0.1がリリースされていたけど気にしない

  • Rust製のパーサコンビネータnomを解剖する(v6.0.0)
    • 前提: nomとは
      • サンプル
    • nomを解剖する3ステップ
      • nom::IResult<I, O, E>
      • パーサ関数とトレイト境界
    • nomのモジュール,パーサ紹介
      • nom::bytes::complete::tag
      • nom::character::complete::satisfy
    • まとめ
    • 余談: IPFactoryについて
    • 余談2: nom::branch::alt について
続きを読む