…Прием, аналогичный приему
Сервантеса, но еще более поразительный, применен в "Рамаяне", поэме
Вальмики, повествующей о подвигах Рамы и о его войне с демонами. В
заключительной книге сыновья Рамы, не знающие, кто их отец, ищут приюта в
лесу, где некий аскет учит их читать. Этот учитель, как ни странно, сам
Вальмики; книга, по которой они учатся, - "Рамаяна". Рама приказывает
совершить жертвоприношение, заклание лошадей; на празднество является
Вальмики со своими учениками. Под аккомпанемент лютни они поют "Рамаяну".
Рама слышит историю своих деяний, узнает своих сыновей и вознаграждает поэта...
Хорхе Луис Борхес, "Скрытая магия в Дон Кихоте"
RECURSIVE: adj. see RECURSIVE.
STAN KELLY-BOOTLE, Devil's DP Dictionary
Лисп – это не просто язык программирования. Лисп – это философия и культура, предмет споров и почти религиозного преклонения.
Целые поколения хакеров выросли на Лиспе. Некоторые из выражений этого языка даже вошли в их повседневную речь, а в MIT до сих пор преподают на Лиспе все основы компьютерный наук. Так называемая «Книга Волшебника» (Wizard Book[1]) – "Structure and Interpretation of Computer Programs" – являющаяся официальным учебником в MIT, содержит примеры исключительно на Лиспе.
Как один из самых старых языков программирования (первая версия появилась в 1958 году), оказавших огромное влияние на всю компьютерную культуру и активно использующийся до сих пор в области задач искусственного интеллекта, Лисп заслуживает нашего пристального внимания.
В 1983 году в трех номерах уже знакомого нам журнала Scientific American были напечатаны статьи о Лиспе знаменитого энциклопедиста нашего времени, физика, философа, лингвиста, исследователя искусственного интеллекта, популяризатора науки и потрясающего по широте интересов и объему знаний человека – Дугласа Хофштадтера[2].
Эти статьи познакомили с Лиспом огромное количество даже далеких от программирования читателей и, я полагаю, сильно способствовали росту популярности языка. В свойственной ему манере, Хофштадтер назвал интерпретатор Лиспа «джином», и представил сессию работы с Лиспом как диалог с этим джином. Автор сего поста с гордостью отмечает, что узнал о Лиспе именно из оригинальных статей Хофштадтера в Scientific American.
Джон Маккарти – создатель Лиспа - определил основные идеи, положенные в основу языка, так:
операции проводятся над символическими выражениями, а не над числами[3].
Эти символические выражения представляются в памяти компьютера в форме списков.
Списки могут вложены друг в друга так, что элементами одного списка могут быть другие списки, и так «до бесконечности».
Ядро языка должно содержать минимальный набор элементарных операций (функций), так, чтобы более сложные операции определялись как композиции из более простых операций.
Лисп использует рекурсивные[4] функции.
Представление Лисп-программ как данных (другими словами, программа на Лиспе – это просто список, над которым можно производить такие же операции как над любым другим списком).
Функция eval, которая служит как для формального определения языка, так и в качестве его интерпретатора.
«Сборщик мусора», то есть программа, встроенная в Лисп, которая автоматически очищает память компьютера от объектов, которые больше не используются.
Список - одно из основополагающих понятий в программировании. Все мы знаем, что такое список - это последовательность элементов некоего множества. Элементы эти могут быть более или менее однородны, но, как правило, они объединены какой-то общей идеей. Возьмём, например, несколько списков из литературы.
Сей-Сенагон в своих "Записках у изголовья" приводит такой замечательный список:
То, что навевает светлое настроение: - Монах, который подносит государю в первый день Зайца жезлы удзуэ, сулящие долголетие. - Главный исполнитель священных плясок микагура. - Танцор, который размахивает флажком во время священных плясок. - Предводитель отряда стражников, которые ведут коней в Праздник умилостивления божеств. - Лотосы в пруде, обрызганные проливным дождём. - Главный актёр в труппе бродячих кукольников.
У этого списка есть название - "То, что навевает светлое настроение". В Лиспе у списков тоже часто будут названия - это имена переменных, указывающих на список. Назвав список по имени, в дальнейшем мы сможем обращаться к нему с помомощью этого имени. Элементы списка, которые сами списками не являются, называются в Лиспе атомами. Таким образом, в списке Сей-Сенагон, атомами являются "монах", "исполнитель священных плясок", "танцор", "предводитель отряда стражников", "лотосы в пруде" и "главный актёр"[5]. С другой стороны, "лотосы в пруде" как раз могут и сами по себе быть списком, состоящим из нескольких лотосов - это ни в коей мере не противоречит синтаксису Лиспа - он позволяет сколь угодно глубоко вкладывать списки друг в друга. Это значит, что элементом одного списка может быть другой список, который, в свою очередь состоит из элементов-списков, и так далее. В конце концов, на самом нижнем уровне, в самом глубоко запрятанном списке, мы всё равно обнаружим атомы.
Следующим важным понятием списка является его голова (head). Голова - это просто-напросто самый первый элемент списка (вспомните, что элементы списка всегда упорядочены). В нашем случае, головой списка будет "монах, который подносит государю в первый день Зайца жезлы удзуэ, сулящие долголетие". По аналогии с головой, в списке определяется хвост (tail). Обратите внимание: хвост - это не последний элемент списка, а все элементы списка, кроме головы![6] Наш хвост будет начинаться "главным исполнителем священных плясок микагура" и заканчиваться "главным актёром в труппе бродячих кукольников". В этом состоит очень важное отличие головы от хвоста: если голова - это элемент списка (которая сама по себе может быть списком, а может быть и атомом), то хвост - это всегда список; даже, если в нём не осталось ни одного элемента, хвост будет называться пустым списком.
Такое определение рекурсивно - оно позволяет работать со списками с помощью рекурсивных функций. Вот что означает рекурсивное определение: список - это голова и хвост, то есть, первый элемент списка (голова), и список, следующий за ним (хвост), который в свою очередь состоит из головы и хвоста. Другими словами, мы определили понятие список с помощью самого себя - это и есть рекурсивное определение.
В этом курсе мы ещё много раз встретимся с рекурсией, потому что она обладает необыкновенной притягательной силой. Красота рекурсии - в её простоте. Рекурсия следует принципу Оккама: "не стоит умножать сущности без необходимости". Ведь чтобы определить некую структуру данных рекурсивно (такую, как, например, список), мы используем саму эту структуру, не призывая на помощь другие вспомогательные структуры и подструктуры - сущности "не умножаются". Так же обстоит дело и с рекурсивными функциями, то есть функциями, которые многократно используют свой собственный код.
Но об этом речь впереди.
[1] Книга называется так потому, что на ее обложке изображен волшебник (ну или кто-то вроде него).
[2] Дуглас Хофщтадтер написал одну из самых известных в компьютерном (да и вообще) мире книг – «Гедель, Эшер, Бах», связывающую воедино множество самых разных областей науки, философии и искусства. За эту книгу он получил Пулитцеровскую премию.
[3] Ады Лавлейс, дочь Байрона, которая считается "первой программисткой" в мире, предвосхитила это утверждение в своих заметках об Аналитической Машине Бэббеджа: "Аналитическая Машина может работать не только с числами, но и с такими объектами, фундаментальные взаимоотношения между которыми могут быть выражены с помощью абстрактных операций". Это предвидение, на самом деле, поражает воображение, учитывая что оно было высказано в 19-м веке.
[4] Мы вскоре увидим, что такое «рекурсивная» функция.
[5] Конечно, этот пример не стоит воспринимать слишком буквально. У атома в Лиспе есть строго определённый синтаксис, и несколько слов, разделённых пробелами (как, например, "лотосы в пруде"), атомом быть не может. Но мы простим Сей-Сенагон такое невежество в вопросах программирования на Лиспе.
[6] Это различие между хвостом и головой списка сохраняется во всех без исключения языках программирования, работающих со списками.