Составить алгоритм сказки репка

Есть интересная тема, на первый взгляд мало относящаяся к алгоритмам. Она «сказочная» с одной стороны, а со стороны другой в ней есть созвучие с насущными проблемами начинающего свой профессиональный путь программиста.

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

Задача

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

Уже позже в сознательном возрасте происходит второе знакомство со сказкой. Часто это происходит в процессе чтения сказки своим детям. У меня же это знакомство случилось в старшей школе. Когда на уроках литературы нас старались научить после прочтения книги не только пересказать сюжет, но и задуматься, что и какими средствами хотел нам сказать автор в своём произведении. Те сказки, которые были выбраны для разбора в текущей статье, в большинстве не имеют известного автора. Их называют «народными». Так что́ «хотел сказать» народ своим растущим детям посредством сказки? Есть ли в сказке польза? Или сказка лишь развлечение, нужное для весёлого и красочного взаимодействия родителей со своим ребёнком?

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

Мы учим ребёнка убегать от бабушки и дедушки? Или лежать на печи и ждать волшебной щуки, исполняющей желания? Конечно, нет. Ну, или очень странно, если — да.

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

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

Рассаживаемся поудобнее. Жили-были дед и баба…

Введение

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

• классификация Аарне — Томпсона — Утера (англ. ATU Index) «Указатель сюжетов фольклорной сказки»,
• работа В.Я.Проппа «Морфология волшебной сказки»,
• статья Акименко Н.А. «Стилевые и текстообразующие характеристики английской народной сказки (диахронический аспект)»,
• статья Кретова А.А. «Фольклор и постфольклор: структура, типология, семиотика»,
• и множество других работ.

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

Где же тут будет о программировании? — спросите Вы.

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

Но в сторону обзоры и общие слова. Начнем рассматривать примеры. Первым у нас на очереди — сказочное описание структуры итерационного процесса накопления с остановкой по изменению условия:

acc = []
while not condition:
    v=next_item()
    do_some(v)
    acc.append(v)

Итерационный процесс

Какая же сказка поможет нам в разборе обусловленного цикла?

Ответим первыми строками этого ценного учебника по программированию циклов:

Жил-был старик со старухою. 
Просит старик:
— Испеки, старуха, колобок!

Да, это сказка «Колобок». Давайте рассмотрим основные элементы сюжета этой сказки.

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

Этот процесс характеризуется несколькими повторениями сходных действий. Такое повторение является одним из важных признаков цепочной сказки. В «Колобке» повторяется последовательность следующих действий:

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

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

Результат всей сказки сводится к получению песенки, описывающей историю встреч колобка:

— Не ешь меня, лиса! 
Я тебе песенку спою, — сказал 
колобок и запел:
— Я Колобок, Колобок!
Я по коробу скребен,
По сусеку метен,
На сметане мешон,
Да в масле пряжон,
На окошке стужон;
Я от дедушки ушел,
Я от бабушки ушел,
Я от зайца ушел,
Я от волка ушел,
И от медведя ушел,
А от тебя, лиса, и подавно уйду!

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

Если приводить примеры подобных «Колобку» сюжетов, то сразу можно вспомнить тождественные истории в сказках других стран. Это, например, сказка «Пряничный человечек», у главного персонажа которой не было такой приметной шарообразной формы, но приключения были почти те же. В указателе Томпсона сюжет «Колобка» отнесен в группу Z33.1 «Сбежавший блин: Женщина печёт блин, который убегает. Его тщетно пытаются поймать разные животные. В конце концов его съедает лиса».

Есть сказки подобные сказке «Колобок», которые не полностью совпадают с ней по сюжету. Например, сказка «Зайкина избушка»: про ледяную избу Лисы и лубяную избу выселенного Зайца. В этой сказке Заяц накапливал рассказ о своих встречах с неудачливыми помощниками, а условием выхода из цикла была хитрость Петуха, напустившего на Лису страху своими боевыми песенкам-страшилками. Подробности сюжета иные, а его структура полностью аналогична. Это цикл накопления с условием выхода!

Вызов подфункций

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

Нужна хорошая «функциональная» сказка. И такие тоже есть — это, например, сказка «Петушок и бобовое зернышко».

Жили-были петушок и курочка...
Клевал как-то петушок бобовые 
зернышки, да второпях и подавился. 

Задача ясна — нужно спасать Петушка. А вот решение этой задачи отличается от решения «Задачи колобка». В нём больше сходства с сюжетом «Зайкиной избушки».

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

— Кузнец, кузнец, дай скорее 
хозяину хорошую косу. 
Хозяин даст коровушке травы, 
коровушка даст молока, 
хозяюшка даст мне маслица, 
я смажу петушку горлышко: 
подавился петушок 
бобовым зернышком.

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

Так что́ есть зависимые действия? Какие есть элементарные действия? Каков способ организации этих действий с точки зрения программиста?

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

Значит, и в этой сказке есть переменная накопления. На этот раз она хранится в «курочкиной памяти». И способ пополнения данных отличается от «колобкового» способа. Посещенные персонажи перечисляются в тексте Курочки в обратном порядке. Последний посещенный персонаж упоминается первым. Это изменение неслучайно. Таким образом формируется список возвратов к предыдущим персонажам для решения всей задачи Курочки. Это же детское описание стекового способа (способ организации и манипулирования данными LIFO, методы обработки товарно-материальных ценностей FIFO и LIFO)!

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

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

Рекурсивный процесс

И уже без большого удивления после небольшого перебора запомненных в детстве сказок был обнаружен и этот образец. Сказочное описание рекурсии существует!

Нужная нам сказка сразу начинается с задачи:

Посадил дед репку. 
Выросла репка большая-пребольшая...

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

Каждый персонаж выполняет следующее действие:

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

Это же точно рекурсия?! Почему каждый новый персонаж меньше предыдущего? В детстве отвечал на этот вопрос: потому что так удобнее тянуть. Но в свете рекурсивного объяснения — ответ другой. В сказке так описано, чтобы показать, что задача на каждом шаге упрощается, и в итоге решение становится доступно даже маленькой мышке.

Это же гораздо нагляднее, чем примеры в университете с числами Фибоначчи, где рекурсия применяется для вычисления рекурсивно заданных чисел? После «Репки» сразу понятно для чего рекурсия может быть полезна, и в чём её главная ценность — способность уменьшать размер задачи разделением на несколько зависимых и одинаковых действий.

Можно здесь вспомнить многие примеры рекурсивного программного решения задач на основе принципа «Разделяй и властвуй» («Уменьшай и властвуй») — та же быстрая сортировка или бинарный поиск в отсортированном списке. Но, уверен, не стоит пробовать рассказать это ребёнку в качестве полезного образца, чтобы научить поиску решения задач, которые встретятся ему в жизни.

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

Да, очень похоже, что сказкой дети учатся создавать простейшие алгоритмы. Может такой способ обучения будет полезен или хотя бы интересен и программисту? Почти всегда это так. Но есть исключения. Способы создавать вредные алгоритмы тоже есть в детских сказках!

Вред бесконечных циклов

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

Конечно, это надо сделать в сказке!

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

while true:
    pass

def f():
    f()

def f():
    g()

def g():
    f()

У всех докучных сказок разное содержание, но выбранный для текущей статьи образец начинается просто:

Купи слона...

Вы говорите, что он Вам не нужен?

Все говорят, 
   что им слон не нужен. 
А ты возьми и купи слона...

Соглашаетесь купить?

Все соглашаются купить. 
А ты возьми и купи слона...

Окончания этой сказки не будет.

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

Ну в целом понятно. Если попробовать вставить такую сказку целиком, то это будет очень вредно даже для текущей статьи. Поэтому killall fairytale_elephant.

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

Неразрешимые задачи

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

Как показать ребенку, что́ ему делать при встрече с такой задачей?

Правильно. И это тоже проще всего сделать сказкой!

И в этом нам поможет самая «бесполезная» и «бессмысленная», как представлялось мне долгие годы, сказка. Начнём с первых строк:

Жили-были дед да баба
Была у них курочка ряба.
Снесла курочка яичко, 
не простое - золотое...

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

Варианты окончания сказки не так важны, как важна́ основа её содержания:

Дед бил, бил - не разбил.
Баба била, била - не разбила.

Здесь у программиста тоже есть прямые аналогии. В программировании пока не говорят о совсем неразрешимых задачах. Но уделяют много внимания задачам, решение которых не получить за приемлемое время. То есть программист пытается оценить насколько сильно задача неразрешима (классы сложности). Это очень важно для взрослых задач. Но ребенку объяснять это пока рановато. А вот объяснить, что некоторые задачи в нашем мире не получается решить, необходимо.

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

Мышка бежала, хвостиком задела, 
яичко упало и разбилось.

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

Выполняя анализ сказки «Курочка ряба», можно вспомнить об еще одной проблеме в задачах программирования. Корни этой проблемы кроются в соотношении класса NP-полных задач и задач класса P. Для использования многих современных средств защиты данных важен ответ на вопрос: равны ли классы P и NP. На этом ответе основываются системы шифрования, в которых сложность расшифровать данные без ключа («мышкиного хвостика») должна намного превосходить сложность расшифровки с наличием этого ключевого инструмента.

Выводы

Сказка — ложь, да в ней намек…

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

Основной вывод, формулируемый в результате выполненного нами рассмотрения детских сказок, прост. Сказки определенно полезны. Это не просто развлечение. Как минимум их можно использовать в качестве иллюстрационного материала при обучении программированию. Но это только на поверхности. А в глубине вопрос. Если сказки так близки к процессам обучения созданию алгоритмов, то имеют ли они эти процессы своей целью? Совсем иначе стоял бы этот вопрос, если бы автором проанализированных нами сказок был развлекающийся программист или математик, как это было, например, со сказками «Алиса в Стране чудес» и «Алиса в Зазеркалье».

Но автор рассмотренных сказок — народ. Так может быть, обучение детей создавать алгоритмы для решения задач — это обычная, но скрытая от внимания часть человеческой жизни?

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

Главной задачей, поставленной в научной работе, является поиск и развитие алгоритмов для синтеза алгоритмов. Эта задача из разряда «разбить золотое яичко от курочки рябы», но на текущий момент уже крепнет уверенность, что она не относится к совершенно неразрешимым. Необходимо лишь знать ключ-подход к ней. Если говорить в сказочных терминах: необходима мышка с соответствующим хвостиком…

Спасибо Вам за внимание.

Отзывы

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

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

Ссылки

• Главная страница работы (GitLab GPL): Проект «Общая теория алгоритмов»
• Вводная статья работы «Разрабатываем теорию алгоритмов как проект с открытым исходным кодом». Пожалуйста, не судите строго эту наивную публикацию «сверх-идеи» устаревшей версии 2019 года.
• Статьи серии «Что такое алгоритм?!»
  • №1 «Действие»,
  • №2 «Обусловленная и связная последовательность»,
  • №3 «Синтез алгоритма запоминанием»
  • №4 «Эволюция памяти»
  • №5 «Копирование иерархии памяти»
• Для заглавной иллюстрации к статье взят рисунок с обложки книги «Репка. Лиса и журавль». Издание Кнебель, 1916
• Иллюстрация к сказке «Колобок» и «Репка» выполнены Елизаветой Меркурьевной Бём
• Иллюстрация к сказке «Петушок и бобовое зернышко» является титульной страницей одноименной книги издательства «Малыш» 1981 г.
• Иллюстрация к сказке «Курочка Ряба» является титульной страницей одноименной книги издательства Г.Ф. Мириманова 1926 г.
• Несколько иллюстраций сделаны на основе кадров мультфильма «Следствие ведут Колобки» (1987)