1 /*=============================================================================
2 Copyright (c) 2014 Paul Fultz II
3 fix.h
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 ==============================================================================*/
7
8 #ifndef BOOST_HOF_GUARD_FUNCTION_FIX_H
9 #define BOOST_HOF_GUARD_FUNCTION_FIX_H
10
11 /// fix
12 /// ===
13 ///
14 /// Description
15 /// -----------
16 ///
17 /// The `fix` function adaptor implements a fixed-point combinator. This can be
18 /// used to write recursive functions.
19 ///
20 /// When using `constexpr`, a function can recurse to a depth that is defined by
21 /// `BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH`(default is 16). There is no limitiation on
22 /// recursion depth for non-constexpr functions. In addition, due to the
23 /// eagerness of `constexpr` to instantiation templates, in some cases, an
24 /// explicit return type must be specified in order to avoid reaching the
25 /// recursion limits of the compiler. This can be accomplished using
26 /// [`boost::hof::result`](/include/boost/hof/result):
27 ///
28 /// int r = boost::hof::result<int>(factorial)(5);
29 ///
30 /// Synopsis
31 /// --------
32 ///
33 /// template<class F>
34 /// constexpr fix_adaptor<F> fix(F f);
35 ///
36 /// Semantics
37 /// ---------
38 ///
39 /// assert(fix(f)(xs...) == f(fix(f), xs...));
40 ///
41 /// Requirements
42 /// ------------
43 ///
44 /// F must be:
45 ///
46 /// * [ConstFunctionObject](ConstFunctionObject)
47 /// * MoveConstructible
48 ///
49 /// Example
50 /// -------
51 ///
52 /// #include <boost/hof.hpp>
53 /// #include <cassert>
54 ///
55 /// int main() {
56 /// auto factorial = boost::hof::fix(
57 /// [](auto recurse, auto x) -> decltype(x) {
58 /// return x == 0 ? 1 : x * recurse(x-1);
59 /// }
60 /// );
61 /// int r = boost::hof::result<int>(factorial)(5);
62 /// assert(r == 5*4*3*2*1);
63 /// }
64 ///
65 /// References
66 /// ----------
67 ///
68 /// * [Fixed-point combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator)
69 /// * [Recursive](Recursive)
70 ///
71
72 #include <boost/hof/always.hpp>
73 #include <boost/hof/detail/callable_base.hpp>
74 #include <boost/hof/reveal.hpp>
75 #include <boost/hof/detail/delegate.hpp>
76 #include <boost/hof/detail/move.hpp>
77 #include <boost/hof/detail/make.hpp>
78 #include <boost/hof/detail/static_const_var.hpp>
79 #include <boost/hof/indirect.hpp>
80 #include <boost/hof/result.hpp>
81 #include <boost/hof/detail/recursive_constexpr_depth.hpp>
82
83
84 namespace boost { namespace hof {
85
86 namespace detail{
87
88 template<class F>
89 struct compute_indirect_ref
90 { typedef indirect_adaptor<const F*> type; };
91
92 template<class F>
93 struct compute_indirect_ref<indirect_adaptor<F*>>
94 { typedef indirect_adaptor<F*> type; };
95
96 template<class F>
make_indirect_ref(const F & f)97 constexpr indirect_adaptor<const F*> make_indirect_ref(const F& f) noexcept
98 {
99 return indirect_adaptor<const F*>(&f);
100 }
101
102 template<class F>
make_indirect_ref(const indirect_adaptor<F * > & f)103 constexpr indirect_adaptor<const F*> make_indirect_ref(const indirect_adaptor<F*>& f) noexcept
104 {
105 return f;
106 }
107
108 template<class F, class=void>
109 struct fix_result
110 {
111 template<class... Ts>
112 struct apply
113 {
114 typedef decltype(std::declval<F>()(std::declval<Ts>()...)) type;
115 };
116 };
117
118 template<class F>
119 struct fix_result<F, typename holder<
120 typename F::result_type
121 >::type>
122 {
123 template<class...>
124 struct apply
125 {
126 typedef typename F::result_type type;
127 };
128
129 };
130
131 template<class F, class Result, int N>
132 struct fix_adaptor_base : F
133 {
134 BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor_base, F);
135
136 typedef typename compute_indirect_ref<F>::type base_ref_type;
137 typedef fix_adaptor_base<base_ref_type, Result, N-1> derived;
138
139
140 template<class... Ts>
base_functionboost::hof::detail::fix_adaptor_base141 constexpr const F& base_function(Ts&&... xs) const noexcept
142 {
143 return boost::hof::always_ref(*this)(xs...);
144 }
145
146 template<class... Ts>
derived_functionboost::hof::detail::fix_adaptor_base147 constexpr derived derived_function(Ts&&... xs) const noexcept
148 {
149 return derived(boost::hof::detail::make_indirect_ref(this->base_function(xs...)));
150 }
151
152 struct fix_failure
153 {
154 template<class Failure>
155 struct apply
156 {
157 template<class... Ts>
158 struct of
159 : Failure::template of<derived, Ts...>
160 {};
161 };
162 };
163
164 struct failure
165 : failure_map<fix_failure, F>
166 {};
167
168
169 BOOST_HOF_RETURNS_CLASS(fix_adaptor_base);
170
171 template<class... Ts>
172 constexpr BOOST_HOF_SFINAE_RESULT(const F&, id_<derived>, id_<Ts>...)
173 operator()(Ts&&... xs) const BOOST_HOF_SFINAE_RETURNS
174 (
175 BOOST_HOF_MANGLE_CAST(const F&)(BOOST_HOF_CONST_THIS->base_function(xs...))
176 (
177 BOOST_HOF_MANGLE_CAST(derived)(BOOST_HOF_CONST_THIS->derived_function(xs...)),
178 BOOST_HOF_FORWARD(Ts)(xs)...
179 )
180 );
181 };
182
183 template<class F, class Result>
184 struct fix_adaptor_base<F, Result, 0> : F
185 {
186 BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor_base, F);
187
188 template<class... Ts>
base_functionboost::hof::detail::fix_adaptor_base189 const F& base_function(Ts&&...) const noexcept
190 {
191 return *this;
192 }
193
194 struct fix_failure
195 {
196 template<class Failure>
197 struct apply
198 {
199 template<class... Ts>
200 struct of
201 : Failure::template of<fix_adaptor_base, Ts...>
202 {};
203 };
204 };
205
206 struct failure
207 : failure_map<fix_failure, F>
208 {};
209
210
211 BOOST_HOF_RETURNS_CLASS(fix_adaptor_base);
212
213 template<class... Ts>
214 typename Result::template apply<fix_adaptor_base, Ts...>::type
operator ()boost::hof::detail::fix_adaptor_base215 operator()(Ts&&... xs) const
216 {
217 return this->base_function(xs...)(*this, BOOST_HOF_FORWARD(Ts)(xs)...);
218 }
219 };
220 }
221
222 template<class F>
223 struct fix_adaptor : detail::fix_adaptor_base<F, detail::fix_result<F>, BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH>
224 {
225 typedef fix_adaptor fit_rewritable1_tag;
226 typedef detail::fix_adaptor_base<F, detail::fix_result<F>, BOOST_HOF_RECURSIVE_CONSTEXPR_DEPTH> base;
227 BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor, base);
228 };
229
230 template<class Result, class F>
231 struct result_adaptor<Result, fix_adaptor<F>>
232 : fix_adaptor<result_adaptor<Result, F>>
233 {
234 typedef fix_adaptor<result_adaptor<Result, F>> base;
235 BOOST_HOF_INHERIT_CONSTRUCTOR(result_adaptor, base)
236 };
237
238 BOOST_HOF_DECLARE_STATIC_VAR(fix, detail::make<fix_adaptor>);
239
240 }} // namespace boost::hof
241
242 #endif
243