fix_fn/
lib.rs

1//! This library enables the creation of recursive closures by providing a
2//! single macro [`fix_fn`]. The functionality is similar to the
3//! [Y combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed-point_combinators_in_lambda_calculus).
4//! Recursive closures can have arbitrary amounts of parameters and can capture
5//! variables.
6//!
7//! ```
8//! use fix_fn::fix_fn;
9//!
10//! let fib = fix_fn!(|fib, i: u32| -> u32 {
11//!     if i <= 1 {
12//!            i
13//!      } else {
14//!          // fib will call the closure recursively
15//!          fib(i - 1) + fib(i - 2)
16//!      }
17//!  });
18//!
19//! assert_eq!(fib(7), 13);
20//! ```
21//! 
22//! The generated code is not completely abstraction free as it uses one dyn trait
23//! (without any boxing) to overcome rust's recursive type limitations.
24//! In most cases, however, the optimizer should be able to eliminate any dynamic dispatch.
25//! 
26//! Unfortunately, mutable recursive closures are not supported.
27
28
29/// Takes a closure definition where the first parameter will be a [`Fn`] to the closure itself.
30/// Returns a recursive closure with the same signature, except the first parameter will be
31/// eliminated.
32/// 
33/// The passed closure needs to have at least one parameter. This
34/// first parameter can be used to call the closure itself, achieving recursion.
35/// It must not be annotated with a type.
36/// 
37/// Additional parameters will be parameters of the resulting closure.
38/// All additional parameters must be annotated with types.
39/// 
40/// The closure definition needs to have a result-type annotation.
41/// 
42/// `move` can be used and has the [usual semantic](https://doc.rust-lang.org/1.18.0/book/first-edition/closures.html#move-closures).
43/// 
44/// # Example
45/// 
46/// ```
47/// use fix_fn::fix_fn;
48///  
49/// let fib = fix_fn!(|fib, i: u32| -> u32 {
50///     if i <= 1 {
51///         i
52///     } else {
53///         // fib will call the closure recursively
54///         fib(i - 1) + fib(i - 2)
55///     }
56/// });
57///
58/// // resulting lambda only has the `i: u32` parameter
59/// assert_eq!(fib(7), 13);
60/// ```
61#[macro_export]
62macro_rules! fix_fn {
63    (
64        $($mov:ident)? |$self_arg:ident $(, $arg_name:ident : $arg_type:ty)* $(,)? |
65            -> $ret_type:ty
66        $body:block
67    ) => {{
68        trait HideFn {
69            fn call(&self, $($arg_name : $arg_type ,)*) -> $ret_type;
70        }
71
72        struct HideFnImpl<F: Fn(&dyn HideFn, $($arg_type ,)*) -> $ret_type>(F);
73
74        impl<F: Fn(&dyn HideFn, $($arg_type ,)*) -> $ret_type> HideFn for HideFnImpl<F> {
75            #[inline]
76            fn call(&self, $($arg_name : $arg_type ,)*) -> $ret_type {
77                self.0(self, $($arg_name ,)*)
78            }
79        }
80
81        let inner = HideFnImpl(
82            #[inline]
83            $($mov)?
84            |$self_arg, $($arg_name : $arg_type ,)*| -> $ret_type {
85                let $self_arg = |$($arg_name : $arg_type ),*| $self_arg.call($($arg_name ,)*);
86                {
87                    $body
88                }
89            }
90        );
91
92
93        #[inline]
94        move |$($arg_name : $arg_type),*| -> $ret_type {
95            inner.call($($arg_name),*)
96        }
97    }};
98    (
99        $($mov:ident)? |$($arg_name:ident $(: $arg_type:ty)?),* $(,)?|
100        $body:expr
101    ) => {
102        compile_error!("Closure passed to fix_fn needs return type!");
103    };
104    (
105        $($mov:ident)? |$self_arg:ident : $self_type:ty $(, $arg_name:ident $(: $arg_type:ty)?)* $(,)? |
106            -> $ret_type:ty
107        $body:block
108    ) => {
109        compile_error!(concat!("First parameter ", stringify!($self_arg), " may not have type annotation!"));
110    };
111    (
112        $($mov:ident)? |$self_arg:ident $(, $arg_name:ident $(: $arg_type:ty)?)* $(,)? |
113            -> $ret_type:ty
114        $body:block
115    ) => {
116        compile_error!("All parameters except first need to have an explicit type annotation!");
117    };
118}
119
120#[cfg(test)]
121mod tests {
122    use std::cell::RefCell;
123
124    #[test]
125    fn test_zero_parameter() {
126        fn create() -> impl Fn() -> i32 {
127            let cell = RefCell::new(0);
128
129            fix_fn!(move |rec| -> i32 {
130                if *cell.borrow() == 10 {
131                    10
132                } else {
133                    *cell.borrow_mut() += 1;
134                    rec()
135                }
136            })
137        }
138
139        let f = create();
140
141        assert_eq!(f(), 10);
142    }
143
144    #[test]
145    fn test_one_parameter() {
146        let fib = fix_fn!(|fib, i: u32| -> u32 {
147            if i <= 1 {
148                i
149            } else {
150                fib(i - 1) + fib(i - 2)
151            }
152        });
153
154        assert_eq!(fib(7), 13);
155    }
156
157    #[test]
158    fn test_two_parameter() {
159        let pow = fix_fn!(|pow, x: u32, y: u32| -> u32 {
160            if y == 1 {
161                x
162            } else if x % 2 == 0 {
163                pow(x * x, x / 2)
164            } else {
165                x * pow(x, y - 1)
166            }
167        });
168
169        assert_eq!(pow(3, 9), 19683);
170    }
171}
fix_fn/lib.rs

fix_fn/
lib.rs
