Goose にはヒープも GC もライフタイム注釈もない、コンパイラは AI が書いた

メモリ安全なシステム言語。ヒープアロケータもガベージコレクタもライフタイム注釈もない。このリポジトリのベンチマークでは、Goose は C++ や Rust より速く動き、しかもメモリ使用量は少ない。

チュートリアル · リファレンス · 仕様 · パッケージ · サンプル · ベンチマーク · 標準ライブラリ

Goose の構文は C や Rust のプログラマーには馴染み深いが、ヒープは存在しない。動的な値はすべて、コンパイラが管理するデータスタック上にインラインで置かれる。成長はポインタを進めるだけで、メモリはスコープを抜けた時点で解放される。このメモリモデルを安全に使えるのは、言語の型規則とライフタイム規則があるからだ。

Goose を選ぶ理由

• メモリ安全でありながら、C++ より速く、safe Rust より速い。 16 個のベンチマークで、Goose は idiomatic な C++ の 3.3 倍、手作業で最適化した C++ の 1.16 倍、最良の safe Rust の 1.12 倍の速度を、それぞれ 1.9 倍、1.3 倍、1.2 倍少ないメモリで出す（結果）。この差は Goose のデータレイアウトとメモリモデルから生まれる。

• アロケータも GC も参照カウントもデストラクタもない。 メモリはコンパイラが静的に割り当てるいくつかのデータスタックにすぎない。100 万要素の構造体を解放するのは 1 回のストアで済む。ネストがどれだけ深くても変わらない。

• 成長しても参照は有効なまま。 成長する配列への参照は、配列が生きている限りずっと有効だ。対応するベンチマークで C++ が reserve を使い、safe Rust が u32 インデックスを使う場面でも、型付き参照をそのまま持ち続けられる。

• 注釈ゼロでメモリ安全。 ライフタイム構文も、エイリアシングや排他性の規則も、unsafe もない。コンパイラが各参照の根を推論し、所有者より長生きしうる参照を拒否する。

• ネストしたデータもインラインのまま。 文字列、文字列の配列、可変長フィールドを持つレコード、そのレコードの配列は、どれもポインタを 1 つも含まない連続したブロックになる。C++ で 160 バイトのアロケーションになるレコードが、Goose では 29 バイトでアロケーションなしだ。

• 保持する分しかコストのかからない enum。 可変モードの ADT では、各値は最大のバリアントではなく自分のバリアントのサイズを取る。これを試すベンチマークでは、Rust の enum に比べてメモリが 4 分の 1、速度が 2 倍になる。

• ポインタより細いリンク。 相対参照は、型付きで検査済みのリンクを 1、2、4 バイトのオフセットとして格納する。これで組んだ構造体は位置非依存なので、データ構造がそのままファイル形式になる。保存は書き込み 1 回、読み込みは読み取りと検証パス 1 回で、悪意あるバイト列はそこで弾かれる。

• すべてがその場で構築される。 値はどんなに深い呼び出しを経ても最終的な置き場所に直接構築される。items.push(parse(line)) はパースしたレコードをそのまま配列に書き込み、成長可能な配列を値で返すコストはゼロだ。

• 複数の呼び出しをまたいで戻れる。 return err from load はアンワインダも Result 型も、呼び出しごとの ? もなしに、静的に検査されたうえで何フレーム上の関数からでも戻る。

• 何も共有しないスレッド。 ワーカーは独自のメモリを持つ別プログラムとしてコンパイルされ、フラットな値は memcpy として型付きキューを渡る。データ競合、ロック、アトミック、メモリオーダリングはこの言語に存在しない。

• オーバーヘッドのないジェネリクスと高階関数。 型を書かなければ引数はジェネリックになる。関数値はコンパイル時に実体化されるので、xs.filter() { it > 0 } は見たとおりのループにコンパイルされ、結果はそのまま出力先へ書き込まれる。

• 入力も出力も普通の C。 Goose は 1 つの C ファイルにコンパイルされるため、C コンパイラさえあればどこでも動き、extern fn を通じて C を直接呼び出せる。同梱の TinyCC バックエンドはビルド手順なしで、プロセス内でプログラムをコンパイルして実行する。

チュートリアルでは実例を通して全体を解説し、リファレンスは言語全体をトピック別に扱い、仕様には正確な規則を、ベンチマークには損失も含めた数値を掲載している。

機能

ここでは Goose の特徴を説明する。チュートリアルでは各機能をより詳しく解説し、サンプルでは 31 本の完全なプログラムで示している。

単一のメモリモデル：スタック、そしてスコープ終了は無料

プログラムが持つのはネイティブのコールスタック、静的データ、そして N 個のデータスタックで、N はコンパイラが決める。データスタックとはバンプポインタ付きの大きなアドレス空間の予約領域であり、メモリはこれ以外にない。各スタックでサイズ変更可能な値は最大 1 つだけ生存し、常に先頭にあるため、伸長時に何かを移動させることも容量をチェックすることもない。これらはすべてコンパイル時に証明され、実行時に追跡するのはバンプポインタだけである。

for round in 3 {
    var scratch: u8[>..] = [];                        // grow-only: growth is a pointer bump
    for i in 100000 { scratch.push((i % 256) as! u8); }
    print("round ", round, ": ", scratch.len, " bytes");
}                                                     // the free: one store to the stack top

何も移動しないので、参照は伸長後も有効

struct Item { id: i32, weight: f32 }

var items: Item[>..] = [];
let first .= items.push(Item { 1, 0.5 });             // a reference to element 0
for i: i32 in 2..1000001 { items.push(Item { i, 0.0 }); }
first.weight = 99.5;                                  // still valid, a million pushes later

push は新しい要素への参照を返すため、配列を構築しながら要素同士をリンクできる。vector<T> や Vec<T> は再確保が起こり得るので、この保証は提供できない。参照の安定性はベンチマークのいくつかの改善に寄与している。

安全な参照、注釈は不要

すべての参照とスライスには静的なルートがある。すなわち、その対象の生存期間を定める変数である。参照は、その対象を所有する変数より長く生存してはならず、互換性のない型を通じて対象にアクセスしてもならない。コンパイラがルートを推論し、ルートごとに関数を特殊化するので、注釈は要らない。エイリアシングや排他性の規則もない。生存期間のチェックに失敗すると、エラーは参照のルートとその参照先を名指しする：

fn longest(a: u8[:], b: u8[:]) -> u8[:] { if a.len >= b.len { a } else { b } }

var outer: u8[>..] = [];
var w = outer[..];
{
    var inner: u8[>..] = [];
    format(inner, "inner text");
    w = longest(outer, inner);     // error: storing a reference rooted at inner,
}                                  //        which does not outlive the destination (§9.2)

スライス T[:] を使えば、要素をコピーせずに任意の配列種別から範囲を受け取る関数を書ける。たとえば split は入力へのスライスを返し、u8[:] をキーとする辞書は文字列のコピーではなくビューを格納する。

ネストしたデータはインラインのまま

単一の配列型は存在しない。サイズの扱いだけが異なる型の一族があり、そのどれもが [metadata][elements...] であり、要素ブロックへのポインタではなくインラインで詰め込まれる：

表記	内容
T[k]	固定長。コンパイル時にサイズが決まる
T[]、T[varint]	構築時にサイズが決まり、その後は不変。固定長または可変長の長さ
T[..k]、T[..]	容量をインラインで持ち、その範囲内で伸縮する
T[>..]	grow-only：主力。内部への参照は有効なまま
T[>..<]	grow-shrink：スタック、キュー、ヒープ

文字列は要するに u8 の配列だ。u8[>..] はビルダー、u8[] は完成した文字列を保持側にインラインで格納するもの、u8[..16] は構造体の中に収まる小さな文字列、u8[:] はビュー。構造体は可変長の部分を含むことができ、それらは宣言順にインラインで並ぶ。つまりレコードは間接参照を一切含まないバイト列になる：

struct Item  { sku: u8[varint], qty: varint, cents: varint }
struct Order { id: varint, customer: u8[varint], items: Item[varint] }

var book: Order[>..] = [];
book.push(Order { id: 1001, customer: "alice",
                  items: [Item { sku: "SKU-441", qty: 2, cents: 1999 },
                          Item { sku: "SKU-7", qty: 1, cents: 500 }] });

この並びは29 バイト、アロケーション 0 回。C++ の std::string + std::vector<Item> なら 160 バイトで 1 回、Rust の String + Vec<Item> なら 153 バイトで 4 回になる。注文板全体が 1 つの配列になり、キャッシュを流れるように走査できる。代償は、可変長要素の配列がシーケンシャルになることだ。反復はできるがインデックスアクセスはできない（その配列への参照を並べた 2 つ目の配列をインデックスとして持てば別だが）。

2 つのサイズで持つ enum

代数的データ型が唯一の動的ポリモーフィズムだ。継承も vtable もない。どの ADT も 2 通りの方法で格納でき、使う場所で選ぶ。固定モード（Shape）はタグと最大ペイロード分の領域を持ち、インデックスアクセスも上書きもできる。可変モード（Shape..）は各値にそのバリアントちょうどのサイズを与える。配列はシーケンシャルになり、値がバリアントを変えることはない。その代わり、ペイロードへの参照を取れる：

enum Shape { Circle { r: f64 }, Rect { w: f64, h: f64 }, Dot }

var packed: Shape..[>..] = [];                 // 9, 17 and 1 bytes, not 17 each
packed.push(Shape.Circle { r: 1.0 });
packed.push(Shape.Rect { w: 2.0, h: 3.0 });
packed.push(Shape.Dot);
for s in packed {
    match s { Rect &r => { r.w += 1.0; }, _ => {} }   // edits the payload in place, inside the array
}

ケース関数を使えば、バリアントごとのディスパッチもできる。バリアントごとにオーバーロードを 1 つ定義する。呼び出しはタグに基づいてジャンプテーブルでディスパッチされ、オーバーロードがすべてのバリアントを網羅しているかはコンパイラが検査する：

fn area(s: Shape.Circle) -> f64 { 3.14159 * s.r * s.r }
fn area(s: Shape.Rect) -> f64   { s.w * s.h }
fn area(s: Shape.Dot) -> f64    { 0.0 }

for s in packed { print(s, " area ", area(s)); }

ポインタより細いリンク

T& はマシンアドレスで、8 バイト、ダングルしない。相対参照は同じリンクを細いオフセットとして格納する。T&<u32> はフィールド自身から同じ配列内のターゲットまでの距離で測るので、構造体は位置非依存になる。T&<u32 in pool> は名前付きプールの基底からの距離で測るので、他の配列からプールへリンクできる。T&<u32>? はオフセット 0 を null として使う。以下は grow-only 配列 1 つに収めた二分探索木で、ノードは 12 バイト：

struct Node { key: i32, left: Node&<u32>?, right: Node&<u32>? }   // 12 bytes, links included

fn insert(pool: Node[>..]&, key: i32) {
    if pool.len == 0 { pool.push(Node { key: key }); return; }
    var cur .= pool[0];                             // .= binds a reference; = would copy the node
    loop {
        if key == cur.key { return; }
        let next = if key < cur.key { cur.left } else { cur.right };
        if next { cur .= next; continue; }          // narrowed by `if`: next is a Node&
        if key < cur.key { cur.left .= pool.push(Node { key: key }); }
        else             { cur.right .= pool.push(Node { key: key }); }
        return;
    }
}

参照は透過的で（* も -> もない）、.= が参照を束縛または付け替え、Node? は nullable 参照であり if、guard、assert が絞り込む。挿入は push 1 回と store 1 回で、push が cur を無効化することはない。ライフタイムが入れ子にならない場合、reusable プールは grow-only 配列と隠れた freelist を組み合わせる。alloc_ref はスロットを再利用するか push し、free はスロットを 1 つ返す。実際には何も解放されないため、古いスロットはメモリを破壊するのではなく、正しい型の別の値を読む。

データはすでにファイル形式である

var image: u8[>..] = tree.to_bytes();           // a framed byte image of the whole array
var loaded, ok = from_bytes<Node[>..]>(image);  // verified before it becomes a value
image[image.len - 3] = 200;                     // tamper with a link ...
var bad, bok = from_bytes<Node[>..]>(image);    // ... and it is false and an empty array

ツリーのリンクは自己相対なので、どこに置いても意味は変わらない。保存はバイト列を書き出すことであり、読み込みはそれを読み戻すことであり、シリアライザもスキーマもポインタの修正も要らない。from_bytes はバイト列が値になる前にフレーミング、すべてのタグ、すべての長さ、すべてのリンクを検査するので、壊れたファイルや悪意あるファイルは false になり、不正な参照になることは決してない。

常にその場で構築される

コピーなし構築の保証（spec §4.3）によれば、構築された値は常に最終的な置き場所に直接構築され、呼び出しを通じて上から下へ伝播する。grow-only 配列を値で返す関数は、その要素を呼び出し元の変数に直接書き込む。あるいは別の配列の中で構築中のレコードのフィールドに書き込む。そのため out 引数はほとんど登場しない。

words.push(str("word", i));                    // formatted straight into the new element
let evens = xs.filter() { it % 2 == 0 };       // built straight into `evens`: no temporary
book.push(Order { id: 1001, customer: "alice", items: parse_items("SKU-441:2:1999;SKU-7:1:500") });

呼び出しをまたいでエラーを返す

struct User { name: u8[..16], age: i32 }

fn load(text: u8[:]) -> User[>..], u8[] {
    var users: User[>..] = [];
    each_split(text, '\n') { users.push(parse_user(it)); };
    return users, "";
}

fn parse_user(line: u8[:]) -> User {              // returns a User: no Result, no error parameter
    let comma = find(line, ",");
    guard comma >= 0 else { return [], str("expected name,age: ", line) from load; }
    let age, ok = parse_int(line[comma + 1..]);
    guard ok else { return [], str("bad age: ", line) from load; }
    let name = trim(line[..comma]);
    return User { name: name, age: age as i32 };
}

return E from f は、何フレーム上であっても、f の最も内側でアクティブな呼び出しの結果として E を返し、その間にあるすべての関数は通常のシグネチャのままである。静的に検査されるので、parse_user のすべての呼び出しは load 呼び出しの内側になければならず、実行時に捕捉されないものはない。アンワインダではなくフレームごとに検査される隠れた判別子であり、メッセージは load の呼び出し元が欲しい場所に直接構築される。サンプル内のパーサは、あらゆる構文エラーにこれを使っている。

ジェネリクスと関数ブロック

fn twice(x) { x + x }                              // an untyped parameter is a generic one

fn each_pair<T, F>(xs: T[:]) {                     // F is a function value: a compile-time entity
    for i in 0..xs.len - 1 { F(xs[i], xs[i + 1]); }
}

fn first_gap(xs: i64[:]) -> i64 {
    each_pair(xs) { a, b => if b - a > 1 { return a; } };   // returns from first_gap, not each_pair
    return -1;
}

let evens = xs.filter() { it % 2 == 0 };
let total = fold(xs, 0) { acc, x => acc + x };
sort(xs) { a, b => a > b };

すべてが単相化される。型引数は引数の型から推論される。それらの型に現れないパラメータは明示的に指定できる。関数値はジェネリックパラメータとして渡される。すべての呼び出しは直接かつインライン化可能で、外へ逃げることはなく、クロージャオブジェクトも関数ポインタも存在しない。そのため高階関数は、見た目どおりのループにコンパイルされる。ブロックは字句的に外側の関数から return でき、ネストした関数は外側の関数のローカル変数を見ることができる。

何も共有しないスレッド

thread_fn worker() {                                // a separate program with its own memory
    loop {
        let job = qget<Job>();                      // blocks on the typed queue for Job
        guard job.n >= 0 else { break; }            // -1 means stop
        qput(Result { n: job.n, digits: count_digits(job.n) });
    }
}

for i in n { ids.push(thread_spawn(worker)); }

共有された可変メモリは存在しない。thread_fn とそれが呼び出すものはすべて、独自のデータスタックとグローバルのコピーを持つ独立したプログラムとしてコンパイルされる。値は型ごとに 1 つずつ用意された型付きキューを通じて受け渡され、どの深さにも参照を持たないフラットな値でなければならない。フラットな Goose の値は連続しているため、この受け渡しは安価だ。ジョブや結果はピクセルを含む実データをそのまま運び、境界を越えるのは memcpy1 回で済む。

thread_spawn_contained で起動したワーカー内でチェックが失敗するか abort が起きても、終了するのはそのワーカーだけだ。メッセージは stderr ではなく、それを待っている相手に届く。だからスーパーバイザはログに残して次のワーカーを起動できる：

var why: u8[>..] = [];
while !thread_wait(thread_spawn_contained(serve, attempt), why) {
    log(why);                                       // "assert failed (serve.goose:12)"
    why.clear();
    attempt++;
}

ワーカーに対する最初の thread_wait(id, msg) がメッセージを受け取る。要求しなかった呼び出し元はメッセージを失う。

普通の C を入力に、普通の C を出力に

extern fn hypot(x: f64, y: f64) -> f64;             // straight from libm
extern fn crc32_bytes(s: const u8[:]) -> u32;       // a slice crosses as { data, len }
extern fn stats_of(xs: i32[:], out: Stats&);        // a struct filled through a pointer

extern fn は Goose のシグネチャを C のシンボルに結びつける。math モジュールと os モジュールはこのインターフェースを使う。境界を越えられるのは、C での表現がサポートされている型だけだ。サポート外のシグネチャは宣言の時点で拒否される。コンパイラはプログラム全体に対して C ファイルを 1 つ出力する。同梱の TinyCC バックエンドは、その C を Goose コンパイラのプロセス内でコンパイルして実行できる。

速度の源泉

速度の大半はメモリモデルから来ている。ヒープ割り当てやオブジェクトごとの破棄がなく、データは連続し、リンクは細く、enum は格納するバリアントに合わせたサイズになっている。すべてのインデックスは境界チェックを受け、不要と証明できるチェックはコンパイラが除去する。スライスの長さに対する assert があれば、カーネルは残りのチェックを排除してベクトル化できることが多い。--bce-lines は残存するチェックを報告する。checkfree fn は境界チェックが 1 つでも残るカーネルを拒否する。インデックス型を使えば、グラフの辺は構築時に済ませた検証を保持できる。ベンチマークはプロセス全体の実時間で測定しており、破棄も含む。

16 個のベンチマークの幾何平均	慣用的な C++ 比	手作業で最適化した C++ 比	最良の safe Rust 比
速度、MSVC バックエンド	3.51x	1.24x	1.13x
速度、clang バックエンド	3.54x	1.26x	1.19x
ピークメモリ	1.95x 少ない	1.32x 少ない	1.25x 少ない

summaryでは得たものと失ったものを説明している。results.mdにはすべての測定値があり、design.mdはスイートが何をテストしているかを説明している。

支払うことになるコスト

• データがどこに置かれるかを意識する必要がある。誰が所有するのか、そのスコープはどこまで続くのか。答えはたいてい「それを構築する関数」であり、それならコストはかからない。そうでない場合は reusable プールを使う。
• 再帰関数は、再帰呼び出しをまたいで成長可能なデータを保持できない。スクラッチは呼び出しの前に終わり、それを超えて生き残るものはプールとして渡す。
• 可変サイズ要素の配列は反復できるがインデックスはできない（参照のインデックスを横に置くのでなければ）。固定モードの enum は指し先にできず、可変モードの enum は上書きできない。コンテナごとに選ぶ。
• 脱出するクロージャはなく、関数ポインタもなく、ADT タグを超える動的ディスパッチもなく、コンパイルはプログラム全体のみ。
• reusable プールに返したスロットをまだ名前で参照していると、次の所有者が書き込んだ内容が読める。これはロジックのバグであり、メモリ破壊にはならない。

完全なリストはチュートリアル §18にある。

ドキュメント

• ドキュメント索引：以下すべての地図であり、これらのファイルから構築されるドキュメントサイトのルート（方法）。
• チュートリアル：例を通して学ぶ親しみやすい入門。まずはこれを読む。
• 言語リファレンス：すべての機能をトピックごとに、それぞれコンパイルできる例とともに解説。言語全体を読める形で書いたもの。
• 言語仕様：正確なルール。なぜコンパイルできなかったのかを知りたいときに。
• サンプル：読む順に並んだ 31 の完全なプログラム。言語のツアーから、JSON パーサ、スレッドを使った Mandelbrot、2 つのプールから構築するファイルツリー、GPU 上の回転するキューブ、ヒープに降り注ぐ数千のボックス、ウィジェットのウィンドウに収まった ToDo リストまで。
• 標準ライブラリ：stdlib/ 配下の読める Goose で書かれた 14 のモジュール。gfx、SDL3 の GPU API 上のグラフィックス（構築方法）、physics、Box3D 上の剛体物理（構築方法）、ui、フォント、テキストレンダリングとゲーム HUD、Nuklear 上のウィンドウとウィジェットを gfx 経由で描画するもの（構築方法）を含む。
• プログラムのビルドとパッケージの利用：goose build、git リポジトリやディレクトリからのライブラリ、プログラム自身の C、そして自分でパッケージを作る方法。
• ベンチマーク：数値と、その背後の完全な結果および設計。
• 実装ノート：コンパイラがパスごとにどう動作するか、そしてテスト方法。

ステータス

Goose は新しい。現時点で存在するのは、プログラム全体をコンパイルする約 3 万行の C++ コンパイラ、仕様書、標準ライブラリ、サンプル、そして CI が Windows、macOS、Linux で追加のサニタイザジョブとともに実行するテストスイートだ。現時点で意図的に対象外としているものは、リサイズ可能な値のムーブ、構造体ごとに複数のリサイズ可能値、ラベル付き break、名前空間のプライバシー、そして OS やライブラリへのさらなるアクセスだ。未対応項目は仕様書の付録 B で追跡している。

ライセンス

Goose は Apache License, Version 2.0 の下でライセンスされている。

著者

Wouter van Oortmerssen：言語設計、コンパイラ設計、コーディング規約。ホームページ、twitter。

Claude Fable：コンパイラ実装、ベンチマーク、サンプルとドキュメントの執筆。

歴史と AI の使用

このリポジトリは、人間による言語設計から、ほぼすべて AI を使って作られた。Goose は数年前に設計し、実装にも着手していた。だがゲームスタートアップの経営（これも私の別のプログラミング言語 Lobster で作られている）に追われ、完成させる時間がなかった。Goose が他の言語にはできないことを実現できると分かっていたし、存在すべき言語だと思っていたので、これは残念だった。

Fable が出るまで、AI がこの作業を助けてくれるとは思っていなかった。十分に優秀で、まともな仕事ができるかもしれないと考えたのだ。私が最近書いた別のコンパイラ（Lobster）のスタイルと構造を、Fable にほぼそのまま踏襲させた。だからコードを見ると、かなり Lobster に似ている。当初の設計では多くの点を未規定のままにしていたが、Fable とのやり取りを何度も重ねるうちにすべて決まり、そのおかげで今はより良い言語になっている。

これはまた、既存の言語を再現するのではなく、新しい言語を実装するために AI を使う試みでもある。

なぜ C++ で作業させたのかと不思議に思うかもしれない。Rust でも、自作の Lobster でも、あるいは Goose 自身でも（それはまだ実現するかもしれない）、明らかにどの言語でもよかったのだから。Fable を使う中で分かったのは、どの言語でもほぼ同じように力を発揮するということ、そして Rust などが持つ強力なガードレールは、かつてほど切実ではなくなったということだ。コンパイラは C を出力するので、C/C++ コンパイラはどのみち手元にある可能性が高い。ひとつのエコシステム内に収めておけば、デプロイと採用が簡単になりそうだ。libtcc も組み込んだし、今後どの C ライブラリを組み込むかは分からない。それに前述のとおり、コンパイラのコードを既存の Lobster コンパイラに似せるのは楽しかった。少なくとも、自分のコードとして読める。