Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ
Описание файла
PDF-файл из архива "Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ", который расположен в категории "". Всё это находится в предмете "введение в функциональное программирование" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Harold AbelsonandGerald Jay SussmanwithJulie SussmanStructure and Interpretationof Computer ProgramsThe MIT PressCambridge, MassatchusettsNew YorkThe McGraw-Hill Companies, Inc.St.LouisSan FranciscoMontrealLondon, EnglandTorontoХарольд АбельсонДжеральд Джей Сассманпри участииДжули СассманСтруктура и интерпретациякомпьютерных программДобросвет, 20063Эта книга посвящается, с уважением и любовью, духу, который живет внутрикомпьютера.“Мне кажется, чрезвычайно важно, чтобы мы, занимаясь информатикой, получали радость от общения с компьютером. С самого начала это было громадным удовольствием. Конечно, время от времени встревали заказчики, ичерез какое-то время мы стали серьезно относиться к их жалобам.
Нам сталоказаться, что мы вправду отвечаем за то, чтобы эти машины использовалисьуспешно и безошибочно. Я не думаю, что это так. Я считаю, что мы отвечаемза то, чтобы их тренировать, указывать им новые направления и поддерживать уют в доме. Я надеюсь, что информатика никогда не перестанет бытьрадостью. Я надеюсь, что мы не превратимся в миссионеров. Не надо чувствовать себя продавцом Библий. Таких в мире и так достаточно. То, что Вызнаете о программировании, могут выучить и другие. Не думайте, что в ваших руках ключ к успешной работе с компьютерами.
Что у Вас, как я думаюи надеюсь, есть — это разум: способность увидеть в машине больше, чем Вывидели, когда Вас впервые к ней подвели, увидеть, что Вы способны сделатьее бóльшим.”Алан Дж. Перлис (1 апреля 1922 – 7 февраля 1990)ОглавлениеПредисловие . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 13Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 181. Построение абстракций с помощью процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1. Элементы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .1.1.1. Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2. Имена и окружение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.3. Вычисление комбинаций . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.4. Составные процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.5. Подстановочная модель применения процедуры . . . . . . . . . . . . . . . . . . .
.1.1.6. Условные выражения и предикаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.7. Пример: вычисление квадратного корня методом Ньютона . . . . . . . . . .1.1.8. Процедуры как абстракции типа «черный ящик» . . . . . . . . . . . . . . . . . . .1.2. Процедуры и порождаемые ими процессы . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .1.2.1. Линейные рекурсия и итерация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.2. Древовидная рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .1.2.3. Порядки роста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.4. Возведение в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.5. Нахождение наибольшего общего делителя .
. . . . . . . . . . . . . . . . . . . . . . .1.2.6. Пример: проверка на простоту . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3. Формулирование абстракций с помощью процедур высших порядков . . . . . .1.3.1. Процедуры в качестве аргументов . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.2. Построение процедур с помощью lambda . . . . . . . . . . . . . . . . . . . . . . . . .1.3.3. Процедуры как обобщенные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.4. Процедуры как возвращаемые значения .
. . . . . . . . . . . . . . . . . . . . . . . . . .222526272931333540434748535859626469707478832. Построение абстракций с помощью данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1. Введение в абстракцию данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .2.1.1. Пример: арифметические операции над рациональными числами . . . .2.1.2. Барьеры абстракции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .909393975Оглавление62.2.2.3.2.4.2.5.2.1.3. Что значит слово «данные»? . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002.1.4. Расширенный пример: интервальная арифметика . . . . . . . . . . . . . . . . . . . 102Иерархические данные и свойство замыкания . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062.2.1. Представление последовательностей . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1072.2.2. Иерархические структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1152.2.3. Последовательности как стандартные интерфейсы . . . . . . . . . . . . . . . . . . 1202.2.4. Пример: язык описания изображений .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132Символьные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1462.3.1. Кавычки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 1462.3.2. Пример: символьное дифференцирование . . . . . . . . . . . . . . . . . . . . . . . . . . 1492.3.3. Пример: представление множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1542.3.4. Пример: деревья кодирования по Хаффману . . . . . . . . . . . . . . . . . . . .
. . . 163Множественные представления для абстрактных данных . . . . . . . . . . . . . . . . . . 1702.4.1. Представления комплексных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1722.4.2. Помеченные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 1752.4.3. Программирование, управляемое данными, и аддитивность . . . . . . . . . 179Системы с обобщенными операциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1862.5.1. Обобщенные арифметические операции . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 1872.5.2. Сочетание данных различных типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1912.5.3. Пример: символьная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1983. Модульность, объекты и состояние . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2113.1. Присваивание и внутреннее состояние объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 2123.1.1. Внутренние переменные состояния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2133.1.2. Преимущества присваивания . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2183.1.3. Издержки, связанные с введением присваивания . . . . . . . . . . . . . . . . . . . 2213.2. Модель вычислений с окружениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2273.2.1. Правила вычисления . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2283.2.2. Применение простых процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2313.2.3. Кадры как хранилище внутреннего состояния . . . . . . . . . . . . . . . . . . . . . . 2343.2.4. Внутренние определения. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2383.3. Моделирование при помощи изменяемых данных . . . . . . . . . . . . . . . . . . . . . . . . . 2413.3.1. Изменяемая списковая структура . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 2423.3.2. Представление очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2503.3.3. Представление таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2543.3.4. Имитация цифровых схем .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2603.3.5. Распространение ограничений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2713.4. Параллелизм: время имеет значение . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . 2813.4.1. Природа времени в параллельных системах . . . . . . . . . . . . . . . . . . . . . . . . 2843.4.2. Механизмы управления параллелизмом . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 2873.5. Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2983.5.1. Потоки как задержанные списки . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 2993.5.2. Бесконечные потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3073.5.3. Использование парадигмы потоков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3143.5.4. Потоки и задержанное вычисление .
