Hi folks,

This is going to be a weird and long post, because I am walking through my thinking as much as I am asking questions. Sorry for the length in advance.

I've recently become fascinated with the many possibilities afforded by the list-abs library, and what strikes me at is that [list-drip] seems to be at the heart of most of them. For those of you who don't know, [list-drip] works by separating (aka "dripping") an incoming list into its individual elements (atoms?). This allows you to do a bunch of operations on these elements before repacking them into a new list. For example, [list-compare] functions like [==] but for lists by checking each list's elements against each other to give out a binary yes or no answer. And of course, [list-drip] is at the core here.

I would like to really figure out the logic behind [list-drip], but the help file (well, really the abstraction itself) is deceptively simple. This is because [list-drip] itself is but an abstraction based on the clever use of [list-split] (which is not an abstraction but an external) and some strange binary math and triggering mechanisms that I don't understand.

Here's the [list-drip] extraction itself:

I'll just talk about this abstraction and ask questions along the way.

Here's the first part. Pretty simple. [trigger] is passing the entire list on, and then sending a bang. This seems weird but I've heard that pd will take care of all the operations starting at the right outlet of trigger first, so the bang is guaranteed to come after the list has been "dripped."

Here's the second part, where we have [list split] doing a binary "less than" operation on the list. "If the list is less than 2 elements long, it gets sent to the outlet and the [spigot] closes, else, open the spigot." This [trigger] then passes a copy of the list onto [spigot] which is either open or closed based on the above result.

Ok now here is where things start to get crazy. The list is now fed into two identical [list split] mechanisms with some weird math going on, which are also feeding back into the top of the second [trigger].

Let's break this down really quick:

First, we get the length of the list, then we feed it into [>> 1]. With some research in pd and the on the web, I come to the conclusion that we are basically dividing (integer division) by 2. This is setting the point for where [list split] outputs a list with only a certain number (but always half) of elements (using the first outlet). As I said before, this result is being fed back into the second [trigger].

So I think basically what's happening is this:

...where the rest of the list is either exactly half the total list length (if it's an even number) or half + 1 (if the total length is an odd number of elements).

So we have two "loops" going on here, where on operates on the first half of the list (will call this the "red" loop, and the other operates on the second "green loop".

Now in terms of trigger ordering, what is happening here? Are we constantly triggering the red loop until there are no more operations, and then moving on the green loop? And what does this mean in the context of the patch? I'm confused about how [trigger] acts in these situations with many nested loops.

To troubleshoot, I attached a print the outlets of both the red and green **[list split]**s, and sent the list [a b c d 1 2 3 4( to [list drip]. Here's the output from the console:

first half: symbol a
second half: symbol b
first half: list a b
first half: symbol c
second half: symbol d
second half: list c d
first half: list a b c d
first half: 1
second half: 2
first half: 1 2
first half: 3
second half: 4
second half: 3 4
second half: 1 2 3 4

To me this output looks like it was printed backwards. Is there some weird interaction between [trigger] and [print] going on?
Furthermore, how is the output of [list drip] organized so that each element is output in it's sequential order? How does the green loop know to wait for the red loop to finish?

@rjp9 yup, basically you put items into a stack and take them out of the stack the reverse order, so it is used to remember what needs to be done next.

an example, the "call stack" is the term used for an area of RAM that stores which function a program is in, so if you have a "main" function:

main(int argc, char ** argv) {
       somefunction()
       someotherfunction()
}

and the functions look like:

somefunction() {
       int cat
      cat = somethirdfunction()
}
someotherfunction() {
       float dog
     somefunction()
}
somethirdfunction() {
       char lettera
         -- do nothing
}

then when the program runs the call stack will look like this at various times:
when it starts main:

main -- has space for function info and argc, argv

when somefunction is called:

main (bottom of stack)
      somefunction - top of stack - has space for function info and an integer (cat)

then somethirdfunction is called and cat's value is set, while in somethirdfunction the stack looks like this:

main (bottom of stack)
      somefunction - middle of stack
            somethirdfunction - top of stack, has space for lettera

since somethirdfunction doesn't do anything, it returns:

main (bottom of stack)
      somefunction - middle of stack

some function exits:

main (bottom of stack)

and someotherfunction is called:

main (bottom of stack)
      someotherfunction - middle of stack

since someotherfunction calls somefunction which calls somethirdfunction, the call stack will eventually look like this when in somethirdfunction here:

main (bottom of stack)
      someotherfunction - second member of stack
            somefunction - third member
                  somethirdfunction -top of stack

and this whole time the "automatic variables" and their values are remembered in the function info. This includes arguments to the function (like in trigger_anything) and other variables declared at the top of each function. and you can have a function call itself too, and have itself in it's own call stack eventually, as in recursive cases like this.
in this case, the stack would be more like, if you have 8 elements:

trigger_anything
 split off first 4 elements
    trigger_anything
      split off first 2 elements
        trigger_anything
           split off first element
             output first element
          split off second element
             output second element
      split off 3rd and 4th elements together (in 2nd trigger_anything)
         trigger anything
           split off 3rd argument
             output 3rd argument
          split off 4th
             output 4th
     split off last 4 elements (from 1st trigger_anything)

and repeat the exact same thing with the last 4

wikipedia has a good page on it https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

To me this output looks like it was printed backwards. Is there some weird interaction between [trigger] and [print] going on?

Not a computer science guy either, but I have learned from experience that you can't always trust [print] to represent the order of operations accurately, especially when you have more than one of them. [print] is part of the order of operations, after all, not independent of it.

@LiamG said:

To me this output looks like it was printed backwards. Is there some weird interaction between [trigger] and [print] going on?

Not a computer science guy either, but I have learned from experience that you can't always trust [print] to represent the order of operations accurately, especially when you have more than one of them. [print] is part of the order of operations, after all, not independent of it.

That actually makes a lot of sense when I looked at the output of my print in my original post and after reading @seb-harmonikar.ar 's comments. It looks like pd doesn't just blindly trigger these events but calculates the entire chain of events before processing it, so it knows which result should come out first. Pretty fascinating for a noob like me!

If anyone is curious, I made my own version of [list-drip] that might be a little easier to understand. The only real catch is that the second outlet of [list split] gives a result before the first outlet, so you have to add a few things to force the order of operations:

Hey, rjp9!
Beware that you're 'normal' version of [list-drip] ist not linear, but rather exponential in computation time! This is because Pd will make a lot of copies of the list and you may end up with a stack overflow. Try, for example, sending a long list with a few hundred alements - Pd will most likely crash!
The main reason why list-abs' [list-drip] abstraction makes use of this special algorithm is to keep the computation time linear.
Coincidently, this has been discussed on the Pd mailing list just a couple of days ago, so you may want to have a look: http://lists.puredata.info/pipermail/pd-list/2015-10/111681.html
(Matt speaks about an abstraction that works basically the same way as your 'normal' one)

Cheers

PS: A good (and faster) alternative to list-abs' [list-split] is zexy's [drip].

@Spacechild1 Huh that is really interesting. Thanks for bringing that up.

BTW: As you might have seen in the mailling list, you shouldn't use the iterative approach either:

It gets reeeeally slow for longer lists, but at least it won't give you a stack overflow.
Ironically enough, it was Miller who was suggesting it, but then it turned out that it won't work as expected because of the copying. Miller somehow gave a hint that he might change the behaviour of [list] in a way that it won't make a copy if the left inlet only receives a bang. Then the iterative approach would work fine.

Finally I'd like to point out that list-abs' [list-drip] actually does two tricks: protecting against stack overflow by halfing the lists AND keeping computation time linear by avoiding all the [list objects] that do unnessecary copying. Pretty clever

@Spacechild1 said:

keeping computation time linear

Could you elaborate on what that means and why it is important for noobs like me

Put in a formal way, it means that computation time equals O(n).
--> https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities
I give you a simple example regarding [list-split]: Let's suppose dripping 100 elements would take 0.01 ms, then dripping 1000 elements will take 0.1 ms; 10.000 elements will take 1 ms etc.

I think the algorithm of [list-drip] itself should be actually O(log(n)) but in Pd you'll end up with O(n). At least this is what I've measured... Please anyone correct me if I'm wrong