«Julie Sussman with Structure and Interpretation of Computer Programs The MIT Press Cambridge, Massatchusetts London, England The McGraw-Hill Companies, Inc. New York St.Louis San Francisco Montreal Toronto Харольд ...»

Harold Abelson

Gerald Jay Sussman

and

Julie Sussman

with

Structure and Interpretation

of Computer Programs

The MIT Press

Cambridge, Massatchusetts London, England

The McGraw-Hill Companies, Inc.

New York St.Louis San Francisco Montreal Toronto Харольд Абельсон Джеральд Джей Сассман Джули Сассман при участии Структура и интерпретация компьютерных программ Добросвет, 2006 3 Эта книга посвящается, с уважением и любовью, духу, который живет внутри компьютера.

“Мне кажется, чрезвычайно важно, чтобы мы, занимаясь информатикой, получали радость от общения с компьютером. С самого начала это было громадным удовольствием. Конечно, время от времени встревали заказчики, и через какое-то время мы стали серьезно относиться к их жалобам. Нам стало казаться, что мы вправду отвечаем за то, чтобы эти машины использовались успешно и безошибочно. Я не думаю, что это так. Я считаю, что мы отвечаем за то, чтобы их тренировать, указывать им новые направления и поддерживать уют в доме. Я надеюсь, что информатика никогда не перестанет быть радостью. Я надеюсь, что мы не превратимся в миссионеров. Не надо чувствовать себя продавцом Библий. Таких в мире и так достаточно. То, что Вы знаете о программировании, могут выучить и другие. Не думайте, что в ваших руках ключ к успешной работе с компьютерами. Что у Вас, как я думаю и надеюсь, есть — это разум: способность увидеть в машине больше, чем Вы видели, когда Вас впервые к ней подвели, увидеть, что Вы способны сделать ее б льшим.” o Алан Дж. Перлис (1 апреля 1922 – 7 февраля 1990) Оглавление Предисловие............................................................................ Предисловие ко второму изданию..................................................... Предисловие к первому изданию...................................................... Благодарности.......................................................................... 1. Построение абстракций с помощью процедур..................................... 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. Процедуры как возвращаемые значения........................... 2. Построение абстракций с помощью данных....................................... 2.1. Введение в абстракцию данных.......................................... 2.1.1. Пример: арифметические операции над рациональными числами.... 2.1.2. Барьеры абстракции.............................................. Оглавление 2.1.3. Что значит слово «данные»?...................................... 2.1.4. Расширенный пример: интервальная арифметика................... 2.2. Иерархические данные и свойство замыкания............................ 2.2.1. Представление последовательностей............................... 2.2.2. Иерархические структуры........................................ 2.2.3. Последовательности как стандартные интерфейсы.................. 2.4. Множественные представления для абстрактных данных.................. 2.4.3. Программирование, управляемое данными, и аддитивность......... 3.1. Присваивание и внутреннее состояние объектов.......................... 3.1.3. Издержки, связанные с введением присваивания................... 3.2.3. Кадры как хранилище внутреннего состояния...................... 3.3. Моделирование при помощи изменяемых данных......................... 3.5.5. Модульность функциональных программ 4.1.7. Отделение синтаксического анализа от выполнения................ 4.2. Scheme с вариациями: ленивый интерпретатор............................ 4.3. Scheme с вариациями — 4.4.3. Является ли логическое программирование математической логикой? 5.2. Программа моделирования регистровых машин........................... 5.2.3. Порождение исполнительных процедур для команд................. 5.2.4. Отслеживание производительности машины....................... 5.4.2. Вычисление последовательностей и хвостовая рекурсия............ 5.4.3. Условные выражения, присваивания и определения................. 5.5.4. Сочетание последовательностей команд............................ 5.5.7. Связь скомпилированного кода с вычислителем.................... Предисловие Программированием занимаются учителя, генералы, диетологи, психологи и родители. Программированию подвергаются армии, ученики и некоторые виды обществ. При решении крупных задач приходится применять последовательно множество программ, б льшая часть которых возникает прямо в процессе решения. Эти программы изобилуо ют деталями, относящимися к той конкретной задаче, которую они решают. Если же Вы хотите оценить программирование как интеллектуальную деятельность особого рода, то Вам следует обратиться к программированию компьютеров; читайте и пишите компьютерные программы — много программ. Не так уж важно, что будет в них написано и как они будут применяться. Важно то, насколько хорошо они работают и как гладко стыкуются с другими программами при создании еще более крупных программ.

Программист должен равно стремиться и к совершенству в деталях, и к соразмерности сложного целого. В книге, которую Вы держите в руках, словом «программирование» мы будем обозначать прежде всего создание, выполнение и изучение программ, написанных на одном из диалектов языка Лисп и предназначенных для выполнения на цифровом компьютере. Использование Лиспа не ограничивает нас в том, чт мы можем описать в наших программах, — лишь в способе их выражения.

Продвигаясь по материалу этой книги, мы будем встречаться с тремя группами явлений: человеческий разум, совокупности компьютерных программ и компьютер. Всякая компьютерная программа — это порожденная человеческим разумом модель реального либо умозрительного процесса. Эти процессы, возникающие из нашего опыта и мысли, многочисленны, сложны в деталях, и мы всегда понимаем их лишь частично. Редко бывает так, что компьютерные программы отображают их к нашему окончательному удовлетворению. Таким образом, хотя наши программы представляют собой тщательно сработанные дискретные совокупности символов, мозаики переплетенных функций, они непрерывно развиваются: мы изменяем их по мере того, как наше восприятие модели приобретает все большую глубину, расширяется и обобщается, до тех пор, пока модель не достигнет, наконец, метастабильного состояния в рамках следующей модели, над которой нам предстоит биться. Радостное возбуждение, сопутствующее компьютерному программированию, происходит из постоянного раскрытия в голове и в компьютере все новых выраженных в виде программ механизмов и из взрыва восприятия, который они порождают. Искусство выражает наши мечты. Компьютер исполняет их под видом программ!

При всей своей мощности, компьютер требователен и придирчив. Ему нужны верные программы, и то, что мы хотим ему сказать, должно быть выражено точно в каждой мелочи. Как и при всякой другой работе с символами, мы убеждаемся в правильности программ через доказательство. Самому Лиспу можно сопоставить семантику (между прочим, тоже модель), и если функцию программы можно выразить, скажем, в терминах исчисления предикатов, то логические методы позволят нам вывести формальное доказательство ее корректности. К сожалению, когда программы становятся большими и сложными, что с ними всегда и происходит, адекватность, непротиворечивость и корректность самих спецификаций становится предметом сомнений, так что большие программы редко сопровождаются полными формальными доказательствами корректности. Поскольку большие программы вырастают из малых, нам необходимо обзавестись арсеналом программных структур, в правильности которых мы можем быть уверены — их можно назвать идиомами — и научиться объединять их в структуры большего размера с помощью организационных методов, ценность которых также доказана. Эти методы подробно обсуждаются в книге, и их понимание существенно для участия в прометеевском предприятии под названием «программирование». Для умения создавать большие, значительные программы нет лучшего помощника, чем свободное владение мощными организационными методами. И наоборот: затраты, связанные с написанием больших программ, побуждают нас изобретать новые методы уменьшения веса функций и деталей, входящих в эти программы.

В отличие от программ, компьютеры должны повиноваться законам физики. Если мы хотим, чтобы они работали быстро — по нескольку наносекунд на смену состояния, — электроны в их цепях не должны проходить большие расстояния (более полуметра).

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

Так или иначе, аппаратура всегда работает ниже того уровня, на котором мы бы хотели программировать. Процессы, посредством которых наши программы на Лиспе переводятся в «машинные» программы, сами являются абстрактными моделями, которые мы воплощаем в программах. Их изучение и реализация многое дают для понимания организационных методов, направленных на программирование произвольных моделей.

Разумеется, так можно смоделировать и сам компьютер. Подумайте об этом: поведение мельчайшего переключателя моделируется квантовой механикой, которая описывается дифференциальными уравнениями, точное поведение которых фиксируется в численных приближениях, представленных в виде компьютерных программ, которые выполняются на компьютере, составленном из... — и так без конца!

Раздельное выделение трех групп явлений — не просто вопрос тактического удобства. Хотя эти группы и остаются, как говорится, в голове, но, проводя это разделение, мы позволяем потоку символов между тремя группами двигаться быстрее. В человеческом опыте с этим потоком по богатству, живости и обилию возможностей сравнится разве что сама эволюция жизни. Отношения между разумом человека, программами и компьютером в лучшем случае метастабильны. Компьютерам никогда не хватает мощности и быстродействия. Каждый новый прорыв в технологии производства аппаратуры ведет к появлению более масштабных программных проектов, новых организационных принципов и к обогащению абстрактных моделей. Пусть каждый читатель время от времени спрашивает себя: «А зачем, к чему все это?» — только не слишком часто, чтобы удовольствие от программирования не сменилось горечью философского тупика.

Из тех программ, которые мы пишем, некоторые (но всегда меньше, чем хотелось бы) решают точные математические задачи, такие, как сортировка последовательности чисел или нахождение их максимума, проверка числа на простоту или вычисление квадратного корня. Такие программы называются алгоритмами, и об их оптимальном поведении известно довольно много, особенно в том, что касается двух важных параметров: времени выполнения и потребления памяти. Программист должен владеть хорошими алгоритмами и идиомами. Несмотря на то, что некоторые программы сопротивляются точной спецификации, в обязанности программиста входит оценивать их производительность и все время пытаться ее улучшить.

Лисп — ветеран, он используется уже около четверти века. Среди живых языков программирования старше него только Фортран. Эти два языка обслуживали нужды важных прикладных областей: Фортран — естественно-научных и технических вычислений, а Лисп — искусственного интеллекта. Обе эти области по-прежнему важны, а программисты, работающие в них, настолько привязаны к этим двум языкам, что Лисп и Фортран вполне могут остаться в деле еще по крайней мере на четверть столетия.

Лисп изменяется. 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, в том числе Уильяма Клингера и Джонатана Риса, которые редактировали R4 RS, а также Криса Хэйнса, Дэвида Бартли, Криса Хансона и Джима Миллера, которые подготовили стандарт IEEE.

Долгое время Дэн Фридман был лидером сообщества языка Scheme. Работа сообщества в более широком плане переходит границы вопросов разработки языка и включает значительные инновации в образовании, такие как курс для старшей школы, основанный на EdScheme компании Schemer’s Inc. и замечательные книги Майка Айзенберга, Брайана Харви и Мэтью Райта.

Мы ценим труд тех, кто принял участие в превращении этой работы в настоящую книгу, особенно Терри Элинга, Ларри Коэна и Пола Бетджа из издательства MIT Press.

Элла Мэйзел нашла замечательный рисунок для обложки. Что касается второго издания, то мы особенно благодарны Бернарду и Элле Мэйзел за помощь с оформлением книги, а также Дэвиду Джонсу, великому волшебнику TEXа. Мы также в долгу перед читателяБлагодарности ми, сделавшими проницательные замечания по новому проекту: Джекобу Кацнельсону, Харди Мейеру, Джиму Миллеру и в особенности Брайану Харви, который был для этой книги тем же, кем Джули была для его книги Просто Scheme.

Наконец, мы хотели бы выразить признательность организациям, которые поддерживали нашу работу в течение этих лет. Мы благодарны компании Хьюлетт-Паккард за поддержку, которая стала возможной благодаря Айре Гольдстейну и Джоэлю Бирнбауму, а также агентству DARPA за поддержку, которая стала возможной благодаря Бобу Кану.

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

перев.

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

ПОСТРОЕНИЕ АБСТРАКЦИЙ С ПОМОЩЬЮ

ПРОЦЕДУР

Мы собираемся изучать понятие вычислительного процесса (computational process).

Вычислительные процессы — это абстрактные существа, которые живут в компьютерах.

Развиваясь, процессы манипулируют абстракциями другого типа, которые называются данными (data). Эволюция процесса направляется набором правил, называемым программой (program). В сущности, мы заколдовываем духов компьютера с помощью своих чар.

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

На исправно работающем компьютере вычислительный процесс выполняет программы точно и безошибочно. Таким образом, подобно ученику чародея, программисты-новички должны научиться понимать и предсказывать последствия своих заклинаний. Даже мелкие ошибки (их обычно называют блохами (bugs) или глюками (glitches)), могут привести к сложным и непредсказуемым последствиям.

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

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

Специалисты по программному обеспечению умеют организовывать программы так, чтобы быть потом обоснованно уверенными: получившиеся процессы будут выполнять те задачи, для которых они предназначены. Они могут изобразить поведение системы заранее. Они знают, как построить программу так, чтобы непредвиденные проблемы не привели к катастрофическим последствиям, а когда эти проблемы возникают, программисты умеютотлаживать (debug) свои программы. Хорошо спроектированные вычислительные системы, подобно хорошо спроектированным автомобилям или ядерным реакторам, построены модульно, так что их части могут создаваться, заменяться и отлаживаться по отдельности.

Программирование на Лиспе Для описания процессов нам нужен подходящий язык, и с этой целью мы используем язык программирования Лисп. Точно так же, как обычные наши мысли чаще всего выражаются на естественном языке (например, английском, французском или японском), а описания количественных явлений выражаются языком математики, наши процедурные мысли будут выражаться на Лиспе. Лисп был изобретен в конце 1950-х как формализм для рассуждений об определенном типе логических выражений, называемых уравнения рекурсии (recursion equations), как о модели вычислений. Язык был придуман Джоном Маккарти и основывается на его статье «Рекурсивные функции над символьными выражениями и их вычисление с помощью машины» (McCarthy 1960).

Несмотря на то, что Лисп возник как математический формализм, это практический язык программирования. Интерпретатор (interpreter) Лиспа представляет собой машину, которая выполняет процессы, описанные на языке Лисп. Первый интерпретатор Лиспа написал сам Маккарти с помощью коллег и студентов из Группы по Искусственному Интеллекту Исследовательской лаборатории по Электронике MIT и Вычислительного центра MIT1. Лисп, чье название происходит от сокращения английских слов LISt Processing (обработка списков), был создан с целью обеспечить возможность символьной обработки для решения таких программистских задач, как символьное дифференцирование и интегрирование алгебраических выражений. С этой целью он содержал новые объекты данных, известные под названием атомов и списков, что резко отличало его от других языков того времени.

Лисп не был результатом срежиссированного проекта. Он развивался неформально, экспериментальным путем, с учетом запросов пользователей и прагматических соображений реализации. Неформальная эволюция Лиспа продолжалась долгие годы, и сообРуководство программиста по Лиспу 1 появилось в 1960 году, а Руководство программиста по Лиспу 1.5 (McCarthy 1965) в 1965 году. Ранняя история Лиспа описана в McCarthy 1978.

щество пользователей Лиспа традиционно отвергало попытки провозгласить какое-либо «официальное» описание языка. Вместе с гибкостью и изяществом первоначального замысла такая эволюция позволила Лиспу, который сейчас по возрасту второй из широко используемых языков (старше только Фортран), непрерывно адаптироваться и вбирать в себя наиболее современные идеи о проектировании программ. Таким образом, сегодня Лисп представляет собой семью диалектов, которые, хотя и разделяют большую часть изначальных свойств, могут существенным образом друг от друга отличаться. Тот диалект, которым мы пользуемся в этой книге, называется Scheme (Схема)2.

Из-за своего экспериментального характера и внимания к символьной обработке первое время Лисп был весьма неэффективен при решении вычислительных задач, по крайней мере по сравнению с Фортраном. Однако за прошедшие годы были разработаны компиляторы Лиспа, которые переводят программы в машинный код, способный производить численные вычисления с разумной эффективностью. А для специализированных приложений Лисп удавалось использовать весьма эффективно3. Хотя Лисп и не преодолел пока свою старую репутацию безнадежно медленного языка, в наше время он используется во многих приложениях, где эффективность не является главной заботой.

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

Но коль скоро Лисп не похож на типичные языки, почему же мы тогда используем его как основу для нашего разговора о программировании? Потому что этот язык обладает уникальными свойствами, которые делают его замечательным средством для изучения важнейших конструкций программирования и структур данных, а также для соотнесения их с деталями языка, которые их поддерживают. Самое существенное из этих свойств — то, что лисповские описания процессов, называемые процедурами (procedures), сами по себе могут представляться и обрабатываться как данные Лиспа. Важность этого в том, что существуют мощные методы проектирования программ, которые опираются на возможность сгладить традиционное различение «пассивных» данных и «активных» процессов. Как мы обнаружим, способность Лиспа рассматривать процедуры в качестве данных делает его одним из самых удобных языков для исследования этих методов. Способность 2 Большинство крупных Лисп-программ 1970х, были написаны на одном из двух диалектов: MacLisp (Moon 1978; Pitman 1983), разработанный в рамках проекта MAC в MIT, и InterLisp (Teitelman 1974), разработанный в компании «Болт, Беранек и Ньюман» и в Исследовательском центре компании Xerox в Пало Альто.

Диалект Portable Standard Lisp (Переносимый Стандартный Лисп, Hearn 1969; Griss 1981) был спроектирован так, чтобы его легко было переносить на разные машины. MacLisp породил несколько поддиалектов, например Franz Lisp, разработанный в Калифорнийском университете в Беркли, и Zetalisp (Moon 1981), который основывался на специализированном процессоре, спроектированном в лаборатории Искусственного Интеллекта в MIT для наиболее эффективного выполнения программ на Лиспе. Диалект Лиспа, используемый в этой книге, называется Scheme (Steele 1975). Он был изобретен в 1975 году Гаем Льюисом Стилом мл. и Джеральдом Джеем Сассманом в лаборатории Искусственного Интеллекта MIT, а затем заново реализован для использования в учебных целях в MIT. Scheme стала стандартом IEEE в 1990 году (IEEE 1900). Диалект Common Lisp (Steele 1982; Steele 1990) был специально разработан Лисп-сообществом так, чтобы сочетать свойства более ранних диалектов Лиспа и стать промышленным стандартом Лиспа. Common Lisp стал стандартом ANSI в 1994 году (ANSI 1994).

3 Одним из таких приложений был пионерский эксперимент, имевший научное значение — интегрирование движения Солнечной системы, которое превосходило по точности предыдущие результаты примерно на два порядка и продемонстрировало, что динамика Солнечной системы хаотична. Это вычисление стало возможным благодаря новым алгоритмам интегрирования, специализированному компилятору и специализированному компьютеру; причем все они были реализованы с помощью программных средств, написанных на Лиспе (Abelson et al. 1992; Sussman and Wisdom 1992).

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

1.1. Элементы программирования Мощный язык программирования — это нечто большее. чем просто средство, с помощью которого можно учить компьютер решать задачи. Язык также служит средой, в которой мы организуем свое мышление о процессах. Таким образом, когда мы описываем язык, мы должны уделять особое внимание тем средствам, которые в нем имеются для того, чтобы комбинировать простые понятия и получать из них сложные. Всякий язык программирования обладает тремя предназначенными для этого механизмами:

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

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

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

В программировании мы имеем дело с двумя типами объектов: процедурами и данными. (Впоследствии мы обнаружим, что на самом деле большой разницы между ними нет.) Говоря неформально, данные — это «материал», который мы хотим обрабатывать, а процедуры — это описания правил обработки данных. Таким образом, от любого мощного языка программирования требуется способность описывать простые данные и элементарные процедуры, а также наличие средств комбинирования и абстракции процедур и данных.

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

4 Называть числа «простыми данными» — это бесстыдный блеф. На самом деле работа с числами является одной из самых сложных и запутанных сторон любого языка программирования. Вот некоторые из возникающих при этом вопросов: Некоторые компьютеры отличают целые числа (integers), вроде 2, от вещественных (real numbers), вроде 2.71. Отличается ли вещественное число 2.00 от целого 2? Используются ли одни и те же арифметические операции для целых и для вещественных чисел? Что получится, если 6 поделить на 2:

3 или 3.0? Насколько большие числа мы можем представить? Сколько десятичных цифр после запятой мы можем хранить? Совпадает ли диапазон целых чисел с диапазоном вещественных? И помимо этих вопросов, разумеется, существует множество проблем, связанных с ошибками округления — целая наука численного анализа. Поскольку в этой книге мы говорим о проектировании больших программ, а не о численных методах, все эти проблемы мы будем игнорировать. Численные примеры в этой главе будут демонстрировать такое поведение при округлении, какое можно наблюдать, если использовать арифметические операции, сохраняющие при работе с вещественными числами ограниченное число десятичных цифр после запятой.

1.1.1. Выражения Самый простой способ начать обучение программированию — рассмотреть несколько типичных примеров работы с интерпретатором диалекта Лиспа Scheme. Представьте, что Вы сидите за терминалом компьютера. Вы печатаете выражение (expression), а интерпретатор отвечает, выводя результат вычисления (evaluation) этого выражения.

Один из типов элементарных выражений, которые Вы можете вводить — это числа.

(Говоря точнее, выражение, которое Вы печатаете, состоит из цифр, представляющих число по основанию 10.) Если Вы дадите Лиспу число интерпретатор ответит Вам, напечатав Выражения, представляющие числа, могут сочетаться с выражением, представляющим элементарную процедуру (скажем, + или *), так что получается составное выражение, представляющее собой применение процедуры к этим числам. Например:

(+ 137 349) (- 1000 334) (* 5 99) (/ 10 5) (+ 2.7 10) 12. Выражения такого рода, образуемые путем заключения списка выражений в скобки с целью обозначить применение функции к аргументам, называются комбинациями (combinations). Самый левый элемент в списке называетсяоператором (operator), а остальные элементы — операндами (operands). Значение комбинации вычисляется путем применения процедуры, задаваемой оператором, каргументам (arguments), которые являются значениями операндов.

Соглашение, по которому оператор ставится слева от операндов, известно как префиксная нотация (prex notation), и поначалу оно может сбивать с толку, поскольку существенно отличается от общепринятой математической записи. Однако у префиксной нотации есть несколько преимуществ. Одно из них состоит в том, что префиксная запись может распространяться на процедуры с произвольным количеством аргументов, как в следующих примерах:

5 Здесь и далее, когда нам нужно будет подчеркнуть разницу между вводом, который набирает на терминале пользователь, и выводом, который производит компьютер, мы будем изображать последний наклонным шрифтом.

(+ 21 35 12 7) (* 25 4 12) Не возникает никакой неоднозначности, поскольку оператор всегда находится слева, а вся комбинация ограничена скобками.

Второе преимущество префиксной нотации состоит в том, что она естественным образом расширяется, позволяя комбинациям вкладываться (nest) друг в друга, то есть допускает комбинации, элементы которых сами являются комбинациями:

(+ (* 3 5) (- 10 6)) Не существует (в принципе) никакого предела для глубины такого вложения и общей сложности выражений, которые может вычислять интерпретатор Лиспа. Это мы, люди, путаемся даже в довольно простых выражениях, например (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) а интерпретатор с готовностью вычисляет его и дает ответ 57. Мы можем облегчить себе задачу, записывая такие выражения в форме (+ (* Эти правила форматирования называются красивая печать (pretty printing). Согласно им, всякая длинная комбинация записывается так, чтобы ее операнды выравнивались вертикально. Получающиеся отступы ясно показывают структуру выражения6.

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

Этот способ работы иногда называют циклом чтение-вычисление-печать (read-eval-print loop). Обратите особое внимание на то, что не нужно специально просить интерпретатор напечатать значение выражения7.

1.1.2. Имена и окружение Одна из важнейших характеристик языка программирования — какие в нем существуют средства использования имен для указания на вычислительные объекты. Мы 6 Как правило, Лисп-системы содержат средства, которые помогают пользователям форматировать выражения. Особенно удобны две возможности: сдвигать курсор на правильную позицию для красивой печати каждый раз, когда начинается новая строка и подсвечивать нужную левую скобку каждый раз, когда печатается правая.

7 Лисп следует соглашению, что у всякого выражения есть значение. Это соглашение, вместе со старой репутацией Лиспа как неэффективного языка, послужило источником остроумного замечания Алана Перлиса (парафразы из Оскара Уайльда), что «Программисты на Лиспе знают значение всего на свете, но ничему не знают цену».

говорим, что имя обозначает переменную (variable), чьим значением (value) является объект.

В диалекте Лиспа Scheme мы даем вещам имена с помощью слова define. Предложение (define size 2) заставляет интерпретатор связать значение 2 с именем size8. После того, как имя size связано со значением 2, мы можем указывать на значение 2 с помощью имени:

size (* 5 size) Вот еще примеры использования define:

(define pi 3.14159) (define radius 10) (* pi (* radius radius)) 314. (define circumference (* 2 pi radius)) circumference 62. Слово define служит в нашем языке простейшим средством абстракции, поскольку оно позволяет нам использовать простые имена для обозначения результатов сложных операций, как, например, вычисленная только что длина окружности — circumference.

Вообще говоря, вычислительные объекты могут быть весьма сложными структурами, и было бы очень неудобно, если бы нам приходилось вспоминать и повторять все их детали каждый раз, когда нам захочется их использовать. На самом деле сложные программы конструируются методом построения шаг за шагом вычислительных объектов возрастающей сложности. Интерпретатор делает такое пошаговое построение программы особенно удобным, поскольку связи между именами и объектами могут создаваться последовательно по мере взаимодействия программиста с компьютером. Это свойство интерпретаторов облегчает пошаговое написание и тестирование программ, и во многом благодаря именно ему получается так, что программы на Лиспе обычно состоят из большого количества относительно простых процедур.

Ясно, что раз интерпретатор способен ассоциировать значения с символами и затем вспоминать их, то он должен иметь некоторого рода память, сохраняющую пары имя-объект. Эта память называется окружением (environment) (а точнее, глобальным 8 Мы не печатаем в этой книге ответы интерпретатора при вычислении определений, поскольку они зависят от конкретной реализации языка.

окружением (global environment), поскольку позже мы увидим, что вычисление может иметь дело с несколькими окружениями)9.

1.1.3. Вычисление комбинаций Одна из наших целей в этой главе — выделить элементы процедурного мышления.

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

• Чтобы вычислить комбинацию, требуется:

– Вычислить все подвыражения комбинации.

– Применить процедуру, которая является значением самого левого подвыражения (оператора) к аргументам — значениям остальных подвыражений (операндов).

Даже в этом простом правиле видны несколько важных свойств процессов в целом.

Прежде всего, заметим, что на первом шаге для того, чтобы провести процесс вычисления для комбинации, нужно сначала проделать процесс вычисления для каждого элемента комбинации. Таким образом, правило вычисления рекурсивно (recursive) по своей природе; это означает, что в качестве одного из своих шагов оно включает применение того же самого правила10.

Заметьте, какую краткость понятие рекурсии придает описанию того, что в случае комбинации с глубоким вложением выглядело бы как достаточно сложный процесс. Например, чтобы вычислить (* (+ 2 (* 4 6)) требуется применить правило вычисления к четырем различным комбинациям. Картину этого процесса можно получить, нарисовав комбинацию в виде дерева, как показано на рис. 1.1. Каждая комбинация представляется в видевершины, а ее оператор и операнды — в виде ветвей, исходящих из этой вершины. Концевые вершины (то есть те, из которых не исходит ни одной ветви) представляют операторы или числа. Рассматривая вычисление как дерево, мы можем представить себе, что значения операндов распространяются от концевых вершин вверх и затем комбинируются на все более высоких уровнях. Впоследствии мы увидим, что рекурсия — это вообще очень мощный метод обработки иерархических, древовидных объектов. На самом деле форма правила вычисления «распространить значения наверх» является примером общего типа процессов, известного как накопление по дереву (tree accumulation).

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

10 Может показаться странным, что правило вычисления предписывает нам в качестве части первого шага вычислить самый левый элемент комбинации, — ведь до сих пор это мог быть только оператор вроде + или *, представляющий встроенную процедуру, например, сложение или умножение. Позже мы увидим, что полезно иметь возможность работать и с комбинациями, чьи операторы сами по себе являются составными выражениями.

Рис. 1.1. Вычисление, представленное в виде дерева.

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

• значением числовых констант являются те числа, которые они называют;

• значением встроенных операторов являются последовательности машинных команд, которые выполняют соответствующие операции; и • значением остальных имен являются те объекты, с которыми эти имена связаны в окружении.

Мы можем рассматривать второе правило как частный случай третьего, постановив, что символы вроде + и * тоже включены в глобальное окружение и связаны с последовательностями машинных команд, которые и есть их «значения». Главное здесь — это роль окружения при определении значения символов в выражениях. В таком диалоговом языке, как Лисп, не имеет смысла говорить о значении выражения, скажем, (+ x 1), не указывая никакой информации об окружении, которое дало бы значение символу x (и даже символу +). Как мы увидим в главе 3, общее понятие окружения, предоставляющего контекст, в котором происходит вычисление, будет играть важную роль в нашем понимании того, как выполняются программы.

Заметим, что рассмотренное нами правило вычисления не обрабатывает определений.

Например, вычисление (define x 3) не означает применение define к двум аргументам, один из которых значение символа x, а другой равен 3, поскольку смысл define как раз и состоит в том, чтобы связать x со значением. (Таким образом, (define x 3) — не комбинация.) Такие исключения из вышеописанного правила вычисления называются особыми формами (special forms). Define — пока что единственный встретившийся нам пример особой формы, но очень скоро мы познакомимся и с другими. У каждой особой формы свое собственное правило вычисления. Разные виды выражений (вместе со своими правилами вычисления) составляют синтаксис языка программирования. По сравнению с большинством языков программирования, у Лиспа очень простой синтаксис; а именно, правило вычисления для выражений может быть описано как очень простое общее правило плюс специальные правила для небольшого числа особых форм11.

1.1.4. Составные процедуры Мы нашли в Лиспе некоторые из тех элементов, которые должны присутствовать в любом мощном языке программирования:

• Числа и арифметические операции представляют собой элементарные данные и процедуры.

• Вложение комбинаций дает возможность комбинировать операции.

• Определения, которые связывают имена со значениями, дают ограниченные возможности абстракции.

Теперь мы узнаем об определениях процедур (procedure denitions) — значительно более мощном методе абстракции, с помощью которого составной операции можно дать имя и затем ссылаться на нее как на единое целое.

Для начала рассмотрим, как выразить понятие «возведения в квадрат». Можно сказать так: «Чтобы возвести что-нибудь в квадрат, нужно умножить его само на себя».

Вот как это выражается в нашем языке:

(define (square x) (* x x)) Это можно понимать так:

Здесь мы имеем составную процедуру (compound procedure), которой мы дали имя square. Эта процедура представляет операцию умножения чего-либо само на себя. Та вещь, которую нужно подвергнуть умножению, получает здесь имя x, которое играет ту 11 Особые синтаксические формы, которые представляют собой просто удобное альтернативное поверхностное представление для того, что можно выразить более унифицированным способом, иногда называют синтаксическим сахаром (syntactic sugar), используя выражение Питера Ландина. По сравнению с пользователями других языков, программистов на Лиспе, как правило, мало волнует синтаксический сахар. (Для контраста возьмите руководство по Паскалю и посмотрите, сколько места там уделяется описанию синтаксиса). Такое презрение к синтаксису отчасти происходит от гибкости Лиспа, позволяющего легко изменять поверхностный синтаксис, а отчасти из наблюдения, что многие «удобные» синтаксические конструкции, которые делают язык менее последовательным, приносят в конце концов больше вреда, чем пользы, когда программы становятся большими и сложными. По словам Алана Перлиса, «Синтаксический сахар вызывает рак точки с запятой».

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

Общая форма определения процедуры такова:

(define ( имя формальные-параметры ) тело ) Имя — это тот символ, с которым нужно связать в окружении определение процедуры13. Формальные-параметры — это имена, которые в теле процедуры используются для отсылки к соответствующим аргументам процедуры. Тело — это выражение, которое вычислит результат применения процедуры, когда формальные параметры будут заменены аргументами, к которым процедура будет применяться14. Имя и формальныепараметры заключены в скобки, как это было бы при вызове определяемой процедуры.

Теперь, когда процедура square определена, мы можем ее использовать:

(square 21) (square (+ 2 5)) (square (square 3)) Кроме того, мы можем использовать square при определении других процедур. Например, x2 + y 2 можно записать как (+ (square x) (square y))) Легко можно определить процедуру sum-of-squares, которая, получая в качестве аргументов два числа, дает в результате сумму их квадратов:

(define (sum-of-squares x y) (+ (square x) (square y))) (sum-of-squares 3 4) Теперь и sum-of-squares мы можем использовать как строительный блок при дальнейшем определении процедур:

12 Заметьте, что здесь присутствуют две различные операции: мы создаем процедуру, и мы даем ей имя square. Возможно, и на самом деле даже важно, разделить эти два понятия: создавать процедуры, никак их не называя, и давать имена процедурам, уже созданным заранее. Мы увидим, как это делается, в разделе 1.3.2.

13 На всем протяжении этой книги мы будем описывать обобщенныйсинтаксис выражений, используя курсив в угловых скобках — напр. имя, чтобы обозначить «дырки» в выражении, которые нужно заполнить, когда это выражение используется в языке.

14 В более общем случае тело процедуры может быть последовательностью выражений. В этом случае интерпретатор вычисляет по очереди все выражения в этой последовательности и возвращает в качестве значения применения процедуры значение последнего выражения.

(define (f a) (sum-of-squares (+ a 1) (* a 2))) (f 5) Составные процедуры используются точно так же, как элементарные. В самом деле, глядя на приведенное выше определение sum-of-squares, невозможно выяснить, была ли square встроена в интерпретатор, подобно + и *, или ее определили как составную процедуру.

1.1.5. Подстановочная модель применения процедуры Вычисляя комбинацию, оператор которой называет составную процедуру, интерпретатор осуществляет, вообще говоря, тот же процесс, что и для комбинаций, операторы которых называют элементарные процедуры — процесс, описанный в разделе 1.1.3. А именно, интерпретатор вычисляет элементы комбинации и применяет процедуру (значение оператора комбинации) к аргументам (значениям операндов комбинации).

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

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

Чтобы проиллюстрировать этот процесс, вычислим комбинацию (f 5) где f — процедура, определенная в разделе 1.1.4. Начинаем мы с того, что восстанавливаем тело f:

(sum-of-squares (+ a 1) (* a 2)) Затем мы заменяем формальный параметр a на аргумент 5:

(sum-of-squares (+ 5 1) (* 5 2)) Таким образом, задача сводится к вычислению комбинации с двумя операндами и оператором sum-of-squares. Вычисление этой комбинации включает три подзадачи. Нам нужно вычислить оператор, чтобы получить процедуру, которую требуется применить, а также операнды, чтобы получить аргументы. При этом (+ 5 1) дает 6, а (* 5 2) дает 10, так что нам требуется применить процедуру sum-of-squares к 6 и 10. Эти значения подставляются на место формальных параметров x и y в теле sum-of-squares, приводя выражение к (+ (square 6) (square 10)) Когда мы используем определение square, это приводится к (+ (* 6 6) (* 10 10)) что при умножении сводится к (+ 36 100) и, наконец, к Только что описанный нами процесс называется подстановочной моделью (substitution model) применения процедуры. Ее можно использовать как модель, которая определяет «смысл» понятия применения процедуры, пока рассматриваются процедуры из этой главы. Имеются, однако, две детали, которые необходимо подчеркнуть:

• Цель подстановочной модели — помочь нам представить, как применяются процедуры, а не дать описание того, как на самом деле работает интерпретатор. Как правило, интерпретаторы вычисляют применения процедур к аргументам без манипуляций с текстом процедуры, которые выражаются в подстановке значений для формальных параметров. На практике «подстановка» реализуется с помощью локальных окружений для формальных параметров. Более подробно мы обсудим это в главах 3 и 4, где мы детально исследуем реализацию интерпретатора.

• На протяжении этой книги мы представим последовательность усложняющихся моделей того, как работает интерпретатор, завершающуюся полным воплощением интерпретатора и компилятора в главе 5. Подстановочная модель — только первая из них, способ начать формально мыслить о моделях вычисления. Вообще, моделируя различные явления в науке и технике, мы начинаем с упрощенных, неполных моделей. Подстановочная модель в этом смысле не исключение. В частности, когда в главе 3 мы обратимся к использованию процедур с «изменяемыми данными», то мы увидим, что подстановочная модель этого не выдерживает и ее нужно заменить более сложной моделью применения процедур15.

Аппликативный и нормальный порядки вычисления В соответствии с описанием из раздела 1.1.3, интерпретатор сначала вычисляет оператор и операнды, а затем применяет получившуюся процедуру к получившимся аргументам. Но это не единственный способ осуществлять вычисления. Другая модель вычисления не вычисляет аргументы, пока не понадобится их значение. Вместо этого она подставляет на место параметров выражения-операнды, пока не получит выражение, в котором присутствуют только элементарные операторы, и лишь затем вычисляет его. Если бы мы использовали этот метод, вычисление (f 5) прошло бы последовательность подстановок 15 Несмотря на простоту подстановочной модели, дать строгое математическое определение процессу подстановки оказывается удивительно сложно. Проблема возникает из-за возможности смешения имен, которые используются как формальные параметры процедуры, с именами (возможно, с ними совпадающими), которые используются в выражениях, к которым процедура может применяться. Имеется долгая история неверных определений подстановки (substitution) в литературе по логике и языкам программирования. Подробное обсуждение подстановки можно найти в Stoy 1977.

(sum-of-squares (+ 5 1) (* 5 2)) за которыми последуют редукции Это дает тот же результат, что и предыдущая модель вычислений, но процесс его получения отличается. В частности, вычисление (+ 5 1) и (* 5 2) выполняется здесь по два раза, в соответствии с редукцией выражения (* x x) где x заменяется, соответственно, на (+ 5 1) и (* 5 2).

Альтернативный метод «полная подстановка, затем редукция» известен под названием нормальный порядок вычислений (normal-order evaluation), в противоположность методу «вычисление аргументов, затем применение процедуры», которое называется аппликативным порядком вычислений (applicative-order evaluation). Можно показать, что для процедур, которые правильно моделируются с помощью подстановки (включая все процедуры из первых двух глав этой книги) и возвращают законные значения, нормальный и аппликативный порядки вычисления дают одно и то же значение. (См. упражнение 1.5, где приводится пример «незаконного» выражения, для которого нормальный и аппликативный порядки вычисления дают разные результаты.) В Лиспе используется аппликативный порядок вычислений, отчасти из-за дополнительной эффективности, которую дает возможность не вычислять многократно выражения вроде приведенных выше (+ 5 1) и (* 5 2), а отчасти, что важнее, потому что с нормальным порядком вычислений становится очень сложно обращаться, как только мы покидаем область процедур, которые можно смоделировать с помощью подстановки. С другой стороны, нормальный порядок вычислений может быть весьма ценным инструментом, и некоторые его применения мы рассмотрим в главах 3 и 416.

1.1.6. Условные выражения и предикаты Выразительная сила того класса процедур, которые мы уже научились определять, очень ограничена, поскольку пока что у нас нет способа производить проверки и выполнять различные операции в зависимости от результата проверки. Например, мы не способны определить процедуру, вычисляющую модуль числа, проверяя, положительное 16 В главе 3 мы описываем обработку потоков (stream processing), которая представляет собой способ обработки структур данных, кажущихся «бесконечными», с помощью ограниченной формы нормального порядка вычислений. В разделе 4.2 мы модифицируем интерпретатор Scheme так, что получается вариант языка с нормальным порядком вычислений.

ли это число, отрицательное или ноль, и предпринимая различные действия в соответствии с правилом Такая конструкция называется разбором случаев (case analysis). В Лиспе существует особая форма для обозначения такого разбора случаев.Она называется cond (от английского слова conditional, «условный») и используется так:

(define (abs x) (cond ((> x 0) x) Общая форма условного выражения такова:

Она состоит из символа cond, за которым следуют заключенные в скобки пары выражений ( p e ), называемых ветвями (clauses). В каждой из этих пар первое выражение — предикат (predicate), то есть выражение, значение которого интерпретируется как истина или ложь17.

Условные выражения вычисляются так: сначала вычисляется предикат p1. Если его значением является ложь, вычисляется p2. Если значение p2 также ложь, вычисляется p3. Этот процесс продолжается до тех пор, пока не найдется предикат, значением которого будет истина, и в этом случае интерпретатор возвращает значение соответствующего выражения-следствия (consequent expression) в качестве значения всего условного выражения. Если ни один из p ни окажется истинным, значение условного выражения не определено.

Словом предикат называют процедуры, которые возвращают истину или ложь, а также выражения, которые имеют значением истину или ложь. Процедура вычисления модуля использует элементарные предикаты 18.

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

Можно написать процедуру вычисления модуля и так:

17 «Интерпретируется как истина или ложь» означает следующее: в языке Scheme есть два выделенных значения, которые обозначаются константами #t и #f. Когда интерпретатор проверяет значение предиката, он интерпретирует #f как ложь. Любое другое значение считается истиной. (Таким образом, наличие #t логически не является необходимым, но иметь его удобно.) В этой книге мы будем использовать имена true и false, которые связаны со значениями #t и #f, соответственно.

18 Еще она использует операцию «минус» -, которая, когда используется с одним операндом, как в выражении (- x), обозначает смену знака.

(define (abs x) (cond ((< x 0) (- x)) что на русском языке можно было бы выразить следующим образом: «если x меньше нуля, вернуть x; иначе вернуть x». Else — специальный символ, который в заключительной ветви cond можно использовать на месте p. Это заставляет cond вернуть в качестве значения значение соответствующего e в случае, если все предыдущие ветви были пропущены. На самом деле, здесь на месте p можно было бы использовать любое выражение, которое всегда имеет значение истина.

Вот еще один способ написать процедуру вычисления модуля:

(define (abs x) (if (< x 0) Здесь употребляется особая форма if, ограниченный вид условного выражения. Его можно использовать при разборе случаев, когда есть ровно два возможных исхода. Общая форма выражения if такова:

(if предикат следствие альтернатива ) Чтобы вычислить выражение if, интерпретатор сначала вычисляет его предикат. Если предикат дает истинное значение, интерпретатор вычисляет следствие и возвращает его значение. В противном случае он вычисляет альтернативу и возвращает ее значение19.

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

Из них чаще всего используются такие:

Интерпретатор вычисляет выражения e по одному, слева направо. Если какое-нибудь из e дает ложное значение, значение всего выражения and — ложь, и остальные e не вычисляются. Если все e дают истинные значения, значением выражения and является значение последнего из них.

Интерпретатор вычисляет выражения e по одному, слева направо. Если какое-нибудь из e дает истинное значение, это значение возвращается как результат выражения or, а остальные e не вычисляются. Если все e оказываются ложными, значением выражения or является ложь.

Значение выражения not — истина, если значение выражения e ложно, и ложь в противном случае.

19 Небольшая разница между if и cond состоит в том, что в cond каждое e может быть последовательностью выражений. Если соответствующее p оказывается истинным, выражения из e вычисляются по очереди, и в качестве значения cond возвращается значение последнего из них. Напротив, в if как следствие, так и альтернатива обязаны состоять из одного выражения.

Заметим, что and и or — особые формы, а не процедуры, поскольку не обязательно вычисляются все подвыражения. Not — обычная процедура.

Как пример на использование этих конструкций, условие что число x находится в диапазоне 5 < x < 10, можно выразить как (and (> x 5) (< x 10)) Другой пример: мы можем определить предикат, который проверяет, что одно число больше или равно другому, как (define (>= x y) (or (> x y) (= x y))) или как (define (>= x y) (not (< x y))) Упражнение 1.1.

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

(+ 5 3 4) (- 9 1) (/ 6 2) (+ (* 2 4) (- 4 6)) (define a 3) (define b (+ a 1)) (+ a b (* a b)) (= a b) (if (and (> b a) (< b (* a b))) (cond ((= a 4) 6) (+ 2 (if (> b a) b a)) (* (cond ((> a b) a) Упражнение 1.2.

Переведите следующее выражение в префиксную форму:

Упражнение 1.3.

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

Упражнение 1.4.

Заметим, что наша модель вычислений разрешает существование комбинаций, операторы которых — составные выражения. С помощью этого наблюдения опишите, как работает следующая процедура:

(define (a-plus-abs-b a b) ((if (> b 0) + -) a b)) Упражнение 1.5.

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

(define (p) (p)) (define (test x y) (if (= x 0) Затем он вычисляет выражение (test 0 (p)) Какое поведение увидит Бен, если интерпретатор использует аппликативный порядок вычислений?

Какое поведение он увидит, если интерпретатор использует нормальный порядок? Объясните Ваш ответ. (Предполагается, что правило вычисления особой формы if одинаково независимо от того, какой порядок вычислений используется. Сначала вычисляется выражение-предикат, и результат определяет, нужно ли вычислять выражение-следствие или альтернативу.) 1.1.7. Пример: вычисление квадратного корня методом Ньютона Процедуры, как они описаны выше, очень похожи на обыкновенные математические функции. Они устанавливают значение, которое определяется одним или более параметром. Но есть важное различие между математическими функциями и компьютерными процедурами. Процедуры должны быть эффективными.

В качестве примера рассмотрим задачу вычисления квадратного корня. Мы можем определить функцию «квадратный корень» так:

Это описывает совершенно нормальную математическую функцию. С помощью такого определения мы можем решать, является ли одно число квадратным корнем другого, или выводить общие свойства квадратных корней. С другой стороны, это определение не описывает процедуры. В самом деле, оно почти ничего не говорит о том, как найти квадратный корень данного числа. Не поможет и попытка перевести это определение на псевдо-Лисп:

(define (sqrt x) (the y (and (>= y 0) Это только уход от вопроса.

Противопоставление функций и процедур отражает общее различие между описанием свойств объектов и описанием того, как что-то делать, или, как иногда говорят, различие между декларативным знанием и императивным знанием. В математике нас обычно интересуют декларативные описания (что такое), а в информатике императивные описания (как)20.

Как вычисляются квадратные корни? Наиболее часто применяется Ньютонов метод последовательных приближений, который основан на том, что имея некоторое неточное значение y для квадратного корня из числа x, мы можем с помощью простой манипуляции получить более точное значение (более близкое к настоящему квадратному корню), если возьмем среднее между y и x/y 21. Например, мы можем вычислить квадратный 20 Декларативные и императивные описания тесно связаны между собой, как и математика с информатикой.

Например, сказать, что ответ, получаемый программой, «верен», означает сделать об этой программе декларативное утверждение. Существует большое количество исследований, направленных на отыскание методов доказательства того, что программа корректна, и большая часть сложности этого предмета исследования связана с переходом от императивных утверждений (из которых строятся программы) к декларативным (которые можно использовать для рассуждений). Связана с этим и такая важная область современных исследований по проектированию языков программирования, как исследование так называемыхязыков сверхвысокого уровня, в которых программирование на самом деле происходит в терминах декларативных утверждений. Идея состоит в том, чтобы сделать интерпретаторы настолько умными, чтобы, получая от программиста знание типа «что такое», они были бы способны самостоятельно породить знание типа «как». В общем случае это сделать невозможно, но есть важные области, где удалось достичь прогресса. Мы вернемся к этой идее в главе 4.

21 На самом деле алгоритм нахождения квадратного корня представляет собой частный случай метода Ньютона, который является общим методом нахождения корней уравнений. Собственно алгоритм нахождения квадратного корня был разработан Героном Александрийским в первом веке н.э. Мы увидим, как выразить общий метод Ньютона в виде процедуры на Лиспе, в разделе 1.3.4.

корень из 2 следующим образом: предположим, что начальное приближение равно 1.

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

Теперь формализуем этот процесс в терминах процедур. Начнем с подкоренного числа и какого-то значения приближения. Если приближение достаточно хорошо подходит для наших целей, то процесс закончен; если нет, мы должны повторить его с улучшенным значением приближения. Запишем эту базовую стратегию в виде процедуры:

(define (sqrt-iter guess x) (if (good-enough? guess x) (sqrt-iter (improve guess x) Значение приближения улучшается с помощью взятия среднего между ним и частным подкоренного числа и старого значения приближения:

(define (improve guess x) (average guess (/ x guess))) где (define (average x y) (/ (+ x y) 2)) Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение. Следующий вариант сойдет для иллюстрации, но на самом деле это не очень хороший тест. (См.

упражнение 1.7.) Идея состоит в том, чтобы улучшать приближения до тех пор, пока его квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска (здесь 0.001)22 :

(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) 22 Обычно мы будем давать предикатам имена, заканчивающиеся знаком вопроса, чтобы было проще запомнить, что это предикаты. Это не более чем стилистическое соглашение. С точки зрения интерпретатора, вопросительный знак — обыкновенный символ.

Наконец, нужно с чего-то начинать. Например, мы можем для начала предполагать, что квадратный корень любого числа равен 123 :

(define (sqrt x) (sqrt-iter 1.0 x)) Если мы введем эти определения в интерпретатор, мы сможем использовать sqrt как любую другую процедуру:

(sqrt 9) 3. (sqrt (+ 100 37)) 11. (sqrt (+ (sqrt 2) (sqrt 3))) 1. (square (sqrt 1000)) 1000. Программа sqrt показывает также, что того простого процедурного языка, который мы описали до сих пор, достаточно, чтобы написать любую чисто вычислительную программу, которую можно было бы написать, скажем, на Си или Паскале. Это может показаться удивительным, поскольку в наш язык мы не включили никаких итеративных (циклических) конструкций, указывающих компьютеру, что нужно производить некое действие несколько раз. Sqrt-iter, с другой стороны, показывает, как можно выразить итерацию, не имея никакого специального конструкта, кроме обыкновенной способности вызвать процедуру24.

Упражнение 1.6.

Лиза П. Хакер не понимает, почему if должна быть особой формой. «Почему нельзя просто определить ее как обычную процедуру с помощью cond?» — спрашивает она. Лизина подруга Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версию if:

(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) Ева показывает Лизе новую программу:

23 Обратите внимание, что мы записываем начальное приближение как 1.0, а не как 1.Во многих реализациях Лиспа здесь не будет никакой разницы. Однако интерпретатор MIT Scheme отличает точные целые числа от десятичных значений, и при делении двух целых получается не десятичная дробь, а рациональное число.

Например, поделив 10/6, получим 5/3, а поделив 10.0/6.0, получим 1.6666666666666667. (Мы увидим, как реализовать арифметические операции над рациональными числами, в разделе 2.1.1.) Если в нашей программе квадратного корня мы начнем с начального приближения 1, а x будет точным целым числом, все последующие значения, получаемые при вычислении квадратного корня, будут не десятичными дробями, а рациональными числами. Поскольку при смешанных операциях над десятичными дробями и рациональными числами всегда получаются десятичные дроби, то начав со значения 1.0, все прочие мы получим в виде десятичных дробей.

24 Читателям, которых заботят вопросы эффективности, связанные с использованием вызовов процедур для итерации, следует обратить внимание на замечания о «хвостовой рекурсии» в разделе 1.2.1.

(new-if (= 2 3) 0 5) (new-if (= 1 1) 0 5) Обрадованная Лиза переписывает через new-if программу вычисления квадратного корня:

(define (sqrt-iter guess x) (new-if (good-enough? guess x) (sqrt-iter (improve guess x) Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратных корней? Объясните.

Упражнение 1.7.

Проверка good-enough?, которую мы использовали для вычисления квадратных корней, будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел. Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативный подход к реализации good-enough? состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение. Верно ли, что на больших и маленьких числах она работает лучше?

Упражнение 1.8.

Метод Ньютона для кубических корней основан на том, что если y является приближением к кубическому корню из x, то мы можем получить лучшее приближение по формуле С помощью этой формулы напишите процедуру вычисления кубического корня, подобную процедуре для квадратного корня. (В разделе 1.3.4 мы увидим, что можно реализовать общий метод Ньютона как абстракцию этих процедур для квадратного и кубического корня.) 1.1.8. Процедуры как абстракции типа «черный ящик»

Sqrt — наш первый пример процесса, определенного множеством зависимых друг от друга процедур. Заметим, что определение sqrt-iter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя. Идея, что можно определить процедуру саму через себя, возможно, кажется Вам подозрительной; неясно, как такое «циклическое» определение вообще может иметь смысл, не то что описывать хорошо определенный процесс для исполнения компьютером. Более осторожно мы подойдем к этому в разделе 1.2. Рассмотрим, однако, некоторые другие важные детали, которые иллюстрирует пример с sqrt.

Рис. 1.2. Процедурная декомпозиция программы sqrt.

Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи: как понять, что очередное приближение нас устраивает, как улучшить очередное приближение, и так далее. Каждая из этих задач решается с помощью отдельной процедуры. Вся программа sqrt может рассматриваться как пучок процедур (показанный на рис. 1.1.8), отражающий декомпозицию задачи на подзадачи.

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

первые десять строк, следующие десять строк и так далее. Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использована при определении других процедур. Например, когда мы определяем процедуру goodenough? с помощью square, мы можем рассматривать процедуру square как «черный ящик». В этот момент нас не интересует, как она вычисляет свой результат, — важно только то, что она способна вычислить квадрат. О деталях того, как вычисляют квадраты, можно сейчас забыть и рассмотреть их потом. Действительно, пока мы рассматриваем процедуру good-enough?, square — не совсем процедура, но скорее абстракция процедуры, так называемая процедурная абстракция (procedural abstraction). На этом уровне абстракции все процедуры, вычисляющие квадрат, одинаково хороши.

Таким образом, если рассматривать только возвращаемые значения, то следующие две процедуры для возведения числа в квадрат будут неотличимы друг от друга. Каждая из них принимает числовой аргумент и возвращает в качестве значения квадрат этого числа25.

(define (square x) (* x x)) (define (square x) (exp (double (log x)))) (define (double x) (+ x x)) Таким образом, определение процедуры должно быть способно скрывать детали. МоНеясно даже, которая из этих процедур более эффективна. Это зависит от того, какая имеется аппаратура. Существуют машины, на которых «очевидная» реализация будет медленней. Представьте себе машину, в которой очень эффективным способом хранятся большие таблицы логарифмов и обратных логарифмов.

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

Локальные имена Одна из деталей реализации, которая не должна заботить пользователя процедуры — это то, какие человек, писавший процедуру, выбрал имена для формальных параметров процедуры. Таким образом, следующие две процедуры должны быть неотличимы:

(define (square x) (* x x)) (define (square y) (* y y)) Этот принцип — что значение процедуры не должно зависеть от имен параметров, которые выбрал ее автор, — может сначала показаться очевидным, однако он имеет глубокие следствия. Простейшее из этих следствий состоит в том, что имена параметров должны быть локальными в теле процедуры. Например, в программе вычисления квадратного корня при определении good-enough? мы использовали square:

(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) Намерение автора good-enough? состоит в том, чтобы определить, достаточно ли близко квадрат первого аргумента лежит ко второму. Мы видим, что автор good-enough?

обращается к первому аргументу с помощью имени guess, а ко второму с помощью имени x. Аргументом square является guess. Поскольку автор square использовал имя x (как мы видели выше), чтобы обратиться к этому аргументу, мы видим, что x в good-enough? должно отличаться от x в square. Запуск процедуры square не должен отразится на значении x, которое использует good-enough?, поскольку это значение x понадобится good-enough?, когда square будет вычислена.

Если бы параметры не были локальны по отношению к телам своих процедур, то параметр x в square смешался бы с параметром x из good-enough?, и поведение good-enough? зависело бы от того, какую версию square мы использовали. Таким образом, процедура square не была бы черным ящиком, как мы того хотим.

У формального параметра особая роль в определении процедуры: не имеет значения, какое у этого параметра имя. Такое имя называется связанной переменной (bound variable), и мы будем говорить, что определение процедуры связывает (binds) свои формальные параметры. Значение процедуры не изменяется, если во всем ее определении параметры последовательным образом переименованы26. Если переменная не связана, мы говорим, что она свободна (free). Множество выражений, для которых связывание определяет имя, называется областью действия (scope) этого имени. В определении процедуры связанные переменные, объявленные как формальные параметры процедуры, имеют своей областью действия тело процедуры.

В приведенном выше определении good-enough?, guess и x — связанные переменные, а counter max-count) (fact-iter (* counter product) Как и раньше, мы можем с помощью подстановочной модели изобразить процесс вычисления 6!, как показано на рис. 1.4.

Сравним эти два процесса. С одной стороны, они кажутся почти одинаковыми. Оба они вычисляют одну и ту же математическую функцию с одной и той же областью определения, и каждый из них для вычисления n! требует количества шагов, пропорционального n. Действительно, два этих процесса даже производят одну и ту же последовательность умножений и получают одну и ту же последовательность частичных произведений. С другой стороны, когда мы рассмотрим «формы» этих двух процессов, мы увидим, что они ведут себя совершенно по-разному Возьмем первый процесс. Подстановочная модель показывает сначала серию расширений, а затем сжатие, как показывает стрелка на рис. 1.3. Расширение происходит по мере того, как процесс строит цепочку отложенных операций (deferred operations), в данном случае цепочку умножений. Сжатие происходит тогда, когда выполняются эти отложенные операции. Такой тип процесса, который характеризуется цепочкой отложенных операций, называется рекурсивным процессом (recursive process). Выполнение этого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии. При вычислении n! длина цепочки отложенных умножений, а следовательно, и объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. Такой процесс называется линейно рекурсивным процессом (linear recursive process).

Напротив, второй процесс не растет и не сжимается. На каждом шаге при любом значении n необходимо помнить лишь текущие значения переменных product, counter и max-count. Такой процесс мы называем итеративным (iterative process).

В общем случае, итеративный процесс — это такой процесс, состояние которого можно описать конечным числом переменных состояния (state variables) плюс заранее заданное правило, определяющее, как эти переменные состояния изменяются от шага к шагу, и плюс (возможно) тест на завершение, который определяет условия, при которых процесс должен закончить работу. При вычислении n! число шагов линейно растет с ростом n. Такой процесс называется линейно итеративным процессом (linear iterative process).

Можно посмотреть на различие этих двух процессов и с другой точки зрения. В итеративном случае в каждый момент переменные программы дают полное описание состояния процесса. Если мы остановим процесс между шагами, для продолжения вычислений нам будет достаточно дать интерпретатору значения трех переменных программы. С рекурсивным процессом это не так. В этом случае имеется дополнительная «спрятанная» информация, которую хранит интерпретатор и которая не содержится в переменных программы. Она указывает, «где находится» процесс в терминах цепочки отложенных операций. Чем длиннее цепочка, тем больше информации нужно хранить30.

Противопоставляя итерацию и рекурсию, нужно вести себя осторожно и не смешивать понятие рекурсивного процесса с понятием рекурсивной процедуры. Когда мы говорим, что процедура рекурсивна, мы имеем в виду факт синтаксиса: определение процедуры ссылается (прямо или косвенно) на саму эту процедуру. Когда же мы говорим о процессе, что он следует, скажем, линейно рекурсивной схеме, мы говорим о развитии процесса, а не о синтаксисе, с помощью которого написана процедура. Может показаться странным, например, высказывание «рекурсивная процедура fact-iter описывает итеративный процесс». Однако процесс действительно является итеративным: его состояние полностью описывается тремя переменными состояния, и чтобы выполнить этот процесс, интерпретатор должен хранить значение только трех переменных.

Различие между процессами и процедурами может запутывать отчасти потому, что большинство реализаций обычных языков (включая Аду, Паскаль и Си) построены так, что интерпретация любой рекурсивной процедуры поглощает объем памяти, линейно растущий пропорционально количеству вызовов процедуры, даже если описываемый ею процесс в принципе итеративен. Как следствие, эти языки способны описывать итеративные процессы только с помощью специальных«циклических конструкций» вроде do, repeat, until, for и while. Реализация Scheme, которую мы рассмотрим в главе 5, свободна от этого недостатка. Она будет выполнять итеративный процесс, используя фиксированный объем памяти, даже если он описывается рекурсивной процедурой. Такое свойство реализации языка называется поддержкой хвостовой рекурсии (tail recursion). Если реализация языка поддерживает хвостовую рекурсию, то итерацию можно выразить с помощью обыкновенного механизма вызова функций, так что специальные циклические конструкции имеют смысл только как синтаксический сахар31.

30 Когда в главе 5 мы будем обсуждать реализацию процедур с помощью регистровых машин, мы увидим, что итеративный процесс можно реализовать «в аппаратуре» как машину, у которой есть только конечный набор регистров и нет никакой дополнительной памяти. Напротив, для реализации рекурсивного процесса требуется машина со вспомогательной структурой данных, называемойстек (stack).