It depends entirely on how much state they need to capture. Ocaml has long had a time travelling debugger (http://caml.inria.fr/pub/docs/manual-ocaml-400/manual030.htm...) which is very useful in the small. Data-centric languages like Bloom (http://www.bloom-lang.net/) can cheaply reconstruct past states using the transaction log. Frameworks like Opis (https://web.archive.org/web/20120304212940/http://perso.elev...) allow not only moving forward and backwards but can exhaustively explore all possible branches using finite state model-checking. The key in each case is to distinguish between essential state and derived state. http://shaffner.us/cs/papers/tarpit.pdf‎ has more to say on that front.