Re: r3rs presentation (long)

[Kent Dybvig <dyb%indiana.csnet@CSNET-RELAY.ARPA>]

    On less significant presentation issues, I would like to present a
    view that a less sophisicated user of Scheme may get about
    continuations.  That is, this reader may conclude that continuations
    are very powerful and always expensive to use.  I know that the T
    compiler of 1981 generated goto's from the a catch and throw
    expression that exited a loop from within a loop.  (Catch and throw is
    old syntax for using continuations.)  Since we promise that
    tail-recursive procedures are executed in constant space, can't we
    promise something about certain simple uses of continuations?
    Otherwise, they may avoided by programmers for the wrong reasons.

The T compiler of 1981 did not support continuations, just Lisp-style
catch and throw.  However, simple uses can be compiled into jumps or
not much more.  For instance, a smart compiler can tell that

    (call/cc (lambda (k) (if (zero? x) (k x) (/ 1 x))))

requires nothing more than a goto for (k x).  The ability to perform
this improvement is easily lost; if k is returned, placed somewhere,
or invoked from within a closure that is returned or placed somewhere,
etc., the full continuation must be made.  Recursion makes things a
little more difficult, since it requires not just a goto but some way
of recording the depth of the stack.  What's more, it takes a fairly
sophisticated compiler (or some special-casing) not to trip on

    (call/cc
       (lambda (return)
          (letrec ([g (lambda (l a)
                         (cond
                            [(null? l) a]
                            [else
                             (when (zero? (car l)) (return 'oops))
                             (g (cdr l) (/ a (car l)))]))])
             (g some-list-of-numbers 1))))

because it appears that return is closed over even though g can be
implemented as a simple loop (but couldn't be, for example, if the
closure g itself were returned instead of 'oops).  But this may be
just what the "do" expression below turns into.

    (call/cc
       (lambda (return)
          (do ([l some-list-of-numbers (cdr l)]
               [a 1 (/ a (car l))])
              ((null? l) a)
              (when (zero? (car l)) (return 'oops)))))

(Actually, it's worse than that, since letrec is itself a derived
form and really appears as a convoluted combination of lambda and
set! expressions.)

Making a guarantee that call/cc produces essentially gotos in simple
situations might backfire, too, resulting in convoluted code to take
advantage of the faster call/cc.  For instance, a programmer might
abandon map in favor of hand-coded loops, or not take full advantage
of closures and recursion.

Another problem with making such a guarantee is that call/cc is a
function, not a special form, and its value might change, e.g., for
tracing or "constraining control".  Certainly, it would be possible
to generate code for the first example something like

    (if (eq? call/cc *primitive-call/cc*)
        {fancy goto code for (if (zero? x) (k x) (/ 1 x))}
        {normal application of call/cc to (lambda (k) ...)}),

but this would be clumsy and wasteful of code space.

Some implementations of Scheme currently promote some or all primitive
functions almost to special form status... if the identifier's binding
is the expected one at compile time, assume it will be at run time and
generate inline code.  For example, car and cdr might be inlined this
way.  In these systems, call/cc could presumably be nailed down too.
But it cannot be guaranteed so in the RRRS without implying that some
primitives are really special forms.

Since I have brought the issue up, how does everyone feel about this
special treatment for primitives?  Should it be explicitly allowed or
disallowed?  All of the arguments against allowing extra special forms
come in to play here as well, plus others, so I'd say it should be
disallowed, at least by default.  I have no problem with some sort of
flag controlling this behavior, e.g., (set! *benchmark-mode* #t).  Or
perhaps we want to say that all primitives are special forms or that
primitive identifiers are not assignable (I don't think so).

How about making call/cc a special form?  I've often wondered if it
should be even though its evaluation rule would be the same as for
function application.  Call/cc is basic to any system, and support
for it must be provided by the compiler, at least in the way it
represents things.  Why should something be a function and not a
special form just because its evaluation rule coincides with the
evaluation rule for function applications?

(By the way, what about "not"?  How many times have you seen someone
turn a conditional expression around to avoid the extra call?)


Kent