30.06.2021 14:19
Hirrolot 0 2500 Источник


>> Осторожно, модерн! — Начальник


Предисловие


В предыдущем опусе сквозь человеческие и зверинные кости явилось устройство для обобщённой макрорекурсии в стиле передачи продолжений. Беда в том, что эта концептуально изящная конструкция не приспособлена под реальность; изуродование препроцессора повлекло за собой изуродование мысли инженера: теперь творцу приходится выражаться в так называемом "перевёрнутом" стиле потока исполнения.


Сегодня речь пойдёт о метаязыке Metalang99 — это надстройка над CPS-двигателем макрорекурсии с привычным потоком исполнения. Его суть — мимикрировать под метаязык стандартного препроцессора Си, но в то же время разрешать обобщённую рекурсию — то, чего так не хватало в написании хоть сколько-то нетривиальных мета-алгоритмов.


Опусография



Содержание


  • Садизм 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]


Показать малыша 

#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?", "Почему не сторонние кодогенераторы", и т.д.).

Комментарии (0)