Re: [Kawa-commonlisp-dev] tagbodies

[Jamison Hope]

On Jul 26, 2012, at 3:13 PM, Helmut Eller wrote:

> On Thu, Jul 26 2012, Charles Turner wrote:
>
> > Most other Lisps use tag bodies quite heavily in some of the system
> > functions, SBCL has this in its parse-body routine:
> >
> > (tagbody
> >          :again
> >          (if forms
> >              (let ((form1 (first forms)))
> >                ;; Note: The (IF (IF ..) ..) stuff is because we don't
> >                ;; have the macro AND yet.:-|
> >                (if (doc-string-p form1 (rest forms))
> >                    (setq doc form1)
> >                  (if (declaration-p form1)
> >                      (setq reversed-decls
> >                            (cons form1 reversed-decls))
> >                    (go :done)))
> >                (setq forms (rest forms))
> >                (go :again)))
> >          :done)
> >         (values forms
> >                 (nreverse reversed-decls)
> >                 doc))))
> >
> > I'm sure there's a way to reformulate this without the goto's, maybe
> > something like
>
> State machines can be written with LABELS and (local) tail-calls.   
> Kawa
> should recognize those and implement them with gotos.  E.g.
>
> (labels ((again ()
>          ...
>          (if (declaration-p form1)
>              (done)
>              (again)))
>         (done ()
>           (values ...)))
>     (again))
>
> >      (let ((end-test nil))
> >         (do ((form-iter forms (cdr form-iter)))
> >             (end-test (values forms (reverse reversed-decls) doc))
> >           (if form-iter
> >               (let ((form1 (car form-iter)))
> >                 (if (doc-string-p form1 (cdr form-iter))
> >                     (setq doc form1)
> >                     (if (declaration-p form1)
> >                         (setq reversed-decls
> >                               (cons form1 reversed-decls))
> >                         (setq end-test t)))))))
> >
> > (haven't tested that)
> >
> > but I'm wondering if these sorts of kludges are worth it?
>
> I think implementing TAGBODY now is a bit of a distraction and  
> messaging
> the source into LABELS isn't that hard.
>
> > How hard would it be to implement TAGBODY?  Seems like I could just
> > use BlockExp to do it.
>
> In general you need to do a modicum of escape analysis before you can
> turn it into BlockExp.  E.g.
>
> (tagbody :foo (bar (lambda () (go :foo))))
>
> needs something like block/return or similar.  There's a paper by  
> Henry
> Baker that shows some ideas how tagbody can be emulated in terms of
> other special forms: http://home.pipeline.com/~hbaker1/MetaCircular.html
>
> I'm not sure how good Kawa is at analyzing escaping continuations so a
> naive translation might allocate continuations even in the simple  
> cases.
>
> One day we will clearly need tagbody and block/return but let's do  
> that
> later.

Agreed. LABELS is very similar to Scheme's letrec, so I would expect the
amount of work to get a working LABELS to be about what you had to do to
make FLET based on LET (i.e. not too much).

For now, it'd probably be faster to just manually convert each TAGBODY  
to
an equivalent LABELS; later on, when we actually need to implement  
TAGBODY...

As Helmut said, we'll need something like escape analysis to ignore  
anything
coming after a GO statement, which we could do now with Scheme's call/ 
cc:

CLHS has this example:

(let (val)
  (tagbody
   (setq val 1)
   (go point-a)
   (incf val 16)
   point-c
   (incf val 04)
   (go point-b)
   (incf val 32)
   point-a
   (incf val 02)
   (go point-c)
   (incf val 64)
   point-b
   (incf val 08))
  val)
=> 15

If I were writing TAGBODY for Scheme, I would probably write it with
syntax-case and have it transform that into something like this:

(let ((val ()))
  (letrec
      ((start (lambda ()
                (call-with-current-continuation
                 (lambda (k)
                   (define (go tag) (k (tag)))
                   (setq val 1)
                   (go point-a)
                   (incf val 16)                   ;; warning -  
unreachable code
                   (point-c)))))
       (point-c (lambda ()
                  (call-with-current-continuation
                   (lambda (k)
                     (define (go tag) (k (tag)))
                     (incf val 04)
                     (go point-b)
                     (incf val 32)                 ;; warning -  
unreachable code
                     (point-a)))))
       (point-a (lambda ()
                  (call-with-current-continuation
                   (lambda (k)
                     (define (go tag) (k (tag)))
                     (incf val 02)
                     (go point-c)
                     (incf val 64)                 ;; warning -  
unreachable code
                     (point-b)))))
       (point-b (lambda ()
                  (call-with-current-continuation
                   (lambda (k)
                     (define (go tag) (k (tag)))   ;; warning - no  
use of go
                     (incf val 08))))))
    (start))
  val)
/dev/stdin:42:30: warning - no use of go
/dev/stdin:29:22: warning - unreachable code
/dev/stdin:37:22: warning - unreachable code
/dev/stdin:21:20: warning - unreachable code
15


Things to note:
1. The implicit first "start" label, which would probably need to be a  
gentemp'd symbol.
2. The go tags can be any kind of atom, so I would probably turn each  
of those into a
   new predictably-named symbol, something like (string->symbol  
(format #f "label-~A" tag)).
3. GO requires fancy syntax-case anaphoric tomfoolery since it's  
intentionally non-hygienic.
4. I'm not sure whether this would properly handle a nested TAGBODY  
GO'ing to a tag from
   an outer TAGBODY.
5. Each lambda body ends with an inserted call to the next tag from  
the source code to
   handle fall-through.

> > Implementations also use MACROLET quite a bit
> > too, but I'm not sure how to approach that. There's also  
> > docstrings..!
>
> Let's not get ahead of ourselves.
>
> > Frankly, I'm loosing my way a bit here in terms of what my goals
> > should be, I'm spending a lot of time on just trying to port code  
> > from
> > SBCL, and I don't feel like I'm making good progress.
>
> Porting DESTRUCTURING-BIND from SBCL seems like the right thing to me.
> But you don't need to fix Kawa so that the code runs unmodified.  If  
> the
> code uses some exotic features, like that &key ((foo bar)) bit, I  
> would
> rewrite that before fixing the compiler.

+1, unless the compiler fix is trivial (sounds like Per thought it  
might be?).

> > DESTRUCTURING-BIND was the goal, but I've pushed several things on my
> > todo stack before that can be implemented. Apologies for
> > disorientation! I'm still struggling with the whole "what should I
> > implement to the spec, what should I skim over to fix later".
>
> So what still on the TODO stack?
>
> You've already done a lot to make &optional/&key work for normal  
> lambdas.
> Do you have some test cases for that?  Should it be reviewed?
>
> Helmut



-Jamie

--
Jamison Hope
The PTR Group
www.theptrgroup.com