古代世界におけるサブルーチン呼び出し: コンピューターがスタックやヒープを持つ前

 (devblogs.microsoft.com)
2 ポイント 投稿者 GN⁺ 2024-04-04 | 1件のコメント | WhatsAppで共有

コンピューターにスタックやヒープがなかった古代のサブルーチン呼び出し

  • 現代のコンピューティングではスタックやヒープを当たり前のものと考えるが、コンピューティング初期にはスタックやヒープなしでコンピューターが動作していた。
  • 動的メモリ割り当てなしのコンピューティングを想像するのはそれほど難しくない。あらゆるものに固定サイズのメモリバッファを使わなければならない。
  • 可変長データを扱う必要がある場合は、想定されるデータを収容できる十分に大きい固定サイズのバッファを確保する。
  • コンパイル時設定を用意してクライアントが最大容量を調整できるようにしたり、固定サイズバッファからメモリを「割り当て」「解放」できるカスタムアロケータを書いたりする。

スタックなしで関数を呼び出す

  • コンパイラは各関数の入力パラメータ、戻りアドレス、ローカル変数のために秘密のグローバル変数を定義する。
  • 関数呼び出しを生成するために、コンパイラはパラメータ値を対応する秘密のグローバル変数に代入し、戻りアドレスを関数の秘密の「戻りアドレス変数」に代入してから、関数の先頭へジャンプする。
  • 関数は秘密のグローバル変数からパラメータを読み取り、論理的にはローカル変数に相当する事前定義済みの秘密のグローバル変数を使う。
  • 関数が終わると、関数の秘密の「戻りアドレス変数」に入っているアドレスへジャンプする。

ABI の最適化

  • ABI を最適化するため、一部の値はグローバル変数ではなくレジスタで受け渡しする。
  • ほとんどのプロセッサは「リンク」レジスタと「リンク付き分岐」命令を備えており、「リンク付き分岐」命令の次のアドレスが自動的にリンクレジスタへ設定される。
  • 最初の 2 つのパラメータをレジスタで渡す呼び出し規約へ最適化する。

再帰呼び出しが不可能

  • 再帰呼び出しは動作しない。再帰呼び出しでは戻りアドレス変数が再帰呼び出しの戻りアドレスで上書きされるため、外側の呼び出しが完了したときに誤った場所へジャンプしてしまう。
  • 当時のプログラミング言語は再帰をサポートしないと宣言することで、この問題を解決していた。

ボーナス対話

  • 一部のコンパイラは自己書き換えコードを使ってさらに巧妙に動作した。特別な戻りアドレス変数は、実際には関数末尾のジャンプ命令のアドレスフィールドそのものだった。
  • プロセッサが間接ジャンプをサポートしていない場合、この方法は実用上の必要性として使われた。
  • サブルーチンの実用的価値が認識された後、多くのプロセッサはサブルーチン呼び出し命令を追加し、サブルーチンの最初のワードに戻りアドレスを保存し、サブルーチンの 2 番目のワードから実行を開始した。
  • サブルーチンから戻るために、サブルーチン開始ラベルを介した間接ジャンプを実行した。

GN⁺の意見

  • この記事は、初期コンピューティング時代にスタックやヒープが存在しなかったときのプログラミング方法を説明することで、現代のソフトウェア開発で使われているメモリ管理手法の発展を理解する助けになる。
  • スタックやヒープがなかった時代のプログラミング手法は、現代の開発者には非常に見慣れず非効率に見えるかもしれないが、コンピューティングの歴史を通じて技術がどのように発展してきたかを理解するうえで重要な背景知識を提供する。
  • 再帰呼び出しが不可能だった時代のプログラミング上の制約は、今日再帰的アルゴリズムを使う開発者にとって興味深い歴史的事実を提供する。
  • 批判的な視点で見ると、このような初期のプログラミング手法は、現代の複雑で多様な要求を満たすには非常に制約が大きかったことを示している。

関連記事

1件のコメント

 
GN⁺ 2024-04-04
Hacker Newsの意見

  • 『The Art of Computer Programming』という本への好意的な評価

    • この本は古く見えるが、ヒープ(heap)やスタック(stack)以前の、さまざまな動的配列やデータ構造を変更するアルゴリズムを扱っている。
    • 本書はガベージコレクションやLispリストの実装についても説明しており、Knuthならではの、期待を抱かせる百科事典のような知識を提供している。

  • 2つの配列が1つの領域を動的に共有する方法の説明

    • 1つの配列は位置 #0 から通常どおり成長し、もう1つは位置 #End から逆向きに成長するようにすることで、2つの配列が静的に割り当てられた領域を効率よく共有する。
    • この方法は複数の配列にも拡張できるが、その段階では Malloc と Realloc を使うほうがよいかもしれない。

  • ALGOL言語に再帰関数を導入することが議論を呼んだという面白い話へのリンクを紹介

    • 再帰がプログラミング言語にどのように導入されたのかという興味深い歴史を、そのリンクを通じて共有している。

  • SUBLEQマシンとビットシリアルマシン向けにForthインタプリタを書いた経験の共有

    • この2つのマシンは、Forthに不可欠な関数呼び出しスタックを持っていない。
    • SUBLEQ は間接ロードやストアを許可せず、通常とは異なる作業を行うために自己書き換えコードが必要になる。
    • 仮想マシンを構築してこれらの機能を実現し、協調的マルチスレッディングをサポートした。
    • 必要な場合、ヒープはForthで書かれ、ソフトウェア関数として実装された浮動小数点演算も含まれる。

  • PDP-8プロセッサのサブルーチン呼び出しに関する技術的進化の説明

    • 初期には JMS 命令が関数の最初のワードに返りアドレスを保存していた。
    • その後は自動インクリメント位置を使って単純なスタックを作り、関数のプロローグ/エピローグがこのスタックを手動で管理することで完全な再帰を可能にした。
    • さらに後にはハードウェアスタックがマイクロプロセッサ実装に追加され、性能が向上した。

  • 長年関数型プログラミングを経験してきたユーザーによる、再帰への好みの共有

    • 再帰アルゴリズムを反復アルゴリズムに変換する方法は知っているが、それでも再帰を好む。
    • ほとんどの場合、再帰は十分に高速であり、コンパイラが末尾再帰をサポートしていればなおさらである。
    • コモドール64のゲームをハックしながら、昔どのようにプログラミングが行われていたのかを学ぼうとしている。

  • 1991年ごろのRS232シリアルマルチプレクサ設計経験の共有

    • Z80プロセッサ、EPROM、Z80-SIOシリアルデバイスを使ったハードウェア設計。
    • スタックがなかったため、関数呼び出しのためにレジスタペアへ返りアドレスを事前にロードする方式を使っていた。

  • ヒープが拡張可能になる以前、プログラマが入力のあり得る分布を考慮し、中間ストレージのサイズを適切に設定しなければならなかった過去の状況への言及

    • これにより「バグと限界」が発生していた。

  • 再帰が使えなかった時代でも、末尾再帰は可能だったという説明

    • 最初の呼び出しに使われた branch_with_link 以外では、通常の分岐を使う必要があった。

  • Enhanced GNU Awk で、関数の外側にある @let ブロックに対してコンパイラが秘密のグローバル変数を割り当てる仕組みの説明

    • これらの変数は可能な限り再利用される。

  • 「Goto considered harmful」論文の世界を描いた投稿への言及

    • ほとんどの人は題名だけを知っているが、この論文はサブルーチンに単一の入り口を与えるべきだと主張している。
    • ときどきアセンブリコードを別のサブルーチンへ飛ばすように書くことはあるが、すべてのアセンブリコードがそうあるべきだとは思わない。