(+ (+ (+ 7 3) 4) 2)

and the innermost expression was being evaluated then the continuation frames would be:


(+ (+ (+ 7 3) 4) 2)
(+ (+ 7 3) 4)
(+ 7 3)


The complicating factor is that when a function calls another function as the last thing it does, it removes itself from the stack, so the continuation frames for


(define (f)
  (f))


(that is, an infinite recursion) always look like

(f)

no matter how many iterations have happened (and this operation will never run out of stack memory, as the equivalent code in C would).

There's a debugger that lets you directly set breakpoints and so on in CVS, but it's not in the public distributions yet (soon!). For now, you only see these when you throw an exception; if it's not ever handled, DrScheme will eventually handle it by showing the continuation frames at the point when the exception occured.

--

[ Parent ]


int f(int i) {
  printf("f\n");
  return g(i);
}
 
int g(int i) {
  if (i == INT_MAX) {
     return 20;
  } else {
     return f(i+1);
  }
}


Most C compilers will generate code such that when f calls g it will push a new activation record for g on the stack setting the return pointer to itself, and then once control has returned to it returning back to whoever called it. That will be slow and consume lots of stack memory in this case. However, if you think about it, since once f calls g there's nothing left for it to do other than return what g gives it right back to its own caller, it could instead free all the memory associated with its own activation record and build a new one for g whose return pointer pointed directly to f's caller, thus using no extra memory. You can actually use this technique to compile function calls in tail position all the way into gotos making them very cheap compared to traditional function calls both in time and memory requirements. In this example, for instance, the compiled code for f and g could turn into something almost equivalent to a while loop in terms of the assembly code it generated.

Anyway, there's a big body of literature on this topic and the implementation I described is one of many. See for instance "RABBIT: A Compiler for SCHEME" from the readscheme library, particularly the section "The Imperative Treatment of Applicative Constructs" starting on page 37 or "Lambda: The Ultimate GOTO" both by Guy Steele, one of Scheme's inventors, and "Proper Tail Recursion and Space Efficiency" by Will Clinger.

--

[ Parent ]

I think some of the material in your flamewar with trhurler could be included here, about thinking about problems and data in more efficient ways. You talked a little bit about it already, but I think it could do with more.

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]

Except that I limit my admiration at C, not C++.

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]

So big it doesn't fit in one paragraph.
--- code ends here ---


In the second blob ("so big it doesn't ...") renders in normal font face. Actually looking at the generated html, maybe it's the fact that scoop is inserting a paragraph tag in there and Mozilla 1.5, the browser I'm using, interprets that as ending the code block? I dunno. I'm using auto format.

--

[ Parent ]