I am not an expert, but I think solutions like this have a potential of hitting an infinite recursion, if evaluating some expression inside the code somehow indirectly invokes the axiom of choice, for example if you construct an object specifically for that purpose.
I don’t think you run into this problem.
My understanding of the axiom of choice, and the axioms in general, is that instead of merely describing how things work, they are describing what things are are talking about (by describing how they work). There are multiple concepts (in the Platonic realm) you could plausibly mean when you use the word “set”. The axiom of choice says “I only mean those models that have the property that for any set of sets, there is a selection that works like this, and the selection itself is included in the model of ‘sets’”. There are models that follow the remaining axioms and have the property, and also models that follow the remaining axioms and don’t have the property.
Yes, there are two places where that shows up in my comment. First, “if math allowed mutable state” is a condition on the concepts one might be referring to, as usually those concepts don’t allow mutable state. (In fact combining sets and mutable state is probably the hardest part, because e.g. what does it mean to take a subset {x \in S | phi(x) } if phi might mutate some state as a side-effect?) Secondly, my “proof” reduces the axiom of choice to excluded middle, and excluded middle is again a feature that you might or might not have in your mathematical universe.
I guess to add, the thing about constructive math (which avoids excluded middle and unrestricted choice) is that it permits models where everything is computational. What I hope I’ve shown is that in some such models, the obstacle to choice really just boils down to excluded middle. (Probably—again it’s really difficult to combine mutable state with other stuff in pure math.)