SICP练习3.22：带局部状态过程实现队列的返回值修正方法

问题描述 #

SICP 第90页§2.1.3节明确说明，一等函数让过程和数据不再有明确边界，正如原文表述：

将过程作为对象进行操作的能力，会自动提供复合数据的表示能力。

第266页§3.3.2节的练习3.22要求用带局部状态的过程实现队列，不使用传统的首尾指针对数据结构，框架代码如下：

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

初始实现（将指针重命名为the-list和last-pair）基础功能可用，但修改操作返回内部列表而非队列本身，导致链式调用失败：

; 这两个链式调用无法运行
(insert-queue! (insert-queue! q 3) 4)
(delete-queue! (delete-queue! q))

按照接口约定，insert-queue!和delete-queue!需要返回修改后的队列对象，而消息传递实现中，队列本身就是内部的dispatch过程。

修复方法 #

只需要调整两处返回值，同时补全一个隐藏的边界bug即可：

• 插入操作完成后，不再返回内部列表the-list，直接返回dispatch（即队列本身）
• 删除操作完成后，同样返回dispatch
• 补全边界逻辑：当删除操作导致队列清空时，同步将last-pair重置为空，避免后续插入操作关联到已被移除的旧节点

修复后的完整代码：

(define (make-queue)
  (let ((the-list '())
        (last-pair '()))
    (define (dispatch m)
      (cond ((eq? m 'empty) (null? the-list))
            ((eq? m 'front) (if (null? the-list)
                                (error "can't take front of empty list")
                                (car the-list)))
            ((eq? m 'ins) (lambda (e)
                            (if (null? the-list)
                                (begin (set! the-list (list e))
                                       (set! last-pair the-list))
                                (begin (set-cdr! last-pair (list e))
                                       (set! last-pair (cdr last-pair))))
                            dispatch))
            ((eq? m 'del) (begin
                           (if (null? the-list)
                               (error "can't delete from empty list")
                               (begin
                                 (set! the-list (cdr the-list))
                                 (if (null? the-list)
                                     (set! last-pair '()))))
                           dispatch))
            ((eq? m 'disp) (display the-list))
            (else (error "Unknown queue operation:" m))))
    dispatch))

(define (empty-queue? q) (q 'empty))
(define (front-queue  q) (q 'front))
(define (insert-queue! q e) ((q 'ins) e))
(define (delete-queue! q) (q 'del))
(define (display-queue q) (q 'disp))

修复后链式调用可正常运行：

(define q (make-queue))
(insert-queue! (insert-queue! q 3) 4)
(display-queue q) ; 输出 (3 4)
(delete-queue! (delete-queue! q))
(display-queue q) ; 输出 ()

内容的提问来源于stack exchange，提问作者Enlico