But it sure is overhyped and it being proprietary is a huge drawback.
But that's not the point anyway - you can implement lots of things on top of Lisp.
Lisp is based on a specific evaluation model. Not term rewriting. The way macros are computed is slightly related (since they take source and return source), but that's all.
In particular the symbolic nature of the language means that everything is first class, functions and function constructions ("functional programming") and expressions in general ("macros") being just basic cases.
if you're trying to make a traditional macro, you would implement it as a function with the HoldFirst et al attribute.
an important thing to know is that ReplaceAll uses arbitrary structural patterns. it's not a simple "turn every a into b". you can say things like "turn every application of the symbol F on an even number into an application of G on that number divided by two".
expr /. F[n_?EvenQ] :> G[n/2]
Right.
> In other words its rewrite system is so powerful that lisp can be naturally threaded into it.
a) lots of systems (turing machines, ...) can implement Lisp.
b) it's not that natural in Mathematica. The natural part comes from its symbolic nature. But if you look at the documentation and read about how they implement lexical closures, it's all vague and not that pretty. The implementation actually needs to rewrite variable names, IIRC.
I wonder why their documentation is so vague? They don't want independent implementations of their language?
That's indeed what Module does, and it is indeed ugly and slow. When we add parse-time macros it'll be trivial to fix this.
For now, many people use Block instead, which does dynamic scoping and is a bit cheaper. I actually really like Block, because it gives you the convenience of a couple of globals that you don't require you to keep passing them along among your backend functions, but they're properly bound to the lifetime of your function (and are re-entrant etc).
The book Paradigms of AI Programming by Peter Norvig shows how to implement these evaluation strategies in efficient Common Lisp.