Vanishing MrEd

[Greg Pettyjohn <GregP@bsquare.com>]

Here's the start of a fractal terrain generator I'm working on:

; vertex of three coords.
(define-struct vertex (x y z))

; make a new vertex by bisecting an edge and calculating a random height.
(define (new-vertex v0 v1)
  (let ([x0 (vertex-x v0)]
        [y0 (vertex-y v0)]
        [z0 (vertex-z v0)]
        [x1 (vertex-x v1)]
        [y1 (vertex-y v1)]
        [z1 (vertex-z v1)])
    (make-vertex
     (/ (+ x0 x1) 2)
     (/ (+ y0 y1) 2)
     (+ (/ (+ z0 z1) 2) (random-offset v0 v1)))))

; how to calculate the random height.
(define (random-offset v0 v1)
  (let ([x0 (vertex-x v0)]
        [y0 (vertex-y v0)]
        [z0 (vertex-z v0)]
        [x1 (vertex-x v1)]
        [y1 (vertex-y v1)]
        [z1 (vertex-z v1)])
    (let ([l (sqrt (+ (expt (- x1 x0) 2) (expt (- y1 y0) 2) (expt (- z1 z0)
2)))])
      (* l (- 1 (exact->inexact (/ (random 200000) 100000)))))))

; take a triangle and make four new ones by connecting the midpoints of
edges.
(define (calculate-new-triangles a b c)
  (let ([d (new-vertex a b)]
        [e (new-vertex b c)]
        (f (new-vertex c a)))
    `((,a ,d ,f) (,d ,b ,e) (,e ,c ,f) (,d ,e ,f))))

; take a list of triangles and make four new triangles for each original
triangle.
(define (new-triangles triangles)
  (if (null? triangles) '()
      (append
       (calculate-new-triangles (caar triangles) (cadar triangles) (caddar
triangles))
       (new-triangles (cdr triangles)))))

; generate terrain by starting with a single equilateral triangle and
generating new triangles
; for several (small integer) itterations.
(define (gen-terrain triangles iterations)
  (if (= iterations 0) triangles
      (gen-terrain (new-triangles triangles) (- iterations 1))))

(define equilateral-triangle
  (list (make-vertex 0 0 0)
        (make-vertex 1 0 0)
        (make-vertex 0.5 (/ (sqrt 3) 2) 0)))

(length (gen-terrain (list equilateral-triangle) 7))


So take a triangle, split it up into four new triangels by considering
the midpoints of edges in the original triangle.

It's an exponential algorithm. The first itteration makes 4 then 16 then 64
and so on.
6 itterations makes a list of 4096 triangles. 7 itterations should make 16k
triangles, but
it won't finish in MrEd. I ran it overnight in MzScheme, don't know how long
it took, but
it took longer than the several minutes I waited before I left.

I'm running (most likely) a debug build for both MrEd and MzScheme.

Here are some more details and some related questions:
4096 triangles takes only a few seconds, I would expect 16k triangles to
take about 4 times as long
instead, after several minutes, MrEd vanishes from my screen without a
trace. :-( --- hey, wait a minute,
this is Scheme, that's not supposed to happen! If it's running out of
memory, shouldn't it post some sort of
error or something? Is this happening because I'm running debug? I assume it
will run faster if I rebuild retail.

So now I'm wondering about tail-call optimization and how/whether MzScheme
uses the/a stack etc.

As for tail call stuff:
In the code above, gen-terrain uses a tail call, i.e. nothing happens to the
value returned by the
recursive call to gen-terrain. So, as I understand it, this will get
replaced by a simple loop by
the compiler.

Now, new-triangles, on the other hand is not a tail call, since the
recursive call returns to append.
I rewrote using a tail call like this:
(define (new-triangles old-v new-v)
  (if (null? old-v) new-v
      (new-vertices (cdr old-v) (append
                                 (calculate-new-triangles (caar old-v)
(cadar old-v) (caddar old-v))
                                        new-v))))

Now, when I run, it finishes after a few momemnents. So obviously the
compiler is treating the two versions of the routine differently. Does it
use a stack to implement the original, non-tail version?
I have a textbook, which describes an optimization that uses
"continuation-passing-style". I started reading about the CPS
transformation, but only gave the chapter a quick once over, since then I've
gotten interested in the OpenGL stuff again and haven't spent much time on
the other studying, so I only have a first notion of how the CPS
transformation works --- already several months old..

Here's my "first notion" of how it works: the compiler, adds a new paramter
to the function. The new parameter is a function that represents the
"continuation" of the computation when the routine finishes. By re-writing
the code using
CPS, any recursive routine then can be transformed into a routine which can
be "flow-charted" (is this sentence true.)
"Flow charted" means that recursive calls are replaced by loops (are
stacks/lists needed?). Finally the "flow-charted" version is used to
generate machine code in later stages of the compiler.

So now I wonder, what is the relationship between tail-call optimizatioin
and "CPS transformations"?
Scheme is tail-call optimized as part of the r5rs, what about other compiler
optimizations, are they required by the spec?
What about MzScheme, what optimizations, transformations does it implement?

Could a CPS transformation, or other optimization, potentially change the
semantics of an algorithm? What if you want it to be slow and use more
memory?

Shriram once said in an email, that tail call optimization was "the most
profound advancement in compiler technology"
--- or something to that affect. (Please forgive, if I've misquoted, if it's
important, I can dig and find the original mail.) I can explain to people
how the simpler version works --- i.e. how a simple tail call is replaced
with a goto and hence avoids using extra stack opperations. Can someone
explain why this is so profound?

Thanks.