Right, that’s what I said. Just because it’s efficient to implement one language that way doesn’t mean it’s efficient to do that for every language in the same family. :)

With non-variadic arithmetic functions:

    (defn add [x]
      (cons (+ (first x) (second x)) (rest (rest x))))

Your “postfix” function can remain a simple “reduce”, but can be totally agnostic of function arity. That frees you up to write the basic combinators:

    (defn dup [x]
      (cons (first x) x))

    (defn zap [x]
      (rest x))

    (defn swap [x]
      (cons (second x) (cons (first x) (rest (rest x)))))

    (defn ap [x]
      (apply (first x) (rest x)))

    ...

A data stack is indeed not required -- see Om (experimental):

http://concatenative.org/wiki/view/Om

It uses prefix notation: instead of a data stack, each function takes the remainder of the program for rewriting.

I whether or not there is a stack is similar to the complementary nature of foldL vs parallel fold (ie Clojure's core/reduce vs reducers). Left-to-right concatenative languages make use of a stack and are appropriate for side effects and stream processing. However, there are pure concatenative languages that operate in parallel via term rewriting, which has a computational model akin to that of a DNA computer.

Enchilada is a concatenative language which is not stack based but instead works through term rewriting.