Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

Предисловие

Из тех программ, которые мы пишем, некоторые (но всегда меньше, чем хотелось бы)

решают точные математические з адачи, такие, как сортировка последовательности чисел

или нахождение и х максимума, проверка числа на простоту или вычисление квадратного

корня. Такие программы называются алгоритмами, и об их оптимальном поведении из-

вестно довольно много, особенно в том, что касается двух важных параметров: времени

выполнения и потребления памяти. Программист должен владеть хорошими ал горит-

мами и идиомами. Несмотря на то, что некоторые программы сопротивляются точной

спецификации, в обязанности программиста входит оценивать их производительность и

все время пытаться ее улучшить.

Лисп — ветеран, он используется уже около четверти века. Среди живых языков

программирован ия старше него только Фортран. Эти два языка обслуживали нужды

важных прикладных областей: Фортран — естественно-научных и технических вычис-

лений, а Лисп — искусственного интеллекта. Обе эти области по-прежнему важны, а

программисты, работающие в них , настолько привязаны к этим двум языкам, что Лисп

и Фор тран вполне могут остаться в деле еще по крайней мере на четверть столетия.

Лисп изменяется. Scheme, его диалект, используемый в этой книге, развился из пер-

воначального Лиспа и отличается от него в некоторых важных отношениях: в частности,

используются статические области связывания переменных, а функции могут возвра-

щать в к ачестве значений другие функции. По семантической структуре Scheme так же

близка к Алголу 60, как и к ранним вариантам Лиспа. Алгол 60, который уже никогда

не будет живым языком, продолжает жить в генах Scheme и Паскаля. Пожалуй, трудно

найти две более разные культуры программирования, чем те, что образовались вокруг

этих двух языков и используют их в качестве единой валюты. Паскаль служит для по-

строения пирамид — впечатляющих, захватывающих статических структур, создаваемых

армиями, которые укладывают на места тяжел ые плиты. При помощи Лиспа порождают-

ся организмы — впечатляющие, захватывающие динамические структуры, создаваемые

командами, которые собирают их из мерцающих мириад более простых организмов. Ор-

ганизующие принципы в обоих случаях остаются одни и те же, за одним существенным

исключением: программист, пишущий на Лиспе, располагает на порядок большей твор-

ческой свободой в том, что касается функций, которые он создает для использования

другими. Программы на Л испе населяют библиотеки функциями, которые оказываются

настолько полезными, что они переживают породившие их приложения. Таким ростом

полезности мы во многом обязаны списку — исконной лисповской структур е данных.

Простота структуры списков и естественность их использования отражаются в удиви-

тельной общности функций. В Паскале обилие о бъявляемых структур данных ведет к

специализации функций, которая сдерживает и наказывает случайное взаимодействие

между ними. Лучше иметь 100 функций, которые работают с одной структурой дан-

ных, чем 10 функций, работающих с 10 структурами. В результате пирамиде приходится

неподвижно стоять тысячелетиями; организм же будет развиваться или погибнет.

Чтобы увидеть эту разницу, сравните подачу материала и упражнения в этой книге с

тем, что Вы найдете в любом вводном тексте, авторы которого используют Паскаль. Не

поддавайтесь ошибочному впечатлен ию, будто этот текст может усвоить лишь студент

MIT — представитель специфической породы, которая только там и встречается. Нет;

именно такова должна быть всякая серьезная книга, посвященная программированию на

Лиспе, вне зависимости от того, где и кто по ней учится.

Учтите, что это текст о программировании, в отличие от больши нства кн иг по Лиспу,

Предисловие

которые испол ьзуются для подготовки работников в области искусственного интеллек-

та. В конце концов, о сновные программистские заботы вычислительной инженерии и

искусственного интеллекта стремятся к взаимопроникновению по мере того, как соот-

ветствующие системы увеличиваются в объеме. Это объясняе т рост интереса к Лиспу

за пределами искусственного интеллекта.

Как и можно было ожидать, глядя на цели, которые ставят перед собой исследователи

в области искусственного интеллекта, область эта порождает множество значительных

программистских задач. В других программистских культурах такой наплыв задач рож-

дает новые языки. В с амом деле, в любой большой программной задаче один из важных

принципов организации состоит в том, чтобы ограничить и изолировать потоки инфор-

мации в отдельных модулях задачи, изобретая для этого язык. По мере прибл ижения

к гран ицам системы, где мы — люди — взаимодействуем чаще всего, эти языки обыч-

но становятся все менее примитивными. В результате такие системы содержат сложные

функции по обработке языка, повторенные по многу раз. У Лиспа же синтаксис и семан -

тика настолько просты, что синтаксический разбор можно считать элементарной задачей.

Так им образом, методы синтаксического разбора не играют почти ник акой роли в про-

граммах на Лиспе, и построение языковых процессоров редко служит препятствием для

роста и изменения больших Лисп-систем . Наконец, именно эта простота синтаксиса и

семантики возлагает бремя свободы на всех программистов на Лиспе. Никакую програм -

му на Л испе больше, чем в несколько с тр ок длиной, невозможно написать, не населив

ее самостоятельными функциями. Находите новое и приспосабливайте; складывайте и

стройте новыми способами! Я поднимаю тост за программиста на Лиспе, укладывающего

свои мысли в гнезда скобок.

Алан Дж. Перлис

Нью-Хейвен, Коннектикут

Предисловие ко второму

изданию

Возможно ли, что программы не похожи

ни на что другое, что они предназначены

на выброс; что вся штука состоит в том,

чтобы всегда видеть в них мыльный

пузырь?

Алан Дж. Перлис

Материал этой книги был основой вводного курса по информатике в MIT начиная с

1980 года. К тому времени, как было выпущено первое издание, мы преподавали этот

материал в течение четырех лет, и прошло еще двенадцать лет до появления второго

издания. Нам приятно, что наша работа была широко признана и включена в другие

тексты. Мы видели, как наши ученики черпали идеи и программы из этой книги и

на их основе строили новые компьютерные системы и языки. Бук вально по старому

талмудическому каламбуру, наши ученики стали нашими строителями. Мы рады, что у

нас такие одаренные ученики и такие превосходные строители.

Готовя это издание, мы включили в него сотни поправок, которые нам подсказали

как наш собственный преподавательский опыт, так и советы коллег из MIT и других

мест. Мы заново спроек тировали большинство основных программных систем в этой

книге, включая систему обобщенной арифметики, интерпретаторы, имитатор регистро-

вых машин и компилятор; кроме того, мы переписали все примеры программ так, чтобы

любая реализация Scheme, соответствующая стандарту Scheme IEEE (IEEE 1990), была

способна выполнять этот код.

В этом издан ии подчеркиваются несколько новых тем. Самая важная из них состоит

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

времени: объекты, обладающие состоянием , параллельное программирование, функцио-

нальное программирование, ленивые вычисления и недетерминистское программирова-

ние. Мы включили в текст новые разделы по параллельным вычислениям и неде терми-

низму и постарались интегрировать эту тему в материал к ниги на всем ее протяжении.

Первое издание книги почти точно следовало программе нашего одно семестрового

курса в MIT. Рассмотреть весь материал, включая то , что добавлено во втор ом изда-

нии, в течение семестра будет невозможно, так что преподавателю придется выбирать.

В нашей собственной практике мы иногда пропускаем раздел про логическое програм-

Предисловие ко второму изданию

мирование (разде л 4.4); наши студенты использу ют имитатор регистровых машин, но

мы не описываем его реализацию (раздел 5.2); наконец, мы даем лишь беглый обзор

компилятора (раздел 5.5). Даже в таком виде курс остается интенсивным. Некоторые

преподаватели предпочтут ограничиться первыми тремя или четырьмя главами, остав-

ляя прочий материал для последующих курсов.

Сайт World Wide Web http://mitpress.mit.edu/sicp предоставляет поддержку

пользователям этой к ниги. Там ес ть программы из книги, простые задания по програм-

мированию, сопроводительные материалы и реализации диалекта Лиспа Scheme.

∗

В настоящее время (август 2005 г.) на сайте имеется также полный текст англоязычного издания. — прим.

перев.

Предисловие к первому изданию

Компьютер подобен скрипке. Представьте

себе новичка, который сначала

испытывает проигрыватель, затем

скрипку. Скрипка, говорит он, звучит

ужасно. Именно этот аргумент мы

слышали от наших гуманитариев и

специалистов по информатике.

Компьютеры, говорят они, хороши для

определенных целей, но они недостаточно

гибки. Так же и со скрипкой, и с

пишущей машинкой, пока Вы не

научились их использовать.

Марвин Минский.

«Почему программирование — хороший

способ выражения малопонятных и

туманно сформулированных идей»

«Структура и интерпретация компью терных программ» — это вводный курс по ин-

форматике в Массачусетском Технологическом институте (MIT). Он обязателен для всех

студентов MIT на специальностях «электротехника» и «информатика», как одна из че-

тырех частей «общей базовой программы обучения», которая включает еще два курса по

электрическим схемам и линейным системам, а также курс по проектированию цифровых

систем. Мы прини мали участие в развитии этого курса начиная с 1978 года и преподава-

ли этот материал в его нынешней форме начиная с осени 1980 года шестистам–семистам

студентам в год. Большая ч асть этих студентов не имела почти или совсем никако-

го формального образования в области вычислительной техники, хотя у многих была

возможность общения с компьютерами, а неко торые обладали значительным опытом в

программирован ии либо проектировании аппаратуры.

Построение этого вводного курса по информатике отражает две основные з адачи. Во-

первых, мы хотим привить слушателям идею , что компьютерный язык — это не просто

способ застави ть компьютер производить вычисления, а новое формальное средство вы-

ражения методологических идей. Таким образом, программы должны писаться для того,

чтобы их читали люди, и лишь во вторую очередь для выполнения машиной. Во-вторых,

мы считаем, что основной материал, на который должен быть направлен курс этого

уровня, — не синтаксис опреде ленного языка программирования, не умные алгоритмы

Предисловие к первому изданию

для эффективного вычисления определенных функций, даже не математический анализ

алгоритмов и оснований программирования, но методы управления интеллектуальной

сложностью больших программных систем.

Наша цель — развить в студентах, проходящих этот курс, хороший вкус к элементам

стиля и эстетике программирования. Они должны овладеть основными методами управ-

ления сложностью в большой системе, уметь прочитать 50-ти страничную программу,

если она написана в хорошем стиле. Они должны в каждый данный момент понимать,

чего сей час не следует читать и что сейчас не нужно понимать. Они не должны испыты-

вать страха перед модификацией программы, сохраняя при этом дух и стиль исходного

автора.

Все эти умения ни в коем случае не исчерпываются компьютерным программирова-

нием. Методы, которым мы учим и из которых мы черпаем , одни и те же в любом техни-

ческом проектировании. Мы управляем сложностью с помощью построения абстракций,

скрывающих, когда это нужно, детали. Мы управляем сложностью путем установления

стандартных интерфейсов, которые позволяют нам строить системы из единообразных,

хорошо понимаемых кусков способом «смеси и стыковки». Мы управляем сложностью с

помощью построения новых языков для описания проекта, каждый из которых концен-

трирует внимание на определенных деталях проекта и уводит его от других.

В основе нашего подхода к предмету лежит убеждение, что «компьютерная наука» не

является наукой и что ее значение мало связано с компьютерами. Компьютерная револю-

ция — это революция в том, как мы мыслим и как мы выражаем наши мысли. Сущность

этих изменений состоит в появлении дисциплины, которую можно назвать компьютер-

ной эпистемологией, — исследовани я структуры знания с императивной точки зрени я,

в противоположность более декларативной точке зрения классических математических

дисциплин. Математика дает нам структуру, в которой мы можем точно описывать по-

нятия типа «что такое». Вычислительная наука дает нам структуру, в которой мы можем

точно описывать понятия типа «как».

В преподавании мы используем диалект языка программирования Лисп. Мы не учим

формальной стороне языка, поскольку в этом не возникает нужды. Мы просто его ис-

пользуем, и студенты схватывают его з а не сколько дней. В этом состоит одно из боль-

ших преимуществ лиспоподобных языков: в них очень мало способов строить составные

выражения и нет почти ни какой синтаксической структуры. Все формальные детали мо-

гут быть описаны за час, как правила шахмат. Спустя некоторое время мы забываем о

формальных свойствах языка (поскольку их нет) и продолжаем говорить о настоящих

вопросах; определяем, ч то именно мы хотим вычислить, как мы будем разбивать задачу

на куски разумного размера и как потом будем работать с этими кусками. Еще одно пре-

имуще ство Лиспа состоит в том, что он поддерживает (но не навязывает) больше кру пно-

масштабных стратегий разбиения программ на модули, чем любой другой известный нам

язык. Можно строить абстракции процедур и данных, можно испол ьзовать фун кции выс-

ших порядков, чтобы охватить общие шаблоны их использования, можно моделировать

локальное состояние с использованием присваивания и изменения данных, можно связы-

вать части программы с помощью потоков и задержанных вычислений, и можно с легко-

стью реализовывать встроенные языки. Все это включено в диалоговое окружение с пре-

восходной поддержкой пошагового проектирования, построения, тестирования и отладки

программ. Мы благодарны всем поколениям кудесников Лиспа начиная с Джона Мак-

карти, которые создали замечательный инструмент непревзойденной силы и красоты.

Предисловие к первому изданию

Scheme, тот диалект Лиспа, который мы используем, пытается совместить силу и

красоту Лиспа и Алгола. От Лиспа мы берем метаязыковую мощь, которой он обязан

простоте своего си нтаксиса, единообразное представление программ как объектов дан -

ных, выделение данных из кучи с последующей их утилизацией сборщи ком мусора.

От Алгола мы берем лексическую область действия и блоковую структуру, подаренные

нам первопроходцами проектирования языков программирования из комитета по Алголу.

Мы хотим упомянуть Джона Рейнольдса и Питера Ландина, открывших связь Чёрче-

ва лямбда-исчисления со структурой языков программирования. Мы также отдаем дань

признательности математикам, разведавшим эту область за десятилетия до появления

на сцене компьютеров. Среди этих первопроходцев был и Алонсо Чёрч, Беркли Россер,

Стефен Клини и Хаскелл Карри.

Благодарности

Мы хотели бы поблагодарить множество л юдей, которые помогли нам создать эту

книгу и этот кур с.

Наш курс — очевидный интеллектуальный потомок «6.321», замечательного курса по

компьютерной лингвистике и лямбда-исчислению , который читали в MIT в конце 60-х

Джек Уозенкрафт и Артур Эванс мл.

Мы очень обязаны Роберту Фано, который реорганизовал вводную програм му MIT

по электротехнике и информатике, сосредоточившись на принципах технического про-

ектирования. Он вдохновил нас на это предприятие и написал первую программу курса,

из которого развилась эта книга.

Стиль и эстетика программирования, которые мы пытаемся привить читателю, во

многом были разработаны совместно с Гаем Льюисом Стилом мл., который вместе с

Джеральдом Джеем Сассманом участвовал в первоначальной разработке языка Scheme.

В дополнение к этому Дэвид Тёрнер, Питер Хендерсон, Дэн Фридман, Дэвид Уайз

и Уилл Клингер научили нас многим из приемов функционального программирования,

которые излагаются в данной книге.

Джон Мозес научил нас структурировать большие системы. Благодаря его опыту с

системой символьных вычислений Macsyma мы стали понимать, что необходимо избе-

гать усложненно сти структур управления и в первую очередь заботиться о такой орга-

низации данн ых, которая отражает реальную структуру моделируемого мира

Марвин Минский и Сеймур Пэйперт сильно повлияли на формирование нашего под-

хода к программированию и к его месту в нашей интеллектуальной жизни. Благодаря им

мы понимаем, что вычисление дает нам средство выражения и исследования мыслей, ко-

торые иначе были бы слишком сложны, чтобы с ними можно было точно работать. Они

подчеркивают, что способность писать и изменять программы дает студенту мощное

средство, с помощью которого исследование становится естественной деятельностью.

Кроме того, мы полностью согласны с Аланом Перлисом в том, что программиро-

вание — это огромное удовольствие и что нам нужно стараться поддерживать радость

программирован ия. Часть этой радости приходит от наблюдения за работой великих ма-

стеров. Нам выпало счастье быть учениками у ног Билла Госпера и Ричарда Гринблатта.

Трудно перечислить всех тех, кто принял участие в развитии программы нашего кур-

са. Мы благодарим всех лекторов, инструкторов и тьюторов, которые работали с нами в

прошедшие пятнадцать лет и потратили много часов сверхурочной работы на наш пред-

мет, особенно Билла Сиберта, Альберта Мейера, Джо Стоя, Рэнди Дэвиса, Луи Брэйда,

Эрика Гримсона, Рода Брукса, Л инна Стейна и Питера Соловитца. Мы бы хотели особо

отметить выдающийся педагогический вклад Франклина Турбака, который теперь пр е-

Благодарности

подает в Уэллесли: е го работа по обучению младшекурсников установила стандарт, на

который мы все можем равняться. Мы благодарны Джерри Сальтцеру и Джиму Милле-

ру, которые помогли нам бороться с тайнами параллельных вычислени й, а также Питеру

Соловитцу и Дэвиду Макаллестеру за их вклад в представление недетерминистских

вычислений в главе 4.

Много людей вложило немалый труд в преподавание этого материала и в других

университетах. Вот некоторые из тех, с кем мы тесно общались в работе: это Джекоб

Кацнельсон в Технионе, Хэрди Майер в Калифорнийском университете в Ирвине, Джо

Стой в Оксфорде, Эл иша Сэкс в университете Пердью и Ян Коморовский в Норвежском

университете Науки и Техники. Мы гордимся коллегами, которые получили награды

за адаптацию этого предмета в других университетах: это Кеннет Йип в Йеле, Брайан

Харви в Калифорнийском университете в Беркли и Дон Хаттенлохер в Корнелле.

Эл Мойе дал нам возможность прочитать этот материал инженерам компании Хьюлетт-

Паккард и устроил производство видеоверсии этих лекций. Мы хотели бы поблагодарить

одаренных преподавателей — в особенности Джима Миллера, Билла Сиберта и Майка

Айзенберга, — которые разработали курсы повышения квалификации с испол ьзованием

этих видеоматериалов и преподавали по ним в различных университетах и корпораци ях

по всему миру.

Множество работников образования проделал и значительную работу по переводу

первого издания. Мишель Бриан, Пьер Шамар и Андре Пик сделали французско е из-

дан ие, Сюзанна Дэниелс-Хэрольд выполнила немецкий перевод, а Фумио Мото

еси —

японский. Мы не знаем авторов китайского издания, однако считаем для себя честью

быть выбранными в качестве объекта «неавторизованного» перевода.

Трудно перечисл ить всех людей, внесших технический вклад в разработку систем

программирован ия на языке Scheme, которые мы используем в учебных целях. Кро-

ме Гая Стила, в список важнейших волшебников входят Крис Хансон, Джо Боубир,

Джим Миллер, Гильермо Росас и Стефен Адамс. Кроме них, существен ное время и

силы вложили Ричард Столлман, Алан Боуден, Кент Питман, Джон Тафт, Нил Мэйл,

Джон Лэмпинг, Гуин Оснос, Трейси Ларраби, Джордж Карретт, Сома Чаудхури, Билл

Киаркиаро, Стивен Кирш, Лей Клотц, Уэйн Носс, Тодд Кэсс, Патрик О’Доннелл, Ке-

вин Теобальд, Дэниел Вайзе, Кеннет Синклер, Энтони Кортеманш, Генри М. Ву, Эндрю

Берлин и Рут Шью.

Помимо авторов ре ализации MIT, мы хотели бы поблагодарить множество людей,

работавших над стандартом Scheme IEEE, в том числе Уильяма Клингера и Джоната-

на Риса, ко торые редактировали R

RS, а также Криса Хэйнса, Дэвида Бартли, Криса

Хансона и Джима Миллера, которые подготовили стандарт IEEE.

Долгое время Дэн Фридман был лидером сообщества языка Scheme. Работа сообще-

ства в более широком плане переходит границы вопросов разработки языка и включает

значительные инновации в образовании, такие как курс для старшей школы, основан-

ный на EdScheme компании Schemer’s Inc. и замечательные книги Майка Айзенберга,

Брайана Харви и М этью Райта.

Мы ценим труд тех, кто при нял участие в превращении этой работы в настоящую

книгу, особенно Терри Элинга, Ларри Коэна и Пола Бетджа из издательства MIT Press.

Элла Мэйзел нашла з амечательный рисунок для обложки. Что касается второго издания,

то мы особенно благодарны Бернарду и Элле Мэйзел за помощь с оформлением книги, а

также Дэвиду Джонсу, великому волшебнику T

Xа. Мы также в долгу перед чи тателя-

Благодарности

ми, сделавшими проницательные замечания по новому проекту: Джекобу Кацнельсону,

Харди Мейеру, Джиму Миллеру и в особенности Брайану Харви, который был для этой

книги тем же, кем Джули была для его книги Просто Scheme.

Наконец, мы хотели бы выразить признательность организациям, которые поддержи-

вали нашу работу в течение этих лет. Мы благодарны компании Хьюлетт-Паккард за

поддержку, которая стала возможной благодаря Айре Гольдстейну и Джоэлю Бирнбау-

му, а также агентству DARPA за поддержку, которая стала возможной благодаря Бобу

Кану.

∗

Со своей стороны хотелось бы поблагодарить Константина Добкина, Андрея Комеча, Сергея Коропа, Алек-

сея Овчинникова, Алекса Отта, Вадима Радионова, Марию Рубинштейн и особен но Бориса Смилгу. — прим.

перев.