Структура и интерпретация компьютерных программ [Харольд Абельсон] (pdf) читать постранично, страница - 2
- Структура и интерпретация компьютерных программ 4.02 Мб, 608с. скачать: (pdf) - (pdf+fbd) читать: (полностью) - (постранично) - Харольд Абельсон
Книга в формате pdf! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
- 1
- 2
- 3
- 4
- . . .
- последняя (197) »
кодирования по Хаффману . . . . . . . . . . . . . . . . . . . . . . . 163
Множественные представления для абстрактных данных . . . . . . . . . . . . . . . . . . 170
2.4.1. Представления комплексных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
2.4.2. Помеченные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
2.4.3. Программирование, управляемое данными, и аддитивность . . . . . . . . . 179
Системы с обобщенными операциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
2.5.1. Обобщенные арифметические операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
2.5.2. Сочетание данных различных типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2.5.3. Пример: символьная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
3. Модульность, объекты и состояние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
3.1. Присваивание и внутреннее состояние объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.1.1. Внутренние переменные состояния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
3.1.2. Преимущества присваивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
3.1.3. Издержки, связанные с введением присваивания . . . . . . . . . . . . . . . . . . . 221
3.2. Модель вычислений с окружениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
3.2.1. Правила вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
3.2.2. Применение простых процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
3.2.3. Кадры как хранилище внутреннего состояния . . . . . . . . . . . . . . . . . . . . . . 234
3.2.4. Внутренние определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
3.3. Моделирование при помощи изменяемых данных . . . . . . . . . . . . . . . . . . . . . . . . . 241
3.3.1. Изменяемая списковая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
3.3.2. Представление очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
3.3.3. Представление таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
3.3.4. Имитация цифровых схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
3.3.5. Распространение ограничений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
3.4. Параллелизм: время имеет значение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
3.4.1. Природа времени в параллельных системах . . . . . . . . . . . . . . . . . . . . . . . . 284
3.4.2. Механизмы управления параллелизмом . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
3.5. Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
3.5.1. Потоки как задержанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
3.5.2. Бесконечные потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
3.5.3. Использование парадигмы потоков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
3.5.4. Потоки и задержанное вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Оглавление
7
3.5.5. Модульность функциональных программ
и модульность объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
4. Метаязыковая абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
4.1. Метациклический интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
4.1.1. Ядро интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
4.1.2. Представление выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
4.1.3. Структуры данных интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
4.1.4. Выполнение интерпретатора как программы . . . . . . . . . . . . . . . . . . . . . . . . 354
4.1.5. Данные как программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
4.1.6. Внутренние определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
4.1.7. Отделение синтаксического анализа от выполнения . . . . . . . . . . . . . . . . 365
4.2. Scheme с вариациями: ленивый интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
4.2.1. Нормальный порядок вычислений и аппликативный порядок вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
4.2.2. Интерпретатор с ленивым вычислением . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
4.2.3. Потоки как ленивые списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
4.3. Scheme с вариациями —
недетерминистское вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
4.3.1. Amb и search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
4.3.2. Примеры недетерминистских программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
4.3.3. Реализация amb-интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
4.4. Логическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
4.4.1. Дедуктивный поиск информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
4.4.2. Как действует система обработки запросов . . . . . . . . . . . . . . . . . . . . . . . . 417
4.4.3. Является ли логическое программирование математической логикой? 425
4.4.4. Реализация запросной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
5. Вычисления на регистровых машинах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
5.1. Проектирование регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
5.1.1. Язык для описания регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
5.1.2. Абстракция в проектировании машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
5.1.3. Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
5.1.4. Реализация рекурсии с
Множественные представления для абстрактных данных . . . . . . . . . . . . . . . . . . 170
2.4.1. Представления комплексных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
2.4.2. Помеченные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
2.4.3. Программирование, управляемое данными, и аддитивность . . . . . . . . . 179
Системы с обобщенными операциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
2.5.1. Обобщенные арифметические операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
2.5.2. Сочетание данных различных типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2.5.3. Пример: символьная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
3. Модульность, объекты и состояние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
3.1. Присваивание и внутреннее состояние объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.1.1. Внутренние переменные состояния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
3.1.2. Преимущества присваивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
3.1.3. Издержки, связанные с введением присваивания . . . . . . . . . . . . . . . . . . . 221
3.2. Модель вычислений с окружениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
3.2.1. Правила вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
3.2.2. Применение простых процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
3.2.3. Кадры как хранилище внутреннего состояния . . . . . . . . . . . . . . . . . . . . . . 234
3.2.4. Внутренние определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
3.3. Моделирование при помощи изменяемых данных . . . . . . . . . . . . . . . . . . . . . . . . . 241
3.3.1. Изменяемая списковая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
3.3.2. Представление очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
3.3.3. Представление таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
3.3.4. Имитация цифровых схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
3.3.5. Распространение ограничений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
3.4. Параллелизм: время имеет значение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
3.4.1. Природа времени в параллельных системах . . . . . . . . . . . . . . . . . . . . . . . . 284
3.4.2. Механизмы управления параллелизмом . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
3.5. Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
3.5.1. Потоки как задержанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
3.5.2. Бесконечные потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
3.5.3. Использование парадигмы потоков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
3.5.4. Потоки и задержанное вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Оглавление
7
3.5.5. Модульность функциональных программ
и модульность объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
4. Метаязыковая абстракция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
4.1. Метациклический интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
4.1.1. Ядро интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
4.1.2. Представление выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
4.1.3. Структуры данных интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
4.1.4. Выполнение интерпретатора как программы . . . . . . . . . . . . . . . . . . . . . . . . 354
4.1.5. Данные как программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
4.1.6. Внутренние определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
4.1.7. Отделение синтаксического анализа от выполнения . . . . . . . . . . . . . . . . 365
4.2. Scheme с вариациями: ленивый интерпретатор . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
4.2.1. Нормальный порядок вычислений и аппликативный порядок вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
4.2.2. Интерпретатор с ленивым вычислением . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
4.2.3. Потоки как ленивые списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
4.3. Scheme с вариациями —
недетерминистское вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
4.3.1. Amb и search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
4.3.2. Примеры недетерминистских программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
4.3.3. Реализация amb-интерпретатора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
4.4. Логическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
4.4.1. Дедуктивный поиск информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
4.4.2. Как действует система обработки запросов . . . . . . . . . . . . . . . . . . . . . . . . 417
4.4.3. Является ли логическое программирование математической логикой? 425
4.4.4. Реализация запросной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
5. Вычисления на регистровых машинах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
5.1. Проектирование регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
5.1.1. Язык для описания регистровых машин . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
5.1.2. Абстракция в проектировании машин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
5.1.3. Подпрограммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
5.1.4. Реализация рекурсии с
- 1
- 2
- 3
- 4
- . . .
- последняя (197) »
Последние комментарии
5 часов 32 минут назад
6 часов 9 минут назад
1 день 19 часов назад
1 день 22 часов назад
2 дней 12 часов назад
2 дней 12 часов назад