@ddw_music All that stuff about instruction pointers and the like was me getting turned around and falling back onto Fourth because that is where my mind goes when I think about stacks. In pd there is no instruction pointer so never any need to return or backtrack or goto. In pd's core, every internal and external object is a literal OOP object and the inlets and outlets are methods of that object. When we create a new object pd creates a new C object of that type and makes an entry for it in glist with its pointer and UI details; when we connect a wire to its outlet pd retrieves the pointers to those objects from the glist and then goes through the outlet method. I am not quite sure how it deals with reaching the end of the branch, I suspect that the last object always has its outlet method run to point it at the branch point and when we append a new object pd just passes that to the new object when it updates the previous end of chain object's outlet method to be the new object.

Some details there might be a tad off, I am not quite good enough with C pointers to really follow pd's source yet, but I am fairly sure that is the mechanics of it. I have no idea about how Max handles this stuff but I would assume it is quite similar.

@FFW said:

By the way, it's also the order the process stack is filled because the full tree is flatten before it computes

Is there a process stack? Can you tell me where to look in the source for it? What is actually on this stack? Is my above reasoning regarding the patch just being a chain of objects incorrect? The patch being a chain of C objects explains why we can't turn off message rate and what happens when pd is running out of cpu but I have not quite grasped how pd's scheduler actually works. I'm guessing my previous post is difficult for a non-native English speaker since my grasp is not great and my explanation is probably not the clearest and I am not sure how well you know pd's internals either. I am almost at the point where I will post on the mailing list to get a response from the devs but I want to get enough of it that my post is not just a very verbose way of saying "I don't get this, explain the entire inner workings of pd for me!"

@oid "Process stack" is my own term to describe how orders arrive at the processor. I'm thinking at low level, below the C one.
Let's consider this tree and translate it in pseudo-assembly or pseudo-forth:

: BANG
push bang to stack

: MESSAGE_One
pop stack if bang push "One"

: MESSAGE_Two
pop stack if bang push "Two"

: PRINT
pop stack, send to console


: RUN
BANG MESSAGE_One PRINT BANG MESSAGE_Two PRINT

RUN

Trigger is unused at run time, it's only used at "flatten" time to put the methods in the right order. the :RUN content is the process stack I talk about.

However audio tree is flatten to create a DSP chain but maybe the control tree is not…

@FFW I sort of thought you meant something like that but wasn't sure. I don't think message rate stuff is flattened and can't find anything in the source but I don't really know, I just don't see much advantage in doing it with how slow and simple message rate is. Thanks for the clarification.

@oid said:

@ddw_music In pd there is no instruction pointer so never any need to return or backtrack or goto.

You absolutely must backtrack in the case of any object that has multiple outputs. Backtracking is most straightforwardly done with a stack.

A stack is only a data structure that defines two operations: add something new at the end (push) and take the last item off of the end (pop) -- last in, first out. "Stack" doesn't define what it should be used for. It may be data, as in FORTH; it may be execution frames; can be anything.

If necessary, I could find it in the source code later, but let's assume that Miller Puckette is no fool, and he knows that tree traversal is best done with a stack, and that he isn't going to waste time trying to implement some alternative to a stack because of a preconception that stacks are for x or y but never z (and further, that he wouldn't post "stack overflow" errors to the console if that was misleading).

I am not quite sure how it deals with reaching the end of the branch...

I'm also not sure of the implementation details in C (don't really need to be), but if each object gets pushed onto a message-passing stack, then it's easy: when this object is done, pop an object off the stack and see if it has outputs that haven't been issued yet; then issue them, or if there are none, pop again and repeat until the stack is empty. Because a stack is LIFO, this is always (literally!) backtracking.

If you've ever used Max's graphical debug mode: it literally shows you the message-passing stack in a window. I'll admit that I don't have the line-number evidence to show exactly how pd does it in C, but I'm not making this up...

Trigger is unused at run time, it's only used at "flatten" time... However audio tree is flatten to create a DSP chain but maybe the control tree is not…

I'm quite sure there's no flattening for control objects. (See Max's debugger, or I bet pd's trace mode will show the same.)

Edit:

trace: bang 
trigger: bang      -- not flattened
message: One 
print: One
trigger: bang      -- and, after doing "One," it backtracked to here
message: Two 
print: Two
backtrace:  -- what happened before the [trace] object?
bng: bang 

Note that you don't know "what happened before the [trace] object" without a stack

Again, if I'm really saying anything controversial, when time permits I can go diving into pd's sources and find the evidence. But IMO the [trace] output is enough.

hjh

@ddw_music I never said pd did not have a stack, I said that I did not think it had a RETURN stack. I don't think I can reasonably respond to your post without risking more confusion.

@oid Perhaps I owe an apology for an excessively critical post -- I can see that I was a bit too heated.

Perhaps part of the problem in this thread is trying to find terminology without agreeing on terminology -- I'm using some terms in a way that you disagree with, or might be misunderstanding to some extent, and vice versa.

I think some of the things that have been said in this thread are misleading in some ways. Message-passing along patch cables isn't a goto -- it just isn't. Gotos have been discouraged for a long time because they're messy. Overuse produces spaghetti code, and goto-heavy code is hard to debug because gotos are history-less -- there's no backtrace to see how you got into a bad place. Pd message passing keeps all the history until you reach the end of the chain. Stack traces are a characteristic of procedure/function calls -- not a characteristic of gotos.

I do see that Pd doesn't use a stack for returning data to a caller. But there have been some statements that seem to go beyond that, for instance, "without a return stack we can't actually return" -- that's true, we can't return data but execution can and does return back to an object that was previously touched.

Again, probably a lot of this is about terminology -- for example, when I used the term "procedure call," that isn't the normal way that Pd users talk about message passing, so there's a bit of "well that doesn't make sense"... but I think the behavior of Pd control objects lines up very closely with the behavior of procedure calls, and I think some of the resistance to this idea has been overstated to some extent or another. (Likewise, to suggest that you totally rejected the idea of a stack is a considerable overstatement -- which I certainly have to retract.)

So I am sorry about getting a bit punchy there -- at the same time, I'm a bit bewildered why so many things I've tried to say in this thread seem to have gotten a "well, no, that's not it" where I guess I hoped for a "hmm, that's interesting, have you considered?"

hjh

@ddw_music said:

Gotos have been discouraged for a long time because they're messy.

Hmm, that's interesting, have you considered Java's use of gotos? They're structured, provide a convenient way for exiting deeply nested loops, and feel similar to Java's exception framework.

Never mind, I just couldn't resist. Carry on.

@jameslo said:

Hmm, that's interesting, have you considered Java's use of gotos?

Nice one well, there's a time and place for everything. There are gotos in SuperCollider's C++ codebase, iirc mainly in the long switch blocks in the bytecode interpreter. I guess... it's like second inversion triads. In conventional harmony, there are a few legit ways to use them, but otherwise, don't; same for gotos.

hjh

@ddw_music

grep " goto " pd-0.55-1/src/* | wc -l
283

There might be one or two comments in there but those are predominately literal gotos. Goto being discouraged is a holdover from BASIC which originally only had goto for moving about in code, it had no functions and literally executed code line by line, as BASIC developed and got other ways to control execution they discouraged the use of goto. In any language with functions or objects etc there is no need to discourage the use of goto since no one is going to try and control program execution through goto for any reason other than an academic exercise. A goto is just telling the IP to goto a remote place in the program code instead of the next instruction, happens everytime you run a function. The most basic implementation of a function:

function f (a b) {  -- push current address to return stack, pop a and b from data stack, set a and b, goto f
    c = $a+$b -- execute f
    return $c -- push c to data stack, pop address off return stack and goto it
}

Generally stacks only hold one data type so we would also have to set the return type in the function header function int f (a b) so return knows which stack to push to. Higher level languages just do all this stuff for you. In pd it would be the outlets which are the gotos, outlets are structs which hold pointers to tell pd where to goto next. Possibly the pointers in the outlet struct might just be used for telling the GUI how to draw the wires, depends on how it is implemented and I can think of at least a half a dozen different ways it could be implemented to the same ends. If the stack only holds pointers to objects it is easy for pd to function without a return stack, when it hits a branch it pushes the pointer for the branch, goes down the branch pushing the pointer for each object, pops each to execute (possibly each being another goto) finally popping the return and does the goto to the branch point to do the next branch. The object way I outlined above accomplishes the same thing but I believe it would be a bit more efficient, in that case the stack could be a data stack or a pointer stack which also holds pointers to data.

Back when I was last trying to sort this out I ended up digging into [trace], it actually has its own stack (possibly two, did not deeply analyze it since it was not what I was looking for). When you turn tracing on it enables tracing in EVERY object on the canvas and they all send their messages back to [trace] which puts them on its stack. This is why enabling trace slows down message passing, also why it took so long for [trace] to get implemented, not so simple as just printing what is on the stack. I think the second stack in [trace] might be a pointer to the pd stack and it uses pd's stack to determine which messages to print and maybe gets part of its data from the stack but as I said, I did not dig into it too deeply and that was awhile back. I suspect pd's stack is a pointer stack but I am not sure if it only holds pointers to objects or also pointers to data, if the latter single stack returns could be more troublesome.

there are a few legit ways to use them, but otherwise, don't; same for gotos.

In my experience they are generally used for blocks of code which you need to reuse often but do not work well within the context of a function or the like, would need to be broken up into dozens of small functions which would make the code difficult to read and inefficient to run because functions have good deal of overhead and generally have scope and limited in what they can return. Gotos also have the advantage of being able to return to somewhere other than from where they were called from, which can also help makes things more efficient, depends on the language and how things are implemented. In some languages goto is slightly different in different contexts, in a loop it is the same as break and goto and in a function it is return and goto, etc.

@oid Thanks. I think this confirms that you and I are talking at orthogonal purposes. What I've been trying to say is that one can use a linked list to implement a stack and use that stack to organize gotos into procedure-call behavior, or one could use a dedicated Stack data type and implement the same behavior using only structured control flow, and the behavior in both cases is that of a procedure call. Pointing out that the one is just a linked list and gotos doesn't make it not procedure-call behavior.

I.e. we're focusing on different levels of abstraction. Or, in answer to your earlier question, "are they really procedure calls or is that just conceptual?" -- I'm mainly interested in the conceptual aspect, yes, and you're mainly interested in the concrete implementation. So any confusion/frustration stems from talking past each other.

hjh

@ddw_music said:

at the same time, I'm a bit bewildered why so many things I've tried to say in this thread seem to have gotten a "well, no, that's not it" where I guess I hoped for a "hmm, that's interesting, have you considered?"

Forgot to address this. It was the stack confusion, your thinking that I meant there was no stack made your posts come across as non-sequitur and saying I am wrong while not explaining why, just explaining your logic in increasingly condescending ways which made it seem like you completely misunderstood what I said and were stubbornly just saying "I am right." I probably came off the same to you. But that was not the case, we were just having different discussions and not realizing it. Hopefully my previous post where I tried to make no assumptions about anything and use it towards both our views will clear things up so we can get back on track?

I suspect we also have abit of a personality clash and take things from each other slightly askew from what we intended, generally not much of an issue and we just move on.

Edit: and you understood that despite my forgetting it in the previous post

@oid Agreed, yes, let's move on.

hjh

BTW though: I hadn't looked closely at the sources earlier, so I was conjecturing. Looked just now. If we take, say, "unpack" as an example of an object that typically has multiple outlets, and see how it responds to a list:

in m.connective.c:

static void unpack_list(t_unpack *x, t_symbol *s, int argc, t_atom *argv)
{
    t_atom *ap;
    t_unpackout *u;
    int i;
    if (argc > x->x_n) argc = (int)x->x_n;
    for (i = argc, u = x->x_vec + i, ap = argv + i; u--, ap--, i--;)
    {
        t_atomtype type = u->u_type;
        if (type != ap->a_type)
            pd_error(x, "unpack: type mismatch");
        else if (type == A_FLOAT)
            outlet_float(u->u_outlet, ap->a_w.w_float);
        else if (type == A_SYMBOL)
            outlet_symbol(u->u_outlet, ap->a_w.w_symbol);
        else outlet_pointer(u->u_outlet, ap->a_w.w_gpointer);
    }
}

... where each output value calls either outlet_float() or outlet_symbol() or outlet_pointer(). It'll move to the next outlet when the outlet_ function returns.

m_obj.c:

void outlet_float(t_outlet *x, t_float f)
{
    t_outconnect *oc;
    if(!stackcount_add())
        outlet_stackerror(x);
    else
        for (oc = x->o_connections; oc; oc = oc->oc_next)
            pd_float(oc->oc_to, f);
    stackcount_release();
}

OK, check for stack overflow and then call pd_float() for each connection from that outlet. (_bang, _symbol, _pointer are similar.)

m_pd.c:

void pd_float(t_pd *x, t_float f)
{
    if (x == &pd_objectmaker)
        ((t_floatmethodr)(*(*x)->c_floatmethod))(x, f);
    else
        (*(*x)->c_floatmethod)(x, f);
}

Get a reference to the next object's floatmethod function, e.g. and call it: a method handler --> an iterator over connections --> a connection handler --> another object's method handler, at which point the cycle recurs.

So the way that it backtracks seems to be simply that e.g. outlet_float() returns and the method handler resumes where it left off: normal tree-traversal recursion using C's call stack (without data return, as these are all void).

Gotos do appear in the Pd source but it looks like the vast majority of these are used for early-exit or for input validation before performing some operation -- goto error, goto fail, goto doit, etc. I don't see them in the message-passing functions. (What I also don't see in the message-passing functions is an explicit stack of objects/connections -- stackcount_add() is just a global counter, no real push/pop -- so if I guessed that pd keeps its own stack of objects visited, that was a wrong conjecture.)

hjh