[racket] strange loops

From: Marijn (hkBst at gentoo.org)
Date: Tue Mar 6 08:23:33 EST 2012

-----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-----

Posted on the users mailing list.