и наоборот, процесс, выполняемый п сопрограммами, часто можно преобразовать в п-проходный процесс. Именно из-за этого соответствия имеет смысл провести сравнительный анализ многопроходных и однопроходных алгоритмов.

a) Психологическое отличие Для одной и той же задачи, как правило, проще создать и понять многопроходный алгоритм, чем однопроходный. Процесс, разделенный на ряд небольших шагов, выполняющихся один после другого, понять намного легче, чем запутанную процедуру, в которой множество преобразований выполняется одновременно.

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

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

b) Разница во времени выполнения. В однопроходном алгоритме не нужно тратить время на то, чтобы упаковать, записать, прочитать и распаковать промежуточные данные, которые передаются между проходами (например, информация на лентах на рис. 22). Поэтому однопроходный алгоритм выполняется быстрее.

c) Различие в объеме памяти. Для однопроходного алгоритма необходимо хранить в памяти все программы одновременно, в то время как для многопроходного алгоритма можно сохранять в памяти только по одной программе. Этот фактор может отразиться на скорости выполнения программы даже в большей степени, чем фактор, указанный в п. (Ь). Например, многие компьютеры имеют ограниченный объем "быстродействующей памяти" и большой объем "медленной памяти". Если каждый проход поместится в быстрой памяти, то вся програм.ма выполнится значительно быстрее, чем в случае использования сопрограмм в одном проходе (так как при использовании сопрограмм большинство программ, скорее всего, будут помещены в "медленную память" либо будут много раз загружаться и выгружаться из быстрой памяти).

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

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

И наоборот, ясно, что некоторые многопроходные алгоритмы нельзя преобразовать в сопрограммы. Отдельные алгоритмы являются многопроходными по своей

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

В автобусе. Маленькая старушка: "Мальчик, ты не подскажешь мне, когда нужно выходить, чтобы попасть на Пасадена-Стрит?".

Мальчик: "Просто следите за мной и выходите за две остановки перед тем, как выйду я".

(Шутка заключается в том, что мальчик предлагает старушсе двухпроходный алгоритм.)

Вот пока и все, что касается многопроходных алгоритмов. С другими примерами сопрограмм мы будем встречаться в различных разделах книги, например они будут частью буферных схем в разделе 1.4.4. Сопрограммы играют также важную роль в моделировании дискретных систем (см. раздел 2.2.5). Важная идея репли-кационных сопрограмм обсуждается в главе 8, а некоторые интересные примеры применения этой идеи можно найти в главе 10.

УПРАЖНЕНИЯ

1. [10] Объясните, почему автору трудно найти небольшие простые примеры сопрограмм.

► 2. [20] В программе, приведенной в тексте раздела, первой запускается сопрограмма OUT. Что произойдет, если первой будет выполняться сопрограмма IN, т. е. если в строке 60 поменять "JMP 0UT1" на "JMP IN1"?

3. [20] Истинно ли утверждение "Все три команды "СМРА PERIOD" из программы OUT можно опустить, и программа по-прежнему будет работать"? (Будьте внимательны.)

4. [20] Покажите, как связь между сопрограммами, аналогичную (1), можно реализовать на реальных компьютерах, которые вы хорошо знаете.

5. [15] Предположим, для обеих сопрограмм IN и OUT нужно, чтобы в промежутке между входом и выходом содержимое регистра А оставалось неизменным. Другими словами, предположим, что в каждом случае появления команды "JMP IN" внутри сопрограммы OUT содержимое регистра А должно оставаться неизменным до возврата управления следующей строке. Аналогичное предположение делается по отношению к команде "JMP OUT" внутри сопрограммы IN. Как в этом случае должна выглядеть связь между сопрограммами? (Ср. с (4).)

► 6. [22] Напишите команды связи между сопрограммами, аналогичные (1), для случая трех сопрограмм. А, В и С, каждая из которых может вызывать любую из двух других. (В каждом случае активизации сопрограммы выполнение начинается с того места, где оно закончилось в прошлый раз.)

► 7. [30] Напишите программу для MIX, которая выполняет преобразование, обратное тому, которое осуществляет программа из текста раздела, т. е. ваша программа должна получать на входе перфокарты типа (3), а на выходе выдавать перфокарты типа (2). На выходе должна быть настолько короткая строка символов, насколько это воз.можно, поэтому нуль перед буквой Z в (2) на этот раз не должен быть перенесен из (3).

1.4.3. Программы-интерпретаторы

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

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

a) на машинно-ориентированном языке можно представить сложную последовательность решений и действий в компактном и удобном виде;

b) такое представление обеспечивает прекрасный способ передачи информации между проходами в многопроходном процессе.

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

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

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

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