Добросвет, 2006, второе издание.
Структура и интерпретация компьютерных программ — это вводный курс по информатике в Массачусетском Технологическом институте (MIT). Он обязателен для всех студентов MIT на специальностях ѕэлектротехникаї и информатика, как одна из четырех частей ѕобщей базовой программы обучения, которая включает еще два курса по электрическим схемам и линейным системам, а также курс по проектированию цифровых систем. Мы принимали участие в развитии этого курса начиная с 1978 года и преподавали этот материал в его нынешней форме начиная с осени 1980 года шестистам-семистам студентам в год. Большая часть этих студентов не имела почти или совсем никакого формального образования в области вычислительной техники, хотя у многих была возможность общения с компьютерами, а некоторые обладали значительным опытом в программировании либо проектировании аппаратуры.
Содержание:
Предисловие.
Предисловие ко второму изданию ix.
Предисловие к первому изданию xi.
Благодарности xv.
Построение абстракций с помощью процедур.
Элементы программирования.
Выражения.
Имена и окружение.
Вычисление комбинаций.
Составные процедуры.
Подстановочная модель применения процедуры.
Условные выражения и предикаты.
Пример: вычисление квадратного корня методом Ньютона.
Процедуры как абстракции типа ѕчерный ящикї.
Процедуры и порождаемые ими процессы.
Линейные рекурсия и итерация.
Древовидная рекурсия.
Порядки роста.
Возведение в степень.
Нахождение наибольшего общего делителя.
Пример: проверка на простоту.
Формулирование абстракций с помощью процедур высших порядков.
Процедуры в качестве аргументов.
Построение процедур с помощью lambda.
Процедуры как обобщенные методы.
Процедуры как возвращаемые значения.
Построение абстракций с помощью данных.
Введение в абстракцию данных.
Пример: арифметические операции над рациональными числами.
Барьеры абстракции.
Что значит слово ѕданныеї?
Расширенный пример: интервальная арифметика.
Иерархические данные и свойство замыкания.
Представление последовательностей.
Иерархические структуры.
Последовательности как стандартные интерфейсы.
Пример: язык описания изображений.
Символьные данные.
Кавычки.
Пример: символьное дифференцирование.
Пример: представление множеств.
Пример: деревья кодирования по Хаффману.
Множественные представления для абстрактных данных.
Представления комплексных чисел.
Помеченные данные.
Программирование, управляемое данными, и аддитивность.
Системы с обобщенными операциями.
Обобщенные арифметические операции.
Сочетание данных различных типов.
Пример: символьная алгебра.
Модульность, объекты и состояние.
Присваивание и внутреннее состояние объектов.
Внутренние переменные состояния.
Преимущества присваивания.
Издержки, связанные с введением присваивания.
Модель вычислений с окружениями.
Правила вычисления.
Применение простых процедур.
Кадры как хранилище внутреннего состояния.
Внутренние определения.
Моделирование при помощи изменяемых данных.
Изменяемая списковая структура.
Представление очередей.
Представление таблиц.
Имитация цифровых схем.
Распространение ограничений.
Параллелизм: время имеет значение.
Природа времени в параллельных системах.
Механизмы управления параллелизмом.
Потоки.
Потоки как задержанные списки.
Бесконечные потоки.
Использование парадигмы потоков.
Потоки и задержанное вычисление.
Модульность функциональных программ и модульность объектов.
Метаязыковая абстракция.
Метациклический интерпретатор.
Ядро интерпретатора.
Представление выражений.
Структуры данных интерпретатора.
Выполнение интерпретатора как программы.
Данные как программы.
Внутренние определения.
Отделение синтаксического анализа от выполнения.
Scheme с вариациями: ленивый интерпретатор.
Нормальный порядок вычислений и аппликативный поря-.
док вычислений.
Интерпретатор с ленивым вычислением.
Потоки как ленивые списки.
Scheme с вариациями недетерминистское вычисление.
Amb и search.
Примеры недетерминистских программ.
Реализация amb-интерпретатора.
Логическое программирование.
Дедуктивный поиск информации.
Как действует система обработки запросов.
Является ли логическое программирование математической логикой?
Реализация запросной системы.
Вычисления на регистровых машинах.
Проектирование регистровых машин.
Язык для описания регистровых машин.
Абстракция в проектировании машин.
Подпрограммы.
Реализация рекурсии с помощью стека.
Обзор системы команд.
Программа моделирования регистровых машин.
Модель машины.
Ассемблер.
Порождение исполнительных процедур для команд.
Отслеживание производительности машины.
Выделение памяти и сборка мусора.
Память как векторы.
Иллюзия бесконечной памяти.
Вычислитель с явным управлением.
Ядро вычислителя с явным управлением.
Вычисление последовательностей и хвостовая рекурсия.
Условные выражения, присваивания и определения.
Запуск вычислителя.
Компиляция.
Структура компилятора.
Компиляция выражений.
Компиляция комбинаций.
Сочетание последовательностей команд.
Пример скомпилированного кода.
Лексическая адресация.
Связь скомпилированного кода с вычислителем.
Литература.
Предметный указатель.
Структура и интерпретация компьютерных программ — это вводный курс по информатике в Массачусетском Технологическом институте (MIT). Он обязателен для всех студентов MIT на специальностях ѕэлектротехникаї и информатика, как одна из четырех частей ѕобщей базовой программы обучения, которая включает еще два курса по электрическим схемам и линейным системам, а также курс по проектированию цифровых систем. Мы принимали участие в развитии этого курса начиная с 1978 года и преподавали этот материал в его нынешней форме начиная с осени 1980 года шестистам-семистам студентам в год. Большая часть этих студентов не имела почти или совсем никакого формального образования в области вычислительной техники, хотя у многих была возможность общения с компьютерами, а некоторые обладали значительным опытом в программировании либо проектировании аппаратуры.
Содержание:
Предисловие.
Предисловие ко второму изданию ix.
Предисловие к первому изданию xi.
Благодарности xv.
Построение абстракций с помощью процедур.
Элементы программирования.
Выражения.
Имена и окружение.
Вычисление комбинаций.
Составные процедуры.
Подстановочная модель применения процедуры.
Условные выражения и предикаты.
Пример: вычисление квадратного корня методом Ньютона.
Процедуры как абстракции типа ѕчерный ящикї.
Процедуры и порождаемые ими процессы.
Линейные рекурсия и итерация.
Древовидная рекурсия.
Порядки роста.
Возведение в степень.
Нахождение наибольшего общего делителя.
Пример: проверка на простоту.
Формулирование абстракций с помощью процедур высших порядков.
Процедуры в качестве аргументов.
Построение процедур с помощью lambda.
Процедуры как обобщенные методы.
Процедуры как возвращаемые значения.
Построение абстракций с помощью данных.
Введение в абстракцию данных.
Пример: арифметические операции над рациональными числами.
Барьеры абстракции.
Что значит слово ѕданныеї?
Расширенный пример: интервальная арифметика.
Иерархические данные и свойство замыкания.
Представление последовательностей.
Иерархические структуры.
Последовательности как стандартные интерфейсы.
Пример: язык описания изображений.
Символьные данные.
Кавычки.
Пример: символьное дифференцирование.
Пример: представление множеств.
Пример: деревья кодирования по Хаффману.
Множественные представления для абстрактных данных.
Представления комплексных чисел.
Помеченные данные.
Программирование, управляемое данными, и аддитивность.
Системы с обобщенными операциями.
Обобщенные арифметические операции.
Сочетание данных различных типов.
Пример: символьная алгебра.
Модульность, объекты и состояние.
Присваивание и внутреннее состояние объектов.
Внутренние переменные состояния.
Преимущества присваивания.
Издержки, связанные с введением присваивания.
Модель вычислений с окружениями.
Правила вычисления.
Применение простых процедур.
Кадры как хранилище внутреннего состояния.
Внутренние определения.
Моделирование при помощи изменяемых данных.
Изменяемая списковая структура.
Представление очередей.
Представление таблиц.
Имитация цифровых схем.
Распространение ограничений.
Параллелизм: время имеет значение.
Природа времени в параллельных системах.
Механизмы управления параллелизмом.
Потоки.
Потоки как задержанные списки.
Бесконечные потоки.
Использование парадигмы потоков.
Потоки и задержанное вычисление.
Модульность функциональных программ и модульность объектов.
Метаязыковая абстракция.
Метациклический интерпретатор.
Ядро интерпретатора.
Представление выражений.
Структуры данных интерпретатора.
Выполнение интерпретатора как программы.
Данные как программы.
Внутренние определения.
Отделение синтаксического анализа от выполнения.
Scheme с вариациями: ленивый интерпретатор.
Нормальный порядок вычислений и аппликативный поря-.
док вычислений.
Интерпретатор с ленивым вычислением.
Потоки как ленивые списки.
Scheme с вариациями недетерминистское вычисление.
Amb и search.
Примеры недетерминистских программ.
Реализация amb-интерпретатора.
Логическое программирование.
Дедуктивный поиск информации.
Как действует система обработки запросов.
Является ли логическое программирование математической логикой?
Реализация запросной системы.
Вычисления на регистровых машинах.
Проектирование регистровых машин.
Язык для описания регистровых машин.
Абстракция в проектировании машин.
Подпрограммы.
Реализация рекурсии с помощью стека.
Обзор системы команд.
Программа моделирования регистровых машин.
Модель машины.
Ассемблер.
Порождение исполнительных процедур для команд.
Отслеживание производительности машины.
Выделение памяти и сборка мусора.
Память как векторы.
Иллюзия бесконечной памяти.
Вычислитель с явным управлением.
Ядро вычислителя с явным управлением.
Вычисление последовательностей и хвостовая рекурсия.
Условные выражения, присваивания и определения.
Запуск вычислителя.
Компиляция.
Структура компилятора.
Компиляция выражений.
Компиляция комбинаций.
Сочетание последовательностей команд.
Пример скомпилированного кода.
Лексическая адресация.
Связь скомпилированного кода с вычислителем.
Литература.
Предметный указатель.