[plt-scheme] build-vector avoids sharing problem

From: Bill Richter (richter at math.northwestern.edu)
Date: Fri Feb 7 21:18:52 EST 2003

Thanks for the Gambit etc. info about, Noel.  See if this is right:

Plt-scheme is about teaching courses out of the book HtDP.

HtDP is not even a book about Scheme, but a book that uses a dialect
of Scheme in order to teach "how to design programs".

There's quite a lot in HtDP about speed and efficiency, and DrScheme
has various tools to test for speed and efficiency.

But that doesn't mean that a program written in Advanced Student
should be particularly fast.  Advanced Student + HtDP is a way to
learn about, among other more important things, speed and efficiency.

So there's no reason to think it's easy to fix an Advanced Student to
run fast on a faster Scheme->C compiler.  I'm left with 2 questions:

1) What language do the PLT hotshots use for blinding speed?

2) In Section 31 of HtDP, "Designing Accumulator-Style Functions",
   there's an interesting discussion about speed:

      Pitfalls: People who encounter accumulator-style programming for
     the first time often get the impression that they are always
     faster or easier to understand (design) than their recursive
     counterparts. Both parts are plain wrong. While it is impossible
     to deal with the full scope of the mistake, let us take a look at
     a small counterexample. [...] 

     the performance of the accumulator-style version of factorial is
     always worse than that of the original factorial function.

That's interesting, but I'm puzzled by this discussion.  From earlier:

             (! 3)			           	    
           = (* 3 (! 2))		       (! 3)	    
           = (* 3 (* 2 (! 1)))		     = (!-a 3 1)   
           = (* 3 (* 2 (* 1 (! 0))))	     = (!-a 2 3)   
           = (* 3 (* 2 (* 1 1)))	     = (!-a 1 6)   
           = (* 3 (* 2 1))		     = (!-a 0 6)   
           = (* 3 2)			     = 6           
           = 6

So the plain factorial and the accumulator-style factorial perform
exactly the same arithmetic operations.  The speed trade-off is only

	     stack space consumption for plain factorial
	  storage consumption for accumulator-style factorial

I think I have read that stack space consumption means
accumulator-style is better, and HtDP has a counterexample.  OK, fine.

BUT: what if we wanted not just n!, but the all of the earlier
factorials too
			1! 2! 3! ... (n-1)! n!

Then clearly accumulator-style is better, because we calculate all the
earlier factorials along the way to n!  With plain-style, we don't
calculate anything but n!  That seems to be the more important point.

Anyway, I clearly have a lot to learn about accumulators & speed, so
I'll go back to HtDP, and no doubt it will improve my program!  And
what I learn, I should be able to apply to a faster-running version of
the program in Gambit, or even C.

In particular, my original question was dumb, how should I compute my
lists B(s,t), which are computed recursively from the earlier B(i,j).

Answer: this is just recursion.  Maybe I need accumulators, and maybe
I don't!  Depends on the problem in a way that HtDP discusses!

Posted on the users mailing list.