You can easily encode any generative sequence model in e.g. Church (Scheme-based), Anglican (Clojure-based) or PyMC (Python-based). These are Turing-complete, s

You can easily encode any generative sequence model in e.g. Church (Scheme-based), Anglican (Clojure-based) or PyMC (Python-based). These are Turing-complete, so they can model any sampleable (computable) distribution. See http://forestdb.org/ http://forestdb.org/ for some examples. E.g. an infinite HMM. I have no experience with Stan. There was some controversy on whether it is Turing-complete, but I cannot elaborate on that. The obvious disadvantage of using a language that is too expressive for something as simple as an HMM is that you loose the nice performance guarantees given by all specialized algorithms such as Viterbi. Theoretically, they can achieve good efficiency by performing program transformations (e.g. with abstract interpretation). But in practice, we are still a bit far from that. A nice trick is to implement your generative model in something very efficient (e.g. Probabilisitic C or something GPU-based). You can then forget the burden of having to encode your own sampling procedure, but at the same time inference might be tractable.