プログラミング言語論 第9回 Hoare論理の練習問題 手続きの引数機構 変数の有効範囲

Slides:



Advertisements
Similar presentations
プログラミング 関数編 情報科学科. プログラミングにあたって C 言語では、 main 内に処理を記述 1000 行になるような大きなプログラムでは、 プログラム全体が何をしているのかを把握 することが困難になる 他人が見ると非常に理解しにくい 作成者であっても時が経てば内容を忘れて、他 人が見た時と同じ状況になる.
Advertisements

2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第5回 関数(1) 情報・知能工学系 山本一公
プログラミング入門2 第4回 配列 for文 変数宣言 初期化
プログラミング言語論プログラミング言語論 命令型プログラミング言語 水野嘉明
情報基礎演習B 後半第5回 担当 岩村 TA 谷本君.
プログラミングパラダイム さまざまな計算のモデルにもとづく、 プログラミングの方法論 手続き型 関数型 オブジェクト指向 代数 幾何.
プログラミング入門2 第10回 構造体 情報工学科 篠埜 功.
プログラミング入門2 第10回 構造体 情報工学科 篠埜 功.
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
情報処理Ⅱ 2005年12月9日(金).
プログラミング言語論 第4回 手続きの引数機構 変数の有効範囲
条件式 (Conditional Expressions)
第4回放送授業.
プログラミング入門2 第2回 複合文、繰り返し 情報工学科 篠埜 功.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
関数 関数とスタック.
プログラミング言語入門 手続き型言語としてのJava
プログラミング2 関数
プログラミング論 ファイル入出力
関数とポインタ 値呼び出しと参照呼び出し swapのいろいろ 関数引数 数値積分
細かい粒度で コードの再利用を可能とする メソッド内メソッドと その効率の良い実装方法の提案
B演習(言語処理系演習)第8回 評価器 田浦.
暗黙的に型付けされる構造体の Java言語への導入
関数の定義.
第10回関数 Ⅱ (ローカル変数とスコープ).
Cプログラミング演習 第7回 メモリ内でのデータの配置.
プログラミング入門2 第8回 ポインタ 情報工学科 篠埜 功.
アルゴリズムとデータ構造 補足資料5-2 「サンプルプログラムsetop.c」
プログラミング入門2 第11回 情報工学科 篠埜 功.
第9回関数Ⅰ (簡単な関数の定義と利用) 戻り値.
プログラミング入門2 第11回 情報工学科 篠埜 功.
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 補足資料5-1 「メモリとポインタ」
プログラミング論 ファイル入出力
プログラミング言語論 第5回 手続きの引数機構 変数の有効範囲
オブジェクト指向プログラミングと開発環境
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
メモリとメモリアドレス, ポインタ変数,関数へのポインタ渡し
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
情報とコンピュータ 静岡大学工学部 安藤和敏
プログラミング入門2 第9回 ポインタ 情報工学科 篠埜 功.
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 3 2 次元配列.
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
ポインタとポインタを用いた関数定義.
第14回 前半:ラムダ計算(演習付) 後半:小テスト
プログラミング論 ポインタ
プログラミング言語論 第10回 情報工学科 篠埜 功.
11.1 標準ライブラリ関数 11.2 関数呼び出しのオーバーヘッド 11.3 大域変数 11.4 プロトタイプ宣言 11.5 関数引数
第5回 プログラミングⅡ 第5回
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
コンパイラ 第12回 実行時環境 ― 変数と関数 ― 38号館4階N-411 内線5459
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
PROGRAMMING IN HASKELL
プログラミング演習I 2003年6月11日(第9回) 木村巌.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング演習II 2004年11月 2日(第3回) 理学部数学科・木村巌.
プログラミング入門2 第5回 配列 変数宣言、初期化について
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング言語論 プログラミング言語論 演習5 解答と解説 演習5 解答と解説 1 1.
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング 3 ポインタ(1).
Presentation transcript:

プログラミング言語論 第9回 Hoare論理の練習問題 手続きの引数機構 変数の有効範囲 情報工学科 篠埜 功

Hoare論理の練習問題 以下のHoare Tripleを推論規則を使って導け。 { a + 2 = 2 } a := a + 2 { a = 2 } { a = 3 } if a = 3 then a := a + 1 else a := a – 1 { a = 4 } { a = 1 } while (a < 5) do a := a + 1 { a = 5 }

変数名から値への対応 命令型言語において変数名は番地を表す。その番地へアクセスすると値が得られる。ある変数名に対する番地は、その変数の宣言によって割り当てられる。変数名から宣言、番地への対応は、手続き呼び出し時の変数名の扱いによって異なる。 変数名の扱いについて、(プログラミング言語設計者にとって)いくつかの選択肢がある。 手続き呼び出し時の引数の受け渡し方法について call by value, call by reference, call by name 変数と宣言の対応関係について Static scope, dynamic scope

手続き(procedure) 手続きとは、プログラムの一部に名前を付けたものである。手続きが呼ばれると、その名前が付けられたプログラムが実行される。 関数(function)は、値を返す手続きのことである。 関数、手続きという用語を区別をしないで用いる場合もある。手続きは、 手続きの名前 仮引数の名前と型 結果の型(関数の場合) 局所宣言と文の並び から成る。

手続き、関数の呼び出し 関数呼び出しは式であり、手続き呼び出しは文である。 (例1) r * sin (angle) (例2) read (ch) read (ch) は手続き呼び出し文である。文なので、文が書ける部分に自由に書くことができる。

手続き(関数)呼び出しの構文 手続き呼び出し文(関数呼び出し式)の構文(前置記法) <手続き名> ( <引数列> ) 手続き呼び出し文(関数呼び出し式)における引数は実引数(actual parameter)と呼ばれる。 (例1) 関数呼び出し式 sin (angle) において angleは実引数。 (例2) 手続き呼び出し文 read (ch) において chは実引数。 手続き(関数)呼び出しにおいて、引数が0個でも括弧が必須の場合が多い(C, Modula-2など)。Pascalでは引数がない場合は括弧を書かない。 (Pascalの例) begin while eoln do readln; read(ch) end において、eolnは引数無し関数呼び出し式、readlnは引数無し手続き呼び出し文、read(ch)は引数有手続き呼び出し文。

手続きの宣言の構文 手続き(関数)の宣言の構文定義は、 手続きの名前 仮引数の名前と型 結果の型(関数の場合) 局所宣言と文の並び の4つが明確になるように、(言語設計者が)設計する。

手続きの宣言の例(Pascal) procedure getch; begin while eoln do readln; read (ch) end; これはgetchという名前の引数無しの手続きの宣言である。

関数の宣言の例(Pascal) function f (x : integer) : integer; var square : integer; begin square := x * x; f := square + 1 end; この例では、fという関数を宣言しており、引数はinteger型、返り値もinteger型であるということを表している。また、Pascalでは、関数名 := …という代入文によって、関数の返り値が決まる。 普通は、return文を用いる(C, Modula-2など)。

再帰関数 function f (n : integer) : integer; begin if n = 0 then f := 1 else f := n * f (n-1); end; これは、階乗を計算する関数である。 例えば、f (3) を計算するときは f (3) = 3 * f (2) = 6 f (2) = 2 * f (1) = 2 f (1) = 1 * f (0) = 1 f (0) = 1 のように関数fが繰り返し呼び出される。

引数の渡し方について function square (x : integer) : integer; begin square := x * x end; という関数宣言において、xは仮引数である。 例えば、square(2)という関数呼び出し式の値は、xに2が代入された状態でx*xを評価した結果であり、4である。square(3)の値は9である。このように数を渡す場合は自明だが、変数や配列の要素を渡す場合はいくつかの方法がある。

引数の渡し方 引数の渡し方には、大きく分けて、 Call-by-value(値呼び、値渡し) Call-by-reference(参照呼び、参照渡し) Call-by-name(名前呼び、名前渡し) の3つがある。

Call by value 仮引数には実引数の評価結果の値が渡される。 手続き(関数)pの仮引数がxのとき、手続き(関数)呼び出しp(e)の実行(評価)は (1) x := e; (2) 手続き(関数)本体の実行 (3) 手続きpが関数の場合は値を返す という順で行われる。 (注)変数xが呼び出し側でも宣言されている場合、仮引数xはそれとは別の変数である。 (squareの例) 関数square (2+3)の評価は、まずx := 2 + 3; が実行される。つまり2+3を評価し、その値5がsquareの仮引数xに代入される。そののちx * xが評価され、25が得られ、それが式square(2+3)の評価結果となる。

うまくいかない例1 procedure nget (c : char); begin while eoln do readln; read (c) end; この例ではcにキーボードから読み込んだ値が入るが、例えば nget (ch) などで呼び出しても 変数chには影響がない。(chとcは別の変数なので) 他の例として、swap (x,y)がある(変数xと変数yの値を入れ替える)

うまくいかない例2 procedure swap (x : integer; y : integer); var z : integer; begin z := x; x := y; y := z end; swap (a,b)のような呼び出しによって、変数aとbの値を入れ替えることはできない。 xとyには変数aとbの値が代入され、その後xとyの値が入れ替えられるので、変数a, bには影響が及ばない。

Call by reference 仮引数には実引数のアドレスが渡される。 (渡されたアドレスが仮引数のアドレスとなる。) Pascalにはcall by referenceがあり、 procedure p (x : integer; var y : integer); …. のように、call by referenceにしたい仮引数部分にvarをつけることによって、その仮引数の処理がcall by referenceになることを表す。 pの第二引数には、変数や配列の要素など、アドレスを持つ式(代入文の左辺に書ける式)を与えなければならない。

swapの例(Pascal) procedure swap (var x : integer; var y : integer); var z : integer; begin z := x; x := y; y := z end; この例では、xもyもcall by referenceである。例えば、swap (i, A[i])は以下のように実行される。 (1) xのアドレスをiのアドレスにする。 (2) yのアドレスをA[i]のアドレスにする。 (3) z := x; x := y; y := z 例えば iが2, A[2]が99の場合、z := 2; i := 99; A[2] = z の実行と同じ効果を持つので、iとA[2]の値が入れ替わることが分かる。

C言語について C言語での引数の受け渡しはcall by valueのみである。 ただ、Cにはポインタがあり、ポインタを渡すことによってcall by referenceをシミュレートできる。 void swap (int * px, int * py) { int z; z = *px; *px = *py; *py = z; } この関数swapを呼び出す際、ポインタ(アドレス)を渡す。 int a = 1, b = 2; swap (&a, &b); これにより、変数aとbの値が入れ替わる。

Call by name Call by nameでは、手続き内部のプログラム中の仮引数を実引数の式で置き換え、手続き呼び出し文をその結果で置き換えたプログラムと同じ意味である。 ただし、上記置き換えで名前の衝突が起こる場合は、名前の付け替えを行う。Algol60はcall by nameである。 program {内積の計算} var i, n, z : integer; a, b : array [0..9] of integer; procedure sum (x : integer); begin while i < n do begin z := z + x; i := i + 1 end end; begin n := 10; i := 0; z := 0; sum (a[i] * b[i]); writeln (z) end. 引数は手続き内部で仮引数が現れた箇所で評価される。これを遅延評価という。遅延評価にはcall by nameとcall by need(引数を一度だけ評価)がある。副作用が無い場合これら2つの評価は一致する。

(補足)Call by value result Call by referenceと似たような効果を持つものとして Call by value resultがある。これは、仮引数に実引数の値を渡し、実引数のアドレスを呼び出し時に保存しておいて、手続き終了時の仮引数の値を、保存しておいたアドレスに代入するというものである。Copy-in/copy-outとも呼ばれる。Adaではin, out, in outという3つの引数渡し方法が使える。In outがcall by value resultである。Call by value resultはcall by referenceと似ているが、異なる。 (例) program i, j : integer; procedure foo (x, y : integer); begin i := y end; begin i := 2; j := 3; foo (i, j) end Call by referenceではiの値は3になるが、call by value resultでは呼び出し後、iの値は2のままである。

変数の有効範囲について 変数には有効範囲(scope)がある。有効範囲の定め方は、静的有効範囲(static scopeあるいはlexical scope)、動的有効範囲(dynamic scope)に分かれる。 プログラム中の各変数がどこで宣言された変数であるかの決め方をスコープ規則(scope rule)という。スコープ規則を定めることにより、各宣言で宣言される名前の有効範囲が定まる。 静的有効範囲では、プログラムテキスト上で各宣言で宣言される変数の有効範囲が分かる。動的有効範囲では、変数の有効範囲は実行状況に依存する。

プログラム例 program L; var n : char; procedure W; begin writeln(n) end; procedure D; n := ‘D’; W {続き(プログラムLの本体)} begin n := ‘L’; W; D end.

Static scope Static scopeでは、プログラム中のある変数xの宣言は、プログラムテキスト上で、その変数を含む一番内側にある、xの宣言である。 Static scopeはlexical scopeとも呼ばれる。コンパイル時に変数の有効範囲が分かる。PascalやC等、ほとんどの言語はstatic scopeである。さきほどのプログラム例の実行結果は、static scopeでは L となる。 (考え方) Localな変数は名前を付け替えても意味は変わらないというのは自然な考え方である。この考えに従うとstatic scopeになる。

Dynamic scope Dynamic scopeでは、手続きpの呼び出し時点で、ある変数xが有効でxに対応する宣言がdの場合、pが呼ばれても変数に対応する宣言はdである。宣言dがなされている手続きが終了すると、xとdとの関係はなくなる。ただし、変数xが有効な状況で変数xの宣言d’がなされた場合、そこからはその変数xに対応する宣言はd’となる。Emacs Lispはdynamic scopeである。さきほどのプログラム例の実行結果はdynamic scopeだと L D になる。 (参考)Dynamic scopeは、コンパイラの実装の間違いから生まれたと言われている。