[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