計算機プログラムの構造と解釈 第二版 P155 問題3.21

Benに間違いを説明する問題。

手続きmake-queueでつくったqueueは値がそのまんま入っているんじゃなくて、

( [queueの先頭へのポインタ] [queueの最後尾(nullの一個前)へのポインタ] )

みたいな感じだ。

だけども、デフォルトでのってる印字プログラムはポインタの先を追っていって表示してくれるので、
Benが誤解したように印字される。

((a b) b)

印字プログラムはポインタの先を追っていって表示してくれるので、単にqueue先頭のポインタを印字プログラムに渡してやれば良いのかと。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)

(define nil '())
(define disp display)
(define nl newline)


(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))

(define (empty-queue? queue)
  (null? (front-ptr queue)))


(define (make-queue)
  (cons '() '()))


(define (front-queue queue)
  (if (empty-queue? queue)
    (error "FRONT called with an empty queue" queue)
    (car (front-ptr queue))))


(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))))


(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)))


(define q1 (make-queue))

(define (print-queue queue)
  (print (front-ptr queue)))

;; main
(define (main args)

  (print "(insert-queue! q1 'a)")
  (insert-queue! q1 'a)
  (print "(insert-queue! q1 'b)")
  (insert-queue! q1 'b)

  (disp "(print q1): ")
  (print q1)

  (disp "(print-queue q1): ")
  (print-queue q1)

  (nl)
  (print "(delete-queue! q1)")
  (delete-queue! q1)

  (disp "(print q1): ")
  (print q1)

  (disp "(print-queue q1): ")
  (print-queue q1)

  (nl)
  (print "(delete-queue! q1)")
  (delete-queue! q1)

  (disp "(print q1): ")
  (print q1)

  (disp "(print-queue q1): ")
  (print-queue q1)

  0)

実行

(insert-queue! q1 'a)
(insert-queue! q1 'b)
(print q1): ((a b) b)
(print-queue q1): (a b)

(delete-queue! q1)
(print q1): ((b) b)
(print-queue q1): (b)

(delete-queue! q1)
(print q1): (() b)
(print-queue q1): ()

print-queueの実装はあってると思うけど、説明の部分は特に自信がない。