The funny thing is, I originally didn't intend the TXR pattern language to be recursive. It needed functional decomposition (pattern functions) to break up a big pattern match into simpler units. When those were implemented, I realized after the fact, hey we have a push-down automaton that can now grok recursive grammars.

I don't see why we would want to rule out a pattern function invoking itself (directly, or through intermediaries); if that hurts, then just don't do that.

(Though I understand that there are languages deliberately designed without unbounded loops or recursion, for justifiable reasons.)

I found in practice that arbitrary recursion depth is (even on languages with formal recursive grammar) very rarely needed. And where it's needed it can probably be implemented as a primitive in the language (map total function over all the nodes) that can do a similar thing.

Then I think you will like https://tkatchev.bitbucket.io/tab/index.html

"It's statically-typed and type-infered.

It also infers memory consumption and guarantees O(n) memory use.

It is designed for concise one-liner computations right in the shell prompt.

It features both a mathematics library and a set of data slicing and aggregation primitives.

It is faster than all other interpreted languages with a similar scope. (Perl, Python, awk, ...)

It is not Turing-complete. (But can compute virtually anything nonetheless.)

It is self-contained: distributed as a single statically linked binary and nothing else.

It has no platform dependencies."

I am a little suspicous that you may be the author ;)

Looks very interesting, but I am not the author.

So XSLT then?

XSLT is Turing complete with the usual caveats about memory. Given its complexity it'd be very unlikely for it not to be, but there's clear proof too: someone has implemented a universal Turing machine in it.