It's possible, but typically what instead happens is that people sacrifice Turing Completeness in the value language. It turns out that this isn't so painful (strong types help a lot) and then you have guaranteed termination all around!