|
Программирование на Лого: главы из совсем новой книгиОт редакции. В процессе подготовки предыдущего номера “Лого-карнавал: опыт и плодотворные идеи” мы узнали, что Сергей Федорович Сопрунов написал совсем новую книгу о языке Лого и программировании на нем (слово “совсем” в данном случае означает, что ряд фрагментов книги еще испещрен многочисленными рабочими пометками, как и что можно сделать/написать лучше/точнее/нагляднее и т.д.). Мы попросили Сергея Федоровича предоставить “Информатике” право первой публикации. Зачем программировать на Лого?Зачем программировать? Компьютеры являются чрезвычайно полезным инструментом. С помощью компьютера вы можете писать тексты, практически мгновенно обмениваться письмами с людьми в разных концах земли, слушать музыку, узнавать последние новости и читать свежие анекдоты, планировать путешествия, смотреть фильмы, создавать свои собственные фильмы и прочее. Один из видов деятельности, для которого естественно использовать компьютер, — это программирование. То, что на компьютере можно программировать, почти так же хорошо известно, как и то, что на компьютере можно играть в игры, — хотя количество людей, умеющих программировать, гораздо меньше количества игроков. В данной публикации мы собираемся обсуждать именно программирование на компьютере. Есть разные причины, по которым люди изучают программирование. Если оставить в стороне тех, кто знакомится с программированием в той или иной степени по принуждению, то можно назвать по меньшей мере две причины. Первая: программирование все еще выглядит привлекательным с профессиональной точки зрения — профессия программиста в наше время достаточно престижна. Существует целый ряд учебных курсов подготовки профессиональных программистов, однако данная публикация никак не претендует на подобную роль. Наше обсуждение программирования на Лого ни в какой степени не является таким учебным курсом. Другим стимулом для изучения программирования является стремление к “компьютерной грамотности”. Работая за компьютером, пользователь общается с разными программами, а их создавали программисты, поэтому для уверенной работы с программами и для полноценного знакомства с компьютером пользователю полезно ознакомиться с основами программирования. Эта точка зрения, не столь безосновательная в эпоху ранней компьютеризации, становится со временем все менее убедительной. Разработчики хороших программ стремятся к тому, чтобы пользователь мог работать с программой, не задумываясь об ее устройстве. Проектируя программу, разработчики рассчитывают, что пользователю не придется обращать внимание на технические аспекты программы и что он сможет сосредоточиться в основном на содержательной стороне своей работы. Знание основ программирования при работе с прикладными программами необходимо не более, чем знание основ машиностроения для вождения автомобиля. Таким образом, и эту причину мы не станем принимать в расчет. Данный текст адресован читателям, которым интересно программирование само по себе, которые считают программирование полезным и интересным интеллектуальным занятием. Программирование дает возможность познакомиться с такими фундаментальными понятиями, как алгоритмы, формальные языки, структуры данных, модульность, не только теоретически, но и практически, экспериментально — компьютер является прекрасным инструментом, реализующим эти концепции. С другой стороны, важность указанных выше понятий отнюдь не ограничивается программированием компьютеров, — это общие принципы, полезные при решении проблем в различных областях интеллектуальной деятельности. Зачем программировать на Лого? Честно говоря, нет большой принципиальной разницы в том, какой именно язык программирования высокого уровня вы выбрали для знакомства с программированием. Мы в качестве такого языка выбрали Лого. Постараемся указать причины, по которым мы считаем, что Лого является подходящей средой для такого знакомства. Мы полагаем, что большинство из вас в той или иной степени сталкивались с этим языком, первые версии которого были разработаны около 40 лет назад. Одна из характерных особенностей Лого — это язык, созданный специально для обучения. Разработчики Лого стремились, в частности, к максимальной простоте и доступности языка. И в самом деле, несложную программу на Лого может написать ученик 4–5-го класса. Такая простота языка способствовала, с одной стороны, широкому распространению Лого в начальном и среднем образовании, а с другой — создала Лого репутацию “игрушечного” языка, “языка программирования для детей”. Такая репутация, конечно, не соответствует действительности — программирование на Лого не исчерпывается простыми программами, создающими несложные мультфильмы на экране. Мы выбрали для программирования Лого, поскольку это полноценный и мощный язык. Что тут имеется в виду? Чем определяется выразительная сила языка программирования? Уж конечно, не тем, какие именно задачи можно решить с его помощью (иными словами, какие алгоритмы можно записать на данном языке), — в этом смысле все языки программирования приблизительно равноценны. Сравнивая между собой разные языки программирования, мы интересуемся тем, решение каких задач записывается на данном языке естественно, насколько особенности языка затрудняют или, наоборот, облегчают понимание текстов программ, и так далее. Наш разговорный язык тесно связан не только со стилем нашей речи, но и с кругом проблем, о которых мы размышляем, и со стилем нашего мышления. То же, хотя, конечно, и в меньшей степени, относится и к языкам программирования. Использование конкретного языка стимулирует специфический стиль рассмотрения и решения программистских проблем. Мы надеемся, что, прочтя этот текст, читатель получит представление о том, в чем состоит “стиль Лого”. Хотелось бы обратить ваше внимание на следующее обстоятельство. Мы сказали, что разработчики Лого в первую очередь стремились к простоте и естественности языка. Они заботились о том, чтобы при написании и чтении программ не приходилось беспокоиться о большом числе технических деталей и синтаксических правил. Для достижения подобных целей приходится неизбежно чем-то жертвовать. В случае большинства версий Лого ценой является эффективность программ. Вам не стоит рассчитывать на Лого, если вы намерены создать полноценную коммерческую программу, — программа, реализованная, скажем, на C или Java, будет скорее всего работать быстрее, использовать меньший объем памяти и пр. Подчеркнем: Лого является языком для изучения программирования, а не для профессиональной разработки программ. Зачем читать книги о программировании на Лого? Если Лого является столь простым языком, что его могут использовать ученики начальной школы, то зачем писать — а тем более читать — книжки, посвященные программированию на этом языке? Действительно, как мы уже говорили раньше, небольшую и вполне содержательную программу на Лого можно написать достаточно просто и быстро, не тратя времени на формальное знакомство с языком. Грубо говоря, пользователь, впервые увидевший Лого, может написать подобную программу в течение получаса. Более того, хотя это нигде явно не используется, мы надеемся, что у вас есть первоначальный опыт работы с Лого: вы знакомы с черепашьей графикой, создавали мультфильмы или простые игры и т.д. Мы рассчитываем на читателей, которым хотелось бы узнать, что представляет собой Лого как среда программирования — что лежит за границей широко известной “игрушечной” области Лого, можно ли Лого использовать за пределами начальной школы. Кроме того, некоторые люди, и я в том числе, испытывают потребность в том, чтобы постараться систематически разобраться в том языке, который они используют. Для того чтобы говорить прозой, нет необходимости знать, что такое проза; для того чтобы в Лого использовать простые списки, нет необходимости знать (как и рассчитывали разработчики), что такое списки. Однако если вас интересует, как устроен язык Лого, то мы надеемся, что эта публикация будет вам полезна. Рекурсия“Я оглянулся посмотреть, не оглянулась ли она, чтоб посмотреть, не оглянулся ли я”. Максим Леонидов Формально в этом разделе не будет ничего нового — мы не будем вводить какие-либо незнакомые примитивы или синтаксические конструкции. Несмотря на это, данный раздел будет скорее всего одним из самых сложных. В самом понятии рекурсии нет ничего сложного и необычного. Обсуждая область видимости переменных, мы говорили о цепочке процедур (точнее — агентов, выполняющих процедуры). Эта цепочка возникает, когда первая процедура вызывает (как подпроцедуру) вторую, вторая — третью и так далее. Может случиться так, что цепочка замкнется — например, третья процедура в процессе своей работы вызовет первую. В этом случае мы имеем дело с рекурсией, а такой вызов называем рекурсивным. Замкнутая цепочка вызовов может быть очень короткой — состоять из одной процедуры, которая вызывает саму себя. Такой замкнутый круг вызовов выглядит как порочный круг. Часто он и является порочным: процедуры последовательно вызывают друг друга, двигаясь по бесконечному кругу. Программа все время повторяет одни и те же действия — “зацикливается”, а зацикливание — один из основных сюжетов ночных кошмаров программистов. Если рекурсия столь опасна, то, возможно, здесь и стоит завершить ее обсуждение, добавив лишь грозное предупреждение: “Пишите свои программы так, чтобы в них ни одна процедура, ни прямо, ни косвенно ни в коем случае не вызывала сама себя!!!” Ситуация, к счастью, не столь проста. Как сложить стопку Мы собираемся написать процедуру, которая печатает примерно следующую, не очень правдоподобную и очень однообразную, историю: Мы положили кошку, а сверху Мы положили мышку, а сверху Мы положили книжку, а сверху Мы положили компьютер, а сверху Мы ничего не положили. А потом мы убрали компьютер. А потом мы убрали книжку. А потом мы убрали мышку. А потом мы убрали кошку. Наша процедура не настолько разумна, чтобы самой подобрать список предметов, которые следует уложить в стопку, — этот список мы будем передавать программе в качестве параметра. Иными словами, у данной процедуры будет один аргумент типа список , элементами этого списка должны быть слова. Так, в приведенном выше примере мы использовали в качестве значения аргумента список [кошку мышку книжку компьютер]. Мы могли бы уточнить, что эти слова должны быть существительными русского языка в родительном падеже, но программисты относятся с гордым презрением к подобным лингвистическим тонкостям. Поскольку наша процедура описывает историю жизни (рождения и исчезновения) стопки предметов, то мы ее назовем стопка. Итак, мы готовы написать заголовок нашей процедуры это стопка :нужно_положить Увы, пока у нас нет ясного представления о том, что писать дальше. Попытки написать процедуру стопка, используя уже рассмотренные подходы, приводят к весьма длинным и сложным текстам. Попробуем начать с того, что рассмотрим какой-то простой частный случай. Представляется, что самым простым случаем является список из одного элемента — нужно положить предмет в стопку и потом его убрать. Вот как может выглядеть такая процедура (названная, по естественным соображениям, стопка1 ): это стопка1 :нужно_положить покажи (слово "|Мы положили | прв :нужно_положить "|, а сверху|) покажи "|Мы ничего не положили.| покажи (слово "|А потом мы убрали | прв :нужно_положить ".) конец Напомню, что здесь мы вынуждены ограничивать строки символов значком “|”, поскольку строки содержат пробелы. Похоже, что нам придется неоднократно класть и убирать разные предметы, поэтому мы предпочтем сделать тексты более ясными и короткими, введя две простые процедуры положи и убери : это положи :предмет покажи (слово "|Мы положили | :предмет "|, а сверху|) конец это убери :предмет покажи (слово "|А потом мы убрали | :предмет ".) конец У каждой из этих процедур один аргумент типа слово. Теперь процедуру стопка1 можно переписать так: это стопка1 :нужно_положить положи прв :нужно_положить покажи "|Мы ничего не положили.| убери прв :нужно_положить конец — надеюсь, что в такой редакции текст процедуры стал чуть понятнее. В тексте мы использовали датчик прв , но могли использовать и псл — для одноэлементного списка это все равно, а для неодноэлементных списков программа все равно работает неправильно — как и следовало ожидать. Процедура стопка1 правильно рассказывает историю стопки из одного предмета. Попробуем теперь написать процедуру, умеющую работать со списком из двух предметов (не волнуйтесь, я надеюсь, что наше обсуждение закончится раньше, чем мы напишем процедуру стопка100). Текст процедуры стопка2 можно было бы составить из слегка отредактированного текста процедуры стопка1 , к которому добавлены две строки: это стопка2 :нужно_положить положи прв :нужно_положить положи прв кпрв :нужно_положить покажи "|Мы ничего не положили.| убери прв кпрв :нужно_положить убери прв :нужно_положить конец — но я предпочту следующий вариант: это стопка2 :нужно_положить положи прв :нужно_положить стопка1 кпрв :нужно_положить убери прв :нужно_положить конец Дотошно разберем, почему эта версия процедуры стопка2 правильно рассказывает историю стопки из двух предметов. Сначала она кладет первый предмет из указанного списка. Потом вызывает процедуру стопка1, правильно работающую со списком из одного предмета, передав ей в качестве аргумента одноэлементный список — исходный список без первого элемента. Дождавшись, когда стопка1 закончит свою историю, процедура стопка2 удаляет предмет, который она положила в самом начале. Полагаю, что вы уже догадались, что процедуру стопка3, правильно работающую со списком из трех слов, мы можем записать в виде это стопка3 :нужно_положить положи прв :нужно_положить стопка2 кпрв :нужно_положить убери прв :нужно_положить конец Используя технологию копирования/вставки, мы без труда напишем процедуры стопка4 и стопка5 : это стопка4 :нужно_положить положи прв :нужно_положить стопка3 кпрв :нужно_положить убери прв :нужно_положить конец это стопка5 :нужно_положить положи прв :нужно_положить стопка4 кпрв :нужно_положить убери прв :нужно_положить конец — но после этого, пожалуй, пора остановиться. Написанные нами процедуры следуют одной и той же несложной схеме: сначала мы кладем первый элемент из заданного списка. Потом мы вызываем процедуру, умеющую складывать и разбирать меньшую стопку, и передаем ей в качестве списка предметов, которые нужно положить, исходный список без первого элемента. После того как вызванная процедура закончит работу, мы убираем предмет, положенный в самом начале. Простое, но важное замечание. Рассмотрим, например, процедуру стопка5 . Положив первый предмет, она вызывает процедуру стопка4. На самом деле для нас неважно, что вызывается именно процедура стопка4 . Все, что нам необходимо для правильной работы процедуры стопка5 , — это то, что вызываемая процедура правильно рассказывает историю стопки из четырех элементов. Нам, например, совершенно неважно, как работает вызванная процедура со списками длины, не равной 4. Итак, поскольку наши процедуры настолько однотипны, возникает желание написать рекурсивную процедуру, следующую описанной схеме: это стопка :нужно_положить положи прв :нужно_положить стопка кпрв :нужно_положить убери прв :нужно_положить конец Такая процедура работать, увы, не будет. Если вам угодно, то вы можете проверить: процедура, к счастью, не зациклится, но ошибочно завершится, после того как выложит все предметы в стопку. Причина неудачи достаточно очевидна, но давайте укажем ее явно. Действительно, давайте посмотрим, как процедура стопка работает, например, со списком из пяти предметов, и сравним ее работу с работой процедуры стопка5 . Первая инструкция в обеих этих процедурах идентична — мы кладем первый предмет из списка. Далее вызываются подпроцедуры, которым передается исходный список без первого элемента: процедура стопка5 вызывает процедуру стопка4, процедура стопка вызывает саму себя — процедуру стопка . Процедура стопка5 успешно завершит работу, поскольку мы уверены, что стопка4 правильно работает со списками из четырех элементов. Процедура стопка тоже успешно завершила бы работу с пятиэлементным списком, если бы она правильно работала со списками из четырех элементов. Однако никакой уверенности (и даже большой надежды) в том, что стопка корректно работает с четырехэлементными списками, у нас нет. Чтобы оправдать или опровергнуть эту надежду, мы пробуем понять, как наша процедура работает со списками из четырех элементов. Те же рассуждения показывают, что для этого нам надо знать, как процедура работает со списками из трех элементов. Для этого надо быть уверенным в том, что для списка из двух элементов процедура работает правильно. Это утверждение зависит от того, как процедура работает с одноэлементными списками. С одноэлементными списками процедура стопка работает из рук вон плохо. Действительно, если список состоит из одного предмета, то, вместо того чтобы просто напечатать 3 нужные строки, процедура стопка организует совершенно ненужный рекурсивный вызов с пустым списком. Однако это дело поправимое. Достаточно в процедуре стопка явно указать, как обрабатывать одноэлементные списки: это стопка :нужно_положить если 1 = сколько :нужно_положить ;в списке ровно один элемент [стопка1 :нужно_положить стоп] положи прв :нужно_положить стопка кпрв :нужно_положить убери прв :нужно_положить конец Теперь мы уверены, что процедура стопка правильно работает со списками из одного элемента. Вспомнив предыдущие рассуждения, мы можем быть уверены, что процедура правильно работает и со списками из двух элементов, а следовательно, и со списками из трех элементов, а следовательно, и со списками из четырех элементов, …, а следовательно, и с любыми списками любой ненулевой длины. Процедура стопка готова. Вы, конечно, можете проверить, правильно ли она работает со списками разной длины, хотя, по-моему, это совершенно излишне — мы совершенно безукоризненно продемонстрировали, что она обязана правильно работать. Можно сделать небольшие косметические изменения. Возможно, вы решите, что наличие отдельной процедуры стопка1 излишне: она не имеет самостоятельного значения, а ее использование в тексте процедуры стопка , скорее, затрудняет, чем облегчает чтение. Нетрудно избавиться от лишней процедуры, перенеся ее текст непосредственно в процедуру стопка : это стопка :нужно_положить если 1 = сколько :нужно_положить ;в списке ровно один элемент [положи прв :нужно_положить покажи "|Мы ничего не положили.| убери прв :нужно_положить стоп] положи прв :нужно_положить стопка кпрв :нужно_положить убери прв :нужно_положить конец Нетрудно заметить, что нет необходимости дублировать строку положи прв:нужно_положить, — эту инструкцию следует выполнить как в случае одноэлементного списка, так и во всех прочих. Поэтому можно чуть-чуть сократить текст процедуры: это стопка :нужно_положить положи прв :нужно_положить если 1 = сколько :нужно_положить ;в списке ровно один элемент [покажи "|Мы ничего не положили.| убери прв :нужно_положить стоп] стопка кпрв :нужно_положить убери прв :нужно_положить конец Более существенное изменение состоит в следующем. В качестве простейшего, выделенного случая мы рассматривали список из одного предмета. Однако легко обнаружить, что этот случай не очень отличается от общей схемы: мы кладем первый (и единственный) предмет из списка, пишем строку “Ничего не положили”, а потом этот предмет убираем. Мы могли бы простейшим случаем считать пустой список предметов. Могут существовать разные мнения о том, как описывать историю стопки из 0 предметов (программист сказал бы заказчику, что “этот случай не описан в Техническом Задании!”). Давайте согласимся, что фраза “Ничего не положили” адекватно описывает историю именно пустой стопки. Тогда специальным случаем можно считать случай пустого списка, что позволяет упростить процедуру следующим образом: это стопка :нужно_положить если пусто? :нужно_положить ;список предметов пуст [покажи "|Мы ничего не положили.| стоп] положи прв :нужно_положить стопка кпрв :нужно_положить убери прв :нужно_положить конец В такой редакции текст процедуры стал несколько короче и понятнее, а кроме того, процедура теперь правильно работает и с пустым списком. Схематически текст нашей процедуры можно представить в следующем виде: в начале нашей процедуры мы проверяем, не относится ли значение аргумента к некоторому специальному случаю (в нашем примере специальным случаем является пустой список). Такая проверка в рекурсивных процедурах иногда называется правилом остановки. Специальные случаи мы обрабатываем особым образом и завершаем процедуру. Во всех остальных, не специальных, случаях мы выполняем некоторые действия, среди которых есть хотя бы один рекурсивный вызов исходной процедуры с аргументом “проще” исходного. В случае процедуры стопка “проще” означает, что список короче исходного. Многие рекурсивные программы следуют именно вышеуказанной схеме. Как это работает Мы надеемся, что предыдущие рассуждения убедили вас, что обсуждавшаяся рекурсивная программа работает правильно для любого непустого списка слов, то есть программа завершает работу, напечатав на экране нужный текст. Давайте теперь потратим некоторое время на то, чтобы разобраться с тем, каким именно образом Лого выполняет подобную программу, — иными словами, что происходит при интерпретации рекурсивной процедуры. Итак, попробуем с некоторой степенью подробности описать выполнение инструкции стопка [кошку мышку книжку компьютер] . Интерпретатор прежде всего выясняет, что требуется выполнить процедуру стопка, и что у этой процедуры один параметр. Параметр в данном случае задан явно, в виде константы, поэтому все готово для начала выполнения процедуры. В соответствии с нашей моделью интерпретатор вызывает Агента001, умеющего выполнять процедуру стопка , и помещает в его единственный контейнер с именем “нужно_положить” список [кошку мышку книжку компьютер] . Сценарий процедуры стопка начинается с выполнения процедуры если , то есть Агент001 должен вызвать соответствующего помощника (агенты, выполняющие процедуры-примитивы и процедуры положи и убери , не представляют для нас большого интереса, поэтому мы не будем давать им отдельные имена). Однако, прежде чем вызвать помощника, выполняющего эту процедура, следует найти значения двух аргументов процедуры если. Значение второго аргумента задано явно — это константа типа список, а значение первого аргумента определяется выражением пусто? :нужно_положить , что, как вы помните, является сокращением для выражения пусто? значение "нужно_положить. Прежде чем выполнять процедуру пусто? , следует, как и ранее, выяснить значение ее аргумента, это значение должен сообщить датчик значение . Итак, Агент001 просит помощника выполнить процедуру значение , передав ему слово “нужно_положить”. Помощник находит контейнер (локальную переменную) с указанным именем непосредственно у агента, вызвавшего данного помощника, и сообщает найденное значение — список [кошку мышку книжку компьютер] . Теперь можно вызвать помощника пусто?, передав ему соответствующее значение. Список не пуст, поэтому помощник сообщает слово “нет”. Вызывается специалист по процедуре если ; поскольку значение его первого аргумента — слово “нет”, то процедура если игнорирует значение второго аргумента и не делает ничего. Агент001 завершил выполнение первой инструкции своего сценария. Вторая инструкция имеет вид: положи прв :нужно_положить, — мы не будем разбирать ее столь же подробно, как и первую. Напомним лишь, что эта инструкция является сокращением выражения положи прв значение "нужно_положить . Рассуждения, полностью аналогичные приведенным выше, показывают, что мы выполним процедуру положи со словом “кошку” — первым элементом списка, лежащего в контейнере Агента001. Процедура положи печатает строку Мы положили кошку, а сверху Третья инструкция такова: стопка кпрв :нужно_положить . Агенту001 следует вызвать помощника, умеющего выполнять процедуру стопка , но, поскольку у этой процедуры имеется один аргумент, сначала нужно найти значение этого аргумента. Для вычисления значения выражения кпрв значение "нужно_положить следует вновь прибегнуть к услугам помощника значение и у найденного им значения — списка [кошку мышку книжку компьютер] следует удалить первый элемент. Итак, вызывается Агент002, умеющий выполнять процедуру стопка , у Агента002 имеется контейнер с именем “нужно_положить”, в этот контейнер помещается список [мышку книжку компьютер]. Обратите внимание, что хотя Агенты 001 и 002 выполняют одну и ту же процедуру (один и тот же сценарий), это два разных агента. Они находятся на разных стадиях выполнения работы. Раньше, обсуждая метафору агентов, мы указывали на то, что агент, выполняющий сценарий, и сам этот сценарий — вовсе не одно и то же. Мы предполагаем, что существует много агентов, умеющих выполнять одну и ту же процедуру. В данный момент активны два специалиста по процедуре стопка . Агент001 находится в процессе выполнения своей третьей инструкции — ждет завершения работы вызванного им помощника. Агент002 только приступил к выполнению своей первой инструкции. Кроме того, важно помнить о том, что у каждого агента есть свой собственный контейнер: в контейнере Агента001 лежит список [кошку мышку книжку компьютер], в контейнере Агента002 — список [мышку книжку компьютер]. Имена у этих контейнеров одинаковые — “нужно_положить”. Агент002 выполняет инструкцию если совершенно так же, как выполнил ее Агент001. Единственное отличие состоит в том, что теперь значение выражения значение "нужно_положить равно [мышку книжку компьютер] , а не [кошку мышку книжку компьютер] . Почему? Как вы помните, агент “значение” начинает поиск нужной переменной с переменных у вызвавшего его агента. Таким образом, хотя имеются две локальные переменные с именем “нужно_положить”, агент значение, обнаружив такой контейнер у Агента002, использует его содержимое и не интересуется всеми прочими. Это, однако, не приводит к существенной разнице при выполнении процедуры если — значение не пусто, поэтому если не делает ничего. Агент002 выполняет вторую инструкцию — в данном случае она эквивалентна положи "мышку , и приступает к выполнению третьей инструкции — стопка кпрв :нужно_положить. Выполнение этой инструкции приводит к тому, что Агент002 нанимает нового помощника — Агента003, тоже специалиста по процедуре стопка , положив ему в контейнер список [книжку компьютер] — значение выражения кпрв :нужно_положить . Очередь агентов увеличилась: Агент001 ждет Агента002, чтобы завершить выполнение третьей инструкции; Агент002 ждет Агента003, чтобы завершить выполнение своей третьей инструкции; Агент003 приступил к работе. У каждого из этих агентов имеется свой собственный контейнер с именем “нужно_положить”, но у всех этих контейнеров разное содержимое. На экране напечатаны две строки: первую строку напечатал Агент001, вторую — Агент002. Работа Агента003 приведет к появлению Агента004, в контейнер которого будет положен одноэлементный список [компьютер]. Через некоторое время Агент004 соответственно вызовет Агента005, поместив в его контейнер список []. В этот момент в очереди находятся агенты 001, 002, 003, 004, каждый из которых находится в процессе выполнения третьей инструкции своего сценария: ждет завершения работы вызванного им помощника. У каждого из этих агентов имеется контейнер с именем “нужно_положить” и содержимым [кошку мышку книжку компьютер], [мышку книжку компьютер] , [книжку компьютер] , [компьютер] соответственно. Каждый из агентов напечатал к данному моменту по одной строке. Деятельность Агента005 несколько отличается от деятельности предыдущих агентов. Начинает он, как и все, с вызова помощника “если”. Однако в этот раз значение выражения пусто? :нужно_положить равно “да”, поскольку выражение значение "нужно_положить сообщит содержимое контейнера текущего агента — пустой список. В этом случае процедура если не игнорирует значение своего второго аргумента, а приступает к его выполнению. Сначала процедура если вызывает процедуру покажи, передав ей в качестве аргумента слово "|Ничего не положили.| — печатается строка Мы ничего не положили. После выполнения этой инструкции процедура если вызывает процедуру стоп. Действие процедуры стоп состоит в следующем: она (успешно) завершает выполнение последней пользовательской процедуры в цепочке (очереди) вызовов. В данном случае процедура стоп вызвана процедурой если. Поскольку это не пользовательская, а примитивная процедура, то она нам не подходит. Да, честно говоря, в данном случае процедуру если было бы бессмысленно завершать — стоп является ее последней инструкцией. Поскольку процедура если была вызвана Агентом005, то он стоит предыдущим в очереди вызовов. Агент005 выполняет именно пользовательскую процедуру, поэтому стоп останавливает работу Агента005. Агент005 после выполнения первой инструкции завершает работу, сообщив об этом вызвавшему его агенту — в данном случае Агенту004. Теперь, после того как выполнение третьей инструкции успешно завершено, Агент004 может приступить к выполнению четвертой, и своей последней, инструкции: убери прв :нужно_положить . Как и раньше, для выполнения инструкции убери прв значение "нужно_положить следует найти значение выражения значение "нужно_положить. Поскольку контейнер текущего агента содержит одноэлементный список [компьютер] , то этот список и будет значением нужного выражения. Итак, четвертая инструкция Агента004 печатает строку Потом мы убрали компьютер. После этого Агент004 завершает работу и сообщает об этом вызвавшему его агенту. Агент003, получив сообщение, печатает свою строку и сообщает о конце работы Агенту002; Агент002 завершает работу и сообщает об этом Агенту001; Агент001, напечатав соответствующую строку, сообщает интерпретатору о том, что работа Агента001, а тем самым, и интерпретация инструкции стопка [кошку мышку книжку компьютер] завершена. Несколько примеров Прежде чем двигаться дальше, разберем еще несколько примеров рекурсивных программ. Вот программа, которая получает на вход какое-то слово, в данном случае — “победа”, и печатает следующую цепочку слов: победа обеда беда еда да а да еда беда обеда победа Работа этой процедуры аналогична работе уже обсуждавшейся процедуры стопка . Нужно лишь заметить, что в данном случае мы анализируем не список, а слово и что печатать следует не первый элемент аргумента, а аргумент без первого элемента (буквы). Еще одно, совершенно непринципиальное, отличие состоит в том, что правило остановки выглядит в данном случае несколько иначе. Вот один из вариантов такой процедуры: это флажок :слово покажи :слово если 1 = сколько :слово [стоп] флажок кпрв :слово покажи :слово конец Попробуем теперь модифицировать процедуру стопка так, чтобы печатать примерно следующую историю: Стопка высотой 0, мы положили кошку. Стопка высотой 1, мы положили мышку. Стопка высотой 2, мы положили книжку. Стопка высотой 3, мы положили компьютер. Стопка высотой 4, мы ничего не положили. Мы убрали компьютер, стопка высотой 3. Мы убрали книжку, стопка высотой 2. Мы убрали мышку, стопка высотой 1. Мы убрали кошку, стопка высотой 0. Назовем эту процедуру высокая_стопка . Этот случай несколько сложнее уже рассмотренных. Если мы попробуем буквально следовать схеме построения процедуры стопка, то натолкнемся на трудности. Действительно, попробуем рассмотреть простейший случай. Давайте пока, как и раньше, считать простейшим случаем список из одного предмета. Вы, при желании, можете считать простейшим случаем какой-то другой — скажем, пустой список предметов — это существенно не влияет на наши рассуждения. Мы можем, как и раньше, попытаться написать отдельную процедуру для простейшего случая — процедуру высокая_стопка1. Нетрудно заметить, что текст, который печатает процедура высокая_стопка1, зависит не только от предмета, который следует положить, но и от того, какой высоты стопка уже лежит на столе. Так, если к тому моменту, когда мы уже кладем последний предмет, высота стопки равна 3, то мы должны напечатать строки Стопка высотой 3, мы положили компьютер. Стопка высотой 4, мы ничего не положили. Мы убрали компьютер, стопка высотой 3. Если же высота стопки в этот момент равна, например, 7, то строка должна быть Стопка высотой 7, мы положили компьютер. Стопка высотой 8, мы ничего не положили. Мы убрали компьютер, стопка высотой 7. Иными словами, процедуры положи и убери должны знать не только, какой предмет кладется/убирается, но и какова высота стопки в данный момент. Решение состоит в том, что мы вводим у процедуры высокая_стопка еще один аргумент — число, указывающее, какова высота уже уложенной стопки. Таким образом, заголовок процедуры имеет вид: это высокая_стопка :нужно_положить :высота Процедуры положи и убери модифицируются следующим образом: это положи :предмет :высота покажи (слово "|Стопка высотой| :высота "|, мы положили | :предмет ".) конец это убери :предмет :высота покажи (слово "|Мы убрали | :предмет "|, стопка высотой| :высота ".) конец Основная часть процедуры высокая _стопка может быть записана следующим образом: это высокая_стопка :нужно_положить :высота … здесь должно быть правило остановки положи прв :нужно_положить :высота высокая_стопка кпрв :нужно_положить :высота + 1 убери прв :нужно_положить :высота конец Рекурсивный вызов несколько изменился: рекурсивно вызывая процедуру высокая_стопка, мы не только сообщаем ей новый, более короткий, список предметов, но сообщаем ей, что высота стопки изменилась — возросла на единицу. Процедура практически завершена — осталось лишь написать соответствующее правило остановки. Если в качестве наименьшего допустимого списка, как и в случае процедуры стопка , мы выберем пустой список, то окончательная редакция процедуры высокая_стопка выглядит так: это высокая_стопка :нужно_положить :высота если пусто? :нужно_положить [покажи (слово "|Стопка высотой| :высота "|, мы ничего не положили.|) стоп] положи прв :нужно_положить :высота высокая_стопка кпрв :нужно_положить :высота + 1 убери прв :нужно_положить :высота конец Инструкция, выполнявшая процедуру стопка, имела вид стопка список-предметов, например, стопка [кошку мышку книжку компьютер] . У процедуры высокая_стопка два аргумента, поэтому в инструкции следует указывать не только начальный список предметов, но и исходную (нулевую) высоту стопки: высокая_стопка [кошку мышку книжку компьютер] 0 .Если вам кажется утомительным каждый раз указывать значение служебного параметра, то вы можете сделать отдельную простую процедуру инициализации: это стопка_высокая :нужно_положить высокая_стопка :нужно_положить 0 конец Хотелось бы обратить ваше внимание на следующую важную особенность процедуры высокая_стопка. Она не только умеет правильно рассказывать историю стопки предметов, положенных на пустой стол и убранных оттуда. Процедуру высокая_стопка можно использовать и в том случае, когда на столе уже лежит какая-то стопка, поверх которой мы кладем/убираем предметы из заданного списка. Нам лишь необходимо знать высоту уже имеющейся стопки. Так, если уже имеется стопка из трех предметов, то, как легко понять, инструкция высокая_стопка [кошку мышку книжку компьютер] 3 напечатает текст Стопка высотой 3, мы положили кошку. Стопка высотой 4, мы положили мышку. Стопка высотой 5, мы положили книжку. Стопка высотой 6, мы положили компьютер. Стопка высотой 7, мы ничего не положили. Мы убрали компьютер, стопка высотой 6. Мы убрали книжку, стопка высотой 5. Мы убрали мышку, стопка высотой 4. Мы убрали кошку, стопка высотой 3. Иными словами, процедура высокая_стопка решает более общую задачу, чем исходная. В этом плане процедура высокая_стопка не является чем-то исключительным. Ситуация, в которой проще написать процедуру, решающую более сложную задачу, встречается при создании рекурсивных процедур достаточно часто. Разрабатывая рекурсивную процедуру, важно постараться найти обобщение исходной задачи, делающее более явным рекурсивную природу задачи. Рассмотрим еще один пример рекурсивной процедуры. Для заданной длины мы хотим напечатать все списки такой длины, элементами которых являются буквы “a” и “b”. Так, если длина равна 4, то процедура должна напечатать следующие 16 строк: a a a a a a a b a a b a a a b b a b a a a b a b a b b a a b b b b a a a b a a b b a b a b a b b b b a a b b a b b b b a b b b b Естественно считать, что при рекурсивном вызове мы будем уменьшать длину искомых списков, то есть мы постараемся объяснить, как можно напечатать все списки длины 4, если предположить, что наша программа умеет печатать списки длины 3. Нетрудно заметить, что указанные 16 строк разбиваются на две группы из 8 строк. В первой группе находятся всевозможные списки из трех элементов, к которым вначале приписана буква a. Во второй — те же трехэлементные списки, к которым вначале приписана буква b . Таким образом, нам было бы нетрудно напечатать все четырехэлементные списки, если бы наша программа умела не просто перечислять трехэлементные списки, а могла бы приписывать к ним нужное нам начало. Решение состоит в том, что, как и в предыдущем случае, мы решаем более общую задачу, чем исходная. Мы хотим написать процедуру все_списки , которая печатает все списки заданной длины, состоящие из букв “a” и “b” и имеющие заданное начало. Точнее, у нашей процедуры будут два аргумента: это все_списки :длина :начало “длина” — некоторое положительное целое число, “начало” — список длины не более “длина”, состоящий из букв “a” и “b”. То есть, например, инструкция все_списки 5 [b a b] должна напечатать следующие 4 строки: b a b a a b a b a b b a b b a b a b b b Исходная задача является очевидным частным случаем обобщенной — нужно лишь в качестве “начала” использовать пустой список. Вот общая схема процедуры все_списки (мы, как и раньше, откладываем формулировку правила остановки на потом): это все_списки :длина :начало … правило остановки ;печатаем все списки нужной длины ;с указанным началом, ;к которому в конце добавлена буква "a" все_списки :длина вксп :начало "a ;печатаем все списки нужной длины ;с указанным началом, ;к которому в конце добавлена буква "b" все_списки :длина вксп :начало "b конец Процедура все_списки вызывает себя дважды: с аргументами :длина вксп :начало "a и :длина вксп :начало "b . Как мы уже говорили, для того чтобы рекурсивная процедура работала корректно, требуется, чтобы аргументы в рекурсивных вызовах были “проще”, чем аргументы вызывающей процедуры. В случае процедуры стопка и высокая_стопка “проще” означало, что список предметов в рекурсивном вызове стал короче. Что же означает слово “проще” в случае процедуры все_списки — ведь значение первого аргумента (числа) не изменилось, а длина второго (списка) — возросла? В данном случае мы считаем, что аргументы “проще”, если сократилась длина еще не написанной части списка: уменьшилась разность между числом длина и количеством элементов в списке начало. Осталось разобраться с правилом остановки — какой случай мы считаем простейшим и что мы должны делать в этом случае. Естественно считать простейшим случаем тот, когда длина начала равна длине всего списка: в этом случае существует ровно один список указанной длины с таким началом — само начало. Таким образом, в этом крайнем случае печать всех списков заданной длины с заданным началом тривиальна — это просто покажи :начало . Вот окончательный текст процедуры: это все_списки :длина :начало ;длина начала равна требуемой длине если :длина = сколько :начало [покажи :начало стоп] ;печатаем все списки нужной длины ;с указанным началом, ;к которому в конце добавлена буква "a" все_списки :длина вксп :начало "a ;печатаем все списки нужной длины ;с указанным началом, ;к которому в конце добавлена буква "b" все_списки :длина вксп :начало "b конец Как мы уже заметили ранее, чтобы напечатать все списки нужной длины, составленные из букв “а” и “b”, следует вызвать процедуру все_списки с пустым началом, например, все_списки 5 [] . Нам может потребоваться перечислить все списки, составленные не из двух букв “a” и “b”, а из элементов произвольного набора символов. В этом случае процедуре нужно указывать не только длину и начало списка, но и заданный набор. Назовем модифицированную процедуру все_списки_из_набора . Тогда ее заголовок может иметь вид это все_списки_из_набора :длина :начало :набор Модификация текста процедуры достаточно очевидна: вместо явного перечисления всех продолжений списка “начало” следует использовать примитив перебор всех элементов списка “набор”. Подход, использованный при разработке процедуры все_списки, используется достаточно часто. Он состоит в том, что мы используем вспомогательную переменную — аккумулятор, в которой в процессе работы накапливается результат: на каждом шаге рекурсии мы добавляем в аккумулятор очередной элемент, в конце рекурсии мы используем значения, накопленные в аккумуляторе. Начальное значение аккумулятора, используемое в начале рекурсии, чаще всего пустое — пустой список или пустое слово. Как расставить 8 ферзей Мы хотим узнать, как можно расставить 8
ферзей на шахматной доске так, чтобы они не били
друг друга. Один способ решения этой задачи
достаточно очевиден. Ясно, что можно
рассматривать лишь такие расстановки ферзей, в
которых на каждой горизонтали шахматной доски
должен находиться ровно один ферзь, — назовем
такие расстановки допустимыми. Каждой
допустимой расстановке соответствует список из
восьми чисел от
Заметим, кстати, что в данной позиции ферзи не бьют друг друга — надеемся, что вас не смущает то, что ферзей, как и следовало ожидать, изображают черепашки. Таким образом, мы могли бы просмотреть все списки длиной 8, составленные из элементов списка [1 2 3 4 5 6 7 8], и отобрать из них подходящие — те, которые соответствуют позициям, в которых ферзи не бьют друг друга. Реализовать такой план вовсе не трудно — чуть ранее мы обсуждали, как сделать процедуру все_списки_из_набора, перечисляющую все списки указанной длины из заданного набора элементов. Таким образом, инструкция все_списки_из_набора 8 [] [1 2 3 4 5 6 7 8] напечатает всевозможные допустимые расстановки ферзей. Осталось лишь модифицировать процедуру все_списки_из_набора так, чтобы перед печатью расстановки (списка) она проверяла, действительно ли в этой позиции ферзи не бьют друг друга. Мы советуем вам самостоятельно осуществить намеченный план. Однако в этом разделе мы рассмотрим несколько иной подход. Одна из причин состоит в том, что просмотр всевозможных допустимых расстановок явно излишен. Действительно, например, нет никакого смысла рассматривать все списки, имеющие вид [1 1 …], — поскольку два первых ферзя стоят на одной и той же вертикали, то все эти позиции нам не подходят. Иными словами, часто по началу списка мы можем определить, что ферзи уже бьют друг друга, — ясно, что продолжать поиск среди списков с таким началом бессмысленно. Итак, приступим к разработке программы. Ферзей у нас будут изображать черепашки, мы будем расставлять ферзей на доске, нарисованной на листе проекта. Давайте начнем с того, что создадим 8 черепашек с именами “ферзь1”, “ферзь2”, …, “ферзь8” и нарисуем подходящую доску. Если вам, как и мне, лень создавать 8 черепашек вручную, то можете воспользоваться примитивом нов_черепашка — у этой команды один аргумент: слово, задающее имя новой черепашки. Таким образом, инструкции пусть "индекс 1 повтори 8 [нов_черепашка слово "ферзь :индекс пусть "индекс :индекс + 1] создадут нужный набор черепашек. Учтите, что черепашка, созданная таким образом, спрятана, поэтому вам, возможно, понадобится показать ее с помощью примитива пч (покажи черепашку) без параметра. Я уверен, что доску вы легко нарисуете без моей помощи. Итак, мы будем расставлять ферзей последовательно, начиная с первой горизонтали. Процесс расстановки будет следовать общей схеме, использованной нами при создании процедуры все_списки . А именно, мы будем предполагать, что задано некоторое “начало” — расстановка ферзей на первых нескольких горизонталях, и мы ищем всевозможные расстановки на оставшихся строках. Процедура расстановки будет рекурсивной, при каждом рекурсивном вызове мы будем увеличивать “начало”, то есть уменьшать количество строк, в которых ферзи еще не поставлены. Предположим, что мы сейчас заняты размещением ферзя в строке номер k, ферзи в строках 1, 2, …, k–1 уже стоят. При этом мы, конечно, предполагаем, что ферзи в строках 1, 2, …, k–1 стоят правильно — не бьют друг друга, иначе нет никакого смысла исследовать такую расстановку. Кроме того, как это принято при разработке рекурсивных программ, мы считаем, что наша процедура правильно находит все расстановки в более простом случае — когда ферзи уже расставлены не только на горизонталях от 1 до k–1, а на горизонталях от 1 до k. Исходя из этих предположений, нетрудно описать рекурсивный шаг: мы находим в k-й строке первое безопасное поле — такое, в котором ферзя в строке k не бьет ни один из уже установленных ферзей, и ставим ферзя на это поле. Далее рекурсивно вызываем процедуру, попросив перечислить все возможные расстановки в строках от k + 1 до 8. После того как перечисление закончено, мы перемещаем ферзя в следующее безопасное поле в строке k и повторяем этот процесс до тех пор, пока не дойдем до конца строки k. Как и раньше, простейший случай — правило остановки — мы обсудим позже. Для воплощения намеченного плана нам потребуется некоторая вспомогательная работа — в частности, нам потребуется несколько служебных процедур: мы должны уметь перемещать ферзя по горизонтали и уметь определять, является ли поле безопасным. Начнем с того, что определим полезные глобальные величины: для перемещения ферзей по шахматной доске нам нужно знать параметры этой доски. Для хранения этих параметров я использовал атрибуты проекта: координаты центра первого (левого нижнего) поля доски я записал в атрибуты левый_нижний_х и левый_нижний_у, размер клетки поля я поместил в атрибут размер_клетки . Кроме того, полезно, чтобы каждый ферзь помнил номер горизонтали, в которой он находится: для этой цели можно использовать свойство черепашки. Я создал свойство ряд и записал в него 1 для черепашки “ферзь1”, 2 — для черепашки “ферзь2” и т.д. Значения этого свойства, равно как и значения атрибутов, являются “константами” — они не будут изменяться в процессе работы проекта. Желательно, чтобы наша процедура умела расставлять ферзей не только на доске 8 ? 8, но и на доске произвольного (меньшего) размера — доска меньшего размера была бы полезна, в частности, при проверке и отладке процедуры. Для этой цели был добавлен атрибут размер_доски — в нем мы будем хранить число строк (столбцов) доски, на которой мы расставляем ферзей. Вот две служебные процедуры, которые нам пригодятся в дальнейшем: это исходная_позиция нов_х левый_нижний_х нов_у левый_нижний_у + размер_клетки * (ряд - 1) конец это передвинь нов_х х_коор + размер_клетки конец Смысл этих процедур очевиден: первая из них устанавливает ферзя в исходную позицию: в центр самой левой клетки соответствующей горизонтали. Вторая процедура передвигает ферзя вправо на одну клетку. Заметим в процедуре исходная_позиция, что вторая строка: нов_у левый_нижний_у + размер_клетки * (ряд - 1) — является следствием излишнего педантизма. Мы не будем перемещать ферзей по вертикали, поэтому можно установить правильную у-координату один раз — например, при создании черепашки. Несмотря на тривиальность данных процедур, возникает вопрос: а какой именно ферзь передвинется, если выполнить команду передвинь ? Ответ простой: передвинется главная черепашка (или главные черепашки, если есть несколько главных). Дело в том, что если на листе имеются черепашки, то как минимум одна из них является главной. Выяснить, какие именно черепашки являются главными, нетрудно — можно воспользоваться датчиком (примитивом) кто без аргументов. Этот датчик возвращает слово — имя главной черепашки, если имеется одна главная черепашка (слово будет пустым, если на листе вовсе нет черепашек) или список имен главных черепашек. Черепашка может становиться главной неявно: главной является новорожденная черепашка, а также та черепашка, на которую последней щелкнули мышкой. Однако черепашку можно сделать главной и явно, с помощью примитивов. У команды для один аргумент. Значением аргумента может быть слово — имя черепашки, которая должна стать главной. Значением аргумента может быть и список — в этом случае список должен содержать имена черепашек, которые станут главными. Так, инструкция для "ферзь3 сделает главной черепашку “ферзь3”, а после выполнения инструкции для [ферзь2 ферзь4] будет две главные черепашки. Кроме того, при создании и переименовании черепашки создается новая команда, имя которой совпадает с именем черепашки, к которому добавлена запятая. Эта команда без аргументов, она делает главной соответствующую черепашку. Иными словами, инструкции для "ферзь3 и ферзь3 полностью эквивалентны. Наличие нескольких главных черепашек несколько запутывает ситуацию, поэтому в наших проектах у нас будет ровно одна главная черепашка. Несколько иной способ заставить нужную черепашку выполнить команду — использовать примитив скажи. У этого примитива два аргумента. Первый аргумент полностью аналогичен единственному аргументу команды для — он определяет, к каким черепашкам мы обращаемся, и может быть как словом, так и списком. Второй аргумент, типа список , устроен несколько сложнее: он может быть как списком инструкций, так и выражением (вызовом датчика) Лого. Вы, возможно, заметили, что в отличие от обыкновения мы не указали тип самого примитива — является ли он командой или датчиком, если датчиком — то каков тип возвращаемого значения. Дело тут не в забывчивости, просто процедура скажи — может быть как командой, так и датчиком, в зависимости от значения своих аргументов. Если значением второго аргумента является список инструкций, то скажи ведет себя как команда, и действие ее состоит в том, что указанный список инструкций выполняется для всех черепашек, указанных в первом аргументе. Если же второй аргумент является вызовом датчика, то скажи — тоже датчик, значением этого датчика является значение указанного вызова для первой из заданных черепашек. Например, инструкция скажи [ферзь2 ферзь4] [исходная_позиция] установит черепашки “ферзь2” и “ферзь4” в исходное положение, значением выражения скажи [ферзь2 ферзь4] [ряд] будет число 2, поскольку именно таково значение свойства ряд черепашки “ферзь2”. Можно сказать, что примитив скажи делает указанные черепашки главными локально на некоторое время — на время выполнения действия, заданного вторым аргументом. После выполнения процедуры скажи главными будут те же черепашки, что и до выполнения примитива. Таким образом, хотя следующие три последовательности инструкций для "ферзь5 передвинь ферзь5, передвинь скажи "ферзь5 [передвинь] приводят на первый взгляд к одному и тому же результату — передвигают черепашку “ферзь5”, между ними есть существенная разница. Первые две строки действительно эквивалентны: они не только передвигают черепашку “ферзь5”, но и делают эту черепашку единственной главной. Третья строка передвигает черепашку, но больше ничего в проекте не меняется. Вернемся к нашей задаче о расстановке ферзей. Нам, конечно, потребуется выяснить, бьет ли один ферзь другого. Вот процедура, выясняющая, бьет ли конкретная черепашка (ее имя указывается в качестве аргумента) главную черепашку: ;Процедура бьет? - логический датчик с одним ;аргументом типа слово. ;Значением аргумента должно быть имя ;черепашки. ;Возвращает слово "да", если указанная ;черепашка ;бьет главную. это бьет? :кто выход или ;черепашки на одной вертикали х_коор = скажи :кто [х_коор] ;черепашки на одной диагонали (модуль (х_коор - скажи :кто [х_коор])) = (модуль (у_коор - скажи :кто [у_коор])) конец В данной процедуре использованы два новых примитива: или и модуль . Первый из них — логический датчик с произвольным числом аргументов, стандартное число аргументов — 2. Значением аргументов должны быть логические значения — слова “да” или “нет”. Датчик или сообщает слово “да”, если значение хотя бы одного из его аргументов — “да”. Датчик модуль, с одним аргументом — числом, сообщает абсолютное значение данного числа. Кроме того, нам нужно будет выяснить, стоит ли черепашка на безопасном поле: не бьет ли ее какой-то из ферзей на предыдущих строках. Для этого можно использовать следующую процедуру: ;Процедура безопасно? - логический датчик, ;сообщает "да", если текущий ;ферзь не бьется предыдущими ферзями ;(ферзями на предыдущих строках). это безопасно? много_раз [j ряд - 1] [если бьет? слово "ферзь 1 + :j [выход "нет]] выход "да конец В этой процедуре мы использовали новый примитив — команду много_раз . Эта команда во многом аналогична команде перебор , обсуждавшейся в разделе о шахматном турнире, — она тоже реализует некоторый простой цикл. У команды много_раз два аргумента, оба типа список. Первый элемент первого списка должен быть словом — это слово используется в качестве имени локальной переменной, остальные элементы первого списка задают выражение, значением которого должно быть положительное число — граница цикла. Второй список является последовательностью инструкций, в которые может входить указанная локальная переменная. Действие команды много_раз состоит в том, что указанная локальная переменная последовательно принимает значения 0, 1, 2 и т.д. и для каждого значения переменной меньше границы выполняются инструкции из второго списка. Как только значение переменной станет больше или равно границе, команда много_раз завершается. В процедуре безопасно имя локальной переменной — j , граница задается выражением ряд – 1. Если, например, главной является черепашка “ферзь6”, то граница цикла будет равна 5. Поэтому для каждого из значений 0, 1, 2, 3, 4 переменной j будет выполнена инструкция если бьет? слово "ферзь 1 + :j [выход "нет] то есть процедура безопасно? сообщит “нет”, если какой-либо из ферзей “ферзь1”, “ферзь2”, …, “ферзь5” бьет ферзя “ферзь6”. Если ни один из этих ферзей не бьет ферзя “ферзь6”, то команда много_раз завершится и выполнится следующая инструкция — программа безопасно? вернет слово “да”. Итак, мы готовы к тому, чтобы написать процедуру, перечисляющую всевозможные расстановки ферзей, в которых они не бьют друг друга. Как мы планировали, процедура будет расставлять ферзей на всех горизонталях, начиная с указанной, — номер этой строки мы будем передавать процедуре в качестве параметра — назовем его “номер_строки”. При этом мы предполагаем, что ферзи в строках 1, 2, …, :номер_строки – 1 уже расставлены и стоят в безопасных позициях. Вот как может выглядеть общая схема процедуры — как обычно, правило остановки мы обсудим позже: это все_позиции :номер_строки здесь должно быть правило остановки… ;находим имя нужной черепашки положим [ферзь слово "ферзь :номер_строки] ;ставим текущего ферзя в левую клетку ;горизонтали скажи :ферзь [исходная_позиция] ;последовательно проверяем все поля данной ;горизонтали повтори размер_доски [;если ферзь стоит безопасно, ;то перечисляем все позиции ;начиная с горизонтали :номер_строки + 1 если скажи :ферзь [безопасно?] [все_позиции :номер_строки + 1] ;переставляем ферзя на следующее поле скажи :ферзь [передвинь]] конец Как мы уже упоминали ранее, структура этой процедуры похожа на структуру процедуры все_списки (и особенно на структуру процедуры все_списки_из_набора ), — советуем вам сравнить тексты этих процедур. Еще одно небольшое замечание: наличие трех команд скажи может показаться излишним — не проще ли один раз сделать нашу черепашку главной, выполнив команду для :ферзь сразу после инструкции положим [ферзь слово "ферзь :номер_строки] ? Конечно, проще, но процедура работать не будет — вы при желании можете это проверить. Дело в том, что у процедуры все_позиции появится побочный эффект: после ее выполнения главной черепашкой будет совсем не та, что перед выполнением. И поэтому передвигать и проверять безопасность мы будем вовсе не для той черепашки, для которой планировали. Простейший случай, для которого нам следует сформулировать правило остановки, достаточно очевиден. Если :номер_строки равен 1 + размер_доски, то это значит, что ферзи на горизонталях 1, 2, …, размер_доски расставлены безопасно, расстановка найдена и ничего содержательного делать не нужно. Решите сами, что следует делать в этом случае. Вы можете, например, напечатать координаты всех ферзей. Можно приостановить процедуру, чтобы вы могли рассмотреть расстановку и убедиться, что она безопасна. Приостановить работу процедуры можно с помощью команды сообщи — у этого примитива один аргумент, который может быть как словом, так и списком. Действие команды состоит в том, что на экране появляется сообщение с указанным текстом, команда приостанавливает работу процедуры до тех пор, пока пользователь не уберет сообщение, нажав кнопку ОК. Правило остановки, использующее примитив сообщи, может выглядеть следующим образом: если :номер_строки = размер_доски + 1 [сообщи [Ферзи расставлены безопасно] стоп] Мне было лень 92 раза нажимать кнопку ОК — имеется именно столько, как я помню, безопасных расстановок ферзей, поэтому я предпочел просто поставить небольшую паузу. Для этого можно использовать примитив (команду) жди с одним числовым аргументом. Эта команда приостанавливает работу на указанное время, время измеряется в десятых долях секунды. Вот окончательный текст процедуры: это все_позиции :номер_строки ;если все ферзи уже расставлены, ;то ничего делать не надо, кроме ;небольшой паузы если :номер_строки = размер_доски + 1 [жди 20 стоп] ;находим имя нужной черепашки положим [ферзь слово "ферзь :номер_строки] ;ставим текущего ферзя в левую клетку ;горизонтали ;и показываем его скажи :ферзь [исходная_позиция пч] ;последовательно проверяем все поля ;данной горизонтали повтори размер_доски [;если ферзь стоит безопасно, ;то перечисляем все позиции ;начиная с горизонтали :номер_строки + 1 если скажи :ферзь [безопасно] [скажи :ферзь [нов_цвет 95] все_позиции :номер_строки + 1] ;переставляем ферзя на следующее поле скажи :ферзь [нов_цвет 15 передвинь]] ;убираем ферзя с доски скажи :ферзь [сч] конец Вы можете заметить, что добавлено не только правило остановки, но и весь текст слегка отредактирован: мы прячем/показываем черепашку, меняем ее цвет. Эти изменения чисто косметические и сделаны лишь для наглядности — мне хотелось видеть, какие ферзи уже расставлены (сколько агентов стоит в очереди, ожидая завершения своих подпрограмм), какого ферзя мы сейчас передвигаем, отыскивая безопасное место, и т.д. Должен признаться, что у меня на экране черепашки мелькали слишком быстро — пришлось добавить небольшую паузу в процедуру передвинь . Рекурсивные датчикиДо сих пор все рекурсивные процедуры, которые мы рассматривали, были командами. Но, конечно, рекурсия часто используется и при создании датчиков. Мы начнем обсуждение рекурсивных датчиков с обработки текстов, точнее — с кодировки, шифрования текстов. Шифр, который мы будем использовать, весьма примитивен: это просто подстановка, замена одного символа кириллицы другим. То есть мы заменим все вхождения буквы “а” на букву “й”, буквы “б” — на “ц” и так далее. Конечно, ни один человек, прочитавший “Пляшущих человечков” Конан Дойла или “Золотого жука” Эдгара По, не станет использовать столь тривиальный шрифт для секретных сообщений, — но нас в данном случае интересует не надежность шрифта, а его простота. Итак, мы зададим шифр с помощью двух
слов. Одно из них содержит буквы в алфавитном,
исходном порядке: "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ,
второе — шифр — определяет подстановку: Начнем с того, что напишем процедуру, кодирующую одну букву. Найти код заданной буквы достаточно просто: нужно просматривать символ за символом оба слова: алфавит и шифр. Как только в алфавите встретилась заданная буква, код буквы (соответствующий символ в слове “шифр”) найден. Приведем эскиз рекурсивной процедуры шифр_буквы . У этой процедуры 3 аргумента типа слово: кодируемая буква (однобуквенное слово); слово, содержащее символы в алфавитном (исходном) порядке; и шифр — слово, составленное из кодов этих символов. это шифр_буквы :буква :исходный :шифр если :буква = прв :исходный [выход прв :шифр] выход шифр_буквы :буква кпрв :исходный кпрв :шифр конец Мы сравниваем первую букву в слове исходный с заданной буквой. Если буквы совпадают, то код найден — это первый символ слова шифр . В противном случае мы удаляем первый, уже проверенный символ в слове исходный, первый символ в слове шифр и вычисляем код буквы с новыми значениями аргументов. Найденный код и будет результатом работы нашей процедуры. Теперь мы можем зашифровать букву, использовав нужные значения аргументов исходный и шифр , — напомню, что в моем проекте нужные слова хранятся в двух текстовых окнах. Например: покажи шифр_буквы "А алфавит шифр Й покажи шифр_буквы "Ю алфавит шифр Б Два замечания по поводу процедуры шифр_буквы. Во-первых, инфиксный логический датчик = (как и соответствующий префиксный датчик равны? ) не различает строчных и прописных букв. Поэтому в нашем случае шифры прописных и строчных букв совпадают. Такое поведение процедуры нас вполне устраивает, но если бы мы захотели шифровать строчные и прописные буквы по-разному, то могли бы воспользоваться логическим датчиком идентичны? с двумя аргументами: этот датчик сообщает слово “да” в том случае, когда значения его аргументов совпадают. Во-вторых, процедура аварийно завершится, если мы попытаемся зашифровать символ, не входящий в исходный алфавит, например, выполним инструкцию покажи шифр_буквы "W алфавит шифр Такое поведение трудно считать приемлемым, поскольку мы не можем гарантировать, что в кодируемом тексте не встречаются символы, отличные от кириллицы. Мы, конечно, могли бы расширить алфавит, однако давайте договоримся, что если символ не входит в алфавит, то мы его не меняем, кодом такого символа является он сам. Небольшая редакция процедуры учитывает эту договоренность и избавляет процедуру от указанного недостатка: это шифр_буквы :буква :исходный :шифр если пусто? :исходный [;мы дошли до конца алфавита ;и не нашли искомой буквы выход :буква] если :буква = прв :исходный [выход прв :шифр] выход шифр_буквы :буква кпрв :исходный кпрв :шифр конец Теперь мы готовы, используя процедуру шифр_буквы, приступить к кодированию слов. Кодировать слова даже проще, чем кодировать буквы: нужно просматривать слово буква за буквой, заменяя каждую букву шифром буквы. Ввиду простоты этой операции, мы напишем три варианта процедуры кодировки слова. Первый вариант не рекурсивный, а итеративный: мы используем цикл — примитив повтори . Вот одна из версий такой процедуры: это шифр_слова_в_цикле :слово :исходный :шифр ;в переменной зашифровано хранится ;зашифрованный ;начальный фрагмент исходного слова положим [зашифровано " ] повтори сколько :слово [;добавляем в слово зашифровано ;код первой ;буквы переменной слово пусть "зашифровано слово :зашифровано шифр_буквы прв :слово :исходный :шифр ;удаляем зашифрованную букву ;из исходного слова пусть "слово кпрв :слово] выход :зашифровано конец Однако поскольку в данный момент мы обсуждаем рекурсию, давайте напишем рекурсивную процедуру. Рекурсивное описание кодировки слова можно сформулировать так: код слова получается объединением кода первой буквы слова и кода более короткого слова — исходного слова без первой буквы. Осталось лишь описать простейший случай: кодом пустого слова является само пустое слово. Вот как выглядит формальная запись данного описания: это шифр_слова :слово :исходный :шифр если пусто? :слово [выход "] выход слово шифр_буквы прв :слово :исходный :шифр шифр_слова кпрв :слово :исходный :шифр конец Вот пример инструкции, кодирующей слово: покажи шифр_слова "преступник алфавит шифр ПРНОЛДПВЗЪ Процедура шифр_слова иллюстрирует весьма распространенную схему рекурсивных датчиков: мы обрабатываем первый элемент объекта, рекурсивно обрабатываем объект без первого элемента и получаем результат, объединив полученные значения. Следующая (и последняя) версия кодирования слова тоже будет рекурсивной — назовем ее шифр_слова*. В этой версии мы будем использовать обсуждавшиеся ранее аккумуляторы. Мы вводим дополнительный аргумент процедуры с именем “зашифровано”, мы предполагаем, что значением этого аргумента является уже зашифрованный начальный фрагмент исходного слова. Рекурсивный шаг состоит в том, что мы вычисляем значение датчика шифр_слова* с новыми значениями аргументов: в исходном слове мы удаляем первую букву, зато к значению аргумента зашифровано мы в конец приписываем код этой буквы. Простейший случай: исходное слово пусто, в этом случае значение датчика совпадает со значением аргумента зашифровано. Нетрудно заметить, что приведенное описание очень близко к исходному, итеративному, поэтому неудивительно, что текст процедуры шифр_слова* почти дословно повторяет текст процедуры шифр_слова_в_цикле : это шифр_слова* :слово :исходный :шифр :зашифровано если пусто? :слово [выход :зашифровано] выход шифр_слова* ;удаляем зашифрованную букву ;из исходного слова кпрв :слово :исходный :шифр ;добавляем еще одну букву в слово ;зашифровано слово :зашифровано шифр_буквы прв :слово :исходный :шифр конец Какая версия: шифр_слова или шифр_слова* лучше? Если кто-то скажет, что лучше всех версия шифр_слова_в_цикле , то он, возможно, будет прав, но еще раз напомню — сейчас мы обсуждаем рекурсию. Прежде всего, не очень понятно, что значит слово “лучше”. До сих пор мы сравнивали в основном текст процедур: какой из них понятнее, проще, нагляднее и пр. В этом смысле, на мой взгляд, обе версии примерно равноценны, — я надеюсь, что вы тоже считаете тексты обеих процедур достаточно простыми и понятными. Какая из них предпочтительнее — дело вкуса. Есть, однако, и другое понимание слова “лучше” — какая процедура эффективнее. Слово “эффективнее” тоже, конечно, допускает разные толкования: одна процедура может быстрее работать, чем другая, или обрабатывать данные такого размера, с которыми не справляется другая процедура, и так далее. В нашей книжке мы практически не будем касаться эффективности программ. Это отдельная важная тема, требующая большого и серьезного обсуждения. Несколько слов об эффективности процедур мы скажем чуть позже в данном разделе, обсуждая числа Фибоначчи. Здесь же мы же ограничимся кратким простым замечанием: эффективность процедуры зависит не только от выбранного вами алгоритма и от того, как вы запишете этот алгоритм, но и от того, как именно реализован язык — в нашем случае Лого. Так, в программе ЛогоМиры 3, которую я использую, процедура шифр_слова справляется с более длинными словами, чем процедура шифр_слова*. В других версиях Лого ситуация может быть противоположной. Одно практическое замечание: если вы решите экспериментальным путем выяснить, при каком размере данных ваша программа ломается, то делайте это крайне осторожно. Учтите, что сломаться может не только ваша процедура, — вам повезет, если вы просто получите сообщение, подобное “Нет свободной памяти в шифр_слова ”. Сломаться может и сама программа Лого: повиснуть или неожиданно завершиться. Поэтому перед подобными рискованными экспериментами побеспокойтесь по крайней мере о том, чтобы сохранить ваш проект. Вернемся к основной теме нашего разговора — шифрованию. Теперь пора кодировать предложения. Если предложение представлено в виде списка слов, то закодировать его не сложно. Процедура кодирования такого списка совершенно аналогична процедуре кодирования слова. Отличие в том, что, поскольку элементами списка являются слова, а не буквы, то мы вместо процедуры шифр_буквы используем процедуру шифр_слова. Вот один из вариантов процедуры шифр_предложения : это шифр_предложения :предложение :исходный :шифр если пусто? :предложение [выход []] выход предложение шифр_слова прв :предложение :исходный :шифр шифр_предложения кпрв :предложение :исходный :шифр конец Вот пример соответствующей инструкции: покажи шифр_предложения [Преступника зовут Джон.] алфавит шифр ПРНОЛДПВЗЪЙ ЩАУДЛ ЕШАВ. Простое предложение, приведенное в предыдущем примере, естественно представить в виде списка слов. Конечно, при анализе текстов приходится иметь дело с более сложными высказываниями и использовать для их записи более сложные структуры. Программе (да и человеку) не очень удобно анализировать утверждение: [Полицейского, сказавшего, что свидетеля, сказавшего, что преступника зовут Джон зовут Джеймс зовут Джереми.] Приходится записывать это примерно так: [Полицейского, [сказавшего, что свидетеля, [сказавшего, что преступника зовут Джон] зовут Джеймс] зовут Джереми.] Итак, нам была бы полезна процедура, шифрующая произвольные списки, а не только списки слов. Результатом шифровки должен быть список такой же структуры, что и исходный, но состоящий из зашифрованных слов, — для вышеприведенного списка шифром является список [ПАФЗЁНХОЪАКА, [ОЪЙЩЙУЧНКА, ЯЛА ОУЗЕНЛНФЮ, [ОЪЙЩЙУЧНКА, ЯЛА ПРНОЛДПВЗЪЙ ЩАУДЛ ЕШАВ] ЩАУДЛ ЕШНХЫО] ЩАУДЛ ЕШНРНЫЗ.] . Общая структура процедуры шифрования списка похожа на структуру процедуры шифр_слова (и шифр_предложения ): мы отдельно шифруем первый элемент списка, рекурсивно шифруем список без первого элемента и объединяем результаты. Важным отличием является то, что первый элемент может быть того же типа, что исходный объект, — он тоже может быть списком. Однако в этом случае он “проще” исходного списка — у него меньшая глубина. Вот текст соответствующей процедуры: это шифр_списка :список :исходный :шифр если пусто? :список [выход []] ;первый элемент списка – слово, ;мы помещаем шифр этого слова ;в качестве первого элемента ;в шифр списка без первого элемента если слово? прв :список [выход внсп шифр_слова прв :список :исходный :шифр шифр_списка кпрв :список :исходный :шифр] ;первый элемент списка – список, ;мы находим (рекурсивно) шифр этого ;элемента и ;помещаем в качестве первого элемента ;в шифр списка без первого элемента выход внсп шифр_списка прв :список :исходный :шифр шифр_списка кпрв :список :исходный :шифр конец Заметим в заключение, что написать нерекурсивную, итеративную версию процедуры шифр_списка не очень просто. Теперь рассмотрим другую задачу — нахождение двоичной записи числа. Эта задача, по существу, очень близка к кодировке — нам следует по числу найти некоторое слово: его двоичную запись. Напомним рекурсивное определение двоичной записи числа n: нам нужно взять двоичную запись целой части n/2 и приписать к ней остаток от деления n на 2. Такое определение можно непосредственно записать в виде процедуры: это двоичная_запись :число если :число = 0 [выход 0] выход слово двоичная_запись целое :число / 2 остаток :число 2 конец Здесь мы использовали два новых примитива: целое и остаток . И тот и другой являются датчиками, у датчика целое один аргумент — число, значением аргумента является наибольшее целое число, не превосходящее значения аргумента. У датчика остаток два числовых аргумента; если эти аргументы — целые числа, то датчик сообщает остаток от деления первого числа на второе. Наша процедура двоичная_запись действительно сообщает двоичную запись числа, однако в этой записи всегда присутствует ведущий ноль: значением выражения двоичная_запись 3 будет слово 011 . Есть несколько разных способов избавиться от этого недостатка; полагаю, что вы сами без труда сможете исправить процедуру. Обратная задача — нахождение числа по его двоичной записи — ничуть не сложнее. Из предыдущего рекурсивного определения непосредственно следует рекурсивная схема нахождения числа по его записи: нужно разделить запись на две части — последний символ и запись числа без последнего символа. Далее, мы находим число, соответствующее записи числа без последнего символа, умножаем его на 2 и прибавляем последний символ. Текст соответствующей процедуры несколько короче (и, возможно, понятнее) этого словесного описания: это число_по_двоичной_записи :запись если пусто? :запись [выход 0] выход (псл :запись) + 2 * число_по_двоичной_записи кпсл :запись конец — скобки в выражении (псл :запись) необходимы, поскольку приоритет датчика + выше, чем приоритет датчика псл. Нетрудно обобщить наши процедуры для работы с записью числа по произвольному основанию. Нужно лишь договориться о том, какие символы мы используем для цифр, значение которых больше 9. Традиционно для таких цифр используются начальные буквы латинского алфавита: A — 10, B — 11, C — 12 ?— и так далее. Вот как выглядит соответствующая процедура нахождения “цифры”: это цифра :число если :число < 10 [выход :число] ;мы рассчитываем, что основание записи ;не превосходит 20 выход элемент :число – 9 [A B C D E F G H I J] конец В процедуре цифра используется новый примитив — датчик элемент с двумя аргументами. Значением первого аргумента должен быть номер — положительное целое число, значение второго аргумента произвольного типа — слово или список. Датчик сообщает элемент (элементом слова является буква) второго аргумента с указанным номером. Если такого элемента нет (номер превышает количество элементов), то датчик сообщает об ошибке. Используя процедуру цифра , нетрудно написать процедуру получения записи числа с произвольным основанием. Эта процедура получается простой модификацией процедуры двоичная_запись: это запись_по_числу :число :основание если :число = 0 [выход 0] выход слово запись_по_числу целое :число / :основание :основание цифра остаток :число :основание конец Столь же нетрудно модифицировать процедуру число_по_двоичной_записи для работы с записью числа по произвольному основанию. В предыдущих примерах текст процедуры являлся более-менее дословной записью словесного рекурсивного определения. Текст, полученный таким образом, обычно достаточно прост и понятен. Однако такой подход отнюдь не всегда приводит к лучшему решению задачи. Классическим примером являются числа Фибоначчи. Числа Фибоначчи — это последовательность целых чисел, начинающаяся с двух единиц, каждый следующий член последовательности получается сложением двух предыдущих. Вот начало этой последовательности: 1, 1, 2, 3, 5, 8, 13, 21, … Если обозначить через Fib(n) элемент последовательности с номером n, то Fib(n) = Fib(n – 1) + Fib(n – 2), если n > 2 и Fib(n) = 1 при n = 1, 2. Такое определение нетрудно записать в виде простой процедуры: это fib :число если :число < 3 [выход 1] выход (fib :число – 1) + fib :число – 2 конец Эта процедура работает правильно, но весьма медленно. Выяснить время работы той или иной инструкции не слишком сложно — можно воспользоваться датчиком без аргументов счетчик , сообщающим время (в десятых секунды) с момента запуска программы или с момента последнего выполнения команды нов_счет. У этой команды нет аргументов, ее действие состоит в том, что счетчик времени обнуляется. Мой компьютер после выполнения инструкций нов_счет покажи fib 35 покажи счетчик сообщил 14930352 1301 то есть нахождение 35-го члена последовательности — числа 14 930 352 заняло у него более двух минут. Такая медлительность не удивительна. Нетрудно заметить, что время нахождения элемента с номером n + 1 примерно вдвое больше времени нахождения элемента с номером n. Действительно, при вычислении элемента с номером n нам приходится выполнять два рекурсивных вызова — для вычисления элементов с номерами n–1 и n–2. Во многих случаях такие неоднократные рекурсивные вызовы устранить весьма трудно, но в случае чисел Фибоначчи от них избавиться можно. Заметим, что элемент с номером n–2 мы вычисляем дважды: при нахождении элемента с номером n–1 и при нахождении элемента с номером n. Часто для того, чтобы не вычислять одно и то же значение многократно, прибегают к технике так называемого динамического программирования: мы запоминаем (в случае Лого — в некотором списке) уже найденные промежуточные значения с тем, чтобы использовать их в дальнейшем. В случае чисел Фибоначчи мы могли бы находить не элемент последовательности с номером n, а список чисел — начальный отрезок последовательности Фибоначчи длиной n. На первый взгляд эта задача не проще исходной, но она существенно упрощается, если использовать аккумулятор. Итак, мы пишем процедуру ряд_fib с двумя аргументами. Один аргумент — аккумулятор — список, содержащий начальный отрезок последовательности Фибоначчи. Второй аргумент — положительное целое число n. Наша процедура должна приписать к значению аккумулятора следующие n элементов: это ряд_fib :начало :число если 0 = :число [вых :начало] вых ряд_fib вксп ;помещаем в конец списка начало ;очередной элемент – сумму двух ;последних элементов списка начало (псл :начало) + (псл кпсл :начало) :начало ;уменьшаем число элементов, :которые нужно добавить :число - 1 конец В отличие от предыдущих использований аккумулятора начальное значение аккумулятора не может быть пустым, оно должно содержать не менее двух первых элементов последовательности Фибоначчи. Вот как можно получить первые 5 чисел Фибоначчи: покажи ряд_fib [1 1] 3 1 1 2 3 5 А значением выражения псл ряд_fib [1 1] 33 будет 35-е число Фибоначчи. Процедура ряд_fib работает достаточно быстро, но у нее есть недостаток: в процессе работы она строит длинные списки. Следующая версия процедуры избавлена и от этого недостатка. Заметим, что для вычисления очередного члена последовательности нам не нужно знать все предыдущие элементы — нам достаточно знать значения лишь двух предыдущих элементов. Поэтому мы можем постараться написать процедуру, сообщающую не весь отрезок последовательности от 1 до n, а пару элементов последовательности: элемент с номером n и элемент с номером n–1. В данной процедуре мы предполагаем, что значение аргумента — номер элемента последовательности — не меньше 2. Значением процедуры будет список из двух чисел — двух соседних элементов последовательности Фибоначчи. Вот текст соответствующей процедуры: это пара_fib :число если :число = 2 [выход [1 1]] положим [предыдущие пара_fib :число – 1] выход список ;первый элемент пары – второй элемент ;предыдущей пары псл :предыдущие ;второй элемент пары – сумма элементов ;предыдущей пары (прв :предыдущие) + псл :предыдущие конец На моем компьютере вычисление значения пара_fib 200 заняло около 0,002 секунды. Постороннее замечание: как я оценил время работы процедуры, если в моем распоряжении лишь датчик счетчик, сообщающий значение времени с точностью до 0,1 секунды? Если бы мы хотели оценить время работы команды, то мы могли бы выполнить примерно такую последовательность инструкций: нов_счет повтори 1000 [процедура] покажи счетчик — где процедура — имя оцениваемой команды (здесь мы, конечно, предполагаем, что время выполнения нашей команды практически постоянно — в частности, никак не зависит от предыдущих выполнений этой команды). Непосредственно использовать указанную последовательность инструкций для датчиков невозможно: датчик возвращает значение, и мы должны им как-то распорядиться. Выполнение инструкций нов_счет повтори 1000 [пара_fib 200] покажи счетчик приведет к сообщению Не знаю, что делать с [1,73402521173e+041 2,80571172993e+041] Стандартное решение (хотя и несколько необычное на первый взгляд) состоит в том, что мы определяем процедуру это игнорируй :значение конец Эта процедура ничего не делает со значением своего единственного аргумента, — ее назначение, как и следует из названия, состоит в том, чтобы просто проигнорировать это значение. Теперь выражение игнорируй пара_fib 200 является корректной инструкцией, и мы можем выполнить инструкции нов_счет повтори 1000 [игнорируй пара_fib 200] покажи счетчик До сих пор мы обсуждали датчики, значениями которых являются списки, слова и числа. Рассмотрим теперь пример рекурсивного логического датчика. Типичным примером такого датчика является алфавитный порядок слов. Алфавитный порядок задается следующим образом. Чтобы сравнить два слова, мы берем первые буквы этих слов. Если эти буквы разные, то первым (по порядку) является слово, чья первая буква находится в алфавите раньше. Если первые буквы равны, то мы сравниваем вторые буквы и так далее. Так, например, слово “москит” находится после слова “марка” и предшествует слову “московский”. Конечно, алфавитный порядок на словах зависит от того, как именно мы определили алфавитный порядок на буквах: различаем ли мы строчные и прописные буквы, как соотносятся русские и латинские буквы и так далее. Давайте считать, что порядок на буквах уже определен, — иными словами, что у нас есть процедура, логический датчик буква_меньше с двумя аргументами типа слово . Если значения обоих аргументов этого датчика — буквы (более наукообразно — однобуквенные слова), то датчик выясняет алфавитный порядок этих букв: возвращает “да”, если первая буква предшествует второй в алфавитном порядке, и возвращает “нет” в противном случае. Что делает датчик буква_меньше в тех случаях, когда его аргументы не являются буквами — например, значения содержат более одной буквы, или являются пустыми словами, или вовсе не являются словами, — нас, в общем, не интересует. Используя этот датчик, нетрудно написать процедуру слово_меньше, сравнивающую два слова. Вот общая схема такой процедуры: это слово_меньше :слово1 :слово2 ;здесь должны быть правила остановки если буква_меньше прв :слово1 прв :слово2 [выход "да] если буква_меньше прв :слово2 прв :слово1 [выход "нет] выход слово_меньше кпрв :слово1 кпрв :слово2 конец Этот текст не требует особых комментариев: он практически непосредственно повторяет текстовое описание. Как это часто бывает, правило остановки не указано явно в текстовом описании. Ясно, что следует остановиться в том случае, когда мы дошли до конца одного из слов, — иными словами, в той ситуации, когда одно слово является началом другого. Нам следует уточнить, какое из этих двух слов мы считаем предшествующим другому, то есть считаем ли мы, что слово “море” идет перед словом “морепродукты”, или наоборот. Если мы, как и большинство составителей словарей, считаем, что начало слова предшествует самому слову, то правила остановки могут быть записаны следующим образом: это слово_меньше :слово1 :слово2 если пусто? :слово2 [выход "нет] если пусто? :слово1 [выход "да] если буква_меньше прв :слово1 прв :слово2 [выход "да] если буква_меньше прв :слово2 прв :слово1 [выход "нет] выход слово_меньше кпрв :слово1 кпрв :слово2 конец Надеюсь, что вам очевиден смысл каждого из этих двух условий и почему они приведены именно в данном порядке. Черепашья графикаОдной из характерных особенностей программных сред Лого является наличие черепашьей графики: у каждой черепашки имеется перо; когда это перо опущено, то черепашка при движении оставляет след — рисует траекторию своего движения. Чаще всего знакомство с Лого начинается именно со знакомства с черепашьей графикой, — мы объясняем черепашке, как нарисовать какую-то геометрическую фигуру, пишем процедуры, которые рисуют на листе разнообразные узоры, и так далее. Черепашья графика настолько тесно ассоциируется с Лого, что время от времени распространялись программные среды, называвшие себя “Лого” и не содержавшие, по сути дела, ничего, кроме черепашьей графики: в них отсутствовали списки, полноценная работа с переменными и многое другое. В данном разделе мы собираемся посмотреть на несколько графических проектов Лого. Однако я полагаю, что вы уже провели некоторое время, рисуя с помощью черепашки квадраты, треугольники и окружности. Поэтому мы собираемся обсудить изображение более сложных объектов. Как нарисовать дерево Мы начнем наше обсуждение с изображения дерева:
Возможно, что этот рисунок не слишком напоминает обычное дерево, которое можно встретить в саду или в лесу (скорее уж — куст), но он достаточно точно изображает то, что в математике и программировании называется двоичным деревом, — на рисунке изображено дерево уровня 5. Я надеюсь, что для вас очевиден рекурсивный характер картинки. Наше дерево уровня 5 состоит из двух больших отрезков — ветвей, проведенных из корня, к вершине каждого из этих ветвей “приклеено” дерево уровня 4. Это рекурсивное описание можно попробовать перевести в (рекурсивную) процедуру. Нашей процедуре, которую мы назовем “дерево”, следует знать, дерево какого уровня мы хотим нарисовать. Кроме того, полезно иметь возможность указывать, какова длина ветвей, растущих из корня. Таким образом, заголовок процедуры будет иметь вид: это дерево :уровень :длина Мы предполагаем, что черепашка стоит в корне дерева и смотрит вертикально вверх. Таким образом, основная часть процедуры (мы пока оставляем в стороне правило остановки) может выглядеть так: лв 30 вп :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень – 1 :длина / 2 нд :длина ;возвращаемся в корень пр 60 вп :длина ;рисуем правую ветвь ;рисуем правое дерево меньшего уровня дерево :уровень – 1 :длина / 2 Теперь о правиле остановки — какой случай мы считаем простейшим и что нам следует делать в этом случае. Достаточно очевидно, что простейшим случаем можно считать дерево уровня 0 — такое дерево нам следует нарисовать в тот момент, когда мы находимся в конце самой верхней ветви дерева. Вершины в конце этих ветвей часто называют “листьями”. Давайте предусмотрим на всякий случай процедуру лист , которая будет рисовать лист дерева нужного размера. В выбранном нами варианте дерева лист рисуется тривиально — процедура лист не делает ничего. Вот какой текст процедуры дерево у нас получился: это дерево :уровень :длина если : уровень = 0 [лист :длина стоп] лв 30 вп :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень – 1 :длина / 2 нд :длина ;возвращаемся в корень пр 60 вп :длина ;рисуем правую ветвь ;рисуем правое дерево меньшего уровня дерево :уровень – 1 :длина / 2 конец это лист :длина конец Вот результат выполнения инструкции дерево 5 150:
Это не совсем то, что мы ожидали увидеть. Я искренне рад, если вы сами, может быть даже до выполнения инструкции, обнаружили ошибку в нашей процедуре. Все дело в том, что мы не позаботились о том, чтобы после выполнения процедуры дерево состояние системы было таким же, как и до ее выполнения. С подобной проблемой мы уже сталкивались, обсуждая побочные эффекты в процедурах и разницу в использовании примитивов для и скажи в процедуре расстановки ферзей. Нарисовав левую ветвь и левое дерево лв 30 вп :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень – 1 :длина / 2 мы рассчитываем, что черепашка вновь в корне левого дерева и стоит тем же курсом, что и до рисования левого дерева. Однако никаких оснований рассчитывать на это у нас нет — процедура дерево оставляет черепашку где попало. Следует побеспокоиться о том, чтобы восстановить исходное состояние. Отредактируем процедуру дерево , добавив еще одну строку. Кроме того, со свойственной нам педантичностью прокомментируем тривиальную процедуру лист : это дерево :уровень :длина если :уровень = 0 [лист :длина стоп] лв 30 вп :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень - 1 :длина / 2 нд :длина ;возвращаемся в корень пр 60 вп :длина ;рисуем правую ветвь ;рисуем правое дерево меньшего уровня дерево :уровень - 1 :длина / 2 ;возвращаем черепашку в исходное положение нд :длина лв 30 конец ;процедура лист должна возвращать черепашку ;в исходное положение это лист :длина конец Теперь мы можем быть уверены, что если процедура дерево правильно рисует дерево уровня k и возвращает черепашку в исходное положение, то эта процедура правильно рисует и дерево уровня k + 1 и возвращает черепашку в исходное положение. Мы уже замечали, что наше дерево выглядит не слишком реалистично. вы можете попробовать, при желании, изменить программу так, чтобы картинка выглядела натуральнее. Например, на приведенном ниже рисунке с изменением уровня дерева меняется не только длина ветвей, но и угол между ветвями (к аргументам процедуры дерево был добавлен еще один — “угол”).
Если вы решите, что дерево излишне симметрично, то попробуйте сделать дерево “случайным” — использовать в процедуре дерево датчик случайный или сл_элемент . Не забудьте, однако, восстанавливать исходное состояние. Например, вы можете решить сделать длину ветвей случайной, но простое добавление датчика случайный … лв 30 вп случайный :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень - 1 :длина / 2 нд случайный :длина ;возвращаемся в корень … к цели, конечно, не приведет. Возвращаясь в корень, мы почти наверняка пройдем не то расстояние, которое мы прошли, рисуя ветвь. Решить эту проблему можно, используя локальные переменные: … положим [левая_ветвь случайный :длина] лв 30 вп :левая_ветвь ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево :уровень - 1 :длина / 2 нд :левая_ветвь ;возвращаемся в корень … Мы не собираемся детально обсуждать все эти модификации — я уверен, что при желании вы можете самостоятельно внести соответствующие изменения в тексты процедур. Лучше мы потратим время на исследование уже нарисованного дерева. Давайте попробуем выяснить, что рисует процедура дерево* — простая модификация процедуры дерево : это дерево* :уровень :длина если :уровень = 0 [лист* :длина стоп] лв 30 вп :длина ;рисуем левую ветвь ;рисуем левое дерево меньшего уровня дерево* :уровень - 1 :длина / 2 нд :длина ;возвращаемся в корень пр 60 вп :длина ;рисуем правую ветвь ;рисуем правое дерево меньшего уровня дерево* :уровень - 1 :длина / 2 ;возвращаем черепашку в исходное положение нд :длина лв 30 конец ;процедура лист* должна возвращать ;черепашку в исходное положение это лист* :длина ;рисуем две ветви лв 30 вп :длина нд :длина пр 60 вп :длина ;возвращаем черепашку в исходное положение нд :длина лв 30 конец Структура процедуры дерево* дословно повторяет структуру процедуры дерево . Отличие лишь в правиле остановки: в тот момент, когда процедура дерево вызывает (тривиальную) процедуру лист, процедура дерево* вызывает процедуру лист*, рисующую две ветки — то есть рисующую дерево уровня 1. Нетрудно понять, что процедура дерево* тоже рисует дерево. Более того, можно убедиться (недоверчивые могут проверить на компьютере, особо недоверчивые — доказать, например, с помощью математической индукции), что инструкция дерево уровень+1 длина в точности эквивалентна инструкции дерево* уровень длина. Иными словами, текст процедуры дерево утверждает, что дерево уровня k + 1 строится так же, как и дерево уровня k, с единственным отличием: в тот момент, когда при построении дерева уровня k рисуется лист, в дереве уровня k + 1 следует нарисовать две ветки — дерево размера 1. Это, конечно, верное утверждение: ясно, что дерево уровня k + 1 получается из дерева уровня k заменой каждого листа на два ветки — дерево уровня 1. Мы написали процедуру дерево , исходя из глобального рекурсивного определения: объяснения, как рисунок уровня k + 1 можно склеить из нескольких (в случае дерева — из двух) рисунков уровня k. Однако, как мы только что заметили, процедура дерево описывает и локальное рекурсивное определение: объяснение того, как рисунок уровня k + 1 можно получить, модифицируя некоторые элементы (в случае дерева — листья) рисунка уровня k. Таким образом, текст процедуры дерево мог быть получен, исходя как из глобального, так и из локального рекурсивного определения. Такая двойственность нам пригодится в дальнейшем, поскольку в одних задачах естественнее рассматривать глобальное, а в других — локальное описание. Еще несколько рекурсивных узоров Нашим следующим примером будет узор, составленный из треугольников:
И здесь, как и в предыдущем примере, (глобальный) рекурсивный характер рисунка достаточно очевиден: чтобы нарисовать треугольник уровня k + 1, нужно в углах правильного треугольника заданного размера нарисовать 3 треугольника уровня k вдвое меньшего размера. Это описание нетрудно записать в виде процедуры: это треугольник :уровень :сторона если :уровень = 0 [стоп] повтори 3 [ ;рисуем меньший треугольник в углу треугольник :уровень – 1 :сторона / 2 ;проводим сторону треугольника и ;переходим в следующий угол вп :сторона пр 120] конец В данной процедуре правило
остановки достаточно очевидно: если уровень
равен 0, то мы не делаем ничего. Основная часть
процедуры тоже достаточно понятна — однако
следует обратить внимание на то, что процедуре треугольник следует возвращать
черепашку в исходное положение. Ведь, проводя
сторону и поворачивая черепашку на 120 градусов,
мы рассчитываем на то, что черепашка находится в
том же состоянии, что и перед выполнением
инструкции треугольник :сторона / 2
:уровень – 1 . К счастью, в случае процедуры треугольник никаких специальных
усилий по восстановлению исходного состояния
черепашки предпринимать не требуется. Нетрудно
заметить, что если треугольник уровня повтори 3[вп :сторона пр 120] восстанавливает исходное состояние черепашки. То, что треугольник уровня 0 не меняет состояния черепашки, более чем очевидно. “Не хотите же вы сказать, — спросил меня коллега, разглядывая захламленный экран моего компьютера, — что разумные рекурсивные графические программы должны всегда восстанавливать исходное состояние?”. Не хочу. В исходном состоянии нет ничего неприкосновенного. Важно отдавать себе отчет в том, как именно наша процедура изменяет исходное состояние. Иногда, как в случае процедуры дерево , мы предпринимаем специальные усилия для того, чтобы восстановить исходное состояние. Иногда, если нам повезло, после выполнения процедуры черепашка находится именно в нужном месте в нужное время, чтобы продолжать работу. Рассмотрим следующий пример:
Изображенная здесь фигура представляет собой “треугольник”, составленный из трех одинаковых кривых, — одна из кривых выделена на рисунке цветом (в газетном варианте — оттенком серого цвета). Как устроена такая кривая (по существу — ломаная линия)? Мы дадим локальное рекурсивное описание этих ломаных: объясним, как получить ломаную уровня k + 1, преобразовав звенья (отрезки) ломаной уровня k. Забегая немножко вперед, заметим, что наш рисунок составлен из трех ломаных уровня 5 размера 250. Итак, ломаная уровня 0 — это просто отрезок заданной длины. Ломаная уровня k + 1 получается из ломаной уровня k следующим образом: каждый отрезок ломаной уровня k заменяется четырьмя отрезками меньшей (точнее — в 3 раза меньшей) длины так, как показано на следующем рисунке:
Здесь серым нарисован исходный отрезок, а черным — заменяющая его ломаная. Вот как выглядят ломаные уровня 2 и 3 соответственно:
Нетрудно объяснить черепашке, как выполнить указанную замену. Предположим, что черепашка стоит в начале отрезка длины размер и ее курс совпадает с направлением отрезка. Тогда инструкция замены может быть записана следующим образом: вп размер / 3 лв 60 вп размер / 3 пр 120 вп размер / 3 лв 60 вп размер / 3 Совершенно очевидно, что эта инструкция изменяет состояние черепашки: выполнив инструкцию, она смещается вперед на расстояние размер. Курс черепашки остается прежним. Мы, конечно, могли бы восстановить исходное состояние, подняв черепашье перо и вернув ее назад на нужное расстояние, но нужно ли это делать? Ведь, выполнив замену одного отрезка, черепашка находится именно в том положении, которое требуется для начала замены следующего отрезка:
Конечно, когда мы заменяем соседние отрезки ломаной уровня k, они повернуты относительно друг друга, а не лежат, как на данном рисунке, на одной прямой. Но поворот отрезка означает, что процедура, рисующая ломаную уровня k, повернет черепашку в нужном направлении и она будет готова к замене следующего отрезка. Итак, мы готовы написать процедуру: это ломаная :уровень :размер если :уровень = 0 [вп :размер стоп] ломаная :уровень – 1 :размер / 3 лв 60 ломаная :уровень – 1 :размер / 3 пр 120 ломаная :уровень – 1 :размер / 3 лв 60 ломаная :уровень – 1 :размер / 3 конец — а инструкция, рисующая исходную фигуру, может быть записана как повтори 3 [ломаная 5 250 пр 120] Процедура написана и даже правильно работает. Завершая данный пример, заметим, что мы выбрали некоторую конкретную замену — мы заменяем отрезок четырьмя отрезками меньшей длины. Вы без труда можете придумать какой-то другой способ замены — заменять отрезок какой-либо другой подходящей ломаной линией. Изображенная на следующем рисунке кривая носит название “кривая дракона” — здесь изображена кривая дракона 10-го порядка. Вообще-то кривая дракона является ломаной линией, соседние отрезки которой расположены под прямым углом друг к другу. На рисунке мы для наглядности “срезали” углы.
Кривая дракона определяется следующим образом. Возьмем лист бумаги. Сложим его пополам. Этот сложенный лист еще раз сложим пополам и повторим эту процедуру несколько раз. Если мы после этого развернем лист так, чтобы каждый сгиб был под прямым углом, и посмотрим на лист с торца, то увидим кривую дракона соответствующего порядка. Вот как выглядит кривая дракона 3-го порядка:
Если вас, как настоящего программиста, коробит от определений, в которых фигурируют бумага, клей и канцелярские скрепки, то в качестве оправдания замечу, что кривую дракона придумал физик Джон Э. Хейуэй, а физики имеют дело и с более низменными объектами. Вот как выглядят кривые дракона 0-, 1-, 2- и 3-го порядков:
Бумажное определение легко переводится в “локальное” рекурсивное: как из кривой дракона k-го порядка получить кривую дракона k + 1-го порядка. Нужно каждый отрезок кривой дракона k-го порядка “согнуть” под прямым углом, так, как показано на рисунках а или б:
Серым на рисунке изображен исходный отрезок, черным — “согнутая” линия. Причем, если представить себе лист бумаги, то достаточно очевидно, что соседние отрезки кривой дракона следует “сгибать” в противоположных направлениях: если данный отрезок согнут, как на рисунке а, то следующий сгиб должен быть б и так далее. На следующем рисунке показано, как кривая дракона 5-го порядка (изображенная черным) получается “сгибанием” каждого отрезка серой кривой дракона 4-го порядка:
Эта ситуация очень напоминает процедуру ломаная: и в этот раз мы заменяем каждый отрезок кривой порядка k некоторой ломаной линией. Есть, правда, и отличие: разные отрезки (четные и нечетные) заменяются по-разному — если нечетные отрезки сгибаются, как на рисунке а, то четные — как на рисунке б. Как именно сгибаются нечетные отрезки — как на рисунке а или как на рисунке б — непринципиально. Все зависит от того, в какую сторону вы привыкли складывать бумагу, и от точки зрения: с какой стороны вы смотрите на сложенный лист. Итак, нам нужны две инструкции для замены: нечетный_отрезок и четный_отрезок. Вот как могут выглядеть процедуры замены отрезка длины размер (мы, как обычно, предполагаем, что черепашка правильно установлена перед началом замены): нечетный_отрезок: вперед размер / кк 2 пр 90 вперед размер / кк 2 четный_отрезок: вперед размер / кк 2 лв 90 вперед размер / кк 2 Здесь использован примитив кк — он извлекает корень квадратный из указанного числа. Мы передвигаем черепашку на расстояние размер / кк 2 , поскольку хотим, чтобы конец заменяющей ломаной совпадал с концом заменяемого отрезка. Но, конечно, нам надо, как и раньше, быть внимательными к изменению начального состояния черепашки — ведь при таких заменах мы изменяем не только ее местоположение, но и курс. Какие меры нам следует предпринять, чтобы после одной замены подготовить черепашку к следующей? Оказывается — как обычно, нам повезло, никаких специальных действий нам предпринимать не нужно:
Мы видим, что после замены нечетного отрезка черепашка находится в исходном положении для замены следующего, четного отрезка, и наоборот. Еще одна тонкость: совершая замену, нам следует указывать, какими именно — четными или нечетными будут отрезки заменяющей ломаной. Нетрудно заметить, что при любой замене: как при замене нечетного отрезка, так и при замене четного отрезка — первый из двух отрезков заменяющей ломаной будет нечетным, а второй — четным. Итак, мы готовы написать две процедуры — замены четного и нечетного отрезков указанного порядка: это нечетный_отрезок :порядок :размер если :порядок = 0 [вперед :размер стоп] положим [катет :размер / кк 2] нечетный_отрезок :порядок – 1 :катет пр 90 четный_отрезок :порядок – 1 :катет конец это четный_отрезок :порядок :размер если :порядок = 0 [вперед :размер стоп] положим [катет :размер / кк 2] нечетный_отрезок :порядок – 1 :катет лв 90 четный_отрезок :порядок – 1 :катет конец Теперь, для того чтобы нарисовать кривую дракона, скажем, 8-го порядка размера 400, достаточно выполнить инструкцию нечетный_отрезок 8 400 . Начальная ориентация черепашки большого значения не имеет — от нее зависит, каким образом кривая будет повернута на листе. Но если вы хотите, чтобы кривая порядка k + 1 совпадала с “согнутой” кривой порядка k, то черепашка должна быть ориентирована так, чтобы быть готовой к замене первого отрезка кривой порядка k. Иными словами, перед рисованием кривой порядка k + 1 черепашка должна быть повернута налево на 45 градусов по сравнению с тем направлением, в котором она начинала рисовать кривую порядка k. Мартин Гарднер советует посмотреть, как выглядят четыре кривых дракона, повернутые на 90 градусов и нарисованные из одной точки. Если вы хотите посмотреть на это зрелище, то возьмите 4 разноцветные черепашки и попросите каждую из них нарисовать кривую дракона. При этом для согласованной работы черепашек лучше воспользоваться примитивом для , а не примитивом скажи . Выполняя инструкцию скажи [ч1 ч2 ч3 ч4] [нечетный_отрезок 11 300] ,черепашка “ч2” начнет рисовать кривую лишь тогда, когда черепашка “ч1” закончит работу. Если же сделать черепашки главными с помощью примитива для, то все черепашки будут работать параллельно. Последнее замечание о кривой дракона: бумажное определение кривой легко преобразуется и в “глобальное” рекурсивное определение. Если посмотреть на сгиб, делящий лист бумаги пополам (на приведенном ниже рисунке он отмечен жирной точкой), то нетрудно заметить, что кривая дракона порядка k составлена из двух кривых порядка k–1, расположенных под углом 90 градусов друг к другу:
Попробуйте самостоятельно написать процедуру построения кривой дракона на основе данного описания. Несколько нерекурсивных рисунков Мне не хотелось бы, чтобы у вас создалось впечатление, будто интересные графические процедуры непременно должны быть рекурсивными. Конечно, рекурсивные процедуры (и не только графические) занимают большую долю среди Лого-процедур, а в нашем тексте они занимают просто львиную долю. Однако нетривиальные рисунки можно нарисовать и не прибегая к рекурсии. Следующий рисунок практически совпадает с узором, нарисованным рекурсивной процедурой треугольник, но в данном случае использовалась не рекурсия, а датчик случайных чисел.
На рисунке присутствует 4 черепашки: три из них, с именами “ч1”, “ч2” и “ч3”, расположены в углах треугольника, четвертую, самую главную, с именем “ч4”, разглядеть невозможно: она где-то внутри треугольника, но ее формой является точка — один темно-серый пиксель. Рисунок получился в результате многократного повторения следующей инструкции: мы наугад выбираем одну из вершин треугольника; находим отрезок, соединяющий черепашку “ч4” и выбранную вершину; перемещаем черепашку “ч4” в середину этого отрезка и ставим точку в этом месте. Вот формальная запись этой инструкции: ;главной черепашкой является черепашка ч4 это шаг ;случайным образом выбираем одну ;из черепашек ;ч1, ч2, ч3 и запоминаем ее имя ;в переменной угол положим [угол сл_элемент [ч1 ч2 ч3]] ;поворачиваем черепашку ч4 курсом на ;черепашку с именем :угол курс_на :угол ;проходим половину расстояния от черепашки ч4 ;до черепашки с именем :угол вп (путь :угол) / 2 ;рисуем точку там, где стоит черепашка ч4 штамп конец Здесь использованы два новых примитива: команда курс_на и датчик путь с одним аргументом, словом — именем черепашки. Команда курс_на поворачивает главную черепашку так, чтобы она “смотрела” на заданную, датчик путь сообщает расстояние от главной черепашки до заданной. Согласованные действия нескольких черепашек могут помочь нарисовать достаточно сложные кривые. Предположим, что черепашка с именем “ч1” равномерно движется по окружности, постоянно выполняя инструкцию вперед 1 направо 1 . Если вы используете программу ЛогоМиры, то проще всего записать эту инструкцию в “рюкзак” черепашки и установить режим выполнения “много раз”. Создадим еще одну черепашку с именем “ч2”, которая тоже будет постоянно выполнять свою, чуть более сложную инструкцию. Начнем с того, что инструкцией для черепашки “ч2” будет строка нов_у скажи "ч1 [у_коор] ,иными словами, мы хотим, чтобы у-координата черепашки “ч2” была такой же, как и у черепашки “ч1”. Если мы запустим обе черепашки, то увидим, что черепашка “ч1”, как и ожидалось, будет двигаться по окружности, а черепашка “ч2” будет совершать колебательные движения. Достаточно установить черепашку “ч2” горизонтально, опустить ее перо и добавить к ее инструкции равномерное движение по горизонтали: нов_у скажи "ч1 [у_коор] вперед 1 чтобы нарисовать синусоиду:
Такой же подход можно использовать при изображении других кривых, например, эллипса. Существует несколько определений эллипса, нам удобнее всего считать, что эллипс — это “деформированная” окружность: окружность, растянутая (или сжатая) вдоль какой-либо оси. Вот как можно формализовать это определение: черепашка “ч1”, как и раньше, движется по окружности. Вертикальная координата черепашки “ч2” совпадает с вертикальной координатой черепашки “ч1”, а горизонтальная — в два раза больше, чем координата черепашки “ч1”. Иными словами, черепашка “ч2” постоянно выполняет инструкцию: нов_место список 2 * скажи "ч1 [х_коор] скажи "ч1 [у_коор]
Завершая обсуждение черепашьей графики, заметим, что многие фигуры и кривые, рассмотренные нами, имеют специальные названия. Так, например, кривая, изображенная ниже, называется “снежинкой Коха”.
В названиях прочих фигур фигурируют не менее громкие имена. Мы старались не использовать подобные термины. Я боялся, что или некоторые читатели подумают, что Хельге фон Кох занимался изучением снега, или нам придется обсуждать, какими замечательными особенностями обладает кривая Коха, — и то и другое не отвечает замыслу книги. С.. Ф.. Сопрунов |
|
|
