PowerPoint プレゼンテーション

オブジェクト指向プログラミング
と開発環境
2007.11.15
2007年度担当中井央
プログラム実行の様子
• ユーザがプログラムを起動
• OSはそれを受け取り、プログラムの実行
を開始
• プログラムが再帰関数呼び出しに対応
するにはその仕組みが必要
• 実行時記憶
– プログラムに割り当てられたメモリの使い方
実行時記憶
• 一般的な実行時記憶の割り当て方
– 目的コード、静的データ、実行時
目的コード
スタック、ヒープからなる
– 実行時スタック、ヒープは実行の様子静的データ
によって動的に使用領域が変化する実行時スタック
– 実行時スタックは関数呼び出しに
対応する
– ヒープは動的なメモリ割当に使われる
ヒープ
再帰呼び出しの仕組み
f(5)
int fact(int n){
if (n < 2) return 1;
else return n * fact(n - 1);
}
n*24 = 120
n=5
n * f(4)
n*6 = 24
それぞれの呼び出し
における n を
覚えているから
計算ができる
n=4
n * f(3)
n*2 = 6
n=3
n * f(2)
n*1 = 2
n=2
n * f(1)
1
n=1
1
再帰呼び出しの仕組み(2)
f(5)
戻ってくるときには
n は 1 になっている
ので正しい答えが
得られない!!
n*1 = 1
n=5
n * f(4)
n*1 = 1
n=4
n * f(3)
n*1 = 1
n=3
n * f(2)
呼び出しごとに
n が上書き
されたら
n*1 = 1
n=2
n * f(1)
1
n=1
1
再帰呼び出しの仕組み(3)
• スタックを使う
main
f(5), n = 5
f(4), n = 4
f(3), n = 3
f(2), n = 2
それぞれの呼び出しの
n を別々に保存
呼び出しが終われば
割り当てられた領域は
スタックから下ろされていく
f(1), n = 1
図ではスタックは
下に伸びていく
プログラムを間違えて
無限再帰を起こすと
使用できるメモリを
食いつぶしてしまう
入れ子型の関数宣言
• 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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
begin
x := 3;
c();
writeln('a');
end;
procedure b;
Begin
writeln('b');
end;
begin
a();
b();
end.
活性レコード
• 関数呼び出し実現のためのスタックの要素
• 各関数呼び出しごとに割り当てられる
– 活性レコードの割当＝活性化
– 実行時のスタックの変化の例は次のスライド
• 主な要素
•返り値
•引数
•動的リンク
•静的リンク
•戻り番地
•レジスタの退避場所
•局所データ
•一時的な値
実行時のスタックの変化の様子
(sample.p)
QuickTimeý Ç²
TIFF (LZW) êLí£ÉvÉçÉOÉâÉÄ
ÅB
Ç™Ç±ÇÃÉsÉNÉ`ÉÉÇ¾ å©ÇÈÇ žÇ½Ç …ÇÕïKóvÇÇ•
局所変数の値の参照
• 活性レコードは１つの関数呼び出しに対応
• 関数内で宣言された変数はそれに対応
する活性レコードに割り当てられる
• 参照は活性レコード内の基準位置からの
オフセットによる関数aの固定領域の始まり
y の位置は基準から
z の分＋yの分
戻った位置
変数 x の領域
変数 y の領域
変数 z の領域
動的に変化する領域の始まり
：
スタックトップ
基準
非局所変数の参照
• 入れ子の深さ (レベル)
– メインを0, 入れ子が深くなるに
つれ、１つずつ大きくなる
• 内側からはその外側の名前
は参照可能
• どの活性レコードの値を参照
すればよいか？？
0
1
2
3
4
1
5
6
2
7
3 8
9
10
11
12
13
14
15
16
たとえば c の中から
a で宣言された変数を参照したい
program test;
var x:integer;
procedure a;
procedure b;
procedure c;
begin
end; { c }
begin
end; { b }
begin
end; { a }
begin
end.
入れ子型静的スコープでの関数
1 program test;
呼び出しの性質
2
• 最初はメイン (レベル0)
• 呼び出しパターンは２通り
– 呼び出し側 p, 呼ばれた側 q と
する
– p < q なら q = p + 1
– p≧q
内から外は
どのレベルでも
OK
外から内は
１つ内側だけ
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var x:integer;
procedure a;
procedure b;
procedure c;
begin
end; { c }
begin
end; { b }
begin
end; { a }
begin
end.
静的リンクの設定
• a→b→c→b→c と読んだ時の実行時スタッ
ク
• p<q の場合
a
b
c
b
c
– a→b や b→c の場合：
呼び出しもとを指せばよい
• p≧q の場合
– c→b や c→a などの場合：
呼び出しもと(直前の活性
レコード) から p-q+1 回静的
リンクを辿ったところ
関数の引数の渡し方
• 値渡し
– C 言語で関数を呼ぶ場合： f(n) を f(a)で
呼んでも、fの本体で n の値をいくら変えても
呼び出しもとの a の値は変わらない
• 参照渡し
– 渡すのは、変数のアドレス
– C だと f(&a) のような形
– 変数の在処を渡すので、関数本体でその中身
を書き換えれば、呼び出し元の変数の中身が
書き変わる
関数呼び出し時の処理
•
呼び出す側の処理
1. 引数の評価、その値を適切な位置へ格納
2. 呼び出される側の活性レコードに現在の
活性レコードへのポインタを格納
3. 静的リンクの設定
4. 戻り番地の設定
5. 呼び出される側へ制御を移す
•
呼ばれた側の処理
1. レジスタの退避
2. 局所データの初期化
3. スタックトップの設定
関数呼び出しからの戻り時の処理
•
呼ばれた側
1. 返り値を所定の場所へ格納する
2. 退避したレジスタの復元
3. スタックトップを呼び出しもとのトップへ戻す
(保存しておいた活性レコードの復元)
•
呼び出し側
•
返り値を取り出す
他のフェーズとの関連
• 実行時環境に合うよう、意味解析等で情報
を作っておく必要がある
– 変数の領域を計算するには型とそれに必要な
サイズを計算しておく
– オフセットを計算する
Java についていくつか
• static がついた変数はプログラム実行中に
は一カ所だけ値の保存場所が用意される
• メソッド内のローカル変数はメソッド呼出し
ごとにスタックフレームに確保される
• オブジェクトは new の実行によりヒープに
確保される
• 例外処理：例外発生時、catch できるところ
までスタックをさかのぼる
その他
• 無限再帰をしたらどうなるか
class Test2 {
static void r(){
r();
}
public static void main
(String args[]){
r();
}
}
% java Test2
Exception in thread "main"
java.lang.StackOverflowError
at Test2.r(Test2.java:3)
at Test2.r(Test2.java:3)
at Test2.r(Test2.java:3)
at Test2.r(Test2.java:3)
...
1024回の
呼出し後、停止
さらなる学習について
• 実行時環境の理解
• プログラムの動作の理解
• よりよいプログラム記述が可能
• さまざまなプログラミング言語 and/or その
コンパイラの仕組みも知ろう!

Download Report