глава 1

построение абстракций с помощью

процедур

Действия, в которых ум проявляет свои способности в отношении своих простых идей, суть главным образом следующие три: 1) соединение нескольких простых идей в одну сложную; так образовались все сложные идеи. 2) Сведение вместе двух идей, все равно, простых или сложных, и сопоставление их друг с другом так, чтобы обозревать их сразу, но не соединять в одну; так ум приобретает все свои идеи отношений. 3) Обособление идей от всех других идей, сопутствующих им в реальной действительности; это действие называется «абстрагированием», и при его помощи образованы все общие идеи в уме.

Джон Локк.

«Опыт о человеческом разуме» (1690) (Перевод А.Н. Савина)

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

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

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

последствиям.

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

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

Программирование на Лиспе

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

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

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

1 Руководство программиста по Лиспу 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).