Is there a language which is not stack-based? I imagine "concatenative" would be mildly more precise of a description.
Coroutines (which often carry their own stacks) can sort-of dodge stacks—effectively utilizing a sort of bespoke linear typing to avoid this—but I don't know of a language which doesn't have c-like, stack-based procedures or subroutines, which places arguments on the stack and registers and operates mostly with respect to that stack and foreign API calls.
A stack is certainly the most intuitive data-structure with which to implement a lambda calculus.
Really, what Forth and descendent languages seem to emphasize is a sort of a data-oriented execution rather than a symbol-oriented execution—C very much encourages you to name types, function signatures, etc, and the result if you don't is extremely difficult to parse and interpret manually, even if you can implement forth as a subset of C.
Forth emphasizes reasoning about the stack directly as data, seemingly forgoing any assistance outside of syntax. Arguably it forgoes the utility of syntax, too.
True, it's a convenient structure, but the Church–Rosser theorem says that the order of beta reduction of terms in the lambda calculus doesn't matter, so a call stack pattern isn't essential.
Conceptually, I would say other languages are variable-based. The key feature of a stack is that you can only access the top element, whereas other languages allow you to name multiple things and access them simultaneously (effectively reaching down the stack to elements not directly accessible). This is implemented with a stack-like structure, but sometimes also using registers. I wouldn't call these languages stack-based because the stack is more of an implementation detail than a defining feature of the language.
For isntance, in C:
int x(int a) {
int b = a >> 1;
int c = a + 34;
f(b);
return c;
}
You can still access the variable "b" in the call to "f" without having to get rid of the value in "c". Before "f" is called, the stack will likely be incremented by two integers worth of space at once, instead of adding the variables one at a time. Then once the block terminates, all variables relating to it are discarded simultaneously.
> Conceptually, I would say other languages are variable-based.
This seems less meaningful than "syntax-based" . Certainly, a "variable" is not a fundamental I deal with on a daily basis in c-based languages—there are necessary exceptions cause by the limitations of the language, of course, like accumulator symbols in a reduction process or state variables in some specific algorithm. Nor do I understand any utility such a concept bings to the table—in fact, this concept brings mostly pain I'd like to forget and forbid from future projects. I refer to "symbols", not "variables".
Regardless, variables are commonly implemented with a stack and are not trivial concepts to differentiate from the equivalent usage of a stack.
Perhaps I should argue for a "syntax-oriented" language instead.
I understand that procedural languages often have variables, but any method of programming that blesses this code as "good" typically doesn't bless the usage of variables outside of looping-with-an-accumulator, state machines, or some other formal usage. I certainly wouldn't emphasize this as any positive characteristic of the language given that its unique attribute is the ability to cause bugs by interacting with it incorrectly (god forbid you have a "pointer variable"—the most curse-upon-humanity type if such a concept were to ever exist)
I write compilers. I don't know why anyone would willing make the mistake of creating the concept of "variables" again.
By "variable" I mean a name with a value attached. It doesn't necessarily have to mutate. Forth doesn't let you define these within procedures. Values are communicated implicitly on the stack in Forth, where other languages give them names and then use the names to say where the value goes. From a compiler perspective, you could think of this as the difference between JVM bytecode and LLVM IR.
> "within" vs "not within" seems like a distraction.
It is a quite significant difference. A name bound at global scope exists with only one value. A name bound at function scope can be instantiated with different values depending on what the function is called with, and can hold multiple values at the same time if the function makes a recursive call to itself.
> I just don't see the distinction you're drawing as meaningful.
Yes, most languages are Turing-complete, so there isn't technically a difference between them. You are welcome to think the difference between Forth and other languages is not meaningful.
For completeness, there are languages that do not require stacks to implement (nor any workarounds that in practice emulate a stack). If you do not support explicit recursion, you don't need one. All variables can be statically allocated and only a single return address needs to be stored for each function, so you do not need a stack for return addresses either.
The most famous example is FORTRAN, until 1990 when they added RECURSIVE directive.
Yes, you are correct. My friend made this post so I didn't have control over the exact wording. That being said, in concatenative programming, the stack is public and, in my case, is virtual.
Coroutines (which often carry their own stacks) can sort-of dodge stacks—effectively utilizing a sort of bespoke linear typing to avoid this—but I don't know of a language which doesn't have c-like, stack-based procedures or subroutines, which places arguments on the stack and registers and operates mostly with respect to that stack and foreign API calls.
A stack is certainly the most intuitive data-structure with which to implement a lambda calculus.
Really, what Forth and descendent languages seem to emphasize is a sort of a data-oriented execution rather than a symbol-oriented execution—C very much encourages you to name types, function signatures, etc, and the result if you don't is extremely difficult to parse and interpret manually, even if you can implement forth as a subset of C.
Forth emphasizes reasoning about the stack directly as data, seemingly forgoing any assistance outside of syntax. Arguably it forgoes the utility of syntax, too.