Previous Entry Share Next Entry
Some notes on TIS-100 programming
I've become enamored with the recently-released Zachtronics game TIS-100, a game very much oriented at low-level programmers.  The conceit is that you've discovered this weird computer from your uncle's estate that comes with a few instructions and a wiped memory where different programs need to be implemented.  However, it's not a straightforward CPU, but instead a grid of micro-CPUs that communicate with each other.  As you develop your programs, you get feedback based on your friend's efforts, often showing you that it's possible to build the same app with fewer instructions or that runs quicker or takes fewer nodes.  At the same time, you're finding corrupted notes from your uncle linking to some sort of conspiracy.

I'm about 1/3rd through with it, but already have hit some very creative challenges.  I like the achievement system, as it pushes you to try alternative ways to build things.

Here's some techniques I wanted to write down:

Saturating math: the registers on the TIS-100 are limited to the range -999 to 999.  Unlike most modern CPUs, if you overflow, it will stay at the maximum or minimun value.  For example, -900 - 200 = -999.  You can use this to identify positive or negative values without using the IF instructions... to make the ACC register 1 when it's current value is positive means you'd write:

ADD 998 # any positive number will now be 999
SUB 998 # positive numbers will now be 1, zero or negative will be less
SUB 999 # zero or negative numbers will be -999, positive numbers will be -998
ADD 999 # transform into 0 or 1

The negative-finding form is similar.

Pushing extra copies: Sometimes you need to compare a value and then use it again, but the original comparison destroyed it's value in your ACC register.  Doing a SAV and SWP takes two instructions, but having the value pushed to you twice means you only need one instruction.  The main pitfall is sometimes this means doing a MOV to NIL because you've got to use up that node's push to unblock it.

Using a node as an extra register: since a node only has one register, ACC.  There's a saved version of it that you access with the SAV and SWP instructions, but there's no way to say something like "ADD SAV".  When you need some storage, push the value to an adjacent node, then have that node push it back one or more times.  A variation on this is a make a smart register where you push a control value that then will cause it to either accept your next push to save into it's value pool or push it's stored value back to you.

Splitting up computation: In order to reduce runtime, look for ways to split up complex tasks across nodes.  Since they all run in parallel, this will often reduce the overall runtime of your program.  It also is a good way to avoid needing to use the backup register to save state.

Set up a back channel: the natural way for you to write nodes means values go in only one direction. However, sometimes it's useful to pause an upstream node for it might also be pushing values to a neighbor. In that case, have the upstream node wait on a push from you and signal it with a value when your done.  This technique seems to be mode useful when you start working with stack nodes, as you don't want to be pushing into a stack from one spot while you're reading from the stack in another.

  • 1
You can create FIFO prepopulated with 0s by linking a few nodes running:

(I am mostly putting this here because I haven't posted on a livejournal in about a decade)

  • 1

Log in