今日の「今更気付いた事」

スタックはFILOの性質を持つので、単方向リンクリストで実装すべき。
そうすれば、(スタックに保存される情報がimmutableであるという前提ならば)スタック自体もimmutableになるので、call/cc(もしくは類似の用途)の為にスタックを非破壊的かつ低コストで保存できる。
また、単方向リンクリストを採用する事によって「単一の過去から複数の未来へ分岐する」構造(つまり、多世界解釈的なスタック構造)をそのまま扱える為、並行処理を目的とするようなVMにとってもおいしい。
勿論、「あとで任意の時点でのスタックトレースを調べる為に、一時的にスタックの内容を保持しまくりたい」といった要望にも低コストで答える事ができる。

という事に気付いたが、調べてみたらこれは基本中の基本のようだった。
どうも無意識の内に、「cpuやVMがネイティブで使うスタックは、破壊的かつ高速でなくてはならないので、連続したメモリ上の一次元配列にする一択」という固定観念があったようだ。