Subject: Can fluid-let be tail-call-clean?
From: (Rob Warnock)
Date: 1999/03/03
Newsgroups: comp.lang.lisp,comp.lang.scheme
Message-ID: <7bj1a6$>
[Subject was ``Re: Barriers to Lisp acceptance - a "survey" question''
in comp.lang.lisp, but this sub-thread has drifted *way* off-topic
and off-group, even. So followups to comp.lang.scheme...]

cdm <> wrote:
| Rob Warnock <> wrote:
| >Seriously, though, the "fluid-let" style [or anything similar, based on
| >dynamic-wind, say] *implies* a non-tail call, yes?  'Cause you want the
| >value to be set *back*, yes? So failing to preserve tail-call optimization
| >shouldn't come as a surprise.
| Not exactly.  The top-level binding must, of course, be restored, but
| the intermediate bindings you make each time around the loop need not
| be restored.  So, if the implementation is clever enough, a fluid-let
| could be tail-recursive.

Yes, while replying to a similar side message from Dorai Sitaram, I
finally realized that both of you are correct. My apologies for not
seeing it sooner.

One way might be for the fluid-let to look at its own continuation,
and if that continuation is some sort of magic "fluid-let frame" that
contains a "restore" of the variable it's about to change, just pass
that continuation on to the body of the fluid-let without building a
new "restore" frame. And by hanging a *set* of variables on the magic
continuation, you could even handle things like the following with a
small stack (though there are some subtleties to worry about in case
one of those intermediate functions, like "perverse-func" below, captures
*its* continuation):

        (define *x* 0)
        (define *y* 1)
        (define *z* 2)

        (let loop ((n 0))
          (fluid-let ((*x* (1+ *x*)))
            (fluid-let ((*y* (* *y* 2)))
              (fluid-let ((*z* (expt *y* *x*)))
                (format #t "~s ~s ~s~%" *x* *y* *z*)
                (if (> *x* 10000000)
                  (list *x* *y* *z*)
                  (loop (1+ n)))))))

| It is probably unreasonable to expect this if fluid-let is implemented
| in terms of dynamic-wind (maybe not, though.  If the dynamic-wind were
| tail-called, and it's entry and exit thunks satisfied certain properties,
| perhaps....)

Well, I haven't thought that part completely through, but those "certain
properties" would have to be *awfully* restrictive if you're going to be
able guarantee that you can "fold" multiple logical invocations of the
"after" thunks into *one* invocation. [Folding multiple "restore"s of
a variable is *trivial*, by comparison...]


Rob Warnock, 8L-855
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA