再帰の深淵を制御せよ：HackにおけるRecursive Typesの設計と「死なない」再帰の極意
Hackの型システムにおいて、再帰型（Recursive Types）は諸刃の剣だ。木構造やネストされたグラフデータを扱う際、型定義を誤ればHHVMの型チェッカー（`hh_client`）は容赦なく悲鳴を上げ、最悪の場合、JITコンパイルの最適化パスを阻害してランタイムパフォーマンスを低下させる。
なぜ、平凡な再帰定義がシステムを蝕むのか。そして、我々はどうすれば「理論的に正しく、かつ実用的に堅牢」な再帰型を構築できるのか。コアコミッターの視点から、その核心を解き明かす。
—
1. なぜ「単純な再帰」は罠なのか
Hackの型チェッカーは決定性（Decidability）を担保するために設計されている。特に複雑な自己参照型を扱う際、型推論が無限ループに陥らないよう、`type` エイリアスにおける再帰には厳格な制約がある。
よくあるアンチパターンはこれだ。
// 警告：これは型チェッカーを混乱させる可能性が高い
type Node = shape(
‘value’ => mixed,
‘children’ => vec
);
この定義は単体では動くように見えるが、複雑なジェネリクスや共用体（Union types）と組み合わせた瞬間、型解決の計算コストが爆発する。HHVMの型チェッカーはスタックオーバーフローを避けるために探索深度を制限しているため、定義が深すぎると「Type inference failed」と突き放されることになる。
—
2. 実践：再帰を安全に扱う「代数的データ型」パターン
木構造を定義する際、`shape` だけで構成するのは避け、`enum` や `abstract class` を組み合わせたタグ付き共用体（Tagged Unions）のアプローチをとるのがHackにおけるベストプラクティスだ。
以下のコードは、AST（抽象構文木）やメニュー構造を安全に表現するための設計パターンである。
namespace App\DataStructures;
/
- 再帰的なツリー構造を表現する代数的データ型
- 継承ではなく、型チェッカーが明示的に追跡可能なインターフェースを使用する
/
interface Tree {}
final class Leaf implements Tree {
public function __construct(public int $value) {}
}
final class Branch implements Tree {
// vec
public function __construct(
public vec
) {}
}
/
- パターンマッチングによる再帰処理
- HHVMのJITは、instanceofのチェックを極めて高速にインライン化する
/
function sumTree(Tree $node): int {
if ($node is Leaf) {
return $node->value;
} else if ($node is Branch) {
$sum = 0;
foreach ($node->children as $child) {
$sum += sumTree($child);
}
return $sum;
}
invariant_violation(‘Unknown tree type’);
}
なぜこれが「美しい」のか
1. 型安全性: `shape` のような構造的な型よりも、クラスベースの定義は型チェッカーがキャッシュしやすく、エラーメッセージも明確になる。
2. パフォーマンス: `if ($node is Leaf)` はHHVMレベルで型ガード（Type Guard）として最適化される。これは、ハッシュマップを何度も参照する `shape` よりも遥かに低コストだ。
—
3. 非同期API連携における「再帰的構造」の罠
外部APIからネストされたJSONを受け取る際、`json_decode` の結果をそのまま再帰型に流し込むのは自殺行為だ。JSONは不完全なデータ構造になり得るため、「境界線（Boundary）」でのバリデーションが不可欠となる。
実務レベルでは、`Shape` や `dict` のまま扱わず、必ずコンストラクターで再帰的に型変換を行う「DTO（Data Transfer Object）」を経由させること。
// 非同期データ取得後の安全な再帰マッピング
final class ConfigNode {
public function __construct(
public string $key,
public vec
) {}
public static function fromDict(dict
$children = vec[];
$rawChildren = $data[‘children’] ?? vec[];
// 再帰的にマッピングを行うことで、型安全な境界を確保する
foreach ($rawChildren as $child) {
if ($child is dict<_, _>) {
$children[] = self::fromDict($child);
}
}
return new self($data[‘key’] as string, $children);
}
}
—
4. チーフアーキテクトからの助言：制約を味方につけろ
Hackの再帰型をマスターする上で最も重要なのは、「型チェッカーを迷わせないこと」だ。
- 循環参照を避ける: 型定義の中に循環が含まれる場合、必ず `interface` を介して間接参照にする。
- 深すぎる再帰の回避: 再帰的な構造が深く（例えば1000層以上）なる可能性がある場合、再帰アルゴリズムではなくスタック（`vec`）を使った反復処理に書き換えること。HHVMのスタックフレームを無駄に消費しない設計が、可用性を直結させる。
- `mixed` を排除する: 再帰の末端が `mixed` になっているコードは、将来のエンジニアへの時限爆弾だ。可能な限り `T` 型などのジェネリクスを使用し、型を固定せよ。
型システムは、制約が増えるほど表現力が高まる。再帰という複雑な概念を、クラスという箱に閉じ込め、インターフェースで制御する。この規律こそが、大規模なHackコードベースを健全に保つ唯一の道だ。
コードレビューの際、`shape` のネストが3段階を超えていたら、「それはリファクタリングの合図だ」と伝えなさい。それが、真に洗練されたエンジニアの振る舞いだ。