Definition of a Function in Concatenative Languages

Concatenative languages are languages where juxtaposition of functions represents composition. Programs consist of the primitives in the language combining to form a large function which takes program input as its argument and whose return value is written to output.

In many concatenative languages, all functions take and return the same structure so that the language can be implemented as a pipeline of operations on that structure. In the case that this structure is a stack, you get a model for many stack-based languages such as Joy, Underload, and CJam. For example, consider the following program that computes (n+1)2:

1 add dup mul


This is a composition of four different functions:

• 1 is a function that pushes 1 to the top of the stack.
• add is a function that replaces the top two items on the stack with their sum.
• dup is a function that makes a copy of the top item on the stack and pushes it again.
• mul is a function that replaces the top two items on the stack with their product.

We allow submissions in the form of functions. Usually, in CJam, I take this to mean a block like {1+_*}. This is the example given in the linked answer, but with the concatenative interpretation, 1+_* is a function, and {1+_*} is a function that pushes a function to the stack.

In Python, if some function f was a valid submission, lambda s:s[:-1]+[f(s[-1])] would certainly not be. The latter seems to be what I've been doing for answers in concatenative languages.

My question, then, is that there are two viewpoints for this in a stack-based language:

• The theoretical viewpoint, in which juxtaposition of several functions composes them into a new function.
• The viewpoint of the implementation (which just applies each of the operations in sequence), in which the same juxtaposition of functions is a snippet that operates on some state already assumed to exist (the stack).

Which perspective is correct here?

• I think one important part of what we consider a function is that you can invoke it as often as you like without having to repeat the code. You can't do that with 1+_*, but you can store {1+_*} in a variable. – Martin Ender Mar 18 '18 at 8:05

We already have a consensus that functions have to be reusable arbitrarily often.

While that consensus arose in the context of side effects (such as changing global variables in a way that prevents the function from working more than once), I think we should apply it to this situation as well.

1+_* is not a function. Yes, it operates on the top of the stack (as a function would), and yes, it pops n and pushes (n+1)2 (as a function would), but you can only use it once.

The whole point of defining a function is that you don't have to write the same code more than once to perform the same procedure. {1+_*} clearly satisfies this, as you can make a copy from wherever (<n>\$), save it in a variable (:F), or map it over an array (%). The bare 1+_* doesn't allow you to do any of these things.

This is the example given in the linked answer, but in reality, 1+_* is a function, and {1+_*} is a function that pushes a function to the stack

You seem to be assuming the answer you want within the "question", but your working definition of function is certainly open to debate. The reason that the linked answer to the primary meta question on this subject calls CJam blocks "function-like" is because when that answer was written blocks, J verbs, etc. were not considered to be functions, strictly speaking.

Consider that the name function has been used in language documentation for something like 50 years. If a language's doc doesn't describe the syntax to define a function, there's probably a good reason why the language designer(s) didn't consider it to have them.

• Using the spec to define these things isn't reliable. Brachylog's spec doesn't mention the term "function" either, but it seems to be treated as such by numerous submissions. – Esolanging Fruit Mar 23 '18 at 18:48
• @EsolangingFruit, from a pedantic point of view, they're wrong: Brachylog has predicates, not functions. I'm sure you can find many other technically false claims in answers on main. But the question that matters is whether Brachylog predicates are function-like. – Peter Taylor Mar 23 '18 at 20:26