第9回講義スライド

プログラミング入門第9回
二宮崇
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/
の工学部/理工学研究科(工学系)の情報工学科の中にある
「2014前-プログラミング入門-二宮」
3
今日の目的

代入
代入操作 set!
 状態変数
 局所状態変数

手続き型プログラミング
 代入を取り入れた利点とその代償

4
3. 標準備品化力、オブジェクトおよび状態

モジュール化
システム全体を系統立ったモジュールに分割
 より大きなシステムの作成に
 分割して開発、保守


モジュール化の戦略

オブジェクト
 環境モデルを用いて説明


置き換えモデルを使うことができない
ストリーム
5
3.1 代入と局所状態

オブジェクト



各オブジェクトは固有の状態を持つ
オブジェクトに命令(メッセージ)を与える
命令により、その状態を変えながら計算を行う
モデル


状態変数



同じ命令を与えても異なる結果が返ってくることが
ある
過去に実行した命令の結果を集約し、新しい命
令の結果に影響を与える変数
オブジェクトの状態を代表
オブジェクト指向

たくさんのオブジェクトを生成し、オブジェク
ト間の相互作用により全体の計算が行われる
6
3.1.1 局所状態変数

銀行口座の例


銀行口座に預金がある
withdrawという手続きでお金を引き出せて、残額が返値と
して返ってくる
> (withdraw 25)
75
> (withdraw 25)
50
> (withdraw 60)
"Insufficient funds"
> (withdraw 15)
35
7
3.1.1 局所状態変数

今まで習った手法
状態がない
 同じ引数の関数には必ず同じ結果

 withdrawは今までの方法では実装できそうにない…
8
3.1.1 局所状態変数

代入操作

特殊形式 set!
 (set!
<name> <new-value>)
 <name>の値を<new-value>を評価した値に変更

begin
 (begin
<exp1> <exp2> … <expk>)
 <exp1>から<expk>まで順に評価
 最後の式<expk>の値をbegin全体の値をして返す
9
3.1.1 局所状態変数
(define balance 100)
(define (withdraw amount)
(if (>= balance amount)
(begin
(set! balance (- balance amount))
balance)
"Insufficient funds"))
10
3.1.1 局所状態変数
口座というオブジェクトをつくる関数
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin
(set! balance (- balance amount))
balance)
"Insufficient funds")))

11
3.1.1 局所状態変数
二つの口座の例
> (define W1 (make-withdraw 100))
> (define W2 (make-withdraw 100))
> (W1 50)
50
> (W2 70)
30
> (W2 40)
"Insufficient funds"

12
3.1.1 局所状態変数

複数の機能を持つオブジェクト

withdraw以外の様々な機能
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin
(set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (display "Unknown request -- MAKE-ACCOUNT")
(display m))))
dispatch)
13
3.1.1 局所状態変数
複数の機能を持つオブジェクトの例
> (define acc (make-account 100))
> ((acc 'withdraw) 50)
50
> ((acc 'withdraw) 60)
"Insufficient funds"
> ((acc 'deposit) 40)
90
> ((acc 'withdraw) 60)
30

14
手続き型プログラミング

手続き型プログラミング
set!を用いたプログラミング
 変数に対する代入操作を繰り返すことにより
計算を進める

15
手続き型プログラミング
関数型プログラミングによる和の計算
(define (sum n)
(if (= n 1)
1
(+ n (sum (- n 1)))))

16
手続き型プログラミング
手続き型プログラミングによる和の計算
(←は代入操作)
1. result ← 0
2. i ← 1
3. i ≤ n の間以下を繰り返す。i ≤ n でなければ7.
に進む。
4. result ← result + i
5. i ← i + 1
6. 3.に戻る。
7. resultを返す。

17
手続き型プログラミング
手続き型プログラミングによる和の計算
(define (sum n)
(define result 0)
(define i 1)
(define (iter)
(if (<= i n)
(begin
(set! result (+ result i))
(set! i (+ i 1))
(iter))
'done))
(iter)
result)

かなりややこしいし、見づらいプログラム…
18
手続き型プログラミング
for
(define (for seq proc)
(if (null? seq)
'done
(begin (proc (car seq))
(for (cdr seq) proc))))

リストseqの各要素に対し、procを順次適用
19
手続き型プログラミング
手続き型プログラミングによる和の計算
(define (sum n)
(define result 0)
(for (range 1 n)
(lambda (i) (set! result (+ result i))))
result)

だいぶすっきりした！
20
手続き型プログラミング

begin以外に連続して式を評価する関数や書式




(define (f x) <式1><式2>…<式n>)
(let ((x 2)(y 3)) <式1><式2>…<式n>)
(cond ((= x 2) <式1><式2>…<式n>)
(else <式1><式2>…<式n>))
(lambda (x) <式1><式2>…<式n>)
21
3.1.2 代入を取り入れた利点

代入を取り入れた利点
手続き型言語のようにプログラムを書ける
 乱数を発生する手続きの実現やモンテカルロ
シミュレーション
 オブジェクト指向型プログラミング

22
3.1.3 代入を取り入れた代価

代入を取り入れた代償
置き換えモデルで解釈できない
 関数型プログラミングでなくなる

 今までの関数は、同じ引数なら必ず同じ値が返って
きた→数学的な関数
23
3.1.3 代入を取り入れた代価
置き換えモデルを使って解釈できない
(define (f i)
(set! i (+ i 1))
i)

計算例
> (f 10)
11
 置き換えモデルによる説明
(f 10)
=(set! i (+ 10 1)) 10
;式が二つ並んでいることに注意
=10
iを11にset!したあと、10を返す、ということになってしまう
(本当は(+ 10 1)の結果である11を返したい)

24
3.1.3 代入を取り入れた代価

同一と変化

参照透明性がなくなる




参照透明(referentially transparent): 式の評価の結果を変えることな
く、式の中で「等しいものは等しいもので置き換えられる」こと
きれいな計算モデルの設計が困難に
計算オブジェクトが同一であるかどうか、形式的に判定することが難し
くなった
例A
(define peter-acc (make-account 100))
(define paul-acc (make-account 100))
異なる二つのオブジェクトが生成

例B
(define peter-acc (make-account 100))
(define paul-acc peter-acc)
本質的に一つのオブジェクトのみ存在。
一つのオブジェクトを二つの変数が共有している。
25
3.1.3 代入を取り入れた代価

手続き型プログラミングの落とし穴

関数型プログラミングでは起こりえないバグ
がでる
26
3.1.3 代入を取り入れた代価
関数型プログラミングによる階乗の計算
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

27
3.1.3 代入を取り入れた代価
手続き型プログラミングによる階乗の計算
(define (factorial n)
(let ((product 1)
(counter 1))
(define (iter)
(if (> counter n)
product
(begin (set! product (* counter product))
(set! counter (+ counter 1))
(iter))))
(iter)))
 しかし、代入の順番を逆にすると、正しくない結果になってし
まう!
(set! counter (+ counter 1))
(set! product (* counter product))

28
3.1.3 代入を取り入れた代価

手続き型プログラミングでもforとrangeを使えば
バグがでにくい
(define (factorial n)
(define product 1)
(for (range 1 n)
(lambda (i) (set! product (* i product))))
product)
29

Download Report