[racket] strange loops

From: Pierpaolo Bernardi (olopierpa at gmail.com)
Date: Tue Mar 6 06:03:47 EST 2012


I was expecting the procedure 'fa' below to run in constant memory,
as, in my understanding, It doesn't use any non-tail recursive loops,
it does not build any data structure, and only performs arithmetic
operations on small integers.

But some of my assumptions must be wrong, as the calls to next-z
accumulate and eventually fill the available memory.

Can someone explain me where's my mistake?

(A secondary note: the debugger shows the value of the squares vector
as a 100 element vector, with no hint that the value is abbreviated.
Pretty confusing, IMHO).



#lang racket

(define (perfect-square? n)
  (= n (sqr (integer-sqrt n))))

(define (fa)
  (let ((squares (for/vector ((i (in-range 1 10000)))
                   (* i i))))
    (let/ec return
      (let next-sum ((sum 3))
        (let ((limit-z (quotient sum 3)))
          (let next-z ((z 1))
            (if (= z limit-z)
              (next-sum (add1 sum))
              (for ((y+z (in-vector squares)))
                (let ((y (- y+z z)))
                  (if (> (+ y z) sum)
                    (next-sum (add1 sum))
                    (let ((x (- sum z y)))
                      (if (and (perfect-square? (+ x y))
                               (perfect-square? (- x y))
                               (perfect-square? (+ x z))
                               (perfect-square? (- x z)))
                        (return (list x y z sum))
                        (next-z (add1 z))))))))))))))


Posted on the users mailing list.