TRDS Implementation in Rc/Funge-98

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:

  1. The ability to stop time.
    This function allows an IP to stop time, hence prevent other IPS from running while the IP that stopped time is capable of continuing to run.
  2. The ability to jump in space.
    This is the simplest function of TRDS. It acts pretty much like a GOTO command. A space jump will move the IP to another location in Funge-Space. When doing a space jump, with or without a time jump, the IP will always execute the jumped to instruction.
  3. The ability to jump in time.
    This is the most complex capability of TRDS. It allows an IP to jump to another tick number before continuing execution. Time jumps may, but are not required to, have a space jump that is executed at the same time as the time jump.

The TARDIS:

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:

  1. Default
    In Default mode, the setting is ignored and the current attributes of the IP are used instead.
  2. Absolute
    In Absolute mode all coordinates are relative to the home of Funge-Space at 0,0[,0] and from the beginning of time 0.
  3. Relative
    In Relative mode all coordinates are relative to the IP at the time the jump is made.

The TARDIS has three settings which need to be set before any jump is made:

  1. Destination coordinates.
    These coordinates are used by space jumps and sets the cell coordinates of where the IP will jump to. If a space jump is made, then the next instruction to be executed will be the instruction that was jumped to. The destination coordinates can be used in all three TARDIS modes:
    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.
  2. Destination delta.
    These coordinates specify what the delta of the IP will be following the Jump. It does not matter if the jump was time or space or even neither, the delta of the IP will be set by these coordinates. This coordinate can be operated in two modes:
    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.
  3. Destination time.
    This setting specifies which clock tick is the destination of the jump. This setting is what allows an IP to jump through time. Any clock tick from 0 up is allowed as a destination time. If the destination time is less than the current tick count, then the jump is made into the past. If the destination time is greater than the tick count, then a jump is made to the future. Jumping into negative time IS allowed, but since nothing exists before time point 0, the destination time of the IP will actually be time point 0. This setting can be used in all 3 modes:
    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.

Supported Functionality:

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.

  1. Stop Time
    When an IP stops time, the tick count should no longer increment. Anything that the IP does while time is stopped is considered to take no time at all. During stopped time no other IPs are executed. If the IP stopped time at tick 100, did 1000 ticks worth of instructions and then continues time, the next actual tick is 101. The G command of TRDS allows an IP to determine what the current tick count actually is. tick counts start from 0, which is where the very first instruction will execute. If an IP is running in stopped time mode and executes the @ instruction to terminate itself, time must then be resumed as if the IP had called C on the same tick as the @. It is not necessary for the IP itself to continue time before terminating, it is a function of the interpreter.

    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.

  2. Continue Time
    When an IP continues time, the tick counter must again run and all other IPS will be capable of executing. IP execution order should remain as if time had never been 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.

  3. Time travel to the future
    This is actually the simplest form of time travel. The IP that travels to the future should not be run during normal processing of the IP table until the tick count reaches the destination time of the future travelling IP. When an IP jumps to the future nothing happens to the tick count or to other IPs, they continue to run normally and the interpreter should continue running normal ticks, the future jumping IP is merely ignored until time catches up with it.
  4. Time travel to the past
    This is the sticky one! When travelling to the past the interpreter must be capable of creating the exact environment of the destination time. This includes all IPs, their stacks, what Funge-space was, any fingerprints loaded on IPS, etc. The destination time needs to appear as if a snapshot was made of the whole virtual machine at that point in time.

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:

Stop Time:

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.

Continuing Time:

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.

Notes: