Can a Forth-like language be implemented with just one stack?

Question

Forth has a stack and a return-stack.

As far as I understand, the point of the return-stack is to store the previous values of the program counter.

C programs put the previous value of program counter on the stack, and use no return stack.

Does Forth only need a return-stack because it returns result(s) on the stack, and thus the previous value of the program counter could be buried?

Answer 1

The "Portable Assembly Language" should be close. It's a concept for a compiler for a language which is almost identical to standard/traditional Forth. There are some restrictions for which kind of programs can be written. Mostly, you have to avoid situations where the depth of the stack can't be statically determined.

This language can be compiled in a way that only requires one stack.

http://www.complang.tuwien.ac.at/anton/euroforth/ef13/papers/ertl-paf.pdf

Answer 2

Preface: I've written extensions for hardware debuggers to trace some problems with messed call stacks, so I've seen some hex dumps of actual C stacks.

The C stack consists of a mixture of return addresses, local variables and function parameters. For each function you can find out where it expects which value, but this knowledge stops at the scope of the function.

You can do it this way with forth as well, but this means a giant overhead: You can place your parameters on the stack and call the function, placing the return address on top of the same stack. No problem: Each command knows that the operands are second and following on the stack. But now the command wants to call another command with these values: This makes it neccessary to change the order of the stack to put the values on top again, as the called command can't know where they are buried in the stack, as you wrote.

A more complex forth compiler could keep track of how many values each command takes and sort the stack before each command call. But at what cost!

Of course, C programs have this overhead, too. If you see non-inline function calls in inline assembly, there is always some register swapping overhead. But good forth programs consist of tiny functions, so you have a lot more function calling and a lot more overhead.

And without any benefit, as in modern computer architecture each register can be used as stack pointer, so you could have a handful of stacks without any problem.

So finally, the answer to your question is: Yes, you can implement a one-stack derivative of forth, but it's pain without gain.

Answer 3

"Forth has a stack and a return-stack." This is true for every extant and preceeding Forth standard, for pre-standard dialects and even for dialects like colorforth that some hesitate to call Forth.

So you have answered your own question:A resounding no. The two stacks are central to the Forth programming model. The programmer is entitled to manipulate both.

The reason is of course that you handle the data yourself and a return address would be in the way. If you insist to compare it with C, C manipulates the data by name, and handles the returning. In fact C has no stack in its programming model. Using one stack is an implemention detail that your are not supposed to worry about.