Section §2.1.3 at page 90 explains, with a very clear example, that first class functions in a language make functions themselves and data be the same thing looked at from different perspectives, or, to cite the book:
the ability to manipulate procedures as objects automatically provides the ability to represent compound data.
At page 266, exercise 3.22 from Section §3.3.2, proposes the following
Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the
make-queueprocedure will have the form(define (make-queue) (let ((front-ptr ...) (rear-ptr ...)) <definitions of internal procedures> (define (dispatch m) ...) dispatch))Complete the definition of
make-queueand provide implementations of the queue operations using this representation.
I easily came up with the following (I've used names the-list and last-pair instead of front-ptr and rear-ptr because I found it clearer, in this case):
(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))
which seems to work pretty fairly well…
… except for one crucial point!
At the beginning of §3.3.2 the two desired mutators (that are part of the queue interface) are defined like this (my emphasis):
(insert-queue! <queue> <item>)inserts the item at the rear of the queue and returns the modified queue as its value.
(delete-queue! <queue>)removes the item at the front of the queue and returns the modified queue as its value, signaling an error if the queue is empty before the deletion.
My solution doesn't abide by those parts of the definition, because both insert-queue! and delete-queue! are returning the-list, which is the bare list, an implementation detail of the queue interface. Indeed, my solution doesn't support things like these
(define q (make-queue)) ; ok
(insert-queue! (insert-queue! q 3) 4) ; doesn't work
(delete-queue! (delete-queue! q)) ; doesn't work
whereas I think it should.
I guess that the solution should see delete-queue! and insert-queue! return a mutated version of the dispatch function.
How do I do that?
No need for that. Simply define
(define (insert-queue! q e)
((q 'ins) e)
q)
(define (delete-queue! q)
(q 'del)
q)
The design is not clean though, as in, these queues are not persistent. The new version and the old share the same underlying buffer (list). There is no old version preserved anymore, just the current version.
So we don't return a new, modified queue; we return the same queue which has been mutated. Conceptually, that is. On a little bit lower level, we return the same dispatch procedure which is a part of the same closure which holds the same internal binding for the internal buffer, which has been mutated.
By the way, using the head sentinel trick, were you start with e.g. (list 1) instead of '(), usually leads to much simplified, clearer code.