>> Осторожно, модерн! — Начальник
Предисловие
В предыдущем опусе сквозь человеческие и зверинные кости явилось устройство для обобщённой макрорекурсии в стиле передачи продолжений. Беда в том, что эта концептуально изящная конструкция не приспособлена под реальность; изуродование препроцессора повлекло за собой изуродование мысли инженера: теперь творцу приходится выражаться в так называемом "перевёрнутом" стиле потока исполнения.
Сегодня речь пойдёт о метаязыке Metalang99 — это надстройка над CPS-двигателем макрорекурсии с привычным потоком исполнения. Его суть — мимикрировать под метаязык стандартного препроцессора Си, но в то же время разрешать обобщённую рекурсию — то, чего так не хватало в написании хоть сколько-то нетривиальных мета-алгоритмов.
Опусография
- Опус I: Предварительные ласки
- Опус II: Рекуррентный экстаз
- Опус III: Садистская машина
Содержание
- Садизм I: Переосмысление двигателя рекурсии
- Садизм II: Прозрение
- Садизм III: Синтаксис и садистская машина
- Садизм IV: Реализация
- Садизм V: Примеры работы
Садизм I: Переосмысление двигателя рекурсии
CPS двигатель рекурсии, представленный в предыдущем опусе, избыточен: мы переопределяли одни и те же макросы по многу раз, что вылилось в чрезмерную сложность реализации и разбухание исходного кода Metalang99. Новая реализация элегантна; она лишена недостатков предыдушей, и, более того, сделана переиспользуемой: вместо того, чтобы увеличивать максимальную глубину рекурсии посредством добавления новых макросов, мы можем одним ML99_PRIV_REC_EXPAND(...)
увеличить её на 1024 шага! Об этом — в настоящей секции.
Начнём сначала. Единственный способ заполучить механизм для рекурсии фиксированной глубины в препроцессоре C/C++ (а этот подвид — самый обобщённый из всех возможных видов рекурсий, поддающихся выражению на языке макросов) — это выразить данный механизм на CPS, подвиде потока исполнения программы, в котором продолжения материализуется в совершенно первоклассную лингвистическую абстракцию — функцию, и передаются друг посредством друга, чтобы продолжить исполнение программы на данном месте (считать — перепрыгнуть в следующую отметку исполнения). Так как мы работаем с макросистемой C/C++, то аналог функций — макрос, этой абстракцией мы и будем пользоваться. Мы будем передавать идентификатор первого рекурсивного макроса в следующий рекурсивный макрос, и тот, в свою очередь, по мере завершения своего исполнения будет передавать поток исполнения в первый рекурсивный макрос, так называемое продолжение. Нам также понадобиться терминальное продолжение — ML99_PRIV_REC_STOP
— оно будет являться продолжением, поставляющимся в самый-самый первый рекурсивный макрос, ведь логично, что никуда, кроме как закончить исполнение программы на данном месте, нам перепрыгивать не нужно. Жилка двигателя рекурсии — это цепочка из макросов-раскрывателей следующего вида:
#define ML99_PRIV_REC_0(choice, ...) ML99_PRIV_REC_NEXT(1, choice)(__VA_ARGS__) #define ML99_PRIV_REC_1(choice, ...) ML99_PRIV_REC_NEXT(2, choice)(__VA_ARGS__) #define ML99_PRIV_REC_2(choice, ...) ML99_PRIV_REC_NEXT(3, choice)(__VA_ARGS__) #define ML99_PRIV_REC_3(choice, ...) ML99_PRIV_REC_NEXT(4, choice)(__VA_ARGS__) #define ML99_PRIV_REC_4(choice, ...) ML99_PRIV_REC_NEXT(5, choice)(__VA_ARGS__) #define ML99_PRIV_REC_5(choice, ...) ML99_PRIV_REC_NEXT(6, choice)(__VA_ARGS__) #define ML99_PRIV_REC_6(choice, ...) ML99_PRIV_REC_NEXT(7, choice)(__VA_ARGS__) #define ML99_PRIV_REC_7(choice, ...) ML99_PRIV_REC_NEXT(8, choice)(__VA_ARGS__) #define ML99_PRIV_REC_8(choice, ...) ML99_PRIV_REC_NEXT(9, choice)(__VA_ARGS__) #define ML99_PRIV_REC_9(choice, ...) ML99_PRIV_REC_NEXT(10, choice)(__VA_ARGS__) ...
И так до 1023:
#define ML99_PRIV_REC_1023 ML99_PRIV_REC_DEFER(ML99_PRIV_REC_0_HOOK)() #define ML99_PRIV_REC_0_HOOK() ML99_PRIV_REC_0
И тут происходит следующее: мы откладываем раскрытие ML99_PRIV_REC_0
на ровно одно препроцессорное раскрытие (ведь иначе ML99_PRIV_REC_0
автоматически заблокируется препроцессором), и в конце всей этой цепочки, если только она не прервалась где-то раньше вследствие завершения исполнения метапрограммы, в конце этой всей цепочки мы получаем что-то вроде ML99_PRIV_REC_0(...)
, где ...
— оставшаяся часть метапрограммы — то бишь мы получаем ровно то, что специфицировали в начале, но уже с редуцированной частью входа:
#define ML99_PRIV_REC_UNROLL(...) ML99_PRIV_REC_UNROLL_AUX(__VA_ARGS__) #define ML99_PRIV_REC_UNROLL_AUX(choice, ...) \ /* Approximately 1024 * 16 reduction steps. */ \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_EXPAND( \ ML99_PRIV_REC_NEXT(0, choice)(__VA_ARGS__) \ ))))))))))))))))
Я говорю о ML99_PRIV_REC_NEXT(0, choice)(__VA_ARGS__)
. Тут мы можем наблюдать цепочку ML99_PRIV_REC_EXPAND
, как я пояснил ранее, и она превосходно сочетается с тем ML99_PRIV_REC_DEFER
, который мы указали в самом начале: ML99_PRIV_REC_DEFER
откладывает раскрытие, чтобы вся предыдущая цепочка макросов-раскрывателей не заблокировалась препроцессором, а ML99_PRIV_REC_EXPAND
находится ровно в том месте, где такая блокировка невозможна по определению: ML99_PRIV_REC_UNROLL_AUX
не является вызванным данной цепочкой раскрывателей, а наоборот — он вызывает цепочку раскрывателей. Мы изворачиваем цепочку кишками наружу и издеваемся над ней столько, сколько нам захочется — а именно 16 раз по 1024 раскрытия (2^14).
Последнее, что заслуживает внимания в самом двигателе — так это макрос ML99_PRIV_REC_NEXT
:
#define ML99_PRIV_REC_NEXT(next_lvl, choice) ML99_PRIV_REC_NEXT_##choice(next_lvl) #define ML99_PRIV_REC_NEXT_0continue(next_lvl) ML99_PRIV_REC_##next_lvl #define ML99_PRIV_REC_NEXT_0stop(_next_lvl) ML99_PRIV_REC_HALT #define ML99_PRIV_REC_HALT(...) __VA_ARGS__
Каждый макрос-раскрыватель принимает формальный параметр choice
, который или 0continue
, или 0stop
(управляющие рекурсией макросы для использования в пользовательском коде):
#define ML99_PRIV_REC_CONTINUE(k) 0continue, ML99_PRIV_REC_DEFER(k##_HOOK)() #define ML99_PRIV_REC_STOP(_k_cx, ...) 0stop, __VA_ARGS__ #define ML99_PRIV_REC_STOP_HOOK() ML99_PRIV_REC_STOP
Этот choice
сопоставляется с образом в привычной манере: если он 0continue
, то переходим к следующему в цепочке макросу-раскрывателю, а если 0stop
, значит было вызвано терминальное продолжение ML99_PRIV_REC_STOP
—тогда просто раскрываемся в то, что осталось (ML99_PRIV_REC_HALT
). Заметьте, что все неиспользуемые ML99_PRIV_REC_EXPAND
не влияют на результат, ведь мы всё равно всё раскрыли — они скорее выступают за ID-функции.
Дабы не быть голословным, вот пример использования:
#define F(acc, i) ML99_PRIV_IF(ML99_PRIV_NAT_EQ(i, 10), F_DONE, F_PROGRESS)(acc, i) #define F_DONE(acc, _i) ML99_PRIV_REC_CONTINUE(ML99_PRIV_REC_STOP)(~, acc) #define F_PROGRESS(acc, i) ML99_PRIV_REC_CONTINUE(F)(acc##X, ML99_PRIV_INC(i)) #define F_HOOK() F #define XXXXXXXXXX 678 ML99_ASSERT_UNEVAL(ML99_PRIV_REC_UNROLL(F(, 0)) == 678);
Данный код конкатенирует X
ровно 10 раз, и в конечном итоге получается 678
. Макросы ML99_PRIV_NAT_EQ
и ML99_PRIV_INC
обладают говорящими за себя именами: первый сравнивает два натуральных числа, второй инкрементирует.
Садизм II: Прозрение
Писать в стиле передачи продолжений — козлёночком стать. Нам нужно компилировать прямой поток исполнения в перевёрнутый. Как это сделать, если макрос не позволяют расширяться в другие макросы? Тут нам помогут три знаменитые проекции Футамуры, тесно связанные с частичными вычислениями; а именно, мы воспользуемся первой проекцией:
Specializing an interpreter for given source code, yielding an executable.
В данном определении три существенных понятия: interpreter, source code и executable:
- Interpreter — это нечто, что интерпретирует прямой поток исполнения. Более того, интерпретатор должен быть написан на CPS (об этом в следующих пунктах).
- Source code — это последовательность термов в прямом потоке исполнения.
- Executable — это то, что мы получим, если специализируем interpreter на source code. Поэтому интерпретатор должен быть написан на CPS.
Итак, наша цель — написать интерпретатор на стиле передачи продолжений (CPS), интерпретирующий метапрограммы, которым естественнен прямой поток исполнения, метапрограммы, входящие в наш будущий функциональный язык для метапрограммирования. Только так мы можем обхитрить препроцессор и скомпилировать то, что по логике нельзя. В следующей секции данный метаязык мы определяем формально: и его синтаксис, и его семантику.
Садизм III: Синтаксис и садистская машина
Синтаксис языка должен отражать то, что мы хотим в итоге получить. Мы хотим обрабатывать вызовы, возможно рекурсивные. Абстрактная машина предписывает правила, по которым синтаксические элементы редуцируются в конечный результат. Не вижу смысла заново расписывать тут всё то, что предписано в спецификации Metalang99. Прочитали — перейдём к реализации.
Садизм IV: Реализация
Теперь самая мякотка! Глянем на исходный код CPS-style интерпретатора:
#include <metalang99/priv/util.h> #include <metalang99/eval/acc.h> #include <metalang99/eval/rec.h> #include <metalang99/eval/syntax_checker.h> #include <metalang99/eval/term.h> #define ML99_PRIV_EVAL(...) \ ML99_PRIV_REC_UNROLL(ML99_PRIV_EVAL_MATCH( \ ML99_PRIV_REC_STOP, \ (~), \ 0fspace, \ ML99_PRIV_EVAL_ACC, \ __VA_ARGS__, \ (0end, ~), \ ~)) // Recursion hooks { #define ML99_PRIV_EVAL_MATCH_HOOK() ML99_PRIV_EVAL_MATCH #define ML99_PRIV_EVAL_0v_K_HOOK() ML99_PRIV_EVAL_0v_K #define ML99_PRIV_EVAL_0args_K_HOOK() ML99_PRIV_EVAL_0args_K #define ML99_PRIV_EVAL_0op_K_HOOK() ML99_PRIV_EVAL_0op_K #define ML99_PRIV_EVAL_0callUneval_K_HOOK() ML99_PRIV_EVAL_0callUneval_K // } #define ML99_PRIV_EVAL_MATCH(k, k_cx, folder, acc, head, ...) ML99_PRIV_CHECK_TERM(head, ML99_PRIV_TERM_MATCH) \ (head, ML99_PRIV_EVAL_)(k, k_cx, folder, acc, (__VA_ARGS__), ML99_PRIV_EVAL_TERM_DATA head) // Reduction rules { #define ML99_PRIV_EVAL_0v ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_0v_K) #define ML99_PRIV_EVAL_0args ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_0args_K) #define ML99_PRIV_EVAL_0op ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_0op_K) #define ML99_PRIV_EVAL_0callUneval ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_0callUneval_K) #define ML99_PRIV_EVAL_0fatal(...) ML99_PRIV_EVAL_0fatal_AUX(__VA_ARGS__) #define ML99_PRIV_EVAL_0fatal_AUX(_k, _k_cx, _folder, _acc, _tail, f, message) \ ML99_PRIV_REC_CONTINUE(ML99_PRIV_REC_STOP)((~), !"Metalang99 error" (f): message) #define ML99_PRIV_EVAL_0abort(_k, k_cx, folder, acc, _tail, ...) \ ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_MATCH) \ (ML99_PRIV_REC_STOP, (~), 0fspace, ML99_PRIV_EVAL_ACC, __VA_ARGS__, (0end, ~), ~) #define ML99_PRIV_EVAL_0end(k, k_cx, _folder, acc, _tail, _) \ ML99_PRIV_REC_CONTINUE(k) \ (ML99_PRIV_EXPAND k_cx, ML99_PRIV_EVAL_ACC_UNWRAP acc) // } (Reduction rules) // Continuations { #define ML99_PRIV_EVAL_0v_K(k, k_cx, folder, acc, tail, ...) \ ML99_PRIV_MACHINE_REDUCE( \ k, \ k_cx, \ folder, \ ML99_PRIV_EVAL_##folder(acc, __VA_ARGS__), \ ML99_PRIV_EXPAND tail) #define ML99_PRIV_EVAL_0args_K(k, k_cx, folder, acc, tail, op, ...) \ ML99_PRIV_MACHINE_REDUCE( \ ML99_PRIV_EVAL_0callUneval_K, \ (k, k_cx, folder, acc, tail, op), \ 0fcomma, \ ML99_PRIV_EVAL_ACC_COMMA_SEP, \ __VA_ARGS__, \ (0end, ~), \ ~) #define ML99_PRIV_EVAL_0op_K(k, k_cx, folder, acc, tail, op, ...) \ ML99_PRIV_MACHINE_REDUCE( \ ML99_PRIV_EVAL_0callUneval_K, \ (k, k_cx, folder, acc, tail), \ 0fcomma, \ ML99_PRIV_EVAL_ACC_COMMA_SEP, \ op, \ __VA_ARGS__, \ (0end, ~), \ ~) #define ML99_PRIV_EVAL_0callUneval_K(k, k_cx, folder, acc, tail, evaluated_op, ...) \ /* If the metafunction `evaluated_op` expands to many terms, we first evaluate these terms and \ * accumulate them, otherwise, we just paste the single term with the rest of the tail. This \ * optimisation results in a huge performance improvement. */ \ ML99_PRIV_IF( \ ML99_PRIV_CONTAINS_COMMA(evaluated_op##_IMPL(__VA_ARGS__)), \ ML99_PRIV_EVAL_0callUneval_K_REGULAR, \ ML99_PRIV_EVAL_0callUneval_K_OPTIMIZED) \ (k, k_cx, folder, acc, tail, evaluated_op##_IMPL(__VA_ARGS__)) #define ML99_PRIV_EVAL_0callUneval_K_OPTIMIZED(k, k_cx, folder, acc, tail, body) \ ML99_PRIV_MACHINE_REDUCE(k, k_cx, folder, acc, body, ML99_PRIV_EXPAND tail) #define ML99_PRIV_EVAL_0callUneval_K_REGULAR(k, k_cx, folder, acc, tail, ...) \ ML99_PRIV_MACHINE_REDUCE( \ ML99_PRIV_EVAL_0v_K, \ (k, k_cx, folder, acc, tail), \ 0fspace, \ ML99_PRIV_EVAL_ACC, \ __VA_ARGS__, \ (0end, ~), \ ~) #define ML99_PRIV_MACHINE_REDUCE(...) ML99_PRIV_EVAL_MATCH(__VA_ARGS__) // } (Continuations)
Он почти 1-в-1 отображает редукционную семантику, описанную в спецификации, за исключением лишь одной оптимизации. Как вы можете наблюдать, мы параметризируем внутренние функции интерпретатора (ВФИ) по k, k_cx, folder, acc, tail
:
k
— следующее продолжение.k_cx
— среда захвата следующего продолжения.folder
— макрос для левой свёртки редуцированного терма вместе с остальными редуцированными термами.acc
— аккумулятор, остальные редуцированные термы.tail
— оставшиеся термы для редукции.
Элегантная концепция — folder
. Она позволяет абстрагироваться от comma-separated и whitespace-separated термов: если мы хотим первое, мы указываем 0fspace
, если второе — 0fcomma
(они впоследствии склеиваются с ML99_PRIV_EVAL
и получаются обычные макросы):
#define ML99_PRIV_EVAL_ACC (, ) #define ML99_PRIV_EVAL_ACC_COMMA_SEP () #define ML99_PRIV_EVAL_0fspace(acc, ...) (ML99_PRIV_EXPAND acc __VA_ARGS__) #define ML99_PRIV_EVAL_0fcomma(acc, ...) (ML99_PRIV_EXPAND acc, __VA_ARGS__) #define ML99_PRIV_EVAL_ACC_UNWRAP(_emptiness, ...) __VA_ARGS__
Жила интерпретатора — опять же, сопоставление с образом. На вход подаётся терм, который сопоставляется с образом на несколько ВФИ, обрабатывающих соответствующий тип терма: ML99_PRIV_EVAL_0fatal
, ML99_PRIV_EVAL_0abort
, ML99_PRIV_EVAL_0v
, ML99_PRIV_EVAL_0args
, ML99_PRIV_EVAL_0op
, ML99_PRIV_EVAL_0callUneval
и ML99_PRIV_EVAL_0end
. Последний — это "искусственый" терм, добавляющийся в последовательность настоящих пользовательских термов, чтобы обнаружить конец данной последовательности. Как правило, каждая такая ВФИ раскрывается в ML99_PRIV_MACHINE_REDUCE
:
#define ML99_PRIV_MACHINE_REDUCE(...) ML99_PRIV_EVAL_MATCH(__VA_ARGS__)
Т.е. выполняет один шаг редукции. Заметьте, что если бы мы просто так вызвали ML99_PRIV_MACHINE_REDUCE
, то ML99_PRIV_EVAL_MATCH
бы просто заблокировался как рекурсивный вызов. Вместо этого, мы материализуем каждую ВФИ в продолжение! Таким образом, ВФИ формируют правильную рекурсию и каждая ВФИ сопоставляется ровно с одним шагом редукции. Пример с v(...)
(нормальной формы терма):
#define ML99_PRIV_EVAL_0v_K_HOOK() ML99_PRIV_EVAL_0v_K ... #define ML99_PRIV_EVAL_0v ML99_PRIV_REC_CONTINUE(ML99_PRIV_EVAL_0v_K) ... #define ML99_PRIV_EVAL_0v_K(k, k_cx, folder, acc, tail, ...) \ ML99_PRIV_MACHINE_REDUCE( \ k, \ k_cx, \ folder, \ ML99_PRIV_EVAL_##folder(acc, __VA_ARGS__), \ ML99_PRIV_EXPAND tail)
Сама функция сопоставления ML99_PRIV_EVAL_MATCH
вызывает ML99_PRIV_EVAL_0v
, которая раскрывается в собственное продолжение, которое вызывается и редуцирует терм, и так по циклу. Интерпретатор на CPS — как и было сказано ранее.
Стоит отметить, что ML99_PRIV_EVAL_MATCH
каждый раз совершают false negative проверку на синтаксическое соответствие:
#define ML99_PRIV_EVAL_MATCH(k, k_cx, folder, acc, head, ...) \ ML99_PRIV_CHECK_TERM(head, ML99_PRIV_TERM_MATCH) \ (head, ML99_PRIV_EVAL_)(k, k_cx, folder, acc, (__VA_ARGS__), ML99_PRIV_EVAL_TERM_DATA head)
Так как термы раскрываются в нечто (kind, ...)
:
#define ML99_call(op, ...) (ML99_PRIV_IF(ML99_PRIV_IS_UNTUPLE(op), 0args, 0op), op, __VA_ARGS__) #define ML99_callUneval(ident, ...) (0callUneval, ident, __VA_ARGS__) #define v(...) (0v, __VA_ARGS__) #define ML99_fatal(f, ...) (0fatal, f, #__VA_ARGS__) #define ML99_abort(...) (0abort, __VA_ARGS__)
То этому ML99_PRIV_CHECK_TERM
остаётся лишь проверить данную форму:
#define ML99_PRIV_CHECK_TERM(term, default) \ ML99_PRIV_IF(ML99_PRIV_IS_UNTUPLE(term), ML99_PRIV_SYNTAX_CHECKER_EMIT_ERROR, default) #define ML99_PRIV_SYNTAX_CHECKER_EMIT_ERROR(term, ...) \ ML99_PRIV_SYNTAX_ERROR(term) \ /* Consume arguments passed to ML99_PRIV_TERM_MATCH, see eval.h. */ ML99_PRIV_EMPTY #define ML99_PRIV_SYNTAX_ERROR(invalid_term) \ ML99_PRIV_REC_CONTINUE(ML99_PRIV_REC_STOP)((~), !"Metalang99 syntax error": {invalid_term})
Это не предотвращает все синтаксические ошибки, но предотвращает многие:
// !"Metalang99 syntax error": {123} ML99_EVAL(123)
Или более продвинутый пример с Datatype99:
// !"Metalang99 error" (ML99_assertIsTuple): "Bar(int) must be (x1, ..., xN)" datatype(A, (Foo, int), Bar(int));
Более того, интерпретатор может прервать исполнение программы по инициативе пользователя, посредством ML99_fatal
или ML99_abort
:
(Пример с ML99_abort
)
#define F_IMPL(x, y, z) v(x + y + z) // abc ML99_EVAL(ML99_call(F, v(1, 2), ML99_abort(v(abc))))
(Пример с ML99_fatal
)
// !"Metalang99 error" (F): "the description of your error" ML99_EVAL(ML99_fatal(F, the description of your error))
(Пример с ML99_fatal
, списки)
// !"Metalang99 error" (ML99_listHead): "expected a non-empty list" ML99_EVAL(ML99_listHead(ML99_nil()))
Более подробно — в главе Testing, debugging, and error reporting пользовательского туториала по Metalang99.
Отлично. Все основные концепции про интерпретатор мы разобрали. Осталось теперь посмотреть на нашего злого пупса в деле.
Садизм V: Примеры работы
Обход двоичного дерева во время компиляции
#include <metalang99.h> #define Leaf(x) ML99_choice(v(Leaf), x) #define Node(lhs, data, rhs) ML99_choice(v(Node), lhs, data, rhs) #define SUM(tree) ML99_match(tree, v(SUM_)) #define SUM_Leaf_IMPL(x) v(x) #define SUM_Node_IMPL(lhs, data, rhs) ML99_add3(SUM(v(lhs)), v(data), SUM(v(rhs))) /* * 4 * / \ * / \ * / \ * 2 6 * / \ / \ * 1 3 5 7 */ #define TREE Node(Node(Leaf(v(1)), v(2), Leaf(v(3))), v(4), Node(Leaf(v(5)), v(6), Leaf(v(7)))) ML99_ASSERT_EQ(SUM(TREE), v(28)); int main(void) {}
Функция Аккермана
#include <metalang99.h> #define ack(m, n) ML99_natMatchWithArgs(m, v(ack_), n) #define ack_Z_IMPL(n) ML99_inc(v(n)) #define ack_S_IMPL(m, n) ML99_natMatchWithArgs(v(n), v(ack_S_), v(m)) #define ack_S_Z_IMPL(m) ack(v(m), v(1)) #define ack_S_S_IMPL(n, m) ack(v(m), ack(ML99_inc(v(m)), v(n))) ML99_ASSERT_EQ(ack(v(0), v(0)), v(1)); ML99_ASSERT_EQ(ack(v(0), v(1)), v(2)); ML99_ASSERT_EQ(ack(v(0), v(2)), v(3)); ML99_ASSERT_EQ(ack(v(1), v(0)), v(2)); ML99_ASSERT_EQ(ack(v(1), v(1)), v(3)); ML99_ASSERT_EQ(ack(v(1), v(2)), v(4)); ML99_ASSERT_EQ(ack(v(2), v(0)), v(3)); ML99_ASSERT_EQ(ack(v(2), v(1)), v(5)); ML99_ASSERT_EQ(ack(v(2), v(2)), v(7)); int main(void) {}
Генерация Duff’s device
(Duff’s device — классический трюк слияния switch
-statement с циклами для автоматической развёртки циклов.)
Нетипизированное лямбда-исчисление
Заключение
Наше путешествие длиною в три опуса подошло к концу. Начинали мы с тривиальных препроцессорных идиом, закончили CPS-style интерпретатором. Данная технология оказалась довольно работоспособной: она дала возможность появиться таким абстракциям, как Datatype99 и Interface99 — алгебраические типы данных и удобная генерация интерфейсов для голого C99. (Рекомендую посмотреть README.md
, в том числе и FAQ всех трёх проектов — там отвечены и такие вопросы, как "Зачем использовать C99?", "Почему не сторонние кодогенераторы", и т.д.).
ссылка на оригинал статьи https://habr.com/ru/post/523688/
Добавить комментарий