Lambda the Ultimate

If you transform your program to a linear form, so each assignment is taken to create a new variable which is only assigned once, you have something similar to what you want - at least in terms of recording each value and its extent. I've been sort of playing with something similar for simulations - quite often you want to record at least a significant subset of the states for replay or visualisation, and being able to schedule an event in the past makes handling collisions easier, but way too busy in my day job to write anything up.

Perhaps take a look at adaptive languages (blelloch/acar/shankar/cooper) that facilitate memoization and then maybe older transparent persistence systems (there might be parts dipping into logging file systems).

I can't recall anything about explicit time intervals that doesn't quickly fall into DB land, logic, or is too domain specific for me (not to say these are bad things!).

Elephant was a John McCarthy's project, perhaps it can inspire you. It was previously discussed on LtU and mentioned in this interview.

From the implementation perspective, this sounds similar to omniscient debuggers.

Ryan Mallon's MS Thesis, The Semantics, Formal Correctness and Implementation of History Variables in an Imperative Programming Language, might be a useful resource for you. In his implementation previous values are indexed by assignment-depth rather than time, but his scheme may be able to be adapted to allow access by time intervals (I haven't studied it in enough depth to know for certain).

Also you might have a look at Jefferson's work in the Time Warp Operating System. Key idea from your perspective is that old variable values are only interesting for as long as they remain reachable by the computation. TWOS offers one strategy for how to integrate the necessary dependency tracking with speculative computation.

Once you get your head around the idea Jefferson is contemplating, then go look at register rename architectures and their associated dataflow controls. A properly done register rename machine implements essentially what Jefferson describes, but without hazard of unbounded rollback, because it has a stable retirement strategy for completed instructions. The difference is that conventional register rename does not contemplate loosely or moderately coupled parallelism, where Jefferson's work does.

My feeling is that Jefferson's work has been under-regarded, and is worth a look.

Talk to Emile van Sebille about Nicles.

Todd Proebsting and Ben Zorn did some work they called Tangible Program Histories, which is similar to what you are describing.

However, I'm wondering if simple streams (in the Scheme/Haskell sense of lazily-evaluated lists) might serve your purposes. Instead of "assigning" the value 7 to variable x, you push 7 onto the list history_of_x. The "current value" of x would then be the head of that list, but you can always get at past values by digging down through the rest of the list.

In a somewhat similar but more specialized vein, you may want to look at digital signal processing, particularly the implementation of FIR and IIR filters. This is a domain where a limited history of certain variables must be maintained, and there are methods for determining just how much history is needed (ie, the filter order). Depending on what sort of data you're processing, you may be able to express your problem as a signal processing system.

I've always imagined that Software Transactional Memory would be relatively easy to extend to support versioned cells. With enough structure-sharing and some favoring of functional programming instead of mutable state, it might even be managed efficiently.

I've often thought it would be a more useful feature at the blurring edges between PL and Operating System - the ability to perform atomic updates to multiple files and automatically version them.