1
\$\begingroup\$

I’m having trouble understanding an SBCL compiler note about unreachable code in the following function. The referenced code is attempting to push a value into an Lparallel queue: (lparallel.queue:push-queue :stop problems) which appears in line 9 of the function. Commenting out this line produces a clean compile of the function, and there are no other compiler complaints in the program. I assume there is some logical coding error that I’m missing, and would appreciate any insights.

Edit: The function itself (df-bnb) runs a depth-first branch & bound search in state space for a goal condition. Beginning with a starting state it builds a depth-first search tree of open nodes (plus closed nodes if graph search is requested), which are maintained in *open*. The function is composed of two basic parts, one for serial, the other for parallel, operation. The serial part works fine, but the compiler note (concerning line 9) relates to the parallel part.

Each thread runs a separate instance of df-bnb in parallel. When any thread becomes idle (ie, available for work by blocking at line 6), another working thread will split off a part of its current *open* (ie, a subproblem), and put it on a problems queue so any idle thread can pick it up. Following the split, the splitting thread continues with what's left of its *open*. Any thread becomes idle after it completes an exhaustive search of its *open*, at which time it announces it is idle (pushes t into the idles queue), and then blocks, waiting for another subproblem to appear in the problems queue (popping from the problems queue if it does).

When all threads become idle, the last one signals completion (pushes t into the done queue) and tells the next thread to stop by pushing :stop into the problems queue). Subsequent idle threads pop the :stop message, push another :stop message (available for the next idle thread to pop), and return-from their instance of df-bnb. The various instances of df-bnb tasks are previously started in a function which sets up the Lparallel kernel, channel, and queues.

(defun df-bnb (&optional problems idles done)
  ;Branch & Bound DFS sequential search algorithm.
  (setf *search-tree* nil)
  (if ww::*parallel*  ;splitoff an *open* chain for subsequent restart
    (iter
      (let ((*open* (lparallel.queue:pop-queue problems)))  ;*open* is now local for a thread
        (lparallel.queue:pop-queue idles)  ;this thread is no longer idle
        (when (eq *open* :stop)  ;stop received from another stopped thread
          (lparallel.queue:push-queue :stop problems) ;restore stop signal for another thread
          (return-from df-bnb))  ;stop this thread
        (when (persistently-linear done)  ;*open* only linearly expandable
          (next-iteration))  ;cancel this *open*, get next one
        (iter
          (when (and (not (small))  ;don't split if small problem
                     (>= (lparallel.queue:queue-count idles) 1))  ;ie, some threads are idle
            (let ((subproblem (split-off)))  ;split problem
              (lparallel.queue:push-queue subproblem problems)))
          (let ((succ-nodes (df-bnb1)))  ;work a little more on current problem
            (if (and (null succ-nodes) ww::*first-solution-sufficient*)
              (return-from df-bnb)
              (loop for succ-node in succ-nodes
                 do (hs::push-hstack succ-node *open*))))
          (when (finished)  ;is this thread's task complete?
            (lparallel.queue:push-queue t idles)  ;this thread now idle
            (if (= (lparallel.queue:queue-count idles) ww::*num-threads*)  ;all threads idle
              (progn (lparallel.queue:push-queue :stop problems)  ;tell next idle thread to stop
                     (lparallel.queue:push-queue t done)  ;signal all done to main
                     (return-from df-bnb))  ;stop this thread
              (leave))))))  ;return from inner loop to get new problem
    (iter (for succ-nodes = (df-bnb1))
      (if succ-nodes
        (dolist (succ-node succ-nodes)
          (hs::push-hstack succ-node *open*))
        (when (or ww::*first-solution-sufficient* (hs::empty-hstack *open*))
          (return-from df-bnb))))))


; file: D:/Users Data/Dave/SW Library/AI/Planning/Wouldwork Planner/bnb-planner.lisp
; in: DEFUN DF-BNB
;     (ITERATE:ITER
;       (LET ((BRANCH&BOUND-PKG::*OPEN*
;              (LPARALLEL.QUEUE:POP-QUEUE BRANCH&BOUND-PKG::PROBLEMS)))
;         (LPARALLEL.QUEUE:POP-QUEUE BRANCH&BOUND-PKG::IDLES)
;         (WHEN (EQ BRANCH&BOUND-PKG::*OPEN* :STOP)
;           (LPARALLEL.QUEUE:PUSH-QUEUE :STOP BRANCH&BOUND-PKG::PROBLEMS)
;           (RETURN-FROM BRANCH&BOUND-PKG::DF-BNB))
;         (WHEN (BRANCH&BOUND-PKG::PERSISTENTLY-LINEAR BRANCH&BOUND-PKG::DONE)
;           (ITERATE:NEXT-ITERATION))
;         (ITERATE:ITER
;           (WHEN (AND # #)
;             (LET #
;               #))
;           (LET (#)
;             (IF #
;                 #
;                 #))
;           (WHEN (BRANCH&BOUND-PKG::FINISHED)
;             (LPARALLEL.QUEUE:PUSH-QUEUE T BRANCH&BOUND-PKG::IDLES)
;             (IF #
;                 #
;                 #)))))
; --> LET* BLOCK TAGBODY PROGN LET IF PROGN LPARALLEL.QUEUE:PUSH-QUEUE
; ==>
;   BRANCH&BOUND-PKG::PROBLEMS
;
; note: deleting unreachable code
\$\endgroup\$
  • 1
    \$\begingroup\$ This question lacks any indication of what the code is intended to achieve. To help reviewers give you better answers, please add sufficient context to your question, including a title that summarises the purpose of the code. We want to know why much more than how. The more you tell us about what your code is for, the easier it will be for reviewers to help you. The title needs an edit to simply state the task. \$\endgroup\$ – Toby Speight Apr 15 at 8:13
  • 1
    \$\begingroup\$ @Toby Speight, I was hoping this was an easy technical question, but I can see how purpose is important too (see edit). Thanks. \$\endgroup\$ – davypough Apr 15 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.