1. 12

  2. 5

    Maintaining a stack by yourself in code seems rather unfortunate (look at how much longer the code is than the generator version), and very much points to a language deficiency. There’s no excuse for a function call being slower than a list access, and tail call support would remove the stack depth issue.

    1. 6

      Tail call support wouldn’t get rid of the need for a stack here because this function calls itself more than once aka “isn’t tail recursive”.

      I would try to add the code from the article with comments showing where it is not tail recursive with comments, but pre-formatted text is not working for me at the moment.

      1. 2

        You’re right. I find it hard to believe that stack depth would be an issue at least for a balanced tree, but again if it is Python really should offer a way to have deeper stacks in the language rather than have users end up writing their own stack emulation.

        1. 5

          So this precise issue was the root of a performance problem in the clojure.tools.emitter.jvm project which I used to work on. Essentially the code generator worked by emitting OpcodeList = List[Either[OpcodeList, Opcode]]. The resulting structure was then traversed one opcode at a time, which meant that you had to recursively call next() on arbitrarily many lazy generator terms in order to get the next opcode you wanted to emit.

          Using the stack of iterators pattern described here becomes an optimization then, because you elide n-1 calls to next() which have to walk back down the stack of iterators to the bottom-most iterator in order to get the next actual opcode you want. Because you’re traversing back up and down many many nested stateful iterators, there isn’t a way to optimize this recursion ala with TCO because you still have to go down n-1 iterator structures to figure out what buffer you’re actually taking the next() of.

          In comparison with the stack of iterators pattern, your next() just needs to peek the top of the stack, take the next from that, and recurs only if it’s another iterator structure. This means you traverse down the entire depth of the tree precisely once, rather than doing so once for every leaf of the tree.

          1. 5

            there isn’t a way to optimize this recursion ala with TCO because you still have to go down n-1 iterator structures to figure out what buffer you’re actually taking the next() of

            The mutable variable in the example stack-of-iterators code, or the one you’d get from a clojure loop/recur, is what provides that benefit. In fact, Clojure performs this optimization for nested LazySeq objects: https://github.com/clojure/clojure/blob/e547d35bb796051bb2cbf07bbca6ee67c5bc022f/src/jvm/clojure/lang/LazySeq.java#L58 - Note that it flattens lazy seq thunks recursively and elides that work on future .seq() calls via the synchronized mutable field.

            Sadly, the optimization is lost if you’re making your own nested structures because you have the vector -> seq -> vector loop going on. You could recover it a mutable variable for the top element on the stack. That’s precisely what TCE would provide as long as you could ensure that the recursive call was actually in tail position. Sadly, the ‘next’ interface is not ideal for that. You need something that returns both the next item and the continuation. So instead of (next seq) -> seq, you’d want (uncons seq) -> [head tail]

            In the case of tools emitter, you could probably also have achieved this effect without mutability via an automatic splice-on-construction collection type. Instead of [:blah … [:foo …] …. :bar] you’d have (spliced :blah … (spliced :foo …) …. :bar) and pay that cost on construction.

            1. 1

              Is there a standard name for a list uncons that returns an option/maybe? It’s a function I’ve often found myself wanting.

              1. 1

                Pattern matching and related constructs generally eliminate the need to name it. However, I’d just call it uncons.

                In Clojure, you can write (if-some [[head & tail] seq] …), but if I recall correctly, the underlying implementation still always uses first/next. Haskell fails better here with the colon/cons syntax in patterns, but trades a sequence abstraction for a concrete list type (at least without various extensions).

                1. 1

                  I’m thinking Scala here, and I’d prefer to avoid the match/case syntax entirely if possible since it’s very easy to use unsafely.

    2. 3

      Excellent way to implement DFS when you have a language with iterators or iterator-like things.

      What I like especially is that this can be changed to a BFS by changing 2 lines of code; the pop and the stack[-1].

      1. 1

        As far as I can tell, this is just working around the fact Python’s iterators don’t compose. In Haskell:

        data Tree a = T a [Tree a]
        dfs :: Tree a -> [a]
        dfs (T x xs) = x : concatMap dfs xs

        Or even better:

        {-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
        import Data.Foldable
        data Tree a = T a [Tree a]
          deriving (Functor, Foldable, Traversable)
        dfs = toList

        Am I missing something?