THE ART OF
COMPUTER PROGRAMMING
VOLUME 1, FASCICLE 1
MMIX
A RISC Computer for the
New Millennium
DONALD E. KNUTH Stanford University
ADDISON-WESLEY
Upper Saddle River, NJ • Boston • Indianapolis • San Francisco
New York • Toronto • Montreal • London • Munich • Paris • Madrid
Capetown • Sydney • Tokyo • Singapore • Mexico City
ИСКУССТВО
ПРОГРАММИРОВАНИЯ
ТОМ 1, ВЫПУСК 1
MMIX
RISC-компьютер для
нового тысячелетия
ДОНАЛЬД Э. КНУТ Станфордский университет
Москва • Санкт-Петербург • Киев
2007
ББК 32. 973. 26-018. 2. 75
К53
УДК 681. 142. 2
Издательский дом "Вильяме"
Зав. редакцией С. Н. Тригуб
Перевод с английского и редакция канд. физ. -мат. наук Ю. Г. MMIX — RISC-компьютер нового
тысячелетия. : Пер. с англ. — М. : 000 "И. Д. Вильяме", 2007. — 160 с. : ил. —
Парал. тит. англ. ISBN 978-5-8459-1163-6 (рус. )
Эта книга представляет собой один из выпусков очередных томов всемирно
известного труда Искусство программирования, не нуждающейся ни в представлении,
ни в рекламе. В данный выпуск вошли разделы первого тома, посвященные RISC-
компьютеру MMIX, который заменит прежний компьютер MIX, и языка ассемблера
MMIX. Материалы этого выпуска в будущем войдут в первый том серии, посвященный
базовым алгоритмам — возможно, с определенными дополнениями и исправлениями
на основе отзывов читателей данного выпуска. ББК 32. 973. 26-018.
2. 75
Все названия программных продуктов являются зарегистрированными торговыми марками
соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами, будь то электронные или
механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного
разрешения издательства Addison-Wesley Publishing Company, Inc. Rights to this book were obtained by arrangement with Addison-Wesley Longman, Inc. Russian language edition published by Williams Publishing House according to the Agreement with
R&I Enterprises International, Copyright © 2007
ISBN 978-5-8459-1163-6 (рус. ) © Издательский дом "Вильяме", 2007
ISBN 0-201-85392-2 (англ. ) © by Pearson Education, Inc. , 2005
СОДЕРЖАНИЕ
Глава 1. Основные понятия 10
1. 3'. MMIX 10
1. 3. 1'. Описание MMIX 10
1. 3. 2'. Язык ассемблера компьютера MMIX 39
1. 3. 3'. Применения к перестановкам 63
1. 4'. Некоторые фундаментальные методы программирования 64
1. 4. Г. Подпрограммы 64
1. 4. 2'. Сопрограммы 79
1. 4. 3'. Программы-интерпретаторы 86
Ответы к упражнениям 109
Предметно-именной указатель 143
ОТ ИЗДАТЕЛЬСТВА
Вы, читатель этой книги, и есть главный ее критик и комментатор. Мы ценим
ваше мнение и хотим знать, что было сделано нами правильно, что можно было
сделать лучше и что еще вы хотели бы увидеть изданным нами. Нам интересно
услышать и любые другие замечания, которые вам хотелось бы высказать в наш
адрес.