• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
84namespace boost { namespace hof {
85
86namespace detail{
87
88template<class F>
89struct compute_indirect_ref
90{ typedef indirect_adaptor<const F*> type; };
91
92template<class F>
93struct compute_indirect_ref<indirect_adaptor<F*>>
94{ typedef indirect_adaptor<F*> type; };
95
96template<class F>
97constexpr indirect_adaptor<const F*> make_indirect_ref(const F& f) noexcept
98{
99    return indirect_adaptor<const F*>(&f);
100}
101
102template<class F>
103constexpr indirect_adaptor<const F*> make_indirect_ref(const indirect_adaptor<F*>& f) noexcept
104{
105    return f;
106}
107
108template<class F, class=void>
109struct fix_result
110{
111    template<class... Ts>
112    struct apply
113    {
114        typedef decltype(std::declval<F>()(std::declval<Ts>()...)) type;
115    };
116};
117
118template<class F>
119struct 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
131template<class F, class Result, int N>
132struct 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>
141    constexpr const F& base_function(Ts&&... xs) const noexcept
142    {
143        return boost::hof::always_ref(*this)(xs...);
144    }
145
146    template<class... Ts>
147    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
183template<class F, class Result>
184struct fix_adaptor_base<F, Result, 0> : F
185{
186    BOOST_HOF_INHERIT_CONSTRUCTOR(fix_adaptor_base, F);
187
188    template<class... Ts>
189    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
215    operator()(Ts&&... xs) const
216    {
217        return this->base_function(xs...)(*this, BOOST_HOF_FORWARD(Ts)(xs)...);
218    }
219};
220}
221
222template<class F>
223struct 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
230template<class Result, class F>
231struct 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
238BOOST_HOF_DECLARE_STATIC_VAR(fix, detail::make<fix_adaptor>);
239
240}} // namespace boost::hof
241
242#endif
243