Should I submit as-is or make modifications?

Submit as-is   0 votes - 0 %
It's not ready, make changes I'll describe in a comment   1 vote - 100 %
 
1 Total Votes
So tell me... by Breaker (6.00 / 1) #1 Thu Mar 11, 2004 at 12:15:39 PM EST
I'm going to assume that you're a working programmer who comes from a C, C++

At any point...
What's on the * call stack* and how do I debug it?


It's a little complicated by jacob (6.00 / 1) #2 Thu Mar 11, 2004 at 12:40:25 PM EST
What's on the call stack? Well, it's not really a stack exactly, so we call it a list of continuation frames, but you can think of it as a stack, and each item represents an expression in the program. So for instance if you were running the program

(+ (+ (+ 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 ]
Alright... by Breaker (6.00 / 1) #3 Thu Mar 11, 2004 at 12:56:27 PM EST
What's on the call stack?

I meant on the processor call stack.  IP, SP, ES, etc.  Don't know what that'll look like on a non Intel like machine, but it's got to translate somewhere...

But in your example, you're using first class values (admittedly, for brevity and clarity, and also a good example), and that's straightforward in any language.  What about ADT's?  Pointers? Structured exception handling?

If you're aiming your tutorial at people that already know how to code, then how about some debug advice?

Heh, took me a few weeks while learning C++, to learn the value of the println commnand...


[ Parent ]
Implementation-specific by jacob (6.00 / 2) #5 Thu Mar 11, 2004 at 01:59:30 PM EST
The Scheme standard really doesn't talk about what's supposed to go on at that level at all, and there are dozens of implementations that all make different choices about how to best represent the data. For that reason the best way to understand what's going on during the dynamic run of a Scheme program isn't to look that the processor or the way bits are set in memory but instead to have a more abstract computational model in your mind and reason about that. For instance there are multiple different viable ways to represent the call-chain in memory, and as I alluded to before, they've all got different trade-offs that will make different operations more or less expensive, they'll all make the whole program look radically different at the architecture level, and trying to figure out what's going on from that sort of information will be just about impossible. On the other hand, if you look at it from a more abstract point of view in which a function call is essentially a basic part of your computation that can't be further reduced, everything will make sense. (Sorry if I'm being a little too verbose or unclear here; this touches strongly on the topic of the master's thesis I'm writing now so I've got a lot to say about it.)

On a more practical level: to debug, your best bets are to use a stepper/debugger to set break points and you the steps a program is taking, use print statements, make use of stack traces, and write small functions you can test independently — one reason a mostly-functional style is very useful.

I hope that answers your question. :)

--

[ Parent ]
you should put forth the argument.. by infinitera (6.00 / 1) #8 Thu Mar 11, 2004 at 02:44:12 PM EST
That the bits and metal debugging people are so fond already disappeared with the virtual machines of Java and C#, and that Scheme actually does it better. ;)

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]
Good answer. by Breaker (6.00 / 2) #15 Fri Mar 12, 2004 at 01:43:35 AM EST
TYVM!


[ Parent ]
Loops by ucblockhead (6.00 / 2) #4 Thu Mar 11, 2004 at 01:19:49 PM EST
I like the additional bit on looping.

One question, again coming from a C bias (maybe you don't know the answer to this): When you use recursion to simulate looping, what sort of optimization does Scheme do to collapse returns? In other words, if I were to simulate for(int i=0;i<10000;i++) using recursion in C, my program would obviously run like crap. How does Scheme avoid this?
---
[ucblockhead is] useless and subhuman

this is actually a big deal by jacob (6.00 / 1) #6 Thu Mar 11, 2004 at 02:24:56 PM EST
The Scheme standard specifies that you've got to do a particular optimization called proper tail recursion or sometimes tail-call optimization. It works like this: say you've got a pair of functions like


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 ]
kind of what i'd like to see in the article too by infinitera (6.00 / 1) #7 Thu Mar 11, 2004 at 02:31:41 PM EST
The standard trollish post on k5 is going to be "So what you're saying is, you can make loops in scheme? Why bother when I already have them!"

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 ]
I am that rarest of things by leviramsey (3.00 / 0) #9 Thu Mar 11, 2004 at 05:58:04 PM EST

A programmer who adores C/C++ and Scheme...


--
Could I be the next Lee Abrams?
heh, by infinitera (6.00 / 1) #10 Thu Mar 11, 2004 at 06:49:12 PM EST
Another thing we have in common.

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 ]
Yerrrrs by Rogerborg (6.00 / 1) #11 Thu Mar 11, 2004 at 07:12:38 PM EST
That's about what I figured.  Well, good luck with it.

-
Metus amatores matrum compescit, non clementia.
<code> tag by gazbo (6.00 / 1) #12 Thu Mar 11, 2004 at 08:42:09 PM EST
Scoop shouldn't do anything with that tag at all; regular tags are all treated alike, and context independent (once it's matched the tag, it checks it's valid, and then spits it out again, plus pushes it on the stack to ensure it matches up) so whitespace or newlines are completely ignored.

I tried to reproduce what you said and couldn't in any post mode - can you find an example where it happens, and post it in Plain Text formatting?  Also, what post mode do you use - HTML or AutoFormat?


I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

testing 1 2 3 by jacob (3.00 / 0) #13 Fri Mar 12, 2004 at 12:58:01 AM EST

--- code begins here ---
hello there is is a big gob of code.

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 ]
Yup, it's a browser thing by gazbo (6.00 / 1) #14 Fri Mar 12, 2004 at 01:14:59 AM EST
Displays fine in IE, not in Firebird.

I have no idea whether the HTML spec claims that a P tag should cancel a code tag or not.  It could also be a CSS thing, where the P tag is resetting the font to the default body style.

Weird.  In the meantime, I suggest installing a proper, standards compliant browser ;-)


I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

[ Parent ]
Also works fine in Opera... (n/t) by leviramsey (3.00 / 0) #16 Fri Mar 12, 2004 at 06:57:31 AM EST

--
Could I be the next Lee Abrams?
[ Parent ]
You got the recursion thing wrong. by em (6.00 / 1) #17 Fri Mar 12, 2004 at 08:09:47 PM EST
Recursion in Scheme is not at all inefficient and does not waste memory,

Nope.  You mean tail recursion doesn't waste memory; it gets compiled into a vanilla loop.  The range function you give is not tail-recursive; it needs to wait for the result of the recursive call (range (+ low 1) high) to pass it to cons; thus, it needs to use the call stack to keep track of the execution state.  The computation of (range 0 9) with your implementation looks like this.


(cons 0 (range 1 9))
(cons 0 (cons 1 (range 2 9)))
(cons 0 (cons 1 (cons 2 (range 3 9))))

...
(cons 0 (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 (cons 6 (cons 7 (cons 8 (cons 9 null))))))))))
...
'(0 1 2 3 4 5 6 7 8 9)

The size of the execution stack grows linearly with high-low.

The efficient, tail-recursive way to do it is as follows (I don't really know Scheme, so I'll do Lispy-looking pseudocode and hope for the best):


(define (range low high)
  (define (iter low i result)
    (cond
      ((= i low) (cons i result))
      (else (iter low (- i 1) (cons i result)))
  (iter low high null))))

iter is an auxiliary tail-recursive function that uses the parameter result to accumulate partial results as we construct the list.  We start constructing the list from the rear, pushing elements into the front in decreasing order.  If we call (range 0 9), we get the following computation:


(iter 0 9 null)
(iter 0 8 '(9))
(iter 0 7 '(8 9))
(iter 0 6 '(7 8 9))
...
(iter 0 0 '(1 2 3 4 5 6 7 8 9))
'(0 1 2 3 4 5 6 7 8 9)

Here, the size of the execution stack is constant. The result list grows linearly, but it's not in the stack.  The same stack frame gets reused for each call to iter.

--em

yes by jacob (6.00 / 1) #18 Sat Mar 13, 2004 at 01:10:16 AM EST
Of course you're right that tail recursion is the most efficient way to go, and a real library implementation of range would probably use the tail-recursive implementation you suggest for that reason. But it's also true that function calls in general in most Scheme implementations are lighter weight than C function calls and that Scheme compilers and interpreters make various representation decisions that will make calling a function cheaper. This basically falls under the category of "things I thought were a little too complicated to explain in the article," though you're right, I ought to at least mention the issue.

--

[ Parent ]