[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: GO in T?

My version of prog translates this:

  (prog (n a)
     y  (set n 5)
        (set a 1)
     z  (cond ((= n 0) (go e)))
        (set a (* a n))
        (set n (- n 1))
        (go z)
     e  (return a))

into this:

(let ((n nil) (a nil))
   (catch return
      (let ((return (no-op return))) ; this is purely to avoid a compiler bug
         (labels (((begin) (go y))
                    (set n 5)
                    (set a 1)
                    (go z))
                    (cond ((= n 0) (go e))   )
                    (set a (* a n))
                    (set n (- n 1))
                    (go z))
                    (return a)))
            (begin)   ))))

where go is defined globally as (lambda (tag) (tag)) [defining it locally
wouldn't be a bad idea].

What about the tail-recursive properties?

(a) If e doesn't explicitly return, but just runs off the end,
I put a "return" at the end.

(b) I live with the fact that some loops will push a lot of stack that
gets cleaned off at the end.  I didn't notice this problem until now.
Fortunately, I don't use PROG except in the expansion of LOOP, and
the T version of LOOP expands into an ITERATE/COND construct.

The above program would be written as something like

  (loop for ((n 5) (a 1))
   until (= n 0)
   result a
     (set a (* a n))
     (set n (- n 1))   )

which would expand into
   (let ((n 5) (a 1))
      (labels ()
            l_o_o_p ()
               (cond ((= n 0) a)
                     (t (set a (* a n))
                        (set n (- n 1))
                        (l_o_o_p))   ))))

The "labels" is for returns used by two tests; "catch" is avoided completely.

It would not be difficult to extend the loop idea to prog, and avoid
the non-tail-recursive problem.