2011/02/24

スタックが無かった頃のお話

Abstract Heresies: Where did the stack go?

The IBM 704 didn't have a stack.

This was not unusual at the time. Although stacks were known about for years before, low-level languages did not make much use of them. Early FORTRAN certainly didn't need a stack, so IBM didn't bother with a hardware implementation.

• IBM704にはスタックが無かった。
• TSXというインストラクションで、現在のプログラムカウンタの値をレジスタに置いてサブルーチンにジャンプすることができた。
• でも、レジスタに置いたアドレスへとジャンプする、いわゆる間接ジャンプをするインストラクションが無かった。
• どうしていたかというと、
  • サブルーチンの最後に無条件ジャンプ命令を置いておく
  • サブルーチンに飛び込んだ時点で、レジスタに呼び出し元のプログラムカウンタの値が入ってるので、それを元に最後の無条件ジャンプ命令の飛び先アドレスを書き換える。

自己書き換えだ。楽しいなあ。

もちろんこれは再入可能じゃない。再入可能にするにはどうしたかというと スタックを自分で作らないとならないのだけれど、当時はメモリアクセスに 比べて演算のコストが高く、スタックポインタを増減させるやり方は重かった。 リンクトリストなら加減算が不要で、しかもあらかじめ貴重なメモリの一部を スタック用に予約する必要がないので、そちらが好まれたとのことだ。

スタックがリンクトリストだと継続の実装も簡単なんだよね。 現代のアーキテクチャではアクセスのローカリティの重要性がとてつもなく大きいので 今使うことは無いだろうけれど… 通常のスタックエリアをNurseryのアロケータとみなして、適宜スタックエリアの ガベージコレクションを行う、という形でSpaghetti Stackを実装することは 今でもできるな。

Tag: Programming