3 ms·

Are all stack-based languages concatenative? What would it take for a stack language to not be concatenative?

saithound 5y ago
Nornally, we call a language concatenative if the concatenation (writing one after the other) of two programs p and q represents the program that computes the composite of the functions that p and q compute. This definition is far from rigorous, but it's good enough for identifying concatenative languages in practice. Most concatenative languages are stack-based, but there are some stack-based languages that are not concatenative (e.g. Befunge, a 2d language with self modifying code) and concatenaive languages that are not stack-based (e.g. Enchilada, which is based on term rewriting).
- beagle3 5y ago
  By your definition, even Python is concatenative, as is any language whose “main” is implicit and allows shadowing. The definition I saw ages ago is much more strict: If P is a program in a concatenative language, then for any A, B such that P=concat(A,B) and A and B are non empty valid programs, then executing A followed by executing B is equivalent to executing P. This does classify Forth, Joy and Factor as concatenative but not Python or line-number-less Basic. Not familiar with Enchilada. I actually got interested in this from a data compression persepective - dictionary compression of a concatenative program - even something as simple as LZ78, is LZ optimal, but still executable without decompressing…..
  - saithound 5y ago
    > By your definition, even Python is concatenative, as is any language whose “main” is implicit and allows shadowing. Not that it's worth arguing over a definition that's specifically marked as non-rigorous, but your statement is wrong, and Python is not concatenative under the definition presented above. The definition is fairly clear: a language is concatenative if the concatenation of two programs p and q represents the program that computes the composite of the functions that p and q compute. We can turn this into a formal definition: if we let concat(-,-)denote concatenation, o denote function composition, and [x] denote the function that the program x represents, the requirement is that the equation [concat(p,q)] = [q] o [p] should hold for all programs p,q. One would struggle to define the meaning of [-] for Python programs, much less prove that the equation above holds for some reasonable definition of the brackets [-]. (And if you could, then Python would be considered concatenative under your definition too)
    - beagle3 5y ago
      I am talking about simple string concatenation. Take two python programs "a.py" and "b.py", exclude command line arguments and stdio file descriptors - and, yes, the string concatenation of "a.py" and "b.py" will generally execute the same computation / "function" that executing "a.py", followed by executing "b.py" will compute. That's true of Forth as well (and you don't even need to exclude the stack state), but not of C. And indeed, it's not worth arguing about a non-rigorous definition, except that at the surface level there's a very inherent difference between the definition you presented and the one I know - which goes to the (rather unusual) definition of "concatenation" which appears to require function application in your definition, unlike the common use of the term in software in general. A quick look at Wikipedia[0] indicates we are both right; The overall definition does refer to programs as functions, but the "Properties" part says "Any subexpression can be replaced with a name that represents the same subexpression. This is referred to in the concatenative community as factoring and is used extensively to simplify programs into smaller parts." It is likely an equivalent requirement (from what I remember, it is, but I don't remember all the details), but relies on the standardized, general meaning of "concatenate" rather than a narrow one specifically for this definition. [0] https://en.wikipedia.org/wiki/Concatenative_programming_language https://en.wikipedia.org/wiki/Concatenative_programming_lang...
- LargoLasskhyfv 5y ago
  There is also (or rather was, because obscure now, and almost bitrotten) https://en.wikipedia.org/wiki/POP-11 https://en.wikipedia.org/wiki/POP-11 as part of https://en.wikipedia.org/wiki/Poplog https://en.wikipedia.org/wiki/Poplog

Nornally, we call a language concatenative if the concatenation (writing one after the other) of two programs p and q represents the program that computes the composite of the functions that p and q compute. This definition is far from rigorous, but it's good enough for identifying concatenative languages in practice. Most concatenative languages are stack-based, but there are some stack-based languages that are not concatenative (e.g. Befunge, a 2d language with self modifying code) and concatenaive languages that are not stack-based (e.g. Enchilada, which is based on term rewriting).

beagle3 5y ago
By your definition, even Python is concatenative, as is any language whose “main” is implicit and allows shadowing. The definition I saw ages ago is much more strict: If P is a program in a concatenative language, then for any A, B such that P=concat(A,B) and A and B are non empty valid programs, then executing A followed by executing B is equivalent to executing P. This does classify Forth, Joy and Factor as concatenative but not Python or line-number-less Basic. Not familiar with Enchilada. I actually got interested in this from a data compression persepective - dictionary compression of a concatenative program - even something as simple as LZ78, is LZ optimal, but still executable without decompressing…..
- saithound 5y ago
  > By your definition, even Python is concatenative, as is any language whose “main” is implicit and allows shadowing. Not that it's worth arguing over a definition that's specifically marked as non-rigorous, but your statement is wrong, and Python is not concatenative under the definition presented above. The definition is fairly clear: a language is concatenative if the concatenation of two programs p and q represents the program that computes the composite of the functions that p and q compute. We can turn this into a formal definition: if we let concat(-,-)denote concatenation, o denote function composition, and [x] denote the function that the program x represents, the requirement is that the equation [concat(p,q)] = [q] o [p] should hold for all programs p,q. One would struggle to define the meaning of [-] for Python programs, much less prove that the equation above holds for some reasonable definition of the brackets [-]. (And if you could, then Python would be considered concatenative under your definition too)
  - beagle3 5y ago
    I am talking about simple string concatenation. Take two python programs "a.py" and "b.py", exclude command line arguments and stdio file descriptors - and, yes, the string concatenation of "a.py" and "b.py" will generally execute the same computation / "function" that executing "a.py", followed by executing "b.py" will compute. That's true of Forth as well (and you don't even need to exclude the stack state), but not of C. And indeed, it's not worth arguing about a non-rigorous definition, except that at the surface level there's a very inherent difference between the definition you presented and the one I know - which goes to the (rather unusual) definition of "concatenation" which appears to require function application in your definition, unlike the common use of the term in software in general. A quick look at Wikipedia[0] indicates we are both right; The overall definition does refer to programs as functions, but the "Properties" part says "Any subexpression can be replaced with a name that represents the same subexpression. This is referred to in the concatenative community as factoring and is used extensively to simplify programs into smaller parts." It is likely an equivalent requirement (from what I remember, it is, but I don't remember all the details), but relies on the standardized, general meaning of "concatenate" rather than a narrow one specifically for this definition. [0] https://en.wikipedia.org/wiki/Concatenative_programming_language https://en.wikipedia.org/wiki/Concatenative_programming_lang...
LargoLasskhyfv 5y ago
There is also (or rather was, because obscure now, and almost bitrotten) https://en.wikipedia.org/wiki/POP-11 https://en.wikipedia.org/wiki/POP-11 as part of https://en.wikipedia.org/wiki/Poplog https://en.wikipedia.org/wiki/Poplog