Re: GO in T?

[Jonathan Rees <Rees@YALE.ARPA>]

    From: Mike Caplinger <mike@RICE.ARPA>

    While I shudder to ask this question, is there some way to simulate a
    general GO in T?  CATCH requires you to know, a priori, about the
    control flow globally in the program, making automatic translation
    difficult.

    I have two applications in mind; translation from some other Lisp
    dialect into T, and using T as an intermediate form for Algol-like
    languages.

Good question.  I admit the need is real.  I give you 4 answers.

#1. If you were writing in pure Scheme with upwards escape functions,
you could translate

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

as

  (let ((n nil) (a nil))
    ((catch go
       (catch return
         (labels (((y)
                   (set n 5)
                   (set a 1)
                   (go z))
                  ((z)
                   (cond ((= n 0) (go e)))
                   (set a (* a n))
                   (set n (- n 1))
                   (go z))
                  ((e)
                   (return a)))
            (y))))))
         
and it would work quite transparently.  Unfortunately, bad things
happen when you run this in T.

#2. If you can make sure that all your GO's have the right
tail-recursive tail-recursive properties, you can use LABELS directly,
and get good object code (direct jumps, no closure consing).  However,
I think this is the problem you were alluding to, so it's not directly
acceptable.

  (let ((n nil) (a nil) (go (lambda (tag) (tag))))
    (catch return
      (labels (((y)
                (set n 5)
                (set a 1)
                (go z))
               ((z)
                (cond ((= n 0) (go e))
                      (else             ;note nontrivial change
                       (set a (* a n))
                       (set n (- n 1))
                       (go z))))
               ((e)
                (return a)))
        (y))))

#3. If you can't make the guarantee of #2, you can use a driver loop,
and a CATCH for each segment of the PROG:

  (let ((n nil) (a nil))
    (catch return
      (labels (((y)
                (catch go
                  (set n 5)
                  (set a 1)
                  (go z)))
               ((z)
                (catch go
                  (cond ((= n 0) (go e)))
                  (set a (* a n))
                  (set n (- n 1))
                  (go z)))
               ((e)
                (catch go
                  (return a))))
        (do ((tag y (tag))) (nil)))))

(The current TC is so buggy with respect to CATCH/LABELS interactions
that I wouldn't expect this to compile correctly.)

#4. If you want more efficient compilation using current compiler
technology, you can throw small integers instead of closures to
the driver loop:

  (let ((n nil) (a nil))
    (catch return
      (let ((y 0)
            (z 1) ;assign unique small numbers to all tags for fast dispatch
            (e 2))
        (do ((tag y (xselect tag
                      ((y)
                       (catch go
                         (set n 5)
                         (set a 1)
                         (go z)))
                      ((z)
                       (catch go
                         (cond ((= n 0) (go e)))
                         (set a (* a n))
                         (set n (- n 1))
                         (go z)))
                      ((e)
                       (catch go
                         (return a))))))
            (nil))))

One could imagine a compiler which "did the right thing" with this
(compiled direct jumps instead of jumps to a dispatch), but of course
there's not much motivation to write one (however, either this or
a primitive GO would be important if we were serious about compiling
Common Lisp or Fortran).

A higher-tech solution would be to do some code analysis to translate
most PROG code into code which would fit solution #2.  This was done
in an early SCHEME interpreter (NSCHSY; circa 1977-78) at MIT.  I
think Jim Meehan at Cognitive Systems (Meehan@Yale), and perhaps some
Yale people (McDermott? Riesbeck?) have also worked on this problem;
maybe one of them could comment.