Этюды для программистов

28. Новый атТРАКцион, или... ПОСТРОЕНИЕ ИНТЕРПРЕТАТОРА ЯЗЫКА ТРАК

Немного найдется языков программирования, которые начинающий программист мог бы реализовать в одиночку всего за несколько недель, но Трак (TRAC) [58] — как раз такой язык. Целью разработчика Трака Калвина Муэрса было создание простого, элегантного, мощного и к тому же интерактивного языка. Он ухитрился на основе старой идеи макро сделать язык, который удовлетворяет всем этим требованиям, может использоваться также в пакетном режиме и вдобавок ко всему необычайно прост для реализации (для написания первого процессора хватило двух выходных дней). Для набора и редактирования рукописи английского оригинала книги использовался некоторый диалект языка Трак.

Представьте, что перед вами интерактивный терминал, который позволяет работать с процессором Трака. Вы набираете свои программы на клавиатуре, переходя, если нужно, с одной строки на другую и заканчивая каждую программу специальной заключительной металитерой (первоначально это апостроф '); эти программы сразу же выполняются. Как только процессор встречает металитеру, он интерпретирует вашу программу и выдает результаты работы на терминал. После этого вы можете набрать новую программу, вызывая тем самым повторение этого цикла. Сама программа может представлять собой любую цепочку литер, но некоторые специальные подцепочки служат для вызова встроенных функций Трака. Функции можно использовать для самых обычных действий с числами или с текстами, но они могут также записывать или извлекать результаты других функций, так что из их значений можно сложить огромные пирамиды. Вызов функции выглядит как #(…) или ##(…), причем внутри скобок снова стоит произвольная цепочка. Тело функции разбито запятыми на аргументы (отсутствие запятых означает, что имеется один аргумент), вычисляемые слева направо по тем же правилам, что и вся программа. Предполагается, что первым аргументом является имя встроенной функции, остальные аргументы передаются этой функции для вычисления значения. Если вызов функции записан с одним диезом в виде #(...), то результат функции повторно сканируется, в противном случае результат передается дальше без обработки. Запись (...), где в цепочке внутри скобок соблюдается баланс скобок, защищает эту цепочку от вычисления. Процессор просто удаляет внешние скобки и оставляет внутренность без внимания. Так, если ум означает функцию умножения, а сл — функцию сложения, то результатом вычисления входной цепочки

((3 + 4)) * 9 = # (ум, # (сл, 3, 4), 9)'

будет цепочка

(3+4)*9 = 63

Обратите внимание на вторую пару скобок вокруг 3 + 4; они необходимы, чтобы в выходной цепочке 3 + 4 осталось заключенным в скобки.

Все действия процессора подчиняются точно сформулированной процедуре, называемой алгоритмом Трак. Процессор содержит три структуры: активную цепочку, нейтральную цепочку и указатель сканирования. Для наглядности обычно считают, что нейтральная цепочка располагается слева, указатель сканирования — посередине и активная цепочка — справа. Указатель сканирования всегда указывает на левый конец активной цепочки, обозревая первую литеру. Литеры, как правило, переходят из активной в нейтральную цепочку; там литеры накапливаются до тех пор, пока их не станет достаточно для построения всех аргументов некоторой функции. Тогда эта функция выполняется и ее результат помещается в активную или нейтральную цепочку в соответствии с типом функции.

Алгоритм состоит из 10 пронумерованных шагов. Работа процессора начинается с шага 1. В алгоритме кое-где говорится о различных отметках литер нейтральной цепочки. Представляйте себе эти отметки как флажки, поставленные у отмеченных литер (конечно, в реализации отметки будут представлены, вероятно, указателями). В любой практической реализации существует специальная клавиша «прерывание» для прекращения бесконечного цикла, предписанного алгоритмом.

1. Очистить процессор; для этого опустошить нейтральную цепочку, удалить содержимое активной цепочки, если оно есть, поместить туда цепочку # (пц, # (чц)) и установить указатель сканирования на первую литеру активной цепочки [59]. Перейти к следующему шагу.

2. Проанализировать литеру, на которую указывает указатель сканирования. Если ее нет, т. е. активная цепочка пуста, вернуться к шагу 1.

3. Если под указателем сканирования — литера табуляции, перевода строки, конца записи или возврата каретки, то удалить ее, продвинуть указатель к следующей литере и вернуться к шагу 2.

4. Если под указателем сканирования — левая скобка, то удалить ее и просмотреть активную цепочку вперед, пока не будет найдена соответствующая ей правая скобка. Переместить в неизменном виде все расположенные между этими скобками литеры в нейтральную цепочку, удалить правую скобку, продвинуть указатель сканирования вперед к следующей за ней литере и после этого вернуться к шагу 2. Если соответствующую правую скобку не удается найти, то вернуться к шагу 1.

5. Если литера, находящаяся под указателем сканирования,— запятая, то удалить ее, пометить самую правую литеру нейтральной цепочки как конец одного аргумента, а следующую литеру — как начало нового аргумента, продвинуть вперед указатель сканирования и вернуться к шагу 2.

6. Если под указателем сканирования — знак диез, а следующая литера — левая скобка, то это означает, что перед нами — начало активной функции. Удалить диез и скобку, продвинуть указатель сканирования после них, отметить самую правую литеру нейтральной цепочки одновременно как начало аргумента и начало активной функции и вернуться к шагу 2.

7. Если под указателем сканирования — знак диез и вслед за ним стоят еще один диез и левая скобка, то это значит, что начинается нейтральная функция. Удалить три литеры ##(, продвинуть указатель после них, отметить самую правую литеру нейтральной цепочки одновременно как начало аргумента и начало нейтральной функции и вернуться к шагу 2.

8. Если под указателем сканирования находится знак диез, но условия шагов 6, 7 не выполняются, то переместить диез в правый конец нейтральной цепочки, передвинуть указатель и вернуться к шагу 2.

9. Если под указателем сканирования оказалась правая скобка, это говорит об окончании функции. Удалить эту скобку, передвинуть указатель сканирования и отметить самую правую литеру нейтральной цепочки как конец аргумента и конец функции. Теперь нейтральная цепочка от самой правой отметки начала функции до только что поставленной отметки конца функции составляет вызов функции Трака. (Если в нейтральной цепочке нет отметки начала функции, то вернуться к шагу 1.) Удалить из нейтральной цепочки аргументы функции (все те аргументы, отметки которых стоят после отметки начала функции) вместе с отметками функции и аргументов. (Ввиду способа нанесения отметок все отметки начала стоят в действительности у литер, непосредственно предшествующих отмечаемым элементам.) Предполагается, что первым аргументом является имя встроенной функции Трака. Вычислить функцию с данными аргументами; лишние аргументы игнорируются, недостающие аргументы автоматически добавляются со значением «пустая цепочка». Значение функции присоединяется справа к нейтральной цепочке, если функция была отмечена как нейтральная, и слева к активной цепочке, если функция была отмечена как активная; в последнем случае указатель сканирования устанавливается на левый конец новой активной цепочки. Если первый аргумент не является именем никакой встроенной функции, то просто поместить в качестве результата функции пустую цепочку. Вернуться к шагу 2.

10. Если литера под указателем сканирования не удовлетворяет ни одному из условий шагов с 3-го по 9-й, то присоединить ее к правому концу нейтральной цепочки, удалить ее из активной цепочки, передвинуть указатель сканирования и вернуться к шагу 2.

Ниже перечислены функции Трака в активной записи, но все они могут вызываться также и в нейтральном режиме. У функции всегда есть значение в виде цепочки, однако функциям не возбраняется выдать в качестве значения пустую цепочку; в особенности это имеет смысл для тех функций, результат которых выражается в побочных эффектах. В дополнение к уже упомянутым структурам процессор может записывать цепочки в некоторой области памяти, называемой памятью бланков. Каждый бланк состоит из трех частей: имени бланка, в качестве которого может выступать любая цепочка, тела бланка, которое тоже может быть любой цепочкой, и указателя бланка, первоначально указывающего на позицию непосредственно перед первой литерой тела бланка. Указатель бланка всегда указывает на позицию непосредственно перед телом, непосредственно после него или между двумя литерами; иначе говоря, он всегда указывает на промежуток между литерами. В телах бланков вперемежку с литерами могут находиться порядковые метки сегментов. С каждой такой меткой связано некоторое положительное целое число, причем эти числа у разных меток не обязаны различаться. Приведенные ниже описания функций слегка переработаны в сравнении с предложениями Муэрса:

#чц «Чтение цепочки» (один аргумент). Значением этой функции является входной поток литер до ближайшей литеры (не включая ее). В результирующую цепочку входят все возвраты каретки, переводы строк, концы записей и литеры табуляции, которые система передает программе в обычных условиях. Металитера всегда отбрасывается, а в системах, ориентированных на использование записей, отбрасывается также и все после металитеры в той же записи.

#чл «Чтение литеры» (один аргумент). В качестве значения функции выдается следующая входная литера, какой бы она ни оказалась. Этим способом можно прочитать любую литеру, включая металитеру.

#(пц,X) «Печать цепочки» (два аргумента). Второй аргумент X печатается на устройстве вывода. Значением функции является пустая цепочка.

#(им,X) «Изменение металитеры» (два аргумента). Эта функция с пустым значением (со значением «пустая цепочка») делает металитерой первую литеру цепочки X. Первоначально роль металитеры играет апостроф.

#(оц,N,В) «Определение цепочки» (три аргумента). Эта функция с пустым значением создает бланк с именем N и телом В. Указатель этого бланка указывает на точку перед первой литерой В. Если бланк с именем N уже существовал, то его предыдущее тело и указатель теряются.

#(сц,N,P1,P2,...) «Сегментация цепочки» (не менее трех аргументов). Эта функция с пустым значением создает в бланке N порядковые метки сегментов. Непустые аргументы Р1, Р2, ... обрабатываются поочередно, слева направо (пустые аргументы игнорируются). Обработка одного аргумента Pi состоит в следующем. Тело бланка N просматривается слева направо, пока не будет найдена подцепочка, в точности равная Pi Эта подцепочка не должна содержать никаких ранее поставленных меток сегментов. Если это так, то подцепочка выбрасывается из тела бланка и на ее место ставится порядковая метка сегмента с номером i. Затем процесс поиска совпадающей подцепочки возобновляется с литеры, лежащей вслед за меткой. После окончания сегментации указатель бланка устанавливается на левый конец бланка. Можно несколько раз сегментировать один бланк.

#(вц,N,А1,А2,...) «Вызов цепочки» (два или больше аргументов). Значением этой функции является тело бланка N, в котором метки сегментов заменены на некоторые подцепочки. Все метки с номером 1 заменяются на аргумент А1, метки с номером 2 — на А2 и т. д. Функции вц требуется такое количество аргументов, каков наибольший номер сегмента в бланке N. Напомним, что лишние аргументы игнорируются, а недостающие считаются пустыми цепочками.

#(вс,N,Z) «Вызов сегмента» (три аргумента). Значением этой функции является подцепочка бланка N от текущего положения указателя бланка до ближайшей справа метки сегмента (в данной функции конец тела рассматривается как метка). Метка не входит в значение функции; указатель бланка помещается непосредственно перед литерой, ближайшей справа к найденной метке. Если перед выполнением функции указатель бланка уже указывал на правый край тела, то значением функции будет аргумент Z, возвращаемый в активном режиме, независимо от режима вызова функции.

#(вл,N,Z) «Вызов литеры» (три аргумента). Значением функции является литера, лежащая сразу вслед за указателем бланка в бланке N. Указатель передвигается в промежуток, следующий за выбранной литерой. Указатель бланка пропускает все метки сегментов, поскольку они — не литеры. Если указатель бланка уже указывает на правый край цепочки, то в качестве значения функции выдается аргумент Z в активном режиме независимо от режима вызова функции.

#(вн,N,D,Z) «Вызов нескольких литер» (четыре аргумента). Значением функции является подцепочка бланка N. Эта подцепочка начинается от текущего положения указателя бланка и содержит |D| литер вправо от него, если D положительно, или влево, если D отрицательно [60]. Литеры в значении функции расположены в том же порядке, что и в теле бланка, т. е. при отрицательном D цепочка не обращается. Метки сегментов, конечно, игнорируются. Указатель бланка передвигается в точку между выбранной подцепочкой и первой непрочитанной литерой в заданном направлении. (Если D равно нулю, то значением будет пустая цепочка, а указатель останется на месте.) Если указателю бланка приходится покинуть цепочку на любом из концов, то значением функции будет аргумент Z, помещаемый в активную цепочку, независимо от режима вызова функции.

#(вн,N,X,Z) «Первое совпадение» (четыре аргумента). Бланк N просматривается вправо от указателя бланка в поисках подцепочки, совпадающей с X и не содержащей меток сегментов. Если такое совпадение найдено, то значением функции будет подцепочка бланка от исходного положения указателя до литеры, находящейся непосредственно перед совпадающей подцепочкой (из значения удаляются метки сегментов), а указатель бланка будет переставлен так, чтобы указывать на позицию непосредственно перед литерой, находящейся непосредственно после совпавшей подцепочки. Если совпадения не найдено, то значением функции будет аргумент Z в активном режиме независимо от режима вызова функции, а указатель бланка останется на прежнем месте.

#(пу,N) «Переустановка указателя» (два аргумента). Эта функция с пустым значением возвращает указатель бланка N в его исходное положение перед первой литерой бланка.

#(уо,N1,N2…) «Удалить определение» (два или более аргумента). Эта функция с пустым значением удаляет бланки с именами N1, N2, … из памяти бланков.

#(ув) «Удалить все» (один аргумент). Эта функция с пустым значением удаляет из памяти бланков все бланки.

Трак выполняет арифметические действия над цепочками из «десятичных» литер. У каждой цепочки имеется арифметическое значение. Оно определяется наиболее длинной подцепочкой, примыкающей к правому краю цепочки и состоящей только из десятичных цифр, перед которыми стоит не более одного знака плюс или минус. Так, арифметическим значением 3 является три, значением а — 4 является минус четыре, + + + +200 имеет значение двести, а значением пустой цепочки и abc является пустая цепочка. В арифметических операциях пустая цепочка воспринимается как нуль. Точность арифметических действий не ограничена — мы не должны подстраиваться под ограничения какой-либо реальной аппаратуры. Результат арифметических операций также будет содержать десятичную цепочку того же вида без старших нулей и без плюса для положительных чисел; нуль будет представлен как 0.

#(сл,А,В) «Сложение» (три аргумента). Значением функции является сумма арифметических значений аргументов, перед которой помещена начальная нечисловая часть аргумента А. Начальная часть аргумента В теряется.

#(вч,А,В) «Вычитание» (три аргумента). Значением функции является результат вычитания арифметического значения аргумента В из арифметического значения А; начальная нечисловая часть А присоединяется спереди к полученной десятичной цепочке, а начальная часть В теряется.

#(ум,А,В) «Умножение» (три аргумента). Значением функций является произведение арифметических значений аргументов А и В, перед которым помещена начальная нечисловая часть А. Начальная часть В теряется.

#(дл,А,В,Z) «Деление» (четыре аргумента). Значением функции является частное от деления числового значения аргумента А на числовое значение В, перед результатом помещается начальная часть А. Начальная часть В теряется. Выполняется целочисленное деление, у частного сохраняется только целая часть; остаток всегда неотрицателен. Если В имеет значение нуль, то значением функции будет аргумент Z в активном режиме независимо от режима вызова функции.

Аналогично арифметическим значениям в Траке функционируют логические значения. Логическим значением цепочки считается наиболее длинная ее правая часть, состоящая целиком из нулей и единиц, т. е. являющаяся двоичной цепочкой. Так, цепочка abc0100 имеет логическое значение 0100, цепочка 1234567890 — значение 0, цепочка 43210—10, а логическим значением abc является, по определению, пустая цепочка.

#(ло,А,В) «Логическое объединение» (три аргумента). Значением этой функции является побитовое логическое объединение Логических значений аргументов А и В. Если они имеют разные длины, то более короткое дополняется слева необходимым количеством нулей для уравнивания длин. Любые нелогические начальные части аргументов теряются.

#(лп,А,В) «Логическое пересечение» (три аргумента). Значением функции является побитовое логическое пересечение логических значений аргументов Л и В. Если аргументы имеют неравные длины, то более длинный усекается слева для выравнивания длин. Любые нелогические начальные части аргументов теряются.

#(лд,А) «Логическое дополнение» (два аргумента). Значение этой функции — побитовое логическое дополнение аргумента А, имеющее ту же длину. Нелогическая начальная часть аргумента теряется.

#(лс,S,А) «Логический сдвиг» (три аргумента). Значением этой функции является сдвинутое логическое значение аргумента A. Величина сдвига дается арифметическим значением аргумента S. Если оно положительно, то происходит сдвиг влево, если отрицательно — то вправо. Значение функции имеет ту же длину, что логическое значение A; освобождающиеся позиции заполняются нулями. Нелогическая начальная часть А теряется.

#(лц,S,А) «Логический циклический сдвиг» (три аргумента). Значением функции является результат циклического сдвига (поворота) логического значения аргумента А. Величина сдвига задается арифметическим значением аргумента S; сдвиг происходит влево, если значение S положительно, и вправо, если оно отрицательно. Циклический сдвиг не меняет длины аргумента. Нелогическая начальная часть А теряется.

#(рв,A,B,T,F) «Равенство» (пять аргументов). Если аргумент А в точности совпадает как цепочка с аргументом В, то значением функции является аргумент Г, в противном случае значение функции — аргумент F. Отметим, что Т и F могут быть любыми цепочками.

#(бл,A,B,T,F) «Больше» (пять аргументов). Значением этой функции является аргумент Т, если арифметическое значение А больше арифметического значения В, и аргумент F в противном случае.

#(зб,A,F1,F2…) «Запись блока» (три или больше аргументов). Функция записывает бланки с именами F1, F2, ... на некоторое внешнее запоминающее устройство. После записи всех бланков они удаляются из памяти бланков и создается новый бланк с именем A, тело которого есть адрес во внешней памяти записанного блока бланков. Если уже есть бланк с именем A, то его старое значение теряется. «Адресом» блока должна быть цепочка; доступ к бланкам во внешней памяти осуществляется при помощи любого бланка, имеющего значением цепочку-адрес. Значение этой функции — пустая цепочка.

#(иб,A) «Извлечь блок» (два аргумента). Эта функция с пустым значением извлекает из внешней памяти блок бланков, «адрес» которого находится в теле бланка с именем А. Бланки возвращаются в память бланков, и если какие-либо из них уже существуют, то прочитанные значения заменяют их старые значения. Внешний блок бланков по-прежнему остается доступным.

#(уб,А) «Удалить блок» (два аргумента). Эта, функция с пустым значением освобождает внешнюю память, в которой хранится блок по адресу, указанному в теле бланка А; этот блок становится недоступным. Одновременно удаляется бланк А.

#(си,S) «Список имен» (два аргумента). Значение этой функции— список имен всех бланков, присутствующих в данный момент в памяти бланков. Имена разделяются цепочкой S.

#(пб,N) «Печать бланка» (два аргумента). Эта функция с пустым значением печатает тело бланка N; на печать выдаются также указатель бланка и метки сегментов. Муэрс предлагает печатать указатель бланка в виде <↑>, а метку сегмента — в виде <i>. Таким образом, результатом пб может быть нечто вроде aB<2>cdE<1><↑><1>hiJ; мы видим одно вхождение метки 2 и два вхождения метки 1.

#(вт) «Включение трассировки» (один аргумент). Эта функция с пустым значением заставляет процессор начать трассировку выполнения функций. Всякий раз, когда функция готова к выполнению, на устройство вывода выдаются все ее аргументы. Если процессор работает в интерактивной системе, то после печати каждого списка аргументов делается пауза, позволяющая пользователю ввести некоторую цепочку. Если это будет пустая цепочка, то процессор продолжает работу, вычисляя функцию; любая другая цепочка вызывает переход к шагу 1 алгоритма Трак.

#(кт) «Выключение (конец) трассировки» (один аргумент). Эта функция с пустым значением выключает трассировку; если трассировка не была включена, то выполнение функции не оказывает никакого воздействия.

Следующие примеры помогут вам почувствовать некоторые возможности языка Трак. Не думайте, однако, что эти конкретные примеры иллюстрируют все возможности каких-либо функций.

Выполнение первой строки из этого ряда программ (заметьте, что каждая строка оканчивается металитерой — апострофом) приводит к запоминанию бланка с именем АА и телом Кот и к печати пустой цепочки. Вторая строка аналогичным образом создает бланк с телом #(вц,АА) и именем ВВ и печатает пустую цепочку. Дальше начинается самое интересное. Функция пц в третьей строке печатает #(вц,ВВ), поскольку внутренняя функция защищена скобками; та же функция в четвертой строке печатает #(вц,АА), поскольку внутренняя функция — нейтральная и, наконец, при выполнении пятой строки печатается Кот.

Эта программа делает точно то же, что и вызов #(ув). Аргументами уо должны быть имена бланков, и си генерирует список имен, разделенных запятыми.

В этих трех строках стандартным рекурсивным способом определяется функция факториал, цепочка Факториал сегментируется по аргументу X и затем вычисляется значение 5!. Необходимы обе пары защитных скобок; внешняя защищает рв от выполнения в момент создания бланка, а внутренняя позволяет избежать умножения в случае истинности условия. Попытайтесь удалить любую из этих пар скобок или заменить вызов рв на нейтральный.

Этот пример делает то же, что предыдущий — определяет функцию факториал и вычисляет 5!. Однако здесь используется то, что аргументы функции вычисляются до вычисления самой функции; это позволяет спрятать определение и сегментацию бланка Факториал внутрь его вызова. Отметим, что после аргумента 5 вызова Факториал не нужно ставить запятую, поскольку он всегда возвращает в качестве значения пустую цепочку.

Тема. Напишите процессор Трака для вашей системы. Процессор должен реализовывать описанные выше алгоритм Трак и встроенные функции. Если в вашей системе имеется возможность хранения файлов, используйте ее для организации внешней памяти бланков. Блоки, записанные в каком-либо сеансе работы с процессором, должны быть доступны в последующих сеансах. Разумно будет включить в ваш процессор как можно больше внутренних средств отладки. Рекомендации исполнителю. В каждой системе приняты свои соглашения относительно набора литер и способа завершения строки. Один из шагов алгоритма Трак выбрасывает из сканируемого текста незащищенные литеры возврата каретки, перевода строки и табуляции. Это позволяет спокойно вводить исходные данные, не думая о возможности случайного разбиения программы на несколько строк вследствие ограничений на длину строки физических устройств. Но выбрасывание этих литер означает также, что их следует явно указывать во входном потоке, чтобы мы могли при желании управлять форматом вывода программы. Так, например, если CR-LF обозначает последовательность литер «возврат каретки — перевод строки», то при вводе цепочки Один CR-LF Два мы увидим на печати ОдинДва в одной строке, в то же время исходные данные Один(CR-LF)Два приведут к печати слова Один на одной строке, а Два — на следующей. Позаботьтесь о том, чтобы ваш процессор правильно работал в этой ситуации. Описывая алгоритм, мы лихо проскочили вопрос об установке и поиске меток аргументов и функций в нейтральной цепочке. На самом деле весьма важно всегда иметь точный список функций и аргументов, в котором указан, в частности, порядок их появления. Проще всего добиться этого с помощью стека. Этим стеком распоряжается исключительно процессор. Каждый раз, когда алгоритм выполняет шаг 1, стек устанавливается в пустое состояние. При маркировке любого начала функции на стек помещается новый блок функции. В блоке функции имеется основная часть постоянного вида, включающая, как минимум, положение в стеке ближайшего нижнего, блока функции, режим вызова данной функции, положение в нейтральной цепочке первой литеры функции, число аргументов функции, обработка которых начата, и число законченных аргументов и положение в нейтральной цепочке начала аргумента, который в данный момент сканируется. Выше постоянной части в стеке располагаются элементы, указывающие для каждого законченного аргумента его начало и конец. Часть этой информации может неявно присутствовать в других местах. Среди типичных ошибок реализации — неправильная работа с пустой цепочкой и потеря информации о функциях, расположенных в нижней части стека, при обработке вышележащих функций.

Память бланков точно так же требует большего внимания, чем ей уделялось в предшествующем изложении. Поскольку как имя, так и тело бланка представляют собой цепочки, имеет смысл хранить их вместе в некоторой разновидности памяти для цепочек. Необходимо также место, где хранились бы указатель бланка и метки сегментов; кроме того, нужно уметь находить бланки. В такой ситуации проще всего выделить достаточно большое пространство бланков и хранить бланки в виде связанного списка. У каждого бланка будет головная часть фиксированного размера; она будет включать указатель на следующий бланк, указатель бланка, начальную позицию и длину имени бланка, а также начало и длину тела. Имя и тело можно хранить сразу вслед за головной частью, а метку сегмента можно представлять некоторой парой литер, окружающих целое число (конечно, необходимо иметь какой-либо другой способ изобразить литеры метки как обычные литеры). Для выполнения поиска бланка можно пройти по списку бланков, а для исключения бланка можно удалить его из списка с помощью перестановки указателей, а затем передвинуть окружающие бланки, чтобы заполнить образовавшуюся дыру. Существуют и другие способы организации памяти бланков; каждому способу присущи свои достоинства и недостатки.

Распределение памяти для процессора также не простая задача. Потребность в памяти для любой из структур — нейтральной цепочки, активной цепочки, стека аргументов и памяти бланков — может превзойти любую заранее установленную границу. Если для этих структур выделяются фиксированные области памяти, то любая из них может переполниться, в то время как в остальных свободного пространства будет хоть отбавляй. Имеется стандартный путь решения этой проблемы. Рассмотрим сначала нейтральную и активную цепочки. Поскольку нейтральная цепочка естественно смотрится слева от активной, выделим им одну область памяти на двоих; в этой области нейтральная цепочка будет расти от левого края вправо, а активная цепочка, наоборот, от правого края влево. При таком способе действий переполнение памяти не наступит, пока активная и нейтральная цепочки не используют в сумме всю выделенную им память. Стек аргументов можно таким же образом объединить с памятью бланков; один из двух промежутков между объединенными парами можно использовать для временного хранения цепочек, переписываемых с одного места на другое.

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

Обсуждая распределение памяти, мы считали, что нам удастся урвать большой аморфный кусок памяти, в котором можно хранить все, что нам будет угодно: литеры, указатели, целые числа, логические флажки и т. д. В языках программирования, по крайней мере в таких, как Паскаль или Алгол, это весьма затруднительно, если вообще возможно. Конечно, в языке ассемблера вся память аморфна, но платой за такую свободу обычно бывают ошибки в обращениях к памяти. Очень часто приходится выбирать между удобством и безопасностью; обычно находят какое-либо компромиссное решение. Вы неизбежно столкнетесь с этой проблемой при выборе языка программирования для реализации.

В вашем процессоре должен быть достаточный набор инструментов анализа, так чтобы процессор вычислял, записывал и выдавал такие величины, как число выполнений каждого шага алгоритма и каждой встроенной функции, максимальная длина каждой внутренней области памяти, число переупаковок памяти из-за переполнений и число вызовов каждой внутренней подпрограммы. Такие инструменты решают три задачи. Во-первых, они служат средством отладки. Если между выдаваемыми числами существует какая-либо априорная зависимость и она не выполняется или если значения некоторых счетчиков не лезут ни в какие ворота, то, вероятно, это указывает на ошибку. Во-вторых, значения счетчиков помогут вам усовершенствовать именно те подпрограммы, которые затрачивают наибольшее время, и настроить параметры алгоритма распределения памяти. И наконец, значения счетчиков, оформленные подходящим образом и с необходимыми разъяснениями, помогут пользователю Трака в правильном и эффективном использовании процессора. Вероятно, значения счетчиков следует сообщать пользователю в конце каждого сеанса.

Инструментовка. На примере этой задачи можно еще раз изучить влияние языка на программирование. Если вы изберете язык высокого уровня типа Паскаля с его многочисленными мерами безопасности, то обнаружите, что большую часть процессора до абсурда легко закодировать, но за эту легкость, вероятно, придется заплатить потерей эффективности и трудностями при реализации распределения памяти. Если, напротив, остановитесь на языке ассемблера, то вполне может случиться, что ваша программа будет эффективной как по памяти, так и по времени, но она будет очень длинной и трудной для отладки, причем вам придется написать многие из тех подпрограмм, которые предоставляются другими языками программирования. Использование языков промежуточного уровня: XPL, BLISS или Фортрана — быть может, объединит преимущества (и, возможно, недостатки) двух крайних подходов. Не исключено также, что некоторые части программы придется написать на одном языке, а остальную программу — на другом. Как бы то ни было, в документации необходимо обосновать выбор языка и привести соображения, которые возникнут у вас по окончании работы.

Длительность исполнения. Для решения этой задачи в одиночку потребуется 7 недель, вдвоем — 4 недели, втроем — 3 недели.

Развитие темы. Один очевидный способ расширить Трак — это допустить вызов бланка в виде функции с именем бланка в качестве первого аргумента, т. е. преобразовывать #(XYZ, ..., ... ) в #(вц, XYZ, ..., ). Если ввести правило, согласно которому телом неопределенного бланка считается пустая цепочка, то описанное выше преобразование автоматически обеспечивает пустое значение для неопределенной функции. Если, кроме того, просматривать бланки перед встроенными функциями, то пользователь сможет заменить какие-либо встроенные функции функциями, изготовленными специально для него. Еще один очевидный способ расширения — добавление новых встроенных функций. Предлагаем два набора встроенных функций. Первый дает дополнительные удобства при работе с цепочками и литерами. Второй набор расширяет возможности ввода/вывода.

#(зм) «Запрос металитеры» (один аргумент). Значением этой функции является однолитерная цепочка, состоящая из текущей металитеры.

#(дц,А) «Длина цепочки» (два аргумента). Значением функции является длина цепочки А в виде десятичной цепочки. Длина пустой цепочки равняется нулю.

#(нл,С) «Номер литеры» (два аргумента). Значением функции является десятичная цепочка, дающая номер первой литеры аргумента С в наборе литер конкретной реализации. Если цепочка С пуста, то и значение функции пусто.

#(лн,D) «Литера по номеру» (два аргумента). Значением этой функции является цепочка из одной литеры, номер которой в наборе литер конкретной реализации задается арифметическим значением аргумента D. Если литеры, с таким номером не существует, то значение функции — пустая цепочка.

#(дс,N) «Диапазон сегментов» (два аргумента). Значение этой функции — десятичная цепочка, равная максимальному номеру метки сегмента в бланке, имя которого задано аргументом N. Если такого бланка нет или в нем нет меток сегментов, то значением функции будет нуль.

#(ио,R1,R2,V) «Изменение основания» (четыре аргумента). Для вычисления значения этой функции находится арифметическое значение аргумента V в системе счисления с основанием R1, затем оно переводится в систему с основанием R2. Множество возможных цифр для всех оснований есть (в возрастающем порядке) 0, 1, … 9, A, B,..,Z. Так, двоичной системе используются цифры 0 и 1 в десятичной — от 0 до 9, в шестнадцатеричной — от 0 до F. Арифметическим значением цепочки в данной системе счисления считается наиболее длинная ее правая подцепочка, которая, возможно, начинается с + или —, а в остальном состоит только из цифр, допустимых в этой системе. Это такое же правило, как правило Трака для десятичных значений. Аргументы R1 и R2 задают систему счисления, указывая наибольшую допустимую цифру (например, 9 для десятичной системы, 1 для двоичной и F для шестнадцатеричной). Если любой из аргументов R1 или R2 не является одной литерой в диапазоне от 0 до Z, то значение функции пусто.

#(ст) «Стоп» (один аргумент). Эта функция с пустым значением вызывает немедленный выход из процессора Трака.

#(пв,F,Z) «Подключение ввода» (три аргумента). Эта функция с пустым значением подключает устройство ввода к файлу, имя которого задается аргументом F, и устанавливает указатель файла на первую запись файла. Если файл не может быть подключен, то значением функции является аргумент Z в активном режиме независимо от режима вызова функции. Любой последующий вызов функции чц приводит к тому, что устройство ввода читает цепочку из файла до ближайшей металитеры и передвигает указатель файла. Если аргумент F пуст, то вновь подключается стандартный файл ввода (ввод с клавиатуры в интерактивных системах).

#(пы,F) «Подключение вывода» (два аргумента). Эта функция с пустым значение подключает устройство вывода к файлу F, и если такого файла еще нет, то создает его. Если аргумент F пуст, функция возвращает вывод на стандартное устройство вывода (на экран терминала в интерактивных системах).

#(уу,N) «Установка указателя» (два аргумента). Эта функция с пустым значением устанавливает указатель файла ввода на запись, расположенную после N — 1 металитер. Если это условие не определяет запись в файле или если файлом служит ввод с клавиатуры, то выполнение функции ничего не меняет.

#(чу) «Чтение указателя» (один аргумент). Функция выдает в качестве значения десятичную цепочку, представляющую текущее состояние указателя файла ввода. Если файл ввода подключен к клавиатуре, то значение функции пусто,

#(чц,Z) «Чтение цепочки» (два аргумента). Эта функция есть видоизменение ранее определенной функции чц. Если из текущего файла ввода невозможен ввод, то значением этой функции является аргумент Z в активном режиме независимо от, режима вызова функции.

Браун (Brown P. J). Macro Processing and Techniques for Portable Software Wiley, New York, NY, 1975. [Имеется перевод: Браун П. Макропроцессоры и мобильность программного обеспечения — М.: Мир, 1977.]

Муэрс (Mooers С. N.). Computer Software and Copyright, Computing Surveys, 7, I, pp. 45—72, 1975.

Хотя эта статья не посвящена непосредственно Траку, ее тематика порождена, по крайней мере отчасти, опасениями за чистоту Трака. Муэрс сформулировал если не закон, то во всяком случае четкую позицию в отношении к вопросам защиты программ.

Муэрс (Mooers С. N.). How Some Fundamental Problems are Treated in the Design of the TRAC Language. In Symbol Manipulation Languages and Techniques, edited by D. G. Bobrow. North-Holland Publishing Co., Amsterdam, pp. 178—190, 1968.

В этой работе Муэрс обсуждает некоторые решения, принятые при проектировании Трака. Трак сравнивается с другими языками для аналогичных целей, в частности с Лиспом. Общефилософские принципы, которые вы почерпнете из этой статьи, послужат отличными дрожжами для закваски познаний по основам Трака.

Муэрс (Mooers С. N.). TRAC, A Procedure-Describing Language for the Reactive Typewriter. CACM, 9, 3, pp. 215—219, 1966.

Нельсон (Nelson Т. Н.). Computer Lib or Dream Machines. Hugo's Book Service, Chicago, IL, 1974.

Всемирный каталог познаний по компьютерам. Эта книга — увлекательный сборник. Она даже имеет два разных названия, в зависимости от того, откуда вы начнете читать ее — с начала или с конца. Нельсон считает, что Трак — предвестник будущих языков, и дает прекрасное введение в него.

Стрейчи (Strachey С). A General Purpose Macrogenerator. Comput. J. 8, 3, pp. 225—241, 1966.

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

Вегнер (Wegner P.). Programming Languages, Information Structures, and Machine Organization. McGraw-Hill, New York, NY, 1978.

И Браун, и Вегнер с позиций общей информатики обсуждают Трак наряду с другими макропроцессорами.