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