Tardis--Haskell package for sending state backwards and forwards through time

The readme does in fact make that claim: "The Reverse State monad allows you to do the reverse: send information backwards to the past, or receive information from the future."

I'm curious as to what exactly that means, but without further explanation I'm going to assume that the thing running in the "past" just waits for information from the "future". It's possible they mean something else, of course, but that's my first guess.

Obviously it doesn't actually violate the laws of causality. However, it looks like it does.

At a high level, I think this is essentially similar to the "time travel" you can get with continuations[1]. The first blog post[2] linked in the readme should make things clearer.

[1]: http://matt.might.net/articles/programming-with-continuation...

[2]: http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reve...

Essentially, a "stateful value"--that is, a value that could be based on some state coupled with that state--is just a function from the state to the value and the new state. It has the type s → (α, s) where s is the type of the state and α is the type of the value. This is the simplest way to represent state in a purely functional way. To actually use it, you have to supply the initial state and you then get the value and the new state.

When you actually use it, you plug the state in to get the value and the next state. Then you go to the next function you want to run, plug the new state into that and so on. The whole program looks neat thanks to do-notation:

    stateful = do currentValue ← get
                  put (currentValue + 1)
                  return ("x_" ++ currentValue)
 

If the current state is 0, stateful gets 0, increments the state and returns "x_0" wrapped in the new state (1). If you sequence two statefuls one after another, you get "x_0" followed by "x_1".

The trick is that each line is actually a function of the type I mentioned before, and is joined with the next line without running it. So the whole stateful "value" (a string) has type State Int String which is effectively a function Int → (String, Int). Each line of the do-notation is the connected by taking the current state, plugging it into the Int → (α, Int) function and getting the new state and value from that.

The reverse state monad works in a very similar way. However, instead of taking the current state and passing it into the new function, it takes the new function's resulting state and passes it into the current function. This is somewhat convoluted, but it works thanks to laziness and the fact that the state is just composing functions at each point. When you actually run it, it all works out.

In practice this means that your program's state behaves backwards. Given the same stateful value:

    stateful = do currentValue ← get
                  put (currentValue + 1)
                  return ("x_" ++ currentValue)

it would give you "x_1", "x_2"... starting from an initial state of 0. Contrast this with the normal state monad which would give you "x_0", "x_1"... The state flows from the put to the get even though the put follows the get. In a sense, the put sends changes the state backwards through time. This isn't what actually happens in the program, of course, but that's what it looks like. What actually happens is that it builds up a big, composed function using the state and then works properly when you run it because of laziness.

So you don't get actual time travel (we're programmers, not physicists!) but you do get some really clever control flow that basically maps your out-of-order program into something computable.

This particular package just combines both the normal state monad and the reverse state monad into one, letting you make big computations that have state running through in both styles--forwards and backwards.

For those that don't want to wait until the similarities emerge, they begin at ~39 minutes. Obviously the primary motivation of the talk was entertainment, however, I imagine that the Perl implementation of "positronic variables" is actually somewhat equivalent to TardisT IO.

Although, this is just a guess as I don't know if the perl implementation is available anywhere.

Me too. I think it is the same talk as he gave at the Open Source Developers Conference in Melbourne [1]. I must say, I never thought someone could explain a Perl library which runs programs in negative time (they finish before they start) using concepts from quantum physics, to a non-physicist like myself.

[1] http://blip.tv/open-source-developers-conference/temporally-...