The DTC Programming Language

You know, DTC, as in "DooMeeR Turing-Complete"...

No, you don't know? Okay, let's make a crash course just for you, then.

Introduction

Programming languages can be classified in three categories. Imperative languages, such as C, Java, or Pascal; functionnal languages, such as SML, Caml, or Scala; and... the others. In this last category, languages such as logic programming languages (Prolog) can be found. Or... esoteric languages. Esoteric, as in "I want to create a programming language based on monkeys". Or as in "Let's try to make a language with only two instructions".

DTC falls into this last category. It's main purpose is to be esoteric. It could have been a language based on monkeys with only two instructions; but it isn't (interesting idea though).

In a way, it's worse.

Let's see a basic program in DTC.

S......0R.....+...
                 .
blablabla    .....
             . Hello
I like chips +
   ...........
   .
   +++++...E
This program takes one argument, adds 7 to it, show it and terminate.

Let's see another, less trivial one.

S....*0-W0?.1X  S
 ^ .     .     ...
 ... !   .     ^ .
     .   .     ... ... /.
     .   ....!     v .  .
     .         .2.>-..? .
S1W2 .         1      ! .
     .         .        .
     .         ...>+.. W1
     .             ^ .  .
     .             ...  .
     .                  .
     .              /   .
     ....................
Warning: actually, this program is from an old version and won't work anymore. Please come back soon with a new version.

As you may have guessed (well done), this program takes two inputs, and exits with the product of these two inputs.

But let's start from the beginning.

Download the interpreter

A Windows binary should be available when the language is less subject to changes. But it won't be very soon, as it requires some modifications (Windows is not as "command-line-friendly" as Linux).

Using the interpreter

The interpreter reads its standard input until the "end of file" character. This input should be a program. Then, the interpreter prints the program and simulate its execution.

If you want to execute a DTC program which is stored in a file, for instance "test.dtc", you can use a pipe:

cat test.dtc | dtc
The interpreter takes some arguments from the command line.

cat test.dtc | dtc 5 2 72 debug
This executes "test.dtc" with the inputs 5, 2, 72 in debug mode. 5 is the first input (input 0), 2 is the second (input 1) and 72 is the third (input 2). You can use up to 9 inputs.

You can use the "debug" argument, after the inputs. It means that the execution will go much more slowly, so it is easier for you to see what's going on. You should use this option at the beginning.

A two-dimensional syntax

A DTC source code is actually a two-dimensional array. Each line of the source file is a line of the array. Each character of a line is a cell of the array. Conversely, each cell of the array is coded as a character in the source file.

This means that there is no such thing as syntax. A DTC program cannot (or at least shouldn't) be seen as a tree. Indeed, each cell is linked to its four neighbours (3 for the cells in the borders, 2 for the cells in the corner, as in a Go game - actually, it could be interesting to make Go Turing-complete; let's leave that as an exercise for the reader).

Let's study a very easy example.

...............
   .
   .....
       .
       .
 .     .
 .     ......
 .          .
 ............
This is a DTC program. It doesn't do anything, beside illustrate my point. It is a two-dimensional array, and each cell contains either a dot "." or a space " ". Conveniently, lines that are shorter than the others are automatically completed with additional spaces.

Now, let's see what we can do with a two-dimensional array.

Tokens

A token is a, well, token, that is dropped into our array, and that moves in the array to calculate things. Tokens contain an integer value. The value can be anything, including a negative number. In the beginning, tokens are dropped in each cells that contain a "S" character (as in "Start"), carrying the value 0.

Let's try to add some "S" in our example.

...............
   .S
   .....   S
       .
       S
 S     .
 .     ......
 .          .
 ............
Now, let's start our program. A cell which is occupied by a token is denoted by "@".

...............
   .@
   .....   @
       .
       @
 @     .
 .     ......
 .          .
 ............
Now, let's study how tokens can move. It's actually pretty simple: they follow the dots. Let's execute our program one step further.

....@..........
   @S
   .@...   S
       @
       S
 S     @
 @     ......
 .          .
 ............
Let's look at the bottom-left token. It has followed the dots and thus have moved one cell downward. The token of the center had two directions to move to: it has duplicated itself to follow these two directions. The token of the right had nowhere to go and disappeared. The top-left token had three directions available and thus has made 2 copies of himself, and followed the dots.

Let's execute one more step.

...@.@.........
   .S
   @.@.@   S
       .
       S
 S     .
 .     @.....
 @          .
 ............
The bottom-left token continued on his way, and so did the two of the center. In the top-left corner, tokens had many directions available, and thus they are some tokens that overlap each other. It's not an issue, but it's a little tricky to follow; you might want to avoid these kind of situations in the beginning.

There is another way to understand tokens. Tokens are not only particles, but also waves (quantum theory is everywhere, even in DTC). What's actually going on is that each step, tokens get copied in every direction. And the original token disappears.

            @
@   ---->  @ @
            @
But if a token comes from the left, it actually won't be copied in the left direction. Same for top, bottom and right. Thus, tokens only move forward. If it comes from the left:

            @
@   ---->    @
            @
Last but not least, tokens that appear in an empty cell (a space " ") just disappear. Thus, tokens can only live on cells that are not empty. If it comes from the left:

Step 1                          Step 2
                  @
..@..   ---->   ...@.   ---->   ...@.
                  @
Now you see why tokens follow dots, and why they get duplicated at crossroads. And you also see the point of the "two-dimensional syntax".

Basic command: Exit (E)

Actually, tokens can go on other cells than dots. We have already seen the cell "S", which is the same as a dot once the program is running. Let's see how to terminate a program using the cell "E" (as in "Exit").

S.............E
In this example, a token is spawned at the cell "S", follow the dots until the cell "E", and then the program exits, showing the value of the token (which can be seen as a return value). Because tokens have a default value of 0 when they spawn, this program will always exit with the value 0.

You can have several exits in a program (from none to a lot). The first token to reach an exit terminates the program.

S.............E
  .
  ............E
Here, the token is duplicated but because the lower path is longer than the upper one, the lower exit won't be used.

Basic command: Inc (+) and Dec (-)

Are you bored of tokens carrying a value of 0? Do you want to actually calculate something?

S....+++..+....++...E
In this example, the token goes through 6 cells with the character "+". This command increments the value of the token. Thus, the token has the value 6 when it reaches the exit.

To decrement a token, just use "-" instead of "+".

S...-+++-+...
            +
     +++++++-
     .
     ----...E
Here, the program terminates with the value 5.

Concurrency is parallelism

In most languages, it's hard to execute two instructions at the same time. In parallel.

In DTC, it's trivial. Let's take a program where a token starts from the left and goes to the right.

S...............
Now let's make a program which does the same thing, but twice.

S...............

S...............
I just copied the original program, and now I have two copies of it running at the same time, in parallel (literally)!

Note: in DTC, parallelism is synchronous. Each step, each token moves one cell further.

Loops

We can already use high-level programming features, such as loop. "for" loops, "while" loops, and so on, are all available for you in DTC.

So what does a loop look like?

.........
.       .
.       .
.........
This is a basic loop. Pretty visual, isn't it? A token will go on, and on if it is trapped in this loop.

..........
.        .
. .....  .
. .   .  .
..........
Here are two loops, a big one, and a little one in the big one. This is a loop nest!

To make a loop, just make a loop. Not too hard to remember.

In pratice, it's not that easy though. Here, tokens get duplicated when they enter the loop, for instance. And we need some kind of exit condition.

S...>.......
     ^     .
     .     .
     .......
In this example, one token is spawned at the "S" cell and then enters the loop. Once it is in the loop, it will stay there and follow it clockwise until the end of time (i.e. when the user gets bored and hits Ctrl+C).

We see two new commands here: ">" and "^". ">" means that a token can only go in the cell if it comes from the left. "^" means that a token can only go in the cell if it comes from the bottom. In other words, ">" is the same as a dot "." if the token comes from the left, and is the same as a space " " if the token comes from any other direction. You can also use "<" (allows tokens coming from the right) and "v" (allows tokens coming from the top).

These commands allow us to control the direction of the tokens in a path, a loop, and to prevent a token from duplicating when it reaches a crossroads.

Now, let's try to add an exit condition.

S...>.......?..
     ^     .
     .     .
     .......
The cell "?" only allows tokens of value 0. It means that a token can only go through it if its value is null. Thus, a token can exit the loop only if its value is 0. You can also use "!" instead of "?". "!" only allows tokens which value is not 0.

After a token of value 0 goes through the cell "?", the loop is not over though. Indeed, the token is duplicated at the crossroads; one copy goes through the cell "?", and the other one continues the loop. If you want to "kill" this token, you can for exemple add a cell "!" this way:

S...>.......?..
     ^     !
     .     .
     .......
Note that this program is basically equivalent to:

S...>..........?..
     ^     .
     .     .
     ...!...
You don't have to put the "?" and the "!" together near the crossroads. It's just a matter of taste.

Now, maybe you'd like the loop to actually do something. Consider this program:

S...+++++...>.......?....E
             ^     !
             ...-...
Here, the token enters the loop with the value 5. Its value is then decremented in the loop down to 0. The token is then able to exit the loop and terminate the program.

Inputs and Registers (0..9), Reading (R) and Writing (W)

We've already seen that the first token to reach an exit determines the output of the program. Now, we'll see how to read the arguments of the program. It will allow you to build programs that depends on an unknown input.

S.....0....R...........X
In this program, a token is spawned to the left. It goes to the right and passes through a cell containing "0". This means that the token is now linked to the register 0, which contains, by default, the content of the first argument of the program. The token continues to the right and meets the "R" character. It means "Read". The token will set its value to the content of the register it is linked to, i.e. 0. Then the token continues until it reaches the exit.

To sum up, this program just return its first argument.

Instead of "0", you can use "1", "2", ... "9" if you want to link the token to another input.

And instead of "R", you can use "W" ("Write") to write the value of the token into the register it is linked to.

Pass Once (*) and Block Once (#)

"*" is a command that allow one token to go through, but only once. In other words, it acts like a dot "." until a token reaches it. It then changes into a space " ".

It allows you to close a path.

S.......*.........
    .       .    .
    .       ......
    S
In this example, we're spawning two tokens, but only one will reach the loop to the right. Indeed, the first to read the star "*" will close the path and the other token will just disappear.

In a dual fashion, you can use "#" to create a wall that will kill the first token that will reach it. It will act as a space " " until a token reaches it. Both the token and the wall are then destroyed, the wall being replaced by a dot ".".

If we replace the star "*" by a wall "#" in our example, it is now the second token that will be able to reach the loop.

S.......#.........
    .       .    .
    .       ......
    S

Open (O) and Close (C)

Star "*" and sharp "#" are handy to open or to close paths, but it works only once. And sometimes you want to open or close a path from a distance. You can use "O" (Open) and "C" (Close).

S>..... .....E
  ^ .
  ...  O
       .
........
.
.......S
In this example, the token from the bottom will open a path for the token to the top. This token will loop forever, sending a copy of itself towards the exit from time to time. But these copies won't be able to go through before the token from the bottom reaches the "O", which creates a star "*" two cells ahead.

Because it is a star "*" which is created, and not a dot ".", the passage will be open for only one token. If you want to keep the passage open, you can create a loop that will send tokens to the "O" forever:

S>..... .........................................E
  ^ .
  ...  O
       .
........ ...
.        . v
............<S
With this loop, every 8 steps, the path will be reopened.

You can use "C" to create a wall "#" instead of a star "*". It can be used to kill a token which is in a loop, for instance. Indeed, tokens in a loop tend to stay there forever.

S>... C.....................................S
  ^ .
  ...
In this example, a token loops until a wall is created from the right.

Comments

Everything that is not a command is a comment. And actually, if a command is not reachable by any token, it can be seen as a comment too.

S.... This is an example
    . of a program that
 ...0 reads its first input
 R    and then exits with
 ...E that input.
You can do funny things too.

Start
00000
  .
  .
  .
.....
Read.
Exit.

Example 1: the addition

We have seen every command of the DTC language. It's time to code some concrete program. Let's start with a program which reads its first input i and exit with the value 2*i.

     -..?...
     v .   O
     ...
     ^  +.. ........E
     .  v .
S..0R.  ...
     .  ^
     .  .
     ....
How does it work? First, a token spawns, read the input, and duplicates itself. Each copy reaches a loop.

The first loop, to the top, decrements its token until its value is 0. Then the token can pass through the "?" and open a path for the token in the second loop, in the middle. This second loop increments the value of the token. This means that each time the top loop decrements its token, the middle loop increments its token. And the token from the middle is only able to go to the exit "E" when the top loop is done.

The lower U-shaped path is only here to be sure the middle loop is a little laggy, because it takes time to open the path to the exit once the token in the top loop has reached the value 0.

As an exercise, try to modify this program so that it takes 2 arguments and returns the sum of these arguments.

Coming soon