# [racket] strange loops

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 06-03-12 12:03, Pierpaolo Bernardi wrote:
>* Hello,
*>*
*>* 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).
*>*
*>* Thanks.
*>*
*>* Pierpaolo
*>*
*>* ================ #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)))
*
This loop is a fiction as all paths in the body go to either next-sum
or next-z and leave the rest of the iteration for whenever. Thus you
never iterate over your vector of squares, but you do build up
stack-frames that promise to do that in a future which never happens.
>* (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))))))))))))))
*
Marijn
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.18 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAk9WD9UACgkQp/VmCx0OL2y8+gCgiXhLP4pkO5/Iv6d0JKNdpv+A
9zMAn33IqJqdEvVczELg+Y3XgYPIECgY
=3QeK
-----END PGP SIGNATURE-----