# RE: [stack] Continuations (was: Wow, a good start)

## wtanksley@bigfoot.com — 2000-05-01 20:58:08

    From: iepos@... [mailto:iepos@...]

     >> In an applicative language, a continuation is a stack frame:

    >> it contains all

    >> parameters and all local variables of the function in

    >> question.  The problem

    >> is that concatenative languages have neither parameters nor

    >> local variables.

    >> As far as I can tell, a continuation is merely "the rest of

    >> what would be

    >> executed in this function": in other words, it's a pointer

    >> to your current

    >> position in the current word.  Four bytes, give or take.

    >Here's my understanding... a stack frame in an applicative language

    >is very similar to the data stack in a concatenative language (such as

    >FORTH or Joy), with this exception: an applicative stack frame will

    >contain an explicit return address pointer (i.e., the continuation

    >parameter) whereas a concatenative data stack typically would not

    >(instead relying on a separate "return stack" for this purpose).

    >Other than that, an applicative stack frame pretty much does the same

    >thing as a data stack in a concatenative language... both are used

    >to pass around parameters and local variables (although, in a

    >concatenative

    >language there is not a distinction between parameters and

    >local variables).

     There's a problem here.  The applicative stack frame is used to hold

    parameters which have been applied to the function, and that's why we save

    it in order to produce a complete continuation.  If we have to save all of

    the data stack, this implies that our language is actually applicative, and

    that pretending otherwise is only a surface sham, doesn't it?

    It also makes it impossible to pass parameters to the continuation.

     >By the way, now seems like a good time to bring up the FORTH-like

    >technique of keeping the return stack separate from the data stack.

    >It seems like a good technique in many ways. Most importantly,

    >it permits one to call a subroutine seamlessly, without making copies

    >of things that are already on the stack, provided that they are in the

    >right place (otherwise, they might have to be swapped around).

    >This can result in speed savings, and in the case of deep recursion,

    >space savings as well.

     I think this is a good point -- in fact, I don't think it's possible to make

    a concatenative language which shares the data stack with the return stack.

    The two are completely unrelated to each other.

     >However, I'm guessing that in a system that does inlining well,

    >the vast majority of time will be spent in an innermost procedure,

    >so that the overhead involving calls might not matter that much anyway.

     Just as an introduction, iepos and I have been arguing over inlining.  He is

    of the opinion that the best inlining is maximal inlining; every time it's

    vaguely possible to inline, you should.  I am of the opinion that the best

    inlining is NO inlining; whenever it's possible to make a call instead of

    inlining the function, you should.  (Cool difference of opinion, huh?)

    I justify my position by noting that call overhead is minimal in

    concatenative languages.  I'm sure he can defend his own position well, but

    his response to that would probably be that the call time is still not zero.

    We could go on for quite a while there.  :-)

    One nice thing about concatenative languages is that inlining is truly

    transparent; there's no code changes needed.

     >- Brent Kerby ("iepos")

     -Billy

## iepos@tunes.org — 2000-05-02 00:06:15

    > >Other than that, an applicative stack frame pretty much does the same

    > >thing as a data stack in a concatenative language... both are used

    > >to pass around parameters and local variables (although, in a

    > >concatenative

    > >language there is not a distinction between parameters and

    > >local variables).

    >

    > There's a problem here.  The applicative stack frame is used to hold

    > parameters which have been applied to the function, and that's why we save

    > it in order to produce a complete continuation.  If we have to save all of

    > the data stack, this implies that our language is actually applicative, and

    > that pretending otherwise is only a surface sham, doesn't it?

     Okay... I'm sort of confused... saving the whole data stack would be

    a very silly, inefficient thing to do in most cases, and wouldn't

    make sense in a concatenative system, but I don't see how it would

    turn the language into an applicative one. Anyhow, I didn't suggest

    saving all of the data stack.

     > >By the way, now seems like a good time to bring up the FORTH-like

    > >technique of keeping the return stack separate from the data stack.

    > >[...]

    >

    > I think this is a good point -- in fact, I don't think it's possible to make

    > a concatenative language which shares the data stack with the return stack.

    > The two are completely unrelated to each other.

     True... it would be quite tricky to share the data stack with the return

    stack in a concatenative system...

     > Just as an introduction, iepos and I have been arguing over inlining.  He is

    > of the opinion that the best inlining is maximal inlining; every time it's

    > vaguely possible to inline, you should.  I am of the opinion that the best

    > inlining is NO inlining; whenever it's possible to make a call instead of

    > inlining the function, you should.

    >

    > I justify my position by noting that call overhead is minimal in

    > concatenative languages.  I'm sure he can defend his own position well, but

    > his response to that would probably be that the call time is still not zero.

     It might be useful now to mention some of the pros/cons of inlining...

    First, some good things that can happen if you don't inline (i.e.,

    instead use a procedure via a pointer):

      1) Storage savings, because one does not have to make redundant

         copies of identical procedures.

      2) Speed improvement. Because of the smaller code size, it may be

         possible for a loop to fit within a processor's cache, whereas

         if we had inlined it might not have fit.

    These advantages only apply if the same procedure is being used multiple

    times. If a procedure is only going to be used one time then inlining

    would almost certainly be better, I think. Now, some advantages of inlining:

      1) Time is saved by not jumping around.

      2) Caching may work better because related code will be kept close

         together, whereas if one had not inlined one might have jumped

         way off to some far location and occupy a page of cache

         that is not being used except for one short procedure.

      3) It may be possible to allocate registers more wisely.

         If one uses a procedure multiple times via a pointer, then it

         is necessary to decide one fixed register interface that must

         work for all callers; callers may then need to swap things around

         whereas they wouldn't if the procedure had been inlined.

      4) It may be easier to garbage-collect the procedure when it is

         no longer needed. If one has a complicated tree (or worse yet, a web)

         of procedures that call one another, then garbage-collection will

         tricky. Inlining procedures would permit the web to be simpler.

         (note: problem number 4 with call-by-pointer doesn't happen in

          traditional systems (say, UNIX) because there is nearly no

          dynamic generation of code, and because it is considered tolerable

          for code in a process to be sitting around even when it is

          no longer needed, as long as it is eventually freed when

          the process terminates. I would suspect that garbage-collection

          of procedures would become more serious if one has dynamic

          generation of code, as I'm guessing we'd want in a system)

    For small procedures, these advantages tell me that inlining is a

    good idea. But, for large procedures, the storage savings compel us

    to use a pointer (and not inline). I'm not sure where the best place

    is to draw the line. I would estimate that maybe about 1K is a good

    place to stop inlining... but maybe that's too high. Experimentation

    is probably the best way to figure that out...

    By the way, to me the issue of inlining-vs-call-by-pointer seems like

    just a special case (although perhaps quite special) of the more

    general question of when to copy data structures by-value and when

    to copy by-reference. The answer I think that came up earlier is this:

      The smaller the data structure, the more we want to copy-by-value.

      The further apart that the data structure is going to be spread

        out across the system, the more we want to copy-by-value.

    As an extreme case, if a data structure is going to be sent all the way

    across a network to other computers, we would only attempt copy-by-reference

    in most dire circumstances (i.e., very large size). And, of course,

    copying-by-reference will not work if one user wants to modify the

    structure (although it might be possible for just the modified portion

    to be copied with the rest still copied by reference).

     > One nice thing about concatenative languages is that inlining is truly

    > transparent; there's no code changes needed.

     True...

     > >- Brent Kerby ("iepos")

    >

    > -Billy

     - Brent Kerby ("iepos")