# Creative abuse of Exim
#
# $dotat: doc/web/writing/exim-turing.conf,v 1.9 2004/08/30 18:37:25 fanf2 Exp $
#
# Sendmail's configuration has for a long time been popular with those
# who enjoy obfuscation, and this combined with its generality means
# that twisted people have used it for programming things other than
# email. Well-known examples include Jonathan H N Chin's neat Towers of
# Hanoi <http://pfaff.newton.cam.ac.uk/jhnc/hanoi-cf.html> and, even
# more extreme, Peter van Heusden's Universal Turing Machine
# <http://www.hopf.demon.co.uk/demon/turing.txt>.
#
# Exim is, however, designed to be simple and straight-forward. It
# actually includes several little languages designed for different
# aspects of handling email -- driver configuration, ACL rules, the
# syntax for address lists, the string expansion system, .forward file
# filters -- but none of them is intended to be Turing-equivalent
# (unlike sendmail.cf). The filter language is the one that looks most
# like a conventional programming language, but it has no loops. Even
# so, Exim's power and flexibility means that its address routing is
# in fact a Turing-equivalent language; I will show this by explaining
# how to translate a Turing machine specification into an Exim
# configuration.
#
# This is not intended to be a satirical attack on Exim; it's simply a
# reflection of the fact that you need a high-functionality program to
# deal with all the practical complexities of email. This inevitably
# makes Turing-equivalence hard to avoid. As another example, I think
# that Postfix can be configured in a Turing-equivalent manner using a
# regex canonical map, although it would require an email to loop
# through the system for each step of the computation.
#
# Anyway, we now need a quick review of Turing machine terminology.
#
# A Turing machine operates on an unbounded tape T which is divided into
# squares labelled with integers ... T[-2], T[-1], T[0], T[1], T[2] ...
# Each square contains a mark m which is a member of the alphabet of
# possible marks M = { m0, m1, m2, ... }. One of these marks is the
# blank not-mark. The marks on the tape before the machine is started
# comprise the input to the Turing machine, and it's usually mostly
# blank.
#
# The Turing machine operates on one square at a time, indicated by the
# machine's position i which is an integer. The initial position of the
# machine is zero. The machine also has a state s which is a member of
# the set of possible states S = { s0, s1, s2, ... }. The initial state
# of the machine is s0. One of the states is the final state sF: when
# the machine enters this state it halts.
#
# The final part is the set of rules R which is a relation mapping
# M * S -> M * S * {-1,0,+1}. Given the mark at the machine's current
# position m = T[i] and the machine's state s, there is a rule
# (m, s) -> (m', s', d) giving a mark m' which replaces the previous
# mark at T[i], and a new machine state s', and a delta which is added
# to i to move the machine up one or down one or leave it in the same
# place.
#
# It turns out to be quite simple to express this in an Exim
# configuration, as follows.
#
# The state of the machine is represented by the domain part (after
# the @) of the email address, and the tape is modelled by the local
# part (before the @) of the email address, so the whole address is
# <T@s>. The blank parts of the tape towards minus infinity and plus
# infinity are left off. In order to represent the position of the
# machine we use a second alphabet M' which is isomorphic to M: All
# squares less than i have marks from M' and squares greater or equal
# to i have marks from M. To move up, the mark in square at i is
# replaced with its counterpart from M', and to move down the square
# at i-1 is replaced by its counterpart from M.
#
# The main thing to put in the configuration file is the set of rules.
# Each rule is represented as a redirect router, using the "domains"
# condition to specify the state that the rule applies to and the
# "local_parts" condition to specify the mark. The latter is done with a
# regular expression of the form ^[M']*m (listing all the marks in the
# alternate alphabet instead of M', and the desired mark instead of m).
# The right-hand part of the rule is described by the redirect data. The
# new state is specified in the domain part of the target address, and
# the alteration to the tape (which implies any change of position) is
# described using a ${sg{$local_part}{}{}} expansion item.
#
# Some caveats: Note that if the alphabet contains any special
# characters then the local part will have to be quoted appropriately;
# you may also need to use caseful_local_part on all the routers. Also
# to reduce the size of the configuration, instead of using redirect
# routers you can use a collection of rewrite rules coupled with a
# single router that causes the address to be rewritten repeatedly.
#
# All that is needed after that is to handle starting and stopping the
# Turing machine. You can make the machine part of a live Exim
# configuration by making the RCPT checking ACL allow through all mail
# to *-TM@$primary_hostname (for any *), then an early router can
# strip off the -TM local part suffix and redirect to the machine's
# start state. The router for the machine's final state can fail the
# address, causing a bounce to be sent back containing the result of
# the computation.
#
# Now to put this into practice. This file is an Exim configuration
# for reducing SK combinator expressions, an example I chose because
# SK expressions are Turing-equivalent, simple to implement, and very
# obfuscated. See <http://www.ioccc.org/years.html#1998_fanf> for more
# background information. This example isn't a translation of a Turing
# machine because I took some short-cuts to make implementation
# simpler. This also demonstrates Exim's support for different
# programming styles :-)
#
# There is one serious limitation, though: Exim restricts the number
# of evaluation steps to 100 (twice as many as Sendmail!) which means
# that you don't get very far with
#	exim -C exim-turing.conf -bt '"(s(skk)(skk))(s(skk)(skk))"'


# define some macros to abbreviate the regexes

ARG = [sk]|[(][<sk>]+[)]
FUN = [(]*[sk](ARG)*
NEST = ([(<sk>]*?)
BRAC = [(]NEST[(]([<sk>]*)[)]NEST[)]

admin_groups = wheel

# return the result of the computation in the SMTP conversation
# (this doesn't work at the moment)

acl_smtp_rcpt = require verify = recipient

# now the main program starts

begin routers

loop:
  domains = loop
  driver = redirect
  data = \"$local_part\"@$qualify_domain

clean:
  domains = !loop
  driver = redirect
  data = \\"${tr{$local_part}{<>}{()}}"

halt:
  driver = redirect
  data = :fail: Combinator reduction halted with result $local_part
  allow_fail

begin rewrite

^"[(](FUN)[)](.*)"@		\"$1$3\"@loop
^"(FUN)BRAC(.*)"@		\"$1($3<$4>$5)$6\"@loop
^"([(]*)s(ARG)(ARG)(ARG)(.*)"@	\"$1($2$4)($3$4)$5\"@clean
^"([(]*)k(ARG)(ARG)(.*)"@	\"$1$2$4\"@clean

# that's all, folks!
