Re: How often are continuations created?

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

Jost Boekemeier <jostobfe@calvados.zrz.TU-Berlin.DE> writes:

> > I think the control stack of a continuation is copied back into the
> > currently active stack when the continuation is invoked.  Isn't that
> > the case?  
> 
> Yes.  I think I got confused by the wording.  Why are there two
> stacks, a data stack and a control stack?  I thought in Keisuke's
> implementation the data stack is what their paper calls the "control
> stack segment".  You could push everything on the stack except the
> "boxed" variables which failed the "set!" test.  So copying the whole
> stack or the whole stack segment isn't a problem.  What Hieb's paper
> avoids is unbounded stack copying by splitting the control stack into
> segments.  IMHO the "data stack" isn't necessary, is it?

No, the control stack is what they call the control stack.  I don't know
where they put intermediate results, but I guess they use local variables
in the frame for every computation.  On the other hand, I use a stack for
intermediate results, which is why I needed a data stack.

I need to improve my compiler before being able to use local variables
for storing intermediate results; otherwise, data stack copying must be
needed.  I guess this will become an obstacle to implementing your
hybrid solution, too.

However, I'm not sure whether using local variables for intermediate
results is more efficient than using a stack.  This is how I allocate
a frame for a procedure call:

  (foo 1 2 3) =>

  %pushi 1      ;; push all arguments
  %pushi 2      ;;  into the stack
  %pushi 3      ;;  in order
  %loadt foo    ;; load the procedure
  %call  3      ;; call it with three arguments

This is the contents of the stack before %call is executed (now I use
a single stack):

  fp->|local vars|
      |frame data|
      |    1     |
      |    2     |
      |    3     |
  sp->|          |

After executing %call, 1, 2, and 3 become local variables in the new
frame.  I do this by just changing the value of fp:

      |local vars|
      |frame data|
      |    1     |
      |    2     |
  fp->|    3     |
      |frame data|
  sp->|          |

This is why procedure calls are very efficient; there is no data copy.
(On the other hand, data must be copied for tail recursive calls.)

> 3. Clinger's solution.  Use a single stack.  When a continuation is
>    reinstated everything is copied from the stack to the heap and
>    stays there.  Easy to implement but slows down the VM a little bit
>    because the code must check if it actually returns from a
>    heap frame or from a stack frame.  I think this solution (which
>    I am currently implementing -- yes, still ...) is the best one.

I guess its slow down is insignificant, but the intermediate results
mentioned above are bothersome.