- 初期のコンピューターでは、スタックやヒープがなくても関数呼び出しを実装する必要があり、コンパイラは引数・戻りアドレス・ローカル変数に対応する隠しグローバル変数で呼び出し状態を管理していた
- 呼び出し側は引数を保存し、戻りアドレス変数に復帰位置を書き込んでから関数の開始位置へジャンプし、関数は計算後に保存されたアドレスへ再びジャンプした
- 論理上のローカル変数も実際にはグローバルな保存領域を使っていたため、見た目は関数でも内部動作は固定メモリと
goto に近かった
- 一部の ABI やプロセッサは、引数の受け渡しや戻りアドレス処理をレジスタや
branch with link で最適化していたが、基本的な制約はそのままだった
- 同じ関数の戻りアドレスが新しい呼び出しで上書きされるため、再帰呼び出しは不可能であり、当時の言語は再帰を禁止するか、明示的にのみ許可する形で対応していた
スタックなしで関数呼び出しを構成する方法
- 初期のコンピューター環境では、今日では当然と考えられているスタックやヒープが存在しなかった
- ヒープがない環境での動的メモリ確保は、固定長バッファで代用できた
- 可変サイズのデータを扱う場合でも、十分に大きな固定バッファをあらかじめ予約した
- 要求データがバッファ容量を超えると、致命的エラーとしてプログラムを終了した
- より親切な実装では、コンパイル時に最大容量を設定できるようにした
- さらに洗練された実装では、固定バッファの上にカスタムアロケータを置き、
allocate や free のように使えるようにした
隠しグローバル変数ベースの呼び出し規約
- スタックなしで関数呼び出しを実装するため、コンパイラは各関数ごとに複数の隠しグローバル変数を定義した
- 入力引数ごとのグローバル変数
- 関数の戻りアドレスを格納するグローバル変数
- ローカル変数に対応するグローバル変数
- 呼び出しコードは次の順序で実行された
- 引数の値を対応する隠しグローバル変数に保存する
- 復帰先の位置を関数の戻りアドレス変数に記録する
- 関数の開始位置へ
goto でジャンプする
- 関数は引数とローカル変数の両方を隠しグローバル変数から読み書きした
- 実行が終わると、戻り値を戻り値レジスタに入れ、関数の戻りアドレス変数に保存されたアドレスへジャンプした
C 風のコードが goto ベースのコードに変わる例
- 例の関数
add_two_values(int a, int b) は、スタックなしでは次のような保存領域に変換できる
a2v_a, a2v_b は引数保存用のグローバル変数a2v_c はローカル変数 c に対応するグローバル変数a2v_retaddr は復帰先アドレス保存用のグローバル変数
- 呼び出し元
sample() は、31415 と 2718 をそれぞれ引数用グローバル変数に保存する
- 続いて
a2v_retaddr に resume の位置を入れ、add_two_values へジャンプする
add_two_values は計算結果を return_value_register に保存した後、a2v_retaddr に従って復帰するresume の位置へ戻った呼び出し元は、戻り値レジスタの値を sample_x に保存する
レジスタと branch with link を用いた最適化
- 同じ構造は、ABI レベルでレジスタ渡しを使うことでより高速にできる
- 多くのプロセッサは特別な
link register と branch with link 命令を備えていた
branch with link は、分岐命令の次の命令のアドレスを自動的に link register に保存する- 呼び出し側は最初の 2 つの引数を
argument_register_1, argument_register_2 に入れられる
- 被呼び出し関数は、これらのレジスタ値を自分の隠しグローバル変数へ移して利用できる
- 戻りアドレスも
link_register から関数の戻りアドレス変数へ保存できる
- この最適化でも、スタックなしで呼び出しと復帰を行うという基本構造は維持されていた
再帰が妨げられる理由
- この呼び出し方式の中核的な制約は、再帰呼び出しができないことにある
- 再帰呼び出しが発生すると、同じ関数の戻りアドレス変数が新しい呼び出しの戻り先で上書きされる
- 外側の呼び出しが終わるとき、本来戻るべき位置が失われ、誤った位置へジャンプしてしまう
- 当時のプログラミング言語は、再帰をサポートしないことでこの問題を回避していた
- FORTRAN は当初サブルーチンすらサポートしておらず、サブルーチンが追加されたのは 1958 年だった
- FORTRAN で再帰サポートが標準になったのは 1991 年で、その際もサブルーチンを
RECURSIVE と明示する必要があった
自己書き換えコードと初期プロセッサのサブルーチン命令
- 一部のコンパイラは、より巧妙に自己書き換えコードを使っていた
- 関数末尾のジャンプ命令に含まれるアドレス欄が、実質的に戻りアドレス変数の役割を果たしていた
- この方式は単なるトリックではなく、実用上の必要だった可能性もある
- 一部のプロセッサは間接ジャンプをサポートしていなかったかもしれない
- サブルーチンの実用性が認められると、多くのプロセッサが専用の呼び出し命令を追加した
- 戻りアドレスをサブルーチンの最初のワードに保存する
- 実際の実行は 2 番目のワードから始まる
- 復帰時にはサブルーチン開始ラベルを通じた間接ジャンプを実行する
- 例のアセンブリでは
bsr add_two_values が add_two_values の最初のワードに戻りアドレスを保存し、ダミーの nop の次にある実際の命令から実行を開始する
1件のコメント
Hacker News のコメント
このテーマでは The Art of Computer Programming が本当に良かった。
一見すると古びて見えるが、ヒープやスタック以前の時代に、動的に変化する配列やデータ構造を扱うアルゴリズムが非常に多い。
本はガベージコレクションや Lisp リストの実装へと丁寧につながっていき、Knuth に期待する百科事典的な知識がそのまま詰まっている。
特に好きな例は、2つの配列が1つの領域を動的に共有する方法だ。1つの配列を
location#0から前方へ伸ばし、2つ目の配列をlocation#Endから後方へ伸ばせば、静的に割り当てられた領域を効率よく分け合える。任意個数の配列にも拡張できるが、そのくらいになると単に
MallocとReallocを使うほうがよく、その手法自体も malloc 風のルーチンにかなり近い。挿入や貼り付けではデータを押し出す必要がなかったが、移動時には必要だった。それでもうまく動いていた。
それだけ確保できなければ推奨値より小さく取り、最小値すら得られなければ起動に失敗した。
システムはその物理 RAM 断片の下側にヒープとライブラリを、上側にスタックを配置していたと記憶している。
System 8 あたりで仮想化レイヤーが追加され、このアプローチの必要性は薄れ、MacOS X の時期には他のシステムと同様にページングメモリを使うようになって、こうした曲芸はもはや不要になった。
それでも、Art of Computer Programming のこうした「妙な裏技」が、複数の同時実行アプリの RAM 割り当て方式だった時代を思い出すと面白い。
一方は上向きに伸び、もう一方は下向きに伸びた。魅力的な構造だったが、約束された性能は結局発揮できなかった。
固定サイズページ内でオフセット配列は前方に伸び、可変長の行値配列は末尾から後方に伸びる。行を削除すると、後方の配列には穴ができることがあると理解している。
ドキュメントが B-tree 構造そのものについて TAOCP を引用しているので、直接の着想源だったとしても驚かない。
ALGOL に再帰関数を入れることはかなり論争的で、面白い逸話として残っている: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - 2022年10月、コメント8件
How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - 2020年5月、コメント47件
How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - 2015年8月、コメント124件
How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - 2014年7月、コメント108件
SUBLEQマシン用のForthインタプリタ（https://github.com/howerj/subleq）と、ビットシリアルマシン用のインタプリタ（https://github.com/howerj/bit-serial）を書いたが、どちらにもForthに必要な関数呼び出しスタックがなかった
SUBLEQは間接ロード/ストアも許さないので、少しでも複雑なことをやるには自己書き換えコードが必要になる
どちらのマシンについても、そうした機能を実行できる仮想マシンを作り、協調的マルチスレッディングも入れるという方針で取り組んだ
ヒープが必要ならForthで書き、浮動小数点ワードセットもForthで書く。多くのMCUには今でも浮動小数点命令がなく、それを実装したソフトウェア関数呼び出しで処理できる
他のコンパイラも言及されてはいないが、似た方法を使っていたのだと思う。一部のBASICインタプリタもVMを実装してからそれをターゲットにしていたし、P-Codeも似ている
基本システムメモリの大半はビデオRAMで、ビデオチップのレジスタを
poke/peekする、かなり面倒な手順でアクセスしなければならなかったビデオチップは自動インクリメントされる現在メモリポインタを保持していて、連続読み出しや書き込みのときにポインタが1ずつ増えていったが、システムメモリの大部分がこの方法でしかアクセスできないという事実自体が、大きなプログラムを書くのを難しくしていた
そこでTIはGPLという抽象マシンを作り、このビデオRAMアクセスをより自然にした。ただしTMS9900上で解釈実行されるのでネイティブコードより遅く、CPUがビデオチップのRAMにアクセスできるタイミングも、水平/垂直帰線期間のようにチップが画面をスキャンアウトしていないときだけだったため、さらに遅かった
BASICのコードと変数もすべてこのビデオメモリ上にあったので、TI-99/4AのBASICインタプリタが何で書かれていたかも明らかだ。まったく速くなかった
興味深いのは、TMS9900には実際の汎用レジスタがなかった点だ。ワークスペースレジスタWR0〜WR15はメモリのどこかにあり、WPワークスペースポインタレジスタがそれを指していた
CPUの物理レジスタはPC、WP、ステータスレジスタの3つだけだった。結果として、非常に原始的なレジスタウィンドウ化ができ、
BLWP命令で分岐すると、メモリ上の別の場所にある新しい「レジスタ」集合が有効になり、戻りアドレスは新しいワークスペースに保存された最近TI-99/4Aの話をよくしているのは、個人プロジェクトでこの機種用のアセンブラを作っているからだ
一部のプロセッサがサブルーチンの最初の命令の直前のワードに戻りアドレスを保存していたという話は正しく、PDP-8がそうだった
PDP-8の進化は、再帰のためのハードウェア支援をめぐる歩みとも見なせる
最初は
JMS命令が関数の最初のワードに戻りアドレスを埋め込んでいた。呼び出し側がJMS命令の後ろに引数を置き、呼び出された側が戻り命令を基準にしたオフセットで引数を読みながら毎回インクリメントし、戻りアドレスが再びコード位置を指すようにすることも多かったその後は、自動インクリメント位置の1つを使って簡単なスタックを作る方式がかなり一般的になった。PDP-8にはポインタとして使うたびにインクリメントされるメモリ位置が8つあり、関数のプロローグ/エピローグがこのスタックを直接管理して、完全な再帰を可能にしていた
さらに後には、Harris 6120のようなマイクロプロセッサ実装にハードウェアスタックが追加され、性能が向上した
R命令、つまり戻りアドレス保存命令があったこの命令は、すでにインクリメントされた
PC+1を対象位置の命令アドレス部分に保存し、慣例上その対象はサブルーチン開始直前の無条件分岐命令だったR命令の後ろには、そのサブルーチンへ向かうU無条件分岐命令を置いたサブルーチンは自分の直前のアドレスへ分岐して戻り、そこには呼び出し地点の直後へ戻る無条件分岐が入っていた
より発展した呼び出し規約を使わない限り、再帰は不可能だった。そしてアセンブリ言語のすべての命令コードは1文字だった
AVR-8向けに書くプログラムでは、Cの呼び出し規約を使うのが正気ではないように感じることがある
アセンブリを使えば、内部ループ変数を大きなレジスタファイル内に保持し続けられるし、あるいは記事で説明されているような方式も使える
こうしたアプリで関数を「色分け」する方法もよい。赤い関数と緑の関数が同時にアクティブにならないと分かっていれば、両者のローカル変数やパラメータを再利用できる
以前参加したマイクロコントローラのコードベースのプロジェクトで、複数の開発者が何週間もかけて、いくつものサブシステムにまたがる捕まえにくいバグを追跡していた
コードを移動すると、バグも一緒に移動した。少し追跡してトラップを仕掛けてみると、呼び出しスタックが深くなりすぎて他のデータ構造を上書きしているコード箇所を見つけることができた
初めてプログラミングを学んだとき、まさにこういうやり方で強制的にプログラミングしていた。1970年代ではなく、2001年の話
最初のプログラミング体験が、ゲーム開発ツール RPG Maker 2000 に付属していた半グラフィカルなスクリプト「言語」だったから
RM2K のスクリプティングを見たことがないなら、Scratch と Emacs の Paredit モードを混ぜたものを想像するといい。例: https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
テキストのように見えるが、テキストのようには編集できず、プロパティダイアログ付きのブロックとしてしか編集できない
当然、RPG Maker のスクリプト言語にはスタックのような気の利いたものもなかった。再利用可能なサブルーチンが必要なら、引数用の秘密のグローバル変数を割り当てる必要があり、再入可能性はなかった
振り返ってみると、十分に意地を張れば RPG Maker 2000 の中にレジスタとランタイムスタックの両方を実装することもできた気がする
最初は簡単に見える。6502 の zero page のような偽の「レジスタ」を作れるし、間接変数アクセス（https://rpgmaker.net/tutorials/523/）でスタックも作れる
問題は、RM2K には「parallel process」スクリプトという形の並行性があること。この種の抽象化を並列プロセスが使うと、別々の「スレッド」が状態を好き放題上書きしてしまう
したがって「仮想コア」ごとに複数の zero page とスタックが必要で、各並列スクリプトに仮想コアを割り当て／バインド／スケジュールしなければならない。つまり各スクリプトが自分だけが知るスタックポインタを何らかの形で持つ必要がある
競合状態に対しても安定させるには、普通はミューテックスのようなものが必要になる
RPG Maker のゲーム開発者たちの執念を考えると、誰かがランタイム機能の一つをだましてミューテックスのように動かす方法を見つけていそうだが、実際に何をしたのかは正直知りたくないくらい怖い
rpgmaker.net で custom battle system が実装されたゲームをダウンロードした記憶がある。内蔵の戦闘システム全体を、あなたが説明したような手法で置き換えた実装だった
エディタで開いて仕組みを見たとき、完全に圧倒された。数百個の「変数」があり、記憶が正しければ i64 だけが許されていて、数百個の「スイッチ」もあった。スイッチはブール値だった
当時はスタック、ヒープ、関数呼び出しのような概念はまったくなかった
それを作って保守／デバッグするのにどれほどのエネルギーがかかったのか、想像もつかない
記憶が正しければ、ZX81 で BASIC プログラムを書くときは「スタックなし」に近い方法で書いていた
1 GOTO 3010 LET C = A + B20 RETURN30 LET A = 140 LET B = 250 GOSUB 1060 LET A = C70 LET B = 380 GOSUB 1090 PRINT CRUN6記事でコンパイラがやっていることを、自分でやっていたわけだ。行番号はメモリアドレスであり、隠れた変数は自分には隠れていなかった。自分がコンパイラだったから
インタプリタがやってくれた唯一のことは、
GOSUBの戻りアドレスを保存することだったただし、コードは文法的に間違っているかもしれないし、記憶が歪んでいるかもしれない。40年は長い時間だが、全体的なアイデアは合っている
それに、マシン内の Z80 プロセッサにはスタック管理機能があった。BASIC インタプリタは本当に単純だったが、言い訳はある。RAM 1KB と、OS・インタプリタ・すべてを収めた ROM 8KB しかなかった
GOSUBはRETURNが参照する行番号やその他の参照を保存し、GOSUB呼び出しをネストすると複数の戻り先を覚えておく必要があるので、何らかの形でスタックが必要になるただし一部の BASIC には汎用スタックではなく、戻りポインタの固定配列と現在位置のインデックスだけがあり、たとえば呼び出し深さが 7 に固定されるようなものだった。プログラマから見ると呼び出しスタックのように動作する
もちろん、誰かがスタックと言うときに期待しそうな、ローカル変数／引数のある「ちゃんとした」スタックではない
BBC BASIC の標準環境では、ネスト呼び出しや再帰を含め、そのとき何が起こるかを見せる面白いデモができた。スタック位置をディスプレイメモリの最上部に設定し、そこに何も描かれないようにすると、処理が進むにつれてスタックが伸びていくのを見ることができた
画面解像度が低かったので、2バイトの戻りアドレスは画面モード 1 や 5 では太いピクセル 8 個に見えた。モード 2 では 4 個だが点滅色が入ってあまり良くなく、モード 0、3、4、6 では 16 個だが、ビット単位で見るのは 8 色の繰り返しより判別しにくかった
任意に拡張できるヒープが存在する以前は、プログラマたちは少なくとも多少の工学的判断をしていた
入力の確率分布を考慮し、すべての中間保存領域のサイズを適切に決める必要があったから
それで「BUGS AND LIMITATIONS」が生まれた
だからすべてをコンパイル時に静的に割り当て、入力がどれだけのメモリを消費するかを知っておく必要がある
しかしメモリ消費の上限を把握することは、アプリケーションプログラマにとっても昔は普通のことだった。メモリ不足は絶対に避けたいから
最近は単にメモリ使用量を YOLO にしているのかもしれない
たとえば sed の最大コマンド長が有限で短い、といった制限があったことに比べれば大きな改善だった
関数型プログラミングを長くやりすぎて、再帰なしでどうコードを書くのか、本気で思い浮かべるのが難しい
再帰アルゴリズムを反復アルゴリズムに変える方法は技術的には知っているし、リソース制約の大きい環境でやったこともあるが、好きではない
たいていは再帰のほうがきれいで、99%の場合は十分速いと思う。コンパイラが末尾再帰をサポートしていれば100%に近いが、より興味深い作業の大半では、結局スタックを自分で管理しなければならない
ときどき、自分が生まれる前はどうしていたのかを学ぶために、わざとそういう作業をする。Commodore 64のゲームをたまにいじっているのだが、速くて安くて使いやすいハードウェアに慣れた今が、どれほど恵まれているかを強く感じる
そうした古いマシンで再帰をするには、スタック機構を自分で作る必要があり、それでもグローバルストレージ以外に基本的に使える手段がないため、対処すべき問題が残っていた
その時代を生きてきたが、誰にも勧めたくない
Enhanced GNU Awkの
@let機能では、関数の外、たとえばBEGINやENDブロック内の@letブロックについては、コンパイラが秘密のグローバル変数を割り当てるようにしていたこれらの変数は、ブロック間で可能な限り再利用される
$ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'$ cat awkvars.out$let0001: untyped variable$let0002: untyped variable$let0003: 1ARGC: 1ARGIND: 0ARGV: array, 1 elementsBINMODE: 0[ .. snip many ]https://www.kylheku.com/cgit/egawk/about/
pingも通らず、nc -z 104.37.63.7 443も通らない更新: セキュリティインフラが壊れているようだ。私はそれが何なのかも知らないし、Twitterも使っていない。ASを確認するとGoogle Fiberだった
それから、私の身元を特定するようなことはしないでほしい