Microsoft PowerPoint L07-Imperative Programming Languages-4-students ( )

Transcription

1 プログラミング言語論 A (Concepts on Programming Languages) 趙建軍 (Jianjun Zhao) 1 第 7 回 命令型言語 (4) (Imperative Programming Languages) 手続き ( 関数 ) の呼び出し

2 今日の講義 手続きとは 手続きの定義 引数渡し スコープ規則 3 今日の講義 手続きとは 手続きの定義 引数渡し スコープ規則 4 2

3 手続きとは プログラムの一部に名前を付けるものである その部分のことを手続きの本体という 手続きが呼ばれると 手続きの本体が実行される この手続きの本体の実行のことを手続きの activation という 関数 (function) は 値を返す手続きのことである 関数 手続きという用語を区別をしないで用いる場合もある 5 手続きとは 手続き : 一連の処理を行う機能単位 名称 サブルーチン (subroutine) 言語 FORTRAN, Basic 手続き (procedure) 関数 (function) メソッド (method) Pascal C, C++, Go Java 手続き ( 関数 ) が名前をつけることができ, その名前で何度でも呼び出すことができる 6 3

4 手続きとは 手続きの必要性 システムの大規模化 複雑化 要求機能を より簡素化された複数の機能に分解し 各々を手続きとして実装する これらを組み合わせて全体を実現 = モジュール化 7 手続きの構文 手続きの定義 < 手続き名 > ( < 仮引数列 > ) 手続きにおける引数は仮引数 (formal parameter) と呼ばれる 手続き呼び出しにおいて 引数が 0 個でも括弧が必須の場合が多い C, Modula-2 など Pascal では引数がない場合は括弧を書かない 8 4

5 手続きの構文 手続き呼び出し文の構文 < 返り値の型名 > < 手続き名 > ( < 実引数列 > ) 手続き呼び出し文における引数は実引数 (actual parameter) と呼ばれる 9 手続きの呼び出し 10 5

6 関数の戻り値 11 手続き呼び出しの例 int plus(int z, int y) { int d = 0; while (d < y) { z++; d++; return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, y); c++; 関数 plus の定義 ( 関数宣言 ) 関数 plus の呼出し 12 6

7 手続きの型 int plus(int z, int y) { int d = 0; while (d < y) { z++; d++; return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, y); c++; すべての関数は型を持つ 関数定義と呼出し側で型が一致してなければならない 13 値を返さない手続き 値を返さない手続きは以下のように定義する Java, C, C++: 戻り値を void に VB: サブルーチンプロシージャとして定義 例 void sample(int x) { x:= x+1: printf( %d n, x); main() { sample(9); 式として扱われない ( 値を評価できない ) 14 7

8 再帰呼び出し (1) 関数の中で関数を呼出すことが可能 main() { printf( %d n, max3(12, 15, 11)); int max3(int x, int y, int z) { return max2(max2(x, y), z); int max2(int x, int y) { if (x >= y) return x; else return y; 15 再帰呼び出し (2) 関数の中で自分自身を呼び出す int factorial(int x) { if (x == 1) { return 1; else { return x * factorial(x 1); 16 8

9 今日の講義 手続きとは 手続きの定義 引数渡し スコープ規則 17 引数 (parameters) 仮引数 (formal parameters) と 実引数 (actual parameters) 仮引数と実引数の対応付け その位置によって対応付ける : positional parameters 仮引数の名称を指定 : keyword parameters 引数に関するその他のしくみ デフォルト値を持つ引数 仮引数と実引数の個数が異なる実引数が足らない 未定義を許す実引数があまる 複数の実引数をリストにしてまとめて1つの仮引数に対応づけるその個数を与える 18 9

10 引数結合方法 C 言語での引数結合の例 宣言 int func(int x, double y) { 呼び出し func( n, x ); 19 引数渡しの原理 実引数を仮引数に渡す方式には複数ある 引数の渡し方式 Call-by-value ( 値呼び 値渡し ) Call-by-reference ( 参照呼び 参照渡し ) Call-by-name ( 名前呼び 名前渡し ) どのように引数を渡すのですか? via. the stack via. the registers or a combination 20 10

11 値呼出し (call-by-value) 仮引数には実引数の評価結果の値が渡される 1. 実引数の値を求める 2. 仮引数は 手続き内の局所変数として生成する 3. 実引数の値をその変数の初期値とする 4. 手続きの本体を実行する 手続き内で局所変数の内容が変化しても 呼出し側に影響しない 局所変数の生成と値のコピーの必要がある 21 値呼出し (call-by-value) C 言語は 値呼出しの機能のみである 例 宣言 int func(int x, double y) { 呼出し func( n, x ); 22 11

12 参照呼出し (call-by-reference) 仮引数には実引数のアドレスが渡される ( 渡されたアドレスが仮引数のアドレスとなる ) 仮引数への変更は 実引数に反映するので 結果を返すためとして使える 局所変数の生成 コピーの必要がない 実引数は変数等であり 式は許されない 変数の衝突に注意が必要 変数呼出し (call by variable) ともいう 23 名前呼出し (call-by-name) 手続きの本体の中の仮引数を実引数の式で置き換えて実行する この置き換えで名前の衝突が起こる場合は 名前の付 け替えを行う 1. 手続きの本体にある仮引数を 対応する実引数の式で置換する 2. ただし これによって手続き内の局所変数と衝突する場合は 局所変数の名前の付け替えをする 3. できあがった手続き本体を 手続き呼出しのところに挿入する 4. ただし この挿入によって手続き内の大域変数が呼出し側の局所変数と衝突する場合は呼出し側の局所変数を付け替える 5. そのまま実行する 名前の衝突 実引数と手続き内の局所変数との衝突手続き内の大域変数と呼出し側の局所変数の衝突 24 12

13 名前呼出しの例 呼出しプログラム begin integer i, n; n:=n+1; p(a[i]) end; proc p(x) begin integer i; x:=x+i+n end; 1 手続き p 本体の仮引数 x を実引数 A[i] で置換 begin integer i; A[i]:=A[i]+i+n end; 4 手続き内の大域変数 n が呼出し側の局所変数と衝突するので 名前の付け替え 2 i が衝突するので局所変数を j に付け替え begin integer j; A[i]:=A[i]+j+n end; begin integer i, m; m:=m+1; begin integer j; A[i]:=A[i]+j+n end; end; 3 呼出し箇所に手続きを挿入 begin integer i, n; n:=n+1; begin integer j; A[i]:=A[i]+j+n end; end; 25 引数渡しと評価方式 引数渡しの方式は式の評価方式と関係する例 p(x,y,z) begin if X>0 then Y else Z end; において 呼出し p(f(x), g(x), h(x)) を考える 参照渡しでは こうした呼出しはできない 値渡しでは f(x), g(x), h(x) を計算し その値を渡す 名前渡しでは f(x), g(x), h(x) をそのまま式として渡し 置換されたプログラムを実行する 26 13

14 今日の講義 手続きとは 手続きの定義 引数渡し スコープ規則 27 プログラミング言語の構成要素 コード (code) Procedures Control Flow Statements Data Access データ (data) Global Static Variables Global Dynamic Data Local Variables Temporaries Parameter Passing Read-only Data 28 14

15 プログラムのメモリレイアウト 各プログラムに割り当てられるメモリの領域は以下のようになっている 0xffff 番地 1 プログラムに割り当てられる領域 ヒープ領域スタック領域静的領域プログラム領域 領域が増減する 書き換え不可能 0x0000 番地 29 各領域の説明 プログラム領域 (program) プログラムの実行コード ( 機械語 ) が格納される 静的領域 (static) プログラムが持つ定数などが格納される char *a = This is a string. ; printf( Hello World!! ); ヒープ領域 (heap) 大域変数が格納される スタック領域 (stack) 自動変数, 関数の引数, 戻り番地などが格納される 30 15

16 自動変数 関数呼出し, ブロック開始時に生成される 関数からの復帰, ブロック終了時に消滅する スタック領域上に確保される main () { int i, j; func(); func() { int x, y; main の中でのみ使用可能 main を抜けると消滅 func の中でのみ使用可能 func を抜けると消滅 31 静的変数 自動変数と同様, 宣言した関数内でしか見れない 関数からの復帰時に消滅せず値が保持される ヒープ領域に確保される main () { int i, j; tick(); tick(); 静的変数であることを示す記憶指定子 tick() { static int count = 0; count++; func の中でのみ使用可能次回呼出し時に値が残っている 32 16

17 大域変数 ( 外部変数 ) 関数の外で宣言する 複数の関数で値を共有できる プログラム実行中消滅しない ヒープ領域に確保される int i, j; main () { i = 1; j = 2; func(); func() { printf( [%d,%d], i, j); main でも func でも使用可能消滅しない [1,2] が表示される 33 有効範囲 ( スコープ, scope) 名前 ( 変数名 手続き名等 ) とその束縛に対し その名前でその束縛が参照されるとき その名前は可視 (visible) という ある名前が可視であるプログラムの範囲をスコープ (scope) という 34 17

18 有効範囲 ( スコープ ) コープ規則 : 1. ある手続きを実行中に変数 x が表れたとき x の宣言がその手続きにあるならば この宣言が x の束縛を決める 2. その手続きにないなら この手続きを定義している手続き ( 親手続き ) の中に宣言を探す そこにあれば その宣言が束縛を決める 3. さらに そこになければ その親 35 有効範囲 ( スコープ ) 通常のスコープの規則 静的スコープ規則 (static scope rule) 静的スコープ規則は プログラムによって予め決められる規則である プログラムの字面で決まるので lexical scope rule ともいう 逆に プログラムのある箇所での束縛の全体を環境 (environment) という 36 18

19 変数のスコープと寿命 スコープ : その変数を見れる範囲 寿命 : その変数に値が保持されている期間 スコープ 寿命 自動変数関数内プログラムの全実行 静的変数関数内プログラムの全実行 大域変数プログラム全体プログラムの全実行 37 スコープと可視性 別々のスコープで同じ名前を使用できる 名前が衝突したときは, 内側のスコープを優先 int i, j; main () { func1(); func2(); func1() { int i, j; func2() { int i, j; main 内における i, j func1 内における i, j func2 内における i, j 38 19

20 手続きのスコープ関係 main var x proca var y procb var z (procb 本体 ) procc var u (procc 本体 ) (proca 本体 ) procd var v proce var w (proce 本体 ) (procd 本体 ) (main 本体 ) 各手続き本体で可視の名前 : main: proca, procd, 変数 x proca: proca, procb, procc, 変数 x, y procb: proca, procb, 変数 x, y, z procc: proca, procb, procc, 変数 x, y, u procd: proca, procd, proce, 変数 x, v proce: proca, procd, proce, 変数 x, v, w その手続きの本体で 名前が可視であれば手続きは呼べる 自分よりも後ろのものは通常可視でない 39 スタック領域の詳細 関数呼出しに応じてスタック領域が確保される 0xffff 番地 main () { int x = 1; x = input(x); int input(int y) { char s[10]; scanf( %s, s); printf("%s n", s); return y + 1; x : y 戻り番地 : s[1] s[0] 引数用 20 バイト 自動変数用 28 バイト 0x0000 番地 main 用 input 用 40 20

21 バッファオーバーフロー攻撃 scanf などで戻り番地を上書きする 戻り番地は 29~32 文字目 0xffff 番地 main () { int x = 1; x = input(x); int input(int y) { char s[10]; scanf( %s, s); printf("%s n", s); return y + 1; x : y 戻り番地 : 不正なコード s[1] s[0] 引数用 20 バイト 自動変数用 28 バイト 0x0000 番地 main 用 input 用 41 21