# 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 and, even # more extreme, Peter van Heusden's Universal Turing Machine # . # # 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 # . 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 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]|[(][]+[)] FUN = [(]*[sk](ARG)* NEST = ([(]*?) BRAC = [(]NEST[(]([]*)[)]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!