I suddenly decided to continue my earlier mod_rewrite experiments, BF+Thue in mod_rewrite and my first excursion in mod_rewrite. That code all worked in theory (and for very small examples), but not in practice: Apache runs out of memory.

The Problem

The basic problem is that for each request, Apache will never return any memory to the system – Apache expects trivial things such as interpreting turing-complete languages to complete quickly and without using more than a smidgeon of memory.

To get around this, I decided to change the “run-time system” to make a redirect for each step, i.e. sending an error back to the user-agent and tell it to make a completely new request to a different URL instead of making mod_rewrite loop on the Apache side until it’s done. Apache allocates the memory for each of these requests separately, and its memory use stays bounded (to the size of the program’s state anyway).

Implementing this mostly this meant simply replacing the [N] flag (which means jumping to the start of the list of rewrite rules but continue rewriting) with the [R] flag that send a redirect to the client. But of course a few other minor shenanigans were lurking – primarily around the “bootstrapping” step.

The original RTS relied on Apache always having a slash at the start of the URI to bootstrap the program, and relied on Apache not complaining if you removed the slash internally while doing the rewriting. With the new redirecting approach, we will need to continue processing from a URI that has a slash (since it’s a completely new request from the client) without bootstrapping that URL again. As described in the comments below, we now use a ‘q’ to tell a bootstrapped program from an unstarted program instead of checking whether the slash was removed or not.

While I was doing these changes I ended up I made the compiler output the RTS with the program instead of requiring separate program and RTS config files.

Thue mod_rewrite Compiler v2.0

Without further ado, here is the updated Thue to mod_rewrite compiler in its entirety, now including all the RTS it needs! (Again, syntax highlighting is set to Perl although the displayed code is a sed program.)

# Bootstrapping part: output the RTS prologue
1 {
i\
# This file should be included in an Apache2 config file for a VirtualHost. \
\
# Enable rewriting\
RewriteEngine on\
 
# Hack to make actual files available if you know their names\
i\
RewriteCond /var/www/rewrite%{REQUEST_FILENAME} -f\
RewriteRule ^.*$ - [L]
 
# This should only run on the first inputed string to add the interpreter.
# After each redirect, the client makes a new request and we return to the
# first rule, so this must be safe and idempotent.
# An initial q indicates whether we have boostrapped the program yet, the
# second q is a separator between the output and the current program state.
# We also add a ^ just for fun.
i\
RewriteRule ^/([^q].*)$ qq^$1
# Remove any leading slash to simplify the rest of our processing
i\
RewriteRule ^/(.*)$ $1
 
# Add an 'r' to distinguish unchanged strings. This would be the termination
# condition for our rewrite system - if the 'r' is still left after running the
# chain of rewrites, we're done and stop looping.
# This rule is probably completely unneccessary since we'll always redirect
# when rewriting, which should already prevent us from reaching the
# end-of-program rule before we're done.
i\
RewriteRule ^(q.*)q(.*)$ $1qr$2
}
 
# Strip comments
s/^#.*$//
# Rewrite question marks since they interfere with mod_rewrite by making the
# productions look like requests with query strings, which apache then splits.
s/\?/Q/g
# .*+(){}^$<>[\\ |]\|\]\)/\\\.*+(){}^$<
s/\([.*+(){}^$<>[\\ |]\|\]\)/\\\1/g
# Skip empty lines
/^$/ d
# This is where we're actually doing something worthwhile:
s/^\(.\+\)::=~\(.*\)$/RewriteRule ^q(.*)qr?(.*)\1(.*)$ q$1\2q$2$3 [R,L]/
s/^\(.\+\)::=\(.*\)$/RewriteRule ^q(.*)qr?(.*)\1(.*)$ q$1q$2\2$3 [R,L]/
# End-of-program marker, we want to ignore everything after this line
/^::=$/ { s/::=//; b end }
 
# Restart processing and input next program line
b
 
# Output the RTS epilogue after the last line of program text
:end
# If the string has changed, we are not yet done. Loop to the beginning and
# remove the changed-marker. This doesn't change the string at all ('-' is a
# special substitution string that passes along the original string), just has
# the [N] flag to trigger apache to restart rewriting.
# This rule is probably completely unneccessary since we'll always redirect
# when rewriting.
a\
RewriteRule ^(q.*q[^r].*)$ $1 [N]
 
# If the string is still unchanged, apply output formatting and send to the
# interface CGI script.
 
# First, remove the unchanged-marker 'r'
a\
RewriteRule ^q(.*)qr(.*)$ q$1q$2
# Finally, pass the resulting string to a simple CGI or PHP script to print it
# to the web browser. [R] means to redirect to it, ending rewriting.
a\
RewriteRule ^q(.*)q(.*)$ /print.php?$1 [R]
# Done. Quit. Get out of here.
q

Testing it out

For obvious reasons I wouldn’t want you to test this on my server, but if you want to set this up on your own server, setup should be very easy: set up a new virtual host and let the virtual host config stanza include the compiled output of your Thue program.

One “small” caveat is that pretty much every HTTP client available will only follow a very small number of recursive redirects. To actually see a largeish program (such as hello world) run to completion you will have to reconfigure your HTTP client to follow a very large (a few hundred thousand) number of redirects. Using the command-line curl program, curl -L -g --max-redirs 300000 seems to do the trick.

Yesterday, I wrote a Thue implementation in Haskell. At this point, the implementation is painfully slow (about 35 minutes to run the brainfuck “Hello World!” through the BF Thue interpreter on my MacBook, as compared to about 4 minutes for the python Thue implementation run in python 2.5.1). I’m thinking I should a) should use ByteString’s instead of String, and b) use some smarter algorithm for matching the rules (instead of untilDone (foldl applyRule input rules), it’d be something more like compiling an automaton out of all rules and untilDone (run automaton)). By reducing the number of rules (eliminating the 50 or so #::=# rules, which are comments in idiomatic Thue but don’t strictly need special processing), I could squeeze about twice the performance out of it – this optimization brought the execution time down to 35 minutes. I need at least 10x the performance before this program is anything to brag about!

Another idea for the future is to implement parallel Thue by splitting up the state and then replacing in the parts until no replacements can be done in parallel, then running a few iterations serially on the whole state. You could also just synchronize once and move the split-point – which would eliminate the problem of deciding when to start going parallell again since you’d never really go serial. With the language designed to allow random replacement order, any valid Thue program already contains the synchronization needed to make it evaluate the right thing and e.g. output things in the correct order, so this is perfectly safe provided you have a correct implementation and correct programs.

Although it’s fun to make things go fast, I think parallel Thue would be much more interesting as it might even be something that’s never been done before!

Anyway, if you want to try it out, here’s my Thue darcs repository, containing the haskell source and the BF interpreter in Thue with the BF Hello world program I’ve been using for testing. It should take exactly 287197 steps (and heaps of time) to complete the execution and print "Hello world!\n" as a series of binary numbers separated by underscores.

Based on the mod_rewrite experiment from the other week, I hacked up a small Thue to mod_rewrite compiler in sed. For testing, I have used the brainfuck interpreter in Thue (as far as I can see, this is like the only example of a “real-world” Thue program). I tested this on the small 3+5 examples included in the BF Thue distribution and tried to test it on BF Hello World, but apache runs out of memory before completing the rewriting

Anyway, in this BF interpreter, the interpretation is bootstrapped by a circumflex, ‘^’, so the interpreter placeholder I introduced last week had a natural use allowing us to simply enter the brainfuck program as a URL, followed by a colon and input as binary underscore-separated numbers (terminated by 0_), and have patience.

The Thue interpreter needs to keep track of a few bits of state – all of this has to be encoded in some reliable way in the URL we’re continually rewriting:

• Have we added the interpreter? For BF+Thue, this is ‘^’ which is really something that has leaked from this one specific Thue program into the interpreter – which is really ugly, but hey, at least it was easy. Anyway, since we’re in the root of the virtual host, we can use the leading slash to encode this information – simply remove it after adding the interpreter, and we can match on ^/(.*)$ to determine whether we should add the bootstrap. (I have since realized that there is not much that prevents a malicious Thue program to output a slash as its first character, thereby breaking my entire system. Well, well, in version 2.0 I’ll replace this with a more robust encoding system.)
• The current output string. Stored in the first part of the URL, terminated by a ‘q’ (I’m having real trouble here with selecting characters unused in the program and all its possible states – otherwise matching would be a bitch)
• Did we rewrite anything in the last pass over the state? If nothing was rewritten, we must terminate the program. After the ‘q’ that terminates the output string, we store an ‘r’ before starting going through the rules and then every time we apply a rule we remove the ‘r’. If the ‘r’ is still there after having tried every rule in the program, we’re done and pass the output string to the printer PHP script.
• Finally, the current program state is stored after the q and r markers and goes on to the end of the URL.

In the end, this became something quite beautiful in its ugliness, although it could certainly need some robustness work. For example, it blindly relies on the Thue program to never ever use q or r anywhere (and probably a few other things I haven’t thought of). This should be changed to a totally robust encoding of anything that the rewrite rules should operate on as data, that can’t interfere with the things that are used as control structures and data formatting by the rewrite rules.

Here is the translator sed script in all its regexp-wtf glory, highlighted as Perl since GeSHi unfortunately doesn’t have sed highlighting.

# Remove comments
s/^#.*$//
# Rewrite question marks since they interfere with mod_rewrite by making the
# productions look like requests with query strings, which apache then splits.
s/\?/Q/g
# Escape characters with special meanings in regexps.
s/\([.*+(){}^$<>[\\ |]\|\]\)/\\\1/g
# Remove the ::= terminating line since it doesn't define a rule.
s/^::=$//
# Output rule: ~asf means to print the string "asf" and remove the matched string.
s/^\(.*\)::=~\(.*\)$/RewriteRule ^(.*)qr?(.*)\1(.*)$ $1\2q$2$3 [N]/
# Normal rule: match substring and replace it
s/^\(.*\)::=\(.*\)$/RewriteRule ^(.*)qr?(.*)\1(.*)$ $1q$2\2$3 [N]/

Note that the resulting rewrite rules are meant to be inserted into the mod_rewrite embedded language bootstrap I built in the previous post.

While setting up my blosxom blog’s apache vhost to rewrite URL:s to pass them by the blosxom CGI script, I happened to set up a redirection loop with apache’s mod_rewrite module – by accident – and realized that mod_rewrite might be Turing complete. (Always my instinct when something has the ability to loop.) After some more thinking, I realized that this apache module really is a bona fide String rewriting system which can be used to implement both Tag systems and Cellular automata, both of which can be Turing complete. Actually, since mod_rewrite can implement any tag system or cellular automaton, mod_rewrite is Turing complete.

So, if one felt like it, mod_rewrite can be configured with a Turing complete set of rewrite rules such that each accessed URL is a program, and the final URL is the out-data (or a link to a CGI-script that gives back the final output to the user, with suitable decoding). It’s possible (trivial, even) to add a first rewrite rule that bootstraps the rewriting with an interpreter string. It’s theoretically possible to have this be something like a Haskell interpreter – imagine the possibilities! – a dog-slow Haskell interpreter implemented in an apache config file!

Here’s a proof-of-concept implementation of a rewrite system framework in mod_rewrite. All that’s missing is a set of rewrite rules to implement something interesting, like 99-bottles-of-beer, bon-digi or a Universal Turing Machine. Note that apache by default limits the number of “internal recursions” to 10, and with any serious use of this you’re likely to hit that limit. Increase as needed.

# This file should be included in an Apache2 config file for a VirtualHost.
 
# Enable rewriting
RewriteEngine on
 
# First off, set a sensible log level so that you can see what goes wrong
RewriteLogLevel 3
RewriteLog "/var/log/apache2/rewrite/rewrite.log"
 
# This should only run on the first inputed string to add the interpreter.
# After each run of substitutions, we return to the first rule, so this must
# be safe and idempotent. So, we add the interpeter prefixed by '-' if the
# string does not start with '-'. (This could also be used for input programs
# to replace the interpreter if they like. We could also simply require input
# programs to come with their own interpreters and do nothing here.)
RewriteRule ^([^-].*)$ -INTERPRETER$1
 
# Add a comma to distinguish unchanged strings. This would be the termination
# condition for our rewrite system. Of course there are other ways to do this,
# for example a regexp which evaluates into the terminate-rule at the bottom.
# Doesn't need to be a comma, of course. If this character is part of the input
# alphabet, it could confuse some things though.
RewriteRule ^(.*)$ ,$1
 
# This is where the implementation of the entire string rewriting system would
# be. The general format is ,xyz -> xy'z - remove the first comma to mark the
# string as matched and changed (if there was a comma to start with), then
# change the string y to y' (with x and z left unchanged).
RewriteRule ^,?(.*)foo(.*)$ $1bar$2
# ... etc until your rewrite rules implement some turing-complete language, or
# a program that does something interesting.
 
# If the string has changed, we are not yet done. Loop to the beginning and
# remove the changed-marker. This doesn't change the string at all ('-' is a
# special substitution string that simple uses the original string), just has
# the [N] flag to trigger apache to restart rewriting.
RewriteRule ^[^,].*$ - [N]
 
# If the string is still unchanged, terminate and apply output-rewriting.
 
# First, remove the comma
RewriteRule ^,(.*)$ $1 
# Since the example string INTERPRETER is not actually interpreted in this
# example, remove it after applying the rewrite rules.
RewriteRule ^-INTERPRETER(.*)$ $1
# Finally, pass the resulting string to a simple CGI or PHP script to print it
# to the web browser. [L] means to abort rewriting here.
RewriteRule ^(.*)$ /print.php?$1 [L]