Ex. 3.21

Ben’s primary confusion seems to be in thinking that multiple references to something are multiple instances of that thing. Although, as Eva points out, he additionally may not realize that what’s being printed to the screen is not a list representing the queue. After all, the queue itself is simply a pair of pointers. When a pair is printed out by most interpreters, it shows whatever the first points to, followed by what the second references. There is a special case when the pointers constitute a list (i.e. the cdr of a pair is either a pointer or the empty list), which is the case here, to ensure that lists are printed out more clearly as a sequence of values.

After anything is inserted into the queue, the front pointer points to the list of all items in the queue, and the rear pointer points to the single-element list at the tail of that same list. When the interpreter gives the result, it will be a two element list: The first element is the list referenced by the front pointer, and the second element is the end of that same pointer sequence, which is where the rear pointer points. Unlike what Ben thought, this is not a duplicated member, but just a second reference to the most-recently-inserted element. (If you find this confusing, refer to the textbook diagrams 3.20 or 3.21 to see what the two pointers of the queue point to.)

The second issue he has, about the queue not really being empty, has to do with how ‘empty’ is actually defined. When determining if the queue is empty, the procedure empty-queue? is always the one used. How does empty-queue? work? It just checks if the front pointer is null. What we see in Ben’s complaint is that the rear pointer (the second part of the printed out result) is the one that still contains a reference to b. It does not look any different externally, as the only means of accessing items in the queue is via the front pointer (using front-queue), and the rear pointer is only used for insertion.

What Ben noticed about deletion could actually lead to a problem. Normally, when a new item is inserted into the queue, the rear pointer will be overwritten, and any reference to its previous value will be removed. But what if this doesn’t happen, and the queue is allowed to exist in this ‘empty’ state while still retaining a value? If many such queues were created and emptied, there would be many unnecessary references as a result.

This implementation thus allows a queue to be ‘empty’ in different ways. If a queue is newly-created, it has no references to anything but the empty list, and requires no memory. Alternately, it can become empty by deletion of all its elements, in which case it actually retains a reference to the last element that was inserted. Moreover, these two situations cannot be distinguished externally, making a program that uses this queue potentially tricky to debug if memory usage becomes a problem.

So Ben does have something of a point. However, we should go on to solve the second part of the exercise anyway. By now the solution may be clear. I mentioned above that the front pointer points to all items in the list. It seems it’s only the printing out of the rear pointer that causes confusion. The queue printing routine is quite short, then: Print only the front pointer (i.e. the list of items it points to). This works, although there is one difficulty that the tests highlight — if a queue is itself an element of a queue, that queue won’t get the benefit of the formatting of print-queue. We are using display on the list items that the front pointer points to, and the display procedure is unaware of how queues are to be printed. It’s not something we can fix without expanding the queue implementation.

Ex 3.22

All of the internal procedures for the queue will be identical to the previous queue procedures; the difference is that since they are all internally defined, we can give them simple names like empty? or insert instead of adding the designator -queue to the end. Additionally, most don’t need any arguments, since they are only operating on the two queue pointers that are defined in the let statement.

The other thing that needs to be done is to redefine the former interface functions to make calls to the procedural queue using the dispatch approach. While this isn’t the only way to implement this, it does make it convenient for us, since we can re-use the same test functions. Note that now if you try to print out this queue directly (without using print-queue) it doesn’t show a longer list, but instead it prints out something describing a procedure, since that is what the variable defined for the queue actually is.

Ex 3.23

For the most part, the deque is the same as a regular queue. We keep track of the items in a list using one pointer, and use another to point to the other end of the list. Insertion from the rear is the same way it was done with the queue, while insertion from the front can be as simple as using cons to add to the list. Deleting from the front is easy as well, since we can just take the cdr of the list. We run into a problem, though, when we want to delete from the rear. If the item at the rear of a list is removed, how can we update the rear pointer? Clearly it just needs to go to the previous item in the list. The previous item in a list is going to be a pair, with the cdr being a pointer. However, we can’t just ‘reverse’ a pointer direction. It only stores where it points; it’s not a thing with a direction we can follow. Furthermore, many pointers can point to the same location, so even if we could back up along pointers, we have no way of knowing which pointer is ‘our’ list without going through the list from the start (which violates the constant-time restriction).

What we need is a list structure that not only tracks forward pointers, but one that tracks the reverse structure as well. We could handle it by keeping a count of the items in each list and a separate reverse list of pointers, but this is prone to errors as there’s more overhead data to keep track of. The approach I eventually went to uses two pointers for each item in the list, one for the next item, and one for the previous. This is commonly known as a doubly-linked list.

Since a Scheme list already stores the ‘next’ pointers (Scheme’s standard list is known more generically as a linked list, since each item is linked by a pointer to the next one), we just need to store a pair containing the queue item and a pointer to the previous list. Of course, a pair in which the cdr points to another pair is in fact a list-like entity. In this case, though, it will point to the previous entry in the list, whose next pointer will lead back to the same pair, including the reference back again. This is the potentially cyclic structure that the footnote in the text warns about. In DrRacket at least, it actually isn’t a problem to display it directly since the interpreter can handle cycles in lists (it prints out a number reference each time a cycle would be printed, and then adds that reference as a label to where the cycle ‘starts’).

The implementation of insertion mostly mirrors that of the pair version of the queue. Something is added to the list. The difference is that we do not add just the item, but a new pair containing the item and a ‘previous’ pointer (the ‘next’ pointer being handled by Scheme). Here are the insertion procedures:

(define (front-insert-deque! deque item)
  (let ((new-entry (cons item '() ))
        )
    (if (empty-deque? deque)
        (insert-first-entry! deque new-entry)
        (let ((new-flist (cons new-entry (forward-list deque)))
              )
          (set-cdr! (car (forward-list deque)) new-flist) ; Set the new previous value for the old head
          (set-forward-list! deque new-flist ) ; set the forward list
        )
        )
    deque
    )
  )

(define (rear-insert-deque! deque item)
  (let ((new-entry (cons item (rear-pointer deque) ))
        )
    (if (empty-deque? deque)
       (insert-first-entry! deque new-entry)
       (let ((new-tail (list new-entry))
                )
           (set-cdr! (rear-pointer deque) new-tail)  ; Add to the end of the list
           (set-rear-pointer! deque new-tail)        ; Update the rear pointer
          )
          
        )
    deque
    )
  )

When inserting at the front, the ‘previous’ pointer is an empty list, but we have to update the former first entry’s ‘previous’ pointer to point to the new head. When inserting at the rear, the former rear pointer will be our new tail’s ‘previous’ entry, so we create those references, and then add the new entry to the end using set-cdr!. In both cases, starting from an empty queue is treated as a special case, since it sets both the front and rear pointers to the same single entry (this is the only time the two pointers are at the same location and need to be updated together).

Deletion from the front is essentially the same as for the queue, since we can just set the new head to the cdr of the list. Rear-deletion needs to ‘back up’ the rear pointer, but also ensure to ‘empty’ the list if it has been deleted all the way to the front.

(define (rear-delete-deque! deque)
  (if (empty-deque? deque)
      (error "Rear-delete called for empty deque.")
      (if (eq? (rear-pointer deque) (forward-list deque))
          (begin
            (set-forward-list! deque '())
            (set-rear-pointer! deque '())
            )
          (begin
            ; Back up the list to previous, then remove this entry.
            (set-rear-pointer! deque (prev-entry (rear-pointer deque)))
            (set-cdr! (rear-pointer deque) '()) 
            )
          )
      )
  deque
  )

If the list is not empty after rear-deletion, updating the rear pointer is accomplished by taking the ‘previous’ pointer from the entry being deleted.

In both cases, we finish by nulling out the ‘next’ pointer or ‘previous’ pointer at the tail/head, depending on which end of the list was modified.

Solutions 3.3.2.