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?

it's a recursive thing: I'll walk through part of an example:
say the list has 5 elements.
The list comes in, and goes into the open spigot.

so at this point the [t a a a a] is sending a list of 5 elements. the following is what happens to the right [list-split] at this moment:
the first 2 elements of the list are sent back to the upper trigger, and go back into the spigot, where they are split again into lists of length 1. element 1 goes back into the upper trigger and out of the outlet, and then the second does as well.

All of this happens before the list of 5 elements is even sent to the left [list split], because of the trigger. A similar thing occurs:
the last 3 elements of the 5-element list are sent to the upper trigger and into the open spigot, and then the first element of that is split off and sent out the outlet. Then the last 2 elements are sent through the spigot and split, and are sent out in order.

The crucial thing to understand is the recursive nature; it has to do with the depth-first message passing in pd.
The first half of the list is split off before the second half, and sent to be split in half again before the second half of the original list is even processed. So it goes the first half of the first half of the first half, etc. until the first element is sent to the outlet. Then it goes back up the "stack" to the second halves of the lists that it missed in doing the first half every time (this happens because of the triggers). So after the first element is sent, the second element is sent. After that, elements 3 and 4 (in a list since they weren't even processed to be split yet) are split and sent out in order. then elements 5-8, which are still in a list, are sent back and processed in the same manner.

Hopefully that's somewhat clear..

(rambling extra stuff:)
From a "computer science" perspective, you could say that you process the first half and put the second half on a "stack" , and then go into the first half, split it in half, put the second half on the "stack", etc. And then after the 1st element is put out, repeat that process for each thing on the top of the stack until you end up with 1 element:

in "pseudocode" (with a datatype "list" and an assumed stack):

function splitlist (list inlist) {
         list firsthalf;
         list secondhalf;
         if length(inlist) == 1 then {
                     output(inlist); -- pass the element
                     if stack exists then {
                            secondhalf = popstack(); -- get the next thing on the stack
                            splitlist(secondhalf); -- call the function recursively
                     }
        } else {
                   firsthalf, secondhalf = split(inlist); -- split the list, pass to variables
                   pushstack(second half); --- push the second half onto the stack
                   splitlist(firsthalf); -- call the function recursively
         }
}

I think that in reality most of this is taken care of in the computer's call stack, though not completely sure on how the memory for the lists is dealt with

@seb-harmonik.ar said:

The crucial thing to understand is the recursive nature; it has to do with the depth-first message passing in pd.
The first half of the list is split off before the second half, and sent to be split in half again before the second half of the original list is even processed. So it goes the first half of the first half of the first half, etc. until the first element is sent to the outlet. Then it goes back up the "stack" to the second halves of the lists that it missed in doing the first half every time (this happens because of the triggers). So after the first element is sent, the second element is sent. After that, elements 2 and 3 (in a list since they weren't even processed to be split yet) are split and sent out in order. then elements 4-8, which are still in a list, are sent back and processed in the same manner.

Brilliant explanation. So basically we're constantly breaking down the list in half until we can't anymore, and then we pass on the individual elements? So is it trigger the object that is somehow keeping track of all this under the hood?

@seb-harmonik.ar said:

I think that in reality most of this is taken care of in the computer's call stack, though not completely sure on how the memory for the lists is dealt with

Ah just read your edit sorry!

Yeah this is what confused me at first because I couldn't tell by looking at the patch where at the list fragments were being stored when they weren't being worked on. So yeah all this is probably going on in computer memory land rather then pd land where we "actually" store lists in [list] objects (obviously that's not what happens but it's makes it easy to visualize with pd)

yes I've been trying to figure out how pd actually allocates and de-allocates lists, so far I can't find it anywhere. However, within the structure of the list-drip patch, what happens is that the computer's call stack stores the pointer to the list elements and the number of elements it is holding (as arguments to the trigger_anything() function), so I don't think things are actually being changed in memory, the pointers to the list atoms and number of atoms to pass are being changed but stored on the computers call stack, and at each depth of the call stack the trigger has the same arguments stored in it's function arguments for trigger_anything.

@seb-harmonik.ar Awesome info. Thanks a ton for your help that really demystified things for me.

@seb-harmonik.ar said:

From a "computer science" perspective, you could say that you process the first half and put the second half on a "stack" , and then go into the first half, split it in half, put the second half on the "stack", etc.

I am definitely not a computer science person by any means, so forgive me if this is a stupid question, but is a "stack" essentially what is allowing pd to "see into the future" and organize calculations, finish some before others, etc?

@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