将队列表示为具有本地状态的过程

问：

第90页的§2.1.3节用一个非常清楚的例子解释了语言中的第一类函数使函数本身和数据从不同的角度来看是同一回事，或者引用本书：

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

在第 266 页，第 §3.3.2 节中的练习 3.22 提出了以下建议

我们可以将队列构建为具有本地状态的过程，而不是将队列表示为一对指针。本地状态将由指向普通列表的开头和结尾的指针组成。因此，该过程将具有以下形式make-queue

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

使用此表示形式完成队列操作的定义并提供其实现。make-queue

我很容易想出以下内容（在这种情况下，我使用了名称而不是 and，因为我发现它更清楚）：the-listlast-pairfront-ptrrear-ptr

(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))))
                            the-list))
            ((eq? m 'del) (begin
                           (if (null? the-list)
                               (error "can't delete from emtpy list")
                               (set! the-list (if (pair? the-list) (cdr the-list) '())))
                           the-list))
            ((eq? m 'disp) (display the-list)) ; added this for convenience
            (else "error")))
    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))

这似乎效果很好......

...除了一个关键点！

在 §3.3.2 的开头，两个所需的变值器（作为队列接口的一部分）是这样定义的（我的重点）：

(insert-queue! <queue> <item>)

在队列的后面插入项，并将修改后的队列作为其值返回。

(delete-queue! <queue>)

删除队列前面的项，并将修改后的队列作为其值返回，如果队列在删除前为空，则发出错误信号。

我的解决方案不遵守定义的这些部分，因为两者都返回 ，这是裸列表，队列接口的实现细节。事实上，我的解决方案不支持这样的事情insert-queue!delete-queue!the-list

(define q (make-queue)) ; ok
(insert-queue! (insert-queue! q 3) 4) ; doesn't work
(delete-queue! (delete-queue! q))     ; doesn't work

而我认为它应该。

我想解决方案应该看到并返回该函数的变异版本。delete-queue!insert-queue!dispatch

我该怎么做？