sounds to me like there is an already existing full language which meets your needs: Prolog.

yes it is a real language... we developed a fully general symbolic agenda-driven Earley parser in Prolog winter quarter :D

Here is a perl-based interpreter (which I haven't used) and here is my favorite prolog interpreter.