Call tail in architectures without a call stack
My answer to a recent question about GOTO and tail recursion was phrased in terms of the call stack. I'm concerned that it is not general enough, so I ask you: How is the concept of a tail call (or equivalent) useful in architectures without a call stack?
As the transmission continues, all called functions replace the calling function and are thus tail calls, so the "tail call" is not a useful distinction. There seems to be no equivalent in messaging and event systems, although please correct me if I'm wrong. The last two architectures are interesting cases as they are related to OOP, not FP. How about other architectures? Were the old Lisp machines call-based?
Edit: According to " What the heck: Continuing Passing Style (CPS) " (and Alex below), the equivalent of a tail call while continuing to pass is not called "the called function replaces the calling function", but "the calling function passes the continuation it gave, rather than creating new sequel ". This type of tail call is useful, unlike what I have argued.
Also, I am not interested in systems that use call stacks at the lower level, since the higher level does not require a call stack. This limitation is not relevant to Alex's answer because he writes that other call architectures ( is that the right term? ) Often have a call stack equivalent, not one they have a call stack somewhere under the hood. In case of continued passage, the structure is similar to arborescence , but with ribs in the opposite direction. Call stack equivalents are very relevant to my interests.
source to share
In case anyone other than me is interested in this question, I have an extended answer for another question that also answers this question. Here's a short, loose version.
When a computing system performs subcomputations (that is, a computation starts and must pause while another computation is performed, because the first depends on the result of the second), a dependency relationship naturally arises between the execution points. In a callback architecture, a relation is topologically a path graph . In CPS, it is a tree where every path between the root and node is an extension. When transmitting messages and streaming, it is a set of path graphs. Synchronous event handling is basically messaging. Triggering the count involves extending the dependency relationship, with the exception of a tail call that replaces the sheet rather than adding to it.
Translating tail call to handling asynchronous events is more complex, so consider a more general version instead. If A subscribes to an event on channel 1, B subscribes to the same event on channel 2, and handler B just fires the event on channel 1 (it broadcasts the event across channels), then A can subscribe to an event on channel 2 instead of subscribing B. This is more general because the tail call equivalent requires that
- Channel 1 is canceled when A is subscribed to channel 2
- handlers are self-signed (when called, they unsubscribe)
Now for two systems that don't do sub-computation: lambda calculus (or term rewriting systems in general) and RPN. For lambda calculus, tail calls roughly correspond to a sequence of abbreviations where the word length is O (1) (see Iterative Processes in SICP section 1.2 ). Take an RPN to use a data stack and an operation stack (as opposed to a workflow, operations are ones that have not yet been processed) and an environment that maps characters to a sequence of operations. The tail can correspond to processes with O (1) stack growth.
source to share
"Non-call stack architectures" usually "mimic" one at some level - for example, back in the days of the IBM 360, we used the S-Type Linkage Convention using register scopes and argument lists, denoted by convention as defined by universal registers.
So the "tail call" can still make a difference: whether the caller needs to store the information needed to resume execution after the calling point (once the called function is finished), or whether it knows that after the function is executed, there will be no execution after the calling point and why just reuse the caller's "call info" instead?
So, for example, optimizing a tail call might mean not adding the continuation needed to resume execution on whatever linked list is used for that purpose ... which I like to see as "simulating the call stack" (at some level, although this is obviously a more flexible convention - don't want the fanboys keep jumping all over my answer ;-).
source to share