Great post. Recently I wrote an interpreter for Scheme using Haskell using the guide "Write Yourself a Scheme" [1]. It was great fun, and it seems that it will be fairly straightforward to write a new domain-specific language using Haskell, using the same principles. That said, it was never clear to me how something like that would work in a non-purely-functional language, and so the fact that the OP used Rust is very exciting.
[1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...