Writing Divided differences using macros

As some sort of enlightening exercise, I want to write divided differences in Rust using Macros.

After a lot of help from the discord channel, we've arrived at this

macro_rules! divided_difference {
    () => {};
    ([$($x:expr,)+]; $f:ident) => { $crate::divided_difference!([$($x),+]; $f) };
    ([$x:expr]; $f:ident) => {
        $f($x)
    };
    ([$left:expr, $right:expr]; $f:ident) => {
        ($f($right) - $f($left)) / ($right - $left)
    };
    ([$leftmost:expr $(,$middle:expr)* ,$rightmost:expr]; $f:ident) => {
        (divided_difference!([$($middle,)* $rightmost]; $f) - divided_difference!([$leftmost, $($middle),*]; $f)) / ($rightmost - $leftmost)
    };
}

where this fails to compile.

See playground.

You can use a variant of tt munchers to handle this

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1c92a6e0f72c55fb177ff138629fca9f

1 Like

This looks like it is the solution, but I am not familiar with @split. I also don't really see why you have another case for this, i.e.

    (@split [$leftmost:expr] [$($middle:expr),*] [$next:expr $(, $rest:expr)*]; $f:ident) => {
        divided_difference!(@split [$leftmost] [$($middle, )* $next] [$($rest),*]; $f)
    };

Thanks!

You need another internal state to handle the tt muncher, this is @split. I just like labeling internal states of this macro state machine with names. In this case split splits off the last element of the list.

1 Like

That state is used to extract the middle. This is recursion, the first @split case is the base case, where there was nothing else in the middle. The second @split case is the recursive case, where there are items in the middle.

@split [0] [] [1, 2, 3, 4, 5] // second @split
@split [0] [1] [2, 3, 4, 5]
@split [0] [1, 2] [3, 4, 5]
@split [0] [1, 2, 3] [4, 5]
@split [0] [1, 2, 3, 4] [5] // first @split

// leftmost = 0
// middle = [1, 2, 3, 4]
// rightmost = 5
1 Like

Normally, Rust macros essentially behave like linked list pattern match. So you can pattern match (x:xs), but you cannot pattern match the end of the linked list (this is the case in many functional programming languages too).

However, by making use of recursion, you can move the entire middle of the list to another list, leaving you with the last part of a list.

#[doc(hidden)]
#[macro_export]
macro_rules! __split_mid_right {
    ($f:tt $leftmost:tt [$(($middle:tt))*] [$rightmost:tt]) => {
        (
            $crate::divided_difference!([$($middle,)* $rightmost]; $f) -
            $crate::divided_difference!([$leftmost $(,$middle)*]; $f)
        ) / ($rightmost - $leftmost)
    };
    ($f:tt $leftmost:tt [$($ms:tt)*] [$x:tt $($xs:tt)*]) => {
        $crate::__split_mid_right!($f $leftmost [$($ms)* $x] [$($xs)*]);
    };
}

#[macro_export]
macro_rules! divided_difference {
    ([$($x:expr,)+]; $f:ident) => {
        $crate::divided_difference!([$($x),+]; $f)
    };
    ([$x:expr]; $f:ident) => {
        $f($x)
    };
    ([$left:expr, $right:expr]; $f:ident) => {
        ($f($right) - $f($left)) / ($right - $left)
    };
    ([$leftmost:expr $(,$middle:expr)*]; $f:ident) => {
        $crate::__split_mid_right!($f $leftmost [] [$(($middle))*])
    };
}
1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.