Django's Template Language is Turing Complete

This post is about an experiment I've had lying around for nearly two years now. It tries to provide evidence that the Django Template Language (DTL) is Turing complete by implementing a Turing machine simulator in pure DTL. It has the following properties:

It has a single-sided infinite tape.
The alphabet consists of arbitrary characters excect for '@', which terminates the left end of the tape.
It's implemented in 90 lines of code (including the template).

A sample machine which detects binary palindromes can be found on github. It's a single, self-contained python script, that produces the following output:

$ python tm.py 1011101
…
accepting YES: ________

$ python tm.py 111000
…
accepting NO: _1100__

Motivation

In discussions about new features or syntax changes for the DTL the argument that template languages are for designers and therefore should be as simple as possible is often used to prevent changes. This argument is laid down in the design philophies behind the DTL, which lists "Don’t invent a programming language" as a design goal.

However, presentation logic often requires more complex operations than the built-in tags and filters provide, which makes custom utility tags and filters necessary for many templates (e.g. all operators except add are unavailable).

Another DTL design philosophy is titled "Assume designer competence". As a developer who writes his own templates, I often wish this principle would take precedence over "Don’t invent a programming language".

Since the DTL already is a programming language – with artificially crippled syntax to prevent potential foot injury – there's hope for Django to eventually move to a more fully featured template language.

In the meantime, Jinja2 is a perfectly good alternative.

The Turing Machine Template

{% if not current_state %}
  {% with INITIAL_STATE as current_state %}
    {% with INITIAL_HEAD|default:0|add:1 as pos %}
      {% with "@"|add:TAPE as tape %}
        {% with "TURING_MACHINE" as tm_tpl %}
          {% include tm_tpl %}
        {% endwith %}
      {% endwith %}
    {% endwith %}
  {% endwith %}
{% else %}
  {% for state in ACCEPTING_STATES %}
    {% if current_state == state %}
      accepting {{ state }}: {{ tape|slice:"1:" }}
    {% endif %}
  {% endfor %}
  {% with pos|stringformat:'s'|add:':' as tape_slice %}
    {% with tape|slice:tape_slice|first|default:BLANK_SYMBOL as symbol %}
      {% for state, read, next_state, write, move in TRANSITIONS %}
        {% if state == current_state %}
          {% if read == symbol %}
            state: {{ current_state }}, position: {{ pos|add:-1 }},
            tape: {{ tape|slice:"1:" }}, read: {{ symbol }},
            write: {{ write }}, move: {{ move }}, next-state: {{ next_state }};
            {% with pos|add:1|stringformat:'s'|add:':' as tail_slice %}
              {% with pos|stringformat:'s' as head_slice %}
                {% with ":"|add:head_slice as head_slice %}
                  {% with tape|slice:tail_slice as tail %}
                    {% with tape|slice:head_slice as head %}
                      {% with head|add:write|add:tail as tape %}
                        {% with pos|add:move as pos %}
                          {% with next_state as current_state %}
                            {% include tm_tpl %}
                          {% endwith %}
                        {% endwith %}
                      {% endwith %}
                    {% endwith %}
                  {% endwith %}
                {% endwith %}
              {% endwith %}
            {% endwith %}
          {% endif %}
        {% endif %}
      {% endfor %}
    {% endwith %}
  {% endwith %}
{% endif %}