[stack] possibilities for macros in a typed language

Recently, I've been thinking about what sort of macro system might be  
suitable for a typed concatenative language. For this discussion, I'll  
assume a language like Cat minus any form of locals/variables. I'll  
call this hypothetical language 'Kitten' from this point on.

Adding macros to Kitten seems fairly easy at first as the syntax is  
easily representable as a list and there are no variables to get in  
the way. Given that adding macros is fairly easy, it seems worth doing  
if they'd be truly useful.

But are they? In Lisp, macros are most commonly used for two reasons.  
The first is a lack of a concise syntax for anonymous functions, but  
this isn't an issue in Kitten. The second is dealing with bindings and  
binding constructs (SET!, etc), but this also isn't an issue. There  
are other uses of macros, but these two probably comprise 90% of the  
use cases.

What other uses then might macros have in Kitten? One use I've come up  
with is allowing a way to write constructs that would otherwise be un- 
typeable. For an example, the m combinator 'dup i' cannot be assigned  
a type for the same reason that '\x -> x x' cannot be assigned a type  
in Haskell; it requires the construction of an infinite type. (Cat's  
version of 'i' is called 'apply' I believe.)

Even though 'dup i' isn't typeable, expressions like '[swap] [swap] i'  
and '[dup] [dup] i' are. Accordingly, we could define a macro like  
'[$A] m => [$A] [$A] i' that would work with quote literals. Such a  
macro is writable in a simple declarative system similar to Diggins's  
MetaCat (http://www.cat-language.com/metacat.html), although I believe  
MetaCat isn't currently usable for such things.

Another deficiency of the type system is a lack of number  
parameterized types. As such, you can't write a function like 'ndup'  
that duplicates the top N values on the stack. With an appropriate  
macro system however, you could expand '3 ndup' to a typeable  
construct. You would need something more powerful than MetaCat to do  
so however.

Optimization is another use of macros (as MetaCat shows). Slava Pestov  
recently walked me through some of the more interesting use cases of  
macros for optimization in Factor as well; 'case' is a good example.

There are of course additional, more complex uses. One example would  
be a macro that translates code that uses locals to code that's  
pointfree. Another might be pattern matching. It's not clear if there  
are sufficiently many of such use cases to warrant the addition of a  
macro system as opposed to simply adding a few additional core  
syntactic constructs.

There are obviously downsides to macros as well. Firstly, you  
sacrifice something in terms of concatenativity. For example, 'A B C  
D' might not be decomposable into 'A B' and 'C D' if macros are  
involved. You also lose something in terms of consistency as  
constructors like 'm' would only be usable with function literals and  
not functions passed at runtime. Finally, you lose the "everything is  
a function" aspect of Kitten. In Kitten, even the literal '3' is  
really a function with the type 'A -> A int'. Similarly, '[dup]' is a  
function with the type 'A -> A (B c -> B c c)'. Macros eliminate this  
property, although perhaps some syntactic means of distinguishing  
macros and functions could help.

Macros are a huge design space. It seems to me that there are  
essentially four possibilities for such a system in Kitten:

1. Offer a MetaCat-like system, perhaps with some additional  
expressivity. This covers a fair chunk of the optimization cases very  
simply and it's declarative nature means that you don't need to write  
macros that cooperate with the type system. (Of course the result of  
the rewriting needs to be typeable.) It also allows for 'm' and  
perhaps other more difficult combinators (condnestrec?) to be  
integrated, at least when dealing with literals.

2. Offer a somewhat Lisp-like system where macros are pure functions  
of the type '[parse-entity] -> [parse-entity]'. This allows more  
flexibility than the MetaCat system, although pointfree syntactic  
manipulation is likely to be more complicated in practice. It is also  
likely to be a good deal more verbose as you'll either need to be  
deconstructing and reconstructing parse-entity sums or casting into  
and out of some universal type.

3. Take the Factor approach and offer proper parse words and  
everything derivable from them. Again, this seems like even more  
flexibility at the cost of even more complexity. I'm not too  
interested in this approach for a language like Kitten; it makes a lot  
of sense for Factor though.

4. Offer no macro system whatsoever as the possibilities aren't worth  
the downsides. Something like MetaCat would be integrated directly  
into the system for purposes of optimization only and wouldn't be  
exposed to the user.

Of course, you could always just use Joy and get runtime macros for  
free!

Many thanks if you've managed to keep reading this long. If anyone has  
thoughts on what an ideal macro system for a Kitten-like language  
might be, or even if such a system is useful, they'd be much  
appreciated.

- John