Infinite recursion in doubly linked list implementation

Question

I am trying to implement a queue as a doubly linked list. However, the enqueue function goes into infinite recursion when I try to enqueue a second node, I can't seem to figure out what's causing it.

(defstruct node
  value
  (next nil)
  (previous nil))



(defstruct (queue (:print-function print-queue))
  (first nil)
  (last nil))

(defun print-queue (queue s d)
  (do ((node (queue-first queue) (node-next node)))
      ((null node) (format s "~%"))
      (format s "~A " (node-value node))))

(defun enqueue (data queue)
  (let ((node (make-node :value data)))
    (if (null (queue-first queue))
        (setf (queue-first queue) node (queue-last queue) node)
        (setf (node-previous node) (queue-last queue)
              (node-next (queue-last queue)) node
              (queue-last queue) node))))

EDIT: Problematic test case

(setf queue (make-queue))
(enqueue 3 queue)
(enqueue 4 queue) ; this call never terminates and blows up the stack

The last statement on CLISP causes a * - Program stack overflow. RESET

on SBCL it just goes into an infinite loop and I have to exit SBCL

Answer 1

Well, you still haven't really looked at the error. ;-)

If you use SBCL:

0] backtrace

...
11898: (SB-KERNEL::%DEFAULT-STRUCTURE-PRETTY-PRINT #1=#S(NODE :VALUE 4 :NEXT NIL :PREVIOUS #S(NODE :VALUE 3 :NEXT #1# :PREVIOUS NIL)) #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {10001ACA23}>)
11899: ((LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT) #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {10001ACA23}>)
11900: (PRIN1 #1=#S(NODE :VALUE 4 :NEXT NIL :PREVIOUS #S(NODE :VALUE 3 :NEXT #1# :PREVIOUS NIL)) NIL)
11901: (SB-IMPL::REPL-FUN NIL)
11902: ((LAMBDA NIL :IN SB-IMPL::TOPLEVEL-REPL))
11903: (SB-IMPL::%WITH-REBOUND-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-IMPL::TOPLEVEL-REPL) {1002ACB00B}>)
11904: (SB-IMPL::TOPLEVEL-REPL NIL)
11905: (SB-IMPL::TOPLEVEL-INIT)
11906: ((FLET #:WITHOUT-INTERRUPTS-BODY-58 :IN SAVE-LISP-AND-DIE))
11907: ((LABELS SB-IMPL::RESTART-LISP :IN SAVE-LISP-AND-DIE))

It's not your function which causes this.

As you can see the error happens in printing the result. You see in the backtrace that the function PRIN1 is used to print a node structure. Your function already returned a result, which now needs to be printed in the REPL.

Your function returns a circular data structure and Lisp tries to print it. Then it goes into an infinite loop.

You need to tell Lisp, that it should deal with circular data structures in the printer.

Use

(setf *print-circle* t)

and try again.

A bit style guide:

• generally use CLOS classes instead of structures
• provide a custom printer for each structure, especially those with circularities
• return meaningful results from functions