The program consists of commands executed in order. There is a single one-bit command:
0: Delete the left-most data bit.
and a single two-bit command:
1 x: If the left-most data bit is 1, copy bit x to the right of the data string.
We halt if ever the data string is empty.
Remarkably, this is enough to do universal computation. Implementing it in Rust's macro system gives a proof (probably not the first one) that Rust's macro system is Turing-complete, aside from the recursion limit imposed by the compiler.
#![feature(trace_macros)] macro_rules! bct { // cmd 0: d ... => ... (0, $($ps:tt),* ; $_d:tt) => (bct!($($ps),*, 0 ; )); (0, $($ps:tt),* ; $_d:tt, $($ds:tt),*) => (bct!($($ps),*, 0 ; $($ds),*)); // cmd 1p: 1 ... => 1 ... p (1, $p:tt, $($ps:tt),* ; 1) => (bct!($($ps),*, 1, $p ; 1, $p)); (1, $p:tt, $($ps:tt),* ; 1, $($ds:tt),*) => (bct!($($ps),*, 1, $p ; 1, $($ds),*, $p)); // cmd 1p: 0 ... => 0 ... (1, $p:tt, $($ps:tt),* ; $($ds:tt),*) => (bct!($($ps),*, 1, $p ; $($ds),*)); // halt on empty data string ( $($ps:tt),* ; ) => (()); } fn main() { trace_macros!(true); bct!(0, 0, 1, 1, 1 ; 1, 0, 1); }
This produces the following compiler output:
bct! { 0 , 0 , 1 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
...
bct.rs:19:13: 19:45 error: recursion limit reached while expanding the macro `bct`
bct.rs:19 => (bct!($($ps),*, 1, $p ; $($ds),*));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
You can try it online, as well.
Notes about the macro
I would much rather drop the commas and write
// cmd 0: d ... => ... (0 $($ps:tt)* ; $_d:tt $($ds:tt)*) => (bct!($($ps)* 0 ; $($ds)*)); // cmd 1p: 1 ... => 1 ... p (1 $p:tt $($ps:tt)* ; 1 $($ds:tt)*) => (bct!($($ps)* 1 $p ; 1 $($ds)* $p)); // cmd 1p: 0 ... => 0 ... (1 $p:tt $($ps:tt)* ; $($ds:tt)*) => (bct!($($ps)* 1 $p ; $($ds)*));
but this runs into the macro future-proofing rules.
If we're required to have commas, then it's at least nice to handle them uniformly, e.g.
// cmd 0: d ... => ... (0 $(, $ps:tt)* ; $_d:tt $(, $ds:tt)*) => (bct!($($ps),*, 0 ; $($ds),*)); // cmd 1p: 1 ... => 1 ... p (1, $p:tt $(, $ps:tt)* ; $($ds:tt),*) => (bct!($($ps),*, 1, $p ; 1 $(, $ds)*, $p)); // cmd 1p: 0 ... => 0 ... (1, $p:tt $(, $ps:tt)* ; $($ds:tt),*) => (bct!($($ps),*, 1, $p ; $($ds),*));
But this too is disallowed. An $x:tt variable cannot be followed by a
repetition $(...)*, even though it's (I believe) harmless. There is an open
RFC about this issue. For now I
have to handle the "one" and "more than one" cases separately, which is
annoying.
In general, I don't think macro_rules! is a good language for arbitrary
computation. This experiment shows the hassle involved in implementing one of
the simplest known "arbitrary computations". Rather, macro_rules! is good at
expressing patterns of code reuse that don't require elaborate compile-time
processing. It does so in a way that's declarative, hygienic, and high-level.
However, there is a big middle ground of non-elaborate, but non-trivial
computations. macro_rules! is hardly ideal for that, but procedural
macros have
problems of their own. Indeed, the bct! macro is an extreme case of a
pattern I've found useful in the real world. The idea is that every
recursive invocation of a macro gives you another opportunity to pattern-match
the arguments. Some of html5ever's
macros
do this, for example.