Д. Кнут - Искусство программирования том 1 (1119450), страница 52
Текст из файла (страница 52)
Анализ современных представлений об оптимальных способах написания всевозможных программ содержится в книге 1 1(егасе Ргобгатт[пд (СашЪг(г[йе Вппл Ргезз), впервые опубликованной в 1992 году. Кстати, в главе 11 этой книги приведен подробный перечень всех ошибок, которые были устранены из программы ТЕХ в период между 1978 и 1991 годами. до некоторого момента лучше допустить наличие ошибок в программе, чем потратить на ее разработку столько времени. сколько необкоднмо дяя устранення всех ошибок (сколько десятилетий на зто потребуется?).
— Д. Ье, 'Т ЬЮРИНГ, Ргороза1з гог АСЕ (1945) УПРАЖНЕНИЯ 1. [10] Сформулируйте характеристики подпрограммы (5). В качестве образца нсполы зуйте (4), где даются характеристики подпрограммы 1.3.2М. 2. [10[ Предложите код, заменяющий (б). Не используйте команду 151, 3. [М15[ Дополните информацию, которая дана в (4), точно указав, что происходит с регистром 3 я фчагом сравнения пря выполнении подпрограммы. Определите также, что происходит в случае, когда в регистре 11 содержится неположительное число. 4.
[51[ Напишите обобщающую ИХХИ подпрограмму нахождения максимального значения для последовательности Х[а), Х[а+ г), Х[а+ 2т), ..., Х[п), где г и и — параметры, ь а — наименьшее положительное число, для которого а ш п (по модулю г), т. е. а = 1 + (п — 1) шод г.
Предусмотрите специальный вход для случая г = 1. Перечисляте характеристики новой подпрограммы, взяв эа образец (4). 5. Щ Предположим, и.„машине М1Х нет регистра Л. Придумайте способ связи подпрограмм, не использующий регистр 3. Проиллюстрируйте свое изобретение на примере, написав подпрограмму МАХ100, фактически эквивалентную (1). Сформулируйте характеристики этой подпрограммы аналогично тому, как это сделано в (4). (Придерживайтесь принятых для М1Х соглашений о самомолифицирующемся коде.) 6. [26[ Предположим, в М1Х нет оператора МОЧЕ.
Напишите подпрограмму с именем МОЧЕ, такую, чтобы ее последовательность вызова "1МР МОЧЕ; МОР А,1(Р)" давала такой же эффект, как и "МОЧЕ А,1(Р)", если бы последнее было допустимо. Единственные отличия должны заключаться в воздействии на регистр 1 и в том, что время выполнения подпрограммы несколько увеличится. 7. [ЕО] Почему к самомодифицирующемуся коду сейчас относятся неодобрительно? 1.4.2. Сопрограммы Подпрограммы — зто частные случаи более общих программных компонентов, называемых сопрограмма,ии. В противоположность несимметричной связи между главной программой и подпрограммой, между сопрограммами, которые вызывающ одна другую, существует полная симметрия. Чтобы понять, что представляет собой сопрограмма, давайте посмотрим на подпрограммы с другой стороны.
В предыдущем разделе мы придерживались той точки зрения, что подпрограмма †э некая аппаратная реализация, которая используется для сокращения количества строк в программе. Это, конечно, правильно, но возможна и другая точка зрения. Можно рассматривать главную программу и подпрограмму как группу программ, причем каждый член группы должен выполнять определенную работу. Главная программа в процессе своей работы активизирует подпрограмму, последняя выполняет собственную функцию, а затем активизирует главную программу. Мы можем выйти за узкие рамки своих представлений и вообразить, что с точки зрения подпрограммы, когда она осуществляет выход, именно она вызывает главную программу. Главная программа продолжает выполнять свои обязанности, а затем "выходит" в подпрограмму. Подпрограмма работает, а затем снова вызывает главную программу.
Эта несколько надуманная философия на самом деле полностью отражает ситуацию с сопрограммами, для которых невозможно определить, где главная программа, а где подпрограмма. Предположим, имеются сопрограммы А и В. Программируя А, можно считать, что  — это подпрограмма; в свою очередь, программируя В, как подпрограмму можно рассматривать уже А. Таким образом, в сопрограмме А команда "ЗМР В" используется для активизации сопрограммы В.
В сопрограмме В команда чЛМР А" применяется для того, чтобы снова активизировать сопрограмму А. Каждый раз при активизации сопрограмма возобновляет выполнение своей программы с той точки, в которой действие было приостановлено в прошлый раз. Сопрограммами А и В могут быть, например, две программы., играющие в шахматы. Их можно скомбинировать так, чтобы они играли одна против другой. В М1Х подобная связь между сопрограммами А и В осуществляется путем включения в программу следующих четырех команд.
А ВХЗ ВХ АХ ЛМР А1 В ЯТЗ АХ ВХ ЛМР 81 (2) А2В583428РСОХУИ3210РЦ898. Для передачи управления любой из сопрограмм требуется четыре машинных такта. Первоначально АХ и ВХ установлены на переход к начальным точкам каждой сопрограммы, А1 и В1. Предположим, сначала запускается сопрограмма А; она начинает выполняться с команды, которая находится в ячейке А1. Когда сопрограмма А выполняет, скажем, команду "ЛМР В" из ячейки А2, команда из ячейки В сохраняет в АХ содержимое гЛ, скажем, команду "ЛМР А2+1", Команда из ВХ переносит нас в ячейку 81, и вслед за этим начинает выполняться сопрограмма В. В конце концов она доходит до команды "ЛМР А", которая находится, скажем, в ячейке 82. Мы сохраняем содержимое гЛ в ВХ и переходим к ячейке А2+1, продолжая выполнять сопрограмму А до тех пор, пока управление снова не перейдет к В, которая сохраняет содержимое регистра Л в АХ, переходит к В2+1 и т.
д. Главное различие между связями "программа — подпрограмма" и "сопрограмма — сопрограмма", как видно из предыдущего примера, состоит в том, что подпрограмма всегда начинается с самого начала (как правило, это фиксированная точка), а главная программа или сопрограмма всегда начинается с места, следующего за той точкой, в которой ее выполнение было прекращено в прошлый раз. Необходимость использования сопрограмл1 на практике естественным образом возникает в случае, когда они связаны с алгоритмами ввода и вывода. Приведем такой пример.
Предположим, что в обязанности сопрограммы А входит считывание перфокарт и выполнение такого преобразования входных данных, которое сводит их к последовательности элементов. Другая сопрограмма, которую мы будем называть В, выполняет дальнейшую обработку этих элементов и печатает ответы. В периодически запрашивает последующие элементы ввода, полученные А.
Таким образом, сопрограмма В вызывает А каждый раз, когда ей нужен следующий элемент ввода, и сопрограмма А вызывает В каждый раз, когда находит элемент ввода. Читатель может сказать: "Ну что ж,  — это главная программа, а А — просто подпрограмма для выполнения ввода". Но это утверждение становится уже не таким правильным, когда процесс А оказывается очень сложным. В действительности можно считать, что А — это главная программа, а  — подпрограмма, выполняющая вывод, и приведенное выше описание останется верным. Но полезность идеи сопрограммы обнаруживается между этими двумя крайностями, когда и А, и В достаточно сложны и каждая из них вызывает другую много раз из различных точек. Подобрать небольшие, простые примеры сопрограмм, иллюстрирующие важность этой идеи, весьма трудно.
В случаях, когда применение сопрограмм приносит наибольшую пользу, зти сопрограммы, как правило, оказываются довольно большими. Чтобы рассмотреть сопрограммы в действии, воспользуемся таким примером. Предположим, необходимо написать программу, преобразуюшую один код в другой. Входной код, который нужно преобразовать, представляет собой последовательность буквенно-цифровых символов, заканчиваюшуюся точкой, например АВВ ВЕЕ ЕЕЕ Е44 446 ббР ОХУ 922 220 ОРЦ 999 999 999 Н. (3) Обратите внимание, что 3426Р означает не 3427 повторений буквы Р, а четыре четверки и три шестерки, за которыми следует буква Р.
Если входная последовательность имеет вид '1. ', то на выходе будет просто '. ', а не ' ..', поскольку первая же точка заканчивает вывод. Наша программа должна выбить выходные данные на перфокартах — по шестнадцать групп на каждой карте, за исключением, возможно, последней Для выполнения такого преобразования напишем две сопрограммы и одну подпрограмму. Подпрограмма с именем ИЕХТСНАН предназначена для нахождения непустых символов (т.
е не пробелов) во входных данных и помещения каждого последующего такого символа в регистр А. 01 е ПОДПРОГРАММА ВВОДА СИМВОЛОВ 06 КЕАОЕВ ЕЦО 16 Номер устройства чтения перфокарт 08 1МРОТ ОЛГО а+16 Место для входных карт 01 МЕХТСНАН ЯТЗ 9Р Вход в подпрограмму 05 ЗХМХ ЗР Первоначально тХ = О 00 1Н ЗбМ 2Р Первоначально г16 = О 07 1М 1МРОТ(НЕАОЕК) Читать следующую карту 08 ЗВОЯ е (НЕАОЕК) Ожидать завершения 00 ЕММб 16 Пусть т16 указывает на слевующее слово. 10 2Н ЕОХ 1МРОТ+16,6 Взять следующее слово нз ввода.
11 1МСб 1 Продвинуть указатель 12 ЗН ЕМТА О 10 ЯВАХ 1 Следующий символ -+ гА 14 9Н ЗАМЕ е Пропустить пробелы 15 ЗИР МЕХТСНАК+1 в Эта подпрограмма имеет следующие характеристики. Последовательность вызова: ЗИР МЕХТСНАН. Состояние при входе: гХ = количество символов, которые еще будут использованы; г16 указывает на следующее слово или г16 = О. указывая, что нужно читать новую карту. гА = следующий непустой символ ввода; гХ и г16 настроены для следующего входа в МЕХТСНАВ. Состояние при выходе Эта последовательность выбивается на перфокартах; пустые колонки, встречающиеся на перфокартах, игйорнруются. Входные данные интерпретируются следующим образом, слева направо: если следующий символ — цифра О, 1, ..., 9 (обозначим ее через п), то он указывает на (н + 1) повторение следующего символа независимо от того, является ли он цифрой. Нецифровой символ обозначает сам себя. Выходные данные нашей программы должны представлять собой последовательность, полученную указанным образом и разделенную на группы по три символа.
Последовательность заканчивается с появлением точки: в последней группе может быть менее трех символов. Например, последовательность (2) должна быть преобразована нашей программой в следующие группы символов: Наша первая сопрограмма с именем 1М находит символы входной последовательности и количебтво их повторений. В первый раз ее выполнение начинается с 1М1. Найден нецифровой символ. Отослать его в сопрограмму ООТ.
Получить символ. Это буква? (Напоминаю, что в символьном коде М1Х цифры 0 — 9 имеют коды ЗΠ— 39.) Эта сопро- грамма имеет следующие характеристики. Последовательность вызова: 5МР 1М. Состояние при выходе (при вызове ООТ): Состояние при входе (после возврата): Вторая сопрограмма с именем ООТ разбивает код на группы по три символа и осуществляет перфорацию. Ее выполнение начинается с ООТ1. 81 ь ВТОРАЯ СОПРОГРАММА 82 АЕР 88 ООТРОТ ОВ10 я+16 84 РОМСН ЕЦО 17 85 ООТ1 ЕМТ4 -16 уб ЕНТ1 ООТРОТ 87 МОЧЕ "1,1(16) 88 1Н ЛМР 1И 80 ЕТА ООТРОТ+16,4(1: 1) 40 СИРА РЕК100 ЛЕ 9Р 42 ЛМР 1М 48 ВТА ОСТРОТ+16,4(2:2) 44 СМРА РЕВ100 Постоянная, используемая для пробелов. Буферная область для ответов. Номер устройства перфорирования. Начать новую выходную перфокарту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
