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

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

((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.