For the record, exactly such a library already exists: http://common-lisp.net/~frideau/lil-ilc2012/lil-ilc2012.html

Although the specific problem of state-with-backtracking would be more idiomatically solved with dynamic binding.