tag:blogger.com,1999:blog-10770855.post114126662846397313..comments2024-03-28T03:20:57.393-04:00Comments on The Little Calculist: The call stack is not a historyDave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-10770855.post-15929758336973241732012-12-18T03:31:46.182-05:002012-12-18T03:31:46.182-05:00I am looking for International calling service pro...I am looking for International calling service provider that provide full <a href="http://www.simplecall.com/us/easy-access-call-history/" rel="nofollow">Online access</a> of my account including Top Up, Registering Phones, Call History, Current Balance etc.simplecallhttps://www.blogger.com/profile/16310714296967512983noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-83717769279172514952011-02-23T19:54:51.734-05:002011-02-23T19:54:51.734-05:00Sorry for the belated comment, but it's a big ...Sorry for the belated comment, but it's a big Internet. In Chicken, of course, the stack <i>is</i> a call history, though it's truncated to the last N calls. And that's exactly what you get when Chicken prints an error traceback: the last N calls, where N depends on the time since the last minor GC.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1170258753281381972007-01-31T10:52:00.000-05:002007-01-31T10:52:00.000-05:00Great post!Great post!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1142039076966240942006-03-10T20:04:00.000-05:002006-03-10T20:04:00.000-05:00My point is not to defend the design decisions tha...My point is not to defend the design decisions that mainstream languages have made, but rather that having made those decisions, they are using the call stack for a dual purpose. This means that theoretically constraining the purpose of the call stack to representing only the future of the computation results in a mismatch between theory and practice in those particular cases. The view of the call stack as being only about the future of the computation makes perfect sense in the functional world, but not so much in the imperative one [but see my caveat in the penultimate paragraph].<BR/><BR/>IOW, if you simply add TCO to a typical imperative language (say Javascript), there will be a loss of information that programmers will notice, while the theory seems to say that nothing has been lost.<BR/><BR/>Of course, the relevant information can be recovered by tail mark accumulation, etc., but as long as you're operating within the imperative paradigm, you may as well just use the call stack for this purpose, as long as you're willing to live without TCO (rather them than me!)<BR/><BR/>[Caveat: the issue is more subtle than the way I've been describing it: without TCO, the future of the computation is exactly equivalent to the history that imperative programmers are interested in. So you could look at this equivalence and conclude that the call stack is, indeed, only about the future of the computation, in all cases, both imperative & functional. But this breaks down as soon as you decide that it's possible to optimize that representation of the future by performing TCO -- then you discover that the imperative call stack contains information that's redundant from the perspective of the future of the computation, but that's useful to the programmer using a debugger or examining an error trace. So the stack-is-the-future theory, and the apparent imperative/functional equivalence, only holds in the imperative world as long as the call stack is not TCO'd.]<BR/><BR/>BTW, the reason I'm bothering you about this is that I had wanted to post almost exactly the same observation in <A HREF="http://lambda-the-ultimate.org/node/1331" REL="nofollow">this LtU thread</A>: that the stack represents the future, and shouldn't be confused with a history. However, in writing that post, I came to the conclusion that there was more to it, and you're now suffering the consequences! :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1142034457346121572006-03-10T18:47:00.000-05:002006-03-10T18:47:00.000-05:00I still maintain that what we consider a valid ent...I still maintain that what we consider a valid entry in this history is a somewhat arbitrary distinction.<BR/><BR/>Consider again the point that you <I>don't</I> keep in the stack trace the set of for-loops that led to the current stack. Yes, you're right that imperative languages make a nice distinction between primitive iterative control constructs and functions, but by forcing this distinction, it prevents programmers from implementing new iterative control constructs <I>using</I> functions.<BR/><BR/>Unless you're content to commit to a fixed set of iterative forms in your language, distinguishing between iteration implemented with primitive loops and iteration implemented with functions simply to claim the dubious distinction that your stack contains a complete history of all "interesting" control events (for this arbitrary definition of "interesting") is a pyrrhic win.<BR/><BR/>Furthermore, it's perfectly possible for users to define particular tail calls as "interesting" control events all on their own by converting them to non-tail calls. This can either be done by applying the identity function, or by adding a "non-tail return" construct to the language. So it's still possible to allow the programmer to decide on a case-by-case basis what control events they want to record, admittedly with some amount of extra work.Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1142033168203196622006-03-10T18:26:00.000-05:002006-03-10T18:26:00.000-05:00The call stack is not a complete history, but in l...The call stack is not a complete history, but in languages/implementations without TCO, the call stack does serve a well-defined historic purpose which is lost when TCO is performed: it provides a complete history of every procedure call that directly led to the current execution point. This is not an arbitrarily incomplete history: it can provide answers to the question "how did execution get here?" that a TCO'd call stack often cannot.<BR/><BR/>Even if you assume that this common property of call stacks is completely accidental, e.g. because the language implementors didn't know about TCO, the fact is that it's relied on enough by people in the real world that it's perfectly reasonable and accurate to say that call stacks in many language implementations serve two overlapping purposes: to record a particularly useful aspect of the history of the computation, and to store the future of the computation. <BR/><BR/>A theoretical model that restricts the call stack to only being about the future of the computation does not model what many real languages actually do. Further, in languages that don't rely heavily on recursion, using the call stack for this dual purpose is actually an excellent bit of optimal engineering.<BR/><BR/>That said, I still want you to make sure they add TCO to Javascript, m'kay? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1141276429273649972006-03-02T00:13:00.000-05:002006-03-02T00:13:00.000-05:00That's funny, I wondered about the same thing! I g...That's funny, I wondered about the same thing! I guess it's only natural, given that it's the other of only two options. :) I didn't think about the "both" option, though.<BR/><BR/>John and I also talked about having options to turn on tail mark accumulation. I've also wondered about having fixed, bounded accumulation (most recent <I>n</I> marks) for debugging's sake, which would still exhibit the same asymptotic behavior.<BR/><BR/>No pre tags does suck. No code or blockquote tags sucks too. Blogger is decidedly mediocre.Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1141273965114796732006-03-01T23:32:00.000-05:002006-03-01T23:32:00.000-05:00One idea that I talked to John about is a variant ...One idea that I talked to John about is a variant of continuation marks (co-marks?) that have the opposite "collapsing" rule.<BR/><BR/>Here's the normal rule:<BR/><BR/>(wcm A (wcm B e)) = (wcm B e)<BR/><BR/>Here's another possibility:<BR/><BR/>(wccm A (wccm B e)) = (wccm A e)<BR/><BR/>So the first mark to get to a frame wins. I argued that this might be more useful for debugging since it has more historical-type information. You could also throw both into the same system and get kind of an "interval" for each frame: it started out in this procedure, and it's now in this other procedure waiting for an answer.<BR/><BR/>(In other news, no pre tags in comments makes me sad.)Ryan Culpepperhttps://www.blogger.com/profile/04275692281825651783noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1141268658242403732006-03-01T22:04:00.000-05:002006-03-01T22:04:00.000-05:00Well, maybe I should have made a somewhat softer s...Well, maybe I should have made a somewhat softer statement: "the call stack is not a <I>complete</I> history." Of course the stack is useful for debugging, but you can't rely on it for the entire history.<BR/><BR/>It's true that it's useful to think of the stack trace as the history, but it's only that part of the computation history that had not yet been completed. Functions that have returned, and functions that have made tail calls are all dead computations, and are thus subject to removal from the evaluation context.Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1141267032043563932006-03-01T21:37:00.000-05:002006-03-01T21:37:00.000-05:00Awww but it's so convenient to think of it as hist...Awww but it's so convenient to think of it as history. I wouldn't be able to debug if I thought that the call stack represented future computation.Anonymousnoreply@blogger.com