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