Pythonのコンパイラを作りたい #5 - リストと辞書の実装

こんにちは。前回（「#4 - 関数定義とスコープ（簡易的な static typing での解釈）」）は、Python の def 文を LLVM IR の関数定義に落とし込む方法をご紹介しました。AST 上の FunctionDef を解析してシンプルな静的型付き関数として扱うことで、高速なコード生成が可能になっていました。

今回は、リスト (list) と辞書 (dict) にスポットを当てます。
Python のリストと辞書は、異なる型の要素を混在できたり、要素数を柔軟に増やしたり、ハッシュマップ的なアクセスを行ったりするなど、非常に動的なデータ構造です。こうした振る舞いを C言語でどう再現しているのか を、実際の構造体や関数実装を例に見ながら紹介していきます。

リポジトリ:
https://github.com/t3tra-dev/pyc

1. PyList の構造

1-1. Python 的なリストの要件

まず、Python のリストがどのような特徴を持つかおさらいしましょう。

1. 型がバラバラでも要素を追加できる
   たとえば [1, "two", 3.0] のように、数値・文字列などが同じリストに入ってもエラーになりません。
2. リストの長さを自由に伸縮できる
   append, insert, pop などで要素数が動的に変化する。
3. インデックスアクセスで好きな位置の要素を取り出せる
   lst[0], lst[1] のように、ランダムアクセスが O(1) で行える (内部的には配列)。

CPython の実装では、PyListObject が「メモリを確保した配列 (element array)」+「現在の要素数や容量(capacity)」をもつ構造となっており、必要に応じて配列サイズを再確保 (realloc) する方針です。本プロジェクト pyc でも、ほぼ同様の手法を C 言語で再現しています。

1-2. 実際の構造体定義

コード例としては以下のようになっています。(runtime/builtin/types.h を参照)

typedef struct PyList {
    int size;        // 現在の要素数
    int capacity;    // 確保している配列の要素数
    void **items;    // ポインタ配列へのポインタ (要素は全て void* で保持)
} PyList;

• size はリスト内に入っている要素数
• capacity は確保済み領域の大きさ (size <= capacity)
• items は「void* の配列」を指し示すポインタ

Python の世界では型が混在するため、内部表現としてはすべて void* として格納しています。こうしておけば、整数でも文字列でもユーザー定義オブジェクトでも、何でも指せるわけです。

1-3. 生成と追加 (PyList_New, PyList_Append)

本プロジェクトでは、runtime/builtin/functions.c などに以下のような関数を用意し、リスト操作を行っています。

1. PyList_New(int capacity)

• 初期容量 capacity ぶんの void* 配列を確保
• PyList 構造体も確保して、size = 0, capacity = capacity, items = ... を設定
• ユーザーが 0 以下を指定したらデフォルト値 (たとえば 8) を使う
• 戻り値として PyList* を返す

2. PyList_Append(PyList *list, void *item)

• if (list->size >= list->capacity) なら拡張処理を実施
  • 新しい配列を GC で確保し、既存の要素をコピー
  • list->capacity を大きめ (例えば 1.5倍など) に設定
• コピー先配列の list->items[list->size] = item;
• list->size++

こちらは CPython が行っている方法とほぼ同じ「動的配列」戦略です。ただし、再確保のアルゴリズムやオーバーヘッド削減策など細かい最適化はあまり入れていません。「とりあえず動く」くらいの簡易実装でも、思ったより実用的に動いてくれます。

2. PyDict の構造

2-1. 辞書とハッシュテーブル

Python の辞書 (dict) はハッシュテーブルに基づいており、キーから O(1) で値を取り出せるのが特長です。さらにキーや値の型を問わずに使えるなど、非常に多機能なデータ構造になっています。
pyc では、複雑な最適化はさておき、最低限のハッシュテーブルを C 言語で実装し「動的な辞書」を作っています。内部構造は以下のとおりです。

typedef struct PyDict {
    int size;        // 現在の要素数 (キーが実際に埋まっている数)
    int capacity;    // 配列全体のサイズ
    void **keys;     // キー配列 (NULLなら未使用)
    void **values;   // 値配列 (keys[i]に対応するvalueを格納)
} PyDict;

• size はキーを格納しているスロット数
• capacity はハッシュテーブルの全スロット数
• keys と values は同じ長さの配列で、keys[i] が NULL なら対応する values[i] も NULL
• 全て void* で扱うので、実際のデータ型はユーザー側が把握している前提

2-2. オープンアドレス方式 (線形探査)

ハッシュ衝突が起きたときには、単純なオープンアドレス方式 (線形探査) を採用しています。
以下は PyDict_SetItem(dict, key, value) のフロー概略です:

1. 要素数が capacity/2 以上になると「再ハッシュ」して容量を倍増
2. h = hash_object(key) でハッシュ値を得る
3. i = h % dict->capacity
4. while dict->keys[i] != NULL && dict->keys[i] != key: i = (i + 1) % dict->capacity;

• 同じキーが見つかれば上書き
• NULL スロットを発見すれば新規挿入

5. dict->keys[i] = key; dict->values[i] = value; dict->size++;

このように、キーのハッシュ値から得たインデックスに挿入し、被っていたら次のインデックスへ……という素朴な手法です。CPython ではさらに高度な探査アルゴリズム (ランダム化やバケット再配置など) を用いて衝突を減らしていますが、pyc ではそこまで踏み込んでいません。

2-3. hash_object の単純さ

現状では unsigned int hash_object(void *key) が、単にポインタ値をキャストして返すだけという非常に簡素な実装です。
厳密に言えば、ポインタをハッシュとして使うのはそこまで有用ではありませんし、Python らしいオブジェクト指向のハッシュ計算とはほど遠い方法です。しかし「最低限ハッシュらしい動きをする」という目的には十分で、プロトタイプとしてはこれでも動きます。
将来的には「PyString 型をキーにした場合は文字列ハッシュを、PyInt 型の場合は整数値のハッシュを計算する」といった形に拡張し、衝突率を下げるのが望ましいでしょう。

3. Python 的挙動を C 言語で再現する苦労

3-1. 異なる型の混在

PyList の items や PyDict の keys, values はすべて void* に統一してあるため、C 言語レベルのコンパイルエラーは回避できます。しかし、「要素を参照して実際に何をするか？」という段になると、呼び出し元が適切にキャストしないと正しい操作ができません。
たとえば整数なら PyInt* に、文字列なら String* にキャストして使う、といった具合です。これは Python の動的型に近い挙動を実現するために仕方ない部分ですが、C 的には安全性が低くなる欠点があります。

3-2. リサイズと再ハッシュ

Python らしさを再現するためには、「リストを append で伸ばす」「辞書を SetItem で増やす」などでメモリ再確保が頻繁に起きる可能性があります。C 言語なら通常 malloc/realloc/free を駆使するところですが、このプロジェクトでは Boehm GC を採用することで、メモリ解放を意識せずに済むようにしています。
GC_malloc を使うと、list->items をコピーして古い配列は放置していても、GC (ガベージコレクタ) が不要になった領域を回収してくれるというわけです。これがない場合は、すべてのオブジェクトの解放タイミングを追跡しなければならず、実装の手間が大幅に増えるところでした。

3-3. 性能面での悩み

CPython のリスト・辞書は数十年の歴史で最適化が進んでおり、様々なチューニングが施されています。pyc の実装はそこまで洗練されていないため、要素数が増えたり衝突が増えたりすると速度が落ちる可能性があります。
しかし、AOT コンパイラと LLVM の強力な API を組み合わせることで、ある程度のマイクロ最適化は LLVM が勝手にやってくれますし、何より「動的型」のオーバーヘッド自体が問題になるほどの大規模アプリケーションを想定していない実験プロジェクトなので、十分に許容範囲内だと考えています。

4. リスト・辞書を実際に使うときの例

4-1. Python でのコード

たとえば source.py に次のようなスクリプトを書いてみます。

listvar = [0, "hello", 42]
dictvar = {
    "apple": 3,
    "banana": 5,
}

pyc では、AST を解析して PyList_New / PyList_Append などの呼び出しを生成し、リストを構築します。また、辞書の場合は PyDict_New / PyDict_SetItem などを呼び出す IR を出力します。
実行時には runtime/builtin/functions.c にある print 関数が呼ばれ、要素を文字列化して画面に表示するイメージです (現在の実装はあまり高機能ではなく、要素をひとつずつ出力する程度)。

4-2. LLVM IR 中での呼び出し例

上記のスクリプトを python -m pyc --emit-llvm source.py した場合、IR には以下のような行が並びます。(イメージ)

%t2 = call ptr @PyList_New(i32 8)
; append 0
%t3 = call ptr @PyInt_FromI32(i32 0)
call i32 @PyList_Append(ptr %t2, ptr %t3)
; append "hello"
%t4 = call ptr @create_string(ptr @.str.1)
call i32 @PyList_Append(ptr %t2, ptr %t4)
; ...

%t9 = call ptr @PyDict_New(i32 8)
; dict["apple"] = 3
%keyA = call ptr @create_string(ptr @.str.2)
%valA = call ptr @PyInt_FromI32(i32 3)
call i32 @PyDict_SetItem(ptr %t9, ptr %keyA, ptr %valA)
; ...

ここで PyInt_FromI32 は整数をオブジェクトとしてラップする関数、create_string は C の文字列を Python 風オブジェクトにする関数です。リストや辞書には最終的に void* として格納されます。
このように “Python のデータ構造” を C で擬似的に表現し、IR から対応する関数を呼び出しているというわけです。

5. まとめ & 次回の話

今回は、リスト (PyList) と辞書 (PyDict) を C 言語で実装し、Python 的な動的配列・ハッシュマップを再現する方法を解説しました。
ポイントは以下の通りです。

• リストは「配列+ 動的リサイズ」という仕組みで、CPython とほぼ同じコンセプトを踏襲
• 辞書は「ハッシュテーブル (オープンアドレス方式)」を採用し、最低限の SetItem, GetItem を実装
• すべて void* で扱うことで、異なる型を混在させてもコンパイルエラーが起きない (ただし実行時の安全性は低い)
• Boehm GC の存在により、複雑なメモリ管理を手書きしなくても済むのが大きな利点

こうした仕組みのおかげで、フィボナッチや数値演算だけでなく、リスト操作や辞書操作も最低限動く "Python もどき" が作れています。機能は限られていますが、プロトタイプとしては十分面白い領域です。

次回は「ランタイムとメモリ管理 (Boehm GC の導入経緯)」をもう少し掘り下げる予定です。自力でメモリ解放処理を書くのが大変だった話や、GC を導入したメリット・デメリットなどを紹介しながら、Python 的なガーベジコレクションをどう再現しているかを見ていきましょう。

次回:
https://zenn.dev/t3tra/articles/f1d407419da53d