# return stack

## Keith Rarick — 2005-04-18 08:41:17

    Greetings. I've recently begun reading about concatenative languages. I

    have some questions about the nature of the return stack and how it

    relates to the "program" itself. I can think of two ways to look at the

    execution of a quotation by a combinator:

    In one view, a call frame in the return stack contains a program and a

    pointer to the next word to be executed. Invoking, say, the i combinator

    has the effect of creating a new call frame with a program in it (which

    program came from the top of the data stack). When this program is

    finished, execution returns to the previous call frame. At the beginning

    of time, the return stack would have exactly one element and the pointer

    would be at the beginning of the program.

    Or, you could say that the return stack *is* the program. Then invoking

    the i combinator simply pushes the contents of its quotation onto the

    return stack. Here, at the beginning of time the return stack would have

    many elements already in it: one for every word.

    Without the ability to see and manipulate the return stack, these two

    views are equivalent as far as I can tell. Which one (if any) is the

    traditional view? Are there other differences I haven't thought of?

    Obviously they are very different when you allow the program to do

    things to the return stack other than just return.

    -Keith

## William Tanksley, Jr — 2005-04-18 19:27:48

    On 4/18/05, Keith Rarick <kr@...> wrote:

     > relates to the "program" itself. I can think of two ways to look at the

    > execution of a quotation by a combinator:

    > In one view, a call frame in the return stack contains a program and a

    > pointer to the next word to be executed. Invoking, say, the i combinator

    > has the effect of creating a new call frame with a program in it (which

    > program came from the top of the data stack). When this program is

    > finished, execution returns to the previous call frame. At the beginning

    > of time, the return stack would have exactly one element and the pointer

    > would be at the beginning of the program.

     That's fine.

     > Or, you could say that the return stack *is* the program. Then invoking

    > the i combinator simply pushes the contents of its quotation onto the

    > return stack. Here, at the beginning of time the return stack would have

    > many elements already in it: one for every word.

     That's also fine.

    I don't know if any actual languages work like this, but Chris' paper

    on his Queue-based language (as opposed to our stack based languages)

    discussed these two possibilities.

     > Without the ability to see and manipulate the return stack, these two

    > views are equivalent as far as I can tell. Which one (if any) is the

    > traditional view? Are there other differences I haven't thought of?

     Neither one is traditional. Forth actually keeps a separate data

    structure, the "instruction pointer", which behaves the same as the IP

    in most microprocessors. Thus, the return stack does not hold any

    indicator of what is currently executing. This is neccesary if you

    plan on allowing any program manipulation of the return stack, since

    any manipulation would obviously change the rTOS, thus instantly

    destroying the VM's idea of what was currently executing.

     > Obviously they are very different when you allow the program to do

    > things to the return stack other than just return.

     Correct.

     > -Keith

     -Billy