20.12.2002
Так получилось, что последние обновления статей на сайте происходят парами, навевая, тем самым, ассоциации с детским стишком Агнии Барто: "Мы с Тамарой ходим парой...". Однако, если в двух предыдущих случаях "Твикс" подавался в связи поступлением материалов в одной упаковке, то в данной ситуации "спаривание" произошло в связи с практически одновременным выходом статей и близостью тематик. Предлагаются:
Статьи перекликаются между собой рассуждениями о рекурсиях и итерациях, аппеляцией к одному и тому же "раздражителю" (Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы), а также общему источнику вдохновения, известному чуть ли ни с детства - ханойской башне.
Быть рекурсией прекрасно, ну а циклом лучше?
Интересно сопоставить мотивы статей.
Из заключения "Ханойских башен и автоматов" следует, что "Несмотря на то, что длина автоматных программ превышает размер традиционных, такие программы обладают тем преимуществом, что по их тексту может быть формально построен граф переходов, который является наиболее компактной и удобной для визуализации и документирования графической формой представления программ и их алгоритмов". Основной же идеей является демонстрация, на конкретной задаче, методов преобразования рекурсиивных функций в конкретную конечно автоматную модель реализуемую в дальнейшем с использованием SWITCH-технологии.
В "Раздражителе" проблема конечности состояний преодолевалась тем, что на рабочую память, используемую функциями выходов, не накладывается никаких ограничений. Это легко и вполне естественно позволяет моделировать самые сложные алгоритмы. Необходимость же получить на выходе нужную автоматную модель вполне объяснима целевыми задачами.
Общеизвестно, что преобразование непараметризированных левых и правых рекурсий в итерации протекает без каких-либо проблем. Непараметризированная и неконцевая рекурсия достаточно просто преобразуется в итерацию, если использовать стек. (Вспоминается программирование на когда-то нерекурсивных Бейсике и Фортране...) Да и стоит ли говорить о проблемах преобразования рекурсий в итерации и обратно? Математически они являются эквивалентным представлением рекуррентности, а процесс преобразования давно изучен и неплохо формализован.
"Фокус-покус и никакого..."
Моя статья о лабиринтах Ханойских башен была вызвана сомнением в высказанном авторами предположении о неконцевой рекурсии в Ханойских башнях. Поэтому я попытался показать, что исходная задача имеет рекурсии на концах, а их спецификой является наличие параметрических выражений, что и затрудняет прямое сведение к итерациям. Однако, подобное сведение возможно если подыскать формулу, обеспечивающую получение результатов, выполняемое ранее параметрическими выражениями. Именно сам подход я и считаю основной идеей статьи. Остальное: получение формулы, дополнительных (более быстрых) решений и сопоставление с автоматными решениями - это вполне естественное оформление материалов подобного плана.
Рассмотренный прием является универсальным и легко применим в других аналогичных ситуациях. Если для ханойской башни получить нужную формулу удалось не сразу, то во многих подобных ситуациях концевая параметрическая рекурсия преобразуется в итерацию достаточно быстро. Можете сами попробовать на функции, вычисляющей факторил как с использованием левой, так и правой рекурсии. Аргумент функции является параметром, преобразуемым в "формулу".
"Что такое хорошо и что такое плохо?"
Мотивами "Борьбы с рекурсией" явились следующие причины: "Первая – скорость работы алгоритмов, вторая – проблемы с реализацией рекурсии... ...насколько вообще актуальна проблема устранения рекурсии."
В результате провозглашается: "Что такое рекурсия, необходима ли...? ...нужна, если скорость работы программы имеет малое значение, если не нужно решать проблему параллельного функционирования программных модулей (прежде всего в рамках самого приложения), то устранением рекурсии вряд ли имеет смысл вообще заниматься.".
"Бить будете? - Еще как!"
В данном случае я не смог обойтись простым представлением статей. В форуме появились "наезды", естественно, со стороны Вячеслава. Он также посоветовал мне не забыть побрюзжать по этому поводу.
В связи с отсутствием мазохических наклонностей я не собираюсь заниматься самоистязанием и посыпать голову пеплом по поводу возможных глюков в моих рассуждениях. Поэтому продолжу парные катания, опираясь на цитаты из форума.
ВЛ: В отношении количества состояний АЛ ошибается. И, кажется, мы с ним это выяснили: его решение требует еще большего числа внутренних состояний.
Одним из скользких рассуждений моей статьи является указание на то, что автомат, выстраиваемый по итеративной программе имеет одно состояние. Естественно, я опирался на наличие одного условного оператора во внешнем цикле и не учитывал сложности формулы, так как подсчет нулей в цикле - это проблема функции выхода, а не перехода. Предполагалось, что формула - это другая сущность, не важная для понимания задачи. Все линейные фрагменты тоже были отнесены не к переходам, а к функциям выхода. Возможно, стоило добавить начально-конечное состояние. Но я пренебрег им. Но даже, если я и ошибаюсь, то не велика беда. В конечном случае каждый волен считать состояния в свою пользу. Толку от этого числа никакого. За что бороться?
ВЛ: А к чему вообще эта «битва» за количество состояний? Это «битва» за эффективность решения, т.е. за его время и за его параллелизм. Количество внутренних состояний определяет ВРЕМЯ исполнения одной итерации и количество ПОСЛЕДОВАТЕЛЬНЫХ ШАГОВ в рамках одной итерации. Подчеркну – итерации, но не времени и параллелизма всего алгоритма, которое определяется количеством итераций или глубиной рекурсии (хотя время алгоритма и зависит от времени одной его итерации, а распараллеливание итераций определяется их зависимостью друг от друга по данным).
Это «битва» и за ясность решения и за его сложность, т.к. чем меньше внутренних состояний, тем меньше, как правило, и сложность решения (хотя это и не всегда так, но это уже отдельный разговор). А чем меньше сложность, тем легче его понять.
Честно говоря, я ничего не понял. Поскольку время выполнения зависит не от количества состояний, а числа переходов между ними, проделанным в ходе выполнения программы. Кроме этого на скорость вычисления влияет и время затраченное на выполнение функций выхода. В подобных ситуациях автомат с одним состоянием может оказаться медленнее автомата с гораздо большим их числом. Однако считать состояния тоже можно по-разному, то есть, в свою пользу. Поэтому можно предложить универсальный эквивалент: считать состоянием значение счетчика команд процессора. Тогда число состояний будет равно количеству машинных команд, а скорость определится количеством команд, выполненных во время работы программы. Включая и команды, вошедшие в состав библиотеки FSA.
Непонятные оговорки о параллелизме - это отдельная тема. Но чуть ниже.
Критиковать мы все можем..., но позвольте заметить...
Собственно говоря, раздел "брюзжалки" был заведен как раз для того, чтобы я не стал штатным литературным критиком. А тут такой базар... "Ах, Ты меня...! Ну, получай..."
"Борьба с рекурсией" в авторском исполнении свелась к поглощению библиотекой FSA этого механизма. Рекурсивные вызовы процедурной программы, были подменены эквивалентными порожденияими вложенных автоматов. Следует отметить, что подобный прием регулярно встечался на практике, в том числе и в рамках моего курса по трансляторам. Понятно, что свои рекурсивно-автоматные рассуждения я тоже выстраивал на чужих плечах. Поэтому еще раз сошлюсь на давно обещаную ссылку:
Торгашев В.А. Управление вычислительными процессами в машинах с динамической архитектурой. - В кн. Вычислительные системы и методы в автоматизации исследований и управления. М.: Наука, 1982, с. 172-187.
Процитирую фрагмент, показывающий использование автоматной трактовки применительно к мультипроцессорным системам:
"В данной работе рассматривается виртуальная мащина с параллельным упралением, базирующаяся на математической модели параллельных вычислений, предложенной Бардзинем (Бардзинь Я.М. Проблемы универсальности в теории растущих автоматов. - Докл. АН СССР, 1964, 157, №3, с. 542-545). Эта модель представляет собой сеть конечных автоматов, для каждого из которых, помимо обычных функций переходов и выходов, определены две специальные функции, первая из которых изменяет связи автомата с другими автоматами сети, а вторая порождает новые автоматы, что приводит к росту сети. Таким образом, модель соответствует растущему автомату."
Не является и новым откровение о повышении скорости алгоритма за счет дополнительной памяти. В незапамятные время существовал выбор между табличными и алгоритмическими методами решения задачи. Именно за счет дополнительной памяти, повышались характеристики арифметических ускорителей и спецпроцессоров. Зачастую, нехватка памяти приводила к поиску таблично-алгоритмических методов решения, обеспечивающих промежуточный баланс между производительностью и стоимостью. Но это все решается в рамках конкретного алгоритма, а не комплекса независимых одновременно выполняющихся задач, каждая из которых строится по своему принципу. Поэтому лично мне непонятна связь с графической системой Windows. Общеизвестно, что обычный вывод реализуется посредством работы процессора, что и ведет в мультипрограммном режиме к удлинению времени выполнеия всех других программ. И проблема эта в современных игрушках решается достаточно стандартно: путем разработки графических ускорителей, работающих одновременно с процессором, использующих более эффективные алгоритмы формирования изображений, дополнительную память и специализированные библиотеки.
Далее. На мой взгляд и потери рекурсии в большей степени связаны не со стеком, а с вызовом процедур, так как никто и ничто не мешает обмениваться рекурсивным процедурам данными напрямую через общую память. Гонять данные через стек - это, опять-таки, проблема алгоритма. Не всегда это и нужно. В том же рекурсивном факториале аргумент можно и не передавать от функции к функции. Это также показывает, что от рекурсии до цикла - один шаг.
int n, t;
int fact() {
// FACT:
if(n > 1) {
t *= n--;
fact(); // goto FACT;
}
return t;
}
int factorial_3(int x) {
t = 1;
n = x;
return fact();
}
Этот вариант кода заимствован из времен программирования на ассемблере PDP-11, позволяющем достаточно эффективно сформировать рекурсивный вызов. А если учесть, что доступ к стеку и прочим дополнительным приладам нерекурсивных программ тоже осуществляется посредством процедур, то... Кроме этого, конвейеризация команд в современных микропроцессорах обеспечивает дополнительное сглаживание этой проблемы. Поэтому, повышение скорости решения задачи во многом определяется не рекурсией, а использованием табличных методов, основанных на предварительном вычислении неизменяющихся данных или устранении повторных вычислений. Это как раз и показывает алгоритм Аккермана.
Предлагая свои рекурсивные решения автор "Борьбы..." осознает, что они гораздо медленне обычных процедурных программ. Поэтому, для обоснование их полезности, приходится обращаться параллелизму, который демонстрируется в приаттаченных примерах, "одновременно" вычисляющих Ханойские башни, факториал и функции Аккермана. Хотя, для достижения подобного эффекта можно было бы просто запустить каждую из этих задач на своем компьютере. Если же необходим реальный параллельный расчет, а не умозрительные игры на основе автоматов, можно воспользоваться кластерными вычислениями. Для этого существуют, например, MPI или PVM.
На мой взгляд основной особенностью FSA является не параллелизм работы, а предоставление программисту инструмента, который, за счет ортогонального расшепления, позволяет в дальнешем выполнять переходы для разных автоматов в едином цикле. При этом каждый из автоматов задается отдельным монолитным описанием. Таким образом достигается неявное и последовательное переключение между отдельными автоматами построенной модели в моменты их перехода из одного состояния в другое. В той же Windows подобные переключения приходится задавать явно путем посылки сообщений из функций обратного вызова. Как и во всеех подобных случаях, явный и неявный подходы обладают как своими достоинствами, так и недостатками.
Подобные неявные трюки делаются во всех мультипрограмммных системах, основным отличием которых является прозрачная дискретизация подзадач по времени, а не по произвольно выстроенным состояниям. Можно много говорить о потенциальной скорости и параллелизме автоматов, реально наблюдая псевдопараллельность небольших программок.
Параллельные миры
В мире существет много религий, о чем достаточно ясно выразился В. Высоцкий: "Кто верит в Аллаха, кто в Исууса, кто ни во что не верит, даже в черта, назло всем...". Программирование, как и многие другие сферы человеческой деятельности не избежало подобных разделений по методологиями парадигмам и прочим параметрам. Бывает, что детальное познание какого-то одного инструмента приводит истовой вере в его повсеместной необходимости. И это не обязательно автоматное программирование. Сторонники различных подходов зачастую разговаривают друг с другом на разных языках. Вполне естественно, что их доводы не только не разбиваются друг о друга: они просто сосуществуют независимо и параллельно в одном пространстве в соответствии с принципом суперпозиции.
На мой взгляд проблема рекурсии совершенно не связана с формализацией, наглядностью представления, скоростью работы, параллельным функционированием и другими факторами. Есть прикладные задачи которые весьма эффективно отражаются в автоматных моделях. Следовательно, нет смысла выдумывать для них рекурсивное решение. Но есть и другие задачи, для которых получение быстрого решения осуществляется с точностью до наоборот. Не следует забывать и о существовании многих иных подходов к разработке программ. То есть, а опять говорю о разноликости программирования: "Мамы вские нужны, мамы всякие важны".
|