🎆

僕も Zig で Lisp インタプリタを書いてみた

2023/09/23に公開

zig

tech

はじめに

新しい言語を覚えるには Lisp インタプリタを書くのが一番！(要出典)
ということで私の周りでじわじわと流行っている Zig で書いてみました。

https://github.com/tubo28/ziglisp

fn repl() !void {
    const stdin = std.io.getStdIn().reader();
    const stdout = std.io.getStdOut().writer();

    var env = Map.init(alloc);
    while (true) {
        try stdout.print(">>> ", .{});
        const line = readLine(stdin) catch |err| switch (err) {
            error.EndOfStream => break,
            else => return err,
        };
        if (line) |l| {
            if (l.len == 0) continue;
            const result = eval(l, &env);
            try stdout.print("{s}\n", .{tos(result)});
        }
    }
}

まだまだ機能は少ないですが、それでもだいたいのアルゴリズムは書ける（評価できる）と思います。
src/examples 以下にテスト用 Lisp プログラムがあり、下記はその一つのマージソートです。

(defun append (list1 list2)
  (cond
    ((null list1) list2)
    (t (cons (car list1) (append (cdr list1) list2)))))

(defun subseq (lst begin end)
  (cond
    ((or (null lst) (<= end 0)) '())
    ((> begin 0) (subseq (cdr lst) (- begin 1) (- end 1)))
    (t (cons (car lst) (subseq (cdr lst) 0 (- end 1))))))

(defun merge (f s)
  (cond
    ((= (length f) 0) s)
    ((= (length s) 0) f)
    ((< (car f) (car s)) (append (list (car f)) (merge (cdr f) s)))
    ((> (car f) (car s)) (append (list (car s)) (merge f (cdr s))))
    ((= (car f) (car s)) (append (list (car f) (car s)) (merge (cdr f) (cdr s))))))

(defun merge-sort (lst)
  (let ((len (length lst)))
    (cond
      ((= len 1) lst)
      (t
      (merge (merge-sort (subseq lst 0 (/ len 2)))
              (merge-sort (subseq lst (/ len 2) len)))))))

(merge-sort '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9))

; => (1 . (1 . (2 . (3 . (3 . (4 . (5 . (5 . (5 . (6 . (7 . (8 . (9 . (9 . (9 . nil)))))))))))))))

GC はありません。また今度書きます。
マクロもありません。マクロは Lisp のキモなのでまた今度きっと書きます……。

冒頭で「要出典」とは書きましたが、実際に何人かの方が同じことを既にやっているので気になる方はググってみてください。

Zig とは

Zig は静的型付けシステムプログラミング言語で、 C 言語を現代の知見で再開発する試みの一つです。

https://ziglang.org/

やってみた感想

Zig やってみた系の記事には僕よりもずっと視座が高い方が書いたのが既にいくつかあります。
なのでこの記事ではそれらに書かれていない感想とか知見を書いていくことにします。

2023年9月現在に始めるのにおすすめの方法

ziglearn.org を読み、その後公式ドキュメントに一通り目を通すのが理解が進んで良かったです。

https://ziglearn.org/

コンパイラがよくクラッシュする

現在活発に開発中なので稀によくコンパイラがクラッシュします（コンパイルエラーではなくコンパイラのエラー）。
だいたいコードが間違っているのが原因ですが、一切エラーメッセージを出さずに SIGSEGV とかで落ちるので文法に慣れていないうちは原因の究明に困ります。
これが初学者にとってはとてもつらい。
初心者は文法エラーのコードを書きがちなためむしろそういったコードを偶発的に生産しがちです。なおかつ開発途上のコンパイラはエラーハンドリングが甘いものなのでクラッシュは実際よく起こり、初心者を困らせます。
私の場合だと Lisp インタプリタを書くにあたりそれで困ることが3回ありました。

各 OS でデファクトスタンダードなパッケージマネージャで普通にインストールしたバイナリだとそんな感じなのですが、デバッグビルドしたコンパイラだと雰囲気だけは分かるエラーメッセージが出るので、若干は原因究明の助けになります。
また、開発者の中では既知の問題で最新 master では直っていることもあります。

なので、がっつり書きたいなら最新 master を clone してきてビルドするのが現段階ではかえって楽だと思います。
その方法としては brew install zig などで入れたコンパイラを使って、 git clone してきたソースコードを README に書かれているとおりの手順でビルドするのがいいと思います。とはいえ新しめの Clang と LLVM が必要なのでまあまあ面倒です。

コンテナのデータ構造が面白い

標準ライブラリに含まれるコンテナのデータ構造を眺めると、他の言語では珍しい面白そうなのがいくつか目に入ります。
その中でも個人的に特に好きなのが MultiArrayList です。
MultiArrayList の概要は日本語だとこの記事が分かりやすいと思います。

例として、大きめの構造体の配列をループで舐めるような処理を書きたくなったとします。
C++ で普通に書くとこうなると思います。

struct S {
  int a;
  int b[1000];
};

vector<S> vec;
for (const S &s: vec) { /* s.a を使って何かする */ }

この書き方のちょっとした欠点として、構造体のサイズが大きいのでプロセッサのキャッシュに乗りづらく、また a の領域がメモリ上で飛び飛びなので SIMD も使えません。
普通はそれでもたいして困りませんが、カリカリにチューニングしたい場面では致命的となります。

対策としては、構造体を解体しそれぞれのフィールドの配列にするという手段があります。こんな感じです。

vector<int> vecA;
vector<array<int, 1000>> vecB;
for (const int &a: vecA) { /* a を使って何かする */ }

開発体験の良さと可読性は犠牲になります。

要はこれを楽に、可読性を落とさずやる方法を提供する標準ライブラリのコンテナが MultiArrayList です。

Tagged Union が便利

C 言語で関数型畑の直和型みたいなことをやりたくなったら、一例として enum を使ってこんな感じのコードにできると思います。

typedef enum {
  TK_INT,      // 整数トークン
  TK_FLOAT,    // 浮動小数点数トークン
} TokenKind;

typedef struct Token Token;

// トークン型
struct Token {
  TokenKind kind; // トークンの型
  union {
    int i_val;        // kindがTK_NUMの場合、その数値
    float f_val;      // kindがTK_FLOATの場合、その数値
  };
};

Token token = ...;
switch (token.kind) {
  case TK_INT: /* token.i_val を使って何かする */;
  case TK_FLOAT: /* token.f_val を使って何かする */;
}

この例では Token の種類として整数・浮動小数点数の2種類があり、それらを union フィールドによって Token 構造体一つで表現しています。
場合分けしてフィールドを参照するときは switch (token.kind) とします。

この書き方は enum を union とは別に定義しなければならないのが面倒です。
また kind が TK_INT のときにうっかり f_val にアクセスしに行くと、 float 型としてはおかしな値になるでしょう。

Zig でこのような厄介事を解決してくれるのが Tagged Union です。
上の C コードを Zig で書くとこうなります。

const Token = union(enum) {
    int: i32,
    float: f32,
};

const int_tok = Token { .int = 42 };
const float_tok = Token { .float = 42.0 };

const token = ...;
switch (token) {
  Token.int => |i| /* i を使って何かする */,
  Token.float => |f| /* f を使って何かする */,
}

読みやすいですし、フィールドをキャプチャした値 i か f を使っておけば間違って違う方にアクセスすることも起こりづらいですね！
またうっかりアクセスすると panic が呼ばれ異常終了します。

終わりに

Zig は Go, Rust, D などと比較して言語機能をあえて大きくせず、 better C に徹している感じです。
記事内で書いたような C 言語のいろいろな「よく見るテクニック」を言語としてサポートしようとする一方で、それ以上のことはしていません。例えば allocator がユーザランドに露出していてユーザに選ばせるのなんかは、 GC がある Go、所有権での解決を図った Rust と対照的です。
それらが邪魔になるような場面ではちょうどいい言語なのではないでしょうか。
まだまだ開発中ですが、今後よくなっていくのが楽しみですね。