[gambit-list] Re: simple unoptimized gsc nontail recursion
Bill Richter
richter at math.northwestern.edu
Wed Dec 7 01:46:51 EST 2005
>Can I get the debugger to tell me what's happening when it crashes
>here?
If you run code from the repl (start gsc without arguments), using
compile-file and load, like (compile-file "Curtis-algorithm"
'(debug)) (load "Curtis-algorithm") then when running out of memory
the debugger is entered.
Thanks, Christian, and I guess that's a general point unrelated to
Marc's heap size tip. And the manual explains how to do it in gsi:
gsi -:dr,h10000 Curtis-algorithm
*** ERROR IN Poly->Tree, "Lambda-defs.scm"@311.21 -- Heap overflow
>
But I didn't learn much, because I couldn't find any variables to
examine: my debugger transcript below. On to your other points:
What's your question?
The one you sort of answered: how does the debugger help me analyze
the heap size error triggered by Marc's idea. But maybe you're asking
a more general general question, so let me ramble:
This is Gambit code from near the top of my web page
<http://www.math.northwestern.edu/~richter/Richter-Curtis-algorithm.tar.gz>
which doesn't run as fast as I'd like it too. Marc & Germaine gave me
some tips before, so it runs a good deal faster than it first did!
Now I just learned about tail recursion (I know, I shoulda learned
this long ago, but I hadn't seen explained at all usefully before
reading Sitaram's Fixnum tutorial (tail recursion = iteration)), so I
posted a question which Marc answered: gsc/gcc will *not* optimize
away all possible tail recursion problems! Don't let the recursion
depth get above 1000 or 10000! So I yelped for help which Marc's
heapsize tip didn't tell me anything. And of course you're right, as
I realized myself, heap size isn't the same thing as recursion depth.
But I think I see some my tail recursion problems. My main loop is
Curtis-alg, which looks tail recursive to me:
(define (Curtis-alg a X top-level-tags min-target)
(if (Poly-0? X)
false
(let ([x (Tree-first X)])
(if (Mono-ascending-left-lex x min-target)
false
(let ([b (lookup-tag x top-level-tags)])
(if b
(let ([X+db (merge-tree (Poly->Tree (truncate-poly (d b) min-target)) X)])
(Curtis-alg a X+db top-level-tags min-target))
x))))))
Curtis-alg builds a huge tree, and the functions used, merge-tree &
Poly->Tree, don't look tail recursive to me! I'll fiddle with this...
Here's my debugger output, modeled on the informative example in the
node "Debugging commands":
> ,i
#<procedure #2 Poly->Tree> =
(lambda (X)
(let ((n-terms (lambda (n S) (list n (Poly->Tree S)))))
(if (empty? X)
empty
(let* ((x (first X)) (n (Mono-first x)) (y (Mono-rest x)))
(if (Mono-1? y)
X
(let loop ((n n) (S_n (list y)) (X (rest X)))
(if (Poly-0? X)
(list (n-terms n (reverse S_n)))
(let* ((x (first X)) (m (Mono-first x)) (y (Mono-rest x)))
(if (= n m)
(loop n (cons y S_n) (rest X))
(cons (n-terms n (reverse S_n))
(loop m (list y) (rest X))))))))))))
> ,e
(current-exception-handler) = primordial-exception-handler
(current-input-port) = '#<input-port #3 (stdin)>
(current-output-port) = '#<output-port #4 (stdout)>
(current-directory) = "/tmp_mnt/rhome/richter/Gambit-Curtis-alg/statprof/Pol...
> ,b
0 Poly->Tree "Lambda-defs.scm"@311:21 (list (n-terms n (reve...
1 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
2 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
3 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
4 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
5 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest...
6 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
7 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest...
8 Curtis-alg "Curtis-algorithm.scm"@325:43 (Poly->Tree (trun...
9 calc-d "Curtis-algorithm.scm"@288:22 (Curtis-alg a (Po...
...
12 ##time
13 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (##time (lambda ()...
14 ##load
15 ##main
> ,+
1 Poly->Tree "Lambda-defs.scm"@299.20 (Poly->Tree S)
\1> ,b
1 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
2 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
3 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
4 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
5 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest...
6 Poly->Tree "Lambda-defs.scm"@299:20 (Poly->Tree S)
7 Poly->Tree "Lambda-defs.scm"@319:33 (loop m (list y) (rest...
8 Curtis-alg "Curtis-algorithm.scm"@325:43 (Poly->Tree (trun...
9 calc-d "Curtis-algorithm.scm"@288:22 (Curtis-alg a (Po...
10 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (calc-d s t)
11 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (do ((s (if (< t M...
12 ##time
13 | Curtis-algorithm.o3| "Curtis-algorithm.scm"@407:1 (##time (lambda ()...
14 ##load
15 ##main
\1> ,e
n = 13
(current-exception-handler) = primordial-exception-handler
(current-input-port) = '#<input-port #3 (stdin)>
(current-output-port) = '#<output-port #4 (stdout)>
(current-directory) = "/tmp_mnt/rhome/richter/Gambit-Curtis-alg/statprof/Pol...
\1> ,q
More information about the Gambit-list
mailing list