Scheme - 標準部品化力、オブジェクトおよび状態(可変データのモデル化(キューの表現(局所状態を持つ手続きとして実装)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X El Capitan - Apple (OS)
• Emacs(Text Editor)
• Scheme (プログラミング言語)
• kscheme (github) (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: 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
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
• Scheme手習い

問題3.22.

コード(Emacs)

(begin
  (define (print obj)
    (display obj)
    (newline))

  (define (make-queue)
    (let ((front-ptr (quote ()))
          (rear-ptr (quote ())))
      (define (set-front-ptr! p) (set! front-ptr p))
      (define (set-rear-ptr! p) (set! rear-ptr p))
      (define (empty-queue?) (null? front-ptr))      
      (define (front-queue)
        (if (empty-queue?)
            (begin (display "Error: front called with an empty queue -- ")
                   (print front-ptr))
            (car front-ptr)))
      (define (insert-queue! item)
        (let ((new-pair (cons item (quote ()))))
          (if (empty-queue?)
              (begin  (set-front-ptr! new-pair)
                      (set-rear-ptr! new-pair))
              (begin (set-cdr! rear-ptr new-pair)
                     (set-rear-ptr! new-pair)))
          dispatch))
      (define (delete-queue!)
        (if (empty-queue?)
            (begin (display "Error: delete! called with an empty queue -- ")
                   (print front-ptr))
            (begin (set-front-ptr! (cdr front-ptr))
                   dispatch)))
      (define (print-queue) (print front-ptr))
      (define (dispatch m)
        (cond ((eq? m (quote insert-queue!)) insert-queue!)
              ((eq? m (quote delete-queue!)) delete-queue!)
              ((eq? m (quote print-queue)) print-queue)
              (else (display "Error: unknown message --  ")
                    (print m))))
      dispatch))

  (define (insert-queue! queue item) ((queue (quote insert-queue!)) item))
  (define (delete-queue! queue) ((queue (quote delete-queue!))))
  (define (print-queue queue) ((queue (quote print-queue))))
  
  (define q (make-queue))
  (define q1 (make-queue))
  (print-queue q1)

  (print-queue (insert-queue! q1 (quote a)))
  (print-queue (insert-queue! q1 (quote b)))
  (print-queue (delete-queue! q1))
  (print-queue (delete-queue! q1))
  )

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

$ ./kscheme sample22.scm
()
(a)
(a b)
(b)
()
$