Структура и интерпретация компьютерных программ mobi. Структура и интерпретация компьютерных программ

Структура и интерпретация компьютерных программ

«Структу́ра и интерпрета́ция компью́терных програ́мм» (англ. Structure and Interpretation of Computer Programs - SICP ) - классическая книга Харольда Абельсона и Джеральда Сассмана о программировании , выпущенная издательством в 1985 году . В институте она использовалась как учебник для начального курса программирования 6.001 с одноимённым названием (6.001 был заменён курсом 6.01 , использующим Python). Помимо этого, книгу используют во многих американских учебных заведениях, имеющих курсы, так или иначе связанные с языком Scheme .

Используя Scheme (диалект языка LISP), авторы описали основные концепции программирования, включая абстракцию (данных и исполнения), рекурсию и метаязыковую абстракцию.

Также в книге изложена практическая реализация концепций регистровой машины и метациклического интерпретатора.

Текст второго издания книги распространяется под лицензией Creative Commons (CC-BY-NC версии 3.0).

Примечания

Ссылки

• Официальная страница книги на сайте издательства MIT Press (англ.)
• SICP Wiki - решения и обсуждение заданий из книги (англ.)
• Лекции авторов книги по курсу SICP (англ.)

Wikimedia Foundation . 2010 .

• Структура данных для непересекающихся множеств
• Структура каталожного номера монет России

Смотреть что такое "Структура и интерпретация компьютерных программ" в других словарях:

ГОСТ Р 54136-2010: Системы промышленной автоматизации и интеграция. Руководство по применению стандартов, структура и словарь - Терминология ГОСТ Р 54136 2010: Системы промышленной автоматизации и интеграция. Руководство по применению стандартов, структура и словарь оригинал документа: 4.1 абстрактная деталь (abstract part): Деталь, которая определена только своей… … Словарь-справочник терминов нормативно-технической документации

SICP

Structure and Interpretation of Computer Programs - Структура и интерпретация компьютерных программ Structure and Interpretation of Computer Programs Автор: Харольд Абельсон, Джеральд Сассман Язык оригинала: английский Оригинал издан: 1985 Серия: The MIT electrical engineering and computer science … Википедия

Языки программирования - Язык программирования формальная знаковая система, предназначенная для записи программ. Программа обычно представляет собой некоторый алгоритм в форме, понятной для исполнителя (например, компьютера). Язык программирования определяет набор… … Википедия

Лисп - Семантика: мультипарадигмальный: объектно ориентированное, функциональное, процедурное программирование Появился в: 1958 Автор(ы): Джон Маккарти Типизация данных … Википедия

Lisp - Лисп Семантика: мультипарадигмальный: объектно ориентированное, функциональное, процедурное программирование Появился в: 1958 г. Автор(ы): Джон Маккарти Типизация данных: сильная, динамическая … Википедия

ЛИСП - Семантика: мультипарадигмальный: объектно ориентированное, функциональное, процедурное программирование Появился в: 1958 г. Автор(ы): Джон Маккарти Типизация данных: сильная, динамическая Диалекты: Common … Википедия

ВТО - это международная финансовая организация ВТО: вступление в ВТО, Россия в ВТО, состав ВТО Содержание >>>>>>>>>>>>>> … Энциклопедия инвестора

Искусственный интеллект - Запрос «ИИ» перенаправляется сюда; см. также другие значения. Искусственный интеллект (ИИ, англ. Artificial intelligence, AI) наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. ИИ… … Википедия

АНАЛИЗ СОЦИАЛЬНЫХ СЕТЕЙ - методология и методы исследования связей между социальными акторами. Возникновение этой методологии относят либо к 1930 м, когда в психологии оформился социометрический подход, либо к 1950 м, когда для анализа ранних описательных исследований… … Социология: Энциклопедия

Книги

• Структура и Интерпретация Компьютерных Программ , Харольд Абельсон, Джеральд Джей Сассман. Книга посвящена описанию различных систем программного синтаксиса, анализу перехода от набора алгоритмов к программному коду. Значительное место уделяется обсуждению набора элементарных…

Книга под названием "Структура и Интерпретация Компьютерных Программ " была выпущена в далёком 1979 году. Раньше по ней преподавали вводный курс в программирование среди студентов MIT. Сейчас книга находится в свободном доступе в Интернете, и любой желающий может скачать и изучать её в своё удовольствие. Помимо книги, в сети также есть цикл видео-лекций от авторов, они расположены на ресурсе MIT OpenCourseware, мне кажется они могут неплохо дополнять друг друга по ходу изучения материала.

Чем же примечательна эта книга? Да хотя бы отзывами на Amazon:) Среди рецензентов есть такие личности как Peter Norvig и Paul Graham. К слову, сейчас у книги рейтинг 3.8 из 5, отчего некоторые известные личности недоумевают. А если серьёзно, то это фундаментальный классический труд в области программирования (ничем не хуже небезызвестной книги The Art of Programming от Д. Кнута, которую никто не читал). Единственным непонятным моментом для меня является факт преподавания курса программирования для новичков по этой книге. Представляю как можно напугать новоиспечённых студентов её содержимым. Интересно, есть ли в сети статистика по которой можно узнать много ли людей, посещавших этот "адский" курс, предпочли в дальнейшем поменять свой major:) Если бы организаторы Code.org пропагандировали программирование по этой книге, получился бы знатный epic fail.

Итак, по-моему мнению, книга явно не для новичков в программировании, так как концепции в ней сложны для восприятия людьми "не нюхавшими пороху", более того, понадобится недюжинный запас мотивации и терпения, так как упражнения после каждой секции сложны и требуют от читателя изрядно "попотеть". Но награда стоит того. Я прочитал лишь первую главу этой книги (их всего 5), проработал часть упражнений и, признаюсь, почувствовал как стал лучше разбираться в некоторых вещах (обрёл какой-никакой фундамент).

В общем, к чему я всё это пишу в блоге? А к тому, что собираюсь прочитать всю книгу и проработать как можно больше упражнений (в частности сложных).

План таков:

• Прочитать книгу.
• По ходу чтения также просматривать лекции, так как в книге порой не всегда можно понять материал с 1-го и даже с 10-го раза.
• Выполнять упражнения в каждой секции. Читать конечно хорошо, но лучше всего материал усваивается только на практике.

Читать я буду русское издание ("Добросвет"), у меня имеется бумажный вариант. В случае проблем с переводом, обращаться к оригиналу никто не запрещал. По ходу моего эксперимента, буду писать заметки в этот блог. Надеюсь публичность даст свою толику мотивации (в день блог посещает в среднем 120 человек).

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

Почему в MIT больше не изучают SICP

• Программирование

На днях широкое внимание привлекло состоявшееся в начале года на митапе NYC Lisp выступление Джеральда Джей Сассмана, - одного из авторов великого и могучего SICP, а также крестного отца Scheme. Всему виной - ответ на вопрос, почему в MIT прекратили преподавать ставший легендарным курс 6.001, построенный на основе книги Сассмана и Абельсона «Структура и интерпретация компьютерных программ» (вопрос задан на 59 минуте).

Сассман назвал две причины; впрочем, сразу замечу, что в первой из них нет ничего особенного. К 1997 году Абельсон и Сассман уже устали рассказывать практически одно и то же с 80-ых, поэтому решили оставить преподавание и предложили главе кафедры самостоятельно решить, как поступить с самим курсом. Здесь удивляться действительно нечему - что угодно может осточертерть, если заниматься им достаточно долго.

Впрочем, вторая причина гораздо серьезнее. По мнению Сассмана, они с Абельсоном осознали, что учебный план SICP больше не в силах подготовить инженеров к тому, что представляет собой «инжиниринг» сегодня. В 80-ых и 90-ых инженеры строили сложные системы, комбинируя простые и хорошо изученные «части». Целью SICP было предоставить язык абстракций для рассуждений о таких системах.

Сегодня дела обстоят не так. Сейчас инженеры обычно пишут код для сложного аппаратного обеспечения, которое они не до конца понимают (причем часто это происходит по причине коммерческой тайны, а не в силу лени или недостатка времени - взять ту же Apple и ее технологии). Это же утверждение справедливо и для программного обеспечения, поскольку программные окружения состоят из гигантских библиотек с широчайшей функциональностью. Согласно Сассману, сегодня его студенты большую часть своего времени тратят на чтение мануалов к этим библиотекам, чтобы разобраться в том, как связать их вместе с простой целью - чтобы всё заработало и сделало то, что им нужно.

Со слов Сассмана, «Программирование сегодня больше напоминает науку: вы берете часть библиотеки и «тыкаете» в нее - смотрите на то, что она делает. Затем вы спрашиваете себя, «Могу ли я настроить это так, чтобы оно делало то, что мне нужно?». Подход «анализ через синтез», используемый в SICP, когда вы строите большую систему из простых, маленьких частей, стал неактуальным. Сегодня мы программируем «методом тыка».

В конце концов, в качестве альтернативы для Lisp в MIT был выбран Python. В пользу языка преподавателей склонил тот факт, что для Python доступно значительное количество библиотек, которые позволяют использовать его для решения упражнений в самых разнообразных типах проектов (например, для написания ПО для управлениям роботами).

Впрочем, сам Сассман пошутил, что использование Python было решением в духе «позднего связывания» (“late binding”) - поскольку план обучения SICP был более «последовательным» по сравнению с тем, что заняло его место. Он признался, что вместе с коллегами по прежнему не представляет себе, каким должен быть оптимальный план обучения.

Мнения насчет современного образования в целом и того, чему же все-таки должны обучаться будущие software engineer, расходятся радикально - поэтому предложить однозначный вывод из нововведения невозможно. Согласно одному из них, фундаментальной целью обучения CS является понимание того, как работают компьютеры, а не изучение конкретных языков программирования, и уж подавно - библиотек. С мнением соавтора курса Абельсона насчет конца эры SICP в MIT можно познакомиться по ссылке .

Современная экономика остро нуждается в присутствии на рынке большого количества прикладных программистов, и университеты выполняют свою обязанность в подготовке студентов к будущему. Естественно, выучить всё, особенно на старте карьеры, представляется невозможным; и в то же время, серьезное изучение CS позволяет уменьшить количество плохого кода и страданий коллег-разработчиков.

Одна из баек про MIT всегда говорила о том, что «изучение SICP и Lisp - это тот момент, когда первокурсники начинают оставлять большую часть мира позади себя по части возможности решения проблем (имеется в виду problem solving) и умению делать свою работу»; более того - многие выпускники MIT в дальнейшем как раз и занимаются тем, что пишут библиотеки сами, а не используют чьи-то еще. Думается, что невзирая на жестокие реалии бизнеса, среди нас найдутся те, кому (втайне) гораздо больше удовольствия приносит процесс обучения программированию «с нуля», эффективное использование ресурсов и построение своих велосипедов, чем ежедневные разборки с чужими API и связывание уже готовых open source компонентов в стремлении сделать то, что требуется - то самое «get work done», о котором вел речь Сассман (хотя новый подход в этом отношении действительно ближе к производственным задачам). Однако, времена, когда студентам в ходе обучения приходилось заниматься созданием компиляторов/интерпретаторов, могут отойти в прошлое быстрее, чем нам кажется.

Разумеется, все это - не повод отказываться от знакомства с SICP. По сложившейся традиции, ссылки на саму