So there has been work done in compiling probabilistic programs directly into C or C++ [1]. Your intuition is correct that in many of these languages if you wrote an HMM and did MAP inference over it you wouldn't recover the Viterbi algorithm, but there is some code in WebPPL[2] that handles this case as outlined in https://arxiv.org/abs/1206.3555.

[1] https://web.stanford.edu/~ngoodman/papers/aistats2014-shred....

[2] http://docs.webppl.org/en/master/inference/methods.html#enum...