Scheme - キューの表現(実装(局所状態を持つ手続き))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.3(可変データでのモデル化)、3.3.2(キューの表現)の問題 3.22を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題3.22

コード(BBEdit)

sample.scm

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! item) (set! front-ptr item))
    (define (set-rear-ptr! item) (set! rear-ptr item))
    (define (empty-queue?) (null? front-ptr))
    (define (front-queue)
      (if (empty-queue?)
          (error "FRONT called with an empty queue" front-queue)
          (car front-ptr)))
    (define (insert-queue! item)
        (let ((new-pair (cons item '())))
          (cond ((empty-queue?)
                 (set-front-ptr! new-pair)
                 (set-rear-ptr! new-pair)
                 (newline)
                 (display "空っぽ")
                 make-queue)
                (else
                 (newline)
                 (display "空っぽではない")
                 (set-cdr! rear-ptr new-pair)
                 (set-rear-ptr! new-pair)
                 make-queue))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue" delete-queue!))
            (else
             (set-front-ptr! (cdr front-ptr))
             make-queue)))
    (define (print-queue) front-ptr)
    (define (dispatch m)
      (cond ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            ((eq? m 'print-queue) print-queue)
            (else
             (error "Undefined operation -- MAKE-QUEUE"
                    m))))
    dispatch))

(define q1 (make-queue))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((q1 'print-queue))

;Value: ()

1 ]=> ((q1 'insert-queue!) 'a)

;Value 2: #[compound-procedure 2 make-queue]

1 ]=> ((q1 'print-queue))

;Value 3: (a)

1 ]=> ((q1 'insert-queue!) 'b)

;Value 2: #[compound-procedure 2 make-queue]

1 ]=> ((q1 'print-queue))

;Value 3: (a b)

1 ]=> ((q1 'delete-queue!))

;Value 2: #[compound-procedure 2 make-queue]

1 ]=> ((q1 'print-queue))

;Value 4: (b)

1 ]=> ((q1 'delete-queue!))

;Value 2: #[compound-procedure 2 make-queue]

1 ]=> ((q1 'print-queue))

;Value: ()