オブジェクト指向言語論 第三回 知能情報学部 新田直也

最小プログラミング言語 構造化プログラミングから手続き呼び出しを取ったもの． Whileプログラム(D.M.Ritchie, C言語の作者) 単純だが，どんな計算でもできることが理論的に証明されているプログラム言語 (チューリングマシンと等価，計算万能) プログラム理論の研究で使われる． 例) 表示意味論(denotational semantics)，プログラム検証 制御構造として，連接，判断(if文)，前判定反復(while文のみを持つ) →構造化定理参照

Whileプログラムの構文 自然数(0を含む)を表す有限個の変数を持つ． 代入文は以下の3通りのみ． 条件式は以下の1通りのみ． 変数 = 0; 変数 = 変数; 変数++; (変数 = 変数 + 1;) 条件式は以下の1通りのみ． 変数 < 変数 プログラムは再帰的に以下のように構成される． プログラム ::= 代入文 または プログラム プログラム または if (条件式) { プログラム } else { プログラム } または while (条件式) { プログラム }

Whileプログラムの例(加算) z = x + y の計算 z = x; c = 0; while (c < y) { z++; }

Whileプログラムの例(減算) z = y - x の計算 z = 0; c = x; while (c < y) { z++; }

Whileプログラムの例(乗算) z = x * y の計算 z = 0; c = 0; while (c < y) { d = 0; while (d < x) { z++; d++; } c++;

手続き 手続き：一連の処理を行う機能単位． FORTRAN, Basic --- サブルーチン Pascal --- プロシージャ(手続き) C, C++ --- 関数 Java --- メソッド 名前をつけることができ，その名前でさまざまな場所から何度でも呼び出すことができる（処理の再利用） ． C言語では関数として扱われる．

手続きの有効性 z = x * y を行うWhile プログラム z = 0; c = 0; while (c < y) { int plus(int z, int x) { int d = 0; while (d < x) { z++; d++; } return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, x); c++; z = 0; c = 0; while (c < y) { d = 0; while (d < x) { z++; d++; } c++;

手続きの定義と呼び出し int plus(int z, int y) { int d = 0; while (d < y) { } return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, y); c++; 関数plusの定義(関数宣言) 関数plusの呼出し

手続きの引数と戻り値 int plus(int z, int y) { int d = 0; while (d < y) { z++; } return z; main() { int z = 0; int c = 0; while (c < x) { z = plus(z, x); c++; 仮引数：定義側の引数 戻り値 実引数：呼出し側の引数

手続きの定義と呼び出しの考え方(1/3) 高校の数学を思い出そう． 関数f(x)が以下のように定義されているとき， f(x) = x2+3x+2 f(3)の値は? f(5)の値は? これらの値が計算できるのなら，プログラミング言語における手続き呼び出しの仕組みもわかるはず． int f(int x) { return (x * x + 3 * x + 2); } main() { printf(“%d, %d\n”, f(3), f(5));

手続きの定義と呼び出しの考え方(2/3) 数学の関数とプログラミング言語の関数の考え方は基本的に同じ． f(x) = x2+3x+2 f(3)の3およびf(5)の5は，実引数である． 関数呼び出し時に実引数の値が仮引数に代入される． 関数呼び出しは値を持ち，計算結果がその値になる． 関数定義（関数宣言） 関数呼び出し(値は20になる) 関数呼び出し(値は42になる)

手続きの定義と呼び出しの考え方(3/3) より複雑な場合も同様． 内側の式から先に評価される． f(x) = x2+3x+2 f(f(3))の値は? 内側の式から先に評価される． f(3) = 32+3*3+2 = 20 f(f(3)) = f(20) = 202+3*20+2 = 462

手続きの型 int plus(int z, int *y) { int d = 0; while (d < *y) { z++; } return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, &x); c++; すべての関数は型を持つ． 関数定義と呼出し側で型が一致 してなければならない．

前方参照とプロトタイプ宣言 プロトタイプ宣言 後方参照 前方参照 int plus(int z, int x) { int d = 0; while (d < x) { z++; d++; } return z; main() { int z = 0; int c = 0; while (c < y) { z = plus(z, x); c++; int plus(int, int); main() { int z = 0; int c = 0; while (c < y) { z = plus(z, x); c++; } int plus(int z, int y) { int d = 0; while (d < y) { z++; d++; return z; プロトタイプ宣言 後方参照 前方参照

再帰呼び出し(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; }

再帰呼び出し(2) 関数の中で自分自身を呼び出すとどうなるか？ int factorial(int x) { if (x == 1) { return 1; } else { return x * factorial(x – 1); } }