Д. Кнут - Искусство программирования том 1 (1119450), страница 57
Текст из файла (страница 57)
Сохранить содержимое гА. Сохранить содержимое гЛ. Взять начальный адрес для трассировки. Сохранить адрес следующей команды. Это адрес выхода? Взять следующую команду. Скопировать ее. Сохранить этот адрес и индексы. Взять код операции, С. С > 38 (ЛАЕО)? С ~ 32 (ЯТЛ)? Заменить ЯТЛ на ЯТА. гА < — имитируемое содержимое гЛ.
С ~ 34 (ЛВОБ)? Тест для команд перехода. С > 47 (ЛП.)? Мы обнаружили команду перехода; изменить ее адрес на "ЛОИР". Восстановить регистр А. Во всех регистрах, кроме Л, теперь правильные значения по отношению к внешней программе. Команда выполняется. Снова сохранить регистр А. Перейти к следующей команде. 1МСА 1 ЛМР С?СЕВ 181 1ОМР ЮА 88(4:б) ЯОВ 1МЯТ(4:б) 1АХ в+4 ЬОА РВЕО(0:2) 1МСА 1 ЯТА 1ВЕО(0:2) ЕМТА в 1МР С?СЕВ ЕРА АВЕО ЗМР СОМ 0 07 00 00 8Н 40 ШМР 41 4й 40 44 45 40 1ЫЯТ1 47 4В РВАЧЕ 49 ?.ЕАЧЕХ 50 АВЕО Константа для строк 29 и 40.
Встретился переход. Это была 155? Если нет, обновите имитируемый регистр 3. Перейти к адресу перехода. Восстановить регистр А. Остановить трассировку. Содержимое имитируемого гА. $ УПРАЖНЕНИЯ 1. (ЯЯ] Модифицируйте программу трассировки твк, чтобы при выходе она восстанавливала регистр Л. (Можете предполагать, что содержимое регистра д ненулевое.) По поводу программ трассировки в целом н этой в частности нужно отметить следующее.
1) Здесь представлена только самая интересная часть программы трассировки — часть, которая является управляющей во время выполнения другой программы. Чтобы трассировка принегла пользу, необходима также программа записи содержимого регистров, но мы ее не включили. Такая программа, хотя и безусловно важная, отвлекает внимание от более тонких моментов программы трассировки. Поэтому модификации, которые в этой связи необходимо ввести в программу, оставлены для упражнения (см.
упр. 2). 2) Занимаемое пространство обычно имеет большее значение, чем время выполнения, т. е. программа должна быть настолько короткой, насколько это возможно. Тогда программа трассировки сможет "сосуществовать" даже с очень большими программами. А время выполнения все равно расходуется на вывод данных. 3) Мы позаботились о том, чтобы избежать изменения содержимого большинства регистров. Фактически программа использует только регистр А машины М1Х.
Программа трассировки не оказывает влияния ни на флаг сравнения, ни на флаг переполнения. (Чем меньше регистров используется, тем меньшее их число нужно восстанавливать.) 4) Когда происходит переход к ячейке ДОМР, необязательно выполнять команду "ЯТА АВЕО", так как содержимое гА не изменилось. 5) После выхода из программы трассировки регистр 3 не восстанавливается.
В упр. 1 показано, как исправить эту ситуацию. 6) На трассируемую программу налагаются только три ограничения. а) Она не должна сохранять что-либо в ячейках, используемых программой трассировки. Ь) Она не должна использовать выходное устройство, на которое выводится информация о трассировке (напрнмер, команда БИВНЯ дала бы неправильное указание). с) Во время трассировки она будет работать медленнее. 2. [лб] Модифицируйте приведенную в тексте программу трассировки таким образом, чтобы перед выполнением каждого шага она записывала на магнитную ленту (устрой- ство 0) следующую ин4юрмацию. Слово 1, поле (О: 2): адрес ячейки, Слово 1, поле (4: 3): регистр Л (перед выполнением). Слово 1, поле (3:3) 2, если результат сравнения — больше, 1 — если равно, 0 — если меньше; плюс 8, если перед выполнением нет переполнения, Слово 2: команда.
Слово 3: регистр А (перед выполнением), Слова 4 — 9: регистры П вЂ” 16 (перед выполнением). Слово 10: регистр Х (перед выполнением). Слова 11-100 каждого блока ленты размером 100 слов должны содержать еще девять групп по 10 слов, записанных в том же формате. 3. [10] В предыдущем упражнении программа трассировки записывает свои выходные данные на магнитную ленту Объясните, почему это лучше, чем непосредственно распеча- тать результаты. 4. [65] Что произойдет, если программа трассировки будет трассировать саму себя? Если более конкретно, то выясните, как будет работать программа трассировки, если две команды — ЕМТХ ЕЕлуЕХ и ЗНР»»1 — поместить непосредственно перед ЕНТЕЕ 6. [26] Рассмотрим задачу, аналогичную предыдущей. Пусть две копии программы трассировки помещены в различных местах памяти и настроены так, чтобы трассировать одна другую. Что произойдет? 6.
[40] Напишите программу трассировки, способную трассировать себя в смысле упр 4: она должна в замедленном режиме распечатывать собственные шаги. а гаа программа будет трассировать саму себя в еще более замедленном режиме, и так до бесконечности, пока будет хватать памяти. 7. [Я5] Подумайте, как написать эффективную программу глрассировки переходов, которая выдает намного меньше выходных данных, чем обычная программа трассировки.
Вместо того чтобы отображать содержимое регистров, программа трассировки переходов просто записывает происходящие переходы Она выдает последовательность пар (хну~), (хнуз), .... Это означает, что программа перешла из ячейки х~ в уь затем (после выполнения команд из ячеек ум у~ + 1, ..., хз) — из ячейки хз в уз и т, д.
[На основании этой информации следующая программа может восстановить ход выполнения программы и установить, как часто выполнялась кахСдая команда.] 1.4.4. Ввод и вывод Вероятно, самое очевидное, чем один компьютер отличается от другого, — это устройства ввода-вывода, а также компьютерные команды, управляющие этими периферийными устройствами. В рамках одной книги невозможно обсудить все проблемы и методы, связанные с данной областью, поэтому мы ограничимся изучением наиболее типичных методов ввода-вывода, применимых для большинства компьютеров. Операторы ввода-вывода машины И1Х представляют собой нечто среднее между самыми разнообразными средствами, имеющимися в реальных компьютерах..
Чтобы вы могли представить себе операции ввода-вывода на конкретном примере, давайте в этом разделе обсудим проблемы оптимального выполнения операций ввода-вывода в машине И1Х. И снова я прошу читателя сннсходнтельно отнестись к таму, что здесь рассма- Ф трнвается анахроничная машина йЕХ с ее перфокартами п т. и. Хотя этн устаревпше устройства сегодня полностью вышли нз употребления, онн по-прежнему могут дать несколько важных уроков. Но, конечно, когда для этой цели будет испол»зоваться компьютер йй1Х, он преподаст нам нх еще лу'чше.
Многие пользователи компьютеров полагают, что ввод и вывод на самом деле не являются частью процесса "настоящего" программирования. Считается, что ввод и вывод — это нудные задачи, которые приходится выполнять только для того, чтобы ввести информацию в компьютер и вывести из него полученные результаты. Поэтому средства ввода-вывода компьютера обычно начинают изучать только после знакомства с остальными его возможностями. И часто случается так, что лишь неболыпая группа программистов некоторого компьютера вообще что-либо знает о деталях операций ввода-вывода. Такое положение вещей в чем-то даже естественно, поскольку программирование ввода-вывода никогда не было особенно привлекательным.
Но до тех пор, пока многие не начнут серьезно относиться к данному предмету, нельзя ожидать, что ситуация изменится, В этом и других разделах (например, в разделе 5.4.6) вы увидите, что в связи с вводом-выводом возникает множество интересных вопросов, а также узнаете о существовании некоторых изящных алгоритмов. Теперь, пожалуй, нужно сделать небольшое отступление по поводу терминологии. В словарях английского языка слова ь1прп(» ("ввод") и "оп(рпФ" ("вывод") раньше приводились только как существительные ("ЯЪа1 Ыпб о1 1приФ аге ъе беы $1пб?ь — "Какого вида данные мы вводим?"). Но теперь уже вошло в привычку использовать их как прилагательные ("1)опп бгор 1Ье 1прпт гаре" — "Не сотрите эту ленту с входными данными") и переходные глаголы ("ИЪу пЫ 1Ье ргойгаш оп(рпт 1Ь(в багЬабе?" — "Почему программа выводит эту чепуху?"). Вместо комбинированного термина "ввод-вывод" чаще всего используют аббревиатуру "В/В" (на английском — "1/О").
Операцию ввода часто называют чшение.и, а вывода соответственно записью. Элементы, составляющие ввод или вывод, обычно называют "данными" (на английском — "па1а"). В английском языке это слово, строго говоря, является формой множественного числа (как и в русском языке. — Прим.
перев.), но используется в собирательном смысле, как будто это единственное число ("ТЬе баса Ьав пос Ьееп геас1."). Точно так и слово "1п(огша11ап» ("информация") является формой как единственного, так и множественного числа. На этом урок английского закончен. Предположим, необходимо прочитать данные с магнитной ленты. Оператор 19 машины И11, как описано в разделе 1.3.1, просто инициирует процесс ввода, и в то время, пока данные вводятся, компьютер продолжает выполнять следующие команды. Поэтому по команде «19 1000(5)" начинается считывание 100 слов с накопителя на магнитных лентах под номером 5 в ячейки памяти 1000-1099, но последующие команды программы пока не должны обращаться к этим ячейкам.
Программа может считать, что ввод завершен только после того, как (а) инициируется другая операция В/В (1й, 0(У? или 100), обращающаяся к устройству 5, или (Ь) команда условного перехода ЗВоЯ(5) или ЛИР(5) показывает, что устройство 5 больше не "занято".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
