Articles

Subroutine

by admin

サブルーチンのアイデアは、計算機がすでにしばらく存在していた後に解決されました。算術命令と条件付きジャンプ命令は事前に計画されており、比較的変更されていませんが、プロシージャコールに使用される特別な命令は長年にわたって大マンチェスター・ベイビーやRCA1802のような初期のコンピュータやマイクロプロセッサは、単一のサブルーチン呼び出し命令を持っていなかった。サブルーチンは実装できますが、プログラマは各呼び出しサイトで一連の命令である呼び出しシーケンスを使用する必要がありました。

サブルーチンは1945年にコンラート-ズーゼのZ4で実装された。1945年、Alan M.Turingは、サブルーチンからの呼び出しと復帰の手段として、「bury」と「unbury」という用語を使用しました。

1947年、ジョン-モークリーはハーバード大学とアメリカ海軍兵器局の共同後援のもと、”大規模なデジタル計算機械のシンポジウム”で一般的なノートを発表した。 ここでは、

を示唆するシリアルおよび並列操作について説明します。..機械の構造は複雑な1ビットである必要はありません。 この手順に不可欠なすべての論理特性が利用可能であるため、マシンに知られている場所でサブルーチンをメモリに配置するための符号化命令を進化させ、それらを容易に使用することができるようにすることが可能である。

つまり、サブルーチンAを除算、サブルーチンBを複素乗算、サブルーチンCを一連の数値の標準誤差の評価など、特定の問題に必要なサブルーチンのリストを通じて指定することができます。 … これらのサブルーチンはすべてマシンに格納され、コーディングで示されているように、それらを番号で簡単に参照するだけです。

Kay McNultyはENIACチームでJohn Mauchlyと緊密に協力し、第二次世界大戦中にプログラミングしていたENIACコンピュータのサブルーチンのアイデアを開発しました。

Goldstineとvon Neumannは1948年8月16日付の論文を書いて、サブルーチンの使用について議論した。

IBM1620、Intel4004、Intel8008、PICマイクロコントローラなどの非常に初期のコンピュータやマイクロプロセッサの中には、専用のハードウェアスタックを使用してリターンアドレスを格納する単一命令サブルーチン呼び出しを持っているものもある。 1960年代半ば以前のマシン（UNIVAC I、PDP-1、IBM1130など）は、通常、呼び出されたサブルーチンの最初のメモリ位置に命令カウンタを保存する呼び出し規約を使用し これにより、任意の深いレベルのサブルーチンのネストが可能になりますが、再帰的なサブルーチンはサポートされません。 PDP-11(1970)は、スタックプッシュサブルーチン呼び出し命令を持つ最初のコンピュータの1つであり、この機能は任意の深いサブルーチンネストと再帰的なサブルーチンの両方をサポートしている。

言語supportEdit

非常に初期のアセンブラでは、サブルーチンのサポートは限られていました。 サブルーチンは互いに、またはメインプログラムから明示的に分離されておらず、実際にはサブルーチンのソースコードは他のサブプログラムのソースコードと いくつかのアセンブラは、呼び出しと戻りシーケンスを生成するために事前定義されたマクロを提供します。 1960年代までには、アセンブラは通常、インラインと別々にアセンブルされたサブルーチンの両方に対して、より洗練されたサポートを持っていました。

サブルーチンlibrariesEdit

この面倒なアプローチでも、サブルーチンは非常に有用であることが判明しました。 一つには、彼らは多くの異なるプログラムで同じコードを使用することができました。 さらに、メモリは初期のコンピュータでは非常に希少なリソースであり、サブルーチンはプログラムのサイズを大幅に節約できました。

多くの初期のコンピュータは、パンチされた紙テープからプログラム命令をメモリにロードしました。 各サブルーチンは、メインプログラム（または”メインライン”）の前または後にロードまたはスプライスされた別々のテープによって提供され、同じサブルーチン 同様のアプローチは、主な入力にパンチカードを使用したコンピュータに適用されます。 Subroutine libraryという名前は、もともと、文字通りの意味で、テープやカードデッキのインデックス付きコレクションを集合的に使用するためのライブラリを意

Return by indirect jumpEdit

自己修正コードの必要性を取り除くために、コンピュータ設計者は最終的に間接ジャンプ命令を提供しました。

これらのコンピュータでは、サブルーチンの戻りジャンプを変更する代わりに、呼び出し元のプログラムは戻りアドレスを変数に格納するため、サブルーチンが完了したときに、事前定義された変数で指定された場所に直接実行する間接ジャンプを実行します。

Jump to subroutineEdit

もう一つの進歩は、戻りアドレスの保存と呼び出し元のジャンプを組み合わせたjump to subroutine命令であり、オーバーヘッドを大幅に最小限に抑たとえば、IBM System/360では、プロシージャ呼び出し用に設計された分岐命令BALまたはBALRは、規則レジスタ14によって、命令で指定されたプロセッサレジスタにリターンアドレスを保存します。 戻るには、サブルーチンはそのレジスタを介して間接分岐命令(BR)を実行するだけで済みました。 サブルーチンが他の目的（別のサブルーチンを呼び出すなど）のためにそのレジスタが必要な場合は、レジスタの内容をプライベートメモリ位置またはレジスタスタックに保存します。

HP2100などのシステムでは、戻りアドレスがブランチのターゲットであったメモリ位置に格納されていることを除いて、JSB命令は同様のタスクを実 プロシージャの実行は、実際には次のメモリ位置から開始されます。 HP2100アセンブリ言語では、たとえば

 ... JSB MYSUB (Calls subroutine MYSUB.) BB ... (Will return here after MYSUB is done.)

と書いて、メインプログラムからMYSUBというサブルーチンを呼び出します。 サブルーチンは

 MYSUB NOP (Storage for MYSUB's return address.) AA ... (Start of MYSUB's body.) ... JMP MYSUB,I (Returns to the calling program.)

JSB命令は、次の命令（すなわちBB）のアドレスをオペランドとして指定された場所（すなわちMYSUB）に配置し、その後の次の場所（すなわちAA=MYSUB+1）に分岐した。 サブルーチンは、間接ジャンプJMP MYSUBを実行することにより、メインプログラムに戻ることができます。Iは、LOCATION MYSUBに格納されている場所に分岐します。

Fortranやその他の言語用のコンパイラは、利用可能な場合にこれらの命令を簡単に使用できます。 しかし、サブルーチンの戻りアドレス、パラメータ、戻り値には固定のメモリ位置が割り当てられていたため、再帰呼び出しはできませんでした。

ちなみに、同様の方法は、1980年代初頭にlotus1-2-3によって、スプレッドシート内の再計算の依存関係を発見するために使用されました。 つまり、リターンアドレスを格納するために、各セルに場所が予約されていました。 循環参照は自然な再計算順序では許可されていないため、これにより、IBM PCなどの小型コンピュータでは非常に限られていたメモリ内のスタック用のスペースを確保することなくツリーウォークが可能になった。

Call stackEdit

サブルーチン呼び出しの最新の実装では、サブルーチン呼び出しと戻りを実装するために、スタックデータ構造の特殊なケースであるコールスタ 各プロシージャ呼び出しは、スタックの先頭にスタックフレームと呼ばれる新しいエントリを作成します; プロシージャが戻ると、そのスタックフレームはスタックから削除され、そのスペースは他のプロシージャコールに使用されます。 各スタックフレームには、対応する呼び出しのプライベートデータが含まれており、通常はプロシージャのパラメータと内部変数、およびリターンアドレ

呼び出しシーケンスは、通常の命令のシーケンス（risc（reduced instruction set computing）やvery long instruction word（VLIW）アーキテクチャでまだ使用されているアプローチ）で実装することができますが、1960年代後半以降に設計された多くの伝統的なマシンには、その目的のための特別な命令が含まれています。

コールスタックは、通常、メモリの連続した領域として実装されます。 スタックがメモリ内で前方または後方に成長するように、スタックの一番下がこの領域内の最も低いアドレスまたは最も高いアドレスであるかどうかは、任意の設計上の選択である。; しかし、多くのアーキテクチャは後者を選んだ。

いくつかの設計、特にいくつかのForth実装では、主に制御情報（戻りアドレスやループカウンタなど）とデータ用の二つの別々のスタックを使用していました。 前者はコールスタックのように機能し、他の言語構造を介してプログラマが間接的にアクセスできるだけであったが、後者はより直接的にアクセスで

スタックベースのプロシージャ呼び出しが最初に導入されたとき、重要な動機は貴重なメモリを節約することでした。 このスキームでは、コンパイラは、各プロシージャのプライベートデータ(パラメータ、戻りアドレス、およびローカル変数)用にメモリ内の別々の領域を予約する必要はありません。 任意の時点で、スタックには、現在アクティブな呼び出しのプライベートデータのみが含まれています(つまり、呼び出されたがまだ返されていません)。 プログラムが通常ライブラリから組み立てられる方法のために、何千ものサブルーチンを含むプログラムを見つけることは珍しいことではありませんでしたが、そのうちのほんの一握りが任意の時点でアクティブになっています。 このようなプログラムの場合、コールスタック機構は大量のメモリを節約する可能性があります。 実際、コールスタックメカニズムは、自動メモリ管理のための最も早く、最も簡単な方法と見なすことができます。

ただし、コールスタックメソッドのもう一つの利点は、同じプロシージャへのネストされた呼び出しごとにプライベートデータの別々のインスタンスを取得するため、再帰的なサブルーチン呼び出しが可能であることです。

Delayed stacking Edit

コールスタックメカニズムの欠点の一つは、プロシージャ呼び出しとそのマッチングリターンのコストが増加することです。 追加コストには、スタックポインタのインクリメントとデクリメント(および、一部のアーキテクチャでは、スタックオーバーフローのチェック)、絶対アドレスではなく、フレーム相対アドレスによるローカル変数とパラメータへのアクセスが含まれます。 コストは、実行時間の増加、またはプロセッサの複雑さの増加、またはその両方で実現され得る。

このオーバーヘッドは、プロシージャ呼び出し自体を行わずに戻るリーフプロシージャまたはリーフ関数で最も明白で好ましくありません。そのオーバーヘッドを減らすために、多くの現代のコンパイラは、実際に必要になるまでコールスタックの使用を遅延させようとします。 たとえば、プロシージャPの呼び出しは、呼び出されたプロシージャの戻りアドレスとパラメータを特定のプロセッサレジスタに格納し、単純なジャンプ プロシージャPが他の呼び出しを行わずに戻った場合、コールスタックはまったく使用されません。 Pが別のプロシージャQを呼び出す必要がある場合は、Qが戻った後に必要なレジスタ(戻りアドレスなど)の内容を保存するためにコールスタックを使