1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

//! This library enables the creation of recursive closures by providing a
//! single macro [`fix_fn`]. The functionality is similar to the
//! [Y combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed-point_combinators_in_lambda_calculus).
//! Recursive closures can have arbitrary amounts of parameters and can capture
//! variables.
//!
//! ```
//! use fix_fn::fix_fn;
//!
//! let fib = fix_fn!(|fib, i: u32| -> u32 {
//!     if i <= 1 {
//!            i
//!      } else {
//!          // fib will call the closure recursively
//!          fib(i - 1) + fib(i - 2)
//!      }
//!  });
//!
//! assert_eq!(fib(7), 13);
//! ```
//! 
//! The generated code is not completely abstraction free as it uses one dyn trait
//! (without any boxing) to overcome rust's recursive type limitations.
//! In most cases, however, the optimizer should be able to eliminate any dynamic dispatch.
//! 
//! Unfortunately, mutable recursive closures are not supported.


/// Takes a closure definition where the first parameter will be a [`Fn`] to the closure itself.
/// Returns a recursive closure with the same signature, except the first parameter will be
/// eliminated.
/// 
/// The passed closure needs to have at least one parameter. This
/// first parameter can be used to call the closure itself, achieving recursion.
/// It must not be annotated with a type.
/// 
/// Additional parameters will be parameters of the resulting closure.
/// All additional parameters must be annotated with types.
/// 
/// The closure definition needs to have a result-type annotation.
/// 
/// `move` can be used and has the [usual semantic](https://doc.rust-lang.org/1.18.0/book/first-edition/closures.html#move-closures).
/// 
/// # Example
/// 
/// ```
/// use fix_fn::fix_fn;
///  
/// let fib = fix_fn!(|fib, i: u32| -> u32 {
///     if i <= 1 {
///         i
///     } else {
///         // fib will call the closure recursively
///         fib(i - 1) + fib(i - 2)
///     }
/// });
///
/// // resulting lambda only has the `i: u32` parameter
/// assert_eq!(fib(7), 13);
/// ```
#[macro_export]
macro_rules! fix_fn {
    (
        $($mov:ident)? |$self_arg:ident $(, $arg_name:ident : $arg_type:ty)* $(,)? |
            -> $ret_type:ty
        $body:block
    ) => {{
        trait HideFn {
            fn call(&self, $($arg_name : $arg_type ,)*) -> $ret_type;
        }

        struct HideFnImpl<F: Fn(&dyn HideFn, $($arg_type ,)*) -> $ret_type>(F);

        impl<F: Fn(&dyn HideFn, $($arg_type ,)*) -> $ret_type> HideFn for HideFnImpl<F> {
            #[inline]
            fn call(&self, $($arg_name : $arg_type ,)*) -> $ret_type {
                self.0(self, $($arg_name ,)*)
            }
        }

        let inner = HideFnImpl(
            #[inline]
            $($mov)?
            |$self_arg, $($arg_name : $arg_type ,)*| -> $ret_type {
                let $self_arg = |$($arg_name : $arg_type ),*| $self_arg.call($($arg_name ,)*);
                {
                    $body
                }
            }
        );


        #[inline]
        move |$($arg_name : $arg_type),*| -> $ret_type {
            inner.call($($arg_name),*)
        }
    }};
    (
        $($mov:ident)? |$($arg_name:ident $(: $arg_type:ty)?),* $(,)?|
        $body:expr
    ) => {
        compile_error!("Closure passed to fix_fn needs return type!");
    };
    (
        $($mov:ident)? |$self_arg:ident : $self_type:ty $(, $arg_name:ident $(: $arg_type:ty)?)* $(,)? |
            -> $ret_type:ty
        $body:block
    ) => {
        compile_error!(concat!("First parameter ", stringify!($self_arg), " may not have type annotation!"));
    };
    (
        $($mov:ident)? |$self_arg:ident $(, $arg_name:ident $(: $arg_type:ty)?)* $(,)? |
            -> $ret_type:ty
        $body:block
    ) => {
        compile_error!("All parameters except first need to have an explicit type annotation!");
    };
}

#[cfg(test)]
mod tests {
    use std::cell::RefCell;

    #[test]
    fn test_zero_parameter() {
        fn create() -> impl Fn() -> i32 {
            let cell = RefCell::new(0);

            fix_fn!(move |rec| -> i32 {
                if *cell.borrow() == 10 {
                    10
                } else {
                    *cell.borrow_mut() += 1;
                    rec()
                }
            })
        }

        let f = create();

        assert_eq!(f(), 10);
    }

    #[test]
    fn test_one_parameter() {
        let fib = fix_fn!(|fib, i: u32| -> u32 {
            if i <= 1 {
                i
            } else {
                fib(i - 1) + fib(i - 2)
            }
        });

        assert_eq!(fib(7), 13);
    }

    #[test]
    fn test_two_parameter() {
        let pow = fix_fn!(|pow, x: u32, y: u32| -> u32 {
            if y == 1 {
                x
            } else if x % 2 == 0 {
                pow(x * x, x / 2)
            } else {
                x * pow(x, y - 1)
            }
        });

        assert_eq!(pow(3, 9), 19683);
    }
}