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:

template <class LList, class Cursor, class RList>
struct 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class LHead, class LTail, 
          class Cursor, 
          class RHead, class RTail>
struct tape<
           tl<LHead, LTail>, // Non-Empty Left List
           Cursor,
           tl<RHead, RTail>  // Non-Empty Right List
       > {
    using get = Cursor;

    template <class T>
    using set = tape<
                    tl<LHead, LTail>, 
                    T, 
                    tl<RHead, RTail>>;

    using move_left  = tape<
                           LTail, 
                           LHead, 
                           tl<Cursor, tl<RHead, RTail>>>;
    using move_right = tape<
                           tl<Cursor, tl<LHead, LTail>>, 
                           RHead, 
                           RTail>;
};


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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class Cursor>
struct tape<
           null_t, // Empty Left List
           Cursor, 
           null_t  // Empty Right List
        > {
    using get = Cursor;
    template <class T>
    using set = tape<null_t, T, null_t>;

    using move_left  = tape<
                           null_t,
                           null_t, 
                           tl<Cursor, null_t>>;
    using move_right = tape<
                           tl<Cursor, null_t>, 
                           null_t, 
                           null_t>;
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class Cursor, 
          class RHead, class RTail>
struct tape<
           null_t,          // Empty Left List
           Cursor, 
           tl<RHead, RTail> // Non-Empty Right List
       > {
    using get = Cursor;
    template <class T>
    using set = tape<null_t, T, tl<RHead, RTail>>;

    using move_left  = tape<
                           null_t, 
                           null_t, 
                           tl<Cursor, tl<RHead, RTail>>>;
    using move_right = tape<
                           tl<Cursor, null_t>, 
                           RHead, 
                           RTail>;
};

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

Case 4 is just a mirrored version of case 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class LHead, class LTail, 
          class Cursor>
struct tape<
           tl<LHead, LTail>, // Non-Empty Left List
           Cursor, 
           null_t            // Empty Right List
       > {
    using get = Cursor;
    template <class T>
    using set = tape<
                    tl<LHead, LTail>, 
                    T, 
                    null_t>;

    using move_left  = tape<
                           LTail, 
                           LHead, 
                           tl<Cursor, null_t>>;
    using move_right = tape<
                           tl<Cursor, tl<LHead, LTail>>, 
                           null_t, 
                           null_t>;
};

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:

template <class Tape>
using get_t = typename Tape::get;

template <class Tape, class T>
using set_t = typename Tape::template set<T>;

template <class Tape>
using move_left_t  = typename Tape::move_left;

template <class Tape>
using move_right_t = typename Tape::move_right;

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

template <class T>
using make_t = tape<null_t, T, null_t>;

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

using foo_tape     = tape<null_t, Foo, null_t>;
using shifted_left = typename foo_tape::move_left;
using set_to_bar   = typename shifted_left::set<Bar>;

// Or in just one line:
using foobar_tape = typename tape<null_t, Foo, null_t>::move_left::set<Bar>;

With those helpers, it becomes more readable:

using foo_tape     = make_t<Foo>;
using shifted_left = move_left_t<foo_tape>;
using set_to_bar   = set_t<shifted_left, Bar>;

// Or in just one line:
using foobar_tape = set_t<move_left_t<make_t<Foo>>, Bar>;

Summary

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.