(def instruction-label first)
(defn ->label+instruction [raw-instructions]
  (reduce (fn [res part]
            (if (symbol? part)
              (conj res [part nil])
              (let [last-label (instruction-label (last res))]
                (conj res [last-label part]))))
          []
          raw-instructions))

(comment
  (->label+instruction '((assign)
                         label-one
                         (test)
                         (branch)
                         label-two
                         (goto))))

=> [[nil (assign)] [label-one nil] [label-one (test)] [label-one (branch)] [label-two nil] [label-two (goto)]]

Instead of using last, I would probably track the current symbol in the accumulator part.

Using peek instead of last would be much faster -- last will walk the whole of res every time.

(second (reduce (fn [[sym res] part] 
                  (if (symbol? part) 
                    [part (conj res [part nil])] 
                    [sym (conj res [sym part])])) 
                [nil []] 
                raw-instructions))

^ @stopachka

Great point, thanks Sean! cc @joeaverbukh

(untested but I think that'll work)

works great!

(defn label-idx [transformed-instructions label]
  (->> transformed-instructions
       (map-indexed (fn [i x] [i (instruction-label x)]))
       (filter (comp (partial = label) last))
       ffirst))

(comment
  (label-idx '[[nil (assign)] [label-one nil] [label-two nil]]
             'label-two))
; => 2

(def indexed (partial map-indexed vector))

(defn positions [filter-fn coll]
  (->> coll
       indexed
       (filter (fn [[_ v]] (filter-fn v)))
       (map first)))

(defn label-idx [label instructions]
  (first (positions (comp (partial = label) instruction-label)
                    instructions)))

(comment
  (label-idx
    'label-two
    '[[nil (assign)] [label-one nil] [label-two nil]]))

@stopachka That's a case where SICP is somewhat hampered by only having lists as data structures. In Clojure, you'd probably use a different data structure, or a pair of data structures, to efficiently track where labels referred.

The whole of clojure.contrib went away between Clojure 1.2 and 1.3. Some parts of it became new Contrib libraries, the rest of it just fell by the wayside. Here's some of that fallout: https://clojure.org/dev/contrib_history

Regarding searching for the first index of a given label, I'd probably use reduce and return (reduced idx) when I hit a match.

(defn label-idx [label instructions]
  (reduce (fn [idx [sym instr]]
            (cond (= label sym) (reduced idx) 
                  (= ::sentinel sym) (reduced -1)
                  :else
                  (inc idx)))
          0
          (conj instructions [::sentinel nil])))

Or you could use a local gensym to create a more unique sentinel item...

Thanks Sean! Makes sense — will play with keeping an auxiliary data struct for labels — something like label->idx! Makes sense

If you get time, thoughts on:

(defn extract-labels [raw-instructions]
  (rest (reduce
          (fn [[idx label->idx instructions] part]
            (if (symbol? part)
              [idx
               (assoc label->idx part (inc idx))
               instructions]
              [(inc idx)
               label->idx
               (conj instructions part)]))
          [-1 {} []]
          raw-instructions)))

(comment
  (let [[label->idx instructions] (extract-labels '((assign foo (const 1))
                                                    label-one
                                                    (test (op =) (const 1) (reg foo))
                                                    (branch (label label-two))
                                                    label-two
                                                    (assign bar (const 2))))]
    (println label->idx)
    (println (map-indexed vector instructions))))

a. a mapping of label->idx 
b. a cleaned up list of instructions

Yup, that's probably a good way to deal with it. I suspect there's a more optimized way that could rely on the shared nature of persistent data structures... Probably a single pass that produces an actual list of instructions (not a vector) such that you could have your map from labels to actual code so you could naturally iterate through the instructions steps and have the label lookup return the sequence of instructions to continue executing. You'd probably need to construct that via lazy-seq to avoid blowing the stack since you'd essentially process it recursively.

Ah, very interesting! Thanks Sean