7
\$\begingroup\$

For fun, I implemented a trampoline function for C++ constexpr functions, since the recursion limit for constexpr functions is much smaller (500 by default on gcc).

It is a bit messy with the type deduction and the fact that the trampolined function must only take a std::tuple as its argument.

#pragma once // Note: I use pragma once, not header guards; I know the tradeoffs

#include <cstddef>

#include <tuple>
#include <type_traits>

namespace trampoline {    
    template<typename Answer>
    static constexpr auto trampoline(Answer && answerInit) {
        std::decay_t<Answer> answer{ std::forward<Answer>(answerInit) };
        while (!answer.finished()) {
            answer = answer.tail_call();
        }
        return answer.value();
    }

    template<typename AnswerFn, typename Args>
    class TrampolineFn
    {
        AnswerFn fn;
        Args args;
    public:
        using args_t = Args;

        constexpr TrampolineFn() = default;
        constexpr TrampolineFn(TrampolineFn<AnswerFn, Args> && other) = default;
        constexpr TrampolineFn(TrampolineFn<AnswerFn, Args> const& other) = default;

        constexpr TrampolineFn<AnswerFn, Args>& operator=(TrampolineFn<AnswerFn, Args> rhs) {
            fn = std::move(rhs.fn);
            assign_args(std::move(rhs.args), std::make_index_sequence<std::tuple_size<Args>::value>{});
            return *this;
        }

        template<typename TAnswerFn, typename TArgs>
        constexpr TrampolineFn(TAnswerFn && fn, TArgs && args)
            : fn{ std::forward<TAnswerFn>(fn) }
            , args{ std::forward<TArgs>(args) }
        {}

        constexpr decltype(auto) operator()() const {
            return fn(args);
        }
    private:
        template<std::size_t... Is>
        constexpr void assign_args(Args rhsArgs, std::index_sequence<Is...>) {
            int unused[] = {
                0,
                (std::get<Is>(args) = std::get<Is>(rhsArgs), 0)...
            };
            (void) unused;
        }
    };

    template<typename AnswerFn, typename Args>
    constexpr auto make_trampoline_fn(AnswerFn && fn, Args && args) {
        return TrampolineFn<AnswerFn, Args>{
            std::forward<AnswerFn>(fn),
            std::forward<Args>(args)
        };
    }

    template<typename T, typename U>
    class Answer
    {
        using AnswerFn = TrampolineFn<Answer<T, U>(*)(U), U>;
        bool finished_;
        AnswerFn fn_;
        T value_;
    public:
        constexpr Answer() = default;
        constexpr Answer(Answer<T, U> const&) = default;
        constexpr Answer(Answer<T, U> &&) = default;
        constexpr Answer& operator=(Answer<T, U> const&) = default;
        constexpr Answer& operator=(Answer<T, U> &&) = default;

        template<typename TTrampolineFn, typename TT>
        constexpr Answer(bool finished, TTrampolineFn && fn, TT value)
            : finished_{ finished }
            , fn_{ std::forward<TTrampolineFn>(fn) }
            , value_{ std::forward<TT>(value) }
        {}

        constexpr bool finished() const { return finished_; }
        constexpr T value() const { return value_; }
        constexpr Answer<T, U> tail_call() const {
            return fn_();
        }
    };

    template<typename T, typename TrampolineFn>
    constexpr auto make_answer(bool finished, T && value, TrampolineFn && fn) {
        return Answer<std::decay_t<T>, typename TrampolineFn::args_t>{
            finished,
            std::forward<TrampolineFn>(fn),
            std::forward<T>(value)
        };
    }
}

As an example of using it, here is a triangular number function:

namespace {   
    constexpr trampoline::Answer<std::uint64_t, std::tuple<std::uint64_t, std::uint64_t>> tri_impl(std::tuple<std::uint64_t, std::uint64_t> arg) {
        if (std::get<0>(arg) == 0) return trampoline::make_answer(true, std::get<1>(arg), trampoline::make_trampoline_fn(&tri_impl, std::tuple<std::uint64_t, std::uint64_t>{ 0, 0 }));
        return trampoline::make_answer(
            false,
            static_cast<std::uint64_t>(0),
            trampoline::make_trampoline_fn(
                &tri_impl,
                std::tuple<std::uint64_t, std::uint64_t>{
                    std::get<0>(arg) - 1,
                    std::get<1>(arg) + std::get<0>(arg)
                }
            )
        );
    }

    constexpr std::uint64_t tri(std::uint64_t n) {
        return trampoline::trampoline(
            trampoline::make_answer(
                false,
                static_cast<std::uint64_t>(0),
                trampoline::make_trampoline_fn(&tri_impl,
                    std::tuple<std::uint64_t, std::uint64_t>{ n, 0 }
                )
            )
        );
    }
}

[demo]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.