I have been playing with toy languages for the guile VM, and you can do quite a lot of things before the VM limits you much.

With some exceptions though: Java VM does not support tail call optimization, which limits how you implement loop constructs.