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

From: Chongkai Zhu (czhu at cs.utah.edu)
Date: Wed May 21 23:29:25 EDT 2008

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.

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.


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

Posted on the users mailing list.