TIS-100

TIS-100

134 ratings
Tesselated Intelligence System Best Practices
By Adam
This guide contains some programming patterns I discovered while programming the TIS-100, covering flow control, memory management, and other basics. Warning: This guide is filled with spoilers!
 
Rate  
Favorite
Favorited
Unfavorite
Introduction
We at Fractured Intelligence Systems offer this document to owners of Tesselated Intelligence System computers, as a replacement for the "Tessellated Intelligence System Best Practices" document that has apparently been removed from all TIS computer packages while in transit through the US Postal Service. Surely it was a simple postal mistake, but as the owners of TIS have been unreachable lately, we have stepped in to fill the void. We are not owned by or affiliated with Tessellated Intelligence Systems (TIS). In this document, we assume that you're familiar with the basic operation of the TIS-100 as described in the official TIS-100 reference manual. If you find this document helpful, please consider purchasing a Fractured Intelligence Systems computer. Our machines are compatible with TIS computers, but better, and with no security clearance required!

(I've only been playing the game a short time, so there may be better practices than these. Also, this should go without saying, but since TIS-100 is a puzzle game this entire document is one big spoiler! If you notice any improvements or errors, please feel free to leave a comment. I may be unable to reply due to a problem with Steam Guard, but I'll read all comments.)
Code Formatting
Each TIS-100 basic execution node (type T21) can store up to 15 instructions. The TIS-100 editor therefore allows you to enter up to 15 lines of code per processor. However, labels and comments are not instructions, so if you want to use all 15 instructions you mustn't "waste" any lines for labels or comments. This means that instead of writing code like the following:
# READ VALUE MOV UP, ACC SAV # READ COUNT MOV UP, ACC # LOOP 'COUNT' TIMES LOOP: JEZ DONE SUB 1 # COUNT = COUNT-1 # SEND VALUE FOR PROCESSING SWP MOV ACC, RIGHT SWP JMP LOOP DONE: # FLUSH THE OUTPUT MOV NIL, RIGHT
you may have to cram everything together, like this:
STRT: MOV UP, ACC SAV MOV UP, ACC LOOP: JEZ DONE SUB 1 SWP MOV ACC, RIGHT SWP JMP LOOP DONE: MOV NIL, RIGHT
This may require very short label names and few or no comments.

In general, you should make your code as easy to understand as possible. But when you need to fit more code in, you may have to compress it. In this guide, code samples will not be compressed even if they require more than 15 lines. As a result, you may need to compress them before entering them into your TIS-100. (The FIS-100 does not have this limitation, allowing you to be as verbose as you like!)
Flow Control
> Comparisons and Branching
The TIS-100 architecture supports four basic comparisons: equal to zero, not equal to zero, less than zero, and greater than zero. All comparisons are done against the accumulator, and these comparisons are used to jump to a new location if the comparison is true. (Here at FIS, we've embraced the TIS-100 instruction set and extended it with less than or equal to zero and greater than or equal to zero comparisons, available in our FIS-101 and later machines!)

For example, if you want to do X when ACC > 0 and do Y otherwise, you can use code like the following.
JGZ DO_X # JUMP IF ACC > 0 # Y (ACC <= 0) JMP DONE # SKIP OVER X DO_X: # X (ACC > 0) DONE:

If you want to do X when ACC >= 0 and do nothing otherwise, you can use code like the following.
JLZ SKIP # JUMP IF ACC < 0 # X (ACC >= 0) SKIP:
Since there's no "jump when the comparison is false" instruction, we use the opposite comparison to get the same effect.

If you want to do X when ACC > 0 and do nothing otherwise, it's a bit more complicated because the opposite of > is <=, but no <= comparison exists in the TIS-100 (unlike the FIS-101). You can use code like the following to emulate it, but it takes two instructions instead of one.
JGZ DO_X # DO X IF ACC > 0 JMP DONE # OTHERWISE, SKIP X DO_X: # X (ACC > 0) DONE:

More complex comparisons can be built on top of these four operations. For example, if you want to perform the comparison ACC > 10, you can do the following.
SUB 10 # ACC = ACC-10 JGZ LABEL # ACC-10 > 0 -> ACC > 10
This, of course, modifies ACC, which you may not want. If you need the original value of ACC you can restore it afterwards using either SAV/SWP or simply ADD 10.

A special case of this is adding or subtracting 1 to implement the less-than-or-equal and greater-than-or-equal comparisons.
ADD 1 # ACC = ACC+1 JGZ LABEL # ACC+1 > 0 -> ACC > -1 -> ACC >= 0

To perform the comparison LEFT > RIGHT, you can do the following.
MOV LEFT, ACC # ACC = LEFT SUB RIGHT # ACC = LEFT-RIGHT JGZ LABEL # ACC > 0 -> LEFT-RIGHT > 0 -> LEFT > RIGHT
In general, you can compare any two non-negative numbers via subtraction. If you need the original values of LEFT and RIGHT in addition to the comparison, you can save them both (see the memory management section for tips on storing multiple values), or simply save RIGHT, which will allow you to restore the original LEFT by adding RIGHT back to LEFT in the same way that ADD 10 could restore the original value of ACC after doing SUB 10 in a previous example.

Note that because the TIS-100 "saturates" the accumulator when arithmetic overflow or underflow occurs (e.g. 950 + 100 = 999), restoring the original values by reversing an ADD or SUB may not work near the extremes of the range. (Remember, the range is -999 to 999.) Although this may be a problem in some domains, no TIS-100 program that we've seen here at FIS uses such large numbers.
> Basic Loops
Most programs require you to use loops, for instance to read and process a zero-terminated sequence of numbers.

'while' loop
A 'while' loop is a loop that checks a condition at the top of the loop and executes the loop body if the condition is true. In C a 'while' loop has this form:
while(condition) { body; }
On a TIS-100, you'd use code like the following:
LOOP: MOV UP, ACC # READ AN ITEM JEZ DONE # STOP IF ZERO # PROCESS ITEM (BODY) JMP LOOP # REPEAT DONE:
If this loop occurred at the end of the program, you could remove the DONE label and jump directly back to the start. This is useful if you need to save a line.

'do/while' loop
A 'do/while' loop checks the condition at the bottom of the loop and therefore always executes the body at least once. In C a 'do/while' loop has this form:
do { body; } while(condition);
On a TIS-100, you'd use code like the following:
LOOP: MOV UP, ACC # PROCESS ITEM (BODY) JNZ LOOP # CONTINUE IF NOT ZERO

'for' loop
A 'for' loop is like a 'while' loop that executes some code before the loop starts and at the end of each iteration. In C a 'for' loop has this form:
for(initialize; condition; update) { body; }
and is roughly equivalent to the following C code:
initialize; while(condition) { body; update; }
For loops are usually used to execute a loop a given number of times. The C loop
for(int i=10; i>0; i--) /* execute body 10 times */ { body; }
can be implemented on a TIS-100 using code like the following.
MOV 10, ACC LOOP: # BODY SUB 1 JNZ LOOP
Note that we use a 'do/while' loop with ACC != 0 rather than a 'while' loop with ACC > 0 (the literal rendering) because it requires less code. Similarly, we count down from 10 rather than counting up from 0 (the normal way 'for' loops are written in C) because counting down to zero is much easier on the TIS-100, given that all comparison instructions compare against zero. If you must count upward to a fixed number X, you can easily use the SUB X, ADD X trick described above in the comparisons section.

Variable-length 'for' loop
Often the number of loop iterations is not known in advance. The following C function:
void processTimes(int value, int count) { while(count-- != 0) process(value); /* similar to for(int i=0; i<count; i++) process(value); */ }
might be implemented on a TIS-100 as follows:
MOV UP, ACC # VALUE SAV MOV UP, ACC # COUNT LOOP: JEZ DONE SUB 1 SWP # SEND VALUE RIGHT FOR PROCESSING MOV ACC, RIGHT SWP JMP LOOP DONE:
This code uses a 'while' loop rather than the shorter 'do/while' loop to handle the possibility that the count equals zero. If the count is known to be greater than zero, you can use a 'do/while' loop instead.
> Switches
Basic Switches
C code often uses 'switches' to quickly choose among alternative code paths. Here's an example.
switch(value) { case 0: case 1: doSomething(); break; case 4: doSomethingElse(); break; default: alarm(); break; }
This is equivalent to the following C code:
if(value == 0 || value == 1) doSomething(); else if(value == 4) doSomethingElse(); else alarm();
The code using 'if' statements is shorter in this case, but when there are many alternatives a switch can be much faster because the machine can often jump directly to the desired branch rather than doing a long sequence of comparisons.

The TIS-100 implements switches using the JRO ("jump relative offset") instruction, although it's fairly limited. (The FIS-102 sports a more flexible JROX instruction.) The above C switch can be implemented on a TIS-100 as follows, assuming the value is non-negative, doSomething() is LEFT, doSomethingElse() is RIGHT, and alarm() is DOWN.
START: MOV UP, ACC # READ VALUE ADD ACC ADD 1 JRO ACC # SWITCH(VALUE*2+1) MOV NIL, LEFT # 0 - doSomething JMP START # break MOV NIL, LEFT # 1 - doSomething JMP START JMP DEFAULT # 2 NOP JMP DEFAULT # 3 NOP MOV NIL, RIGHT # 4 - doSomethingElse JMP START DEFAULT: MOV NIL, DOWN # 2, 3, 5+ - alarm
There are several things to note here. First, we use value*2+1 as the argument to the switch. This is because JRO takes the number of instructions to jump ahead (or back if negative), and we need up to 2 instructions for each switch case. If the most complex case was 3 instructions long, we'd multiply by 3 instead. Then we add 1 because an argument of 0 to JRO makes it jump back to itself, and we need it to always jump forward. Note that NOPs are added to cases 2 and 3 to pad them out to two instructions. Finally, note the handling of switch cases 5 and above. This uses an undocumented feature of JRO: if the argument is too large, it'll jump to the last instruction. Thus, we must ensure that the default case is implemented by the last instruction on the processor. (If we know that the value is from 0-4, then we can inline the default case into the switch and it doesn't need to be the last instruction.)

The switch implementation used above doesn't work well when some cases are much larger than others. If one case uses five instructions and all the others use just one, all cases will still need to be five instructions long, and given the 15-instruction limit of the TIS-100 type T21 processing node, the available space will be quickly consumed. Also, note how in the above code, the instructions for case 0 and case 1 are duplicated. A more efficient (but more limited) implementation is like this:
START: MOV UP, ACC ADD 1 JRO ACC JMP CASE0_1 # 0 JMP CASE0_1 # 1 JMP DEFAULT # 2 JMP DEFAULT # 3 JMP CASE4 # 4 CASE0_1: MOV NIL, LEFT JMP START CASE4: MOV NIL, RIGHT JMP START DEFAULT: MOV NIL, DOWN
This code uses a jump table. The JRO instruction selects the appropriate JMP instruction from the table, and the JMP instruction jumps to the implementation of the case. Note how there's no need to multiply the switch argument (because each case is one instruction long), the code for cases 0 and 1 is not duplicated, and the overall code is shorter. The downside is that this code cannot handle values outside the range 0-4. Whereas the above switch code would redirect all greater values to the default case, greater values here may cause it to jump inside one of the case bodies. Note that you can save a single instruction here by replacing the final case in the jump table (JMP CASE4) with the code for case 4, but for clarity this wasn't done in the example.

Looping with switches
In the Basic Loops section, this example was given. The following C code:
void processTimes(int value, int count) { while(count-- != 0) process(value); }
might be implemented on a TIS-100 as:
MOV UP, ACC # VALUE SAV MOV UP, ACC # COUNT LOOP: JEZ DONE SUB 1 SWP # SEND VALUE RIGHT FOR PROCESSING MOV ACC, RIGHT SWP JMP LOOP DONE:

But a faster implementation, if you know 'count' will be from roughly 0 to 12 (or less), uses a switch. The equivalent C implementation would be (for count from 0 to 7):
void processTimes(int value, int count) { switch(count) { case 7: process(value); case 6: process(value); case 5: process(value); case 4: process(value); case 3: process(value); case 2: process(value); case 1: process(value); } }
This uses the fact that without a 'break' or other jump statement, a switch case in C will "fall through" and begin executing the next case after it. So if the value is 1, it executes a single process() call. If the value is 2, it executes the process() call in case 2 and then "falls through" and executes the process() call in case 1. And so on. This is not a good example of the optimization in C - it's typically used when the work done in each case is very small - but it may be useful sometimes in the TIS-100. Similar TIS-100 code could be (using LEFT as temporary storage):
START: MOV UP, ACC # COUNT ADD 1 NEG MOV ACC, LEFT # SAVE -(COUNT+1) MOV UP, ACC # VALUE JMP SWITCH MOV ACC, RIGHT # 7 MOV ACC, RIGHT # 6 MOV ACC, RIGHT # 5 MOV ACC, RIGHT # 4 MOV ACC, RIGHT # 3 MOV ACC, RIGHT # 2 MOV ACC, RIGHT # 1 JMP START SWITCH: JRO LEFT # JRO -(COUNT+1)
This trick in this example is the use of negative arguments to JRO. Since the value is known to be from 0 to 7, the argument to JRO will be from -1 to -8, respectively. If it's -1 (corresponding to an input of 0), it'll jump back one instruction and execute JMP START. If it's -2 (corresponding to an input of 1), it'll jump back two instructions and execute MOV ACC, RIGHT and then JMP START. If it's -3 (corresponding to an input of 2), it'll jump back three instructions, executing MOV ACC, RIGHT twice and then JMP START. By moving the prologue code into another processor you can handle up to 12 switch cases with this method.
> Functions
In most cases, each function on a TIS-100 will be a separate processor node. Since a processor can be connected to at most four other nodes, and uses at least one node for input, you're usually limited to calling three functions. If the processor uses external memory nodes, that may further reduce the number of functions it can call. It is possible to share functions between nodes, but arranging the nodes within the TIS-100's 4x3 grid may be difficult. (Note that the FIS-120 supports an amazingly flexible 5x4 grid!)

Basic principles
Consider this simple C function:
int add3(int a, int b, int c) { return a + b + c; }
You could implement this on a TIS-100 as follows (assuming it's called from the left):
MOV LEFT, ACC # ACC = A ADD LEFT # + B ADD LEFT # + C MOV ACC, LEFT # RETURN ACC
This function is not particularly useful but it illustrates two basic principles of processors as functions: parameters are passed in the input pipe and return values are passed back on the same pipe.

On the TIS-100 you can just as easily have multiple return values as multiple parameters. Consider this pseudo-C function that returns two values:
int,int swap(int a, int b) { return {b, a}; }
This could be implemented on a TIS-100 (called from the left) as:
MOV LEFT, ACC # READ A MOV LEFT, LEFT # READ AND RETURN B MOV ACC, LEFT # RETURN A

Multi-caller functions
In the previous example, the functions could only be called by the node on the left, since they're not listening to input from any other node. The ANY and LAST pseudo-ports let you call functions from multiple nodes. Consider this C function:
int mul3(int n) { return n*3; }
If you want such a function to be callable from both the left and the right, you can use code like this (assuming DOWN is temporary storage):
MOV ANY, ACC MOV ACC, DOWN # TEMP = ACC ADD ACC # ACC = ACC*2 ADD DOWN # + TEMP == ACC*3 MOV ACC, LAST
If called from the left, LAST will direct the return value back to the left. If called from the right, it will direct it back to the right. Since there's only one parameter, you don't have to worry about race conditions between the left and right processors. If there were multiple input parameters, race conditions could become a problem.

Multiple functions on a processor
To increase the number of functions available, you can pack multiple small functions into a single processor. This is generally done by adding an additional parameter to the function, although you can avoid this if the operation to perform is already obvious from the parameters. For instance, if the add3 and mul3 functions above were combined on a single processor (called from the left), you might use code like the following.
MOV LEFT, ACC # 0:ADD3, 1:MUL3 JNZ MUL3 # ADD3 MOV LEFT, ACC # ACC = A ADD LEFT # + B ADD LEFT # + C JMP RET # MUL3 MUL3: MOV LEFT, ACC MOV ACC, DOWN # TEMP = ACC ADD ACC # ACC = ACC*2 ADD DOWN # + TEMP == ACC*3 RET: MOV ACC, LEFT # RETURN ACC
Because it has multiple parameters, the function can't safely use ANY and LAST (unless you do extra work to prevent race conditions).

Calling functions
Calling a function on the TIS-100 architecture is not the same as calling a function on an inferior, single processor machine. On a single-processor machine, the calling function is suspended while the called function is running. On a TIS-100 machine all processors are running in parallel all the time, and when one processor calls a function on another processor, the two functions continue running in parallel.

Because the IO ports that allow communication between processors pause ("block") the processor while waiting for input to be read or output to be written, this can be exploited to achieve serialized function calling like you would get on a single-processor machine despite the TIS-100's parallel architecture. For example, to call the mul3 function defined above (assuming it's on the right), you'd use code like the following:
MOV ACC, RIGHT # DOWN = MUL3(ACC) MOV RIGHT, DOWN
First you pass the arguments and then you read the return values. To call the add3/mul3 combo function instead you'd use:
MOV 1, RIGHT # SELECT MUL3 MOV ACC, RIGHT # DOWN = MUL3(ACC) MOV RIGHT, DOWN
What's really happening when you call mul3 is something like the following:
# At this point, the processor running MUL3 (RIGHT) is paused waiting for input. MOV ACC, RIGHT # DOWN = MUL3(ACC) # After supplying input, the MUL3 function resumes and begins the calculation. # At this point, we can continue running independently on our own processor. ... other work here ... # When we want to to collect the result from the MUL3 function, we read from it, # causing our processor to pause until MUL3 is finished (if necessary). MOV RIGHT, DOWN
Usually you want to obtain the result of the function immediately after initiating the call, but in some cases you can improve performance or simplify code by doing other work while waiting for the function to finish.

Functions without parameters or return values
If a function has no parameters, you should just give it a dummy parameter and have the caller pass NIL (or anything). If a function has no return value, that is a more interesting case. If you want the function to be able to be called synchronously (where the caller can pause until it completes), then give the function a dummy return value and return NIL (or anything). If the function is intended to run in parallel with the caller without synchronization, you shouldn't return anything. An example where parallelized functions might be useful is a 'void drawRect(int x, int y, int width, int height)' function that runs in parallel with the caller, drawing the rectangle on the screen while the caller performs other work. The drawRect function may itself call a 'drawLine(int x, int y, int width)' function that runs in parallel with the drawRect function. You needn't worry about calling a function a second time while it's still processing, because the attempt to write the parameters for the second call will pause until the function finishes its work and reads the new parameters.

Aggregate functions
Since the TIS-100 is designed for processing numerical sequences, aggregate functions are a frequently useful pattern. Aggregate functions are called repeatedly with values from a sequence, and are then called with a special value that indicates the end of the sequence, upon which they produce the result of the calculation or otherwise complete their processing. A function that returns the sum of a zero-terminated sequence is one example. It's called an arbitrary number of times and, upon seeing a zero, returns the final sum. An example in C (that unlike our TIS-100 equivalent always returns a value) is:
int sumseq(int value) { static int sum = 0; sum += value; int ret = sum; if(value == 0) sum = 0; return ret; }
Equivalent TIS-100 code (that only returns a value at the end of the sequence, that uses RIGHT as temporary storage, and that's called from the left) is:
MOV NIL, RIGHT # SUM = 0 LOOP: MOV LEFT, ACC # VALUE = NEXT JEZ RET # IF(VALUE != 0) ADD RIGHT # SUM += VALUE MOV ACC, RIGHT JMP LOOP RET: # ELSE RETURN SUM MOV RIGHT, LEFT
Memory Management
Many problems are difficult to solve without sufficient memory. Each TIS-100 type T21 processing node has two cells of memory: one general purpose register (ACC) and one backup register (BAK). Unfortunately, having only a single general purpose register is very limiting, so external storage is necessary for many problems. (The FIS type F22 processing node, compatible with all FIS and TIS machines, has two general purpose registers - an amazing 100% increase!) The type T30 stack memory node can be used to store and retrieve up to 15 values in sequential FILO (first in, last out) order, but since these devices are expensive and somewhat hard to find we'll describe methods of managing memory both with and without stack nodes.
> Processor-based Memory, Part 1
Using SAV and SWP
The BAK register on the T21 processor can only be accessed through the SAV instruction (which copies ACC to BAK) and the SWP instruction (which swaps ACC and BAK). Because the BAK register can't be accessed directly, it's not very useful. In general, the BAK register can be used to operate on two numbers simultaneously as long as the numbers don't need to interact. For instance, it can be used to implement the following C function:
void fillImage(int color) { /* fill each line. the TIS-100 visualization module is 18 lines tall */ for(int y=17; y >= 0; y--) fillLine(y, color); }
In this function we must keep track of both the Y coordinate and the color, but since the two don't interact (i.e. we aren't adding them together or something) we can use SAV and SWP to implement the function as follows (assuming it's called from above and fillLine is RIGHT):
START: MOV UP, ACC # COLOR SAV # BAK = COLOR MOV 17, ACC # Y LOOP: MOV ACC, RIGHT # PASS Y SWP # ACC = COLOR, BAK = Y MOV ACC, RIGHT # PASS COLOR SWP # ACC = Y, BAK = COLOR JEZ START # BREAK IF Y = 0 SUB 1 # Y = Y-1 JMP LOOP

Creating a one-cell stack
When two values must interact (e.g. be added together), you cannot store them in ACC and BAK because instructions cannot directly access the BAK register. In that case you must use a separate node for temporary storage. A type T30 stack node would work well, but if you don't have one available you can easily create a one-cell stack from a type T21 processor node. For example, to create a memory cell accessible from the left, use the following code:
MOV LEFT, LEFT
This is roughly equivalent to the program:
MOV LEFT, ACC MOV ACC, LEFT
From the left, you can use the memory cell exactly as you would a one-element stack. You move values in to store them and out to read them.
# SUM ZERO-TERMINATED NUMBER SEQUENCES # INPUT SEQUENCES ABOVE, OUTPUT SUMS BELOW MOV NIL, RIGHT # SUM = 0 LOOP: MOV UP, ACC # READ VALUE JEZ DONE ADD RIGHT # SUM += VALUE MOV ACC, RIGHT JMP LOOP DONE: MOV RIGHT, DOWN # OUTPUT SUM
This one-element stack is a simple case of a more general method of creating memory controllers from processor nodes, which will be explored in further sections below.

Creating a two- or three-cell stack or a two-cell queue
Using SAV and SWP, you can create a memory controller that acts like a stack with two cells of space, but this introduces a limitation of using processors as memory controllers. In general, memory controller code must be matched to the code of the processor that uses it. That is to say, it must be designed with a particular access pattern in mind. The reason is that unlike a stack node, which is capable of both reading and writing on demand, a processor node cannot simultaneously be in a READ state and a WRITE state. You must know ahead of time whether the other node is going to read or write, and issue the matching MOV instruction. So here is a two-cell stack, accessible from the left:
MOV LEFT, ACC # READ 1ST VALUE MOV LEFT, LEFT # READ A 2ND VALUE, AND WRITE IT MOV ACC, LEFT # WRITE 1ST VALUE
This stack assumes that two values will be written and then two values will be read. Unlike a T30 stack node, you cannot write and then read only a single value. It could be used as follows:
MOV UP, RIGHT # STORE A MOV UP, RIGHT # STORE B ... MOV RIGHT, DOWN # READ B MOV RIGHT, DOWN # READ A
Creating a two-cell queue instead of a stack is about as easy. The difference is that a stack returns its values in reverse order, while a queue returns them in the same order.
MOV LEFT, ACC # READ A SAV MOV LEFT, ACC # READ B SWP MOV ACC, LEFT # WRITE A SWP MOV ACC, LEFT # WRITE B
You can also create a three-cell stack with a single processor.
MOV LEFT, ACC # READ A SAV MOV LEFT, ACC # READ B MOV LEFT, LEFT # READ AND WRITE C MOV ACC, LEFT # WRITE B SWP MOV ACC, LEFT # WRITE A
Creating a three-cell queue with a single T21 processor is not possible.

Write-once, read-multiple memory
Sometimes you need a memory cell that you can write to once and then read from multiple times. For example, to find the minimum value in a sequence of numbers you may want to compare a number with the current minimum (stored in memory) and then read the current minimum again if it's still the minimum value seen so far. This requires a write-once, read-twice memory cell, and is an example of how a memory controller must be matched to the access pattern of the code that uses it. The memory controller is easy to write:
MOV LEFT, ACC # READ VALUE MOV ACC, LEFT # WRITE VALUE TWICE MOV ACC, LEFT
The code that uses it might look like this:
# FIND MINIMUMS OF ZERO-TERMINATED SEQUENCES START: MOV 999, RIGHT # MIN = 999 LOOP: MOV UP, ACC # READ VALUE JEZ DONE SAV # SAVE NEW VALUE SUB RIGHT # NEW - MIN JLZ LESS # JUMP IF NEW < MIN # NEW >= MIN, SO KEEP OLD MIN MOV RIGHT, RIGHT # KEEP MIN JMP LOOP LESS: # NEW < MIN, SO REPLACE MIN MOV RIGHT, NIL # DISCARD MIN SWP # RESTORE NEW VALUE MOV ACC, RIGHT # MIN = NEW JMP LOOP DONE: MOV RIGHT, DOWN # OUTPUT MIN MOV RIGHT, NIL
Note the two uses of MOV RIGHT, NIL in the code. These are necessary to maintain the write, read, read pattern of access.

Write-once, read-infinitely memory is also useful sometimes, and is easy to implement.
MOV LEFT, ACC LOOP: MOV ACC, LEFT JMP LOOP

The idea of write-once, read-multiple memory can be generalized for the case where you don't know how many times you'll read it - a write-once, read-N-times model. This can be helpful in implementing the following C function:
void doRepeatedly(int a, int b, int count) { while(count-- != 0) do(a, b); }
Since the function has two values to pass to the child function plus a loop counter, it needs extra storage that can be written once and read multiple times. The memory controller would look this this:
# READ VALUE AND COUNT. WRITE VALUE N TIMES START: MOV LEFT, ACC # VALUE SAV MOV LEFT, ACC # COUNT LOOP: # WRITE VALUE N TIMES JEZ START SWP MOV ACC, LEFT SWP SUB 1 JMP LOOP
and the rest of the function would look like this (assuming the memory is RIGHT and the 'do' function is LEFT):
MOV UP, ACC # A SAV MOV UP, RIGHT # B MOV UP, ACC # COUNT MOV ACC, RIGHT LOOP: JEZ START SWP # ACC = A, BAK = COUNT MOV ACC, LEFT # DO(A, B) MOV RIGHT, LEFT SWP # ACC = COUNT, BAK = A SUB 1 JMP LOOP

General memory controllers
You can create memory controllers with a wide variety of interfaces, not only stacks or queues, as long as you match the access patterns. For example, a memory controller with a write, read, write, read, read access pattern may be useful for some problems, and you can use the techniques described above to create one.
> Processor-based Memory, Part 2
Serving multiple processors
As described in the Functions section, a function with only one input can be safely shared between processors. A one-cell stack like the one described above is a one-input function. Therefore, one processor can serve as memory for several other processors if it's written using ANY and LAST.
MOV ANY, LAST
Several processors can use this node to store a single memory item. Each processor can store a different value and it will work fine without any race conditions. The write-once, read-twice memory cell described above can also be shared, since it only has a single input. But two-cell stacks are effectively two-input functions and cannot be safely shared unless you do work to prevent race conditions.

Creating a six-cell stack or a four-cell queue
As shown above, you can create a three-cell stack with a single processor node. By combining two processor nodes, you can create a four-, five-, or six-cell stack, or a three- or four-cell queue. Assuming you have a three-cell stack to the right, you can create a six-cell stack quite easily:
MOV LEFT, RIGHT # READ A MOV LEFT, RIGHT # READ B MOV LEFT, RIGHT # READ C MOV LEFT, ACC # READ D SAV MOV LEFT, ACC # READ E MOV LEFT, LEFT # READ AND WRITE F MOV ACC, LEFT # WRITE E SWP MOV ACC, LEFT # WRITE D MOV RIGHT, LEFT # WRITE C MOV RIGHT, LEFT # WRITE B MOV RIGHT, LEFT # WRITE A
You can chain more nodes together to create even larger stacks and queues.

Creating a variable-length queue or stack
It's possible to connect processors together to create stacks and queues that have a variable length rather than a fixed length, but they are less efficient. One possible technique follows. First, imagine four nodes connected together from left to right. The first three have this code:
START: MOV ANY, ACC JEZ RETURN SWP JEZ START SWP MOV ACC, RIGHT JMP START RETURN: SWP JEZ RTEST MOV NIL, RIGHT RLOOP: MOV ACC, LAST MOV RIGHT, ACC RTEST: JNZ RLOOP MOV NIL, LAST SAV
and the last one has this code:
START: MOV ANY, ACC JEZ RETURN SWP JEZ START SWP MOV ACC, RIGHT JMP START RETURN: SWP MOV ACC, LAST JEZ START MOV NIL, LAST MOV NIL, ACC SAV
The effect is to create a variable-length queue that can hold up to four non-zero numbers. (If you want more than four, add more processors to the chain.) The queue can be used like this (where the first node in the queue is UP):
# ADD 3 ITEMS TO QUEUE MOV 1, UP MOV 2, UP MOV 3, UP # READ THEM BACK MOV 0, UP # SEND READ SIGNAL READ: MOV UP, ACC JEZ START # STOP IF WE SEE A ZERO # PROCESS ITEM HERE JMP READ # NOW WE CAN ADD NEW ITEMS IF WE WANT
The MOV NIL, LAST line can be removed from the first node in the queue chain if you don't want it to add a zero at the end of the items. However, you will have to keep track of the number of items in the queue. Similar code can be used to create a variable-length stack. It's possible to change the code to allow you to remove just a single item rather than all items at once. This allows you to add two items, remove one, and add another. You would simply change it to respond with only a single item upon receiving the read signal (0). This also gives you enough space to change the read signal from zero to another number (such as -1), allowing you to store zeros in the queue. The problems with this approach are the large number of nodes used, the inability to store all possible values, and the fact that the queue or stack doesn't block in the same way that a type T30 stack node does.
> Stack-based Memory
If you have access to some of the hard-to-find type T30 stack nodes - we at FIS will manage to duplicate the technology soon - you can greatly expand your storage capabilities. A type T30 stack node can store up to 15 values. Although its use is generally quite obvious, we will present a few tips here.

Easy variable-length stacks
If you want to store a variable number of items in a stack, you normally have to keep track of the number of items so that you can read the correct number of items later. Given the small number of registers on the T21 processor, this can be troublesome. One idea is to store zero or -1 on the stack before the data, and then you can simply read until you find a number equal to or less than zero. For example (where the zero-terminated data stream is UP and the stack is RIGHT):
MOV NIL, RIGHT # ZERO MARKS STACK BOTTOM FILL: # FILL THE STACK MOV UP, ACC JEZ EMPTY MOV ACC, RIGHT JMP FILL EMPTY: # EMPTY THE STACK MOV RIGHT, ACC JEZ DONE # PROCESS ITEM JMP EMPTY DONE:

Indexed memory using two stacks
If you manage to get your hands on two T30 stack nodes, you can build indexed memory holding up to 15 items. If you have a stack node UP containing some items and an empty stack node DOWN, you can look up an item by index with code similar to the following:
START: # LEFT IS THE NUMBER OF ITEMS IN UP, MINUS ONE, FOR ZERO-BASED INDEXING # RIGHT SENDS US THE INDEX AND RECEIVES THE VALUE MOV LEFT, ACC # ACC = COUNT-1 SUB RIGHT # SUBTRACT INDEX DIG: # DIG DOWN TO FIND THE ITEM JEZ FOUND MOV UP, DOWN SUB 1 JMP DIG FOUND: MOV UP, ACC # GET THE VALUE MOV ACC, RIGHT # RETURN IT MOV ACC, UP # PUT IT BACK MOV LEFT, ACC # ACC = COUNT-1 SUB RIGHT # SUBTRACT INDEX BURY: # PUT EVERYTHING BACK JEZ START MOV DOWN, UP SUB 1 JMP BURY
As described, RIGHT sends the index and receives the value. To make it work with a sequence of indexes, you might use code like the following in RIGHT, which reads indexes from UP and writes the looked-up values DOWN.
MOV UP, ACC # GET INDEX MOV ACC, LEFT # SEND INDEX MOV LEFT, DOWN # RETRIEVE VALUE MOV ACC, LEFT # SEND INDEX AGAIN
Parallelizing Code
This section contains a couple tips on parallelizing operations. Although the TIS-100 is a parallel computing system, parallelizing complex operations can be difficult due to the small 4x3 node grid. It may be difficult to fit a single implementation into the system, let alone two copies of it. Because of this, we've decided not to focus extensively on this rarely-used optimization. Nonetheless, here are a few tips. (We'd like to remind you that the FIS-120 supports a massive 5x4 grid!)

The basic idea in parallel processing is to split the input stream into multiple streams, process each one independently, and then combine the results at the end. On a TIS-100, you usually need to ensure that data takes the same amount of time to travel down each path so that they come out the other side in the same order that they went in. If the paths have different timings, items may exit in the wrong order. (For example, if the first input goes down path A and the second input goes down path B, but B is faster, the first output may come from B rather than A, causing the output stream to not correlate with the input stream.) You can work around this by adding delays to even up the path timings, or by ensuring that the first stream is sent down the faster path and the second stream down the slower path.

Although you'll need to duplicate the main processing in each path, you don't need to duplicate everything. One-cell memory and one-input helper functions can be safely shared between the paths as described in the Processor-based Memory and Functions sections respectively. Here is a simple example of parallel processing.

# SPLIT INPUT (UP) BETWEEN RIGHT AND DOWN MOV UP, RIGHT MOV UP, DOWN
MOV LEFT, ACC # READ INPUT # PROCESS ITEM HERE MOV ACC, DOWN # WRITE OUTPUT
MOV UP, ACC # READ INPUT # PROCESS ITEM HERE MOV ACC, RIGHT # WRITE OUTPUT
# MERGE OUTPUTS TOGETHER MOV ANY, DOWN
Closing
We hope you enjoyed this introduction to TIS (and FIS!) programming fundamentals. Please contact us for a mail-order catalog containing our full line of Fractured Intelligence Systems computing products, or for any other reason, at the following address:

FIS
P.O. Box 1337
Shaftsberg, MI 48882
USA

Or, call us toll-free (within the continental United States) at 1-800-FIS-4YOU.
< >
6 Comments
FunQie Apr 20 @ 2:56am 
Wow bravo stuff! Is this file hidden in the game & will be revealed with the game progress, or is it provided by a third party or a summary from you or other player?
Trying hard to hold it back before I finish all the fragment coding
Hawk777 Jun 9, 2016 @ 11:59pm 
One very easy way to handle race conditions when a “function” takes multiple parameters and can be accesed from multiple sides is to observe that the LAST port can be read from, not only written to! Just read the first parameter from ANY and the rest of the parameters from LAST, also writing the return value to LAST. Now you have built a node that can receive packets from any side, but always receives a whole packet at a time from a single side.
finno61 Dec 22, 2015 @ 1:40am 
Brilliant guide. Thank you!
Norgus Dec 2, 2015 @ 1:32am 
I took it upon myself to make a rough-and-ready PDF version: https://dl.dropboxusercontent.com/u/844898/TIS%20Best%20Practices.pdf

anyone more proficient at formatting can have the source HTML here:
https://dl.dropboxusercontent.com/u/844898/TIS100-bestpractices.html
Norgus Dec 1, 2015 @ 1:47pm 
Nice, do you think you could provide a PDF so I can print out a copy to keep with my TIS manual?
Mr.Yeah Nov 29, 2015 @ 11:14am 
As a former TIS user, I'm very interested in your products because I can see how they can lift up some of TIS's limits.
But I live in Germany after my promotion. Is it possible to acquire FIS products in Europe?