VM/Interpreter - stack or register based?

Well I want people to use interpreted code which can be adjusted from within the Serial Monitor. I didn't want to limit the use of the vm, but I could dynamically apply different instruction sets for different usages.

[EDIT]: Maybe it's best to implement (most important part of) the basic AVR instructions and complement this (dynamically) with specific instructions depending on usage. Is this something done before and should this have its benefits?