YOYU Stack：縮小共有・分岐拡張を持つ汎用スタック構造
概要
[編集]本稿では、YOYUにおいて設計された「ヨユースタック（YOYU Stack）」の一般構造を定式化し、スタック構造を必要とする様々な文脈（実行コンテクスト、構文解析、逆探索アルゴリズム、証明木、など）への応用可能性を示す。この構造は、**縮小時の共有、拡張時の分岐、pinnedフラグによる明示的ライフサイクル管理**という三原則に基づいて構成される。
背景
[編集]従来、スタックは線形に伸縮する単一構造として扱われてきた。関数呼び出しスタック、逆探索の履歴、構文解析の状態スタックなどがそれにあたる。しかし、現代的な処理系では、バックトラッキング、並列分岐、継続、クロージャといった要請により、**状態空間の分岐と合流**が必要になる。
ヨユースタックの三原則
[編集]縮小時の共有
[編集]同一の上位構造に戻る縮退的な操作では、新たな構造を作らず、既存の共有ノードを再利用することでメモリと計算コストを最小化する。
拡張時の分岐
[編集]別の方向に状態が進展する場合には、新たな子ノードを接続することで、非破壊的な状態分岐を可能とする。これにより過去の状態を温存したまま新しい状態に移行できる。
pinnedによるライフサイクル管理
[編集]特定の状態ノードが外部から参照される（例：クロージャ、継続、スナップショットなど）場合には、pinnedフラグを立てることでガベージコレクション対象から除外する。これにより参照解決の正確性を維持しつつ、GCレス動作を可能とする。
応用事例
[編集]関数呼び出しスタック
[編集]通常の関数呼び出しではスタックポインタのみを操作すればよいが、継続やクロージャなどの非線形遷移が要求される場合でも、ヨユースタックにより自然な分岐と保持が可能となる。
逆探索アルゴリズム（例：深さ優先探索）
[編集]探索の状態履歴をすべて記録・分岐しつつ、終了した探索の枝を即時破棄可能。backjumpingやmemoizationとの親和性が高い。
構文解析・証明木構築
[編集]構文解析状態や導出規則適用の履歴を分岐ごとに保持し、必要に応じて復元可能。形式論理における構文木の追跡にも適用可能。
実装指針
[編集]各ノードは以下のフィールドを持つ：
- 親ノードへのポインタ
- 自身を構成するローカルデータ
- pinnedフラグ
- 子ノードへの枝分かれリンク群（任意）
YOYUではこの構造を**ハッシュテーブルベースの変数束縛環境**に直接応用している。
意義
[編集]本構造は、再帰・継続・スレッド・非決定性探索といった制御構造において、**統一的で破壊を伴わない記述と実行**を可能とする。また、状態のコピーやGCの負担を軽減する設計にも通じる。