В этом разделе будет описано, как отображаются высокоуровневые конструкции Рефала-05 (данные — объектные выражения, рефал-машина, сопоставление с образцом и т.д.) на более низкоуровневые понятия компьютера, выраженные в терминах языка Си.
В первой главе раздела мы рассмотрим списковое представление поля зрения — способ построения данных Рефала в виде двусвязных списков, не опускаясь в технические подробности. Эту главу рекомендуется прочитать всем, поскольку изложенные в ней сведения нужны, чтобы писать эффективные программы для данной реализации. Последующие главы будут необходимы лишь для разработки собственных внешних функций на Си и для доработки самого компилятора.
Во второй главе будут обсуждаться структуры данных поля зрения уже в терминах языка Си, реализация рефал-машины и идеология компиляции функций на Рефале в целевой код. После прочтения этой главы содержимое порождаемых компилятором файлов на Си станет частично понятным. Также в этой главе будут описаны те функции рантайма, которые используются в сгенерированном коде.
Третья глава является уже руководством по написанию функций на Си, которые можно вызывать из Рефала. В ней будет приведён пример написания такой функции, а также будут рассмотрены функции рантайма, предназначенные для использования программистом.
Как было сказано в разделе 2, рассматриваемая реализация действительно моделирует работу рефал-машины. Это значит, что в памяти программы на Рефале представлено каким-то образом поле зрения, которое переписывается по шагам. В разделе 5, в частности, рассказывается, что содержимое поля зрения можно увидеть при аварийной остановке программы, либо на каждом шаге, откомпилировав программу с особыми ключами.
Актуальная реализация представляет поле зрения в виде двусвязного списка —
структуры данных, состоящих из узлов (звеньев), каждое из которых содержит
ссылки (указатели) на следующее звено и предыдущее. Каждое звено такого списка
представляет либо символ (литеру, число или функцию), либо скобку ((, ),
<, >). Узлы-символы хранят значения символов (соответственно, значение
литеры, число или указатель на представление функции), узлы-скобки хранят
указатели на другие узлы-скобки.
Узлы, соответствующие круглым скобкам, хранят указатели на сопряжённые скобки:
открывающая ( содержит указатель на узел, содержащий парную ей ) и наоборот.
Благодаря этому сопоставление выражения с образцом вида (…) … или … (…)
выполняется за константное время. Если образец начинается на круглую скобку,
то следуя по указателю в ней, легко найти парную скобку и затем продолжить
сопоставление частей образца внутри и после скобок.
С угловыми скобками хитрее. Как мы помним из раздела 2, рефал-машина должна находить на каждом шаге очередное первичное активное подвыражение — самую левую пару угловых скобок, не содержащую внутри себя других скобок. Указатели, хранимые в угловых скобках, позволяют находить его за небольшое константное время, избегая полного просмотра поля зрения.
Что значит, найти первичное активное подвыражение? Это значит, что нужно получить указатели на искомые угловые скобки — между ними будет находиться имя функции и её аргумент.
Открывающие угловые скобки, также как и круглые, содержат ссылки на парные
им закрывающие. Это позволяет, найдя левую скобку, сразу зафиксировать парную
ей. Каждая закрывающая угловая скобка содержит указатель на ту открывающую
скобку, которая активируется после текущей. Указатель на левую угловую скобку
первичного активного подвыражения хранится в глобальной переменной рантайма
s_stack_ptr. Последняя правая угловая скобка ссылается на NULL. Таким
образом, скобки активации провязаны в односвязный список. Выглядит это так:
s_stack_ptr ────┐
┌─────────────┼───────────────────────────────────────────────────────┐
│ │ ┌───────────────────────────┐ │ NULL
│ │ ┌──────┼─────────────┐ │ │ ↑
↓ ↓ │ ↓ ↓ │ │ │
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗
║ < ║←→║ F ║←→║ < ║←→║ G ║←→║ > ║←→║ < ║←→║ H ║←→║ < ║←→║ I ║←→║ > ║←→║ > ║←→║ > ║
╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝
│ │ ↑ │ │ ↑ ↑ ↑
│ └─────────────┘ │ └─────────────┘ │ │
│ └──────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────────┘
Первичное активное подвыражение в этом примере <G>, на его левую скобку
указывает глобальная переменная g_stack_ptr, правую угловую скобку
рефал-машина найдёт, если проследует по указателю из левой скобки. При вызове
функции G первичное активное подвыражение будет снято со стека (изъято
из односвязного списка) и переменная s_stack_ptr будет указывать на следующую
пару скобок вызова <I>. Если вызов <G> заменится на пустоту, то поле зрения
приобретёт следующий вид:
s_stack_ptr ──────────────────┐
┌───────────────────────────┼────────────────────┐ NULL
│ ┌─────────────┼─────────────┐ │ ↑
↓ ↓ ↓ │ │ │
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗
║ < ║←→║ F ║←→║ < ║←→║ H ║←→║ < ║←→║ I ║←→║ > ║←→║ > ║←→║ > ║
╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝
│ │ │ ↑ ↑ ↑
│ │ └─────────────┘ │ │
│ └──────────────────────────────────┘ │
└───────────────────────────────────────────────────────┘
Допустим, вызов <I> тоже вычислился в пустоту:
s_stack_ptr ────┐
┌─────────────┼─────────────┐ NULL
↓ ↓ │ ↑
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═╧═╗
║ < ║←→║ F ║←→║ < ║←→║ H ║←→║ > ║←→║ > ║
╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═══╝
│ │ ↑ ↑
│ └─────────────┘ │
└──────────────────────────────────┘
Если вызов функции заменяется на выражение с новыми скобками активации, то они
тоже добавляются в стек. Пусть вызов <H> заменяется на <K> <L>.
s_stack_ptr NULL
↓ ↑
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗
║ < ║←→║ F ║←→║ < ║←→║ K ║←→║ > ║←→║ < ║←→║ L ║←→║ > ║←→║ > ║
╚═╤═╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝
│ ↑
└───────────────────────────────────────────────────────┘
На стек сначала будет положена пара скобок вокруг L, затем, вокруг K:
s_stack_ptr ────┐
┌─────────────┼──────────────────────────────────┐
│ │ ┌──────┐ │ NULL
↓ ↓ │ ↓ │ ↑
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═══╗ ╔═══╗ ╔═╧═╗ ╔═╧═╗
║ < ║←→║ F ║←→║ < ║←→║ K ║←→║ > ║←→║ < ║←→║ L ║←→║ > ║←→║ > ║
╚═╤═╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═╤═╝ ╚═══╝ ╚═══╝ ╚═══╝
│ │ ↑ │ ↑ ↑
│ └─────────────┘ └─────────────┘ │
└───────────────────────────────────────────────────────┘
Таким образом, ссылки в угловых скобках позволяют эффективно находить первичное активное подвыражение в поле зрения.
Когда рефал-машина передаёт управление функции, она получает пару указателей на угловые скобки, ограничивающие первичное активное подвыражение. Функция должна будет выделить из этого выражения аргумент (отбросив скобки вызова и своё имя), последовательно сопоставить аргумент с каждым из образцов, и для первого подошедшего образца построить результат по шаблону в правой части.
Примечание. Из соображений минимализма текущая реализация Рефала-05 выполняет сопоставление аргумента с каждым из образцов независимо — при переходе к следующему забывает о том, какие операции сопоставления в предыдущих образцах уже выполнялись.
Сопоставление с образцом разбивается на последовательность элементарных операций: сопоставления со скобками, символами, переменными. Общий принцип следующий. В процессе сопоставления отслеживается один или несколько диапазонов — ещё не проанализированных участков аргумента и соответствующих им участков образца. Сопоставление начинается с того, что единственным диапазоном объявляется весь аргумент и весь образец. Действия в последующих абзацах повторяются до тех пор, пока не останется ни одного диапазона.
Если есть диапазон, образец которого начинается или заканчивается символом, проверяется, что этот участок аргумента не пустой и начинается или заканчивается тем же символом. Символ вычёркивается из диапазона образца. Сопоставление с символами выполняется за малое константное время.
Иначе, если есть диапазон, который начинается (заканчивается) скобочным термом, проверяется, что аргумент начинается (заканчивается) на круглую скобку, по ссылке находится парная ей скобка, из диапазона удаляется скобочный терм, создаётся новый диапазон, соответствующий содержимому скобок. Сопоставление со скобочным термом выполняется за константное время.
Иначе, если есть диапазон с пустым образцом — проверяется, что участок аргумента тоже пустой. Диапазон удаляется. Сопоставление с пустотой выполняется за константное время.
Иначе, если есть диапазон, который начинается (кончается) на переменную, которая
уже получила своё значение, проверяется, что участок аргумента тоже начинается
(заканчивается) на это же значение. Переменная вычёркивается из диапазона.
Переменные, сопоставляемые в таких случаях, называются повторными.
Сопоставления с s-переменными выполняются за константное время, не зависящее
от значения переменной, поскольку значением может быть либо литера (char),
либо число (long int), либо имя функции (указатель). Сопоставление с t- и
e-переменными выполняются за время, пропорциональное числу узлов в их значениях.
Интересное примечание. Заметим, что значением t- и e-переменной является плоский двусвязный список, поэтому для сравнения на равенство достаточно последовательного просмотра в простом цикле. Рекурсивных вызовов для сравнения содержимого скобок не нужно, а это значит, что глубина вложенности скобок ограничена лишь размером поля зрения. В других реализациях Рефала сравнение на равенство может требовать рекурсию, а значит, и системный стек.
Иначе, если есть диапазон, состоящий из одной e-переменной, ещё не получившей своего значения, переменная связывается с соответствующим участком аргумента. Такая e-переменная называется закрытой. Диапазон удаляется. Сопоставление с закрытой переменной всегда успешно и выполняется за константное время.
Иначе, если есть диапазон, начинающийся (заканчивающийся) на s- или t-переменную, то от участка аргумента отделяется символ или терм и связывается с переменной (переменная здесь ещё не связана, поскольку проверка на повторные переменные выполняется раньше). Переменная вычёркивается из диапазона. Связывание новой s- или t-переменной выполняется за константное время.
Если ни одно из перечисленных условий не выполнилось, то или не осталось
ни одного диапазона, или все диапазоны имеют вид e.X … e.Y, где e-переменные
ещё не получили своего значения. Самая первая несвязанная e-переменная в записи
левой части предложения (она же первая переменная самого левого диапазона)
объявляется открытой. Она последовательно связывается с префиксом участка
аргумента длиной 0, 1, 2… терма и для каждого её значения продолжается
сопоставление с образцом до тех пор, пока не найдётся первое удачное
сопоставление. Иначе говоря, остальная часть образца помещается в цикл по всем
допустимым длинам открытой e-переменной. Переменная вычёркивается из диапазона.
Выбор каждого следующего значения выполняется за константное время (просто
сдвигается указатель на начало следующего терма), но надо понимать, что все
последующие операции выполняются в этом цикле.
Таким образом, если в образце есть одна открытая переменная — время сопоставления со всем образцом будет линейно зависеть от длины (в термах) соответствующего участка аргумента, две открытые переменные дадут квадратичные затраты времени (произведение количества удлинений первой переменной на количество для второй).
Пример. Рассмотрим сопоставление с образцом
(e.Name) e.Values-B ( (e.Name) e.Value ) e.Values-E
1 2 3 4 5 6 7 8 9 10 11
Элементы образца пронумерованы для того, чтобы ссылаться на них в тексте. Перечислим операции сопоставления, которые будут выполняться для этого образца (если о временны́х затратах не говорится, то подразумевается константа).
e.Name (2).e.Values-B … e.Values-E. Переменная e.Values-B (4)
объявляется открытой. Последующие операции выполняются в цикле для всех
возможных длин e.Values-B (числу термов диапазона):
e.Name (7) слева. От диапазона внутри
скобок 6, 8 отделяется префикс, равный значению переменной e.Name (2).
Время сопоставления пропорционально длине совпадающей части известного
значения переменной и диапазона, сверху ограничено длиной e.Name (2)
в узлах списка.e.Name (7) и закрывающей скобкой 8
с пустотой.e.Value (9).e.Values-E (11).Время сопоставления с этим образцом пропорционально произведению длины в узлах
переменной e.Name и длины участка e.Values-B … e.Values-E в термах. Вернее,
ограничено сверху этой величиной.
Пример. Рассмотрим сопоставление с образцом
(e.Set1-B t.Common e.Set1-E) (e.Set2-B t.Common e.Set2-E)
1 2 3 4 5 6 7 8 9 10
Операции сопоставления:
e.Set1-B (2):
t.Common (3), переменная получает значение.e.Set1-E (4).e.Set2-B (7):
t.Common (8). Время сопоставления
пропорционально длине t.Common (3) в узлах списка.e.Set2-E (9).Время сопоставления пропорционально произведению длин (в термах) содержимого
обоих скобочных термов и длины повторной переменной t.Common (в узлах списка).
Важный вывод. Если образец содержит открытые переменные или повторные t- и e-переменные, то время сопоставления с ним зависит от значений этих переменных. В остальных случаях время сопоставления зависит только от вида образца.
Кстати, образцы без открытых переменных и повторных t- и e-переменных в теории метавычислений над Рефалом называются L-выражениями. Для функций, все предложения которых являются L-выражениями, можно определить простую и выразительную систему эквивалентных преобразований (см. например, здесь).
Примечание. Можно придумать реализации, в которых эти операции сопоставления были бы гораздо быстрее. Например, если для всех скобочных термов хранить глобальную хеш-таблицу, и при создании нового терма проверять, есть ли такой же в таблице, то сравнение одноимённых t-переменных будет выполняться за константное время. Если для каждого объектного выражения, которое строится в программе, поддерживать суффиксное дерево, то поиск по открытым переменным также мог быть эффективнее линейного просмотра. Идея использования суффиксных деревьев в Рефале предложена Скоробогатовым С. Ю. [частное сообщение].
В результате успешного сопоставления с образцом переменные предложения
получают свои значения. E-переменные представляются парой указателей на начало
и конец (для пустых переменных они оба равны нулю), s-переменные представляются
указателем на узел, t-переменные — на первое звено значения (символ или левую
круглую скобку). Если переменная входит в образец несколько раз (является
повторной,) то для неё запоминаются все вхождения. Например, если переменная
e.X входила в образец 3 раза, то все её вхождения будут сохранены в трёх
парах указателей.
Построить результат — это значит, построить двусвязный список, на который следует заменить первичное активное подвыражение в поле зрения, и, собственно, выполнить эту замену. При этом, само первичное активное подвыражение уже становится ненужным, а это значит, что оттуда можно взять готовые фрагменты результата. Текущая реализация, однако, берёт оттуда только значения e- и t-переменных (s-переменные дешевле построить заново).
Но в некоторых случаях e- и t-переменные приходится копировать — без копии не обойтись, если в правой части предложения некоторая переменная имеет больше вхождений, чем в левую. Например, для предложения
t.SymTable (e.Name) e.Name =
<Lookup t.SymTable e.Name> '+' <Lookup t.SymTable e.Name>
переменную t.SymTable придётся скопировать, в то время как e.Name — нет.
Копирование t- или e-переменной требует времени, пропорционального длине значения переменной в узлах списка. Для правильного связывания между собой парных круглых скобок в копии дополнительная память не требуется — как стек используются поля связи узлов ещё не спаренных скобок. Псевдокод:
bracket_stack = NULL
for (p ← очередной узел оригинала) {
q = alloc_node();
if (p — открывающая скобка) {
q->tag = открывающая_скобка;
q->link = bracket_stack;
bracket_stack = q;
} else if (p — закрывающая скобка) {
q->tag = закрывающая_скобка;
парная = bracket_stack;
bracket_stack = парная->link;
парная->link = q;
q->link = парная;
q->link = bracket_stack;
} else {
/* p — символ */
скопировать значение p в q;
}
}
Здесь снова должен быть bracket_stack == NULL
Таким образом, копирование, как и сравнение на равенство, не требует рекурсии и вообще не зависит от глубины вложенности скобок. А значит, глубина вложенности ограничена лишь размером поля зрения.
После построения результата функция возвращает выполнение рефал-машине, а та ищет следующее первичное активное подвыражение.
Время выполнения функций, написанных на Си (в частности, встроенных функций) зависит уже от семантики и реализации самой функции.
Как сказано в разделе про реализацию, Рефал-05 содержит встроенный профилировщик, выводящий затраты времени на отдельные операции. Вернёмся к этим метрикам в свете новых знаний.
Total program time — общее время выполнения программы.Builtin time — время выполнения функций, написанных на Си.(Total refal time) — суммарное время выполнения функций, написанных
на Рефале. В сумме с Builtin time должно давать 100 %.Linear pattern time — время сопоставления с образцом до цикла по открытой
переменной и без учёта сопоставления с повторными t- и e-переменными.Linear result time — время построения правой части без учёта времени
копирования t- и e-переменных.Open e-loop time (clear) — время, затраченное на циклы удлинения открытых
переменных без учёта сопоставления повторных t- и e-переменных внутри цикла.Repeated ?-var match time (???? e-loops) — время на сопоставление повторных
t- и e-переменных. Вместо ? записывается литера t или e, вместо ???? —
слово inside или outside. Соответственно, это время выполнения внутри
и вне цикла удлинения открытых e-переменных.t- and e-var copy time — время копирования переменных при построении
правой части.Step count — количество шагов рефал-машины.Memory used — наибольшая длина поля зрения в узлах. Поскольку актуальная
реализация выделенную память не освобождает до завершения программы, то после
достижения пика объём используемой памяти останется равным наибольшему
значению.Бывает. Помимо реализации Рефала на плоских двусвязных списках, есть ещё и представления объектных выражений двусвязными списками с подвешенными скобками (Рефал-6, FLAC), односвязными списками (Рефал-2 Эйсымонта), представление объектных выражений массивами (или векторами) (Рефал Плюс, Рефал-Java) и даже «векторно-списковое» — массивное, но с отложенной конкатенацией, предложенное Скоробогатовым (рукопись, нигде не опубликовано).
Все эти реализации отличаются затратами времени на базовые операции.
Списковое представление с подвешенными скобками отличается тем, что в нём каждый узел списка соответствует не знаку записи объектного выражения (символ или одна из двух скобок), а целому терму. Узел скобочного терма содержит указатель на список узлов, соответствующий содержимому скобок. Выражения, представленные таким образом, копируются дешевле — не нужно создавать полную копию содержимого скобок, достаточно создать новый узел, содержащий указатель на тот же подсписок. Недостаток — гораздо менее очевидно, когда значение переменной копируется, а когда — переносится.
Односвязные списки в реализации Эйсымонта эффективнее расходуют память, узлы
содержат не два указателя, а только один. Это было актуально на старых ЭВМ
с небольшой памятью, может быть актуально и сейчас, поскольку такие программы
могут эффективнее использовать кэш. Недостаток заключается в том, что
сопоставление справа-налево выполняется не за константное, а за линейное время.
Т.е. для образца вида e.X s.Y придётся просмотреть весь аргумент в поисках
последнего звена, чтобы его связать с s.Y, а весь предшествующий участок —
с e.X. В остальном временны́е затраты похожи на представление с подвешенными
скобками.
Массивовое представление облегчает копирование переменных — e-переменная представляется парой индексов на начало и конец массива, t-переменная — индексом самого элемента. Недостаток — затраты времени на конкатенацию. При выполнении предложения
(e.X) (e.Y) = e.X e.Y;
потребуется выделить новый участок массива длиной, равной сумме длин переменных
e.X и e.Y и скопировать туда их содержимое. Следующая функция
Fab {
'A' e.Rest = 'B' <Fab e.Rest>;
s.Other e.Rest = s.Other <Fab e.Rest>;
/* пусто */ = /* пусто */;
}
требует в списковой реализации линейного времени, в наивной массивной — квадратичного. Менее наивные реализации могут выделять память с запасом, дабы на следующей итерации не выделять новый кусок, а копировать значения рядом с имеющимся. Например, для того же
(e.X) (e.Y) = e.X e.Y;
если значению e.Y предшествует свободный участок более длинный, чем e.X,
значение e.X может быть скопировано туда. В случае функции Fab такая
стратегия может обеспечить и линейную сложность (но это не гарантируется).
Векторно-списковое представление Скоробогатова откладывает конкатенацию до того момента, когда содержимое скобок (круглых или угловых) не станет полностью пассивным. Функции в таком представлении принимают вектор (массив), но возвращают список фрагментов вектора. Например, для правой части
… = <F <G> 10 <H> 20>;
функции G и H сформируют некоторые списоки фрагментов вектора, которые
к моменту вызова F будут объединены (вместе с константами 10 и 20)
в один сплошной массив. Рассмотренная выше функция Fab в векторно-списковой
реализации однозначно будет иметь линейное время работы.
Также можно представить себе реализации, использующие ropes (раз, два) — в них стоимость копирования и конкатенации будет равна логарифму от длины выражений в термах, либо даже деки с конкатенацией, предложенные Крисом Окасаки (см. его книгу «Чисто функциональные структуры данных», перевод gogabr’а, последняя глава) — для них все операции имеют амортизированное константное время (копирование, конкатенация, сопоставление справа и слева). Но таких реализаций пока не создано, автор надеется когда-нибудь провести такие исследования.
Звено двусвязного списка выглядит так:
enum r05_datatag {
R05_DATATAG_ILLEGAL = 0,
R05_DATATAG_CHAR,
R05_DATATAG_FUNCTION,
R05_DATATAG_NUMBER,
R05_DATATAG_OPEN_BRACKET,
R05_DATATAG_CLOSE_BRACKET,
R05_DATATAG_OPEN_CALL,
R05_DATATAG_CLOSE_CALL,
};
struct r05_node {
struct r05_node *prev;
struct r05_node *next;
enum r05_datatag tag;
union {
char char_;
struct r05_function *function;
r05_number number;
struct r05_node *link;
} info;
};
Структура узла состоит из четырёх полей: две ссылки вперёд (next) и назад
(prev), тип узла (tag) и поле информации (info), которое является
объединением. Актуальное поле объединения зависит от типа. Рассмотрим типы
подробнее.
R05_DATATAG_ILLEGAL означает, что узел не инициализирован никак. Ни одно
из полей info не актуально. Такие узлы могут встречаться в списке свободных
узлов (см. далее), но их не может быть в поле зрения.R05_DATATAG_CHAR — литера, поле info.char_.R05_DATATAG_FUNCTION — указатель на функцию, info.function. Структуру
r05_function мы рассмотрим ниже.R05_DATATAG_NUMBER — число, info.number.R05_DATATAG_OPEN_BRACKET, R05_DATATAG_CLOSE_BRACKET,
R05_DATATAG_OPEN_CALL, R05_DATATAG_CLOSE_CALL — соответственно, это
(, ), <, >, актуальное поле info.link. О том, как оно используется,
подробно написано выше.Описатель функции — это структура, содержащая указатель на функцию и её имя:
struct r05_function {
r05_function_ptr ptr;
const char *name;
};
Значение числа — целое, беззнаковое, 32-разрядное:
typedef unsigned int r05_number;
(На платформах, где unsigned int не 32-разрядный, компилятор не соберётся.)
Функция принимает первичное активное подвыражение — указатели на открывающую и закрывающую скобки вызова функции, функция ничего не возвращает.
typedef void (*r05_function_ptr) (
struct r05_node *begin, struct r05_node *end
);
Подробнее о функциях — в следующем параграфе.
В памяти программы на Рефале-05 присутствует три глобальных связанных списка.
Первый — это уже известное нам поле зрения, второй — список свободных узлов,
третий — копилка. Содержимое копилки находится в рантайме (refal05rts.c),
а не в библиотеке встроенных функций (Library.c) только для того, чтобы
отображать его в аварийном дампе.
Поле зрения ограничено двумя глобальными (статическими) переменными
static struct r05_node s_begin_view_field;
static struct r05_node s_end_view_field;
Список свободных узлов также ограничен переменными
static struct r05_node s_begin_free_list;
static struct r05_node s_end_free_list;
Копилка представлена аналогичным образом:
static struct r05_node s_begin_buried;
static struct r05_node s_end_buried;
Теги этих граничных узлов — R05_DATATAG_ILLEGAL. Узлы списков между этими
границами распределяются в динамической памяти во время выполнения программы.
На вершину стека угловых скобок поля зрения указывает переменная s_stack_ptr:
static struct r05_node *s_stack_ptr;
В списке свободных узлов распределяется память для строящегося результатного выражения, прежде чем попасть в поле зрения. Также, после завершения очередного шага остатки первичного активного подвыражения наоборот переносятся из поля зрения в список свободных узлов.
Новые элементы, как правило, распределяются в списке свободных узлов путём переинициализации старых узлов, если старых узлов не хватает, новые распределяются в динамической памяти, после чего помещаются в этот список.
Для просмотра содержимого списка свободных узлов в дампе нужно установить
макрос препроцессора Си R05_DUMP_FREE_LIST — см. третий раздел.
Наблюдаемые в списке скобки обоих видов обычно не сбалансированы, ссылки
внутри них могут указывать на произвольные узлы поля зрения или списка
свободных узлов. Этот список — строительный материал для порождения новых
узлов поля зрения.
Содержимое копилки имеет вид (e.Key '=' e.Value)*. Для просмотра его
содержимого нужно установить макрос R05_DUMP_BURIED — см. третий раздел.
Исходный файл на Рефале содержит объявления и определения функций и ничего больше. Сгенерированный код на Си имеет следующий вид:
/* Automatically generated file. Don't edit! */
#include "refal05rts.h"
〈объявления всех используемых функций〉
〈определения функций в порядке их следования в исходнике〉
/* End of file */
Файл refal05rts.h содержит определения структур данных поля зрения
и объявления функций, выполняющих элементарные операции сопоставления с левой
частью и построения правой части.
В части объявлений описываются дескрипторы как функций, которые в исходном
файле объявлялись при помощи $EXTERN, так и определённых в исходном файле
функций. Благодаря этому в последующих определениях функций можно ссылаться
на любые функции из текущей области видимости.
В следующей части записываются скомпилированные тела функций в том порядке, в каком они располагались в исходнике.
Каждая функция Рефала-05 компилируется в функцию на языке Си (с сигнатурой
r05_function_ptr) и описатель функции — структуру r05_function. Например,
функция
$ENTRY Extern {
e.Name = '$EXTERN ' e.Name ';\n';
}
будет скомпилирована в
R05_DEFINE_ENTRY_FUNCTION(Extern, "Extern") {
r05_this_is_generated_function();
do {
/* e.Name: 2 */
struct r05_node *p[5] = { 0 };
/* e.Name */
p[0] = arg_begin->next;
p[1] = arg_end;
r05_close_evar(p+2, p[0], p[1]);
r05_reset_allocator();
r05_alloc_chars("$EXTERN ", 8);
r05_alloc_insert_pos(p+4);
r05_alloc_chars(";\n", 2);
r05_correct_evar(p+2);
r05_splice_evar(p[4], p+2);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
}
где макрос R05_DEFINE_ENTRY_FUNCTION(Extern, "Extern") раскроется в
static void r05c_Extern(struct r05_node *arg_begin, struct r05_node *arg_end);
struct r05_function r05f_Extern = { r05c_Extern, "Extern" };
static void r05c_Extern(struct r05_node *arg_begin, struct r05_node *arg_end)
Имя функции на Си и описателя получается из имени исходной функции путём
декорирования — замены в нём всех минусов - на m_, прочерков _ на u_
и добавлением префикса: r05c_ для функций и r05f_ для описателей.
Именами аргументов функции по умолчанию являются arg_begin и arg_end.
Компилируемая функция всегда имеет статическую область видимости, описатель статический для локальных функций и нестатический для entry-функций.
И вообще, описатель первичен.
Очевидно, у всех пустых функций тело будет идентичным. Поэтому для них применена оптимизация — тело функции не генерируется, описатель содержит указатель на их общую реализацию. Так например,
*$EENUM Success, Fails
будет скомпилировано в
R05_DEFINE_ENTRY_ENUM(Success, "Success")
R05_DEFINE_ENTRY_ENUM(Fails, "Fails")
что после раскрытия макросов даст
struct r05_function r05f_Success = { r05_enum_function_code, "Success" };
struct r05_function r05f_Fails = { r05_enum_function_code, "Fails" };
Функция r05_enum_function_code при вызове вызывает ошибку отождествления
(recognition impossible) — всегда завершает выполнение программы с дампом поля
зрения.
Для каждой функции в исходном файле и для каждой используемой внешней функции (включая и встроенные), в начале файла добавляется объявление её дескриптора:
R05_DECLARE_ENTRY_FUNCTION(Mu)
R05_DECLARE_ENTRY_FUNCTION(Div)
R05_DECLARE_ENTRY_FUNCTION(Mod)
R05_DECLARE_ENTRY_FUNCTION(Ord)
R05_DECLARE_ENTRY_FUNCTION(Symb)
R05_DECLARE_ENTRY_FUNCTION(Compare)
R05_DECLARE_ENTRY_FUNCTION(R05_TextFromTree)
R05_DECLARE_ENTRY_FUNCTION(Extern)
R05_DECLARE_ENTRY_FUNCTION(Function)
R05_DECLARE_ENTRY_FUNCTION(Entry)
R05_DECLARE_ENTRY_FUNCTION(Local)
R05_DECLARE_ENTRY_FUNCTION(Sentences)
R05_DECLARE_LOCAL_FUNCTION(TextFromSentence)
R05_DECLARE_ENTRY_FUNCTION(Native)
R05_DECLARE_LOCAL_FUNCTION(FlatLines)
R05_DECLARE_ENTRY_FUNCTION(Symbol)
R05_DECLARE_ENTRY_FUNCTION(Char)
R05_DECLARE_ENTRY_FUNCTION(Number)
R05_DECLARE_ENTRY_FUNCTION(Word)
R05_DECLARE_ENTRY_FUNCTION(Variable)
R05_DECLARE_ENTRY_FUNCTION(Brackets)
R05_DECLARE_ENTRY_FUNCTION(Call)
R05_DECLARE_ENTRY_FUNCTION(TextFromExpr)
R05_DECLARE_LOCAL_FUNCTION(TextFromExpr_Char)
R05_DECLARE_LOCAL_FUNCTION(TextFromTerm)
R05_DECLARE_ENTRY_FUNCTION(EscapeChar)
R05_DECLARE_LOCAL_FUNCTION(EscapeChar_Aux)
R05_DECLARE_LOCAL_FUNCTION(EscapeChar_SwCompare)
R05_DECLARE_LOCAL_FUNCTION(CharFromHex)
Макросы R05_DECLARE_LOCAL_FUNCTION и R05_DECLARE_ENTRY_FUNCTION раскрываются,
соответственно, в
extern struct r05_function r05f_Mu;
...
static struct r05_function r05f_TextFromSentence;
extern struct r05_function r05f_Native;
...
static struct r05_function r05f_CharFromHex;
В отличие от C++, язык Си допускает многократное объявление статических переменных в одном файле, важно только, чтобы инициализатор был только у одной из них.
Символы-функции сравниваются на равенство по значению info.function —
указатели на дескрипторы должны совпадать. Поле ptr дескриптора используется
для вызова функции рефал-машиной, поле name для вывода имени функции функциями
вывода (Prout, Putout) или в дампе поля зрения.
Непустые функции компилируются по следующему шаблону:
R05_DEFINE_*****_FUNCTION(FuncName, "FuncName") {
r05_this_is_generated_function();
do {
…
код предложения 1
…
return;
} while (0);
do {
…
код предложения 2
…
return;
} while (0);
…
r05_recognition_impossible(); /* может отсутствовать */
}
Вызов r05_this_is_generated_function(); добавляется в начало каждой функции,
написанной на Рефале — он позволяет профилировщику отличать функции, написанные
на Рефале, от функций, написанных на Си, и считать время последних отдельно.
Вызов r05_recognition_impossible(); в конце завершает программу с выдачей
сообщения об ошибке отождествления (recognition impossible) и аварийным дампом.
На него передаётся управление, если не было выполнено ни одно из предложений.
Если последнее предложение имеет вид e.VarName = …; то вызов
r05_recognition_impossible(); в конце будет отсутствовать, поскольку в таком
предложении образец не может не сопоставиться (см. выше пример функции
Extern).
Каждое предложение состоит из трёх этапов:
r05_recognition_impossible(), если предложение было последним).
При выполнении первого этапа поле зрения не изменяется.NO MEMORY и аварийным дампом. При построении нового результатного выражения
поле зрения также не меняется, поэтому в дампе будет виден неискажённый
вызов упавшей функции.return;).Таким образом, в случае ошибки отождествления поле зрения и список свободных узлов остаются неизменными. При ошибке распределения памяти поле зрения неизменно, в списке свободных узлов может быть частично создан результат работы функции. Когда поле зрения перестраивается, выполнение функции с выдачей дампа прерваться не может. Такое соглашение упрощает для пользователя отладку программы.
Встроенные функции Рефала-05, написанные на Си, тоже следуют этому соглашению: если они прерывают программу с выдачей ошибки, поле зрения неизменно, когда они перекраивают поле зрения, формируя возвращаемое значение, они прерваться не могут. При написании функций на Си вручную рекомендуется поступать также.
Псевдокод предложения без открытых переменных имеет вид
do {
объявления переменных
/* сопоставление с образцом */
if (! элементарное сопоставление)
continue;
if (! элементарное сопоставление)
continue;
…
r05_reset_allocator();
распределение памяти
сборка результата
return;
} while (0);
Если одно из элементарных сопоставлений не удалось, оператор continue;
передаёт управление на следующую операцию с проверкой постусловия. Поскольку
в условии записан константный 0, выполнение предложения прерывается.
Вызов r05_reset_allocator(); подготавливает список свободных узлов
к распределению памяти (подробности далее) и уведомляет профилировщик,
что сопоставление с образцом закончилось и надо считать время построения
результатного выражения.
Каждая открытая переменная образует вложенный цикл:
do {
объявления переменных
/* сопоставление с образцом */
if (! элементарное сопоставление)
continue;
…
/* цикл по открытой переменной e.X */
e.X ← пустая
r05_start_e_loop();
do {
if (! элементарное сопоставление)
continue;
if (! элементарное сопоставление)
continue;
…
/* цикл по другой открытой переменной e.Y */
e.Y ← пустая
r05_start_e_loop();
do {
if (! элементарное сопоставление)
continue;
…
r05_reset_allocator();
распределение памяти
сборка результата
return;
} while (r05_open_evar_advance(e.Y, её диапазон));
r05_stop_e_loop();
} while(r05_open_evar_advance(e.Y, её диапазон));
r05_stop_e_loop();
} while (0);
В тело цикла по e-переменной помещается весь остаток предложения. Если
последующие сопоставления выполняются успешно, цикл вместе со всем предложением
и всей функцией завершается оператором return;. Если одно из элементарных
сопоставлений не выполнилось, то оператор continue; перебрасывает на проверку
условия цикла, которая содержит вызов r05_open_evar_andvance(…). Эта функция
пытается удлинить e-переменную на один терм. Если удаётся (возвращается истина),
выполняется следующая итерация, иначе — цикл завершается. Если завершился самый
внутренний цикл открытой переменной (в примере e.Y), управление передаётся
на условие внешнего цикла (в примере e.X), которая точно также пытается
удлиниться. Если завершился внешний цикл, то завершается и всё предложение.
Функция r05_start_e_loop(), вызов которой добавляется перед каждым циклом,
уведомляет профилировщик, что линейная часть сопоставления кончилась, и время
сопоставления с повторными переменными нужно считать отдельно.
Вызов r05_stop_e_loop() наоборот, сообщает профилировщику, что цикл
удлинения открытой переменной закончился: если образец, содержащий открытую
переменную не сопоставился, то время выполнения образца следующего предложения
должно будет считаться как линейное.
Будем называть лексемы, составляющие запись образца, элементами образца.
Аргументом функции является объектное выражение, представление которого в виде двусвязного списка описано выше. Аргумент находится между именем функции и закрывающей угловой скобкой.
Сопоставление аргумента с образцом заключается в выделении фрагментов аргумента, соответствующих отдельным элементам образца. Фрагменты, соответствующие элементам, располагаются последовательно и вплотную:
E-переменные, значением которых является пустое выражение, не соответствуют ни одному звену аргумента.
У каждого фрагмента есть начало и конец — указатель на самое левое
и самое правое звено. Можно перечислить все звенья фрагмента, если начать
с левого звена и перемещаться по ссылкам next до тех пор, пока не встретим
правое звено. Если мы сдвинем левый указатель влево (пройдём по ссылке prev)
или правый вправо (по ссылке next), то длина фрагмента увеличится на одно
звено. Если же наоборот — сдвинем левый указатель вправо по ссылке next
или правый влево по ссылке prev, то длина фрагмента сократится на один.
Из этих соображений e-переменные, имеющие пустое значение, представляются
«нахлёстом» — левый указатель указывает на звено, следующее за звеном,
на который указывает правый указатель, иначе говоря, right->next == left или
left->prev == right.
Фрагменты, соответствующие символам, скобкам и s-переменным образца, состоят из одного звена, поэтому для их хранения отводится один указатель (очевидно, одновременно хранящий начало и конец). Фрагменты, соответствующие t- и e-переменным, представляются парой указателей. Если значением t-переменной является символ, то оба указателя будут ссылаться на одно и то же звено, если скобочный терм, то на открывающую и закрывающую скобки.
Для описания алгоритма сопоставления дополним и аргумент, и образец до терма
активации — припишем <Func в начало и > в конец. Такой образец будем
называть расширенным образцом.
Сопоставляемым элементам будем приписывать индексы, причём t- и e-переменные будут получать сразу два последовательных индекса. Индексы будут соответстовать индексам указателей в сгенерированном коде.
Имени функции, предшествующей образцу и аргументу, всегда соответствует индекс 0, закрывающей угловой скобке — индекс 1. Эти два элемента сопоставляются в самом начале. (Открывающая угловая скобка при сопоставлении с образцом роли не играет, поэтому у неё нет индекса.)
Пример:
<Func (e.Name) e.Values-B ((e.Name) e.Value) e.Values-E>
0 1
Участок образца, содержащий несопоставленные элементы, будем называть дыркой, причём дырка может быть и пустой. Дырки будем обозначать как открытые интервалы по индексам конца предшествующего и начала последующего элементов. В начале сопоставления не распознан весь аргумент, ему соответствует дырка (0, 1) (после имени функции и до закрывающей угловой скобки).
Сопоставление с элементом означает обнаружение начала и конца элемента. Если у некоторого элемента соседний элемент уже сопоставлен, то можно сопоставить один из краёв данного элемента.
Жёсткими элементами мы будем называть элементы, сопоставление одного края которых однозначно определяет второй край.
Если при сопоставлении с образцом некоторая переменная получает своё значение, то это вхождение переменной в образец мы будем называть новой переменной. Если к моменту сопоставления переменной она уже имела значение, то такие вхождения мы будем называть повторными переменными.
Если e-переменная ещё не получила своё значение, но однозначно определимы оба её края — ей предшествует и за ней следует сопоставленный элемент - то она сразу получает своё значение. Такие вхождения e-переменных будем называть закрытыми переменными (закрытые переменные всегда e-переменные).
Жёсткими элементами являются символы, скобки, повторные вхождения переменных и новые s- и t-переменные.
Звенья круглых скобок имеют ссылки на парные скобки, поэтому после сопоставления одной из скобок, можно сразу же сопоставить и парную ей.
Если образец допускает неоднозначное сопоставление, то после сопоставления
жёстких элементов и закрытых переменных может появиться одна или несколько
e-переменных, у которых сопоставлен только один край. Например, в расширенном
образце <Func e.X '=' e.Y '+' e.Z> у переменной e.X будет сопоставлено
только начало, а у e.Z — только конец. Самую левую e-переменную, в таком
случае, с сопоставленным началом, будем называть открытой переменной
(открытые переменные тоже всегда e-). Алгоритм сопоставления с образцом
будет перебирать все допустимые значения открытой переменной и для каждого
из них будет выполнять последующие шаги сопоставления. Перебор значений
открытой переменной будем называть циклом по открытой переменной или
циклом по e-переменной.
Заметим, что порядок сопоставления жёстких элементов на результат не влияет, однако, в качестве открытой всегда нужно выбирать самую левую e-переменную с сопоставленным началом.
При сопоставлении с образцом дырки меняются:
Опишем теперь алгоритм сопоставления из актуальной реализации:
Сопоставляется один из жёстких элементов, одна из пустых дырок или закрытых переменных. В актуальной реализации поиск ведётся в следующем порядке:
Генерируется команда сопоставления с данным элементом или пустой дыркой, возврат к началу цикла.
Иначе все дырки начинаются с e-переменных. Самая левая из них становится открытой, для неё генерируется заголовок цикла её удлинения, переменная становится сопоставленной.
В примерах ниже сопоставление с дырками будем обозначать как
(u, v) → X[r, s] (s, v) (сопоставление слева) или (u, v) → (u, r) X[r, s]
(сопоставление справа), где u, v, r, s — индексы, X — сопоставляемый
элемент, который получает индексы r и s. Если для представления элемента
достаточно только одного индекса, то будем записывать X[r]. Здесь (s, v)
или (u, r) — новая дырка. Циклы по открытой переменной будем обозначать как
CYCLE((u, v) → e.X[r, s] (s, v)).
Визуально дырки будем выделять фигурными скобками.
Пример. Рассмотрим тот же пример, что и в предыдущей главе:
<Func {(e.Name) e.Values-B ((e.Name) e.Value) e.Values-E}>
0 1
Изначально сопоставлены элементы 0 и 1, они же образуют единственную дырку.
Первым подлежит сопоставлению открывающая скобка:
(0, 1) → ([2] (2, 3) )[3] (3, 1)
<Func ({e.Name}) {e.Values-B ((e.Name) e.Value) e.Values-E}>
0 2 3 1
Сопоставление с круглыми скобками привело к образованию двух новых дырок.
Далее сопоставляется закрытая переменная e.Name:
(2, 3) → e.Name[4, 5]
<Func ( e.Name ) {e.Values-B ((e.Name) e.Value) e.Values-E}>
0 2 4 5 3 1
Жёсткие элементы, пустые дырки и закрытые переменные отсутствуют, ищем самую
левую переменную с сопоставленным началом. Это e.Values-B — открытая:
CYCLE((3, 1) → e.Values-B[6, 7] (7, 1))
<Func ( e.Name ) e.Values-B {((e.Name) e.Value) e.Values-E}>
0 2 4 5 3 6 7 1
Снова открывающая скобка:
(7, 1) → ([8] (8, 9) )[9] (9, 1)
<Func ( e.Name ) e.Values-B ({(e.Name) e.Value}) {e.Values-E}>
0 2 4 5 3 6 7 8 9 1
Снова открывающая скобка:
(8, 9) → ([10] (10, 11) )[11] (11, 9)
<Func ( e.Name ) e.Values-B ( ( {e.Name}) {e.Value}) {e.Values-E}>
0 2 4 5 3 6 7 8 10 11 9 1
Повторная переменная e.Name:
(10, 11) → e.Name[12, 13 ← 4, 5] (13, 11)
<Func ( e.Name ) e.Values-B ( ( e.Name {}) {e.Value}) {e.Values-E}>
0 2 4 5 3 6 7 8 10 12 13 11 9 1
Между повторным вхождением e.Name и закрывающей скобкой должно быть пусто:
(13, 11) → ε
<Func ( e.Name ) e.Values-B ( ( e.Name ) {e.Value}) {e.Values-E}>
0 2 4 5 3 6 7 8 10 12 13 11 9 1
Две закрытые переменные:
(11, 9) → e.Value[14, 15]
<Func ( e.Name ) e.Values-B ( ( e.Name ) e.Value ) {e.Values-E}>
0 2 4 5 3 6 7 8 10 12 13 11 14 15 9 1
(9, 1) → e.Values-E[16, 17]
<Func ( e.Name ) e.Values-B ( ( e.Name ) e.Value ) e.Values-E >
0 2 4 5 3 6 7 8 10 12 13 11 14 15 9 16 17 1
Дырки кончились, мы построли последовательность команд отождествления:
(0, 1) → ([2] (2, 3) )[3] (3, 1)
(2, 3) → e.Name[4, 5]
CYCLE((3, 1) → e.Values-B[6, 7] (7, 1)) {
(7, 1) → ([8] (8, 9) )[9] (9, 1)
(8, 9) → ([10] (10, 11) )[11] (11, 9)
(10, 11) → e.Name[12, 13 ← 4, 5] (13, 11)
(13, 11) → ε
(11, 9) → e.Value[14, 15]
(9, 1) → e.Values-E[16, 17]
построение правой части
return;
}
Пример. Другой пример из предыдущей главы, с двумя циклами:
(e.Set1-B t.Common e.Set1-E) (e.Set2-B t.Common e.Set2-E)
Расширяем образец и начинаем отождествление:
<Func {(e.Set1-B t.Common e.Set1-E) (e.Set2-B t.Common e.Set2-E)}>
0 1
(0, 1) → ([2] (2, 3) )[3] (3, 1)
<Func ({e.Set1-B t.Common e.Set1-E}) {(e.Set2-B t.Common e.Set2-E)}>
0 2 3 1
(3, 1) → ([4] (4, 5) )[5] (5, 1)
<Func ({e.Set1-B t.Common e.Set1-E}) ({e.Set2-B t.Common e.Set2-E}){}>
0 2 3 4 5 1
(5, 1) → ε
<Func ({e.Set1-B t.Common e.Set1-E}) ({e.Set2-B t.Common e.Set2-E}) >
0 2 3 4 5 1
Есть две дырки, обе начинаются на e-переменную. Выбираем ту переменную, которая в записи левой части левее, по ней строим цикл.
CYCLE((2, 4) → e.Set1-B[6, 7] (7, 4))
<Func ( e.Set1-B {t.Common e.Set1-E}) ({e.Set2-B t.Common e.Set2-E}) >
0 2 6 7 3 4 5 1
T-переменная слева, закрытая переменная:
(7, 3) → t.Common[8, 9] (9, 3)
<Func ( e.Set1-B t.Common {e.Set1-E}) ({e.Set2-B t.Common e.Set2-E}) >
0 2 6 7 8 9 3 4 5 1
(9, 3) → e.Set1-E[10, 11]
<Func ( e.Set1-B t.Common e.Set1-E ) ({e.Set2-B t.Common e.Set2-E}) >
0 2 6 7 8 9 10 11 3 4 5 1
Открытая переменная e.Set2-B, повторная t-переменная, закрытая переменная:
CYCLE((4, 5) → e.Set2-B[12, 13] (13, 5))
<Func ( e.Set1-B t.Common e.Set1-E ) ( e.Set2-B {t.Common e.Set2-E}) >
0 2 6 7 8 9 10 11 3 4 12 13 5 1
(13, 5) → t.Common[14, 15 ← 8, 9] (15, 5)
<Func ( e.Set1-B t.Common e.Set1-E ) ( e.Set2-B t.Common {e.Set2-E}) >
0 2 6 7 8 9 10 11 3 4 12 13 14 15 5
(15, 5) → e.Set2-E[16, 17]
<Func ( e.Set1-B t.Common e.Set1-E ) ( e.Set2-B t.Common e.Set2-E ) >
0 2 6 7 8 9 10 11 3 4 12 13 14 15 16 17 5 1
Сопоставление завершено. Получается такая последовательность элементарных команд сопоставления:
(0, 1) → ([2] (2, 3) )[3] (3, 1)
(3, 1) → ([4] (4, 5) )[5] (5, 1)
(5, 1) → ε
CYCLE((2, 4) → e.Set1-B[6, 7] (7, 4)) {
(7, 3) → t.Common[8, 9] (9, 3)
(9, 3) → e.Set1-E[10, 11]
CYCLE((4, 5) → e.Set2-B[12, 13] (13, 5)) {
(13, 5) → t.Common[14, 15 ← 8, 9] (15, 5)
(15, 5) → e.Set2-E[16, 17]
постороение правой части
return;
}
}
Пример. Построим код для отождествления с образцом
e.Begin (e.Inner) e.End (e.Left 'X' e.Inner)
Строим расширенный образец, видим скобки справа:
<Func {e.Begin (e.Inner) e.End (e.Left 'X' e.Inner)}>
0 1
(0, 1) → (0, 2) ([2] (2, 3) )[3]
<Func {e.Begin (e.Inner) e.End} ({e.Left 'X' e.Inner}) >
0 2 3 1
Обе дырки начинаются на e-переменную. Самую левую из них e.Begin
назначаем открытой и строим цикл её удлинения:
CYCLE((0, 2) → e.Begin[4, 5] (5, 2)
<Func e.Begin {(e.Inner) e.End} ({e.Left 'X' e.Inner}) >
0 4 5 2 3 1
(5, 2) → ([6] (6, 7) )[7] (7, 2)
<Func e.Begin ({e.Inner}) {e.End} ({e.Left 'X' e.Inner}) >
0 4 5 6 7 2 3 1
(6, 7) → e.Inner[8, 9] /* закрытая */
<Func e.Begin ( e.Inner ) {e.End} ({e.Left 'X' e.Inner}) >
0 4 5 6 8 9 7 2 3 1
Переменная e.Inner уже получила значение, а значит, e.Left — не открытая.
(2, 3) → (2, 10) e.Inner[10, 11] /* повторная */
<Func e.Begin ( e.Inner ) {e.End} ({e.Left 'X'} e.Inner ) >
0 4 5 6 8 9 7 2 10 11 3 1
(2, 10) → (2, 12) 'X'
<Func e.Begin ( e.Inner ) {e.End} ({e.Left} 'X' e.Inner ) >
0 4 5 6 8 9 7 2 12 10 11 3 1
(7, 2) → e.End[13, 14] /* закрытая */
<Func e.Begin ( e.Inner ) e.End ({e.Left} 'X' e.Inner ) >
0 4 5 6 8 9 7 13 14 2 12 10 11 3 1
(2, 12) → e.Left[15, 16] /* закрытая */
<Func e.Begin ( e.Inner ) e.End ( e.Left 'X' e.Inner ) >
0 4 5 6 8 9 7 13 14 2 15 16 12 10 11 3 1
Запишем код сопоставления полностью:
(0, 1) → (0, 2) ([2] (2, 3) )[3]
CYCLE((0, 2) → e.Begin[4, 5] (5, 2) {
(5, 2) → ([6] (6, 7) )[7] (7, 2)
(6, 7) → e.Inner[8, 9] /* закрытая */
(2, 3) → (2, 10) e.Inner[10, 11] /* повторная */
(2, 10) → (2, 12) 'X'
(7, 2) → e.End[13, 14] /* закрытая */
(2, 12) → e.Left[15, 16] /* закрытая */
построение результата
return;
}
Вернёмся к шаблону кода предложения
do {
объявления переменных
/* сопоставление с образцом */
if (! элементарное сопоставление)
continue;
…
/* цикл по открытой переменной e.X */
e.X ← пустая
r05_start_e_loop();
do {
if (! элементарное сопоставление)
continue;
…
r05_reset_allocator();
распределение памяти
сборка результата
return;
} while(r05_open_evar_advance(e.X, её диапазон));
r05_stop_e_loop();
} while (0);
В той части, которая обозначена объявления переменных, описывается массив
указателей, используемых при сопоставлении с образцом (сопоставленные элементы)
и построении правой части (об этом в соответствующем параграфе).
Каждое вхождение переменной Рефала запоминается отдельно, поэтому,
например, если в левой части было две переменных e.Key, то в массиве будут
зарезервированы две пары указателей для представления этой переменной.
Для вхождений s-переменных в массиве указателей резервируется указатель на одно звено, соответствующее значению этой переменной, для вхождений t- и e-переменных — по паре звеньев.
T-переменная изображается парой указателей на первый и последний узел. Если переменная хранит символ, оба указателя равны, если переменная хранит скобочный терм, то пара указателей указывает на открывающую и закрывающую скобки соответственно.
Значением e-переменных является произвольное объектное выражение, в том числе пустое. В терминах спискового представления — произвольный участок списка. Изображается e-переменная парой указателей на начало и на конец — указывают они на первый и последний узел участка.
На стадии сопоставления с образцом пустой участок представляется «перехлёстом»:
указатели ссылаются на два смежных звена, при этом первый указатель ссылается
на второе звено и наоборот. На стадии сборки результатного выражения пустое
значение представляется парой нулевых указателей (т.к. команды r05_splice…
могут переместить звенья, представлявшие пустой диапазон).
Массив указателей описывается как
struct r05_node *p[k] = { 0 };
где k — его размер.
Массив указателей предваряется комментариями, в которых записываются положения переменных в нём. Например:
/* e.Name: 4, 12 */
/* e.Values-B: 6 */
/* e.Value: 14 */
/* e.Values-E: 16 */
struct r05_node *p[18] = { 0 };
Переменная e.Name имеет два вхождения в левую часть, оба вхождения
соответствуют парам ячеек p[4], p[5] и p[12], p[13] соответственно.
Переменная e.Values-B располагается в паре ячеек p[6], p[7] и т.д.
В функции сопоставления с образцом и построения результата передаётся адрес
первой ячейки массива, соответствующего переменной, т.к. t- и e-переменные
всегда занимают смежные ячейки. Поэтому вместо p[i] и p[i′] достаточно
передать p+i. Для s-переменных тоже передаётся ссылка, однако она передаётся
для единообразия генерации кода.
Также этот массив используется при построении результата, о чём будет сказано в следующем параграфе.
Команды сопоставления делятся на следующие разновидности:
(u, v) → ε,(u, v) → (u, r) X[r, s]
(u, v) → X[r, s] (s, v),С команды инициализации первой дырки начинается код разбора левой части. Она выглядит так:
p[0] = arg_begin->next;
p[1] = arg_end;
Она получает указатели на начало и конец активного выражения (arg_begin
и arg_end, соответственно), отбрасывает от них левую угловую скобку,
указатель на имя функции и правую угловую скобку присваивает p[0] и p[1]
соответственно.
Команда сопоставления с пустотой имеет вид:
if (! r05_empty_hole(p[u], p[v]))
continue;
(Здесь и далее переменные u, v, i, j будут метапеременными — в реальном
коде на их месте будут располагаться конкретные целые числа. Метапеременная
со штрихом означает значение, на 1 большее одноимённой переменной без штриха.)
Функция r05_empty_hole(left, right) принимает два указателя и проверяет,
что между звеньями left и right ничего нет: left->next == right.
Команды сопоставления слева/справа имеют вид
if (! r05_***_left(p+i, p[u], p[v], «значение»))
continue;
if (! r05_***_right(p+i, p[u], p[v], «значение»))
continue;
где вместо *** записывается сопоставляемый элемент, вместо «значение» —
образ его значения. Доступны следующие операции:
*** |
«значение» |
|---|---|
function |
указатель на описатель функции &r05f_ИмяФункции |
char |
символьный литерал вида 'a', '\n' или '\ooo' |
number |
целое число с суффиксом UL, например 42UL |
brackets |
нет значения |
svar |
нет значения |
tvar |
нет значения |
repeated_svar |
указатель на старую переменную, p+j |
repeated_tvar |
парa указателей на старую переменную p+j |
repeated_evar |
парa указателей на старую переменную p+j |
Все команды сопоставления принимают указатель на позицию фрагмента в массиве указателей, границы дырки и образ значения.
Эти команды сопоставления проверяют, что дырка начинается либо заканчивается
на указанное значение: конкретный символ, произвольный символ, произвольный
терм, терм или объектное выражение с конкретным значением. Позиция символа
сохраняется в p[i].
Команды сопоставления с символами трёх видов просто содержат значение символа, проверяют, что дырка не пустая и начинается/заканчивается на указанный символ.
Команда сопоставления со скобками проверяет, что дырка не пустая и начинается
или заканчивается на скобку, находит парную скобку и сохраняет обе скобки
в массиве указателей. Левая скобка всегда сохраняется в p[i], правая —
в p[i′].
Команды сопоставления с новой s-переменной проверяют, что диапазон не пустой
и начинается или заканчивается на произвольный символ — указатель на этот
символ присваивается переменной p[i].
Команды сопоставленя с новой t-переменной проверяют, что диапазон не пустой
и присваивают t-переменной p[i] и p[i′] указатель на первый
и последний терм соответственно.
Команды сопоставления с повторной s-переменной проверяют, что диапазон
начинается/заканчивается на символ с указанным значением (переменная p[j])
и присваивают новой переменной (p[i]) указатель на равный ему терм.
Команды сопоставления с повторной t- или e-переменной работают аналогично предыдущим, только имеют дело с парой указателей.
Команда сопоставления с закрытой e-переменной (u, v) → e.X[i, i′]
компилируется в вызов макроса:
r05_close_evar(p+i, p[u], p[v]);
В позицию p[i] сохраняется p[u]->next, в p[i′] — p[v]->prev.
r05_close_evar является макросом, поэтому аргументы могут вычисляться
несколько раз.
Циклы по открытым e-переменным компилируются в цикл do … while (…).
Цикл в псевдокоде
CYCLE((u, v) → e.X[i, i′] (i′, v)) {
операции сопоставления
построение результата
return;
}
будет отображаться в
p[i] = p[u]->next;
p[i′] = p[u];
r05_start_e_loop();
do {
операции сопоставления
построение результата
return;
} while (r05_open_evar_advance(p+i, p[v]));
r05_stop_e_loop();
На первой итерации цикла длина открытой переменной равна нулю, уменьшаемая
дырка неизменна. . На каждой следующей функция r05_open_evar_advance()
увеличивает e-переменную на один терм и сокращает соответствующую дырку.
Если сопоставление внутри цикла успешно, то строится результатное выражение
и функция вместе с циклом завершается оператором return;. Если не успешно,
выполнение передаётся условию внутри тела цикла, которое и приводит
к удлинению переменной. Если удлинить переменную невозможно — правая граница
переменной p[i′] выходит за правую границу дырки p[v], функция
r05_open_evar_advance() возвращает нулевое значение, тем самым прерывая цикл.
Пример. Предложение с ранее рассмотренным образцом
(e.Name) e.Values-B ((e.Name) e.Value) e.Values-E = /* пусто */;
Псевдокод образца:
(0, 1) → ([2] (2, 3) )[3] (3, 1)
(2, 3) → e.Name[4, 5]
CYCLE((3, 1) → e.Values-B[6, 7] (7, 1)) {
(7, 1) → ([8] (8, 9) )[9] (9, 1)
(8, 9) → ([10] (10, 11) )[11] (11, 9)
(10, 11) → e.Name[12, 13 ← 4, 5] (13, 11)
(13, 11) → ε
(11, 9) → e.Value[14, 15]
(9, 1) → e.Values-E[16, 17]
построение правой части
return;
}
Сгенерированный код:
do {
/* e.Name: 2 */
struct r05_node *p[5] = { 0 };
/* e.Name */
p[0] = arg_begin->next;
p[1] = arg_end;
r05_close_evar(p+2, p[0], p[1]);
r05_reset_allocator();
r05_alloc_chars("$EXTERN ", 8);
r05_alloc_insert_pos(p+4);
r05_alloc_chars(";\n", 2);
r05_correct_evar(p+2);
r05_splice_evar(p[4], p+2);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0); }
Комментарий с текстом образца после определения массива p формируется
автоматически.
Предложение с рассмотренным ранее образцом:
(e.Set1-B t.Common e.Set1-E) (e.Set2-B t.Common e.Set2-E) = ;
Псевдокод сопоставления с образцом:
(0, 1) → ([2] (2, 3) )[3] (3, 1)
(3, 1) → ([4] (4, 5) )[5] (5, 1)
(5, 1) → ε
CYCLE((2, 4) → e.Set1-B[6, 7] (7, 4)) {
(7, 3) → t.Common[8, 9] (9, 3)
(9, 3) → e.Set1-E[10, 11]
CYCLE((4, 5) → e.Set2-B[12, 13] (13, 5)) {
(13, 5) → t.Common[14, 15 ← 8, 9] (15, 5)
(15, 5) → e.Set2-E[16, 17]
постороение правой части
return;
}
}
Сгенерированный код:
do {
/* e.Set1-B: 6 */
/* t.Common: 8, 14 */
/* e.Set1-E: 10 */
/* e.Set2-B: 12 */
/* e.Set2-E: 16 */
struct r05_node *p[18] = { 0 };
/* (e.Set1-B t.Common e.Set1-E) (e.Set2-B t.Common e.Set2-E) */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_brackets_left(p+2, p[0], p[1]))
continue;
if (! r05_brackets_left(p+4, p[3], p[1]))
continue;
if (! r05_empty_hole(p[5], p[1]))
continue;
p[6] = p[2]->next;
p[7] = p[2];
r05_start_e_loop();
do {
if (! r05_tvar_left(p+8, p[7], p[3]))
continue;
r05_close_evar(p+10, p[9], p[3]);
p[12] = p[4]->next;
p[13] = p[4];
r05_start_e_loop();
do {
if (! r05_repeated_tvar_left(p+14, p[13], p[5], p+8))
continue;
r05_close_evar(p+16, p[15], p[5]);
r05_reset_allocator();
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (r05_open_evar_advance(p+12, p[5]));
r05_stop_e_loop();
} while (r05_open_evar_advance(p+6, p[3]));
r05_stop_e_loop();
} while (0);
Предложение с ранее рассмотренным образцом:
e.Begin (e.Inner) e.End (e.Left 'X' e.Inner) = ;
Псевдокод образца:
(0, 1) → (0, 2) ([2] (2, 3) )[3]
CYCLE((0, 2) → e.Begin[4, 5] (5, 2) {
(5, 2) → ([6] (6, 7) )[7] (7, 2)
(6, 7) → e.Inner[8, 9] /* закрытая */
(2, 3) → (2, 10) e.Inner[10, 11] /* повторная */
(2, 10) → (2, 12) 'X'
(7, 2) → e.End[13, 14] /* закрытая */
(2, 12) → e.Left[15, 16] /* закрытая */
построение результата
return;
}
Сгенерированный код:
do {
/* e.Begin: 4 */
/* e.Inner: 8, 10 */
/* e.End: 13 */
/* e.Left: 15 */
struct r05_node *p[17] = { 0 };
/* e.Begin (e.Inner) e.End (e.Left 'X' e.Inner) */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_brackets_right(p+2, p[0], p[1]))
continue;
p[4] = p[0]->next;
p[5] = p[0];
r05_start_e_loop();
do {
if (! r05_brackets_left(p+6, p[5], p[2]))
continue;
r05_close_evar(p+8, p[6], p[7]);
if (! r05_repeated_evar_right(p+10, p[2], p[3], p+8))
continue;
if (! r05_char_right(p+12, p[2], p[10], 'X'))
continue;
r05_close_evar(p+13, p[7], p[2]);
r05_close_evar(p+15, p[2], p[12]);
r05_reset_allocator();
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (r05_open_evar_advance(p+4, p[2]));
r05_stop_e_loop();
} while (0);
Как было сказано ранее, построение результатного выражения делится на две фазы: распределение памяти и сборка результата. Стадия распределения памяти может остановить программу с выдачей дампа, но поле зрения не меняет. Стадия сборки результата перекраивает поле зрения, провязывает ссылки в скобочных узлах и прерваться ошибкой не может.
Фаза распределения памяти довольно бесхитростна. Распределение памяти
начинается с команды r05_reset_allocator();, которая подготавливает
распределитель памяти к построению результата, подробнее её обсудим чуть
ниже.
Затем последовательно просматривается правая часть и для каждого элемента:
Очевидно, «вычёркивание» позволяет находить вхождения переменных, которые копировать не нужно, достаточно только переносить.
При создании скобок сохраняются их позиции в списке свободных узлов — они нужны будут на стадии сборки результата для провязывания их между собой.
Рантайм содержит внутреннюю переменную s_free_ptr, которая указывает
на следующий непроинициализированный узел в списке свободных узлов. Функция
r05_reset_allocator(); устанавливает этот указатель на начало списка
свободных узлов (а также сообщает профилировщику, что анализ левой части
закончился, начался синтез правой).
Команды создания новых элементов инициализируют узлы, начиная с s_free_ptr,
при этом сдвигая этот указатель вперёд. Если указатель s_free_ptr указывает
на s_end_free_list, то команды создания запрашивают у операционной системы
память для создания новых узлов. Если память выделить не удаётся, либо число
созданных узлов превысило R05_MEMORY_LIMIT (см. раздел 3), программа
завершается с выдачей аварийного дампа.
Команда сохранения позиции вставки возвращает текущее значение s_free_ptr,
не сдвигая его. Однако, есть один нюанс. Позиция вставки может указывать
только на актуальный узел, поэтому, когда s_free_ptr ссылается
на s_end_free_list, распределяется память для новых узлов. Следовательно,
запрос позиции вставки может привести к остановке программы с выдачей аварийного
дампа. Это не ошибка в API, это так и было задумано. Поэтому команды сохранения
позиции могут располагаться только во второй фазе — фазе распределения памяти.
Точно также, как и команды сопоставления слева/справа, команды распределения памяти строятся по одному шаблону и имеют вид
r05_alloc_***(«значение»);
где *** и «значение» определяются таблицей:
*** |
«значение» |
|---|---|
char |
символьный литерал вида 'a', '\n' или '\ooo' |
chars |
"строка", длина, например, "abc", 3 |
number |
целое число с суффиксом UL, например 42UL |
function |
указатель на описатель функции, &r05f_ИмяФункции |
open_bracket |
позиция, p+j |
close_bracket |
позиция, p+j |
open_call |
позиция, p+j |
close_call |
позиция, p+j |
insert_pos |
позиция, p+j |
svar |
s-переменная, p+i |
tvar |
t-переменная, пара указателей: p+i |
evar |
e-переменная, пара указателей: p+i |
Функция r05_alloc_chars() добавлена для оптимизации случая, когда несколько
литер идут подряд. Аналогичной оптимизации для левой части не предусмотрено,
поскольку по опыту автора эта оптимизация нужна гораздо реже.
Странная функция r05_alloc_insert_pos() добавлена в API для единообразия
генерации кода для второй фазы — чтобы не рассматривать частный случай отдельно.
Для данной операции в API предусмотрена функция r05_insert_pos(), возвращающая
позицию вставки, а r05_alloc_insert_pos — это просто макрообёртка над ней.
Теперь становится понятным второе предназначение массива указателей p:
struct r05_node *p[k] = { 0 };
В этом массиве сохраняются указатели на скобки и позиции вставки.
Команды третьей фазы предложения (и второй фазы обработки правой части) более разнообразны.
Помещение угловых скобок на стек выполняется командой
r05_push_stack(p[j]);
где p[j] должен ссылаться на угловую скобку. Эта функция просто кладёт узел
на вершину стека s_stack_ptr, как было описано в самом начале раздела.
Первичное активное подвыражение — это пара скобок активации, такая что
Нетрудно заметить, что самая левая закрывающая угловая скобка будет принадлежать первичному активному подвыражению. И вообще, функции в поле зрения будут вычисляться в порядке перечисления их закрывающих угловых скобок:
<F <G > <H <I > > >
1 2 3 4
Поэтому порядок команд r05_push_stack определяется порядком закрывающих
угловых скобок:
Например, для выражения выше, скобки на стек будут положены в следующем порядке:
<F <G > <H <I > > >
2 8 7 4 6 5 3 1
Легко убедиться, что они дадут именно ту картину связей, которая рассматривалась в самом начале раздела.
Связывание круглых скобок выполняется командой
r05_link_brackets(p[i], p[j]);
Тут всё просто — поля info.link обоих узлов проставляются друг на друга.
Перенос переменных в их позиции выполняется командами
r05_splice_tvar(p[j], p+i);
r05_splice_evar(p[j], p+i);
Обе команды переносят значения переменных перед сохранённым указателем.
После сопоставления с образцом пустые e-переменные содержат пару указателей, ссылающихся на два соседних звена, причём второй указатель ссылается на предшествующее звено, а первый — на последующее.
Операции переноса могут нарушить этот инвариант, если одно из этих звеньев принадлежит переносимой переменной. Поэтому всем операциям переноса переменных предшествуют операции коррекции e-переменных:
r05_correct_evar(p+i);
которые для пустых переменных присваивают им пару нулевых указателей. Функция
r05_splice_evar() распознаёт пару нулевых указателей как пустую переменную
и не выполняет операцию переноса.
Перенос подготовленного результата в поле зрения:
r05_splice_from_freelist(arg_begin);
Должна выполняться после всех команд r05_splice_?var.
Команда переносит фрагмент списка свободных узлов от начала до текущего
положения s_free_ptr (не включая сам s_free_ptr) перед открывающей
угловой скобкой первичного активного подвыражения. Вернее того, что от него
осталось, поскольку команды r05_splice_?var уже перенесли его фрагменты
в подготовленный результат.
Удаление первичного активного подвыражения из поля зрения:
r05_splice_to_freelist(arg_begin, arg_end);
Команда переносит первичное активное подвыражение в список свободных узлов.
Содержимое списка свободных узлов меняется, поэтому она должна вызываться
после r05_splice_from_freelist.
Рассмотренных сведений достаточно для того, чтобы читать сгенерированный код на Си для программ на Рефале.
Пример. Функция
$ENTRY Apply {
s.Fn e.Argument = <Mu s.Fn e.Argument>;
(t.Closure e.Bounded) e.Argument =
<Apply t.Closure e.Bounded e.Argument>;
}
компилируется в
R05_DEFINE_ENTRY_FUNCTION(Apply, "Apply") {
r05_this_is_generated_function();
do {
/* s.Fn: 2 */
/* e.Argument: 3 */
struct r05_node *p[8] = { 0 };
/* s.Fn e.Argument */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_svar_left(p+2, p[0], p[1]))
continue;
r05_close_evar(p+3, p[2], p[1]);
r05_reset_allocator();
r05_alloc_open_call(p+5);
r05_alloc_function(&r05f_Mu);
r05_alloc_svar(p+2);
r05_alloc_insert_pos(p+6);
r05_alloc_close_call(p+7);
r05_push_stack(p[7]);
r05_push_stack(p[5]);
r05_correct_evar(p+3);
r05_splice_evar(p[6], p+3);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
do {
/* e.Argument: 4 */
/* t.Closure: 6 */
/* e.Bounded: 8 */
struct r05_node *p[13] = { 0 };
/* (t.Closure e.Bounded) e.Argument */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_brackets_left(p+2, p[0], p[1]))
continue;
r05_close_evar(p+4, p[3], p[1]);
if (! r05_tvar_left(p+6, p[2], p[3]))
continue;
r05_close_evar(p+8, p[7], p[3]);
r05_reset_allocator();
r05_alloc_open_call(p+10);
r05_alloc_function(&r05f_Apply);
r05_alloc_insert_pos(p+11);
r05_alloc_close_call(p+12);
r05_push_stack(p[12]);
r05_push_stack(p[10]);
r05_correct_evar(p+4);
r05_correct_evar(p+8);
r05_splice_tvar(p[11], p+6);
r05_splice_evar(p[11], p+8);
r05_splice_evar(p[11], p+4);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
r05_recognition_impossible();
}
Пример. Функция
$ENTRY Map {
t.Fn t.Next e.Tail = <Apply t.Fn t.Next> <Map t.Fn e.Tail>;
t.Fn = ;
}
компилируется в
R05_DEFINE_ENTRY_FUNCTION(Map, "Map") {
r05_this_is_generated_function();
do {
/* t.Fn: 2 */
/* t.Next: 4 */
/* e.Tail: 6 */
struct r05_node *p[14] = { 0 };
/* t.Fn t.Next e.Tail */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_tvar_left(p+2, p[0], p[1]))
continue;
if (! r05_tvar_left(p+4, p[3], p[1]))
continue;
r05_close_evar(p+6, p[5], p[1]);
r05_reset_allocator();
r05_alloc_open_call(p+8);
r05_alloc_function(&r05f_Apply);
r05_alloc_insert_pos(p+9);
r05_alloc_close_call(p+10);
r05_alloc_open_call(p+11);
r05_alloc_function(&r05f_Map);
r05_alloc_tvar(p+2);
r05_alloc_insert_pos(p+12);
r05_alloc_close_call(p+13);
r05_push_stack(p[13]);
r05_push_stack(p[11]);
r05_correct_evar(p+6);
r05_push_stack(p[10]);
r05_push_stack(p[8]);
r05_splice_tvar(p[9], p+2);
r05_splice_tvar(p[9], p+4);
r05_splice_evar(p[12], p+6);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
do {
/* t.Fn: 2 */
struct r05_node *p[4] = { 0 };
/* t.Fn */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_tvar_left(p+2, p[0], p[1]))
continue;
if (! r05_empty_hole(p[3], p[1]))
continue;
r05_reset_allocator();
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
r05_recognition_impossible();
}
Пример. Функция
DoLoadFile {
/* пусто */ 0 = /* конец файла, пропускаем тут пустую строку */;
e.Line 0 = (e.Line) /* конец файла */;
e.Line = (e.Line) <DoLoadFile <Get <LOAD-SAVE-HANDLE>>>;
}
компилируется в
R05_DEFINE_LOCAL_FUNCTION(DoLoadFile, "DoLoadFile") {
r05_this_is_generated_function();
do {
struct r05_node *p[3] = { 0 };
/* 0 */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_number_left(p+2, p[0], p[1], 0UL))
continue;
if (! r05_empty_hole(p[2], p[1]))
continue;
r05_reset_allocator();
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
do {
/* e.Line: 3 */
struct r05_node *p[8] = { 0 };
/* e.Line 0 */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_number_right(p+2, p[0], p[1], 0UL))
continue;
r05_close_evar(p+3, p[0], p[2]);
r05_reset_allocator();
r05_alloc_open_bracket(p+5);
r05_alloc_insert_pos(p+6);
r05_alloc_close_bracket(p+7);
r05_link_brackets(p[5], p[7]);
r05_correct_evar(p+3);
r05_splice_evar(p[6], p+3);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
do {
/* e.Line: 2 */
struct r05_node *p[13] = { 0 };
/* e.Line */
p[0] = arg_begin->next;
p[1] = arg_end;
r05_close_evar(p+2, p[0], p[1]);
r05_reset_allocator();
r05_alloc_open_bracket(p+4);
r05_alloc_insert_pos(p+5);
r05_alloc_close_bracket(p+6);
r05_alloc_open_call(p+7);
r05_alloc_function(&r05f_DoLoadFile);
r05_alloc_open_call(p+8);
r05_alloc_function(&r05f_Get);
r05_alloc_open_call(p+9);
r05_alloc_function(&r05f_LOADm_SAVEm_HANDLE);
r05_alloc_close_call(p+10);
r05_alloc_close_call(p+11);
r05_alloc_close_call(p+12);
r05_push_stack(p[12]);
r05_push_stack(p[7]);
r05_push_stack(p[11]);
r05_push_stack(p[8]);
r05_push_stack(p[10]);
r05_push_stack(p[9]);
r05_link_brackets(p[4], p[6]);
r05_correct_evar(p+2);
r05_splice_evar(p[5], p+2);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
}
Заметим, что последнее предложение функции имеет вид e.Line = …;, а значит,
всегда выполняется успешно. Поэтому команда r05_recognition_impossible();
в конце не генерируется.
Пример. Программа
$ENTRY Go {
= <Prout 'What is your name?'> <Hello <Card>>;
}
Hello {
/* пусто */ = <Prout 'Hello!'>;
e.UserName = <Prout 'Hello, ' e.UserName '!'>;
}
компилируется в следующий текст
/* Automatically generated file. Don't edit! */
#include "refal05rts.h"
R05_DECLARE_ENTRY_FUNCTION(Card)
R05_DECLARE_ENTRY_FUNCTION(Prout)
R05_DECLARE_ENTRY_FUNCTION(Go)
R05_DECLARE_LOCAL_FUNCTION(Hello)
R05_DEFINE_ENTRY_FUNCTION(Go, "Go") {
r05_this_is_generated_function();
do {
struct r05_node *p[8] = { 0 };
/* */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_empty_hole(p[0], p[1]))
continue;
r05_reset_allocator();
r05_alloc_open_call(p+2);
r05_alloc_function(&r05f_Prout);
r05_alloc_chars("What is your name?", 18);
r05_alloc_close_call(p+3);
r05_alloc_open_call(p+4);
r05_alloc_function(&r05f_Hello);
r05_alloc_open_call(p+5);
r05_alloc_function(&r05f_Card);
r05_alloc_close_call(p+6);
r05_alloc_close_call(p+7);
r05_push_stack(p[7]);
r05_push_stack(p[4]);
r05_push_stack(p[6]);
r05_push_stack(p[5]);
r05_push_stack(p[3]);
r05_push_stack(p[2]);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
r05_recognition_impossible();
}
R05_DEFINE_LOCAL_FUNCTION(Hello, "Hello") {
r05_this_is_generated_function();
do {
struct r05_node *p[4] = { 0 };
/* */
p[0] = arg_begin->next;
p[1] = arg_end;
if (! r05_empty_hole(p[0], p[1]))
continue;
r05_reset_allocator();
r05_alloc_open_call(p+2);
r05_alloc_function(&r05f_Prout);
r05_alloc_chars("Hello!", 6);
r05_alloc_close_call(p+3);
r05_push_stack(p[3]);
r05_push_stack(p[2]);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
do {
/* e.UserName: 2 */
struct r05_node *p[7] = { 0 };
/* e.UserName */
p[0] = arg_begin->next;
p[1] = arg_end;
r05_close_evar(p+2, p[0], p[1]);
r05_reset_allocator();
r05_alloc_open_call(p+4);
r05_alloc_function(&r05f_Prout);
r05_alloc_chars("Hello, ", 7);
r05_alloc_insert_pos(p+5);
r05_alloc_char('!');
r05_alloc_close_call(p+6);
r05_push_stack(p[6]);
r05_push_stack(p[4]);
r05_correct_evar(p+2);
r05_splice_evar(p[5], p+2);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
return;
} while (0);
}
/* End of file */
Чтобы ещё лучше понимать работу рефал-машины, рассмотрим некоторые фрагменты
кода её реализации. Код местами будет упрощён, в частности, будут опущены
встроенные средства отладки и профилирования. Желающие могут прочитать исходники
рантайма целиком (refal05rts.h, refal05rts.c), они короткие, менее
2000 строк, но для прикладного программирования, включая даже написание
функций на Си, это не нужно. Фрагменты исходников в этом параграфе даются
только в качестве иллюстрации.
Примечание. Фрагменты исходного текста актуальны на момент написания документации. В последующем рантайм может обновляться без синхронного обновления этого параграфа.
Начнём с начала — с функции main():
int main(int argc, char **argv) {
s_argc = argc;
s_argv = argv;
init_view_field();
start_profiler();
main_loop();
r05_exit(0);
}
Глобальные (статические) переменные s_argc и s_argv сохраняют значения
аргументов командной строки для того, чтобы их могла прочитать встроенная
функция Arg. Функция init_view_field() создаёт вызов <Go> в поле зрения.
start_profiler() засекает время начала выполнения программы. main_loop() —
главный цикл преобразования поля зрения. Функция r05_exit() завершает работу
рефал-машины и всей программы целиком.
Подсистему профилирования мы рассматривать не будем, поскольку содержательно интересного в ней ничего нет — рефал-машина и без неё останется рефал-машиной.
Функция init_view_field() создаёт начальное содержимое поля зрения при помощи
уже известных нам функций построения результата:
static void init_view_field(void) {
struct r05_node *open, *close;
r05_reset_allocator();
r05_alloc_open_call(&open);
r05_alloc_function(&r05f_Go);
r05_alloc_close_call(&close);
r05_push_stack(close);
r05_push_stack(open);
r05_splice_from_freelist(s_begin_view_field.next);
}
Основной цикл работы рефал-машины (с сокращениями):
static void main_loop(void) {
while (! empty_stack()) {
struct r05_node *function;
s_arg_begin = pop_stack();
s_arg_end = pop_stack();
function = s_arg_begin->next;
if (R05_DATATAG_FUNCTION == function->tag) {
(function->info.function->ptr)(s_arg_begin, s_arg_end);
} else {
r05_recognition_impossible();
}
}
}
Скобки активации, которые располагаются в поле зрения, обязательно должны образовывать односвязный список — стек скобок активации. Поэтому условие, что рефал-машина выполняет шаги до тех пор, пока поле зрения активно — в нём есть вызовы функций, эквивалентно условию, что стек скобок активации не пуст.
На каждой итерации со стека снимаются левая и правая скобки — они соответствуют первичному активному подвыражению, из следующего после левой скобки узла извлекается указатель на функцию и эта функция вызывается с передачей ей указателей на скобки. Если справа от левой скобки активации функции не оказалось — программа завершается с выдачей аварийного дампа и ошибки невозможности отождествления.
Операции со стеком довольно очевидные — просто оперируют с односвязным списком:
static struct r05_node *s_stack_ptr = NULL;
void r05_push_stack(struct r05_node *call_bracket) {
call_bracket->info.link = s_stack_ptr;
s_stack_ptr = call_bracket;
}
static struct r05_node *pop_stack(void) {
struct r05_node *res = s_stack_ptr;
s_stack_ptr = s_stack_ptr->info.link;
return res;
}
static int empty_stack(void) {
return (s_stack_ptr == 0);
}
Функция r05_exit() освобождает память и завершает программу вызовом функции
exit() языка Си (код с сокращениями):
void r05_exit(int retcode) {
end_profiler();
free_memory();
exit(retcode);
}
Профилировщик при остановке выводит статистику, free_memory() освобождает
память, выделенную под узлы в поле зрения и в списке свободных узлов.
Функция r05_recognition_impossible() выполняющая аварийный останов при
невозможности отождествления, реализована посредством r05_exit():
void r05_recognition_impossible(void) {
fprintf(stderr, "\nRECOGNITION IMPOSSIBLE\n\n");
make_dump();
r05_exit(EXIT_CODE_RECOGNITION_IMPOSSIBLE);
}
Константа EXIT_CODE_RECOGNITION_IMPOSSIBLE определена как 201, функция
make_dump() распечатывает содержимое поля зрения на stderr.
Элементарные операции распределения памяти реализованы посредством функции
r05_alloc_node(), которая инициализирует очередной узел в списке свободных
узлов. Вот как это выглядит в refal05rts.h (фрагмент):
struct r05_node *r05_alloc_node(enum r05_datatag tag);
struct r05_node *r05_insert_pos(void);
#define r05_alloc_char(ch) \
(r05_alloc_node(R05_DATATAG_CHAR)->info.char_ = (ch))
void r05_alloc_chars(const char buffer[], size_t len);
#define r05_alloc_number(num) \
(r05_alloc_node(R05_DATATAG_NUMBER)->info.number = (num))
#define r05_alloc_function(func) \
(r05_alloc_node(R05_DATATAG_FUNCTION)->info.function = func)
. . .
#define r05_alloc_insert_pos(pos) (*(pos) = r05_insert_pos());
. . .
Функции r05_alloc_node() и r05_insert_pos() реализованы так:
struct r05_node *r05_alloc_node(enum r05_datatag tag) {
struct r05_node *node;
ensure_memory();
node = s_free_ptr;
s_free_ptr = s_free_ptr->next;
node->tag = tag;
return node;
}
struct r05_node *r05_insert_pos(void) {
ensure_memory();
return s_free_ptr;
}
Функция ensure_memory() обеспечивает наличие узлов в позиции s_free_ptr,
т.е. если они есть, управление просто возвращается, если нет — распределяет
новую память, если распределить память не удалось — программа аварийно
завершается. После вызова ensure_memory() в r05_alloc_node() узел в позиции
s_free_ptr получает новый тег, указатель s_free_ptr сдвигается вперёд,
указатель на новый узел возвращается. В r05_insert_pos() всё ещё проще —
обеспечивается (ensure), что указатель s_free_ptr указывает на валидный узел
(не на границу s_end_free_list) и этот указатель возвращается.
Функция ensure_memory() устроена так:
static void ensure_memory(void) {
if ((s_free_ptr == &s_end_free_list) && ! create_nodes()) {
fprintf(stderr, "\nNO MEMORY\n\n");
make_dump();
r05_exit(EXIT_CODE_NO_MEMORY);
}
}
Если s_free_ptr указывает на границу и не удалось выделить новую память —
аварийно останавливаем программу. Иначе ничего делать не надо. Очевидное
постусловие: s_free_ptr указывает на валидный узел.
Функцию create_nodes() рассматривать не будем, отметим лишь, что ради повышения
быстродействия она выделяет память кусками (chunks) по несколько сотен узлов
за раз и инициализирует новые узлы тегом R05_DATATAG_ILLEGAL.
Рассмотрим операции копирования t- и e-переменных (в первой главе раздела давался псевдокод, можете сравнить):
/* в файле refal05rts.h */
#define r05_alloc_tvar r05_alloc_tevar
#define r05_alloc_evar r05_alloc_tevar
/* в файле refal05rts.c */
void r05_alloc_tevar(struct r05_node **sample) {
struct r05_node *p, *limit;
clock_t start_copy_time = clock();
struct r05_node *bracket_stack = 0;
for (p = sample[0], limit = sample[1]->next; p != limit; p = p->next) {
struct r05_node *copy = r05_alloc_node(p->tag);
if (is_open_bracket(copy)) {
copy->info.link = bracket_stack;
bracket_stack = copy;
} else if (is_close_bracket(copy)) {
struct r05_node *open_cobracket = bracket_stack;
assert(bracket_stack != 0);
bracket_stack = bracket_stack->info.link;
r05_link_brackets(open_cobracket, copy);
} else {
copy->info = p->info;
}
}
assert(bracket_stack == 0);
add_copy_tevar_time(clock() - start_copy_time);
}
Видно, что для копирования объектных выражений рекурсивных вызовов не требуется. Аналогично не требуется рекурсии и для сравнения выражений на равенство:
#define r05_repeated_tvar_left(v, l, r, s) \
r05_repeated_tevar_left(v, l, r, s, 't')
int r05_repeated_tevar_left(
struct r05_node **tevar, struct r05_node *left, struct r05_node *right,
struct r05_node **tevar_sample, char type
) {
clock_t start_match = clock();
struct r05_node *current = left->next;
struct r05_node *limit = right;
struct r05_node *cur_sample = tevar_sample[0];
struct r05_node *limit_sample = tevar_sample[1]->next;
while (
/* порядок условий важен */
current != limit && cur_sample != limit_sample
&& equal_nodes(current, cur_sample)
) {
cur_sample = cur_sample->next;
current = current->next;
}
(type == 't' ? add_match_repeated_tvar_time : add_match_repeated_evar_time)(
clock() - start_match
);
/*
Здесь current == limit || cur_sample == limit_sample
|| ! equal_nodes(current, cur_sample)
*/
if (cur_sample == limit_sample) {
/* Это нормальное завершение цикла — вся образцовая переменная проверена */
tevar[0] = left->next;
tevar[1] = current->prev;
return 1;
} else {
return 0;
}
}
static int equal_nodes(struct r05_node *node1, struct r05_node *node2) {
if (node1->tag != node2->tag) {
return 0;
} else {
switch (node1->tag) {
case R05_DATATAG_CHAR:
return (node1->info.char_ == node2->info.char_);
case R05_DATATAG_NUMBER:
return (node1->info.number == node2->info.number);
case R05_DATATAG_FUNCTION:
return equal_functions(node1->info.function, node2->info.function);
/*
Сведения о связях между скобками нужны для других целей,
здесь же нам важны только их одновременные появления.
*/
case R05_DATATAG_OPEN_BRACKET:
case R05_DATATAG_CLOSE_BRACKET:
return 1;
/*
Данная функция предназначена только для использования функциями
сопоставления с образцом. Поэтому других узлов мы тут не ожидаем.
*/
default:
r05_switch_default_violation(node1->tag);
}
}
}
Рефал-05 позволяет программисту писать функции на Си и затем вызывать их из кода
на Рефале. Действительно: на вход компилятору могут быть переданы как исходники
на Рефале (расширение .ref), так и исходники на Си (расширение .c). Первые
будут откомпилированы в Си, и те, и другие будут переданы компилятору Си.
Поэтому, если в исходнике написано $EXTERN Foobar;, компилятору не важно,
функция Foobar была написана на Рефале и скомпилирована в Си, или сразу была
написана на Си.
Поэтому простейшим примером функции Рефала, написанной на Си, будет следующая программа:
#include <stdio.h>
#include "refal05rts.h"
R05_DEFINE_ENTRY_FUNCTION(Go, "Go") {
printf("Hello, World!\n");
r05_splice_to_freelist(arg_begin, arg_end);
}
Здесь определена функция Рефала (посредством макроса R05_DEFINE_ENTRY_FUNCTION),
которая печатает сообщение при помощи функции printf() и удаляет свой вызов
из поля зрения.
Заметим, что в эту функцию мы намеренно не добавляли вызов
r05_this_is_generated_function(), нам нужно, чтобы профилировщик считал эту
функцию внешней функцией (замерял её время в метрике Builtin time).
В дальнейшем мы рассмотрим более развёрнутый пример функции на Си.
Как сказано в предыдущей главе, выполнение предложения делится на три стадии:
Первые два этапа не меняют поле зрения. Последний этап, который перекраивает поле зрения, не может прерваться остановкой с выдачей отладочного дампа. При написании собственных функций на Си рекомендуется предерживаться такого же соглашения.
В первых двух главах была рассмотрена та часть API рантайма, которая используется сгенерированным кодом. В этом разделе мы перечислим функции, которые предназначены для использования в самописном коде на Си.
size_t r05_read_chars(
struct r05_node **char_interval, char buffer[], size_t buflen,
struct r05_node *left, struct r05_node *right
);
size_t r05_read_chars(
char buffer[], size_t buflen,
struct r05_node **first, struct r05_node **last
);
Функция r05_read_chars() распознаёт в дырке (left, right) префикс
из литер максимальной длины, однако не превышающей buflen. Прочитанные литеры
помещаются в массив buffer. Переменная char_interval должна ссылаться
на массив из двух указателей на звенья, в неё будут помещены указатели
на первое и последнее звено прочитанного префикса.
Возвращаемое значение: число прочитанных литер.
Функция завершает чтение при достижении одного из трёх условий:
buflen литер,left, right),char_interval[1]->next не является литерой.Функция r05_insert_pos() уже упоминалась выше, но не лишне повторить.
struct r05_node *r05_insert_pos(void);
Она возвращает позицию вставки, эквивалентна по своему действию макрофункции
r05_alloc_insert_pos(pos), которая используется в сгенерированном коде.
void r05_alloc_string(const char *string);
Функция аналогична r05_alloc_chars(), однако длину распределяемой строки
определяет по концевому нулю.
Доступно также несколько функций взаимодействия с виртуальной машиной и операционной средой:
void r05_recognition_impossible(void);
void r05_exit(int retcode);
void r05_builtin_error(const char *message);
void r05_builtin_error_errno(const char *message);
const char *r05_arg(int no);
Первые четыре функции завершают работу рефал-машины и поэтому могут вызываться
только изнутри работающей рефал-машины. Последняя
возвращает аргумент командной строки с указанным номером, либо пустую строку
"", если запрашиваемый номер превышает количество актуальных аргументов.
По сути функция r05_arg() реализует семантику встроенной функции Arg
в терминах языка Си, встроенная функция является лишь обёрткой над этой функцией
API рантайма.
r05_recognition_impossible() и r05_exit() уже рассматривались ранее — первая
останавливает программу с выдачей ошибки невозможности отождествления и аварийным
дампом, вторая просто завершает программу.
Функции r05_builtin_error() и r05_builtin_error_errno() останавливают
программу с выдачей пользовательского сообщения об ошибке, аварийным дампом
и устанавливают код возврата в 203. Вторая функция тажке распечатывает
значение errno и его строковое представление, формируемое функцией
strerror() стандартной библиотеки Си.
В пользовательских функциях на Си рекомендуется различать
r05_recognition_impossible() с одной стороны, и r05_builtin_error***()
с другой. Если аргумент функции не соответствует ожидаемому формату, например,
функция деления получила вместо чисел литеры или функции, либо функция открытия
файла получила вместо строки литер скобочный терм, рекомендуется выдавать ошибку
невозможности отождествления. Если же произошла семантическая ошибка в самой
функции — деление на ноль или искомый файл открыть не удалось — следует вызвать
r05_builtin_error() с соответствующим текстом ошибке. Если завершилась
неудачей библиотечная функция языка Си, которая может устанавливать errno,
то рекомендуется использовать r05_builtin_error_errno() для формирования
более детального сообщения об ошибке.
Давайте напишем функцию, определяющую объём файла, для наглядности добавив в неё все мыслимые проверки.
Функция будет иметь следующий формат:
<FileSize s.CHAR+> == s.NUMBER
Т.е. функция будет принимать строку литер и возвращать целое число. Точно также,
как и встроенная функция Open, наша функция будет предполагать, что файл
существует и доступен для чтения, в противном случае функция будет аварийно
останавливать программу с выдачей дампа.
Ради переносимости функцию будем писать на стандартном Си, хоть этот способ
немного ограничен: не будет возможности определить объём файлов, чей размер
не влезает в long int.
Единственный доступный в стандартном Си способ определения размера файла состоит
в его открытии для чтения (fopen()), установке позиции в конец файла
(fseek()) и получении этой позиции как числа long int (ftell()). После
получения объёма файла его потребуется закрыть (fclose()). Любая
из перечисленных стандартных функций может завершиться неуспешно, что мы будем
каждый раз проверять.
Функция fopen() получает имя файла в виде C-строки — указателя на массив
символов, поэтому возникает вопрос, а где распределять под него память
и какого размера? Можно выделять память в куче при помощи malloc(),
и, по мере анализа аргумента, буфер расширять при помощи realloc()’а,
но это усложнит алгоритм — потребуется обрабатывать потенциальную ошибку
недостатка памяти, а также не забыть явно вызвать free(). Поэтому поступим
иначе — выделим память на стеке. Размер такого буфера стандарт языка Си
рекомендует устанавливать равным размеру макроса FILENAME_MAX. На платформах,
где есть ограничение на максимальную длину файла, макрос содержит наибольшую
допустимую константу. На других платформах он просто содержит некоторое
рекомендуемое значение (по наблюдениям автора чаще всего это 1K, 2K или 4K).
Если длина цепочки литер в аргументе превышает FILENAME_MAX, будем выдавать
сообщение об ошибке.
Функция будет выполняться в три стадии:
FILENAME_MAX, всё нормально, если аргумент пустой,
либо содержит не литеры — нарушение формата (ошибка отождествления), если
длина цепочки литер превышает допустимую — семантическая ошибка,Первые две стадии поле зрения не меняют, но могут завершиться аварийно. Третья стадия аварийно прерваться не может.
Рассмотрим текст функции (вместе с тестовым примером) целиком, а затем прокомментируем нюансы.
Тестовый пример (filesize-test.ref):
*$FROM filesize
$EXTERN FileSize;
$ENTRY Go {
= <PrintSize 'filesize.c'> <PrintSize 'filesize-test.ref'>;
}
PrintSize {
e.FileName = <Prout 'Size of ' e.FileName ' is ' <FileSize e.FileName>>;
}
Исходный файл на Си (filesize.c):
#include <stdio.h>
#include "refal05rts.h"
/*
<FileSize s.CHAR+> == s.NUMBER
*/
R05_DEFINE_ENTRY_FUNCTION(FileSize, "FileSize") {
struct r05_node *fname[2];
char filename[FILENAME_MAX + 1];
size_t filename_len;
FILE *f;
long int size;
struct r05_node *callee = arg_begin->next;
/* сопоставление с образцом */
filename_len =
r05_read_chars(fname, filename, FILENAME_MAX, callee, arg_end);
filename[filename_len] = '\0';
if (filename_len == 0) {
r05_recognition_impossible();
}
if (! r05_empty_hole(fname[1], arg_end)) {
struct r05_node *p = fname[1]->next;
while (p != arg_end && p->tag == R05_DATATAG_CHAR) {
p = p->next;
}
if (p == arg_end) {
r05_builtin_error("very long filename");
} else {
r05_recognition_impossible();
}
}
/* получение объёма файла */
f = fopen(filename, "r");
if (f == NULL) {
r05_builtin_error_errno("Can't open file");
}
if (fseek(f, 0, SEEK_END) != 0) {
r05_builtin_error_errno("Can't seeking to end of file");
}
size = ftell(f);
if (size == -1L) {
r05_builtin_error_errno("Can't telling position of file");
}
if (fclose(f) == EOF) {
r05_builtin_error_errno("Can't close file correctly");
}
/* построение результата */
arg_begin->tag = R05_DATATAG_NUMBER;
arg_begin->info.number = (r05_number) size;
r05_splice_to_freelist(callee, arg_end);
}
Поскольку мы пишем на языке Си89, мы вынуждены записывать объявления переменных до выполняемых операторов, поэтому функция начинается с объявлений:
R05_DEFINE_ENTRY_FUNCTION(FileSize, "FileSize") {
struct r05_node *fname[2];
char filename[FILENAME_MAX + 1];
size_t filename_len;
FILE *f;
long int size;
struct r05_node *callee = arg_begin->next;
Смысл каждой из этих переменных будет ясен по контексту использования.
Переменная callee указывает на узел, следующий за левой угловой скобкой, он
содержит имя функции. Эта переменная понадобится в самом конце.
На стадии сопоставления с образцом мы проверяем, что аргумент удовлетворяет
формату и семантическому ограничению (его длина не превышает FILENAME_MAX),
значение аргумента сохраняется в массиве filename:
/* сопоставление с образцом */
filename_len =
r05_read_chars(fname, filename, FILENAME_MAX, callee, arg_end);
filename[filename_len] = '\0';
if (filename_len == 0) {
r05_recognition_impossible();
}
if (! r05_empty_hole(fname[1], arg_end)) {
struct r05_node *p = fname[1]->next;
while (p != arg_end && p->tag == R05_DATATAG_CHAR) {
p = p->next;
}
if (p == arg_end) {
r05_builtin_error("very long filename");
} else {
r05_recognition_impossible();
}
}
Весь аргумент функции (дырка от callee до arg_end) должен быть именем файла.
Функция r05_read_chars распознает в этой дырке префикс максимальной длины
(но не более FILENAME_MAX), являющийся последовательностью литер, указатели
на этот префикс сохранятся в fname[0] и fname[1].
Вызов r05_read_chars() отделяет от диапазона [fname_b, fname_e] префикс
из литер длины не более FILENAME_MAX, количество прочитанных литер сохраняется
в filename_len. Вызов r05_read_chars() не добавляет концевой нуль к строке,
поэтому его приходится добавлять явно:
filename[filename_len] = '\0';
Если ни одну литеру прочесть не удалось, значит, или аргумент пустой, или он не начинается с литеры — нарушение формата:
if (filename_len == 0) {
r05_recognition_impossible();
}
Дальше тоньше. Если литеры прочитать удалось и все они влезли в буфер, значит сопоставление с образцом прошло успешно и в буфере находится имя файла. В противном случае мы имеем одно из двух: или в аргументе были нелитеры, то есть ошибка отождествления, или цепочка литер слишком длинная, то есть семантическая ошибка. Значит, нужно проанализировать остаток диапазона — является ли он последовательностью одних лишь литер. В цикле перебираем все узлы списка пока не достигнем конца, либо узла-нелитеры. Если достигли конца — семантическая ошибка, иначе — ошибка формата.
if (! r05_empty_hole(fname[1], arg_end)) {
struct r05_node *p = fname[1]->next;
while (p != arg_end && p->tag == R05_DATATAG_CHAR) {
p = p->next;
}
if (p == arg_end) {
r05_builtin_error("very long filename");
} else {
r05_recognition_impossible();
}
}
Вторая стадия специфики Рефала почти не имеет — вызовы стандартных функций с проверками возвращаемого значения:
/* получение объёма файла */
f = fopen(filename, "r");
if (f == NULL) {
r05_builtin_error_errno("Can't open file");
}
if (fseek(f, 0, SEEK_END) != 0) {
r05_builtin_error_errno("Can't seeking to end of file");
}
size = ftell(f);
if (size == -1L) {
r05_builtin_error_errno("Can't telling position of file");
}
if (fclose(f) == EOF) {
r05_builtin_error_errno("Can't close file correctly");
}
Единственный нюанс — каждая из этих функций может устанавливать errno
(стандарт не гарантирует, зависит от реализации), поэтому об ошибке сообщаем
при помощи r05_biltin_error_errno().
Последний этап — построение результата:
/* построение результата */
arg_begin->tag = R05_DATATAG_NUMBER;
arg_begin->info.number = (r05_number) size;
r05_splice_to_freelist(callee, arg_end);
}
Здесь мы превращаем левую угловую скобку в символ-число со значением размера файла, участок от имени функции до правой угловой скобки удаляем из поля зрения.
Можно было написать так:
/* построение результата */
r05_reset_allocator();
r05_alloc_number((r05_number) size);
r05_splice_from_freelist(arg_begin);
r05_splice_to_freelist(arg_begin, arg_end);
}
Можно предположить, что этот вариант окажется медленнее, поскольку требуется
выполнять больше операций, но здесь проблема не в быстродействии — затраты
на обращение к файловой системе гораздо выше. Проблема здесь в том, что
с вызовом r05_alloc_number() функция может завершиться из-за недостатка
памяти, хотя дополнительной памяти ей вовсе не требуется. Поэтому рекомендуется
использовать первый вариант.
Рекомендация. Если функция на Си может повторно использовать часть аргумента для построения результата без дополнительных выделений памяти, и повторное использование не приводит к усложнению функции, то распределения памяти лучше избежать.