[Ненормальное программирование, Программирование, Совершенный код, C++, C] Металингвистический совратитель Си. Опус III: Садистская машина
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
>> Осторожно, модерн! — Начальник
Предисловие
В предыдущем опусе сквозь человеческие и зверинные кости явилось устройство для обобщённой макрорекурсии в стиле передачи продолжений. Беда в том, что эта концептуально изящная конструкция не приспособлена под реальность; изуродование препроцессора повлекло за собой изуродование мысли инженера: теперь творцу приходится выражаться в так называемом "перевёрнутом" стиле потока исполнения.
Сегодня речь пойдёт о метаязыке 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 интерпретатора:
[eval/eval.h]
Показать малыша
SPL
#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: Примеры работы
Обход двоичного дерева во время компиляции
[examples/binary_tree.c]
#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) {}
Функция Аккермана
[examples/ackermann.c]
#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?", "Почему не сторонние кодогенераторы", и т.д.).
===========
Источник:
habr.com
===========
Похожие новости:
- [Веб-дизайн, Интерфейсы, Usability, Графический дизайн] Руководство по цвету в UX/UI-дизайне (перевод)
- [Java] Реактивное программирование со Spring (перевод)
- [Java] Реактивное программирование со Spring, часть 4 R2DBC (перевод)
- [Разработка игр, Unity, Игры и игровые приставки] Менеджер качества, или как не спалить лоу-энд девайсы ультра-графикой
- [Java] Реактивное программирование со Spring, часть 3 WebFlux (перевод)
- [Развитие стартапа, Разработка под AR и VR, Медгаджеты, Мозг, Биология] Нереализованные стартапы — проект АЭЛИТА
- [Информационная безопасность, Браузеры] Пора запретить рекламу, основанную на слежке (перевод)
- [Java] Реактивное программирование со Spring, часть 2 Project Reactor (перевод)
- [Информационная безопасность, Криптография, Серверное администрирование] Инфраструктурой российского DoubleVPN завладели зарубежные спецслужбы
- [IT-инфраструктура, Облачные вычисления] Гибридная ИТ-инфраструктура: как прикрутить облака к реальности?
Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_programmirovanie (Программирование), #_sovershennyj_kod (Совершенный код), #_c++, #_c, #_si (си), #_c99, #_c11, #_c++, #_metaprogrammirovanie (метапрограммирование), #_makrosy (макросы), #_preprotsessor (препроцессор), #_jazyk_programmirovanija_si (язык программирования си), #_kompjuternaja_lingvistika (компьютерная лингвистика), #_metajazyk (метаязык), #_kodogeneratsija (кодогенерация), #_metasintaksis (метасинтаксис), #_shablony_c++ (шаблоны c++), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_programmirovanie (
Программирование
), #_sovershennyj_kod (
Совершенный код
), #_c++, #_c
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 13:50
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 >> Осторожно, модерн! — Начальник Предисловие В предыдущем опусе сквозь человеческие и зверинные кости явилось устройство для обобщённой макрорекурсии в стиле передачи продолжений. Беда в том, что эта концептуально изящная конструкция не приспособлена под реальность; изуродование препроцессора повлекло за собой изуродование мысли инженера: теперь творцу приходится выражаться в так называемом "перевёрнутом" стиле потока исполнения. Сегодня речь пойдёт о метаязыке Metalang99 — это надстройка над CPS-двигателем макрорекурсии с привычным потоком исполнения. Его суть — мимикрировать под метаязык стандартного препроцессора Си, но в то же время разрешать обобщённую рекурсию — то, чего так не хватало в написании хоть сколько-то нетривиальных мета-алгоритмов. Опусография
Содержание
Садизм 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.
Итак, наша цель — написать интерпретатор на стиле передачи продолжений (CPS), интерпретирующий метапрограммы, которым естественнен прямой поток исполнения, метапрограммы, входящие в наш будущий функциональный язык для метапрограммирования. Только так мы можем обхитрить препроцессор и скомпилировать то, что по логике нельзя. В следующей секции данный метаязык мы определяем формально: и его синтаксис, и его семантику. Садизм III: Синтаксис и садистская машина Синтаксис языка должен отражать то, что мы хотим в итоге получить. Мы хотим обрабатывать вызовы, возможно рекурсивные. Абстрактная машина предписывает правила, по которым синтаксические элементы редуцируются в конечный результат. Не вижу смысла заново расписывать тут всё то, что предписано в спецификации Metalang99. Прочитали — перейдём к реализации. Садизм IV: Реализация Теперь самая мякотка! Глянем на исходный код CPS-style интерпретатора: [eval/eval.h] Показать малышаSPL#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:
Элегантная концепция — 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: Примеры работы Обход двоичного дерева во время компиляции [examples/binary_tree.c] #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) {} Функция Аккермана [examples/ackermann.c] #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?", "Почему не сторонние кодогенераторы", и т.д.). =========== Источник: habr.com =========== Похожие новости:
Ненормальное программирование ), #_programmirovanie ( Программирование ), #_sovershennyj_kod ( Совершенный код ), #_c++, #_c |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 13:50
Часовой пояс: UTC + 5