Re: How often are continuations created?

[Keisuke Nishida <kxn30 at po dot cwru dot edu>]

Marius Vollmer <mvo@zagadka.ping.de> writes:

> I see.  But why are you putting a and b into external frames?  Because
> they are mutable?  Or because there is a call/cc lurking?

Because there is a call/cc.  They are usually local variables:

  (lambda (a) (set! a 1)) =>

  .program1
    %make-program .program2
    %return

  .program2
    %loadi 1
    %savel:0                ;; `a' is local
    %loadi #<unspecified>
    %return

The compiler externalizes all possible mutable variables modified
by continuation calls.

> I think you want to be able to optimize things like
> 
>     (do ((i 0 (1+ i)))
>         ((= i N))
>       (vector-set! v i (magic-computation i)))
> 
> into code that doesn't use an external frame for `i' and likewise does
> not create a fresh frame for every iteration.  When you use only a
> single frame (which is legitimate because the binding of i can not be
> captured by a closure), you need to modify it.

My current compiler does it:

  (do ((i 0 (1+ i)))
      ((= i N))
   (vector-set! v i (magic-computation i)))  =>

  ;; expanded by syncase (how could I avoid this?)
  (let doloop ((i (quote 0)))
    (if (not (= i N)) 
        (begin
          (vector-set! v i (magic-computation i))
          (doloop (1+ i)))))  =>

  ;; expanded by the compiler
  (letrec ((doloop (lambda (i)
                     (if (not (= i N)) 
                         (begin
                           (vector-set! v i (magic-computation i))
                           (doloop (1+ i)))))))
    (doloop 0))  =>

  .program1
    %make-program .program2
    %savee:0:0              ;; (set! doloop (lambda ...)) `doloop' is external
    %pushi 0
    %loade:0:0
    %tail-call 1            ;; (doloop 0)

  .program2
    %pushl:0                ;; `i' is local
    %loadt N
    num-eq2                 ;; (= N i)
    not                     ;; (not (= N i))
    %br-if-not L1
    %pusht v                ;; v
    %pushl:0                ;; i
    %pushl:0
    %loadt magic-computation
    %call 1                 ;; (magic-computation i)
    %push
    %loadi 3
    %func vector-set!       ;; (vector-set! v i (magic-computation i))
    %loadl:0
    1+                      ;; (1+ i)
    %push
    %loade:0:0
    %tail-call 1            ;; (doloop (1+ i)) tail recursive call
L1: %loadi #<unspecified>
    %return

Currently, a frame is created only when a procedure is called:

  (let ((a 1)) (let ((b 2)) a b)) =>

  .program1
    %loadi 1
    %savel:1     ;; (set! a 1)
    %loadi 2
    %savel:0     ;; (set! b 2)
    %loadl:1     ;; a
    %loadl:0     ;; b
    %return

I removed %bind, %unbind, and %export instructions.  %call does everything.

> But magic-computation might use call/cc in a way that would invalidate
> the assumption that we do not need a new frame for every value of `i'.
> Hmm.  Can bindings be made optimistically intern, and be externalized
> when they are captured by call/cc?

Since magic-computation is a procedure, %call creates a new frame for
it.  `i' is still a local variable because magic-computation cannot
refer to it.  Is there any problem with this?

> I think it would be easier to provide support for the features of your
> VM on the Scheme level and then translate to Scheme.  For example, we
> could have something like the `tagbody' of Common Lisp and your
> compiler could generate efficient code for it.

Yes.. with some extensions to the Scheme compiler for such procedures,
it is possible to generate efficient code.  One thing I had in my mind
was the dynamic scope support for Emacs Lisp, but it will be solved in
a similar way.

I totally agree that it is a good idea to have a good intermediate
language like Scheme for translation.  Okay, I'll specialize the
compiler for Scheme.