第2回講義スライド

プログラミング入門第2回
二宮崇
1
教科書

Structure and Interpretation of Computer
Programs, 2nd Edition: Harold Abelson,
Gerald Jay Sussman, Julie Sussman, The MIT
Press, 1996
http://mitpress.mit.edu/sicp/

計算機プログラムの構造と解釈第二版, ジェラ
ルド・ジェイサスマン, ジュリーサスマン, ハ
ロルドエイブルソン (著), 和田英一 (訳), ピ
アソン・エデュケーション, 2000年
2
講義資料
この講義のウェブサイト
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/itp
愛媛大学総合情報メディアセンターのMoodle Ver.2
http://moodle.ehime-u.ac.jp/
の工学部/理工学研究科(工学系)の情報工学科の中にある
「2015前-プログラミング入門-二宮」
3
今日の目的
関数
 置き換えモデル
 作用的順序と正規順序
 ブラックボックスとしての関数
 局所変数とスコープ

4
1.1.4 関数

関数も環境において定義できる
(define (関数名
引数) 本体)
例: 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑥𝑥 = 𝑥𝑥 × 𝑥𝑥
(define (square x) (* x x))
例: 𝑓𝑓 𝑥𝑥, 𝑦𝑦 = 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑥𝑥 + 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑦𝑦)
(define (f x y) (+ (square x) (square y)))
5
1.1.4 関数
引数のない関数も定義できる
(define (f) (+ 3 5 6))

(f)→14
6
1.1.5 置き換えモデル


関数の評価のためのモデル
置き換えで計算を進める計算モデル
例
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f x) (sum-of-squares (+ x 1) (* x 2)))
(f 5)を評価
(f 5)
=(sum-of-squares (+ 5 1) (* 5 2))
=(sum-of-squares 6 10)
=(+ (square 6) (square 10))
=(+ (* 6 6) (* 10 10))
=(+ 36 100)
=136
7
1.1.5 置き換えモデル

計算モデル
実際の計算方法と関係なく、プログラムはこ
のように解釈される、というプログラムの意
味を与えてくれる
 抽象化された言語設計が可能になる
 置き換えモデルは単純明快

 どのような答えを返せば良いのか明確
 実装に依存しない
 効率的なプログラミング言語の設計が可能になる
8
作用的順序と正規順序

作用的順序



正規順序


引数を評価してから作用させる
コンピュータ上で実際に行われている計算順序
関数を完全に展開してから簡約する
正しい値が得られる関数については、作用的
順序も正規順序も同じ値になることが示され
ている
9
作用的順序と正規順序
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f x) (sum-of-squares (+ x 1) (* x 2)))
作用的順序による評価
正規順序による評価
(f 5)
(f 5)
=(sum-of-squares (+ 5 1) (* 5 2)) =(sum-of-squares (+ 5 1) (* 5 2))
=(sum-of-squares 6 10)
=(+ (square (+ 5 1)) (square (* 5 2)))
=(+ (square 6) (square 10))
=(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
=(+ (* 6 6) (* 10 10))
=(+ (* 6 6) (* 10 10))
=(+ 36 100)
=(+ 36 100)
=136
=136
10
1.1.8 ブラックボックス抽象と
しての関数

手続きの実装にいろいろな方法





(define
(define
(define
(define
(square
(square
(double
(double
x)
x)
x)
x)
(* x
(exp
(+ x
(* 2
x))
(double (log x))))
x))
x))
関数による手続きの抽象化


プログラマはsquareやdoubleがどのような値を返
すか、それだけ知っていれば良い。
具体的な実装については知らなくても良い
11
局所変数

関数の中の引数は局所変数
(define (square x) (* x x))の中のx
 同じ名前の大域変数があったとしても、この関数の定義内
では異なる変数として扱われる (関数の定義の中で束縛さ
れていると言います)
例: 大域変数 x = 5の状態で(square 100)を呼び出したとし
ても、大域変数のxは影響を受けず、square内でのみx=100と
して扱われる


大域変数と局所変数が同じように扱われてしまうと…
(define x 100)
(define (square x) (* x x))
(square 10)を実行すると、xが10に束縛されて、大域変数のx
が100から10に変わってしまう
12
局所変数

数学における関数の引数と同じ性質



引数は関数内でのみ有効
大域変数より局所変数が優先される
他の関数の引数の影響を受けない
𝑥𝑥 = 5
𝑓𝑓 𝑥𝑥 = 𝑔𝑔 5𝑥𝑥 + 𝑥𝑥
𝑔𝑔 𝑥𝑥 = 𝑥𝑥 2
(define x 5)
(define (f x) (+ (g (* 5 x)) x))
(define (g x) (* x x))
𝑓𝑓 𝑥𝑥 = 𝑥𝑥 2
𝑓𝑓 𝑦𝑦 = 𝑦𝑦 2
(define (f x) (* x x))
(define (f y) (* y y))

引数の変数名を変えても同じ関数
13
局所変数

局所変数が有効な範囲のことをスコープと
いう


関数の引数のスコープは関数の本体
プログラムをみてそのスコープを決定でき
ることを静的スコープ (lexical scoping)
という
14

Download Report