Meta-circular evaluation and immutability

Is it possible to write meta-circular evaluator without mutable data structures?

>>1

Yes. The touhouing machine can be modeled without mutation, so you name it, it can be done without mutation. But avoiding mutation can have consequences on efficiency, and the asymptotic bound of the algorithm.