[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>