[plt-scheme] DrScheme crash, and my bad programming

On May 21, 2008, at 8:29 PM, Chongkai Zhu wrote:

> I would suggest you to read more about *tail call*, or as some one  
> put it, tail recursion. Afterall, let loop is just a macro that  
> expands to recursive function call.

Indeed; the only non-tail-call is the one that Chongkai points out.   
Presumably, in the original C code there was a mutation of a global  
counter.

I changed it to be tail-calling, and now it runs cheerfully forever.   
I changed it to be tail-calling by adding an accumulator.

HtDP covers this in section VI, "Accumulating Knowledge".  However, I  
don't see a specific discussion in that section of this particular need.

John



> In the code you posted, the line
>
>    [(solution6? a b c d n) (add1 (count-solutions a b c (add1 d) n))]
>
> is not tail call. You didn't post the code that "break up the  
> recursion into one function that recurses on c and d while another  
> recurses on a and b", so I can't tell whether it is tail call or not.
>
> Chongkai
>
> Joshua Zucker wrote:
>> I know that there's probably a more conventional way to write code
>> like this -- this is just my dorky translation of a C for loop into a
>> recursion.
>>
>> (define (solution6? a b c d n)
>>   (let ([f (- (* 12 n (- n 2)) b (* 3 c) (* 2 d))])
>>     (and (>= f 0)
>>          (>= (* n n n) (+ a b c d (- (* 8 n) (* 2 a) b) f)))))
>>
>> (define (count-solutions a b c d n)
>>   (cond
>>     [(> a (* 4 n)) 0]
>>     [(> b (- (* 8 n) (* 2 a))) (count-solutions (add1 a) 0 0 0 n)]
>>     [(> c (- (* 4 n (- n 2)) b)) (count-solutions a (add1 b) 0 0 n)]
>>     [(> d (quotient (- (* 12 n (- n 2))
>>                        b
>>                        (* 3 c))
>>                     2)) (count-solutions a b (add1 c) 0 n)]
>>     [(solution6? a b c d n) (add1 (count-solutions a b c (add1 d)  
>> n))]
>>     [else (count-solutions a b c (add1 d) n)]))
>>
>> But if you run (count-solutions 0 0 0 0 10) or so,
>> where the recursion is then going a couple hundred million layers  
>> deep,
>> DrScheme crashes.
>>
>> If I break up the recursion into one function that recurses on c  
>> and d
>> while another recurses on a and b, then it has no trouble.
>>
>> If you want me to be more specific about exactly what code I run to
>> make DrScheme crash, let me know.  (By crash, I mean the application
>> quits -- v372 on OS X 10.4)
>>
>> But I'm also writing because I figure there are more elegant ways to
>> write for-loop-esque code like this -- maybe I should post that to
>> plt-edu instead -- but I'd love to learn what the conventional way is
>> to write this type of code.  Something with let loop?  I've seen that
>> idiom but I don't really get it.
>>
>> Finally, the algorithm here is just brute-force counting of solutions
>> to a system of three linear diophantine equations in seven variables,
>> where all the variables have to be nonnegative.  So I pick 4 of them,
>> look at all the possibilities, and check for whether the remaining
>> values are positive (with a few shortcuts, since the limits of the
>> loop guarantee some of them will be positive).  So maybe there are
>> much much much more efficient ways of counting the number of  
>> solutions
>> to a system like this?  (Equivalently, the number of lattice  
>> points in
>> a 7-dimensional region bounded by a bunch of hyperplanes.)
>>
>> Thanks!
>> --Joshua Zucker
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20080522/7b4ebb0a/attachment.p7s>