|Perl: the Markov chain saw|
Erm. The art of language design hasn't been around for 25+ years without having come up with solutions to this kind of thing. I don't want to sound negative but did you do any research into language design before embarking on this project?
I completely agree with the concept of Doing for Oneself before simply grabbing other peoples solutions when doing your own projects, however usually at the point where you start needing to ask for help, it is usually best to go read up on general industry practice first.
In this case, the very first thing you should have is a grammar based parser. As mentioned above, grammars are extremely effective at solving this particular type of problem. Indeed perl5 has a module called Parse::RecDecent or something which contains some excellent documentation on how to develop a proper grammar using it, and it plugs right into perl beautifully.
The alternative course of action is, of course, to simply translate the basic language into valid perl and make perl do the hard work. I'm not sure why you chose not to follow this path but I assume you have your reasons.
Anyway, my recommendation would be to consider re-writing the interpreter using RecDecent. Once the initial learning curve is over you should find it almost trivial to implement the language. I understand that you said "Don't worry about the structure of *my* program" but the essence of a good solution is understanding where the problem lies, and it lies in your program structure :)