【入門編】【上級者向け】Recursive Typesの定義と制限：木構造や再帰的データ構造を安全に扱う方法 – Hack言語コア・静的型システムとHHVMのアーキテクチャ解析バイブル

こんにちは！HHVMの内部構造やHackの厳格な型システムに魅せられた皆さん、日々のコーディング楽しんでいますか？

他のプログラミング言語、例えばTypeScriptやJava、RustあたりからHackの世界に飛び込んできた開発者が、最初に「おっ？」と立ち止まる壁のひとつが厳格な静的型付け（Strict Mode）における再帰的データ構造（Recursive Types）の扱いなんですよね。

「木構造（Tree）やグラフ構造を安全に表現したいのに、型チェッカーに怒られてしまう……」
そんな悩みを抱えたことはありませんか？

今回は、HHVMの型チェッカーが裏側でどうやって型を見ているのかという本質に少しだけ触れながら、Hackで再帰的データ構造をエレガントかつ安全に定義する極意を、優しく紐解いていきますね。ここをクリアすれば、Hackの型システムの奥深さがグッと身近になりますよ！

—

そもそも、なぜHackの「Strict Mode」で再帰型が難しくなるのか？

Hackでは、ファイルの先頭に `hh_strict` を宣言することで、完全な静的型付けの世界に入ることができます。これにより、実行時エラーの大部分をコンパイル（型チェック）時に根絶できるのが最大の強みですよね。

しかし、自分自身の型の中に自分自身を組み込もうとする「再帰的データ構造（Recursive Types）」を素朴に書こうとすると、型チェッカーが無限のネストの迷宮に迷い込んでしまい、コンパイルエラーを引き起こすことがあります。

まずは、よくある「やってしまいがちな失敗例」を見てみましょう。

陥りがちな文法エラーの例

<<__Strict>>
namespace Hack\Exs;

// 【注意】これは意図通りに動かない（あるいは制限にぶつかる）例です
class Node {
// 自分自身をプロパティに持たせたい！
public function __construct(
public string $value,
public ?Node $left,
public ?Node $right,
) {}
}

「あれ？これ普通に動くんじゃなの？」と思いましたよね。実は、単純なクラスベースの参照であればこれでも動くケースはあるのですが、ジェネリクスやエイリアス、あるいは複雑なイミュータブル（不変）な構造を表現しようとした瞬間、型チェッカーは牙をむきます。

特に、`type` や `newtype` を使った型エイリアスで再帰を行おうとすると、HHVMの型チェッカーは無限展開を防ぐために厳格なガードを発動させます。

// これは型チェッカーに拒絶されます（無限再帰の検知）
type RecursiveList = ?(T, RecursiveList);

「自分の定義の中に自分自身が無限に出てくる型」は、型推論エンジンにとって計算量の爆発やデッドロックを招く魔物なのです。

—

安全に木構造を構築する：Hack流・再帰型の極意

では、Hackで安全かつパフォーマンス高く木構造や再帰的データ構造を扱うにはどうすれば良いのでしょうか？
答えは「適切なクラス設計」と「代数的データ型（ADT）的なアプローチ」の組み合わせにあります。

HHVMのJITコンパイラと型チェッカーを最大限に味方につける、実用的なコードを見てみましょう。

実装例：安全なジェネリック・ツリー構造

<<__Strict>>
namespace Hack\Advanced;

汎用的なバイナリツリーのノードを表現するクラス
厳格な型付けのもと、安全に再帰構造を維持します。

/
final class BinaryTree {
// プロパティの型を明示し、不変性（Immutability）を意識させる設計
public function __construct(
private T $value,
private ?BinaryTree $left = null,
private ?BinaryTree $right = null,
) {}

public function getValue(): T {
return $this->value;
}

public function getLeft(): ?BinaryTree {
return $this->left;
}

public function getRight(): ?BinaryTree {
return $this->right;
}

再帰的にツリーを走査するメソッド（深さ優先探索）

/

public static function traverse(
?BinaryTree $node,
(function(T): void) $callback,
): void {
if ($node === null) {
return;
}

// 左を走査
self::traverse($node->getLeft(), $callback);
// 現在のノードを処理
$callback($node->getValue());
// 右を走査
self::traverse($node->getRight(), $callback);
}
}

// — 実際の利用イメージ —
<<__EntryPoint>>
function main(): void {
// 数値を格納するツリーを構築
// (10)
// / \
// (5) (20)

$root = new BinaryTree(
10,
new BinaryTree(5),
new BinaryTree(20)
);

// 安全に型チェックされたコールバックで走査
BinaryTree::traverse($root, (int $val) ==> {
echo “Value: {$val}\n”;
});
}

このコードの美しいところは、HHVMの型チェッカーが `T` の型を完全に追跡できるため、コールバック関数の中身まで一切の妥協なく静的型安全が保証される点です。

—

HHVMの裏側：なぜこのアプローチが効率的なのか？

ここで少しだけ、HHVMのアーキテクチャに踏み込んでみましょう。

Hackのコードは、一度bytecode（HHBC）にコンパイルされ、HHVMの仮想マシン上で実行されます。その際、型チェッカー（`hhvm` の静的解析フェーズ）は、クラスやメソッドの境界を越えた無限の型展開を嫌います。

先ほど紹介したクラスベースの再帰構造がなぜ安全に処理されるかというと、「参照（Reference）の方向が明確であり、型チェッカーがツリーの深さをその場で展開する必要がないから」です。型チェッカーは「あ、このプロパティは自分自身の型を持つポインタだな」と構造のポインタとして一発で認識できるため、無限ループに陥らないのです。

もしあなたが複雑なJSONパーサーや抽象構文木（AST）をHackで実装する場合も、この「クラスによるカプセル化と自己参照」のパターンを守ることで、HHVMの型チェッカーを完璧に味方につけることができます。

—

まとめ：ここをクリアすればHackの基本はバッチリ！

今回は、HackのStrict Modeにおける再帰的データ型の制限と、それを安全に突破するための実践的なテクニックを解説しました。

型エイリアスでの過度な自己参照は型チェッカーを混乱させるので避ける。
`final class` とジェネリクスを組み合わせたオブジェクト指向アプローチが最も安全でHHVMと相性が良い。
再帰メソッドを書くときは、ベースケース（終了条件、例：`$node === null`）を必ず記述し、型安全なコールバックを活用する。

このポイントさえ押さえておけば、複雑なデータ構造を扱う大規模なHackアプリケーションでも、型エラーにおびえることなく、自信を持ってコードを書くことができるようになりますよ。

厳しいけれど、私たちのコードを最高の品質へと導いてくれるHackの型システム。ぜひ今日の開発から試してみてくださいね。それでは、次の極限の知見でお会いしましょう！