Tardis--Haskell package for sending state backwards and forwards through time(github.com)

58 pointsby tikhonj14 yıl önce9 comments

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

https://github.com/DanBurton/tardis

9 comments

ordinary14 yıl önce

I was 'slightly' sceptical upon seeing the title. The readme makes it clear no fundamental laws of nature are violated: this package sends information forwards through time, but can obviously only receive it from the past.

I admit to feeling at the same time both vindicated in my scepticism, and disappointed at there being no breakthrough in physics.

joshzayin14 yıl önce

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.

EvilTerran14 yıl önce

Well, the past doesn't necessarily have to wait for the value from the future to arrive, thanks to lazy evaluation. But yes, you've got the basic gist of it.

State and Reverse State are both about having a single conceptually-mutable "cell" (although that can, of course, be a complex value like a mapping or whatever), written with "put" and read with "get" -- take a minimal example:

  do put "Past"
     x <- get
     put "Future"
     return x

In State, that would result in "Past"; in Reverse State, it would result in "Future".

The blog posts linked at the bottom of the readme may help make things clearer.

tikhonj14 yıl önce

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.

swordswinger1214 yıl önce

Sigh... This post reminds me so much of Dan Friedman's PL class. BRB, gonna write some Scheme.

sordina14 yıl önce

Reminds me of the talk "Temporally Quaquaversal Virtual Nanomachine Programming In Multiple Topologically Connected Quantum-Relativistic Parallel Timespaces...Made Easy!" surrounding some 'similar' ideas in Perl:

http://blip.tv/oreilly-open-source-convention/oscon-2008-dam...

sordina14 yıl önce

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.

pserwylo14 yıl önce

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-...

jheriko14 yıl önce

This looks like labelling something really mundane and normal as something special. Typcial academic code bs.

Well done for managing to so thoroughly over engineer something so trivial. There is no problem you can solve with this that isn't trivially solvable if you use sensible tools. :)