Exercise 3.21 · 习题

Exercise 3.21: Ben Bitdiddle decides to test the
queue implementation described above. He types in the procedures to the Lisp
interpreter and proceeds to try them out:

(define q1 (make-queue))

(insert-queue! q1 'a)
((a) a)

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

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

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

“It’s all wrong!” he complains. “The interpreter’s response shows that the

last item is inserted into the queue twice. And when I delete both items, the

second b is still there, so the queue isn’t empty, even though it’s

supposed to be.” Eva Lu Ator suggests that Ben has misunderstood what is

happening. “It’s not that the items are going into the queue twice,” she

explains. “It’s just that the standard Lisp printer doesn’t know how to make

sense of the queue representation. If you want to see the queue printed

correctly, you’ll have to define your own print procedure for queues.” Explain

what Eva Lu is talking about. In particular, show why Ben’s examples produce

the printed results that they do. Define a procedure print-queue that

takes a queue as input and prints the sequence of items in the queue.

练习 3.21：Ben Bitdiddle 决定测试上面描述的队列实现。他将这些过程输入 Lisp 解释器，并尝试运行：

(define q1 (make-queue))

(insert-queue! q1 'a)
((a) a)

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

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

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

“全错了！”他抱怨道。“解释器的响应显示最后一项被插入了队列两次。而当我删除两项之后，第二个 b 还在那里，队列明明应该是空的，却不空。”Eva Lu Ator 提示 Ben 误解了实际发生的情况。“并非两项进入了队列，”她解释道，“只是标准的 Lisp 打印机不知道如何呈现队列的表示方式。如果你想正确地打印队列，就需要为队列自定义一个打印过程。”请解释 Eva Lu 所说的含义。具体而言，说明为什么 Ben 的示例会产生那样的打印结果。请定义一个过程 print-queue，它以队列为输入，并按顺序打印队列中的各项。