オブジェクト指向プログラミングと開発環境 2007.11.15 2007年度担当　中井央

プログラム実行の様子 ユーザがプログラムを起動 OSはそれを受け取り、プログラムの実行を開始 プログラムが再帰関数呼び出しに対応　　するにはその仕組みが必要 実行時記憶 プログラムに割り当てられたメモリの使い方

実行時記憶 一般的な実行時記憶の割り当て方 目的コード、静的データ、実行時 スタック、ヒープからなる 目的コード、静的データ、実行時　　　スタック、ヒープからなる 実行時スタック、ヒープは実行の様子によって動的に使用領域が変化する 実行時スタックは関数呼び出しに　　対応する ヒープは動的なメモリ割当に使われる 実行時スタック ヒープ 静的データ 目的コード

再帰呼び出しの仕組み int fact(int n){ if (n < 2) return 1; else return n * fact(n - 1); } f(5) n * f(4) n * f(3) n * f(2) n * f(1) 1 n=5 n=4 n=3 n=2 n=1 n*1 = 2 n*2 = 6 n*6 = 24 n*24 = 120 それぞれの呼び出し における n を 覚えているから 計算ができる

再帰呼び出しの仕組み(2) 戻ってくるときには f(5) n は 1 になっている ので正しい答えが n=5 得られない!! n * f(4) n * f(3) n * f(2) n * f(1) 1 n=5 n=4 n=3 n=2 n=1 n*1 = 1 呼び出しごとに n が上書き されたら

再帰呼び出しの仕組み(3) スタックを使う それぞれの呼び出しの n を別々に保存 main f(5), n = 5 f(4), n = 4 呼び出しが終われば 割り当てられた領域は スタックから下ろされていく プログラムを間違えて 無限再帰を起こすと 使用できるメモリを 食いつぶしてしまう 図ではスタックは 下に伸びていく

入れ子型の関数宣言 C言語では許していない Pascal 他の言語ではサポート サンプルプログラムは次のスライド参照 １つ内側の関数は参照可能 それより内側は見えない 内側からはそれを囲む名前は参照可能

Pascal プログラムの例 sample.p 1 program test(input, output); 2 3 procedure a; 4 5 var x : integer; 6 7 procedure c; 8 begin 9 writeln('c'); 10 if 0 < x then 11 begin 12 x := x - 1; 13 c(); 14 end; 15 end; 16 begin 17 x := 3; 18 c(); 19 writeln('a'); 20 end; 21 22 procedure b; Begin 24 writeln('b'); 25 end; 26 27 begin 28 a(); 29 b(); 30 end.

活性レコード 関数呼び出し実現のためのスタックの要素 各関数呼び出しごとに割り当てられる 主な要素 活性レコードの割当＝活性化 実行時のスタックの変化の例は次のスライド 主な要素 返り値 引数 動的リンク 静的リンク 戻り番地 レジスタの退避場所 局所データ 一時的な値

実行時のスタックの変化の様子 (sample.p)

局所変数の値の参照 活性レコードは１つの関数呼び出しに対応 関数内で宣言された変数はそれに対応 する活性レコードに割り当てられる 関数内で宣言された変数はそれに対応　する活性レコードに割り当てられる 参照は活性レコード内の基準位置からのオフセットによる 関数aの固定領域の始まり 変数 x の領域 変数 y の領域 変数 z の領域 動的に変化する領域の始まり ： スタックトップ y の位置は基準から z の分＋yの分 戻った位置 基準

非局所変数の参照 入れ子の深さ (レベル) 内側からはその外側の名前は参照可能 どの活性レコードの値を参照すればよいか？？ 1 program test; 2 3 var x:integer; 4 5 procedure a; 6 procedure b; 7 procedure c; 8 begin 9 end; { c } 10 begin 11 end; { b } 12 begin 13 end; { a } 14 15 begin 16 end. 入れ子の深さ (レベル) メインを0, 入れ子が深くなるにつれ、１つずつ大きくなる 内側からはその外側の名前は参照可能 どの活性レコードの値を参照すればよいか？？ 1 2 3 たとえば c の中から a で宣言された変数を参照したい

入れ子型静的スコープでの関数呼び出しの性質 1 program test; 2 3 var x:integer; 4 5 procedure a; 6 procedure b; 7 procedure c; 8 begin 9 end; { c } 10 begin 11 end; { b } 12 begin 13 end; { a } 14 15 begin 16 end. 最初はメイン (レベル0) 呼び出しパターンは２通り 呼び出し側 p, 呼ばれた側 q とする p < q なら　q = p + 1 p ≧ q 外から内は １つ内側だけ 内から外は どのレベルでも OK

静的リンクの設定 a b c b c a→b→c→b→c と読んだ時の実行時スタック p<q の場合 p≧q の場合 a→b や b→c の場合：　　　呼び出しもとを指せばよい p≧q の場合 c→b や c→a などの場合：　呼び出しもと(直前の活性 レコード) から p-q+1 回静的リンクを辿ったところ a b c b c

関数の引数の渡し方 値渡し C 言語で関数を呼ぶ場合： f(n) を f(a)で 呼んでも、fの本体で n の値をいくら変えても呼び出しもとの a の値は変わらない 参照渡し 渡すのは、変数のアドレス C だと f(&a) のような形 変数の在処を渡すので、関数本体でその中身を書き換えれば、呼び出し元の変数の中身が書き変わる

関数呼び出し時の処理 呼び出す側の処理 呼ばれた側の処理 引数の評価、その値を適切な位置へ格納 呼び出される側の活性レコードに現在の　　活性レコードへのポインタを格納 静的リンクの設定 戻り番地の設定 呼び出される側へ制御を移す 呼ばれた側の処理 レジスタの退避 局所データの初期化 スタックトップの設定

関数呼び出しからの戻り時の処理 呼ばれた側 呼び出し側 返り値を所定の場所へ格納する 退避したレジスタの復元 スタックトップを呼び出しもとのトップへ戻す(保存しておいた活性レコードの復元) 呼び出し側 返り値を取り出す

他のフェーズとの関連 実行時環境に合うよう、意味解析等で情報を作っておく必要がある 変数の領域を計算するには型とそれに必要なサイズを計算しておく オフセットを計算する

Java についていくつか static がついた変数はプログラム実行中には一カ所だけ値の保存場所が用意される メソッド内のローカル変数はメソッド呼出しごとにスタックフレームに確保される オブジェクトは new の実行によりヒープに確保される 例外処理：例外発生時、catch できるところまでスタックをさかのぼる

その他 無限再帰をしたらどうなるか class Test2 { static void r(){ r(); } public static void main (String args[]){ % java Test2 Exception in thread "main" java.lang.StackOverflowError at Test2.r(Test2.java:3) ... 1024回の 呼出し後、停止

さらなる学習について 実行時環境の理解 プログラムの動作の理解 よりよいプログラム記述が可能 さまざまなプログラミング言語 and/or そのコンパイラの仕組みも知ろう!