Chris Double has a nice post about Screamer, the non-deterministic programming system (which he ported to Corman Lisp).

I'd heard of Screamer but had always thought it to be a very difficult product which would be hard to port. In fact, it was almost trivial. It's all done with macros. Basically it walks the code you write using macros looking for non-deterministic function calls. When these are found it converts that code to continuation-passing-style and uses these continuations to implement backtracking, etc. It's very clever but you don't need to know anything about the implementation to use it.

Screamer seems like a nice example of the ability to extend the lisp language with macros.