I wonder if I should make a new macro system that is different from
the term rewriting rules for Cat, or if I should extend the
expressiveness of the term rewriting rules. The problem is that term
rewriting rules are declarative, and performing any real programming
with declarative constructs is very hard. See for example: XSLT.

I want to implement something like what Tom Schouten and others have
done using Scheme macros to translate blocks of code into new blocks
of code, but where data is passed along the way. It is kind of like
translating Cat code into CPS (continuation passing style) format, or
a kind of pseduo-monad. Basically every statck instruction gets
wrapped with a "dip" instruction, so that the data on the top of the
stack is left unmolested.

So the question is: to do this do I extend the term rewriting system,
add another macro system, or add declarative constructs to the
language. The last one is not really an option as far as I am
concerned.

Just thinking out loud, feel free to jump in and comment.