お気楽 Scheme プログラミング入門

Gauche は make でクラスのインスタンスを生成します。スロットの初期値は make でセットすることができますが、このほかに総称関数 initialize を使ってインスタンスの初期化をカスタマイズすることができます。

●総称関数 initialize

initialize は make から呼び出される総称関数です。インスタンスを生成するとき、initialize をオーバーライドすることで独自の初期化処理を行うことができます。

initialize instance initargs

initialize はインスタンスが生成されてから呼び出されます。このとき、スロットは未束縛であることに注意してください。スロットの初期値は :init-form や :init-value を使って設定することができますが、この処理は Gauche が提供する initialize の基本メソッドで行われます。したがって、単純に initialize をオーバーライドすると、スロットは未束縛のままになってしまいます。次の例を見てください。

リスト : initialize の例 (1)

; クラス定義
(define-class <foo> ()
  ((a :accessor foo-a :init-value 1 :init-keyword :a)))

(define-method initialize ((x <foo>) initargs)
  (if (slot-bound? x 'a)
      (format #t "slot a is ~S~%" (foo-a x))
    (print "slot a is unbound")))

この例はクラス <foo> の initialize をオーバーライドしています。slot-bound? はスロットが束縛されているかチェックする関数です。

slot-bound? instance slot-name

slot-name はスロット名を表すシンボルです。instance のスロット slot-name が束縛されていれば #t を、未束縛であれば #f を返します。

それから、任意のオブジェクトにスロットがあるかチェックする関数 slot-exists? もあります。

slot-exists? object slot-name

slot-exists? はオブジェクト object にスロット slot-name が存在すれば #t を、なければ #f を返します。

それでは、クラス <foo> のインスタンスを生成してみましょう。

gosh> (define x (make <foo> :a 10))
slot a is unbound
x
gosh> (slot-bound? x 'a)
#f

make からオーバライドした initialize が呼び出されますが、このときスロット a は未束縛の状態です。このあと、生成されたインスタンスのスロット a を slot-bound? でチェックすると #f が返ってきます。このように、initialize をオーバーライドすると、:init-value や :init-keyword で指定したスロットの初期化処理が行われないのです。

この場合、next-method を呼び出してスーパークラスのメソッド initialize を呼び出すようにします。

リスト : initialize の例 (2)

(define-method initialize ((x <foo>) initargs)
  (next-method)
  (if (slot-bound? x 'a)
      (format #t "slot a is ~S~%" (foo-a x))
    (print "slot a is unbound")))

実行例は次のようになります。

gosh> (define x (make <foo> :a 10))
slot a is 10
x
gosh> (slot-bound? x 'a)
#t

initialize を使ってインスタンスの初期化処理を行う場合は注意してください。

●ベクタによるキューの実装

それでは簡単な例題として、ベクタを使って「キュー (queue) 」を実装してみましょう。ベクタの場合、先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

           0  1  2  3  4  5  6  7  8  9
rear = 0  ↓
QUEUE    [                              ]  : QUEUE は空
front= 0  ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : データの追加
front= 0  ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : 10を取り出す
front= 1     ↑

rear = 3           ↓
QUEUE    [10 20 30                      ]  : 20,30を取り出す
front= 3           ↑

                    図 1 : キューの動作

まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値をインクリメントします。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。

次に、データを取り出す場合、front の示すデータを取り出してから front の値をインクリメントします。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。

このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなる場合もキューは空になります。実際にプログラムを作る場合は、キューの要素数をカウントする変数を用意しておくと、キューの状態を簡単に判断することができるので便利です。

rear, fornt ともに値は増加していく方向なので、いつかはベクタの範囲をオーバーします。このため、ベクタを先頭と末尾がつがっているリング状と考え、rear, front がベクタの範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、ベクタを使ってキューを実装する場合は、リングバッファとするのが普通です。

●プログラムの作成

最初に、キューを操作するためのメソッドを表 1 に示します。

次に、キューを表すクラスを定義します。

リスト：クラス queue の定義

(define-class <queue> ()
  ((buff  :accessor queue-buff  :init-keyword :buff)
   (size  :accessor queue-size  :init-keyword :size)
   (nums  :accessor queue-nums  :init-keyword :nums  :init-value 0)
   (front :accessor queue-front :init-keyword :front :init-value 0)
   (rear  :accessor queue-rear  :init-keyword :rear  :init-value 0)))

; 初期化
(define-method initialize ((q <queue>) intargs)
  (next-method)
  (if (not (slot-bound? q 'size))
      (error "<queue> : slot size is unbound"))
  (set! (queue-buff q) (make-vector (queue-size q))))

スロット nums はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。スロット size はキューの大きさを表し、スロット buff にはベクタをセットします。ベクタは initialize で生成してスロット buff にセットします。これで大きさ size のベクタを用意することができます。

次はデータを挿入するメソッド enqueue! を作ります。次のリストを見てください。

リスト : データの挿入

(define-method enqueue! ((q <queue>) value)
  (if (queue-full? q)
      (error "queue is full"))
  (vector-set! (queue-buff q) (queue-rear q) value)
  (inc! (queue-nums q))
  (inc! (queue-rear q))
  (if (= (queue-rear q) (queue-size q))
      (set! (queue-rear q) 0)))

まず、メソッド queue-full? を呼び出して、キューが満杯かチェックします。そうであればエラーを送出します。データ value は rear の位置に格納し、nums と rear の値を更新します。そして、rear の値がベクタの範囲を超えたならば 0 に戻します。rear の値を更新する処理は、次のようにプログラムしてもかまいません。

(set! (queue-rear q)
      (modulo (+ (queue-rear q) 1) (queue-size q)))

剰余を求める関数 modulo を使うのがポイントです。

次は、キューの先頭データを参照するメソッド queue-peek と、キューからデータを取り出すメソッド dequeue! を作ります。

リスト : データを取り出す

; 先頭データを参照
(define-method queue-peek ((q <queue>))
  (if (queue-empty? q)
      (error "queue is empty"))
  (vector-ref (queue-buff q) (queue-front q)))

; データの取り出し
(define-method dequeue! ((q <queue>))
  (begin0
    (queue-peek q)
    (dec! (queue-nums q))
    (inc! (queue-front q))
    (if (= (queue-front q) (queue-size q))
        (set! (queue-front q) 0))))

queue-peek はメソッド queue-empty? を呼び出してキューにデータがあるかチェックします。キューが空の場合はエラーを送出します。データがある場合、スロット front の位置にあるデータが先頭なので、vectore-ref で先頭データを取り出して返します。dequeue! は queue-peek で先頭の値を求め、その値を bigin0 で返します。あとはスロット nums を -1 して、front の値を +1 します。front の値がベクタの範囲を超えたら 0 に戻します。

あとのメソッドは簡単なので説明は省略いたします。詳細はプログラムリスト１をお読みくださいませ。

●実行例

それでは簡単な実行例を示します。

gosh> (define a (make <queue> :size 8))
a
gosh> (dotimes (x 8) (enqueue! a x))
#t
gosh> (enqueue! a 8)
*** ERROR: queue is full

gosh> (queue-length a)
8
gosh> (queue-full? a)
#t
gosh> (queue-empty? a)
#f
gosh> (dotimes (x 8) (format #t "~D " (dequeue! a)))
0 1 2 3 4 5 6 7 #t
gosh> (queue-empty? a)
#t
gosh> (queue-full? a)
#f
gosh> (queue-length a)
0

正常に動作していますね。

●プログラムリスト１

;
; queue.scm : リングバッファによるキューの実装
;
;             Copyright (C) 2010 Makoto Hiroi
;

;;; キューの定義

(define-class <queue> ()
  ((buff  :accessor queue-buff  :init-keyword :buff)
   (size  :accessor queue-size  :init-keyword :size)
   (nums  :accessor queue-nums  :init-keyword :nums  :init-value 0)
   (front :accessor queue-front :init-keyword :front :init-value 0)
   (rear  :accessor queue-rear  :init-keyword :rear   :init-value 0)))

; 初期化
(define-method initialize ((q <queue>) intargs)
  (next-method)
  (if (not (slot-bound? q 'size))
      (error "<queue> : slot size is unbound"))
  (set! (queue-buff q) (make-vector (queue-size q))))

;;; メソッドの定義

; 空か？
(define-method queue-empty? ((q <queue>))
  (zero? (queue-nums q)))

; 満杯か？
(define-method queue-full? ((q <queue>))
  (= (queue-nums q) (queue-size q)))

; データの挿入
(define-method enqueue! ((q <queue>) value)
  (if (queue-full? q)
      (error "queue is full"))
  (vector-set! (queue-buff q) (queue-rear q) value)
  (inc! (queue-nums q))
  (inc! (queue-rear q))
  (if (= (queue-rear q) (queue-size q))
      (set! (queue-rear q) 0)))

; 先頭データを参照
(define-method queue-peek ((q <queue>))
  (if (queue-empty? q)
      (error "queue is empty"))
  (vector-ref (queue-buff q) (queue-front q)))

; データの取り出し
(define-method dequeue! ((q <queue>))
  (begin0
    (queue-peek q)
    (dec! (queue-nums q))
    (inc! (queue-front q))
    (if (= (queue-front q) (queue-size q))
        (set! (queue-front q) 0))))

; 要素数を求める
(define-method queue-length ((q <queue>))
  (queue-nums q))

; 空にする
(define-method queue-clear! ((q <queue>))
  (set! (queue-nums q) 0)
  (set! (queue-front q) 0)
  (set! (queue-rear q) 0))