Macro system apparently has trouble with nested token trees

[eholk]

The title is my best hypothesis for what's happening. It is probably wrong.

I have a set of macros that should implement a lambda calculus interpreter:

macro_rules! eval {
    { $e:tt } => (ee! { $e , (id_k) })
}

macro_rules! ee {
    { [$(#$x:ident)+] $([$y:ident,$v:tt])*, $k:tt } =>
        (lookup!{$(#$x)+, $([$y,$v])*, $k});

    { (λ $x:ident. $e:tt) $([$y:ident,$v:tt])*, $k:tt } =>
        (apply_k! {$k, (closure $x . $e : $([$y,$v])*)});

    { ($rator:tt $rand:tt) $([$y:ident,$v:tt])*, $k:tt } =>
        (ee! { $rator $([$y,$v])*,
              (rator_k $rand $([$y,$v])*, $k)});
}

macro_rules! lookup {
    { #$x:ident, [$y:ident,$v:tt] $([$ys:ident,$vs:tt])*, $k:tt }
    => (apply_k!{$k, $v});

    { #$x:ident$(#$xs:ident)+, [$y:ident,$v:tt]$([$ys:ident,$vs:tt])+,
     $k:tt }
    => (lookup!{$(#$xs)+, $([$ys,($vs)])+, $k});
}

macro_rules! apply_k {
    { (id_k), $v:tt } => { log_syntax! { $v }; () };
    { (rator_k $rand:tt $([$y:ident,$vs:tt])*, $k:tt), $v:tt } => (
        ee! { $rand $([$y,$vs])*,
              (rand_k $v, $k) }
    );
    { (rand_k (closure $x:ident . $e:tt : $([$y:ident,$vs:tt])*), $k:tt),
       $v:tt } => (
        ee! { $e [$x,$v] $([$y,$vs])*, $k }
    )
}

I can use this to interpret a lambda calculus term:

fn main() {
    trace_macros!(true);

    eval! {
        ((λ x. [#x]) (λ y. [#y]))
    };
}

This evaluates as follows, which is clearly wrong:

eval! { ((λ x.[#x])(λ y.[#y])) }
ee! { ((λ x.[#x])(λ y.[#y])),(id_k) }
ee! { (λ x.[#x]),(rator_k(λ y.[#y]),(id_k)) }
apply_k! { (rator_k(λ y.[#y]),(id_k)),(closure x.[#x]:) }
lambda.rs:50:21: 50:22 error: No rules expected the token (
lambda.rs:50         ((λ x. [#x]) (λ y. [#y]))

However, if I copy the last line in the macro trace and try to run that, I get a little further:

apply_k! { (rator_k(λ y.[#y]),(id_k)),(closure x.[#x]:) }
ee! { (λ y.[#y]),(rand_k(closure x.[#x]:),(id_k)) }
apply_k! { (rand_k(closure x.[#x]:),(id_k)),(closure y.[#y]:) }
lambda.rs:45:34: 45:35 error: No rules expected the token (
lambda.rs:45     apply_k! { (rator_k(λ y.[#y]),(id_k)),(closure x.[#x]:) };

If I repeat the process, I get:

apply_k! { (rand_k(closure x.[#x]:),(id_k)),(closure y.[#y]:) }
ee! { [#x][x,(closure y.[#y]:)],(id_k) }
lambda.rs:45:48: 45:49 error: No rules expected the token (
lambda.rs:45     apply_k! { (rand_k(closure x.[#x]:),(id_k)),(closure y.[#y]:) };
                                                             ^

And again...

ee! { [#x][x,(closure y.[#y]:)],(id_k) }
lookup! { #x,[x,(closure y.[#y]:)],(id_k) }
lambda.rs:45:17: 45:18 error: No rules expected the token (
lambda.rs:45     ee! { [#x][x,(closure y.[#y]:)],(id_k) };
                              ^

And again...

lookup! { #x,[x,(closure y.[#y]:)],(id_k) }
apply_k! { (id_k),(closure y.[#y]:) }
(closure y.[#y]:)

The last line, (closure y.[#y]:), is what I would expect the original expression to evaluate to. The fact that repeated invocation causes us to make a little more progress each time makes me think there's a bug in how macro parsing works.

[lkuper]

A minimal test case would be helpful.

[paulstansifer]

The syntax in the bug report is out-of-date. Here's a lambda calculus interpreter in Rust's macro system (working as of 028eeb1, according to my super superficial testing).

macro_rules! eval (
    ( $e:tt ) => (ee! ( $e , (id_k) ))
)

macro_rules! ee (
    ( [$(#$x:ident)+] $([$y:ident,$v:tt])*, $k:tt ) =>
        (lookup!($(#$x)+, $([$y,$v])*, $k));

    ( (λ $x:ident. $e:tt) $([$y:ident,$v:tt])*, $k:tt ) =>
        (apply_k! ($k, (closure $x . $e : $([$y,$v])*)));

    ( ($rator:tt $rand:tt) $([$y:ident,$v:tt])*, $k:tt ) =>
        (ee! ( $rator $([$y,$v])*,
              (rator_k $rand $([$y,$v])*, $k)));
)

macro_rules! lookup (
    ( #$x:ident, [$y:ident,$v:tt] $([$ys:ident,$vs:tt])*, $k:tt )
    => (apply_k!($k, $v));

    ( #$x:ident$(#$xs:ident)+, [$y:ident,$v:tt]$([$ys:ident,$vs:tt])+,
     $k:tt )
    => (lookup!($(#$xs)+, $([$ys,($vs)])+, $k));
)

macro_rules! apply_k (
    ( (id_k), $v:tt ) => ( { log_syntax! ( $v ); () } );
    ( (rator_k $rand:tt $([$y:ident,$vs:tt])*, $k:tt), $v:tt ) => (
        ee! ( $rand $([$y,$vs])*,
              (rand_k $v, $k) )
    );
    ( (rand_k (closure $x:ident . $e:tt : $([$y:ident,$vs:tt])*), $k:tt),
       $v:tt ) => (
        ee! ( $e [$x,$v] $([$y,$vs])*, $k )
    )
)

fn main() {
    trace_macros!(true);

    eval! (
        ((λ x. [#x]) (λ y. [#y]))

        // For a good time, call:
        //((λ x. ([#x] [#x])) (λ x. ([#x] [#x])))
    );
}