Implementing a Turing Tape for Use at Compile Time

Turing Machines consist of a tape with memory cells, a tape reader like cassette drives and a program table. Implementing the tape drive part with an array and a pointer is a trivial thing to do with imperative programming languages. It becomes more interesting when learning purely functional programming, especially in the context of template meta programming in C++. As a preparation for the next article, i will show how to implement a turing tape based on type lists, usable at compile time.

The code in this article depends largely on the code in the article about type lists, and the article about character type list transformations.

The tape is implemented as a data structure containing two type lists and a cursor type. This structure embodies the idea that, when looking at a turing tape, there is a current cell, which is represented by the cursor type. Left and right of the current cell is the rest of the tape, which is represented by those two lists.

Easy enough, this is the template type signature of the turing tape:

Just as described previously, it contains a list representing the left part of the tape, a list representing the right part of the tape, and the cursor is located just between them. In theory, the turing tape is infinitely long. Representing it with lists, it is very easy to make it virtually infinitely long, because it is possible to attach new cells to it on demand, as soon as it seems to end.

The operations which can be applied to a turing tape, are:

In imperative programming, the data structure containing the turing tape state would just be modified in trivial ways. In purely functional programming, we would create a completely new data structure instance, which differs from the old one in so far that it contains the desired modification.

Implementing the tape template class has a simple base case, and three special cases:

The most complicated part of the following code is the pattern matching part of the template type signature.

Case 1: Non-empty Left/Right Lists

Case 2: The tape only consists of the cursor item (Left and right list are empty)

This case is very simple. The get and set functions work just equal to the one before.

When moving the tape left or right, there are no list heads/tails in both directions.

When shifting the tape to the left, the cursor becomes the tip. It is then the only element in the previously empty right list. There are no items coming from the left list, so it is still empty. The cursor is just set to null_t, representing an empty cell.

When this list is later used with specific payload types, this situation needs to be fixed in the sense, that empty cells should be initialized to some default type.

Case 3: The left list is empty, the right one is non-empty

I leave case 3 and 4 mostly uncommented. They are kind of hybrids of case 1 and 2, because they match in cases where one list is empty, and the list on the other side is non-empty. That means that shift left or shift right are actually shifting the respective non-empty list like case 1 does, but then create a new empty item of the other empty list, just like case 2 does.

Case 4: The right list is empty, the left one is non-empty

Case 4 is just a mirrored version of case 3.

Adding Convenient using Clause Helpers

The tape class can already be easily accessed in order to perform all four defined actions on it. However, this would also be followed by the typical clumsy typename keywords.

Therefore we define some using clause helpers:

Another useful helper is make_t, which creates a new, empty tape, which already contains a specific type at its cursor position:

Without those helpers, shifting and setting a newly created tape would look like this:

With those helpers, it becomes more readable:


What we’ve got now is a tape structure, which can be instantiated, shifted around and inbetween its empty cells can be filled with values. A turing machine or any other system for which it would be of use, would wrap around that type and add some more functionality.

When implementing this, being in the role of a novice template meta programmer, i found this to be a nice exercise for pattern matching.