Мнение

С.Ф. Сопрунов,
Москва

Что я сделал за эту ночь? Ничего нужного... Хотя нет! У кого-нибудь была в школьной программе информатики фигня под названием ЛогоМиры? Если не была, то вам не понять... А я вот скачал и целый час пытался там что-то изобразить %)

http://mukaltin.livejournal.com/124333.html

Как объясняет профессор Пейперт, один из авторов Лого, в основополагающей книге [1]: “Лого — это обозначение философии обучения с помощью расширяющейся семьи языков программирования...”. Данная статья в основном посвящена языкам программирования Лого, а не соответствующей философии обучения. Тем более мы настоятельно рекомендуем каждому педагогу, предполагающему использовать язык Лого в своей практике, прочесть указанную книгу. Вам будет чрезвычайно полезно познакомиться с замыслом создателей Лого, даже если некоторые их идеи покажутся вам спорными.

Первые версии языка Лого были разработаны в конце 60-х — начале 70-х годов в Массачусетсском технологическом институте (MIT) группой под руководством Пейперта. С тех пор Лого превратилось в обширное семейство языков. Конечно, язык Лого в этом смысле не уникален — для большинства языков программирования, таких, как С++, имеется семейство различных версий как самого языка, так и соответствующих сред разработки. Однако семейству Лого присуща некоторая специфика. Версии Лого отличаются не столько тем, на какой платформе (Windows, Macintosh и пр.) или в какой версии операционной системы реализован язык, а тем, какому кругу пользователей адресована та или иная версия.

Рис. 1. Программа в ПеровЛого и результат ее выполнения

Существуют версии Лого, предназначенные для использования в начальной школе. Примером такой версии является ПервоЛого [2], в которой программа записывается в виде последовательности специальных значков (иконок).

К подобным версиям некоторые традиционные понятия языков программирования, например синтаксис, просто не применимы. С другой стороны, существуют версии Лого, такие, как StarLogo [3], адресованные студентам университета и исследователям. Язык StarLogo предназначен для моделирования взаимодействия большого количества объектов (например, моделирования дорожного движения). Такое моделирование требует столь значительных вычислительных ресурсов, что вначале StarLogo удалось реализовать только на суперкомпьютере MIT, и лишь позже появились реализации для персональных компьютеров. Неудивительно, что разработчики StarLogo пожертвовали некоторыми привычными особенностями языка Лого ради эффективности реализации.

Отдельную группу образуют версии языка, предназначенные для управления роботами. Примером подобного языка является CricketLogo, контролирующий поведение миниатюрного робота — Cricket’а [4].

Рис. 2. Cricket

Разработчики реализовали его на встроенном в Cricket микрокомпьютере с общей памятью всего 6 Кб. Ясно, что такие версии Лого неизбежно обладают существенными ограничениями.

Таким образом, нужно помнить о том, что, говоря далее о Лого, мы подразумеваем “большинство версий Лого” или “наиболее распространенные версии Лого” — в отношении отдельных версий Лого наши утверждения будут просто-напросто неверны.

Далее, следует иметь в виду, что во многих версиях Лого (ImaginLogo, ПервоЛого, ЛогоМиры и пр.) язык Лого является центральным, но не единственным элементом программной среды. В таких программных средах, которые иногда называют универсальными творческими средами, имеются, например, встроенный графический редактор, средства работы с мультимедиа и пр. Язык Лого является ядром подобной среды, именно с помощью этого языка пользователь описывает поведение и взаимодействие различных объектов своего проекта. Однако универсальный характер среды позволяет преподавателю организовать работу так, чтобы изучение программистских конструкций являлось не самоцелью, а было бы “побочным эффектом” достижения содержательной (с точки зрения ученика) цели: моделирования физического процесса, создания компьютерной игры и пр.

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

Во-первых, Лого является открытой средой. То есть не программа определяет, чем должен заниматься пользователь: выполнить некоторое упражнение, решить указанную задачу, — а пользователь (в нашем случае ученик совместно с преподавателем) выбирает, чем именно он планирует заниматься. Дело среды — предоставить пользователю удобные и естественные средства выполнения запланированной им работы.

Как мы уже упоминали, Лого претендует на то, чтобы быть достаточно универсальным инструментом. Поэтому черепашки — традиционно основные объекты Лого — должны быть достаточно универсальными исполнителями. Они должны уметь рисовать узоры на экране, изображать персонажей в мультфильме, моделировать движение планет и соударение атомов и т.д.

Часто цитируется утверждение, что “у Лого нет ни порога, ни потолка” [5]. Об “отсутствии потолка” — о том, что Лого является полноценным языком программирования, мы поговорим позже. Отсутствие же порога означает, что у ученика есть возможность делать простую, но содержательную работу практически сразу после знакомства с компьютерной средой. Мы не хотим, чтобы ученик предварительно изучал сложные синтаксические правила, знакомился с тем, как следует оформлять текст программы, как запускать ее на выполнение и т.д.

Этому способствует режим прямого выполнения, присутствующий почти во всех версиях Лого. Инструкция, написанная в специальном окне (поле команд), может быть немедленно выполнена; тут же, на экране, пользователь видит результат выполнения инструкции. Следующая простая текстовая инструкция эквивалентна картиночной инструкции на рис. 1:

повтори 36 [вперед 120 направо 170]

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

Позже мы подробнее поговорим о синтаксисе языка, пока же вам придется поверить на слово, что формальный синтаксис чрезвычайно прост, чтобы не сказать — “примитивен”. Простота синтаксиса не является сама по себе существенным достоинством языка — нас более интересует, является ли язык удобным инструментом для выражения наших мыслей. Однако в случае Лого синтаксис простой и удобный, что облегчает жизнь начинающему программисту, работающему с простыми программами. С другой стороны, простой синтаксис может осложнить поиск ошибки в сложной программе.

Эти три качества — прямое выполнение, простота библиотеки процедур и простой синтаксис — во многом унаследованы от предка Лого — языка Лисп [6]. Основной областью применения этого языка являются задачи искусственного интеллекта. При исследовании подобных задач важна не столько эффективность программы (т.е. скорость выполнения, экономия памяти), сколько возможность просто модифицировать алгоритм, сравнить разные модификации программы и т.д.

Простота структуры языка Лого (и Лиспа) базируется на том, что Лого — интерпретируемый, а не компилируемый язык. Процесс компиляции состоит, грубо говоря, в том, что все написанные пользователем процедуры переводятся в машинные коды. Только после такого перевода компьютер может запустить написанную пользователем программу. У интерпретируемых языков этап компиляции отсутствует. При запуске пользовательской инструкции специальная программа-интерпретатор последовательно читает, декодирует и выполняет инструкцию “слово за словом”. Если в процессе выполнения инструкции встретился вызов пользовательской процедуры, то интерпретатор приступает к чтению текста этой процедуры и т.д. Конечно, интерпретация имеет много других достоинств (и недостатков) по сравнению с компиляцией, кроме простоты структуры языка.

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

Последнее замечание касается рекурсии. Конечно, большинство языков программирования допускает рекурсивный вызов процедур. Но зачастую рекурсивные программы рассматриваются как что-то экзотическое, программистам не рекомендуется без крайней необходимости пользоваться этой конструкцией. В Лого рекурсия является одним из основных приемов программирования. Используемые в Лого структуры данных — списки (о них мы поговорим позже) — ориентированы на использование в рекурсивных программах. Реализуя язык Лого, разработчики предполагают, что рекурсия будет использоваться повсеместно, и прилагают специальные усилия к тому, чтобы рекурсивные вызовы не снижали эффективность программ. Достаточно заметить, что во многих версиях Лого нет никаких способов организовать цикл, кроме уже упомянутой простой команды повтори, — все более сложные циклы реализуются с помощью рекурсии.

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

Обратимся к начальной школе. В настоящее время Лого является одной из самых популярных сред в информатическом образовании в начальной школе. Как было уже сказано, Лого является открытой средой — она не указывает ученику, что и когда следует делать за компьютером. Тем более Лого не навязывает преподавателю единственно правильный способ использования данной компьютерной среды. Несмотря на это, по нашему мнению, Лого наиболее плодотворно используется в сочетании с проектным подходом. Под проектом мы понимаем задание в свободной форме, выполнение которого требует достаточно большого времени. В процессе работы над проектом ученик уточняет задание, корректирует его. Критерием “правильности” выполнения проекта является не столько мнение критиков (учителя, родителей, одноклассников), сколько мнение автора — удалось ли ему реализовать свой замысел, работает ли программа так, как было задумано. Чаще всего проект, как и большинство творческих работ, не бывает окончательно завершенным — в процессе работы над проектом у ученика возникают новые идеи о том, как может быть продолжена и усовершенствована работа. Примеры простых проектов для начальной школы приведены в [7].

Рассмотрим подробнее уже упоминавшуюся среду ПервоЛого. Команды управления черепашками представлены в виде картинок (иконок). Это не только облегчает еще не слишком грамотным программистам запись и чтение инструкций, но и избавляет их от синтаксических ошибок: любая последовательность команд синтаксически правильна. Конечно, содержательные ошибки — инструкция работает не так, как задумано — остаются. Очень важно выработать у ученика “правильное” отношение к ошибкам. Ошибка — это не низкая оценка, выставленная учителем или компьютером выполненной работе (или тем более самому ученику). Нахождение и устранение ошибок — обычный этап любой нетривиальной работы. Обнаруженная ошибка — не повод для огорчения, а повод для размышления и анализа причин, вызвавших ошибку. Такое отношение к ошибкам, конечно, необходимо не только в школе и не только на занятиях информатики. Разработчики Лого придавали большое значение формированию подобного отношения, что заметно, в частности, в формулировке сообщений компьютера об ошибках. Так, компьютер не сообщает: “вы написали непонятную инструкцию текст_инструкции” или “инструкция текст_инструкции неверна”, а “не знаю, как выполнить
текст_инструкции”. Компьютер выступает в качестве доброжелательного партнера, старающегося выполнить порученную работу, однако он все понимает буквально, ему трудно понять, что ученик “имел в виду”, отдавая то или иное приказание.

Конечно, картиночный язык ПервоЛого неизбежно ограничен, но его возможностей хватает, в частности, для реализации существенной части традиционного Лого — черепашьей геометрии. Простейших команд: вперед и назад на указанное расстояние, повернись на заданный угол, подними перо и опусти перо (у черепашки имеется перо, которым она рисует во время движения) — достаточно для создания весьма сложных изображений. Управляя черепашкой с помощью этих команд, ученики знакомятся с такими важными геометрическими понятиями, как расстояние и направление. Причем “знакомятся” не в школьном смысле этого слова, а в буквальном: эти понятия становятся их добрыми знакомыми, привычным инструментом. “Если я поверну руль вот так, на 90°, то угол будет как в квадрате, а мне нужно повернуть не так круто — может, 60°?”. Чрезвычайно важно, что ученику не так уж трудно представить “себя черепашкой”, он может постараться понять, как он сам должен был бы двигаться, чтобы выполнить требуемое действие. В затруднительной ситуации предложите ученику выйти из-за компьютера, стать так, как сейчас стоит управляемая им черепашка, и постараться проанализировать, какие должны быть дальнейшие шаги. Например, не многие ученики могут сразу научить черепашку рисовать окружность. Однако пройти по кругу и заметить, что “я все время немножко иду вперед и немножко поворачиваю”, не так трудно — а это уже практически готовая инструкция для черепашки. Игнорируйте то, что в классе не принято расхаживать, — в компьютерном классе всегда происходит много необычного.

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

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

Черепашья графика является почтенной, очень важной и чрезвычайно увлекательной областью Лого, но возможности ПервоЛого отнюдь не исчерпываются черепашьей графикой. Эта среда включает в себя такие инструменты, как графический редактор, средства работы с мультимедиа, что позволяет учащимся создавать мультфильмы, делать собственные компьютерные игры и пр. Как мы уже замечали ранее, наиболее интересных результатов добиваются ученики в тех классах, где не запоминают наизусть список команд черепашки и не заучивают, как работают разные кнопки графического редактора, а предлагают выполнить содержательную (с точки зрения ученика) работу.

Рис. 3.

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

Рис. 4. Титульный лист льбома по сказке “Дюймовочка”

Хотя, по существу, ученики знакомятся с программированием, термин “программирование” практически не используется в классе. Ученики говорят о том, что они “учат черепашку” или “объясняют что-то черепашке”. В начальной школе программирование на Лого является органической частью создания компьютерных проектов. Нам кажется весьма полезным, чтобы и сама информатика в начальных классах тоже не была бы чем-то отдельным, изолированным, а органически сочеталась с остальной школьной и внешкольной деятельностью учеников. Добиться этого не просто, не все здесь зависит исключительно от преподавателя информатики. Однако в тех случаях, когда удается организовать такую межпредметную деятельность, результаты могут получиться достаточно интересными.

Рис. 5. Набор форм к сказке “Гадкий утенок” (московская школа № 1811).

Ученики на уроке технологии сделали из бумаги объемные изображения персонажей сказки, сфотографировали их и вставили в альбом ПервоЛого. Теперь каждый ученик может попробовать “оживить” персонажи и сделать мультфильм по данной сказке

Завершая обсуждение ПервоЛого, как примера среды Лого для начальной школы, заметим следующее: хотя “язык” ПервоЛого прост, его нельзя считать примитивным. Разработчики старались, например, дать возможность ребенку работать с такими современными концепциями, как программирование, управляемое событиями (event-driven programming). В жизни черепашки могут произойти разные события: во время движения она может столкнуться с другой черепашкой, попасть на поле заданного цвета, получить сообщение (в ПервоЛого черепашки могут посылать сообщения друг другу). Ребенок может объяснить черепашке, как ей следует реагировать на то или иное событие. Таким образом, во многих случаях управление черепашкой состоит не в указании последовательности действий, которые ей следует совершить, а в сообщении ей “правил поведения” в проекте.

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

В Лого имеются данные трех типов: числа, слова и списки. В числах и словах (конечных последователях символов) нет ничего специфического — вы можете выполнять основные математические операции над числами; работая со словами, вы можете “склеить” два слова и получить новое слово; можете выяснить, является ли слово пустым; можете выяснить, какой символ находится на i-м месте в слове; можете получить новое слово, отбросив первую или последнюю букву непустого слова и т.д. Традиционно константы типа слово обозначаются открывающей кавычкой, закрывающая кавычка не ставится — так, "привет — это пятибуквенное слово.

Список — это конечный набор элементов, каждый элемент может быть или числом, или словом, или списком. Основные операции со списками: выяснить, является ли список пустым; добавить новый элемент в начало (конец) имеющегося списка; получить первый (последний) элемент непустого списка; отбросить первый (последний) элемент непустого списка. Константы типа список ограничиваются квадратными скобками “[”, “]”. Так, [4 [a d [c d]] привет] — это список из трех элементов, первый элемент — число 4; третий — слово “привет”; второй — список из трех элементов, последний элемент которого — список из двух слов.

В Лого имеются команды и функции (функции традиционно называются датчиками). Выполнение команды приводит к некоторому (явному или скрытому) изменению состояния системы, результатом выполнения датчика является некоторое значение. Так, команда вперед перемещает черепашку на расстояние, указанное единственным аргументом команды; датчик случайный возвращает случайное число из диапазона, определяемого его единственным аргументом; у датчика цвет_поля нет аргументов, он сообщает цвет экрана в том месте, где находится черепашка. Термин “датчик” был выбран потому, что в Лого у многих функций нулевое число аргументов, а математики не любят функции с нулевым числом аргументов, не являющиеся константами. Команды и датчики могут быть встроенными в среду (примитивами) или созданными пользователем.

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

вперед 200 нов_цвет элемент случайный 4 [красный синий зеленый]

Здесь выполняются две команды: уже знакомая нам команда вперед и команда нов_цвет — команда, изменяющая цвет черепашки. У последней команды один аргумент: имя (или номер) цвета. Значение этого аргумента сообщает датчик элемент с двумя аргументами — номер элемента и список (или слово), из которого мы выбираем элемент. Второй аргумент в вызове датчика элемент задан константой [красный синий зеленый], значение первого аргумента сообщает датчик случайный с одним аргументом — числом. В данном случае случайный 4 случайным образом выбирает целое число от 0 до 3, если выпадет 0, то выполнение инструкции приведет к ошибке.

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

повтори случайный 100 элемент случайный 4 [[вперед 10][назад 10][направо 20]]

Аналогично, имеется команда если с двумя аргументами: слово и список. Действие команды состоит в том, что если значение первого аргумента — слово “да”, то выполняется инструкция, содержащаяся во втором аргументе. Если значение первого аргумента — слово “нет”, то команда если не делает ничего. Если значение первого аргумента — какое-то иное слово, то выполнение команды приведет к ошибке. Обычно значение первого аргумента сообщается датчиком — “логическим датчиком”, значением которого всегда является слово “да” или “нет”, например: если равно? 0 случайный 10 [сообщи "Повезло!"?]

В том же стиле происходит и работа с переменными: есть команда пусть с двумя аргументами: первый аргумент слово (имя переменной), второй — произвольного типа (значение). Действие команды пусть состоит в том, что в переменную с указанным именем помещается заданное значение. Датчик значение с одним аргументом типа слово (имя переменной) сообщает текущее значение указанной переменной. Поскольку значения переменных приходится извлекать очень часто, в Лого существует сокращение “:” — выражение значение ”имя_переменной эквивалентно выражению :имя_переменной (например, значение ”скорость эквивалентно :скорость).

Возможность использовать команды и датчики вместо синтаксических конструкций — это специфика интерпретируемого языка. Рассмотрим характерный пример проявления этой специфики: примитив делай, аналог которого отсутствует в большинстве компилируемых языков. У этого примитива один аргумент, значением аргумента должен быть текст корректной инструкции Лого (или корректного вызова датчика). Действие примитива состоит в выполнении заданной инструкции или, соответственно, в вызове датчика (в последнем случае выполнение примитива делай вернет полученное значение). Как обычно, нет никаких ограничений на вид аргумента, команды делай — это может быть константа или вызов какого-либо датчика, например, получение значения переменной. Примитив делай является чрезвычайно мощным инструментом — по существу, он позволяет программно сформировать в какой-либо переменной или в текстовом окне текст процедуры (на Лого) и использовать его.

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

это while :условие-цикла :тело-цикла

если не делай :условие-цикла [стоп]

делай :тело-цикла

while :условие-цикла :тело-цикла

конец

После этого можно, например, использовать инструкцию while [х_коор < 200][вперед 1] и пр.

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

Прежде всего стоит познакомить ваших учеников с черепашьей графикой (если они не познакомились с ней в начальной школе). Работа с графикой во “взрослых” версиях Лого (например, в версии ЛогоМиры, которую мы и будем использовать далее) обогащается, в частности, благодаря использованию двух фундаментальных понятий. Это уже упоминавшаяся рекурсия и понятие переменной.

;у процедуры спираль один

;числовой аргумент — шаг.

;Первая строка — заголовок

;процедуры: служебное слово

;это, имя процедуры и список

;формальных параметров.

это спираль :шаг

;выражение :имя_переменной ;сообщает значение переменной

вперед :шаг направо 61

спираль :шаг + 0.5

;служебное слово конец

;в отдельной строке

;завершает описание

;процедуры

конец

Рис. 6. Процедура спираль и результат ее работы с начальным шагом 10.

Как изменится фигура, если на каждом шаге менять не только расстояние, но и угол поворота? Символ “;” указывает в Лого на комментарии

Разнообразные узоры и фракталы естественно описываются в терминах рекурсии, что позволяет непосредственно программировать их в Лого. Бесконечные рекурсивные вызовы не представляют проблемы для пользователя, поскольку пользователь видит процесс работы программы и может в любой момент прервать ее выполнение. Но, конечно, черепашья графика не ограничивается узорами и спиралями. Тому, кто всерьез заинтересовался черепашьей геометрией, мы советуем прочесть прекрасную книгу [8]. Одна из самых интересных идей этой книги — реализация сферической геометрии — изложена в [9].

Как и в начальной школе, существенное место в средней школе занимает междисциплинарное использование Лого. Как мы уже упоминали, среда Лого предоставляет удобные средства моделирования физических процессов, статистических экспериментов и т.д. Конечно, существует множество профессионально сделанных программных сред, предназначенных, например, для моделирования физических экспериментов. Стоит ли вашим ученикам тратить время и силы на разработку собственных “микромиров”? Это непростой вопрос. Мы полагаем, что в ряде случаев познавательная ценность разработки собственной среды существенно выше, чем использования готовой. Эта разница подобна разнице в программировании алгоритма сортировки и использовании функции сортировки из стандартной библиотеки.

Вернемся к нашей основной теме — программированию на языке Лого. Справедливо утверждение о том, что язык программирования отражает некоторую область задач, решения которых естественно реализуются в данном языке. Более того, язык программирования, который мы используем, влияет на наш подход к поиску решения задачи, влияет в конечном итоге на стиль нашего мышления. В чем же специфика программирования на Лого, какие задачи естественно реализуются в этом языке, какой стиль решения традиционных программистских задач можно назвать “решением в стиле Лого”?

Эти вопросы подробно обсуждаются в классическом трехтомнике [10]. В этой книге, являющейся вводным курсом для профессиональных программистов, рассматриваются такие нетривиальные темы, как конечные автоматы, построение компиляторов и пр. Мы, конечно, не готовы здесь обсуждать столь сложные темы и ограничимся несколькими простыми примерами.

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

привет

приве

прив

при

пр

п

Вот один из вариантов такой программы:

это треугольник :слово

если пусто? :слово [стоп]

покажи :слово

треугольник кпсл :слово

конец

Датчик пусто? возвращает “да”, если его аргумент — пустое слово или список; датчик кпсл (с одним аргументом — слово или список) отбрасывает последний элемент аргумента (последний символ в случае слова). Смысл команды покажи очевиден. Тем, кто считает данный пример слишком тривиальным, предлагаем написать программу, печатающую строки в обратном порядке: для слова “привет” результат должен выглядеть так:

п

пр

при

прив

приве

привет

Обратимся теперь к двум традиционным программистским задачам: сортировке и поиску. Многие эффективные методы сортировки основаны на следующей (рекурсивной) процедуре: мы делим исходный набор на несколько частей, сортируем каждую часть отдельно и объединяем отсортированные части. Примером такого подхода является упрощенный метод быстрой сортировки списка чисел: мы удаляем первое число из списка и разбиваем оставшийся список на две части — числа, меньшие удаленного (“голова” списка), и числа, большие или равные удаленному (“хвост” списка). Потом мы отдельно сортируем голову и хвост списка и получаем отсортированный список, выписав голову списка, удаленный элемент и хвост списка. Это словесное описание практически непосредственно переводится в программу:

это быстрая_сортировка :список

если пусто? :список [выход :список]

положим [гол_хв голова_хвост прв :список кпрв :список]

выход (предложение быстрая_сортировка

прв :гол_хв

прв :список

быстрая_сортировка псл :гол_хв)

конец

Команда выход аналогична слову return в С, она используется при записи функции, эта команда прерывает выполнение процедуры-функции, значением функции является значение аргумента команды выход. Команда положим создает и инициализирует локальную переменную (в нашем случае — переменную гол_хв). Датчик предложение объединяет все свои аргументы в один список; поскольку у этого датчика может быть любое число аргументов, то вызов этого датчика заключается в круглые скобки. Функции прв, псл, кпрв возвращают первый элемент списка, последний элемент списка и список без первого элемента соответственно. Пользовательская функция голова_хвост (не выписанная здесь) получает на вход два аргумента — число (границу) и список чисел и возвращает список из двух элементов (списков): первый список включает элементы исходного списка, меньшие границы, второй — все прочие.

В случае сортировки мы использовали списки простейшей структуры — списки, элементами которых являются числа; рассматривая поиск, мы будем, по существу, использовать рекурсивную (древесную) структуру списков.

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

[

[58 Venezuela]

[

[44 United Kingdom]

[

[33 France]

[]

[]

]

[

[52 Mexico]

[]

[]

]

]

[

[91 India]

[]

[

[213 Algeria]

[]

[]

]

]

]

Вот текст соответствующей программы:

это поиск :база :код

если пусто? :база [выход "]

положим [главный прв прв :база]

если :код = :главный

[выход элемент 2 прв :база]

если :код < :главный

[выход поиск элемент 2 :база :код]

выход поиск элемент 3 :база :код

конец

Смысл датчика элемент понятен — он сообщает элемент с указанным номером из заданного списка.

Мы упоминали о том, что современные версии Лого позволяют использовать параллельные процессы. Согласованные действия участников таких процессов могут существенно упростить решение некоторых задач. Допустим, мы хотим нарисовать график синусоиды:

 Рис. 7

На рис. 7 одна черепашка (с именем “окружность”) движется по окружности, бесконечно повторяя инструкцию вперед 1 направо 1. Инструкция второй черепашки чуть сложнее: Х-координата ее местоположения равномерно увеличивается,
Y-координата ее местоположения совпадает с
Y-координатой черепашки “окружность”. Вот формальный текст инструкции второй черепашки (для удобства чтения текст разбит на две строчки):

нов_х х_коор + 1

нов_у скажи "окружность [у_коор]

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

Дополнительные вопросы

В каждом из перечисленных ниже пунктов мы предлагаем вам ответить не только на непосредственно заданные вопросы, но и на дополнительные: “Если вы считаете, что задание, приведенное в данном пункте, заслуживает изучения, то как вы организуете работу с подобным заданием в классе? Если вы считаете, что задание не заслуживает изучения, то почему?”. Пункты 1—4 предполагают использование ПервоЛого или ЛогоМиров (на ваше усмотрение), для работы с пунктами 5—8 ЛогоМиры существенно предпочтительнее. Сведения о Лого, изложенные в данной статье, могут быть недостаточны для точных формальных ответов на поставленные вопросы.

1. Чтобы нарисовать окружность, можно попросить черепашку выполнить инструкцию повтори много_раз [вперед 1 направо 1] (точное число повторений нам сейчас не важно). Что нужно изменить в инструкции, чтобы нарисовать окружности большего и меньшего размера? Как научить черепашку рисовать снеговика?

2. После выполнения инструкции повтори 4 [вперед 100 направо 90] черепашка нарисует квадрат и вернется в исходное положение, после выполнения инструкции повтори 3 [вперед 100 направо 120] черепашка нарисует треугольник и тоже вернется в исходное положение. Верно ли, что при любом значении угла поворота, после некоторого числа повторений черепашка возвращается в исходное положение? Если да, то как количество повторений связано с величиной угла? Как научить черепашку рисовать пятиконечную звезду?

3. Черепашка должна моделировать автомобиль, едущий по извилистой дороге, — дорога рисуется определенным цветом на листе и может иметь произвольную форму. Как научить черепашку не вылетать при движении с дороги? (Указание: воспользуйтесь умением черепашки реагировать на цвет листа.)

4. Есть ли в вашем классе ученики, у которых день рождения совпадает (приходится на один и тот же день в году)? Многие люди находят удивительным, что если в классе более 25 человек, то шансы на то, что такие ученики найдутся, более 50%. Как можно было бы в Лого подтвердить это утверждение? Воспользуйтесь тем, что черепашка может двигаться на случайное расстояние, оставлять метку там, где она находится, и проверять цвет поля.

5. Смоделируйте движение корабля в реке. Используйте стандартные элементы (например, бегунки) для задания собственной скорости корабля и скорости течения реки. Используйте кнопку для изменения направления движения корабля (по течению/против течения). Предусмотрите в проекте какие-то средства для измерения пройденного расстояния и времени.

6. К двоичному поиску: напишите процедуру, создающую базу нужного нам вида. Процедура получает на вход список пар [код название], список упорядочен по возрастанию кодов. Результатом работы процедуры должна быть база данных. Указание: используйте подпроцедуру, получающую на вход список L и положительное целое число N и возвращающую список из трех элементов: подсписок элементов L с номерами меньше N, элемент с номером N и подсписок элементов L с номерами больше N.

7. Вот схематичное описание программы “Угадай животное”: пользователь загадывает животное, программа пытается его угадать, задавая вопросы, на которые пользователь отвечает “да” или “нет”.
В конце концов программа высказывает догадку (например: “Ваше животное — кошка?”). Если программа ошиблась, то она просит пользователя сообщить загаданное животное и вопрос, который помогает отличить загаданное животное от догадки, высказанной программой. В нашем примере, если пользователь загадал тигра, то таким вопросом мог бы быть “Это дикое животное?”. Программа самообучающаяся — она “запоминает” полученные сведения и использует их в следующих турах игры. Сделайте эскиз программы “Угадай животное”. Указание: данная программа аналогична программе поиска, отличие состоит в процедуре пополнения базы данных.

8. Трудно ли научить черепашку рисовать эллипс? Поможет ли здесь наличие нескольких черепашек?

Литература

1. Пейперт С. Переворот в сознании: дети, компьютеры и плодотворные идеи. М.: Педагогика, 1989.

2. Сопрунов С.Ф., Ушакова А.С., Яковлева Е.И. ПервоЛого 3.0: Справочное пособие. М.: Институт новых технологий, 2006.

3. Resnick M. Turtles, termites, and traffic jams: explorations in massively parallel microworlds, MIT Press, 1997.

4. http://www.handyboard.com/cricket/

5. Harper D. Logo: theory and practice. Brooks/Cole Publishing Company, 1989.

6. Маурер У. Введение в программирование на языке ЛИСП. М.: Мир, 1976.

7. Яковлева Е.И. ЛогоМозаика. М.: Институт Новых Технологий, 2000.

8. Abelson H., diSessa A. Turtle Geometry: The Computer as a Medium for Exploring Mathematics. MIT Press, 1986.

9. Сопрунов С.Ф. Черепашка, которая живет на сфере. / Информатика, № 4, 2006, с. 9–13.

10. Harvey B. Computer Science Logo Style 2/e — 3 vol. set, MIT Press, 1997.