Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 2
Текст из файла (страница 2)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324Оглавление73.5.5. Модульность функциональных программи модульность объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3304. Метаязыковая абстракция . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3354.1. Метациклический интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3384.1.1. Ядро интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 3394.1.2. Представление выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3434.1.3. Структуры данных интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 3504.1.4. Выполнение интерпретатора как программы . . . . . . . . . . . . . . . . . . . . . . . . 3544.1.5. Данные как программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3574.1.6. Внутренние определения. . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3604.1.7. Отделение синтаксического анализа от выполнения . . . . . . . . . . . . . . . . 3654.2. Scheme с вариациями: ленивый интерпретатор . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3694.2.1. Нормальный порядок вычислений и аппликативный порядок вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3704.2.2. Интерпретатор с ленивым вычислением . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 3724.2.3. Потоки как ленивые списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3794.3. Scheme с вариациями —недетерминистское вычисление . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3814.3.1. Amb и search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3834.3.2. Примеры недетерминистских программ . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 3864.3.3. Реализация amb-интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3944.4. Логическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 4044.4.1. Дедуктивный поиск информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4074.4.2. Как действует система обработки запросов . . . . . . . . . . . . . . . . . . . . . . . . 4174.4.3. Является ли логическое программирование математической логикой? 4254.4.4. Реализация запросной системы . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4295. Вычисления на регистровых машинах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4505.1. Проектирование регистровых машин . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4515.1.1. Язык для описания регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 4545.1.2. Абстракция в проектировании машин . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 4575.1.3. Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4595.1.4. Реализация рекурсии с помощью стека . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4635.1.5. Обзор системы команд . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4715.2. Программа моделирования регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 4725.2.1. Модель машины . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . 4735.2.2. Ассемблер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4765.2.3. Порождение исполнительных процедур для команд . . . . . . . . . . . . . . . . . 4805.2.4. Отслеживание производительности машины . . . . . . . . . . . . .
. . . . . . . . . . 4865.3. Выделение памяти и сборка мусора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4895.3.1. Память как векторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4895.3.2. Иллюзия бесконечной памяти . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4945.4. Вычислитель с явным управлением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5005.4.1. Ядро вычислителя с явным управлением . . . . . . . . . . . . . . . . . . . . . . . . . . 5025.4.2. Вычисление последовательностей и хвостовая рекурсия . . . . . .
. . . . . . 5075.4.3. Условные выражения, присваивания и определения . . . . . . . . . . . . . . . . . 5105.4.4. Запуск вычислителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5125.5. Компиляция . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5175.5.1. Структура компилятора. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5205.5.2. Компиляция выражений . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . 5245.5.3. Компиляция комбинаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5305.5.4. Сочетание последовательностей команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5365.5.5. Пример скомпилированного кода . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5395.5.6. Лексическая адресация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5475.5.7. Связь скомпилированного кода с вычислителем . . . . . . . . . . . . . . . . . . . .
551Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 566ПредисловиеПрограммированием занимаются учителя, генералы, диетологи, психологи и родители. Программированию подвергаются армии, ученики и некоторые виды обществ. Прирешении крупных задач приходится применять последовательно множество программ,бо́льшая часть которых возникает прямо в процессе решения.
Эти программы изобилуют деталями, относящимися к той конкретной задаче, которую они решают. Если жеВы хотите оценить программирование как интеллектуальную деятельность особого рода, то Вам следует обратиться к программированию компьютеров; читайте и пишитекомпьютерные программы — много программ. Не так уж важно, что будет в них написано и как они будут применяться. Важно то, насколько хорошо они работают и какгладко стыкуются с другими программами при создании еще более крупных программ.Программист должен равно стремиться и к совершенству в деталях, и к соразмерностисложного целого.
В книге, которую Вы держите в руках, словом «программирование» мыбудем обозначать прежде всего создание, выполнение и изучение программ, написанныхна одном из диалектов языка Лисп и предназначенных для выполнения на цифровомкомпьютере. Использование Лиспа не ограничивает нас в том, что́ мы можем описать внаших программах, — лишь в способе их выражения.Продвигаясь по материалу этой книги, мы будем встречаться с тремя группами явлений: человеческий разум, совокупности компьютерных программ и компьютер. Всякаякомпьютерная программа — это порожденная человеческим разумом модель реальноголибо умозрительного процесса.
Эти процессы, возникающие из нашего опыта и мысли,многочисленны, сложны в деталях, и мы всегда понимаем их лишь частично. Редкобывает так, что компьютерные программы отображают их к нашему окончательномуудовлетворению. Таким образом, хотя наши программы представляют собой тщательно сработанные дискретные совокупности символов, мозаики переплетенных функций,они непрерывно развиваются: мы изменяем их по мере того, как наше восприятие модели приобретает все большую глубину, расширяется и обобщается, до тех пор, покамодель не достигнет, наконец, метастабильного состояния в рамках следующей модели,над которой нам предстоит биться.
Радостное возбуждение, сопутствующее компьютерному программированию, происходит из постоянного раскрытия в голове и в компьютеревсе новых выраженных в виде программ механизмов и из взрыва восприятия, которыйони порождают. Искусство выражает наши мечты. Компьютер исполняет их под видомпрограмм!При всей своей мощности, компьютер требователен и придирчив.
Ему нужны верныепрограммы, и то, что мы хотим ему сказать, должно быть выражено точно в каждоймелочи. Как и при всякой другой работе с символами, мы убеждаемся в правильности10Предисловиепрограмм через доказательство. Самому Лиспу можно сопоставить семантику (междупрочим, тоже модель), и если функцию программы можно выразить, скажем, в терминах исчисления предикатов, то логические методы позволят нам вывести формальноедоказательство ее корректности. К сожалению, когда программы становятся большими и сложными, что с ними всегда и происходит, адекватность, непротиворечивость икорректность самих спецификаций становится предметом сомнений, так что большиепрограммы редко сопровождаются полными формальными доказательствами корректности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
