6.3. Язык сборки

      6.3.1. Постановка задачи. Вновь обратимся к построению архива веществ, однако теперь выберем другую его модификацию, также описанную в разд. 6.1.6. А именно, допустим, что среди атрибутов веществ встречаются и такие, которые задают поведение вещества в форме фрагмента алгоритма. И пусть в подобных фрагментах, в свою очередь, могут содержаться заявки на добавление новых веществ в формируемую таблицу атрибутов. Рассредоточенный набор тогда становится как бы «саморасширяющимся», поскольку в таблице веществ теперь собираются не только вещества, явно запрошенные в тексте программы, но также и вещества, объявленные во включаемых в программу фрагментах-атрибутах.
      Реализация такого рассредоточенного набора потребует дополнительных усилий. Придется, вообще говоря, многократно повторять процесс сборки таблицы, подключая все новые и новые запрашиваемые вещества. Проблема здесь даже не столько в сложности реализации, сколько в обеспечении ее эффективности. С одной стороны, легко заметить, что подключение новых веществ затрагивает только сравнительно небольшой участок формируемой программы. С другой стороны, универсальному алгоритму сборки выявить такой участок нелегко, особенно в случае, когда подобных «саморасширяющихся» рассредоточенных наборов в программе несколько.
      В связи с этим имеет смысл рассмотреть и немного иную, нетрадиционную организацию сборки. Заботы об эффективности частично перекладываются на разработчика программы. Ведь можно позволить себе реализовать сравнительно простой универсальный алгоритм сборки, если разработчику, желающему добиваться большей эффективности, предоставить инструмент более низкого уровня — язык сборки.
      Создание языка сборки исключительно с целью обслуживания архива веществ было бы, разумеется, неуместным расточительством. Однако приложения этого языка выходят далеко за рамки данной конкретной задачи. С его появлением откроется возможность эффективной реализации самых разнообразных конфигурационных построений. Кроме того, что не менее важно, язык сборки способен разбудить дремлющие конфигурационные фантазии разработчика, а это, вероятно, стимулировало бы формирование, отбор и распространение новых продуктивных расширяемых конструкций.
      Существующие операционные среды, как правило, полностью скрывают свои алгоритмы сборки от разработчика программы. Причина этого, по-видимому, — традиционное пренебрежение обслуживанием расширяемости. Даже на более низком уровне подобные возможности чаще всего предоставляются: наряду с развитыми современными языками разработчику программы обычно доступен и ассемблер, позволяющий эффективно разрешить самые тонкие проблемы уровня операторов. На уровне же модулей в распоряжении разработчика находятся только штатные макропроцессоры, трансляторы и компоновщик, механизмы которых полностью скрыты, и поэтому не может быть и речи об их замене или даже о незначительной модификации.
      В то же время алгоритм сборки программы относительно несложен. Его можно достаточно компактно записать на каком-либо из распространенных языков, если предварительно дополнить этот язык необходимыми здесь типами данных и операциями. Некоторые особенности такого расширения языка мы проиллюстрируем на небольшом примере. Возможно, следовало бы сразу привести полное решение задачи об архиве веществ, сформулированной в начале данного раздела, однако это решение представляется несколько тяжеловатым для первого знакомства с языком. Поэтому мы ограничимся более простым примером сборки, а к архиву веществ вернемся немного позже.
      Как и ранее, здесь не ставится цель дать законченное и строгое описание языка сборки. Вводится только несколько характерных конструкций, позволяющих почувствовать общую направленность языка и достаточных для программирования сравнительно простого варианта сборки. В качестве базового языка выберем Си, и над ним будем надстраивать некоторые типы данных и операции.

      6.3.2. Некоторые конструкции. Прежде всего нам понадобится новый агрегат данных — множество. Множество представляет собой неупорядоченную совокупность произвольного числа однотипных элементов. Встроим множество в Си следующим образом. Описание множества будет выглядеть подобно описанию массива, но вместо квадратных скобок («[», «]») тут записываются угловые («<», «>») и не указывается число элементов.
      Значение множества можно задать явно, перечислив через запятую составляющие его элементы и заключив это перечисление в фигурные скобки. В частности, пустое множество задается в виде «{}». Значение множества может фигурировать не только в описаниях при инициализации переменных, но и в выражениях.
      На множества очевидным образом распространяется действие операций: «+» — объединение множеств, «–» — разность, «=» — присваивание. Множество может записываться в позиции условия, где пустое множество вырабатывает значение «ложь», а непустое — «истина».
      С множеством следовало бы, вообще говоря, связать особый вид оператора цикла, осуществляющий последовательный перебор всех составляющих множество элементов. Однако в нашем примере такой оператор не потребуется, и поэтому определять его мы не будем.
      Для манипулирования множествами введем еще три встроенных функции. Функция in

int in(тип_элемента set<>, тип_элемента elem);

определяет, принадлежит ли множеству set элемент elem, и выдает значение «1» («истина»), если принадлежит, и «0» («ложь») — в противном случае. Функция count

int count(тип_элемента set<>);

подсчитывает и выдает в качестве своего значения число элементов множества set. Функция one_of

тип_элемента one_of(тип_элемента set<>);

определена только для непустого множества и выдает в качестве значения один из элементов этого множества.
      Агрегаты данных, подобные только что введенному нами множеству, — не редкость в современных языках программирования. Но там (например, в Модуле-2) чаще имеется в виду множество ограниченного размера, допускающее благодаря этому простую и предельно эффективную реализацию. Для наших же целей существенна именно произвольность размеров множества, позволяющая, в частности, определять как множество любую совокупность весьма многочисленных объектов, хранящихся в программном фонде.
      Важная особенность вводимого множества заключается в том, что тут не делается различий между элементами, располагаемыми в оперативной и во внешней памяти. Оказывается, что таким образом можно практически без потери эффективности радикально сократить размеры реализующих сборку алгоритмов, разгрузив их от явных операторов обмена с внешней памятью. (Подобные приемы нередко применяются в алгоритмических языках, ориентированных на работу с базами данных.)
      Для нашего примера достаточно будет считать, что в программном фонде хранятся объекты двух типов: модули трансляции (transl) и входные точки (entry). Модули трансляции являются первичными объектами, а входные точки — вторичными, отражающими атрибуты имеющихся в фонде модулей трансляции. Каждый объект программного фонда имеет идентификатор, представляемый значением типа ident (например, восьмисимвольной строкой).
      Модуль трансляции отображается в структуру следующего вида:

где name — идентификатор модуля, entry — множество идентификаторов входных точек модуля, extrn — множество идентификаторов внешних ссылок модуля.
      Входные точки имеют вид

где name — идентификатор входной точки, а transl — множество ссылок на модули трансляции, в которых определена точка входа с данным идентификатором. Предполагается, что объекты типа entry автоматически создаются, корректируются и уничтожаются по мере включения в программный фонд и исключения из него модулей трансляции.
      Наконец, потребуются две функции для работы с объектами программного фонда. Первая из них, get_entry

struct entry *get_entry(ident name);

выдает в качестве значения ссылку на хранящийся в программном фонде объект типа entry с указанным идентификатором. Если объекта с таким идентификатором нет, выдается пустая ссылка.
      Вторая функция, add_transl

void add_transl(struct transl *module);

реализует включение в формируемую программу указанного модуля трансляции. В частности, add_transl берет на себя заботы по предупреждению препроцессирования и трансляции для ранее обрабатывавшихся модулей.

      6.3.3. Реализация корневой компоновки. Теперь мы располагаем всем необходимым для того, чтобы перейти к небольшому примеру использования языка сборки. Запишем с помощью этого языка решение задачи сборки для одного из вариантов корневой схемы компоновки (см. разд. 4.10.4).
      Пусть в программном фонде хранятся объекты только двух упомянутых выше типов: модули трансляции и входные точки. Для каждого из модулей трансляции известно множество идентификаторов его входных точек и внешних ссылок. Требуется написать функцию linkage, осуществляющую сборку программы. (При таком составе программного фонда не нужно препроцессирование, сборка сводится к трансляции и компоновке — поэтому и был выбран идентификатор linkage.)
      Головной модуль собираемой программы указывается в качестве параметра main функции linkage. Все модули трансляции, которые требуется включить в собираемую программу, должны быть подвергнуты обработке с помощью только что введенной нами функции add_transl. Кроме того, функция linkage формирует два выходных параметра, диагностирующих причины возможной неудачи сборки: множество unresolved не разрешенных в ходе сборки ссылок и множество ambiguous неоднозначно разрешимых ссылок.
      Решение данной задачи можно записать в виде

void linkage /* сборка программы */ (
  /* вход */
    struct transl *main,        /* головной модуль трансляции */
  /* выход */
    ident (*unresolved)<>,      /* неразрешенные ссылки */
    ident (*ambiguous)<>        /* неоднозначно разрешимые
                                 * ссылки */
{
  struct transl *module = main; /* модуль трансляции */
  ident handling<> = {};        /* еще не обработанные ссылки */
  ident ref;                    /* обрабатываемая ссылка */
  ident linked<> = {};          /* разрешенные ссылки */
  struct entry *entry;          /* входная точка */
  for (;;) {
    if (module) {
      add_transl(module);
      linked += module–>entry;
      handling += module–>extrn;
      module = (void*)0;
    }
    if (!handling)
      break;                 /* ==> все ссылки обработаны ==> */
    ref = one_of(handling);
    handling –= {ref};
    if (in(linked, ref))
      continue;               /* ––> ссылка уже разрешена ––> */
    entry = get_entry(ref);
    if (!entry) {
      *unresolved += {ref};
      continue;                 /* ––> ссылка неразрешима ––> */
    }
    if (count(entry–>transl) != 1)
      *ambiguous += {ref};
    module = one_of(entry–>transl);
  } /* for */
} /* linkage */

      Для того чтобы избежать дублирования некоторых операторов, пришлось воспользоваться циклом с выходом из середины. Тело цикла начинается с подключения очередного модуля (если это необходимо). Модуль включается в собираемую программу (add_transl); его входные точки добавляются к множеству разрешенных ссылок, а его внешние ссылки — к множеству еще не обработанных ссылок.
      Затем, если все ссылки обработаны, цикл сборки завершается. Если же остались необработанные ссылки, то выбирается одна из них и исключается из числа необработанных. Если ссылка уже разрешена, то переходим к следующей ссылке, т. е. цикл повторяется. В противном случае из программного фонда извлекается (get_entry) соответствующая структура entry. Если такой структуры нет, то ссылка неразрешима и можно переходить к следующей ссылке.
      Если же соответствующая структура entry нашлась, то анализируется число модулей трансляции (count), содержащих рассматриваемую входную точку. Такой модуль должен быть единственным, иначе ссылка трактуется как неоднозначно разрешимая. Далее выбирается (случайным образом) один из содержащих рассматриваемую входную точку модулей трансляции, в результате чего очередное повторение цикла начнется с подключения этого модуля.
      Завершение цикла означает, что сборка программы закончена.
      Итак, с помощью предложенного языка одну из простейших модификаций сборки удалось записать достаточно компактно. Теперь можно вернуться к архиву веществ.

      6.3.4. Реализация архива веществ. Напомним обстоятельства, послужившие нам первоначальным стимулом для обращения к языку сборки. При реализации архива веществ, допускающего в качестве атрибутов веществ алгоритмические фрагменты, возникли определенные сложности. Точнее, сложности вызывали не сами алгоритмические фрагменты, а то, что они, будучи вставленными в программу, могли в свою очередь выдать заявки на пополнение рассредоточенного набора веществ. Таким образом, рассредоточенный набор становился «саморасширяющимся», т. е. в него включались не только вещества, непосредственно объявленные в программе, но и вещества, объявляемые в алгоритмических фрагментах, извлекаемых из архива.
      Эффективная реализация «саморасширяющегося» рассредоточенного набора в рамках универсальной штатной процедуры сборки программы представляется неоправданно трудоемкой. Значительно проще переложить заботы о повышении эффективности сборки на разработчика, вооружив его таким тонким и действенным инструментом, как язык сборки. Более того, при наличии данного языка можно даже позволить себе вовсе не реализовывать в штатной процедуре сборки некоторые сравнительно редкие ситуации, подобные интересующему нас сейчас «саморасширяющемуся» набору.
      С помощью языка сборки разработчик способен запрограммировать алгоритм самой деликатной части обработки «саморасширяющегося» набора — выявления окончательного состава всех необходимых веществ. Полное описание такого алгоритма на языке сборки, вероятно, утомило бы даже самого заинтересованного читателя, поэтому мы здесь наметим только основные его компоненты.
      Прежде всего, алгоритм будет иметь дело с составом программного фонда, существенно более богатым по сравнению с рассмотренным только что (см. разд. 6.3.3) примером. Наряду с модулями трансляции в фонде содержатся другие виды модулей, в частности элементы регулярного набора веществ. Так же как и в рассмотренном примере, каждому объекту программного фонда сопоставляется определенная структура, поля которой содержат значения отдельных используемых при сборке атрибутов этого объекта.
      В число атрибутов объектов входят и записанные в их текстах объявления элементов рассредоточенного набора. Таким образом, для того чтобы сформировать полный набор объявленных веществ, достаточно просмотреть записи всех включаемых в формируемую программу объектов, собирая воедино все содержащиеся в них поля объявленных элементов.
      Как и ранее, препроцессирование и трансляцию отдельных модулей трансляции выполняет встроенная в язык сборки функция add_transl (см. разд. 6.3.2). Предполагается, что add_transl должна вызываться только тогда, когда выявлены составы всех рассредоточенных наборов, гнезда которых находятся в тексте указанного модуля трансляции. Разумеется, наличие наборных гнезд также отражено в структурах, сопоставленных объектам программного фонда, т. е. все эти сведения доступны на уровне языка сборки.
      Основное отличие алгоритма сборки, обслуживающего «саморасширяющийся» набор, от алгоритма, разобранного в разд. 6.3.3, заключается в том, что модули трансляции, содержащие «саморасширяющиеся» наборные гнезда, могут обрабатываться несколько раз. Однократной обработки, вообще говоря, недостаточно, поскольку она выполняется исходя из текущего состава «саморасширяющегося» набора, а этот состав — не окончательный, он может затем пополниться новыми элементами при обработке данного или соседних модулей.
      Приведенные соображения, возможно, не настолько подробны и конкретны, чтобы ответить на все возникающие вопросы, но они все же позволяют заключить, что реализация архива веществ на языке сборки — не такая уж сложная задача. С ней легко справится любой квалифицированный программист, тем более что в качестве каркаса он может использовать элементы разобранной нами программы из разд. 6.3.3.
      Более внимательный анализ позволяет провести и более глубокую параллель с алгоритмом из разд. 6.3.3. Ведь и там, по сути дела, был реализован «саморасширяющийся» рассредоточенный набор. В качестве объявлений элементов выступали внешние ссылки модуля, в качестве регулярного однородного набора — хранящиеся в программном фонде модули трансляции (содержащие, в свою очередь, внешние ссылки — объявления элементов). Алгоритм определял окончательный состав рассредоточенного набора, задающий подмножество модулей трансляции, образующее выполняемую программу.

      6.3.5. Место языка сборки. То, что языку сборки отведено место в заключительной части книги, отнюдь не означает, что этот язык является апофеозом всех мыслимых конфигурационных построений. Напротив, он играет весьма скромную, чисто техническую роль конфигурационного ассемблера, к услугам которого придется прибегать сравнительно редко.
      Вместе с тем сфера применения языка сборки не ограничивается рамками рассмотренных выше модификаций рассредоточенного набора — она существенно шире. Реализация языка восполнила бы заметный пробел в современном штатном системном обеспечении. Дело в том, что до сего времени круг понятий всей области расширяемых программ далеко не стабилизировался. Поэтому говорить о какой-либо полноте соответствующих средств поддержки высокого уровня было бы преждевременно. В отдельных ситуациях штатные средства могут пока еще оказаться бессильными или неэффективными, и в такой обстановке представляется вполне уместным обращение к помощи языка сборки для решения любых нетривиальных конфигурационных задач.