第11回講義スライド

プログラミング入門第11回
二宮崇
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
今日の目的

可変リストの応用
キュー
 連想リストオブジェクト
 クォートとlist関数の違い

4
3.3.2 キューの表現

キュー(queue)

FIFO (first in first out)を実現するリスト
新しく挿入される要素は、リストの末尾に加えられる
 リストの先頭の要素のみ取り出す(削除する)ことができ
る

先頭
取り出し
い
末尾
リスト
う
え
お
か
き
く
け
追加
あ
5
3.3.2 キューの表現

キューの関数

(make-queue)


(empty-queue? q)


キューqの先頭の要素を返す
(insert-queue! q d)


キューqが空であるかどうか判定する
(front-queue q)


キューを作成
キューqに要素dを追加する
(delete-queue! q)

キューqの先頭の要素を削除する
6
3.3.2 キューの表現

キューのデータ構造

効率を良くするためにキューの先頭と末尾を
指すポインタを持たせる
7
3.3.2 キューの表現
キューの基本関数
(define (make-queue) (cons '() '()))
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

リストでデータオブジェクトを表現して、set-car!やset-cdr!を使っ
て値を書き換えるようにするとだいぶ楽にオブジェクトを作れる
（関数を返すことによってオブジェクトを作成するやり方に比べかな
り簡単）
8
3.3.2 キューの表現

empty-queue?
先頭のデータを示すポインタが末尾ならキューは空
(define (empty-queue? queue) (null? (front-ptr queue)))


front-queue
先頭の要素をみるにはfront-ptrが指すリストの先頭の要素を返
せば良い
(define (front-queue queue)

(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))
9
3.3.2 キューの表現

insert-queue!



rear-ptrが示す末尾のデータに要素を追加
rear-ptrが新しく追加したデータを指すように変更す
る
キューが空の場合には特殊な操作が必要

front-ptrとrear-prtが同じ新しいデータを指すようにする
(insert-queue! q 'd)
10
3.3.2 キューの表現
(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
(cond ((empty-queue? queue)
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else
(set-cdr! (rear-ptr queue) new-pair)
(set-rear-ptr! queue new-pair)
queue))))
(insert-queue! q 'd)
11
3.3.2 キューの表現

delete-queue!
先頭の要素を削除
 set-front-ptr!でfront-ptrを一つ後ろにつな
げなおす

(delete-queue! q)
12
3.3.2 キューの表現
(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))
(delete-queue! q)
13
3.3.3 表の表現

連想リスト(キーと値のペアによるリスト)

空になったときに困らないようにダミーエン
トリーをつくっておく
頭 (head)
背骨(backbone)
*table*がダミーエントリー
 頭付きリスト(headed list)と呼ばれる

14
3.3.3 表の表現

ダミーを用いない場合
table

問題点

tableから先頭の要素を削除したい場合は、(set!
table (cdr table))としなくてはいけないが、table
以外の任意の変数名が使える一般的な関数を定義する
ことができない
15
3.3.3 表の表現
新しい連想リストの作成
(define (make-table) (list '*table*))


検索 lookup

等しいキーがあるかどうか順にみていく
(define (myassoc key records)
(cond ((null? records) #f)
((equal? key (car (car records))) (car records))
(else (myassoc key (cdr records)))))
(define (lookup key table)
(let ((record (myassoc key (cdr table))))
(if record
(cdr record)
#f)))
16
3.3.3 表の表現

insert!

新しいエントリーを挿入する
(define (insert! key value table)
(let ((record (myassoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value) (cdr table)))))
'ok)
17
3.3.3 表の表現
実行例
> (define a (make-table))
> a
(*table*)
> (insert! 'a 1 a)
ok
> a
(*table* (a . 1))
> (insert! 'b 2 a)
ok
> (insert! 'c 3 a)
ok
> (lookup 'b a)
2
> a
(*table* (c . 3) (b . 2) (a . 1))
>

18
クォートとlist関数の違い
クォートによるリスト: '(a b c)
 list関数によるリスト: (list 'a 'b 'c)
同じリストを返すようにみえるけど違いがあるので注意
が必要


クォートによるリスト



関数に埋め込まれているリスト
プログラムの読み込み時に関数と一緒に一度だけ生成され
る
list関数によるリスト

プログラム実行中に新しくリストを生成
19
クォートとlist関数の違い
define (f) '(a b c))
(define (g) (list 'a 'b 'c))
(define x (list (f) (f) (f)))
(define y (list (g) (g) (g)))
> x
((a b c) (a b c) (a b c))
> y
((a b c) (a b c) (a b c))
> (set-car! (car x) 'change)
> (set-car! (car y) 'change)
> x
((change b c) (change b c) (change b c))
> y
((change b c) (a b c) (a b c))
> (f)
(change b c)
20
クォートとlist関数の違い

クォートによって生成されたx
x
a

b
c
list関数によって生成されたy
y
a
b
c
a
b
c
a
b
c
21
クォートとlist関数の違い

インタプリタの処理の流れ
1.
プログラムを読み込む



2.
(define (f x) …)といった関数の定義を読み込んだ
とき関数オブジェクトが生成される
クォートによるリストはこの関数オブジェクトと一緒
に生成され、関数オブジェクトの中に埋め込まれる
後で関数を実行したときには同じリストが返される
プログラムを実行


list関数によるリストは関数の実行時に初めて生成さ
れる
list関数の実行毎に異なるリストオブジェクトが生成
される
クォートによるリストは静的なリスト
list関数によるリストは動的なリスト
22

Download Report