This document is an addendum to the official specification for TRDS. The scope of this document is to clarify what TRDS is and the implementation strategy within Rc/Funge-98. This is an official addendum to the TRDS specification and narrows somewhat the scope of what TRDS should be able to do.
Since there are so many questions and problems concerning time travel, this document lays out the specific things that must be implemented to be considered a conformant implementation of TRDS. Cases not described in this document should be considered undefined behavior and is up to individual implementers should they decide to solve some other question or problem concerning time travel.
Primary goal of TRDS:
The main functions of TRDS are as follows:
TARDIS comes from the world of Dr. Who (Yes, I am a big fan!!) and is an acronym for Time And Relative Dimensions In Space.
Each IP has its own TARDIS which is for its use alone. One IP cannot affect the TARDIS of another IP.
There are three modes which TARDIS settings can be set to:
The TARDIS has three settings which need to be set before any jump is made:
|DEFAULT||- When this setting is set to default it uses the IPs current coordinates as the point of jump at the point the jump is made. In essence by using the default mode, no space jump will be performed.|
|ABSOLUTE||- In absolute mode these coordinates are relative to Funge-space home of 0,0[,0]. It does not matter where the IP is located when the jump is made it will go to the specified cell.|
|RELATIVE||- In relative mode these coordinates are relative to where the IP is when it executes the Jump command. Positive coordinates jump right and down, negative coordinates jump up and left.|
|DEFAULT||- When in default mode the delta of the IP will remain unchanged following the jump.|
|ABSOLUTE||- When in absolute mode, the delta of the IP will be set to the delta TARDIS setting following the jump.|
|DEFAULT||- When set to default, the destination time is the tick count at the time the Jump is made, hence no time jump will actually occur. When you are wanting to only do a space jump, this setting set to default will prevent a time jump.|
|ABSOLUTE||- In absolute, the time coordinate is realative to the beginning of time, in other words tick 0.|
|RELATIVE||- In relative mode, the destination time of the jump is relative to what the tick count is at the time the Jump is made. The same restriction applies here, an attempt to jump back in time before time point 0 will leave the IP at time point 0.|
These are the possibilites for which TRDS defines what is to be done. Any situations not listed below are considered to be undefined by TRDS.
Since stopping time does not increment the tick counter, nothing the IP does during this time can be the destination of a time jump.
G executed within stopped time should show the time counter of when the IP had stopped time. For example, if the tick count was 100 when the IP executed S to stop time, a subsequent G will return 100.
If the IP that stopped time performs a time jump, this does NOT restart time! At the destination time, time will still be stopped.
If an IP that stops time jumps into the future, then time will resume until the time that the IP jumped to and then time will again be stopped.
When time continues, it is possible for some IPs to execute in the same tick if they are in the IP list AFTER the IP that stopped time continues it. Continuing time does not automatically cause the time counter to jump to the next tick without giving IPs that have not yet run in this tick a chance to run.
Notes on multiple IP Time Travel:
Time travel with just a single IP is not terribly complicated, even when jumping to the past, but when there are two or more IPs involved in time travel, then jumping to the past becomes considerably more difficult.
If an IP jumps into the past, in addition to all the normal things like IPs stacks, Funge-space, etc being correct, time travelling IPS that arrived BEFORE the IP that currently jumped must also exist! and they should be like they were when the jump destination is reached by the newly jumped IP.
Example: IP#1 jumps backwards at cyle 1000 to tick 100. During this new future IP#2 is born somewhere and makes a jump backwards at tick 1100 to destination tick 150. Since IP#1 jumped back before this, it still exists when IP#2 arrives at tick 150 and now both time traveling IP#1 and time travelling IP#2 exist.
Time travelling IPs that would arrive after the jumped to point NEED NOT RECUR! At the time an IP arrives, the future no longer exists since a new future can now be created by the actions of time travelling IPs!
Example: IP#1 makes a backwards jump at tick 1000 to tick 500. IP#2 is born at some point and jumps backwards at tick 2000 to tick 100. Since this jump is before IP#1's, time travelling IP#1 does not exist, since it did not arrive until tick 500. At tick 500 IP#1 will STILL NOT EXIST. When IP#2 travelled back in time, a new future was created and the old one no longer exists, the changed future may not have allowed IP#1 to jump back. If however the new future does allow IP#1 to jump back again to tick 500, then it will jump back in the manner of the example above.
When travelling back in time, the normal birth of the time travelling IP still occurs! whether at the beginning of the program or a susequent t command. The interpreter needs to keep these two connected such that when the tick is reached where the ip jumped, the new one must cease to exist, it does not jump into the past again! Note: In the case of a changed future, then it IS POSSIBLE for an IP to jump to the past again.
Example: IP#1 is born at tick 100 and at tick 1000 makes a jump back in time to tick 50. When tick 100 is reached again, if the conditions for the original creation of IP#1 still exist, then IP#1 should be born again and there are now two IP#1s which are linked together, one is a time traveller and the other is normal. both of these IPs are now running up until tick 1000. At tick 1000 where the time travelling IP#1 originally jumped backwards, the non time travelling IP is terminated with no jump, the time travelling IP#1 would continue to execute.
An IP that jumped backwards in time and changed the situation enough that would prevent its own birth does NOT eliminate the IP.
Example: IP#1 is born at tick 200. At tick 1000 it makes a jump back to tick 100. Before tick 200, IP#1 changes Funge-Space in a way that prevents IP#1 from being born at tick 200. When tick 200 arrives, IP#1 would not be created again because of the change the time travelling IP#1 made. Time travelling IP#1 continues to execute! Just because it prevented its original birth does not cause the time travelling IP to disappear.
A time travelling IP can jump back in time after another version of itself has jumped to an earlier time and both time travelling versions of the IP will exist!
Example: IP #1 at tick 1000 jumps beck to tick 100. When the time travelling IP#1 reaches tick 1500 it makes a jump back to tick 200. Since it orginally had jumped back to tick 100, there are now two time-travelling IP#1s running at tick 200.
When a time travelling IP jumps back in time where a time travelling copy of itself already exists, the two must keep track of where the jumps were. the time travelling IP#1 would terminate the non-time travelling IP#1 when IP#1 originally jumped. When the second time travelling IP#1 reaches its jump point then the first time travelling IP#1 needs to be eliminated.
Example: IP#1 jumps back at tick 1000 to tick 100 becoming IP#1a. At tick 1000 the non time travelling IP#1 will terminate without another jump back. IP#1a continues to run until it reaches tick 1500 and initiates a jump back to tick 200 becoming IP#1b. At this time IP#1a must also exist in the time and state that it was at tick 200. Both run until tick 1500 which is where IP#1b had jumped and now IP#1a will be terminated and IP#1b continues to run.
Implementation stragegy for Rc/Funge-98
In Rc/Funge-98 all IPs are given a unique uid/serial number combination. No two IPs should ever have the same uid/serial. This does not mean that uids are not repeated. In the case of time travel, an IP must have the uid that it had once before. As such the uid counter is reset to zero and restarted when starting from the beginning of time. The serial number portion of the uid is incremented each time that an IP makes a time jump.
Here are the data structures that are used to support TRDS:
|Jumps||- This holds a table of IP data structures. Each IP that is within this table represents a jump. The entries in this table are complete IPs, and are duplicated back into funge-space when time travel to the past occurs.|
|NumJumps||- Number of IPs in the Jumps table.|
|StopTime||- This variables specifies whether or not time is stopped. when the value of this variable is -1, then time is NOT stopped. Any other value will be the sequence number (NOT the uid) of the IP that stopped time.|
|PrintTime||- This variable is used to suprress output when the interpreter is in recreation mode. Since time before the jump point is not actually running, it should not output anything. This variable will contain the tick count at which point output can resume.|
|TimeJumped||- This variable is used to indicated to the main execution loop that a time jump to the past has been performed. The main loop uses this to prevent execution of any more IPs in the IP chain, since at this point time needs to be restarted from the beginning.|
|serial||- This is an addition to the uid in order to uniquily identify IPs. Each time that an IP makes a time jump its serial number will be incremented.|
|RunTime||- This is used to indicate when an IP should begin running. The IP will only execute if the tick count is greater or equal to RunTime.|
|TSpX||- This holds the Tardis destination space X coordinate.|
|TSpY||- This holds the Tardis destination space Y coordinate.|
|TSpZ||- This holds the Tardis destination space Z coordinate.|
|TvX||- This holds the Tardis destination X delta.|
|TvY||- This holds the Tardis destination Y delta.|
|TvZ||- This holds the Tardis destination Z delta.|
|TTime||- This holds the Tardis destination time coordinate.|
|RTSpX||- This holds the Tardis return space X coordinate.|
|RTSpY||- This holds the Tardis return space Y coordinate.|
|RTSpZ||- This holds the Tardis return space Z coordinate.|
|RTvX||- This holds the Tardis return X delta.|
|RTvY||- This holds the Tardis return Y delta.|
|RTvZ||- This holds the Tardis return Z delta.|
|RTTime||- This holds the Tardis return time coordinate.|
|SpMode||- This holds the Tardis space coordinate mode.|
|VMode||- This holds the Tardis vector mode.|
|TMode||- This holds the Tardis time coordinate mode.|
To implement stop time it is necessary to have a variable that indicates time is stopped and which IP stopped it. In Rc/Funge-98 a single variable exists for this purpose called StopTime. This variable either holds -1 which means that time is not stopped or else it holds the IP number which stopped time. The IP number is not the uid, it is the position of the IP within the table of active IPs. When StopTime is not -1, then the CycleCount no longer increments and the only IP allowed to run is the one in the slot specified by StopTime.
To continue time the variable StopTime is set to -1. Also within the code that handles the @ command a check is made to see if @ is executing on the IP that stopped time, and if so will resume time by setting StopTime = -1.
When any IP makes any jump:
When a jump is made the return coordinates of the Tardis need to be set. This is accomplished by first moving the IP along its delta and then recording this location along with the delta and time that the jump was made. The IP is then moved backward along its delta back to the jump point. The reason that the IP is moved ahead is that when a return jump is used it should not execute the J again but rather the next instruction in the path of the IP as if no jump had ever occured.
Next the space jump mode is checked and if it is set for either Absolute or Relative jump mode, then the IPs location vector will be set to the Tardis destination space coordinates.
Next the delta mode is checked, If the delta mode is enabled on the Tardis then the IPs delta vector will be changed to the value set in the Tardis.
Finally the time mode is checked. If it is set for either Relative or Absolute time then the IP will make a time jump as outlines in the following sections. If the time mode is set for Default, then no time jump will occur.
Time jump to the future:
Time travel to the future is trivial to implement. The IP data structure contains a variable called RunTime. If CycleCount is less than RunTime then the IP does not execute. In essence it remains frozen until CycleCount catches up with it. So if the IP jump to tick 1000, it remains frozen until CycleCount reaches 1000 at which point the IP will continue to run. When jumping to the future, all events from the point of the jump up to the destination run normally within the interpreter, no special action is needed, just freeze the IP until time catches up with it.
Time travel to the past:
Now the fun begins. Rc/Funge-98 uses the method of starting from scratch when an IP jumps to the past and then running up until the arrival time. First the Jump table is checked to see if this jump has already happened. This check is made by comparing the source and destination coordinates along with the uid/serial of the jumping ip. If this jump is found in the jump table then this jump is a duplicate of a prior jump and the ip will be killed in order to prevent a time loop.
If the jump was not found in the table of time travelling IPs then this IP is allowed to time travel. First thing that needs to happen is examine the table of time travelling IPs and remove any IPs that have a jump time that is later than the current jump. The future beyond the jump point of the current IPs jump no longer exists, and any of thse jumps are allowed to happen again, plus No time travellers should appear in funge-space after the current jump unless they occur again through normal processing.
Next the current IP has its RunTime variable set to the tick count of when it should begin running and then is inserted into the jump table as being a time travelling IP.
Next comes the reset of the vm. Funge-space is cleared and the original program is reloaded from disk. The IP chain is cleared of all IPs and then a single new IP is created for uid 0/0. This is the IP that normally starts any Funge program run. At this point the vm is in the state it was when it first started.
Next the Jump table is processed to insert all IPs that remain in the jump table back into the IP chain. Each IP already has its RunTime variable set so now they act just like future jumps, remaining frozen until the tick counter catches up. Note: The IPs in the jump table are duplicated to the IP list, not just copied, this allows the stack and loaded fingerprints to be preserved for additional jumps where these IPs would be placed back into the environment.
The VM PrintTime variable is then set for the time of the current jump. This variable is used to prevent any output from . and , (and hopefully others). While the VM is running from time 0 up til the jump point, this is not really occuring and therefore no output should be generated during this phase.
The TimeJumped flag is then set in order to indicated to the VM main execution loop that a time jump to the past has occured and that the VM has been reset to its starting state. This will prevent the main execution loop from trying to execute any more IPs from the original time. The next tick through the VM will run normally.
Now the VM is simply running from the beginning, when PrintTime is reached then output will again be allowed. Each time traveller wakes up on its own when its RunTime is reached.