【初赛复习】【理性愉悦】编译时 bf 解释器
本文部分参考自 C++ Compiler as a Brainfuck Interpreter。
大家好今天是中秋节，来干点有意义的事！
马上就要初赛了，还是复习一下 c++ 吧。
最近 modulo256 很火，为啥不用 c++ 写一个 brainf**k 解释器呢？
当然，我们追求极致的性能，因此我们要求在编译期计算出结果！！！111
#include <iostream>
#include <string>
#include <type_traits>
template <char... val> struct Array {
using type = Array<val...>;
static constexpr inline auto size = sizeof...(val);
};
template <typename T>
concept Array_t = requires(T a) {
{ T::size } -> std::convertible_to<std::size_t>;
};
template <Array_t T> struct GetFirst;
template <char val0, char... val1> struct GetFirst<Array<val0, val1...>> {
static constexpr inline char value = val0;
};
template <> struct GetFirst<Array<>> {
static constexpr inline char value = 0;
};
template <Array_t T> struct DropFirst;
template <char val0, char... val1> struct DropFirst<Array<val0, val1...>> {
using value = Array<val1...>;
};
template <> struct DropFirst<Array<>> {
using value = Array<>;
};
template <Array_t T, int index>
constexpr char Get()
requires(index >= 0 && index < T::size)
{
if constexpr (index > 0)
return Get<typename DropFirst<T>::value, index - 1>();
else
return GetFirst<T>::value;
};
namespace detail {
template <Array_t T, char val> struct _Append_Impl;
template <char... original, char val>
struct _Append_Impl<Array<original...>, val> {
using value = Array<original..., val>;
};
template <Array_t T1, Array_t T2, int idx, char val> struct _Set_Impl;
template <char ori0, char... ori1, char... res, char val>
struct _Set_Impl<Array<ori0, ori1...>, Array<res...>, 0, val> {
using value =
typename _Set_Impl<Array<ori1...>, Array<res..., val>, -1, val>::value;
};
template <char... ori, char... res, char val>
struct _Set_Impl<Array<ori...>, Array<res...>, -1, val> {
using value = Array<res..., ori...>;
};
template <char ori0, char... ori1, char... res, int idx, char val>
requires(idx > 0)
struct _Set_Impl<Array<ori0, ori1...>, Array<res...>, idx, val> {
using value =
_Set_Impl<Array<ori1...>, Array<res..., ori0>, idx - 1, val>::value;
};
} // namespace detail
template <Array_t T, char val> struct Append {
using value = detail::_Append_Impl<T, val>::value;
};
template <Array_t T, int idx, char val> struct Set {
using value = detail::_Set_Impl<T, Array<>, idx, val>::value;
};
template <int n> struct SetupArray {
using value = Append<typename SetupArray<n - 1>::value, 0>::value;
};
template <> struct SetupArray<0> {
using value = Array<>;
};
template <Array_t Code, int cur, int dep, bool dir>
constexpr int next_matching_bracket() {
if constexpr (cur < 0 || cur >= Code::size)
return -1;
else {
constexpr int dlt = dir ? 1 : -1;
constexpr int tp =
((Get<Code, cur>() == '[') ? 1 : ((Get<Code, cur>() == ']' ? 0 : -1)));
if constexpr (~tp) {
constexpr int nxt = dep + ((tp ^ dir) ? -1 : 1);
if constexpr (!nxt)
return cur;
else
return next_matching_bracket<Code, cur + dlt, nxt, dir>();
} else
return next_matching_bracket<Code, cur + dlt, dep, dir>();
}
}
template <int _ip, int _dp> struct State {
static constexpr inline int ip = _ip, dp = _dp; // instruction, data
};
template <typename T>
concept State_t = requires(T a) {
{ T::ip } -> std::convertible_to<int>;
{ T::dp } -> std::convertible_to<int>;
};
template <Array_t _code, Array_t _memory, Array_t _console, Array_t _input,
State_t _state, typename Final_Flag = void>
struct VM {
using code = _code;
using memory = _memory;
using console = _console;
using input = _input;
using state = _state;
static constexpr inline char cur_inst = Get<_code, _state::ip>();
static constexpr inline int cur_dlt =
(cur_inst == '+') ? 1 : (cur_inst == '-' ? -1 : 0);
static constexpr inline int cur_data =
cur_inst == ',' ? GetFirst<input>::value : Get<memory, state::dp>();
using next_state =
State<(cur_inst == '[' && !Get<memory, state::dp>())
? next_matching_bracket<code, state::ip, 0, 1>() + 1
: ((cur_inst == ']' && Get<memory, state::dp>())
? next_matching_bracket<code, state::ip, 0, 0>() + 1
: state::ip + 1),
(cur_inst == '>' ? state::dp + 1
: (cur_inst == '<' ? state::dp - 1 : state::dp))>;
static constexpr inline bool halt = next_state::ip >= code::size;
using next_memory = Set<memory, state::dp, cur_data + cur_dlt>::value;
using next_console =
std::conditional_t<cur_inst == '.',
typename Append<console, cur_data>::value, console>;
using next_input =
std::conditional_t<cur_inst == ',', typename DropFirst<input>::value,
input>;
using final_vm = VM<code, next_memory, next_console, next_input, next_state,
std::conditional_t<halt, std::true_type, void>>::final_vm;
};
template <Array_t _code, Array_t _memory, Array_t _console, Array_t _input,
State_t _state>
struct VM<_code, _memory, _console, _input, _state, std::true_type> {
using code = _code;
using memory = _memory;
using console = _console;
using input = _input;
using state = _state;
using final_vm = VM<code, memory, console, input, state, std::true_type>;
};
using input_code = Array<
'>', '+', '+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '>', '-', ']', '<', '.', '>', '>', '+', '+', '+',
'+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+', '+', '+', '+', '+',
'+', '+', '+', '+', '>', '-', ']', '<', '+', '.', '>', '>', '+', '+', '+',
'+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+', '+', '+', '+', '+',
'+', '+', '+', '+', '>', '-', ']', '<', '+', '+', '+', '+', '+', '+', '+',
'+', '.', '.', '>', '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'[', '<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '>', '-', ']',
'<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '.', '>', '>',
'+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+',
'+', '+', '>', '-', ']', '<', '.', '>', '>', '+', '+', '+', '+', '[', '<',
'+', '+', '+', '+', '+', '+', '+', '+', '>', '-', ']', '<', '.', '>', '>',
'+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+',
'+', '+', '+', '+', '+', '+', '>', '-', ']', '<', '-', '.', '>', '>', '+',
'+', '+', '+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '+', '>', '-', ']', '<', '+', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '+', '.', '>', '>', '+', '+', '+', '+', '+', '+',
'[', '<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '+', '>', '-', ']', '<', '.', '>', '>', '+', '+',
'+', '+', '+', '+', '+', '+', '+', '+', '[', '<', '+', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '>', '-', ']', '<', '+', '+', '+', '+', '+', '+',
'+', '+', '.', '>', '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'[', '<', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '>', '-', ']',
'<', '.', '>', '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
'[', '<', '+', '+', '+', '>', '-', ']', '<', '.'>;
using work_mem = SetupArray<64>::value;
template <typename T> __attribute__((noinline)) void emit_code() {
__asm__("nop");
}
template <Array_t arr> void output() {
if constexpr (!arr::size)
return;
else
putchar(GetFirst<arr>::value), output<typename DropFirst<arr>::value>();
}
int main() {
using result =
VM<input_code, work_mem, Array<>, Array<>, State<0, 0>>::final_vm;
output<result::console>(), puts("");
// std::string qwq, ans;
// std::cin >> qwq;
// for (char ch : qwq)
// std::cout << "'" << ch << "',";
}编译命令：-std=c++23 -Ofast -ftemplate-depth=10000000
经过了足足 $26.053s$ 后，我们得到了可执行文件。
$ ./my_compile_time_bf
Hello, World!